TY - CONF
T1 - On Maxsum Fair Cake Divisions
AU - Brams, Steven J.
AU - Feldman, Michal
AU - Lai, John K.
AU - Morgenstern, Jamie
AU - Procaccia, Ariel D.
N1 - Funding Information:
This work was partially supported by the Israel Science Foundation (grant number 1219/09), by the Leon Recanati Fund of the Jerusalem School of Business Administration, the Google Inter-university center for Electronic Markets and Auctions, and the People Programme (Marie Curie Actions) of the European Union’s Seventh Framework Programme (FP7/2007-2013) under REA grant agreement number 274919. John Lai is supported by an NDSEG fellowship. Jamie Morgenstern is supported by an NSF GRFP fellowship and a Microsoft Research Graduate Women’s Scholarship.
Funding Information:
This work was partially supported by the Israel Science Foundation (grant number 1219/09), by the Leon Recanati Fund of the Jerusalem School of Business Administration, the Google Inter-university center for Electronic Markets and Auctions, and the People Programme (Marie Curie Actions) of the European Union's Seventh Framework Programme (FP7/2007-2013) under REA grant agreement number 274919. John Lai is supported by an NDSEG fellowship. Jamie Morgenstern is supported by an NSF GRFP fellowship and a Microsoft Research Graduate Women's Scholarship.
Publisher Copyright:
Copyright © 2012, Association for the Advancement of Artificial Intelligence (www.aaai.org). All rights reserved.
PY - 2012
Y1 - 2012
N2 - We consider the problem of selecting fair divisions of a heterogeneous divisible good among a set of agents. Recent work (Cohler et al., AAAI 2011) focused on designing algorithms for computing maxsum-social welfare maximizing-allocations under the fairness notion of envy-freeness. Maxsum allocations can also be found under alternative notions such as equitability. In this paper, we examine the properties of these allocations. In particular, we provide conditions for when maxsum envy-free or equitable allocations are Pareto optimal and give examples where fairness with Pareto optimality is not possible. We also prove that maxsum envy-free allocations have weakly greater welfare than maxsum equitable allocations when agents have structured valuations, and we derive an approximate version of this inequality for general valuations.
AB - We consider the problem of selecting fair divisions of a heterogeneous divisible good among a set of agents. Recent work (Cohler et al., AAAI 2011) focused on designing algorithms for computing maxsum-social welfare maximizing-allocations under the fairness notion of envy-freeness. Maxsum allocations can also be found under alternative notions such as equitability. In this paper, we examine the properties of these allocations. In particular, we provide conditions for when maxsum envy-free or equitable allocations are Pareto optimal and give examples where fairness with Pareto optimality is not possible. We also prove that maxsum envy-free allocations have weakly greater welfare than maxsum equitable allocations when agents have structured valuations, and we derive an approximate version of this inequality for general valuations.
UR - http://www.scopus.com/inward/record.url?scp=84868289328&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84868289328&partnerID=8YFLogxK
M3 - Paper
AN - SCOPUS:84868289328
SP - 1285
EP - 1291
T2 - 26th AAAI Conference on Artificial Intelligence, AAAI 2012
Y2 - 22 July 2012 through 26 July 2012
ER -