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...
| Main Authors: | , , , |
|---|---|
| Other Authors: | |
| Format: | Journal Article |
| Language: | English |
| Published: |
2022
|
| Subjects: | |
| Online Access: | https://hdl.handle.net/10356/161276 |
| _version_ | 1811679868233973760 |
|---|---|
| author | Bei, Xiaohui Igarashi, Ayumi Lu, Xinhang Suksompong, Warut |
| author2 | School of Physical and Mathematical Sciences |
| author_facet | School of Physical and Mathematical Sciences Bei, Xiaohui Igarashi, Ayumi Lu, Xinhang Suksompong, Warut |
| author_sort | Bei, Xiaohui |
| collection | NTU |
| description | 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. |
| first_indexed | 2024-10-01T03:15:59Z |
| format | Journal Article |
| id | ntu-10356/161276 |
| institution | Nanyang Technological University |
| language | English |
| last_indexed | 2024-10-01T03:15:59Z |
| publishDate | 2022 |
| record_format | dspace |
| spelling | ntu-10356/1612762023-02-28T20:11:30Z The price of connectivity in fair division Bei, Xiaohui Igarashi, Ayumi Lu, Xinhang Suksompong, Warut School of Physical and Mathematical Sciences Science::Mathematics Fair Division Envy-Freeness 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. Ministry of Education (MOE) Published version This work was partially supported by the Ministry of Education, Singapore, under its Academic Research Fund Tier 1 (RG23/20), by the KAKENHI Grant-in-Aid for JSPS Fellows(18J00997), by the European Research Council (ERC) under grant 639945 (ACCORD), by an NUS Start-Up Grant, and by JST, ACT-X. 2022-08-23T06:51:37Z 2022-08-23T06:51:37Z 2022 Journal Article Bei, X., Igarashi, A., Lu, X. & Suksompong, W. (2022). The price of connectivity in fair division. SIAM Journal On Discrete Mathematics, 36(2), 1156-1186. https://dx.doi.org/10.1137/20M1388310 0895-4801 https://hdl.handle.net/10356/161276 10.1137/20M1388310 2-s2.0-85132235267 2 36 1156 1186 en RG23/20 SIAM Journal on Discrete Mathematics © 2022 SIAM. Published by SIAM under the terms of the Creative Commons 4.0 license. application/pdf |
| spellingShingle | Science::Mathematics Fair Division Envy-Freeness Bei, Xiaohui Igarashi, Ayumi Lu, Xinhang Suksompong, Warut The price of connectivity in fair division |
| title | The price of connectivity in fair division |
| title_full | The price of connectivity in fair division |
| title_fullStr | The price of connectivity in fair division |
| title_full_unstemmed | The price of connectivity in fair division |
| title_short | The price of connectivity in fair division |
| title_sort | price of connectivity in fair division |
| topic | Science::Mathematics Fair Division Envy-Freeness |
| url | https://hdl.handle.net/10356/161276 |
| work_keys_str_mv | AT beixiaohui thepriceofconnectivityinfairdivision AT igarashiayumi thepriceofconnectivityinfairdivision AT luxinhang thepriceofconnectivityinfairdivision AT suksompongwarut thepriceofconnectivityinfairdivision AT beixiaohui priceofconnectivityinfairdivision AT igarashiayumi priceofconnectivityinfairdivision AT luxinhang priceofconnectivityinfairdivision AT suksompongwarut priceofconnectivityinfairdivision |