A note on envy-free cake cutting with polynomial valuations

Research output: Contribution to journal/Conference contribution in journal/Contribution to newspaperJournal articleResearchpeer-review

The cake cutting problem models the fair allocation of a heterogeneous divisible resource among multiple players. The central fairness criterion is envy-freeness and a major open question in this domain is the design of a bounded protocol that can compute an envy-free allocation of the cake for any number of players. The only existing finite envy-free cake cutting protocol for any number of players, designed by Brams and Taylor [4], has the property that its runtime can be made arbitrarily large by setting up the valuation functions of the players appropriately. Moreover, there is no closed formula that relates the valuation functions to the number of queries required by the protocol.

In this note we show that when the valuations can be represented as polynomial functions, there exists a protocol in the standard query model that is much simpler conceptually and has a runtime bound depending on the maximum degree over all polynomials.
Original languageEnglish
JournalInformation Processing Letters
Volume115
Issue2
Pages (from-to)93-95
Number of pages3
ISSN0020-0190
DOIs
Publication statusPublished - 2015

See relations at Aarhus University Citationformats

ID: 84416977