Optimal Proportional Cake Cutting with Connected Pieces

Xiaohui Bei · Ning Chen · Xia Hua · Biaoshuai Tao

66 citations0/0 files storedProceedings of the AAAI Conference on Artificial Intelligence

No readable copy stored yet — this record is metadata only.

No open-access location is known for this record yet.

Literature note Cite in a project Citation map

Game Theory and Voting Systems Complexity and Algorithms in Graphs Optimization and Search Problems

Abstract

We consider the classic cake cutting problem where one allocates a divisible cake to n participating agents. Among all valid divisions, fairness and efficiency (a.k.a. ~social welfare) are the most critical criteria to satisfy and optimize, respectively. We study computational complexity of computing an efficiency optimal division given the conditions that the allocation satisfies proportional fairness and assigns each agent a connected piece. For linear valuation functions, we give a polynomial time approximation scheme to compute an efficiency optimal allocation. On the other hand, we show that the problem is NP-hard to approximate within a factor of Ω 1/√n for general piecewise constant functions, and is NP-hard to compute for normalized functions.

Paper brief

Loading…

Cite this work

Citation unavailable for this work.

BibTeX RIS CSL-JSON

No public copy is stored for this record, so only the metadata is cited.

Citations in this library

Citation map →

Stored only when both papers are in the corpus — 66 citations exist upstream.

References

1961How to Cut A Cake Fairly 2000Cake-Cutting Algorithms: Be Fair if You Can.2012Truth, justice, and cake cutting 2011Optimal Envy-Free Cake Cutting

Cited by

2013How to Cut a Cake Before the Party Ends 2021On Maxsum Fair Cake Divisions 2019Pareto-Optimal Allocation of Indivisible Goods with Connectivity Constraints

Explore the map →

Papers that cite the same references — the relational fallback while embeddings are still backfilling.

Imported from OpenAlex (CC0) — nothing here is generated.