The price of connectivity in fair division
From MaRDI portal
Publication:5864211
DOI10.1137/20M1388310zbMATH Open1492.91153arXiv1908.05433MaRDI QIDQ5864211FDOQ5864211
Authors: Xiaohui Bei, Ayumi Igarashi, Xinhang Lu, Warut Suksompong 
Publication date: 3 June 2022
Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)
Abstract: We study the allocation of indivisible goods that form an undirected graph and quantify the loss of fairness when we impose a constraint that each agent must receive a connected subgraph. Our focus is on well-studied fairness notions including envy-freeness and maximin share fairness. We introduce the price of connectivity to capture the largest gap between the graph-specific and the unconstrained maximin share, and derive bounds on this quantity which are tight for large classes of graphs in the case of two agents and for paths and stars in the general case. For instance, with two agents we show that for biconnected graphs it is possible to obtain at least of the maximin share with connected allocations, while for the remaining graphs the guarantee is at most . In addition, we determine the optimal relaxation of envy-freeness that can be obtained with each graph for two agents, and characterize the set of trees and complete bipartite graphs that always admit an allocation satisfying envy-freeness up to one good (EF1) for three agents. Our work demonstrates several applications of graph-theoretic tools and concepts to fair division problems.
Full work available at URL: https://arxiv.org/abs/1908.05433
Recommendations
Resource and cost allocation (including fair division, apportionment, etc.) (91B32) Connectivity (05C40)
Cites Work
- Graph theory
- A simple test on 2-vertex- and 2-edge-connectivity
- On the complexity of partitioning graphs into connected subgraphs
- Partitioning graphs into connected parts
- Title not available (Why is that?)
- A polynomial-time approximation scheme for maximizing the minimum machine completion time
- Eine Verallgemeinerung des \(n\)-fachen Zusammenhangs für Graphen
- Impartial division of a dollar
- Computing an st-numbering
- Almost envy-freeness with general valuations
- Fair division of indivisible items between two people with identical preferences: Envy-freeness, Pareto-optimality, and equity
- The undercut procedure: an algorithm for the envy-free division of indivisible items
- Non-Separable and Planar Graphs
- On partitioning a graph into two connected subgraphs
- Two-player fair division of indivisible items: comparison of algorithms
- Two-person fair division of indivisible items: an efficient envy-free algorithm
- Fair enough: guaranteeing approximate maximin shares
- Fairly allocating many goods with few queries
- Fair allocation of indivisible goods: improvement
- On maximin share allocations in matroids
- Communication complexity of discrete fair division
- Almost envy-free allocations with connected bundles
- Maximin share allocations on cycles
- Envy-free allocations respecting social networks
- Almost envy-freeness in group resource allocation
- Democratic fair allocation of indivisible goods
- Closing gaps in asymptotic fair division
- When do envy-free allocations exist?
Cited In (13)
- Dividing connected chores fairly
- Approximate envy-freeness in graphical cake cutting
- Democratic fair allocation of indivisible goods
- Reachability of fair allocations via sequential exchanges
- Keep your distance: land division with separation
- On Fair Division under Heterogeneous Matroid Constraints
- Dividing connected chores fairly
- Maximin share allocations on cycles
- Dividing a graphical cake
- Almost envy-free allocations with connected bundles
- Fair division of graphs and of tangled cakes
- Mind the gap: cake cutting with separation
- Almost envy-free allocations with connected bundles
Uses Software
This page was built for publication: The price of connectivity in fair division
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5864211)
