Random priority item allocation
From Wikipedia, the free encyclopedia
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 partners have to divide (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).
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 | 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.
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