Fully Polynomial-Time Approximation Schemes for Fair Rent Division

Eshwar Ram Arunachaleswaran (), Siddharth Barman () and Nidhi Rathi ()
Additional contact information
Eshwar Ram Arunachaleswaran: Department of Computer and Information Science, University of Pennsylvania, Philadelphia, Pennsylvania 19104
Siddharth Barman: Department of Computer Science and Automation, Indian Institute of Science, Bangalore 560012, India
Nidhi Rathi: Department of Mathematics, Indian Institute of Science, Bangalore 560012, India

Mathematics of Operations Research, 2022, vol. 47, issue 3, 1970-1998

Abstract: We study the problem of fair rent division that entails splitting the rent and allocating the rooms of an apartment among agents in a fair manner (i.e., under the imposed rents, no agent has a strictly stronger preference for any other agent’s room). The utility functions specify the cardinal preferences of the agents for the rooms for every possible room rent. Although envy-free solutions are guaranteed to exist under reasonably general utility functions, efficient algorithms for finding them were known only for quasilinear utilities . This work addresses this notable gap and develops a fully polynomial-time approximation scheme for fair rent division with minimal assumptions on the utility functions. Envy-free solutions correspond to equilibria of a two-sided matching market with monetary transfers; hence, this work also provides efficient algorithms for finding approximate equilibria in such markets. We complement the algorithmic results by proving that the fair rent division problem lies in the intersection of the complexity classes polynomial parity arguments on directed graphs and polynomial local search.

Keywords: Primary: 91B32; secondary: 91B15; 91B68; 91B14; fair rent division; envy-freeness; resource allocation; FPTAS; fixed points; equilibrium computation (search for similar items in EconPapers)
Date: 2022
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/moor.2021.1196 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ormoor:v:47:y:2022:i:3:p:1970-1998

Access Statistics for this article

More articles in Mathematics of Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().