IDEAS home Printed from https://ideas.repec.org/a/spr/grdene/v11y2002i5d10.1023_a1020485018300.html
   My bibliography  Save this article

Use of Linear Programming to Find an Envy-Free Solution Closest to the Brams–Kilgour Gap Solution for the Housemates Problem

Author

Listed:
  • Richard F. Potthoff

    (Duke University)

Abstract

Although the Gap Procedure that Brams and Kilgour (2001) proposed for determining the price of each room in the housemates problem has many favorable properties, it also has one drawback: Its solution is not always envy-free. Described herein is an approach that uses linear programming to find an envy-free solution closest (in a certain sense) to the Gap solution when the latter is not envy-free. If negative prices are allowed, such a solution always exists. If not, it sometimes exists, in which case linear programming can find it by disallowing negative prices. Several examples are presented.

Suggested Citation

  • Richard F. Potthoff, 2002. "Use of Linear Programming to Find an Envy-Free Solution Closest to the Brams–Kilgour Gap Solution for the Housemates Problem," Group Decision and Negotiation, Springer, vol. 11(5), pages 405-414, September.
    • Handle: RePEc:spr:grdene:v:11:y:2002:i:5:d:10.1023_a:1020485018300
    DOI: 10.1023/A:1020485018300
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1023/A:1020485018300
    File Function: Abstract
    Download Restriction: Access to the full text of the articles in this series is restricted.
    File URL: https://libkey.io/10.1023/A:1020485018300?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
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Steven J. Brams & D. Marc Kilgour, 2001. "Competitive Fair Division," Journal of Political Economy, University of Chicago Press, vol. 109(2), pages 418-443, April.
    2. Flip Klijn, 2000. "An algorithm for envy-free allocations in an economy with indivisible objects and money," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 17(2), pages 201-215.
    3. Claus-Jochen Haake & Matthias G. Raith & Francis Edward Su, 2002. "Bidding for envy-freeness: A procedural approach to n-player fair-division problems," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 19(4), pages 723-749.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Carraro, Carlo & Marchiori, Carmen & Sgobbi, Alessandra, 2005. "Advances in negotiation theory : bargaining, coalitions, and fairness," Policy Research Working Paper Series 3642, The World Bank.

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Francisco Sánchez Sánchez, 2022. "Envy-Free Solutions to the Problem of Room Assignment and Rent Division," Group Decision and Negotiation, Springer, vol. 31(3), pages 703-721, June.
    2. Azacis, Helmuts, 2008. "Double implementation in a market for indivisible goods with a price constraint," Games and Economic Behavior, Elsevier, vol. 62(1), pages 140-154, January.
    3. Thomson, William, 2011. "Chapter Twenty-One - Fair Allocation Rules," Handbook of Social Choice and Welfare, in: K. J. Arrow & A. K. Sen & K. Suzumura (ed.), Handbook of Social Choice and Welfare, edition 1, volume 2, chapter 21, pages 393-506, Elsevier.
    4. Andersson, T. & Svensson, L.-G. & Yang, Z., 2010. "Constrainedly fair job assignments under minimum wages," Games and Economic Behavior, Elsevier, vol. 68(2), pages 428-442, March.
    5. Atila Abdulkadiroğlu & Tayfun Sönmez & M. Utku Ünver, 2004. "Room assignment-rent division: A market approach," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 22(3), pages 515-538, June.
    6. Tommy ANDERSSON & Lars EHLERS, 2013. "An Algorithm for Identifying Agent-k-Linked Allocations in Economies with Indivisibilities," Cahiers de recherche 17-2013, Centre interuniversitaire de recherche en économie quantitative, CIREQ.
    7. Tommy Andersson & Christer Andersson, 2009. "Solving House Allocation Problems with Risk-Averse Agents," Computational Economics, Springer;Society for Computational Economics, vol. 33(4), pages 389-401, May.
    8. , & , & ,, 2014. "Budget-balance, fairness and minimal manipulability," Theoretical Economics, Econometric Society, vol. 9(3), September.
    9. Haake, Claus-Jochen & Raith, Matthias G. & Su, Francis Edward, 2017. "Bidding for envy freeness," Center for Mathematical Economics Working Papers 311, Center for Mathematical Economics, Bielefeld University.
    10. Andersson, Tommy & Ehlers, Lars & Svensson, Lars-Gunnar, 2014. "Least manipulable Envy-free rules in economies with indivisibilities," Mathematical Social Sciences, Elsevier, vol. 69(C), pages 43-49.
    11. Ning Sun & Zaifu Yang, 2009. "Strategy Proof And Privacy Preserving Fair Allocation Mechanism," The Japanese Economic Review, Japanese Economic Association, vol. 60(2), pages 143-151, June.
    12. Erel Segal-Halevi, 2019. "Generalized Rental Harmony," Papers 1912.13249, arXiv.org, revised Feb 2020.
    13. Simmons, Forest W. & Su, Francis Edward, 2003. "Consensus-halving via theorems of Borsuk-Ulam and Tucker," Mathematical Social Sciences, Elsevier, vol. 45(1), pages 15-25, February.
    14. Johannes Brustle & Jack Dippel & Vishnu V. Narayan & Mashbat Suzuki & Adrian Vetta, 2019. "One Dollar Each Eliminates Envy," Papers 1912.02797, arXiv.org.
    15. ANDERSSON, Tommy & EHLERS, Lars & SVENSSON, Lars-Gunnar, 2012. "(Minimally) 'epsilon'-Incentive Compatible Competitive Equilibria in Economies with Indivisibilities," Cahiers de recherche 2012-03, Universite de Montreal, Departement de sciences economiques.
    16. Tommy Andersson & Lars Ehlers & Lars-Gunnar Svensson, 2012. "(Minimally) ?-Incentive Compatible Competitive Equilibria in Economies with Indivisibilities," Cahiers de recherche 04-2012, Centre interuniversitaire de recherche en économie quantitative, CIREQ.
    17. Ehtamo, Harri & Kettunen, Eero & Hamalainen, Raimo P., 2001. "Searching for joint gains in multi-party negotiations," European Journal of Operational Research, Elsevier, vol. 130(1), pages 54-69, April.
    18. Nolan Miller & Alexander Wagner & Richard Zeckhauser, 2013. "Solomonic separation: Risk decisions as productivity indicators," Journal of Risk and Uncertainty, Springer, vol. 46(3), pages 265-297, June.
    19. Steven Brams & D. Kilgour & Christian Klamler, 2012. "The undercut procedure: an algorithm for the envy-free division of indivisible items," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 39(2), pages 615-631, July.
    20. Meertens, Marc & Potters, Jos & Reijnierse, Hans, 2002. "Envy-free and Pareto efficient allocations in economies with indivisible goods and money," Mathematical Social Sciences, Elsevier, vol. 44(3), pages 223-233, December.

    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:spr:grdene:v:11:y:2002:i:5:d:10.1023_a:1020485018300. 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.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with 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: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    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.