Files and links (1)
Preprint (Author's original)arXiv.org - Non-exclusive license to distribute, Open
Preprint
Beyond Cake Cutting: Allocating Homogeneous Divisible Goods
arXiv (Cornell University)
12 Jan 2022
Abstract
The problem of fair division known as "cake cutting" has been the focus of
multiple papers spanning several decades. The most prominent problem in this
line of work has been to bound the query complexity of computing an envy-free
outcome in the Robertson-Webb query model. However, the root of this problem's
complexity is somewhat artificial: the agents' values are assumed to be
additive across different pieces of the "cake" but infinitely complicated
within each piece. This is unrealistic in most of the motivating examples,
where the cake represents a finite collection of homogeneous goods.
We address this issue by introducing a fair division model that more
accurately captures these applications: the value that an agent gains from a
given good depends only on the amount of the good they receive, yet it can be
an arbitrary function of this amount, allowing the agents to express
preferences that go beyond standard cake cutting. In this model, we study the
query complexity of computing allocations that are not just envy-free, but also
approximately Pareto optimal among all envy-free allocations. Using a novel
flow-based approach, we show that we can encode the ex-post feasibility of
randomized allocations via a polynomial number of constraints, which reduces
our problem to solving a linear program.
Metrics
6 Record Views
Details
- Title
- Beyond Cake Cutting: Allocating Homogeneous Divisible Goods
- Creators
- Ioannis CaragiannisVasilis GkatzelisAlexandros PsomasDaniel Schoepflin
- Publication Details
- arXiv (Cornell University)
- Resource Type
- Preprint
- Language
- English
- Academic Unit
- Computer Science (Computing)
- Other Identifier
- 991021868725104721