Random serial dictatorship
Random serial dictatorship (RSD),[1] also called: random priority (RP),[2] is a procedure for dividing indivisible items fairly among people. Suppose [math]\displaystyle{ n }[/math] partners have to divide [math]\displaystyle{ n }[/math] (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 is ex-ante envy-free (EF), since each agent has the same chance to appear in each position in the ordering. Obviously, it is not ex-post envy-free, since an agent who happens to be last in the random permutation might envy agents who appear earlier.
RSD always yields an ex-post Pareto efficient (PE) outcome. However, it 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 | Item z | |
|---|---|---|---|
| Alice | 1 | 0.8 | 0 |
| Bob | 1 | 0.2 | 0 |
| Carl | 1 | 0.2 | 0 |
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.[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 ex-ante PE (which implies ex-post PE) and ex-ante EF, but not truthful. There is provably no mechanism that is symmetric, truthful and ex-ante PE.[4]
Generalizations
More objects than agents
When there are more than [math]\displaystyle{ n }[/math] 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]
See also
The page on fair random assignment compares RSD to other procedures for solving the same problem, such as the probabilistic-serial rule.
References
- ↑ 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.
- ↑ 2.0 2.1 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.
- ↑ Manea, Mihai (2009). "Asymptotic ordinal inefficiency of random serial dictatorship". Theoretical Economics 4 (2): 165–197.
- ↑ 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". Econometrica 45 (3): 665–681. doi:10.2307/1911681. http://www.kellogg.northwestern.edu/research/math/papers/175.pdf.
- ↑ Brandl, Florian; Brandt, Felix; Suksompong, Warut (2016). "The impossibility of extending random dictatorship to weak preferences". Economics Letters 141: 44–47. doi:10.1016/j.econlet.2016.01.028.
 |
