Paper Info
Title
Communication Complexity of Discrete Fair Division.
Abstract
We initiate the study of the communication complexity of fair division with indivisible goods. We focus on some of the most well-studied fairness notions (envy-freeness, proportionality, and approximations thereof) and valuation classes (submodular, subad-ditive and unrestricted). Within these parameters, our results completely resolve whether the communication complexity of computing a fair allocation (or determining that none exist) is polynomial or exponential (in the number of goods), for every combination of fairness notion, valuation class, and number of players, for both deterministic and randomized protocols.
Year
DOI
Venue
2019
10.5555/3310435.3310557
SODA '19: Symposium on Discrete Algorithms San Diego California January, 2019
DocType
Volume
Citations 
Conference
abs/1711.04066
0
PageRank 
References 
Authors
0.34
9
2
Name
Order
Citations
PageRank
Benjamin Plaut1102.64
Tim Roughgarden24177353.32