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.
  • 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).
  • 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.

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
  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.
  2. 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.
  3. 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.
  4. Hylland, Aanund; Zeckhauser, Richard (1979). "The Efficient Allocation of Individuals to Positions". Journal of Political Economy. 87 (2): 293. doi:10.1086/260757.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.