More Web Proxy on the site http://driver.im/

research-article

Equitable Rent Division

Author:

Rodrigo A. VelezAuthors Info & Claims

ACM Transactions on Economics and Computation (TEAC), Volume 6, Issue 2

Article No.: 9, Pages 1 - 25

https://doi.org/10.1145/3274528

Published: 29 September 2018 Publication History

Abstract

How should a group of roommates allocate the rooms and contributions to rent in the house they lease? Economists have provided partial answers to this question in a literature that spans the last 40 years. Unfortunately, these results were developed in a non-linear fashion, which obscures them to the non-specialist. Recently, computer scientists have developed an interest in this problem, advancing from an algorithmic complexity perspective. With this new interest gaining traction, there is an evident need for a coherent development of the results in economics literature. This article does so. In particular, we build connections among results that were seemingly unrelated and considerably simplify their development, fill in non-trivial gaps, and identify open questions. Our focus is on incentives issues, the area in which we believe economists have more to contribute in this discussion.

References

[1]

Ahmet Alkan. 1994. Monotonicity and envyfree assignments. Economic Theory 4, 4 (1994), 605--616.

[2]

Ahmet Alkan, Gabrielle Demange, and David Gale. 1991. Fair allocation of indivisible goods and criteria of justice. Econometrica 59, 4 (1991), 1023--1039. http://www.jstor.org/stable/2938172

[3]

Tommy Andersson and Lars Ehlers. 2013. An algorithm for envy-free allocations in an economy with indivisible objects and money. Retrieved on March 3, 2018 from http://www.cireqmontreal.com/wp-content/uploads/cahiers/17-2013-cah.pdf Cahier 17-2013, CIREQ.

[4]

Tommy Andersson, Lars Ehlers, and Lars-Gunnar Svensson. 2014. Budget-balance, fairness and minimal manipulability. Theoretical Economics 9, 3 (2014), 753--777. http://econtheory.org/ojs/index.php/te/article/view/20140753/0

[5]

Tommy Andersson, Lars Ehlers, and Lars-Gunnar Svensson. 2014. Least manipulable envy-free rules in economies with indivisibilities. Mathematical Social Sciences 69 (2014), 43--49.

[6]

Enriqueta Aragones. 1995. A derivation of the money Rawlsian solution. Social Choice and Welfare 12, 3 (1995), 267--276.

[7]

H. Āzacis. 2008. Double implementation in a market for indivisible goods with a price constraint. Games and Economic Behavior 62 (2008), 140--154.

[8]

Carmen Beviá. 2010. Manipulation games in economies with indivisible goods. International Journal of Game Theory 39, 1 (2010), 209--222.

[9]

Olivier Bochet and Toyotaka Sakai. 2007. Strategic manipulations of multi-valued solutions in economies with indivisibilities. Mathematical Social Sciences 53, 1 (2007), 53--68.

[10]

D. Foley. 1967. Resource allocation and the public sector. Yale Economic Essays 7 (1967), 45--98.

[11]

Yuji Fujinaka and Takuma Wakayama. 2015. Maximal manipulation of envy-free solutions in economies with indivisible goods and money. Journal of Economic Theory 158, Part A (2015), 165--185.

[12]

Y. Gal, M. Mash, A. D. Procaccia, and Y. Zick. 2017. Which is the fairest (rent division) of them all? Journal of the ACM 64, 6 (Nov. 2017), Article 39, 22 pages.

Digital Library

[13]

David Gale. 1984. Equilibrium in a discrete exchange economy with money. International Journal of Game Theory 13, 1 (1984), 61--64.

Digital Library

[14]

J. Goldman and A. D. Procaccia. 2014. Spliddit: Unleashing fair division algorithms. SIGecom Exchanges 13, 2 (2014), 41--46.

Digital Library

[15]

Jerry R. Green and Jean-Jacques Laffont. 1979. Incentives in Public Decision Making. North-Holland, Amsterdam.

[16]

Flip Klijn. 2000. An algorithm for envy-free allocations in an economy with indivisible objects and money. Social Choice and Welfare 17, 2 (2000), 201--215.

[17]

Serge-Christophe Kolm. 1971. Justice et Equité. Paris: Cepremap (an English translation is: Justice and Equity, 1997, Cambridge, MA: MIT Press).

[18]

E. Maskin. 1999. Nash equilibrium and welfare optimality. Review of Economic Studies 66 (1999), 83--114. http://www.jstor.org/stable/2566947 first circulated in 1977.

[19]

Antonio Nicoló and Rodrigo A. Velez. 2017. Divide and compromise. Mathematical Social Sciences 90 (2017), 100--110. In honor of Hervé Moulin.

[20]

Ariel Procaccia, Rodrigo A. Velez, and Dingli Yu. 2018. In Proceedings of the 2018, 32nd AAAI Conference on Artificial Intelligence. AAAI.

[21]

Roy Radner. 1980. Collusive behavior in noncooperative epsilon-equilibria of oligopolies with long but finite lives. Journal of Economic Theory 22, 2 (1980), 136--154.

[22]

Walter Stromquist. 1980. How to cut a cake fairly. American Mathematical Monthly 87, 8 (1980), 640--644. http://www.jstor.org/stable/2320951

[23]

Francis E. Su. 1999. Rental harmony: Sperner’s lemma in fair division. American Mathematical Monthly 106, 10 (1999), 930--942. http://www.jstor.org/stable/2589747

[24]

L.-G. Svensson. 1983. Large indivisibles: An analysis with respect to price equilibrium and fairness. Econometrica 51 (1983), 939--954. http://www.jstor.org/stable/1912044

[25]

Koichi Tadenuma and William Thomson. 1991. No-envy and consistency in economies with indivisible goods. Econometrica 59, 6 (1991), 1755--1767. http://www.jstor.org/stable/2938288

[26]

Koichi Tadenuma and William Thomson. 1995. Games of fair division. Games and Economic Behavior 9, 2 (May 1995), 191--204. http://ideas.repec.org/a/eee/gamebe/v9y1995i2p191-204.html.

[27]

K. Tadenuma and W. Thomson. 1995. Refinements of the no-envy solution in economies with indivisible goods. Theory and Decision 39 (1995), 189--206.

[28]

William Thomson. 1983. The fair division of a fixed supply among a growing population. Mathematics of Operations Research 8, 3 (1983), 319--326. http://www.jstor.org/stable/3689303

Digital Library

[29]

Hal R. Varian. 1974. Equity, envy, and efficiency. Journal of Economic Theory 9, 1 (1974), 63--91.

[30]

Hal R. Varian. 1976. Two problems in the theory of fairness. Journal of Public Economics 5, 3--4 (1976), 249--260.

[31]

Rodrigo A. Velez. 2011. Are incentives against economic justice? Journal of Economic Theory 146 (2011), 326--345.

[32]

Rodrigo A. Velez. 2015. Sincere and sophisticated players in an equal-income market. Jouranl of Economic Theory 157, 0 (2015), 1114--1129.

[33]

Rodrigo A. Velez. 2016. Fairness and externalities. Theoretical Economics 11 (2016), 381--410.

[34]

Rodrigo A. Velez. 2017. Sharing an increase of the rent fairly. Social Choice and Welfare 48, 1 (2017), 59--80.

[35]

Rodrigo A. Velez and William Thomson. 2012. Let them cheat&excl; Games and Economic Behavior 75, 2 (2012), 948--963.

Cited By

Velez R(2023)Equitable rent division on a soft budgetGames and Economic Behavior10.1016/j.geb.2023.01.008139(1-14)Online publication date: May-2023
https://doi.org/10.1016/j.geb.2023.01.008
Arunachaleswaran EBarman SRathi N(2022)Fully Polynomial-Time Approximation Schemes for Fair Rent DivisionMathematics of Operations Research10.1287/moor.2021.119647:3(1970-1998)Online publication date: 1-Aug-2022
https://dl.acm.org/doi/10.1287/moor.2021.1196
Segal-Halevi E(2022)Generalized Rental HarmonyThe American Mathematical Monthly10.1080/00029890.2022.2037988129:5(403-414)Online publication date: 13-Apr-2022
https://doi.org/10.1080/00029890.2022.2037988
Show More Cited By

Index Terms

Equitable Rent Division
1. Applied computing
  1. Law, social and behavioral sciences
    1. Economics
2. Theory of computation
  1. Theory and algorithms for application domains
    1. Algorithmic game theory and mechanism design
      1. Algorithmic mechanism design

Recommendations

Sincere and sophisticated players in the envy-free allocation problem
EC '13: Proceedings of the fourteenth ACM conference on Electronic commerce

We study the problem of allocating a collective endowment of n objects among n agents when monetary compensation is available. We require budget balance and assume complete information. We also assume that money is desirable and that no object is ...
Sincere and sophisticated players in the envy-free allocation problem
EC '13: Proceedings of the fourteenth ACM conference on Electronic commerce

We study the problem of allocating a collective endowment of n objects among n agents when monetary compensation is available. We require budget balance and assume complete information. We also assume that money is desirable and that no object is ...
The Price of Fairness for Indivisible Goods
Abstract
We investigate the efficiency of fair allocations of indivisible goods using the well-studied price of fairness concept. Previous work has focused on classical fairness notions such as envy-freeness, proportionality, and equitability. However, ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on Economics and Computation

ACM Transactions on Economics and Computation Volume 6, Issue 2

May 2018

159 pages

ISSN:2167-8375

EISSN:2167-8383

DOI:10.1145/3241735

Editors:
David Pennock
Microsoft
,
Ilya Segal
Stanford University

Issue’s Table of Contents

Copyright © 2018 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 29 September 2018

Accepted: 01 July 2018

Revised: 01 March 2018

Received: 01 August 2017

Published in TEAC Volume 6, Issue 2

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

6
Total Citations
View Citations
244
Total Downloads

Downloads (Last 12 months)24
Downloads (Last 6 weeks)2

Reflects downloads up to 01 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Velez R(2023)Equitable rent division on a soft budgetGames and Economic Behavior10.1016/j.geb.2023.01.008139(1-14)Online publication date: May-2023
https://doi.org/10.1016/j.geb.2023.01.008
Arunachaleswaran EBarman SRathi N(2022)Fully Polynomial-Time Approximation Schemes for Fair Rent DivisionMathematics of Operations Research10.1287/moor.2021.119647:3(1970-1998)Online publication date: 1-Aug-2022
https://dl.acm.org/doi/10.1287/moor.2021.1196
Segal-Halevi E(2022)Generalized Rental HarmonyThe American Mathematical Monthly10.1080/00029890.2022.2037988129:5(403-414)Online publication date: 13-Apr-2022
https://doi.org/10.1080/00029890.2022.2037988
Sánchez Sánchez F(2022)Envy-Free Solutions to the Problem of Room Assignment and Rent DivisionGroup Decision and Negotiation10.1007/s10726-022-09779-w31:3(703-721)Online publication date: 21-Mar-2022
https://doi.org/10.1007/s10726-022-09779-w
Velez R(2022)A polynomial algorithm for maxmin and minmax envy-free rent division on a soft budgetSocial Choice and Welfare10.1007/s00355-021-01386-z59:1(93-118)Online publication date: 22-Jan-2022
https://doi.org/10.1007/s00355-021-01386-z
Andersson TEhlers L(2021)An algorithm for identifying least manipulable envy‐free and budget‐balanced allocations in economies with indivisibilitiesInternational Journal of Economic Theory10.1111/ijet.1230018:1(50-60)Online publication date: 26-Mar-2021
https://doi.org/10.1111/ijet.12300

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Issue’s Table of Contents