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 [1].
Contiguous Cake Cutting: Hardness Results and Approximation Algorithms
Authors: Paul Goldberg, Alexandros Hollender, Warut Suksompong
JAIR 2020 | Venue PDF | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | In this paper, we present several algorithmic and hardness results on contiguous cake cutting. We begin by highlighting two representative results; as is standard in the cake-cutting literature, we represent the cake by the interval [0, 1] and normalize the agents valuations so that each agent has value 1 for the entire interval. We design a quadratic-time algorithm that works for general additive valuations under the Robertson-Webb model and produces a contiguous allocation in which any agent has additive envy no more than 1/3 towards any other agent (Theorem 3.1). In other words, any agent i s value for her own piece is at most 1/3 less than her value for any other agent j s piece, where her value for the entire cake is 1. We consider variants of the cake-cutting problem where we impose constraints on the desired allocation (Section 4). We show that for several natural variants, the decision problem of whether there exists a contiguous envy-free allocation satisfying the corresponding constraints is NP-hard. In particular, this holds for the variants where (i) a certain agent must be allocated the leftmost piece; (ii) the ordering of the agents is fixed; and (iii) one of the cuts must fall at a given position. |
| Researcher Affiliation | Academia | Paul W. Goldberg EMAIL Alexandros Hollender EMAIL University of Oxford Oxford, United Kingdom Warut Suksompong EMAIL National University of Singapore Singapore |
| Pseudocode | Yes | Algorithm 1 1/3-Envy-Free Algorithm for Arbitrary Valuations 1: procedure Approximate EFArbitrary 2: ℓ 0, N [n] 3: for i N do 5: while some agent in N values [ℓ, 1] at least 1/3 do 6: for i N do 7: if vi(ℓ, 1) 1/3 then 8: ri leftmost point such that vi(ℓ, ri) = 1/3 11: j arg mini N ri, r mini N ri 12: Mj [ℓ, r] 13: ℓ r, N N\{j} 14: if N = then 15: j arbitrary agent in N 16: Mj [ℓ, 1] 18: j last agent removed from N 19: Mj Mj [ℓ, 1] 20: return (M1, . . . , Mn) |
| Open Source Code | No | The paper describes algorithms and hardness results but does not mention any open-source code release, specific repository links, or code in supplementary materials. |
| Open Datasets | No | The paper focuses on theoretical computer science problems such as cake cutting and fair division with indivisible items. It does not use or refer to any empirical datasets; instead, it defines theoretical 'instances' of problems like 3-SAT for its hardness proofs. For example: 'We reduce from the 3-partition problem.' and 'Consider an instance of 3-SAT with m clauses C1, . . . , Cm using the variables x1, . . . , xn and their negations.' |
| Dataset Splits | No | The paper is theoretical and does not involve experiments on empirical datasets, therefore, there are no dataset splits to describe. |
| Hardware Specification | No | The paper is purely theoretical, focusing on algorithms, complexity, and proofs in the context of cake cutting and fair division. It does not describe any experimental setups or computational evaluations that would require specific hardware specifications. |
| Software Dependencies | No | The paper describes theoretical algorithms and complexity results. It does not mention any specific software or libraries with version numbers required for implementation or reproduction. |
| Experiment Setup | No | This paper is theoretical, presenting approximation algorithms and hardness results. It does not contain any empirical experimental setup details, hyperparameters, or training configurations. |