More Web Proxy on the site http://driver.im/

research-article

Fair enough: guaranteeing approximate maximin shares

Authors:

Ariel D. Procaccia,

Junxing WangAuthors Info & Claims

EC '14: Proceedings of the fifteenth ACM conference on Economics and computation

Pages 675 - 692

https://doi.org/10.1145/2600057.2602835

Published: 01 June 2014 Publication History

Abstract

We consider the problem of fairly allocating indivisible goods, focusing on a recently-introduced notion of fairness called maximin share guarantee: Each player's value for his allocation should be at least as high as what he can guarantee by dividing the items into as many bundles as there are players and receiving his least desirable bundle. Assuming additive valuation functions, we show that such allocations may not exist, but allocations guaranteeing each player 2/3 of the above value always exist, and can be computed in polynomial time when the number of players is constant. These theoretical results have direct practical implications.

References

[1]

ABDULKADIROĞLU, A., SÖONMEZ, T., AND ÜNVER, M. U. 2004. Room assignment-rent division: A market approach. Social Choice and Welfare 22, 3, 515--538.

[2]

ALON, N. 1987. Splitting necklaces. Advances in Mathematics 63, 241--253.

[3]

ASADPOUR, A. AND SABERI, A. 2007. An approximation algorithm for max-min fair allocation of indivisible goods. In Proceedings of the 39th Annual ACM Symposium on Theory of Computing (STOC). 114--121.

Digital Library

[4]

BANSAL, N. AND SVIRIDENKO, M. 2006. The Santa Claus problem. In Proceedings of the 38th Annual ACM Symposium on Theory of Computing (STOC). 31--40.

Digital Library

[5]

BEZÁKOVÁ, I. AND DANI, V. 2005. Allocating indivisible goods. SIGecom Exchanges 5, 3, 11--18.

Digital Library

[6]

BOUVERET, S. AND LEMAÎ TRE, M. 2014. Characterizing conflicts in fair division of indivisible goods using a scale of criteria. In Proceedings of the 13th International Conference on Autonomous Agents and Multi-Agent Systems (AAMAS). Forthcoming.

Digital Library

[7]

BRAMS, S. J., EDELMAN, P. H., AND FISHBURN, P. C. 2003. Fair division of indivisible items. Theory and Decision 55, 2, 147--180.

[8]

BRAMS, S. J., KILGOUR, M., AND KLAMLER, C. 2014. Two-person fair division of indivisible items: An efficient, envy-free algorithm. Notices of the AMS 61, 2, 130--141.

[9]

BRAMS, S. J. AND TAYLOR, A. D. 1995. An envy-free cake division protocol. The American Mathematical Monthly 102, 1, 9--18.

[10]

BRAMS, S. J. AND TAYLOR, A. D. 1996. Fair Division: From Cake-Cutting to Dispute Resolution. Cambridge University Press.

[11]

BUDISH, E. 2011. The combinatorial assignment problem: Approximate competitive equilibrium from equal incomes. Journal of Political Economy 119, 6, 1061--1103.

[12]

CARAGIANNIS, I., KAKLAMANIS, C., KANELLOPOULOS, P., AND KYROPOULOU, M. 2009. The efficiency of fair division. In Proceedings of the 5th International Workshop on Internet and Network Economics (WINE). 475--482.

Digital Library

[13]

DE CLIPPEL, G., MOULIN, H., AND TIDEMAN, N. 2008. Impartial division of a dollar. Journal of Economic Theory 139, 176--191.

[14]

DEMERS, A., KESHAV, S., AND SHENKER, S. 1989. Analysis and simulation of a fair queueing algorithm. In Proceedings of the ACM Symposium on Communications Architectures & Protocols (SIGCOMM). 1--12.

Digital Library

[15]

EDMONDS, J. AND PRUHS, K. 2006a. Balanced allocations of cake. In Proceedings of the 47th Symposium on Foundations of Computer Science (FOCS). 623--634.

Digital Library

[16]

EDMONDS, J. AND PRUHS, K. 2006b. Cake cutting really is not a piece of cake. In Proceedings of the 17th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 271--278.

Digital Library

[17]

GHODSI, A., ZAHARIA, M., HINDMAN, B., KONWINSKI, A., SHENKER, S., AND STOICA, I. 2011. Dominant resource fairness: Fair allocation of multiple resource types. In Proceedings of the 8th USENIX Conference on Networked Systems Design and Implementation (NSDI). 24--37.

Digital Library

[18]

HILL, T. 1987. Partitioning general probability measures. Annals of Probability 15, 2, 804--813.

[19]

LIPTON, R. J., MARKAKIS, E., MOSSEL, E., AND SABERI, A. 2004. On approximately fair allocations of indivisible goods. In Proceedings of the 6th ACM Conference on Electronic Commerce (EC). 125--131.

Digital Library

[20]

MAGDON-ISMAIL, M., BUSCH, C., AND KRISHNAMOORTHY, M. S. 2003. Cake cutting is not a piece of cake. In Proceedings of the 20th International Symposium on Theoretical Aspects of Computer Science (STACS). 596--607.

Digital Library

[21]

MARKAKIS, E. AND PSOMAS, C.-A. 2011. On worst-case allocations in the presence of indivisible goods. In Proceedings of the 5th International Workshop on Internet and Network Economics (WINE). 278--289.

Digital Library

[22]

MOULIN, H. 1990. Uniform externalities: Two axioms for fair allocation. Journal of Public Economics 43, 3, 305--326.

[23]

MOULIN, H. 2003. Fair Division and Collective Welfare. MIT Press.

[24]

PARKES, D. C., PROCACCIA, A. D., AND SHAH, N. 2012. Beyond Dominant Resource Fairness: Extensions, limitations, and indivisibilities. In Proceedings of the 13th ACM Conference on Electronic Commerce (EC). 808--825.

Digital Library

[25]

PAZNER, E. AND SCHMEIDLER, D. 1978. Egalitarian equivalent allocations: A new concept of economic equity. Quarterly Journal of Economics 92, 4, 671--687.

[26]

PROCACCIA, A. D. 2009. Thou shalt covet thy neighbor's cake. In Proceedings of the 21st International Joint Conference on Artificial Intelligence (IJCAI). 239--244.

Digital Library

[27]

PROCACCIA, A. D. 2013. Cake cutting: Not just child's play. Communications of the ACM 56, 7, 78--87.

Digital Library

[28]

WOEGINGER, G. 1997. A polynomial-time approximation scheme for maximizing the minimum machine completion time. Operations Research Letters 20, 4, 149--154.

Digital Library

[29]

WOEGINGER, G. J. AND SGALL, J. 2007. On the complexity of cake cutting. Discrete Optimization 4, 213--220.

Digital Library

Cited By

Kulkarni PKulkarni RMehta RDastani MSichman JAlechina NDignum V(2024)Approximating APS Under Submodular and XOS Valuations with Binary MarginalsProceedings of the 23rd International Conference on Autonomous Agents and Multiagent Systems10.5555/3635637.3662961(1057-1065)Online publication date: 6-May-2024
https://dl.acm.org/doi/10.5555/3635637.3662961
Babichenko YFeldman MHolzman RNarayan VMohar BShinkar IO'Donnell R(2024)Fair Division via Quantile SharesProceedings of the 56th Annual ACM Symposium on Theory of Computing10.1145/3618260.3649728(1235-1246)Online publication date: 10-Jun-2024
https://dl.acm.org/doi/10.1145/3618260.3649728
Dai SGuo XMiao HGao GXu YZhang Y(2024)The existence and efficiency of PMMS allocationsTheoretical Computer Science10.1016/j.tcs.2024.114388989:COnline publication date: 21-Mar-2024
https://dl.acm.org/doi/10.1016/j.tcs.2024.114388
Show More Cited By

Index Terms

Fair enough: guaranteeing approximate maximin shares
1. Applied computing
  1. Law, social and behavioral sciences
    1. Economics
2. Theory of computation
  1. Design and analysis of algorithms

Recommendations

Fair Public Decision Making
EC '17: Proceedings of the 2017 ACM Conference on Economics and Computation

We generalize the classic problem of fairly allocating indivisible goods to the problem of fair public decision making, in which a decision must be made on several social issues simultaneously, and, unlike the classic setting, a decision can provide ...
Fair Division of Indivisible Goods Among Strategic Agents
AAMAS '19: Proceedings of the 18th International Conference on Autonomous Agents and MultiAgent Systems

We study fair division of indivisible goods among strategic agents in a single-parameter environment. This work specifically considers fairness in terms of envy freeness up to one good (EF1) and maximin share guarantee (MMS). We show that (in a single-...
Mechanism design for fair division: allocating divisible items without payments
EC '13: Proceedings of the fourteenth ACM conference on Electronic commerce

We revisit the classic problem of fair division from a mechanism design perspective and provide an elegant truthful mechanism that yields surprisingly good approximation guarantees for the widely used solution of Proportional Fairness. This solution, ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

EC '14: Proceedings of the fifteenth ACM conference on Economics and computation

June 2014

1028 pages

ISBN:9781450325653

DOI:10.1145/2600057

General Chair:
Moshe Babaioff
Microsoft Research
,
Program Chairs:
Vincent Conitzer
Duke University
,
David Easley
Cornell University

Copyright © 2014 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGecom: Special Interest Group on Economics and Computation

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 June 2014

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

Conference

EC '14

Sponsor:

SIGecom

EC '14: ACM Conference on Economics and Computation

June 8 - 12, 2014

California, Palo Alto, USA

Acceptance Rates

EC '14 Paper Acceptance Rate 80 of 290 submissions, 28%;

Overall Acceptance Rate 664 of 2,389 submissions, 28%

Upcoming Conference

EC '25

Sponsor:
sigecom

The 25th ACM Conference on Economics and Computation

July 7 - 11, 2025

Stanford , CA , USA

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

104
Total Citations
View Citations
572
Total Downloads

Downloads (Last 12 months)67
Downloads (Last 6 weeks)8

Reflects downloads up to 19 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Kulkarni PKulkarni RMehta RDastani MSichman JAlechina NDignum V(2024)Approximating APS Under Submodular and XOS Valuations with Binary MarginalsProceedings of the 23rd International Conference on Autonomous Agents and Multiagent Systems10.5555/3635637.3662961(1057-1065)Online publication date: 6-May-2024
https://dl.acm.org/doi/10.5555/3635637.3662961
Babichenko YFeldman MHolzman RNarayan VMohar BShinkar IO'Donnell R(2024)Fair Division via Quantile SharesProceedings of the 56th Annual ACM Symposium on Theory of Computing10.1145/3618260.3649728(1235-1246)Online publication date: 10-Jun-2024
https://dl.acm.org/doi/10.1145/3618260.3649728
Dai SGuo XMiao HGao GXu YZhang Y(2024)The existence and efficiency of PMMS allocationsTheoretical Computer Science10.1016/j.tcs.2024.114388989:COnline publication date: 21-Mar-2024
https://dl.acm.org/doi/10.1016/j.tcs.2024.114388
Li LDeng B(2024)Fair Division with Weighted and Prioritized AgentsAlgorithmic Aspects in Information and Management10.1007/978-981-97-7801-0_15(171-181)Online publication date: 21-Sep-2024
https://dl.acm.org/doi/10.1007/978-981-97-7801-0_15
Lonc ZElkind E(2023)Approximating fair division on D-claw-free graphsProceedings of the Thirty-Second International Joint Conference on Artificial Intelligence10.24963/ijcai.2023/315(2826-2834)Online publication date: 19-Aug-2023
https://dl.acm.org/doi/10.24963/ijcai.2023/315
Sengupta RNagi RSreenivas R(2023)Equitable Allocation of Operations and Makespan Minimization for Autonomous AgentsIEEE Transactions on Automation Science and Engineering10.1109/TASE.2022.318153020:1(703-717)Online publication date: Jan-2023
https://doi.org/10.1109/TASE.2022.3181530
Zulauf KWagner R(2023)Countering Negotiation Power Asymmetries by Using the Adjusted Winner AlgorithmOperations Research Forum10.1007/s43069-023-00206-74:1Online publication date: 10-Mar-2023
https://doi.org/10.1007/s43069-023-00206-7
Biswas APayan JSengupta RViswanathan V(2023)The Theory of Fair Allocation Under Structured Set ConstraintsEthics in Artificial Intelligence: Bias, Fairness and Beyond10.1007/978-981-99-7184-8_7(115-129)Online publication date: 30-Dec-2023
https://doi.org/10.1007/978-981-99-7184-8_7
Cousins CViswanathan VZick Y(2023)Dividing Good and Great Items Among Agents with Bivalued Submodular ValuationsWeb and Internet Economics10.1007/978-3-031-48974-7_13(225-241)Online publication date: 31-Dec-2023
https://doi.org/10.1007/978-3-031-48974-7_13
Cousins CViswanathan VZick Y(2023)The Good, the Bad and the Submodular: Fairly Allocating Mixed Manna Under Order-Neutral Submodular PreferencesWeb and Internet Economics10.1007/978-3-031-48974-7_12(207-224)Online publication date: 31-Dec-2023
https://doi.org/10.1007/978-3-031-48974-7_12
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents