dc.contributor.author Abebe, Rediet dc.contributor.author Kleinberg, Jon dc.contributor.author Parkes, David dc.date.accessioned 2019-10-22T13:30:37Z dc.identifier.citation Abebe, 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.uri http://nrs.harvard.edu/urn-3:HUL.InstRepos:41593087 * dc.description.abstract We 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.sponsorship Engineering and Applied Sciences en_US dc.language.iso en_US en_US dc.publisher ACM, Inc. en_US dc.relation.isversionof https://dl-acm-org.ezp-prod1.hul.harvard.edu/citation.cfm?id=3091171 en_US dc.relation.hasversion https://arxiv.org/abs/1611.06589 en_US dash.license META_ONLY dc.subject Social Choice en_US dc.subject Fair Division en_US dc.subject Graph-Theoretic Methods en_US dc.title Fair Division via Social Comparison en_US dc.type Conference Paper en_US dc.description.version Version of Record en_US dash.depositing.author Parkes, David dc.date.available 2019-10-22T13:30:37Z dc.relation.book Proceedings of the 16th Conference on Autonomous Agents and MultiAgent Systems en_US dash.workflow.comments FAR2017 en_US dash.contributor.affiliated Abebe, Rediet dash.contributor.affiliated Parkes, David
﻿