The undercut procedure: An algorithm for the envy-free division of indivisible items

Steven J. Brams, D. Marc Kilgour, Christian Klamler

    Research output: Contribution to journalArticlepeer-review

    Abstract

    We propose a procedure for dividing a set of indivisible items between two players. We assume that each player's preference over subsets of items is consistent with a strict ranking of the items, and that neither player has information about the other's preferences. Our procedure ensures an envy-free division-each player receives a subset of items that it values more than the other player's complementary subset-given that an envy-free division of "contested items," which the players would choose at the same time, is possible. We show that the possibility of one player's undercutting the other's proposal, and implementing the reduced subset for himself or herself, makes the proposer "reasonable," and generally leads to an envy-free division, even when the players rank items exactly the same. Although the undercut procedure is manipulable and its envy-free allocation may be Pareto-inferior, each player's maximin strategy is to be truthful. Applications of the procedure are discussed briefly.

    Original languageEnglish (US)
    Pages (from-to)615-631
    Number of pages17
    JournalSocial Choice and Welfare
    Volume39
    Issue number2-3
    DOIs
    StatePublished - Jul 2012

    ASJC Scopus subject areas

    • Social Sciences (miscellaneous)
    • Economics and Econometrics

    Fingerprint

    Dive into the research topics of 'The undercut procedure: An algorithm for the envy-free division of indivisible items'. Together they form a unique fingerprint.

    Cite this