Notice: The reproducibility variables underlying each score are classified using an automated LLM-based pipeline, validated against a manually labeled dataset. LLM-based classification introduces uncertainty and potential bias; scores should be interpreted as estimates. Full accuracy metrics and methodology are described in Coakley et alK. L. Coakley, T. Snelleman, H. Hoos, and O. E. Gundersen, "The embrace of open science: An analysis of a decade of AI research and 56 800 conference papers," Under Review, 2026..
Approximate Envy-Freeness in Graphical Cake Cutting
Authors: Sheung Man Yuen, Warut Suksompong
IJCAI 2023 | Venue PDF | 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 EMAIL |
| 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. |