Show simple item record

dc.contributor.authorAbebe, Rediet
dc.contributor.authorKleinberg, Jon
dc.contributor.authorParkes, David
dc.date.accessioned2019-10-22T13:30:37Z
dc.identifier.citationAbebe, Rediet, Jon Kleinberg, and David Parkes. 2017. Fair Division via Social Comparison. AAMAS '17 Proceedings of the 16th Conference on Autonomous Agents and MultiAgent Systems, São Paulo, Brazil, May 08- 12, 2017, 281-289.en_US
dc.identifier.urihttp://nrs.harvard.edu/urn-3:HUL.InstRepos:41593087*
dc.description.abstractWe study cake cutting on a graph, where agents can only evaluate their shares relative to their neighbors. This is an extension of the classical problem of fair division to incorporate the notion of social comparison from the social sciences. We say an allocation is {\em locally envy-free} if no agent envies a neighbor's allocation, and locally proportional if each agent values its own allocation as much as the average value of its neighbors' allocations. We generalize the classical ``Cut and Choose" protocol for two agents to this setting, by fully characterizing the set of graphs for which an oblivious {\em single-cutter protocol} can give locally envy-free (thus also locally-proportional) allocations. We study the {\em price of envy-freeness}, which compares the total value of an optimal allocation with that of an optimal, locally envy-free allocation. Surprisingly, a lower bound of $\Omega(\sqrt{n})$ on the price of envy-freeness for global allocations also holds for local envy-freeness in any connected graph, so sparse graphs do not provide more flexibility asymptotically with respect to the quality of envy-free allocations.en_US
dc.description.sponsorshipEngineering and Applied Sciencesen_US
dc.language.isoen_USen_US
dc.publisherACM, Inc.en_US
dc.relation.isversionofhttps://dl-acm-org.ezp-prod1.hul.harvard.edu/citation.cfm?id=3091171en_US
dc.relation.hasversionhttps://arxiv.org/abs/1611.06589en_US
dash.licenseMETA_ONLY
dc.subjectSocial Choiceen_US
dc.subjectFair Divisionen_US
dc.subjectGraph-Theoretic Methodsen_US
dc.titleFair Division via Social Comparisonen_US
dc.typeConference Paperen_US
dc.description.versionVersion of Recorden_US
dash.depositing.authorParkes, David
dc.date.available2019-10-22T13:30:37Z
dc.relation.bookProceedings of the 16th Conference on Autonomous Agents and MultiAgent Systemsen_US
dash.workflow.commentsFAR2017en_US
dash.contributor.affiliatedAbebe, Rediet
dash.contributor.affiliatedParkes, David


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record