Almost envy-free allocations with connected bundles
From MaRDI portal
Publication:2078044
Abstract: We study the existence of allocations of indivisible goods that are envy-free up to one good (EF1), under the additional constraint that each bundle needs to be connected in an underlying item graph. If the graph is a path and the utility functions are monotonic over bundles, we show the existence of EF1 allocations for at most four agents, and the existence of EF2 allocations for any number of agents; our proofs involve discrete analogues of the Stromquist's moving-knife protocol and the Su--Simmons argument based on Sperner's lemma. For identical utilities, we provide a polynomial-time algorithm that computes an EF1 allocation for any number of agents. For the case of two agents, we characterize the class of graphs that guarantee the existence of EF1 allocations as those whose biconnected components are arranged in a path; this property can be checked in linear time.
Recommendations
Cites work
- A constructive proof of a permutation-based generalization of Sperner's lemma
- A moving-knife solution to the four-person envy-free cake-division problem
- Algorithmic solutions for envy-free cake cutting
- Allocating contiguous blocks of indivisible chores fairly
- Almost envy-free allocations with connected bundles
- Approximation Algorithms for Computing Maximin Share Allocations
- Cake cutting algorithms
- Cake division with minimal cuts: envy-free procedures for three persons, four persons, and beyond
- Computing an st-numbering
- Envy-free cake division without assuming the players prefer nonempty pieces
- Fair enough: guaranteeing approximate maximin shares
- Graph theory
- How to Cut A Cake Fairly
- How to Cut a Cake Fairly
- scientific article; zbMATH DE number 3831632 (Why is no real title available?)
- scientific article; zbMATH DE number 3949734 (Why is no real title available?)
- scientific article; zbMATH DE number 3511203 (Why is no real title available?)
- scientific article; zbMATH DE number 1234106 (Why is no real title available?)
- scientific article; zbMATH DE number 1015852 (Why is no real title available?)
- scientific article; zbMATH DE number 3315017 (Why is no real title available?)
- Maximin share allocations on cycles
- Rental Harmony: Sperner's Lemma in Fair Division
- Some Combinatorial Lemmas in Topology
- The Approximation of Fixed Points of a Continuous Mapping
Cited in
(21)- Mind the gap: cake cutting with separation
- Two-person fair division of indivisible items when envy-freeness is impossible
- Envy-free allocations respecting social networks
- Almost envy-free allocations with connected bundles
- The price of connectivity in fair division
- Fair division of graphs and of tangled cakes
- Fairly taking turns
- Approximate envy-freeness in graphical cake cutting
- Fair division with two-sided preferences
- Reachability of fair allocations via sequential exchanges
- Dividing a graphical cake
- Welfare loss in connected resource allocation
- On the price of fairness of allocating contiguous blocks
- Fair distribution of delivery orders
- Differentially private fair division
- Parameterized complexity of incomplete connected fair division
- Envy-free and efficient allocations for graphical valuations
- Achieving envy-freeness through items sale
- Logarithmic comparison-based query complexity for fair division of indivisible goods
- Approximating proportional and maximin allocations on d-claw-free graphs
- The complexity of envy-free graph cutting
This page was built for publication: Almost envy-free allocations with connected bundles
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2078044)
