BEGIN:VCALENDAR
CALSCALE:GREGORIAN
PRODID:iCalendar-Ruby
VERSION:2.0
BEGIN:VEVENT
DESCRIPTION: We study the allocation of indivisible goods that form an undi
rected 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-stu
died fairness notions including envy-freeness and maximin share fairness. W
e introduce the price of connectivity to capture the largest gap between th
e 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 t
wo 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 r
emaining graphs the guarantee is at most 1/2. In addition\, we determine th
e optimal relaxation of envy-freeness that can be obtained with each graph
for two agents\, and characterize the set of trees and complete bipartite g
raphs that always admit an allocation satisfying envy-freeness up to one go
od (EF1) for three agents. Our work demonstrates several applications of gr
aph-theoretic tools and concepts to fair division problems. Joint work with
Xiaohui Bei\, Ayumi Igarashi\, and Xinhang Lu.
DTSTAMP:20220615T184800
DTSTART:20220711T160000
CLASS:PUBLIC
LOCATION:Technische Universität Berlin\n Institut für Mathematik\n Straße d
es 17. Juni 136\n 10623 Berlin\n Room MA 041 (Ground Floor)
SEQUENCE:0
SUMMARY:Warut Suksompong (National University of Singapore): The Price of C
onnectivity in Fair Division
UID:107920550@www.facetsofcomplexity.de
URL:http://www.facetsofcomplexity.de/monday/20220711-C-Suksompong.html
END:VEVENT
END:VCALENDAR