An Algorithmic Framework for Strategic Fair Division
Authors: Simina Brânzei, Ioannis Caragiannis, David Kurokawa, Ariel Procaccia
AAAI 2016 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We study the paradigmatic fair division problem of fairly allocating a divisible good among agents with heterogeneous preferences, commonly known as cake cutting. Classic cake cutting protocols are susceptible to manipulation. Do their strategic outcomes still guarantee fairness? To address this question we adopt a novel algorithmic approach, proposing a concrete computational model and reasoning about the gametheoretic properties of algorithms that operate in this model. Specifically, we show that each protocol in the class of generalized cut and choose (GCC) protocols... is guaranteed to have approximate subgame perfect Nash equilibria, or even exact equilibria if the protocol s tie-breaking rule is flexible. We further observe that the (approximate) equilibria of proportional protocols... must be (approximately) proportional, thereby answering the above question in the positive (at least for one common notion of fairness). |
| Researcher Affiliation | Academia | Simina Brˆanzei University of California Berkeley simina.branzei@gmail.com Ioannis Caragiannis University of Patras caragian@ceid.upatras.gr David Kurokawa Carnegie Mellon University dkurokaw@cs.cmu.edu Ariel D. Procaccia Carnegie Mellon University arielpro@cs.cmu.edu |
| Pseudocode | Yes | Algorithm 1: A GCC protocol. ... Algorithm 2: A non-GCC protocol. ... Algorithm 3: Selfridge-Conway: an envy-free protocol for three agents. |
| Open Source Code | No | The paper does not provide any statement or link indicating that the source code for the methodology described in the paper is openly available. |
| Open Datasets | No | The paper focuses on theoretical analysis and does not use or train models on specific datasets. |
| Dataset Splits | No | The paper is theoretical and does not involve empirical experiments with training, validation, or test dataset splits. |
| Hardware Specification | No | The paper is theoretical and does not report empirical experiments that would require specific hardware specifications. |
| Software Dependencies | No | The paper is theoretical and focuses on algorithmic frameworks and game-theoretic properties, so it does not list specific software dependencies with version numbers. |
| Experiment Setup | No | The paper is theoretical and does not describe empirical experiments with specific setup details or hyperparameters. |