Fair random assignment
Fair random assignment is a kind of a fair division problem.
In the assignment problem, n objects have to be allocated fairly among n agents. Each agent has to receive exactly one object. Examples include the assignment of jobs to workers, of rooms to housemates, of time slots to users of a common machine, and so on.
In general, a fair assignment may be impossible to attain. For example, if Alice and Batya both prefer the eastern room to the western room, only one of them will get it and the other will be envious. In the random assignment setting, fairness is attained using a lottery. So in the simple example above, Alice and Batya will toss a fair coin and the winner will get the eastern room.
There are several ways to extend the "coin toss" method to situations in which there are more than two agents, and they may have different preference relations on the objects:[1][2][3]
- Random Priority (RP, aka Random Serial Dictatorship or RSD) is a very simple mechanism that only requires agents to have ordinal ranking on individual items. It chooses a random priority-ordering on the items and lets each agent in turn pick his favorite remaining item.
- Probabilistic Serial (PS) is another mechanism that works only with ordinal ranking on items. Agents "eat" their favorite remaining items in a constant speed, and the fraction each agent managed to eat is his/her probability to get this item.
- Competitive Equilibrium from Equal Incomes (CEEI) is a market-based mechanism: each item is viewed as a divisible commodity. Each agent is given -share of each commodity, then the agents are allowed to trade until there is equilibrium.[4] This is a more complex mechanism that requires the agents to have full cardinal utility functions (or, alternatively, ordinal ranking on tteries).
Properties
One desired property of a random assignment rule is Pareto efficiency (PE). There are two variants of PE:
- Ex-post PE means that, after the final allocation is determined, no other allocation is better for some agent and at least as good for the others. All three rules above (RP, PS and CEEI) are ex-post PE.
- Ex-ante PE is a stronger property. It means that no other lottery is better for some agent and at least as good for the others. To define this property, it is important to know how agents compare lotteries. CEEI is ex-ante PE when agents compare lotteries based on their expected utility. PS is ex-ante PE when agents compare lotteries by stochastic dominance (this property is called ex-ante sd-PE). In contrast, RP is not ex-ante PE.
Another desired property is envy-freeness (EF). Again, there are two variants of EF:
- Ex-post EF means that, after the final allocation is determined, no agent prefers the allocation of another agent. No rule satisfies this strong property; indeed, it may be impossible to find an ex-post EF allocation of indivisible objects.
- Ex-ante EF means that no agent prefers the lottery of another agent. Again, defining this property requires to know how agents compare lotteries. CEEI is ex-ante EF w.r.t. expected utilities. PS is ex-ante EF w.r.t. stochastic dominance (this property is called ex-ante sd-EF). RP is weakly ex-ante sd-EF.
A third desired property is truthfulness (also called strategyproofness). CEEI is not truthful. PS is weakly sd-truthful when there is at most one object per person. RP is sd-truthful in this case, and it can be extended in a truthful way also to the general case when there are more objects than people. The following table compares the various rules' properties (the RP and PS columns are based on [5]):
| #items ≤ #agents | #items > #agents | |||||
|---|---|---|---|---|---|---|
| RP | PS | CEEI | RP | PS | CEEI | |
| Ex-ante efficiency | No | sd-PE | PE | No | sd-PE | PE |
| Ex-ante fairness | Weak sd-EF | sd-EF | EF | Weak sd-EF | sd-EF | EF |
| Truthfulness | sd-truthful | Weak sd-truthful | No | sd-truthful* | No | No |
Comparison
Hosseini, Larson and Cohen[5] compare RP to PS in various settings. They show that:
- When there are at most 2 objects and at most 3 agents, RP and PS return the same allocation.
- When there are at most 2 objects, for any number of agents, PS is truthful and RP is envy-free.
- When there are 3 or more objects (and 3 or more agents), RP and PS may return different allocations, and no allocation Pareto-dominates the other. For example, suppose there are three objects a,b,c and three agents with preference-rankings (1) a>c>b, (2) a>b>c, (3) b>a>c. Then, to agent (1), both RP and PS give 1/2 a + 1/2 c; to agent (2), RP gives 1/2 a + 1/6 b + 1/3 c while PS gives 1/2 a + 1/4 b + 1/4 c which is stochastically-dominant; and to agent (3), RP gives 5/6 b + 1/6 c while PS gives 3/4 b + 1/4 c which is stochastically-dominated. So (1) is indifferent, (2) strictly prefers PS and (3) strictly prefers RP.
See also
- Rental harmony is a variant of the assignment problem in which fairness is attained using monetary payments, instead of randomization.
- Fair item allocation is a setting in which agents may get more than one item.
References
- ^ 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.
- ^ Yılmaz, Özgür (2009). "Random assignment under weak preferences". Games and Economic Behavior. 66: 546–558. doi:10.1016/j.geb.2008.04.017.
- ^ Katta, Akshay-Kumar; Sethuraman, Jay (2006). "A solution to the random assignment problem on the full preference domain". Journal of Economic Theory. 131: 231–250. doi:10.1016/j.jet.2005.05.001.
- ^ Hylland, Aanund; Zeckhauser, Richard (1979). "The Efficient Allocation of Individuals to Positions". Journal of Political Economy. 87 (2): 293. doi:10.1086/260757.
- ^ a b Hadi Hosseini, Kate Larson, Robin Cohen (2018). "Investigating the characteristics of one-sided matching mechanisms under various preferences and risk attitudes".
{{cite web}}: CS1 maint: multiple names: authors list (link) CS1 maint: url-status (link)