Random priority item allocation

Last updated March 27, 2023

Random priority (RP),^[1] also called Random serial dictatorship (RSD),^[2] is a procedure for fair random assignment - dividing indivisible items fairly among people.

Suppose $n$ partners have to divide $n$ (or fewer) different items among them. Since the items are indivisible, some partners will necessarily get the less-preferred items (or no items at all). RSD attempts to insert fairness into this situation in the following way. Draw a random permutation of the agents from the uniform distribution. Then, let them successively choose an object in that order (so the first agent in the ordering gets first pick and so on).

Properties

RSD is a truthful mechanism when the number of items is at most the number of agents, since you only have one opportunity to pick an item, and the obviously dominant strategy in this opportunity is to pick the best available item.

RSD always yields an ex-post Pareto efficient (PE) outcome. Moreover, in an assignment problem, every deterministic PE assignment is the outcome of SD for some ordering of the agents.^[1]^: Lem.1

However, RSD is not ex-ante PE when the agents have Von Neumann-Morgenstern utilities over random allocations, i.e., lotteries over objects (Note that ex-ante envy-freeness is weaker than ex-post envy-freeness, but ex-ante Pareto-efficiency is stronger than ex-post Pareto-efficiency). As an example, suppose there are three agents, three items and the VNM utilities are:

	Item x	Item y
Alice	1	0.8
Bob	1	0.2
Carl	1	0.2

RSD gives a 1/3 chance of every object to each agent (because their preferences over sure objects coincide), and a profile of expected utility vector (0.6, 0.4, 0.4). But assigning item y to Alice for sure and items x,z randomly between Bob and Carl yields the expected utility vector (0.8, 0.5, 0.5). So the original utility vector is not Pareto efficient.

Moreover, when agents have ordinal rankings, RSD fails even the weaker property of sd-efficiency.^[1]^: Sec.2

When the rankings of the agents over the objects are drawn uniformly at random, the probability that the allocation given by RSD is ex-ante PE approaches zero as the number of agents grows.^[3]

An alternative rule, the probabilistic-serial rule, is sd-efficient (which implies ex-post PE) and sd-envy-free (which implies ex-ante envy-freeness), but it is not truthful. It is impossible to enjoy the advantages of both mechanisms:

With cardinal additive utility functions, no mechanism is symmetric, truthful and ex-ante PE.^[4]
With ordinal utility functions, no mechanism is sd-efficient, strategyproof, and treats equals equally.^[1]^: Thm.2

Generalizations

More objects than agents

When there are more than $n$ objects, some agents may get more than one object. There are several ways to extend RSD to this case.

One way is to define a quota for each agent (such that the sum of quotas equals the number of objects), and let each agent in turn pick items up to his/her quota. This procedure remains strategyproof, but it is very unfair.
Another way is to let each agent pick a single object, and then do another round in which each agent picks a single object, until all objects are taken; this leads to the round-robin item allocation procedure. This procedure is fairer, but it is not strategyproof.
Both procedures are special cases of a picking sequence.

General decision-making

RSD can be defined for the more general setting in which the group has to select a single alternative from a set of alternatives. In this setting, RSD works as follows: First, randomly permute the agents. Starting with the set of all alternatives, ask each agent in the order of the permutation to choose his favorite alternative(s) among the remaining alternatives. If more than one alternative remains after taking the preferences of all agents into account, RSD uniformly randomizes over those alternatives. In the item division setting mentioned earlier, the alternatives correspond to the allocations of items to agents. Each agent has large equivalence classes in his preference, since he is indifferent between all the allocations in which he gets the same item.

In this general setting, if all agents have strict preferences over the alternatives, then RSD reduces to drawing a random agent and choosing the alternative that the agent likes best. This procedure is known as random dictatorship (RD), and is the unique procedure that is efficient and strategyproof when preferences are strict.^[5] When agents can have weak preferences, however, no procedure that extends RD (which includes RSD) satisfies both efficiency and strategyproofness.^[6]

Related Research Articles

Pareto efficiency or Pareto optimality is a situation where no action or allocation is available that makes one individual better off without making another worse off. The concept is named after Vilfredo Pareto (1848–1923), Italian civil engineer and economist, who used the concept in his studies of economic efficiency and income distribution. The following three concepts are closely related:

In social choice theory, a dictatorship mechanism is a rule by which, among all possible alternatives, the results of voting mirror a single pre-determined person's preferences, without consideration of the other voters. Dictatorship by itself is not considered a good mechanism in practice, but it is theoretically important: by Arrow's impossibility theorem, when there are at least three alternatives, dictatorship is the only ranked voting electoral system that satisfies unrestricted domain, Pareto efficiency, and independence of irrelevant alternatives. Similarly, by Gibbard's theorem, when there are at least three alternatives, dictatorship is the only strategyproof rule.

Fair item allocation is a kind of a fair division problem in which the items to divide are discrete rather than continuous. The items have to be divided among several partners who value them differently, and each item has to be given as a whole to a single person. This situation arises in various real-life scenarios:

Envy-freeness, also known as no-envy, is a criterion for fair division. It says that, when resources are allocated among people with equal rights, each person should receive a share that is, in their eyes, at least as good as the share received by any other agent. In other words, no person should feel envy.

Rental harmony is a kind of a fair division problem in which indivisible items and a fixed monetary cost have to be divided simultaneously. The housemates problem and room-assignment-rent-division are alternative names to the same problem.

Envy-free (EF) item allocation is a fair item allocation problem, in which the fairness criterion is envy-freeness - each agent should receive a bundle that they believe to be at least as good as the bundle of any other agent.

In economics, dichotomous preferences (DP) are preference relations that divide the set of alternatives to two subsets: "Good" versus "Bad".

Approximate Competitive Equilibrium from Equal Incomes (A-CEEI) is a procedure for fair item assignment. It was developed by Eric Budish.

The Decreasing Demand procedure is a procedure for fair item allocation. It yields a Pareto-efficient division that maximizes the rank of the agent with the lowest rank. This corresponds to the Rawlsian justice criterion of taking care of the worst-off agent.

Fair random assignment is a kind of a fair division problem.

A simultaneous eating algorithm(SE) is an algorithm for allocating divisible objects among agents with ordinal preferences. "Ordinal preferences" means that each agent can rank the items from best to worst, but cannot (or does not want to) specify a numeric value for each item. The SE allocation satisfies SD-efficiency - a weak ordinal variant of Pareto-efficiency (it means that the allocation is Pareto-efficient for at least one vector of additive utility functions consistent with the agents' item rankings).

Various experiments have been made to evaluate various procedures for fair division, the problem of dividing resources among several people. These include case studies, computerized simulations, and lab experiments.

Truthful cake-cutting is the study of algorithms for fair cake-cutting that are also truthful mechanisms, i.e., they incentivize the participants to reveal their true valuations to the various parts of the cake.

Truthful resource allocation is the problem of allocating resources among agents with different valuations over the resources, such that agents are incentivized to reveal their true valuations over the resources.

When allocating objects among people with different preferences, two major goals are Pareto efficiency and fairness. Since the objects are indivisible, there may not exist any fair allocation. For example, when there is a single house and two people, every allocation of the house will be unfair to one person. Therefore, several common approximations have been studied, such as maximin-share fairness (MMS), envy-freeness up to one item (EF1), proportionality up to one item (PROP1), and equitability up to one item (EQ1). The problem of efficient approximately-fair item allocation is to find an allocation that is both Pareto-efficient (PE) and satisfies one of these fairness notions. The problem was first presented at 2016 and has attracted considerable attention since then.

Course allocation is the problem of allocating seats in university courses among students. Many universities impose an upper bound on the number of students allowed to register to each course, in order to ensure that the teachers can give sufficient attention to each individual student. Since the demand for some courses is higher than the upper bound, a natural question is which students should be allowed to register to each course.

Online fair division is a class of fair division problems in which the resources, or the people to whom they should be allocated, or both, are not all available when the allocation decision is made. Some situations in which not all resources are available include:

In economics and computer science, the house allocation problem is the problem of assigning objects to people with different preferences, such that each person receives exactly one object. The name "house allocation" comes from the main motivating application, which is assigning dormitory houses to students. Other commonly used terms are assignment problem and one-sided matching. When agents already own houses, the problem is often called a housing market. In house allocation problems, it is assumed that monetary transfers are not allowed; the variant in which monetary transfers are allowed is known as rental harmony.

Fair allocation of items and money is a class of fair item allocation problems in which, during the allocation process, it is possible to give or take money from some of the participants. Without money, it may be impossible to allocate indivisible items fairly. For example, if there is one item and two people, and the item must be given entirely to one of them, the allocation will be unfair towards the other one. Monetary payments make it possible to attain fairness, as explained below.

Ordinal Pareto efficiency refers to several adaptations of the concept of Pareto-efficiency to settings in which the agents only express ordinal utilities over items, but not over bundles. That is, agents rank the items from best to worst, but they do not rank the subsets of items. In particular, they do not specify a numeric value for each item. This may cause an ambiguity regarding whether certain allocations are Pareto-efficient or not. As an example, consider an economy with three items and two agents, with the following rankings:

References

1 2 3 4 Bogomolnaia, Anna; Moulin, Hervé (2001). "A New Solution to the Random Assignment Problem". Journal of Economic Theory. 100 (2): 295. doi:10.1006/jeth.2000.2710.
↑ Abdulkadiroglu, Atila; Sonmez, Tayfun (1998). "Random Serial Dictatorship and the Core from Random Endowments in House Allocation Problems". Econometrica. 66 (3): 689. doi:10.2307/2998580. JSTOR 2998580.
↑ Manea, Mihai (2009). "Asymptotic ordinal inefficiency of random serial dictatorship". Theoretical Economics. 4 (2): 165–197. hdl: 10419/150127 .
↑ Zhou, Lin (1990). "On a conjecture by gale about one-sided matching problems". Journal of Economic Theory. 52: 123–135. doi:10.1016/0022-0531(90)90070-Z.
↑ Gibbard, Allan (1977). "Manipulation of schemes that mix voting with chance" (PDF). Econometrica. 45 (3): 665–681. doi:10.2307/1911681. JSTOR 1911681.
↑ Brandl, Florian; Brandt, Felix; Suksompong, Warut (2016). "The impossibility of extending random dictatorship to weak preferences". Economics Letters. 141: 44–47. arXiv: 1510.07424 . doi:10.1016/j.econlet.2016.01.028. S2CID 4917725.

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.

[bm01-1] 1 2 3 4 Bogomolnaia, Anna; Moulin, Hervé (2001). "A New Solution to the Random Assignment Problem". Journal of Economic Theory. 100 (2): 295. doi:10.1006/jeth.2000.2710.

[as98-2] Abdulkadiroglu, Atila; Sonmez, Tayfun (1998). "Random Serial Dictatorship and the Core from Random Endowments in House Allocation Problems". Econometrica. 66 (3): 689. doi:10.2307/2998580. JSTOR 2998580.

[m09-3] Manea, Mihai (2009). "Asymptotic ordinal inefficiency of random serial dictatorship". Theoretical Economics. 4 (2): 165–197. hdl: 10419/150127 .

[z90-4] Zhou, Lin (1990). "On a conjecture by gale about one-sided matching problems". Journal of Economic Theory. 52: 123–135. doi:10.1016/0022-0531(90)90070-Z.

[g77-5] Gibbard, Allan (1977). "Manipulation of schemes that mix voting with chance" (PDF). Econometrica. 45 (3): 665–681. doi:10.2307/1911681. JSTOR 1911681.

[bbs16-6] Brandl, Florian; Brandt, Felix; Suksompong, Warut (2016). "The impossibility of extending random dictatorship to weak preferences". Economics Letters. 141: 44–47. arXiv: 1510.07424 . doi:10.1016/j.econlet.2016.01.028. S2CID 4917725.

[1]

[2]

[3]

[4]

[5]

[6]