Fair and efficient cake division with connected pieces
From MaRDI portal
(Redirected from Publication:776236)
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.
Recommendations
Cites work
- scientific article; zbMATH DE number 1234106 (Why is no real title available?)
- scientific article; zbMATH DE number 1015852 (Why is no real title available?)
- A discrete and bounded envy-free cake cutting protocol for four agents
- Algorithmic solutions for envy-free cake cutting
- Approximating the throughput of multiple machines in real-time scheduling
- Cake cutting algorithms for piecewise constant and piecewise uniform valuations
- Consensus of Subjective Probabilities: The Pari-Mutuel Method
- Envy-free cake divisions cannot be found by finite protocols
- Fully polynomial-time approximation schemes for fair rent division
- How to Cut a Cake Fairly
- Interval selection: Applications, algorithms, and lower bounds
- Polynomial time approximation schemes for dense instances of \( \mathcal{NP}\)-hard problems
- Proof verification and the hardness of approximation problems
- Rental Harmony: Sperner's Lemma in Fair Division
- The Nash Social Welfare Function
- The bargaining problem
- The efficiency of fair division
Cited in
(19)- Mind the gap: cake cutting with separation
- Fair and square: cake-cutting in two dimensions
- Two birds with one stone: fairness and welfare via transfers
- Resource-monotonicity and population-monotonicity in connected cake-cutting
- 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
- Monotonicity and competitive equilibrium in cake-cutting
- Fair multi-cake cutting
- Toss one's cake, and eat it too: partial divisions can improve social welfare in cake cutting
- Maximize egalitarian welfare for cake cutting
- Contiguous cake cutting: hardness results and approximation algorithms
- Fair Cake Division Under Monotone Likelihood Ratios
- Consensus-Halving: Does It Ever Get Easier?
- On the possibilities for partitioning a cake
- Fairness and efficiency in cake-cutting with single-peaked preferences
- Cake cutting algorithms
- Waste makes haste: bounded time algorithms for envy-free cake cutting with free disposal
- Dividing a graphical cake
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)
