Abstract
“Mirror, mirror, on the wall, who is the fairest of them all?”
The Evil Queen
What is a fair way to assign rooms to several housemates and divide the rent between them? This is not just a theoretical question: many people have used the Spliddit website to obtain envy-free solutions to rent division instances. But envy freeness, in and of itself, is insufficient to guarantee outcomes that people view as intuitive and acceptable. We therefore focus on solutions that optimize a criterion of social justice, subject to the envy-freeness constraint, in order to pinpoint the “fairest” solutions. We develop a general algorithmic framework that enables the computation of such solutions in polynomial time. We then study the relations between natural optimization objectives and identify the maximin solution, which maximizes the minimum utility subject to envy freeness, as the most attractive. We demonstrate, in theory and using experiments on real data from Spliddit, that the maximin solution gives rise to significant gains in terms of our optimization objectives. Finally, a user study with Spliddit users as subjects demonstrates that people find the maximin solution to be significantly fairer than arbitrary envy-free solutions; this user study is unprecedented in that it asks people about their real-world rent division instances. Based on these results, the maximin solution has been deployed on Spliddit since April 2015.
- A. Abdulkadiroğlu, T. Sönmez, and M. U. Ünver. 2004. Room assignment-rent division: A market approach. Social Choice and Welfare 22, 3 (2004), 515--538.Google ScholarCross Ref
- A. Alkan, G. Demange, and D. Gale. 1991. Fair allocation of indivisible goods and criteria of justice. Econometrica 59, 4 (1991), 1023--1039. Google Scholar
- E. Aragones. 1995. A derivation of the money Rawlsian solution. Social Choice and Welfare 12 (1995), 267--276. Google ScholarCross Ref
- S. J. Brams and D. M. Kilgour. 2001. Competitive fair division. Journal of Political Economy 109 (2001), 418--443. Google ScholarCross Ref
- E. Budish, G. P. Cachon, J. Kessler, and A. Othman. 2017. Course match: A large-scale implementation of approximate competitive equilibrium from equal incomes for combinatorial allocation. Operations Research 65, 2 (2017), 314--336. Google ScholarDigital Library
- I. Caragiannis, D. Kurokawa, H. Moulin, A. D. Procaccia, N. Shah, and J. Wang. 2016. The unreasonable fairness of maximum Nash product. In Proceedings of the 17th ACM Conference on Economics and Computation (EC’16). 305--322.Google Scholar
- N. Dupuis-Roy and F. Gosselin. 2011. The simpler, the better: A new challenge for fair-division theory. In Proceedings of the 33rd Annual Meeting of the Cognitive Science Society (CogSci’11). 3229--3234.Google Scholar
- D. Foley. 1967. Resource allocation and the public sector. Yale Economics Essays 7 (1967), 45--98.Google Scholar
- J. Goldman and A. D. Procaccia. 2014. Spliddit: Unleashing fair division algorithms. SIGecom Exchanges 13, 2 (2014), 41--46. Google ScholarDigital Library
- J. R. Green and J.-J. Laffont. 1979. Incentives in Public Decision Making. North Holland.Google Scholar
- C.-J. Haake, M. G. Raith, and F. E. Su. 2002. Bidding for envy-freeness: A procedural approach to -player fair-division problems. Social Choice and Welfare 19 (2002), 723--749. Google ScholarCross Ref
- D. K. Herreiner and C. D. Puppe. 2009. Envy freeness in experimental fair division problems. Theory and Decision 67, 1 (2009), 65--100. Google ScholarCross Ref
- D. K. Herreiner and C. D. Puppe. 2010. Inequality aversion and efficiency with ordinal and cardinal social preferences—An experimental study. Journal of Economic Behavior & Organization 76, 2 (2010), 238--253. Google ScholarCross Ref
- F. Klijn. 2000. An algorithm for envy-free allocations in an economy with indivisible objects and money. Social Choice and Welfare 17 (2000), 201--215. Google ScholarCross Ref
- S. Kohler. 2013. Envy can promote more equal division in alternating-offer bargaining.Journal of Neuroscience, Psychology, and Economics 1, 6 (2013), 31--41. Google ScholarCross Ref
- A. Mas-Colell, M. D. Whinston, and J. R. Green. 1995. Microeconomic Theory. Oxford University Press.Google Scholar
- G. Schneider and U. S. Krämer. 2004. The limitations of fair division: An experimental evaluation of three procedures. Journal of Conflict Resolution 48, 4 (2004), 506--524.Google ScholarCross Ref
- F. E. Su. 1999. Rental harmony: Sperner’s lemma in fair division. American Mathematical Monthly 106, 10 (1999), 930--942. Google ScholarCross Ref
- L.-G. Svensson. 1983. Large indivisibles: An analysis with respect to price equilibrium and fairness. Econometrica 51, 4 (1983), 939--954. Google ScholarCross Ref
- L.-G. Svensson. 2009. Coalitional strategy-proofness and fairness. Economic Theory 40, 2 (2009), 227--245. Google ScholarCross Ref
- K. Tadenuma and W. Thomson. 1991. No-envy and consistency in economies with indivisible goods. Econometrica 59, 6 (1991), 1755--1767. Google ScholarCross Ref
- K. Tadenuma and W. Thomson. 1995. Refinements of the no-envy solution in economies with indivisible goods. Theory and Decision 39, 2 (1995), 189--206. Google ScholarCross Ref
- R. Velez. 2017. Sharing an increase of the rent fairly. Social Choice and Welfare 48, 1 (2017), 59--80. Google ScholarCross Ref
Index Terms
- Which Is the Fairest (Rent Division) of Them All?
Recommendations
Which Is the Fairest (Rent Division) of Them All?
EC '16: Proceedings of the 2016 ACM Conference on Economics and ComputationWhat is a fair way to assign rooms to several housemates, and divide the rent between them? This is not just a theoretical question: many people have used the Spliddit website to obtain envy-free solutions to rent division instances. But envy freeness, ...
Which is the fairest (rent division) of them all?: extended abstract
IJCAI'17: Proceedings of the 26th International Joint Conference on Artificial IntelligenceWhat is a fair way to assign rooms to several housemates, and divide the rent between them__ __ This is not just a theoretical question: many people have used the Spliddit website to obtain envy-free solutions to rent division instances. But envy ...
Robust rent division
NIPS '22: Proceedings of the 36th International Conference on Neural Information Processing SystemsIn fair rent division, the problem is to assign rooms to roommates and fairly split the rent based on roommates' reported valuations for the rooms. Envy-free rent division is the most popular application on the fair division website Spliddit. The ...
Comments