Indirect Revelation Mechanisms for Cake Cutting

Simina Branzei; Peter Bro Miltersen

Indirect Revelation Mechanisms for Cake Cutting

Department of Computer Science

Research output: Contribution to conference › Conference abstract for conference › Research

Abstract

We consider discrete protocols for the classical Steinhaus cake cutting problem. Under mild technical conditions, we show that any deterministic strategy-proof protocol in the standard Robertson-Webb query model is dictatorial, that is, there is a fixed agent to which the protocol allocates the entire cake. In contrast, we exhibit randomized protocols that are truthful in expectation and compute approximately fair allocations.

Original language	English
Publication date	14 Mar 2014
Number of pages	7
Publication status	Published - 14 Mar 2014
Event	Economics and Computational Aspects of Game Theory and Social Choice - Warsaw, Poland Duration: 14 Mar 2014 → 14 Mar 2014

Conference

Conference	Economics and Computational Aspects of Game Theory and Social Choice
Country/Territory	Poland
City	Warsaw
Period	14/03/2014 → 14/03/2014

Access to Document

Cite this

@conference{0d359d3d60eb4b858d9535d131f852e7,

title = "Indirect Revelation Mechanisms for Cake Cutting",

abstract = "We consider discrete protocols for the classical Steinhaus cake cutting problem. Under mild technical conditions, we show that any deterministic strategy-proof protocol in the standard Robertson-Webb query model is dictatorial, that is, there is a fixed agent to which the protocol allocates the entire cake. In contrast, we exhibit randomized protocols that are truthful in expectation and compute approximately fair allocations.",

author = "Simina Branzei and Miltersen, {Peter Bro}",

year = "2014",

month = mar,

day = "14",

language = "English",

note = "Economics and Computational Aspects of Game Theory and Social Choice ; Conference date: 14-03-2014 Through 14-03-2014",

}

TY - ABST

T1 - Indirect Revelation Mechanisms for Cake Cutting

AU - Branzei, Simina

AU - Miltersen, Peter Bro

PY - 2014/3/14

Y1 - 2014/3/14

N2 - We consider discrete protocols for the classical Steinhaus cake cutting problem. Under mild technical conditions, we show that any deterministic strategy-proof protocol in the standard Robertson-Webb query model is dictatorial, that is, there is a fixed agent to which the protocol allocates the entire cake. In contrast, we exhibit randomized protocols that are truthful in expectation and compute approximately fair allocations.

AB - We consider discrete protocols for the classical Steinhaus cake cutting problem. Under mild technical conditions, we show that any deterministic strategy-proof protocol in the standard Robertson-Webb query model is dictatorial, that is, there is a fixed agent to which the protocol allocates the entire cake. In contrast, we exhibit randomized protocols that are truthful in expectation and compute approximately fair allocations.

M3 - Conference abstract for conference

T2 - Economics and Computational Aspects of Game Theory and Social Choice

Y2 - 14 March 2014 through 14 March 2014

ER -

Indirect Revelation Mechanisms for Cake Cutting

Abstract

Conference

Access to Document

Fingerprint

Cite this