IDEAS home Printed from https://ideas.repec.org/a/eee/ejores/v271y2018i2p620-631.html
   My bibliography  Save this article

Two-player fair division of indivisible items: Comparison of algorithms

Author

Listed:
  • Kilgour, D. Marc
  • Vetschera, Rudolf

Abstract

We study algorithms for allocating a set of indivisible items to two players who rank them differently. We compare eleven such algorithms, mostly taken from the literature, in a computational study, evaluating them according to fairness and efficiency criteria that are based on ordinal preferences as well as Borda counts. Our study is exhaustive in that, for every possible instance of up to twelve items, we compare the output of each algorithm to all possible allocations. We thus can search for “good” allocations that no algorithm finds. Overall, the algorithms do very well on ordinal properties but fall short on Borda properties. We also discuss the similarity of algorithms and suggest how they can be usefully combined.

Suggested Citation

  • Kilgour, D. Marc & Vetschera, Rudolf, 2018. "Two-player fair division of indivisible items: Comparison of algorithms," European Journal of Operational Research, Elsevier, vol. 271(2), pages 620-631.
    • Handle: RePEc:eee:ejores:v:271:y:2018:i:2:p:620-631
    DOI: 10.1016/j.ejor.2018.05.057
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0377221718304764
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.ejor.2018.05.057?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 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.
    2. Steven J. Brams & D. Marc Kilgour & Christian Klamler, 2017. "Maximin Envy-Free Division of Indivisible Items," Group Decision and Negotiation, Springer, vol. 26(1), pages 115-131, January.
    3. Jean-François Laslier, 2010. "In Silico Voting Experiments," Studies in Choice and Welfare, in: Jean-François Laslier & M. Remzi Sanver (ed.), Handbook on Approval Voting, chapter 0, pages 311-335, Springer.
    4. Dimitris Bertsimas & Vivek F. Farias & Nikolaos Trichakis, 2012. "On the Efficiency-Fairness Trade-off," Management Science, INFORMS, vol. 58(12), pages 2234-2250, December.
    5. Andreas Darmann & Christian Klamler, 2016. "Proportional Borda allocations," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 47(3), pages 543-558, October.
    6. Brams, Steven & Kilgour, D. Marc & Klamler, Christian, 2014. "How to divide things fairly," MPRA Paper 58370, University Library of Munich, Germany.
    7. Steven J. Brams & Daniel L. King, 2005. "Efficient Fair Division," Rationality and Society, , vol. 17(4), pages 387-421, November.
    8. Jean-François Laslier & M. Remzi Sanver (ed.), 2010. "Handbook on Approval Voting," Studies in Choice and Welfare, Springer, number 978-3-642-02839-7, December.
    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. Aziz, Haris & Huang, Xin & Mattei, Nicholas & Segal-Halevi, Erel, 2023. "Computing welfare-Maximizing fair allocations of indivisible goods," European Journal of Operational Research, Elsevier, vol. 307(2), pages 773-784.
    2. Andreas Darmann & Christian Klamler, 2019. "Using the Borda rule for ranking sets of objects," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 53(3), pages 399-414, October.
    3. Montes, Ignacio & Rademaker, Michael & Pérez-Fernández, Raúl & De Baets, Bernard, 2020. "A correspondence between voting procedures and stochastic orderings," European Journal of Operational Research, Elsevier, vol. 285(3), pages 977-987.
    4. Cornilly, Dries & Puccetti, Giovanni & Rüschendorf, Ludger & Vanduffel, Steven, 2022. "Fair allocation of indivisible goods with minimum inequality or minimum envy," European Journal of Operational Research, Elsevier, vol. 297(2), pages 741-752.
    5. Steven J. Brams & D. Marc Kilgour & Christian Klamler, 2022. "Two-Person Fair Division of Indivisible Items when Envy-Freeness is Impossible," SN Operations Research Forum, Springer, vol. 3(2), pages 1-23, June.
    6. D. Marc Kilgour & Rudolf Vetschera, 2024. "Two-Person Fair Division with Additive Valuations," Group Decision and Negotiation, Springer, vol. 33(4), pages 745-774, August.

    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. Steven J. Brams & D. Marc Kilgour & Christian Klamler, 2022. "Two-Person Fair Division of Indivisible Items when Envy-Freeness is Impossible," SN Operations Research Forum, Springer, vol. 3(2), pages 1-23, June.
    2. Steven J. Brams & D. Marc Kilgour & Christian Klamler, 2017. "Maximin Envy-Free Division of Indivisible Items," Group Decision and Negotiation, Springer, vol. 26(1), pages 115-131, January.
    3. Jean-François Laslier, 2016. "Heuristic Voting Under the Alternative Vote: The Efficiency of “Sour Grapes” Behavior," Homo Oeconomicus: Journal of Behavioral and Institutional Economics, Springer, vol. 33(1), pages 57-76, August.
    4. Brams, Steven J. & Kilgour, D. Marc & Klamler, Christian, 2013. "Two-Person Fair Division of Indivisible Items: An Efficient, Envy-Free Algorithm," MPRA Paper 47400, University Library of Munich, Germany.
    5. Andreas Darmann & Christian Klamler, 2019. "Using the Borda rule for ranking sets of objects," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 53(3), pages 399-414, October.
    6. Felix Brandt & Patrick Lederer, 2021. "Characterizing the Top Cycle via Strategyproofness," Papers 2108.04622, arXiv.org, revised Jun 2023.
    7. Fedor Sandomirskiy & Erel Segal-Halevi, 2019. "Efficient Fair Division with Minimal Sharing," Papers 1908.01669, arXiv.org, revised Apr 2022.
    8. Florian Brandl & Felix Brandt & Christian Stricker, 2022. "An analytical and experimental comparison of maximal lottery schemes," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 58(1), pages 5-38, January.
    9. Rudolf Vetschera & D. Marc Kilgour, 2013. "Strategic Behavior in Contested-Pile Methods for Fair Division of Indivisible Items," Group Decision and Negotiation, Springer, vol. 22(2), pages 299-319, March.
    10. Brams, Steven J. & Kilgour, D. Marc & Klamler, Christian, 2014. "An algorithm for the proportional division of indivisible items," MPRA Paper 56587, University Library of Munich, Germany.
    11. Ján Palguta, 2011. "Voting Experiments: Measuring Vulnerability of Voting Procedures to Manipulation," Czech Economic Review, Charles University Prague, Faculty of Social Sciences, Institute of Economic Studies, vol. 5(3), pages 324-345, November.
    12. RAMAEKERS, Eve, 2010. "Fair allocation of indivisible goods among two agents," LIDAM Discussion Papers CORE 2010087, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    13. Eve Ramaekers, 2013. "Fair allocation of indivisible goods: the two-agent case," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 41(2), pages 359-380, July.
    14. Mostapha Diss & Eric Kamwa, 2019. "Simulations in Models of Preference Aggregation," Working Papers hal-02424936, HAL.
    15. repec:hal:pseose:halshs-01168670 is not listed on IDEAS
    16. Andreas Darmann & Christian Klamler, 2016. "Proportional Borda allocations," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 47(3), pages 543-558, October.
    17. Haris Aziz, 2016. "A generalization of the AL method for fair allocation of indivisible objects," Economic Theory Bulletin, Springer;Society for the Advancement of Economic Theory (SAET), vol. 4(2), pages 307-324, October.
    18. Núñez, Matías & Laslier, Jean-François, 2015. "Bargaining through Approval," Journal of Mathematical Economics, Elsevier, vol. 60(C), pages 63-73.
    19. Mostapha Diss & Eric Kamwa & Issofa Moyouwou & Hatem Smaoui, 2021. "Condorcet Efficiency of General Weighted Scoring Rules Under IAC: Indifference and Abstention," Studies in Choice and Welfare, in: Mostapha Diss & Vincent Merlin (ed.), Evaluating Voting Systems with Probability Models, pages 55-73, Springer.
    20. Eric Kamwa, 2019. "On the Likelihood of the Borda Effect: The Overall Probabilities for General Weighted Scoring Rules and Scoring Runoff Rules," Group Decision and Negotiation, Springer, vol. 28(3), pages 519-541, June.
    21. 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.

    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:eee:ejores:v:271:y:2018:i:2:p:620-631. 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: Catherine Liu (email available below). General contact details of provider: http://www.elsevier.com/locate/eor .

    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.