Strategic fair division
Strategic fair division is the branch of fair division in which the participants are assumed to hide their preferences and act strategically in order to maximize their own utility, rather than playing sincerely according to their true preferences.
To illustrate the difference between strategic fair division and classic fair division, consider the divide and choose procedure for dividing a cake among two agents. In classic fair division, it is assumed that the cutter cuts the cake into two pieces that are equal in his eyes, and thus he always gets a piece that he values at exactly 1/2 of the total cake value. However, if the cutter knows the chooser's preferences, he can get much more than 1/2 by acting strategically. For example, suppose the cutter values a piece by its size while the chooser values a piece by the amount of chocolate in it. So the cutter can cut the cake into two pieces with almost the same amount of chocolate, such that the smaller piece has slightly more chocolate. Then, the chooser will take the smaller piece and the cutter will win the larger piece, which may be worth much more than 1/2 (depending on how the chocolate is distributed).
The research in strategic fair division has two main branches.
One branch is related to game theory and studies the equilibria in games created by fair division algorithms:
- The Nash equilibrium of the Dubins-Spanier moving-knife protocol;[1]
- The Nash equilibrium and subgame-perfect equilibrium of generalized-cut-and-choose protocols;[2]
- The equilibria of envy-free protocols for allocating an indivisible good with monetary compensations.[3]
- The price of anarchy of Nash equilibria of two mechanisms for homogeneous-resource allocation: the Fisher market game and the Trading Post game.[4]
The other branch is related to mechanism design and aims to find truthful mechanisms for fair division, in particular:
- Truthful cake-cutting;
- Truthful resource allocation;
- Truthful fair division of rooms and rent.
References
- ↑ Brânzei, Simina; Miltersen, Peter Bro (2013). "Equilibrium Analysis in Cake Cutting". Proceedings of the 2013 International Conference on Autonomous Agents and Multi-agent Systems. AAMAS '13 (Richland, SC: International Foundation for Autonomous Agents and Multiagent Systems): 327–334. ISBN 9781450319935. http://dl.acm.org/citation.cfm?id=2484920.2484974.
- ↑ Brânzei, Simina; Caragiannis, Ioannis; Kurokawa, David; Procaccia, Ariel D. (2016-02-21). "An Algorithmic Framework for Strategic Fair Division" (in en). Thirtieth AAAI Conference on Artificial Intelligence 30. doi:10.1609/aaai.v30i1.10042. https://www.aaai.org/ocs/index.php/AAAI/AAAI16/paper/view/12294.
- ↑ Tadenuma, Koichi; Thomson, William (1995-05-01). "Games of Fair Division". Games and Economic Behavior 9 (2): 191–204. doi:10.1006/game.1995.1015. ISSN 0899-8256.
- ↑ Brânzei, Simina; Gkatzelis, Vasilis; Mehta, Ruta (2016-07-06). "Nash Social Welfare Approximation for Strategic Agents". arXiv:1607.01569 [cs.GT].
 |  |
