Please use this identifier to cite or link to this item: https://hdl.handle.net/10356/161276
Title: The price of connectivity in fair division
Authors: Bei, Xiaohui 
Igarashi, Ayumi
Lu, Xinhang
Suksompong, Warut
Keywords: Science::Mathematics
Issue Date: 2022
Source: 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
Project: RG23/20
Journal: SIAM Journal on Discrete Mathematics
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 $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.
URI: https://hdl.handle.net/10356/161276
ISSN: 0895-4801
DOI: 10.1137/20M1388310
Schools: School of Physical and Mathematical Sciences 
Rights: © 2022 SIAM. Published by SIAM under the terms of the Creative Commons 4.0 license.
Fulltext Permission: open
Fulltext Availability: With Fulltext
Appears in Collections:SPMS Journal Articles

Files in This Item:
File Description SizeFormat 
20m1388310.pdf442.24 kBAdobe PDFThumbnail
View/Open

SCOPUSTM   
Citations 20

12
Updated on Jun 11, 2024

Web of ScienceTM
Citations 50

4
Updated on Oct 31, 2023

Page view(s)

76
Updated on Jun 13, 2024

Download(s) 50

42
Updated on Jun 13, 2024

Google ScholarTM

Check

Altmetric


Plumx

Items in DR-NTU are protected by copyright, with all rights reserved, unless otherwise indicated.