Approximate Envy-Freeness in Graphical Cake Cutting
Authors: Sheung Man Yuen, Warut Suksompong
IJCAI 2023 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We study the problem of fairly allocating a divisible resource in the form of a graph, also known as graphical cake cutting. Unlike for the canonical interval cake, a connected envy-free allocation is not guaranteed to exist for a graphical cake. We focus on the existence and computation of connected allocations with low envy. For general graphs, we show that there is always a 1/2additive-envy-free allocation and, if the agents valuations are identical, a (2 + ϵ)-multiplicativeenvy-free allocation for any ϵ > 0. In the case of star graphs, we obtain a multiplicative factor of 3 + ϵ for arbitrary valuations and 2 for identical valuations. We also derive guarantees when each agent can receive more than one connected piece. All of our results come with efficient algorithms for computing the respective allocations. |
| Researcher Affiliation | Academia | Sheung Man Yuen and Warut Suksompong National University of Singapore {yuens,warut}@comp.nus.edu.sg |
| Pseudocode | Yes | Algorithm 1 ITERATIVEDIVIDE(G, N)., Algorithm 2 RECURSIVEBALANCE(A, ϵ)., Algorithm 3 BALANCE(A, ϵ)., Algorithm 4 BALANCEPATH(P, ϵ). |
| Open Source Code | No | The paper does not provide an explicit statement or link to open-source code for the described methodology. |
| Open Datasets | No | The paper is theoretical and does not involve the use of datasets for training. |
| Dataset Splits | No | The paper is theoretical and does not discuss training, test, or validation dataset splits. |
| Hardware Specification | No | The paper is theoretical and does not describe the hardware used for experiments. |
| Software Dependencies | No | The paper does not mention specific software dependencies with version numbers. |
| Experiment Setup | No | The paper is theoretical and does not include details about an experimental setup. |