Fair and efficient cake division with connected pieces
From MaRDI portal
Publication:776236
DOI10.1007/978-3-030-35389-6_5zbMATH Open1435.91103arXiv1907.11019OpenAlexW2989818063MaRDI QIDQ776236FDOQ776236
Authors: Eshwar Ram Arunachaleswaran, Siddharth Barman, Rachitesh Kumar, Nidhi Rathi 
Publication date: 30 June 2020
Abstract: The classic cake-cutting problem provides a model for addressing fair and efficient allocation of a divisible, heterogeneous resource (metaphorically, the cake) among agents with distinct preferences. Focusing on a standard formulation of cake cutting, in which each agent must receive a contiguous piece of the cake, this work establishes algorithmic and hardness results for multiple fairness/efficiency measures. First, we consider the well-studied notion of envy-freeness and develop an efficient algorithm that finds a cake division (with connected pieces) wherein the envy is multiplicatively within a factor of 2+o(1). The same algorithm in fact achieves an approximation ratio of 3+o(1) for the problem of finding cake divisions with as large a Nash social welfare (NSW) as possible. NSW is another standard measure of fairness and this work also establishes a connection between envy-freeness and NSW: approximately envy-free cake divisions (with connected pieces) always have near-optimal Nash social welfare. Furthermore, we develop an approximation algorithm for maximizing the -mean welfare--this unifying objective, with different values of , interpolates between notions of fairness (NSW) and efficiency (average social welfare). Finally, we complement these algorithmic results by proving that maximizing NSW (and, in general, the -mean welfare) is APX-hard in the cake-division context.
Full work available at URL: https://arxiv.org/abs/1907.11019
Recommendations
Resource and cost allocation (including fair division, apportionment, etc.) (91B32) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Welfare economics (91B15)
Cites Work
- The bargaining problem
- Polynomial time approximation schemes for dense instances of \( \mathcal{NP}\)-hard problems
- Proof verification and the hardness of approximation problems
- Consensus of Subjective Probabilities: The Pari-Mutuel Method
- Rental Harmony: Sperner's Lemma in Fair Division
- Title not available (Why is that?)
- Approximating the throughput of multiple machines in real-time scheduling
- Title not available (Why is that?)
- Interval selection: Applications, algorithms, and lower bounds
- How to Cut a Cake Fairly
- The Nash Social Welfare Function
- The efficiency of fair division
- Envy-free cake divisions cannot be found by finite protocols
- Algorithmic solutions for envy-free cake cutting
- Cake cutting algorithms for piecewise constant and piecewise uniform valuations
- Fully polynomial-time approximation schemes for fair rent division
- A discrete and bounded envy-free cake cutting protocol for four agents
Cited In (19)
- Two birds with one stone: fairness and welfare via transfers
- Fairness and efficiency in cake-cutting with single-peaked preferences
- Toss one's cake, and eat it too: partial divisions can improve social welfare in cake cutting
- Fair multi-cake cutting
- Fair and square: cake-cutting in two dimensions
- The complexity of cake cutting with unequal shares
- Contiguous cake cutting: hardness results and approximation algorithms
- Resource-monotonicity and population-monotonicity in connected cake-cutting
- Waste makes haste: bounded time algorithms for envy-free cake cutting with free disposal
- Consensus-Halving: Does It Ever Get Easier?
- A discrete and bounded locally envy-free cake cutting protocol on trees
- Approximate envy-freeness in graphical cake cutting
- Allocating contiguous blocks of indivisible chores fairly
- Fair Cake Division Under Monotone Likelihood Ratios
- On the possibilities for partitioning a cake
- Monotonicity and competitive equilibrium in cake-cutting
- Dividing a graphical cake
- Mind the gap: cake cutting with separation
- Cake cutting algorithms
This page was built for publication: Fair and efficient cake division with connected pieces
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q776236)
