Non-Exploitable Protocols for Repeated Cake Cutting
Authors: Omer Tamuz, Shai Vardi, Juba Ziani
AAAI 2018 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | 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 nonexploitable 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 3n cuts per day, and a nonadaptive 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 3n cuts per day. |
| Researcher Affiliation | Academia | Omer Tamuz, Shai Vardi, Juba Ziani {tamuz,svardi,jziani}@caltech.edu California Institute of Technology, 1200 E California Blvd, Pasadena, CA 91125 |
| Pseudocode | Yes | Protocol 1.1. One agent cuts the cake into two pieces, X and X. The other agent chooses one of {X, X}. The agent that cut the cake receives the remaining piece. ... Protocol 2.2. For t = {1, 2, . . . , n}, let Ht-1 be the set of (forced and unforced) cuts made on day t-1, and let H0 = . On day t, the forced cuts are Ht-1. Let the segments resulting from these cuts be Xt-1, . . . , Xt-m. The cutter cuts each Xt-k, k {1, . . . , m} into two slices, Xt-k,0, Xt-k,1. The chooser chooses between U k Xt-k,0 and U k Xt-k,1. |
| Open Source Code | No | The paper does not provide any statements or links indicating the availability of open-source code for the methodology described. |
| Open Datasets | No | The paper is theoretical and does not involve empirical experiments with datasets, thus no training data is mentioned or made available. |
| Dataset Splits | No | The paper is theoretical and does not involve empirical experiments with datasets, thus no validation data splits are specified. |
| Hardware Specification | No | The paper is theoretical and does not involve empirical experiments that would require specific hardware. Therefore, no hardware specifications are provided. |
| Software Dependencies | No | The paper is theoretical and does not discuss software implementations or dependencies with version numbers. |
| Experiment Setup | No | The paper is theoretical and focuses on protocol design and analysis, rather than empirical experiments. Therefore, no experimental setup details like hyperparameters are provided. |