Jump to content

Random priority item allocation

From Wikipedia, the free encyclopedia
This is an old revision of this page, as edited by Erel Segal (talk | contribs) at 19:51, 1 March 2017 (Assisted by Citation bot). The present address (URL) is a permanent link to this revision, which may differ significantly from the current revision.

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

Suppose partners have to divide (or less) different items among them. Since the items are indivisible, some partners will necessarily get the less-preferred items (or no items at all). RP 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

RP is fair, at least in the sense of equal treatment of equals, since each agent has the same chance to appear in each position in the ordering.

RP 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 just to pick the best available item.

However, RP is not Pareto efficient when the agents have Von Neumann-Morgenstern utilities over random allocations (lotteries over objects). In fact, there exits no mechanism that satisfies symmetry, truthfulness and Pareto efficiency.[3]

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

RP 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]

See also

References

  1. ^ 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.
  2. ^ a b 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.
  3. ^ Zhou, Lin (1990). "On a conjecture by gale about one-sided matching problems". Journal of Economic Theory. 52: 123. doi:10.1016/0022-0531(90)90070-Z.