IDEAS home Printed from https://ideas.repec.org/a/inm/ormoor/v47y2022i3p1970-1998.html
   My bibliography  Save this article

Fully Polynomial-Time Approximation Schemes for Fair Rent Division

Author

Listed:
  • 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)

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.

Suggested Citation

  • Eshwar Ram Arunachaleswaran & Siddharth Barman & Nidhi Rathi, 2022. "Fully Polynomial-Time Approximation Schemes for Fair Rent Division," Mathematics of Operations Research, INFORMS, vol. 47(3), pages 1970-1998, August.
    • Handle: RePEc:inm:ormoor:v:47:y:2022:i:3:p:1970-1998
    DOI: 10.1287/moor.2021.1196
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/moor.2021.1196
    Download Restriction: no
    File URL: https://libkey.io/10.1287/moor.2021.1196?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:inm:ormoor:v:47:y:2022:i:3:p:1970-1998. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    We have no bibliographic references for this item. You can help adding them by using this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Chris Asher (email available below). General contact details of provider: https://edirc.repec.org/data/inforea.html .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.