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) is a truthful mechanism. It is ex-ante envy-free, and ex-post Pareto efficient, but not ex-ante Pareto-efficient. It is a very simple mechanism that only requires agents to have ordinal ranking on individual items.
- Probabilistic Serial (PS) is an algorithm that guarantees ex-ante envy-freeness, ex-ante and ex-post Pareto efficiency, but is not truthful. It requires only ordinal ranking on items.
- 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] It is ex-ante and ex-post Pareto-efficient, and ex-ante envy-free, but not truthful. This is a more complex mechanism that requires the agents to have full cardinal utility functions (or, alternatively, ordinal ranking on lotteries).
Comparison
Hosseini, Larson and Cohen[5] compare RP to PS in various settings. They show that:
- There are situations in which each rule finds an allocation that is better to some agents and worse for other agents. 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.
- ^ 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)