Proportional pie-cutting

Steven J. Brams, Michael A. Jones, Christian Klamler

    Research output: Contribution to journalArticlepeer-review

    Abstract

    David Gale (Math Intell 15:48-52, 1993) was perhaps the first to suggest that there is a difference between cake and pie cutting. A cake can be viewed as a rectangle valued along its horizontal axis, and a pie as a disk valued along its circumference. We will use vertical, parallel cuts to divide a cake into pieces, and radial cuts from the center to divide a pie into wedge-shaped pieces. We restrict our attention to allocations that use the minimal number of cuts necessary to divide cakes or pies. In extending the definition of envy-freeness to unequal entitlements, we provide a counterexample to show that a cake cannot necessarily be divided into a proportional allocation of ratio p:1-p between two players where one player receives p of the cake according to her measure and the other receives 1-p of the cake according to his measure. In constrast, for pie, we prove that an efficient, envy-free, proportional allocation exists for two players. The former can be explained in terms of the Universal Chord Theorem, whereas the latter is proved by another result on chords. We provide procedures that induce two risk-averse players to reveal their preferences truthfully to achieve proportional allocations. We demonstrate that, in general, proportional, envy-free, and efficient allocations that use a minimal number of cuts may fail to exist for more than two players.

    Original languageEnglish (US)
    Pages (from-to)353-367
    Number of pages15
    JournalInternational Journal of Game Theory
    Volume36
    Issue number3-4
    DOIs
    StatePublished - Mar 2008

    Keywords

    • Cake-cutting
    • Envy-freeness
    • Pie-cutting
    • Proportionality
    • Truth-telling

    ASJC Scopus subject areas

    • Statistics and Probability
    • Mathematics (miscellaneous)
    • Social Sciences (miscellaneous)
    • Economics and Econometrics
    • Statistics, Probability and Uncertainty

    Fingerprint Dive into the research topics of 'Proportional pie-cutting'. Together they form a unique fingerprint.

    Cite this