CaltechAUTHORS
  A Caltech Library Service

Non-Exploitable Protocols for Repeated Cake Cutting

Tamuz, Omer and Vardi, Shai and Ziani, Juba (2018) Non-Exploitable Protocols for Repeated Cake Cutting. In: Thirty-Second AAAI Conference on Artificial Intelligence. Association for the Advancement of Artificial Intelligence , pp. 1226-1233. https://resolver.caltech.edu/CaltechAUTHORS:20191010-132749128

[img] PDF - Published Version
See Usage Policy.

523Kb

Use this Persistent URL to link to this item: https://resolver.caltech.edu/CaltechAUTHORS:20191010-132749128

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.


Item Type:Book Section
Related URLs:
URLURL TypeDescription
https://www.aaai.org/ocs/index.php/AAAI/AAAI18/paper/view/17113PublisherArticle
ORCID:
AuthorORCID
Tamuz, Omer0000-0002-0111-0418
Ziani, Juba0000-0002-3324-4349
Additional Information:© 2018 Association for the Advancement of Artificial Intelligence. Omer Tamuz was supported by a grant from the Simons Foundation (#419427). Shai Vardi was supported in part by the Linde Foundation and NSF grants CNS-1254169 and CNS-1518941. Juba Ziani was supported by NSF grants #1331343 and #1518941, and US-Israel Binational Science Foundation grant #201234.
Funders:
Funding AgencyGrant Number
Simons Foundation419427
Linde Institute of Economic and Management ScienceUNSPECIFIED
NSFCNS-1254169
NSFCNS-1518941
NSFCCF-1331343
NSFCNS-1518941
Binational Science Foundation (USA-Israel)2012348
Subject Keywords:cake cutting; fair division; dynamic fair division; repeated cake cutting; exploitability
Record Number:CaltechAUTHORS:20191010-132749128
Persistent URL:https://resolver.caltech.edu/CaltechAUTHORS:20191010-132749128
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:99216
Collection:CaltechAUTHORS
Deposited By: Tony Diaz
Deposited On:10 Oct 2019 20:41
Last Modified:09 Jul 2020 22:09

Repository Staff Only: item control page