Non-Exploitable Protocols for Repeated Cake Cutting

Authors

  • Omer Tamuz California Institute of Technology
  • Shai Vardi California Institute of Technology
  • Juba Ziani California Institute of Technology

Keywords:

cake cutting, fair division, dynamic fair division, repeated cake cutting, exploitability

Abstract

We introduce the notion of exploitability in cut-and-choose protocols for repeated cake cutting. If a cut-and-choose protocol is repeated, the cutter can possibly gain information about the chooser from her previous actions, and exploit this information for her own gain, at the expense of the chooser. We define a generalization of cut-and-choose protocols - forced-cut protocols - in which some cuts are made exogenously while others are made by the cutter, and show that there exist non-exploitable forced-cut protocols that use a small number of cuts per day: When the cake has at least as many dimensions as days, we show a protocol that uses a single cut per day. When the cake is 1-dimensional, we show an adaptive non-exploitable protocol that uses 3 cuts per day, and a non-adaptive protocol that uses n cuts per day (where n is the number of days). In contrast, we show that no non-adaptive non-exploitable forced-cut protocol can use a constant number of cuts per day. Finally, we show that if the cake is at least 2-dimensional, there is a non-adaptive non-exploitable protocol that uses 3 cuts per day.

Downloads

Published

2018-04-25

How to Cite

Tamuz, O., Vardi, S., & Ziani, J. (2018). Non-Exploitable Protocols for Repeated Cake Cutting. Proceedings of the AAAI Conference on Artificial Intelligence, 32(1). Retrieved from https://ojs.aaai.org/index.php/AAAI/article/view/11472

Issue

Section

AAAI Technical Track: Game Theory and Economic Paradigms