The price of connectivity in fair division
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 introduc...
Saved in:
| Main Authors: | , , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | English |
| Published: |
2022
|
| Subjects: | |
| Online Access: | https://hdl.handle.net/10356/161276 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Institution: | Nanyang Technological University |
| Language: | English |
| Summary: | 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 $3/4$ of the maximin share
with connected allocations, while for the remaining graphs the guarantee is at
most $1/2$. 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. |
|---|