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

research-article

Public Access

Leximin Allocations in the Real World

Authors:

David Kurokawa,

Ariel D. Procaccia,

Nisarg ShahAuthors Info & Claims

ACM Transactions on Economics and Computation (TEAC), Volume 6, Issue 3-4

Article No.: 11, Pages 1 - 24

https://doi.org/10.1145/3274641

Published: 23 October 2018 Publication History

All formats PDF

Abstract

As part of a collaboration with a major California school district, we study the problem of fairly allocating unused classrooms in public schools to charter schools. Our approach revolves around the randomized leximin mechanism. We extend previous work to show that the leximin mechanism is proportional, envy-free, Pareto optimal, and group strategyproof, not only in our classroom allocation setting, but in a general framework that subsumes a number of settings previously studied in the literature. We also prove that the leximin mechanism provides a (worst-case) 4-approximation to the maximum number of classrooms that can possibly be allocated. Our experiments, which are based on real data, show that a non-trivial implementation of the leximin mechanism scales gracefully in terms of running time (even though the problem is intractable in theory), and performs extremely well with respect to a number of efficiency objectives. We establish the practicability of our approach, and discuss issues related to its deployment.

References

[1]

A. Abdulkadiroğlu, T. Sönmez, and M. U. Ünver. 2004. Room assignment-rent division: A market approach. Social Choice and Welfare 22, 3 (2004), 515--538.

[2]

N. Anari, T. Mai, S. O. Gharan, and V. V. Vazirani. 2016. Nash social welfare for indivisible items under separable, piecewise-linear concave utilities. In Proceedings of the 29th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA’18), 2274--2290.

Digital Library

[3]

H. Aziz. 2014. Random assignment with multi-unit demands. arXiv:1401.7700.

[4]

G. Birkhoff. 1946. Three observations on linear algebra. Universidad Nacional de Tucumán, Revista A 5 (1946), 147--151.

[5]

O. Bochet, R. Ilkılıç, H. Moulin, and J. Sethuraman. 2012. Balancing supply and demand under bilateral constraints. Theoretical Economics 7, 3 (2012), 395--423.

[6]

A. Bogomolnaia and H. Moulin. 2001. A new solution to the random assignment problem. Journal of Economic Theory 100 (2001), 295--328.

[7]

A. Bogomolnaia and H. Moulin. 2004. Random matching under dichotomous preferences. Econometrica 72 (2004), 257--279.

[8]

A. Bogomolnaia, H. Moulin, and R. Stong. 2005. Collective choice under dichotomous preferences. Journal of Economic Theory 122, 2 (2005), 165--184.

[9]

S. J. Brams and A. D. Taylor. 1996. Fair Division: From Cake-Cutting to Dispute Resolution. Cambridge University Press.

[10]

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

[11]

E. Budish, Y.-K. Che, F. Kojima, and P. Milgrom. 2013. Designing random allocation mechanisms: Theory and applications. American Economic Review 103, 2 (2013), 585--623.

[12]

Y. K. Che and F. Kojima. 2010. Asymptotic equivalence of probabilistic serial and random priority mechanisms. Econometrica 78, 5 (2010), 1625--1672.

[13]

Y. Chen, J. K. Lai, D. C. Parkes, and A. D. Procaccia. 2013. Truth, justice, and cake cutting. Games and Economic Behavior 77 (2013), 284--297.

[14]

T. S. H. Driessen. 1988. Cooperative Games, Solutions and Applications. Springer.

[15]

G. Freitas. 2010. Combinatorial Assignment under Dichotomous Preferences. Manuscript.

[16]

R. M. Freund and S. Mizuno. 2000. Interior Point Methods: Current Status and Future Directions. Springer.

[17]

R. M. Freund, R. Roundy, and M. Todd. 1985. Identifying the Set of Always-Active Constraints in a System of Linear Inequalities by a Single Linear Program. Technical Report 1674-85. Massachusetts Institute of Technology (MIT), Sloan School of Management.

[18]

A. Ghodsi, M. Zaharia, B. Hindman, A. Konwinski, S. Shenker, and I. Stoica. 2011. Dominant resource fairness: Fair allocation of multiple resource types. In Proceedings of the 8th USENIX Conference on Networked Systems Design and Implementation (NSDI’11). 24--37.

Digital Library

[19]

J. Goldman and A. D. Procaccia. 2014. Spliddit: Unleashing fair division algorithms. SIGecom Exchanges 13, 2 (2014), 41--46.

Digital Library

[20]

A. Hylland and R. Zeckhauser. 1979. The efficient allocation of individuals to positions. The Journal of Political Economy 87, 2 (1979), 293--314.

[21]

L. Khachiyan. 1979. A polynomial algorithm in linear programming. Soviet Mathematics Doklady 20 (1979), 191--194.

[22]

F. Kojima. 2009. Random assignment of multiple indivisible objects. Mathematical Social Sciences 57, 1 (2009), 134--142.

[23]

W. Li, X. Zhang, and X. Zhang. 2014. Multi-Resource Fair Allocation with Bounded Number of Tasks in Cloud Computing Systems. arXiv:1410.1255.

[24]

H. Moulin. 2003. Fair Division and Collective Welfare. MIT Press.

[25]

Dritan Nace and James B. Orlin. 2007. Lexicographically minimum and maximum load linear programming problems. Operations Research 55, 1 (2007), 182--187.

Digital Library

[26]

A. Othman, C. H. Papadimitriou, and A. Rubinstein. 2014. The complexity of fairness through equilibrium. In Proceedings of the 15th ACM Conference on Electronic Commerce (EC’14). 209--226.

Digital Library

[27]

A. Othman, T. Sandholm, and E. Budish. 2010. Finding approximate competitive equilibria: Efficient and fair course allocation. In Proceedings of the 9th International Joint Conference on Autonomous Agents and Multi-Agent Systems (AAMAS’10). 873--880.

Digital Library

[28]

D. C. Parkes, A. D. Procaccia, and N. Shah. 2015. Beyond dominant resource fairness: Extensions, limitations, and indivisibilities. ACM Transactions on Economics and Computation 3, 1 (2015).

Digital Library

[29]

E. Pazner and D. Schmeidler. 1978. Egalitarian equivalent allocations: A new concept of economic equity. Quarterly Journal of Economics 92, 4 (1978), 671--687.

[30]

A. D. Procaccia. 2013. Cake cutting: Not just child’s play. Communications of the ACM 56, 7 (2013), 78--87.

Digital Library

[31]

M. Pycia. 2011. Assignment with Multiple-Unit Demands and Responsive Preferences. Manuscript.

[32]

J. M. Robertson and W. A. Webb. 1998. Cake Cutting Algorithms: Be Fair If You Can. A. K. Peters.

[33]

A. E. Roth. 1986. On the allocation of residents to rural hospitals: A general property of two-sided matching markets. Econometrica (1986), 425--427.

[34]

A. E. Roth, T. Sönmez, and M. U. Ünver. 2005. Pairwise kidney exchange. Journal of Economic Theory 125 (2005), 151--188.

[35]

E. Tardos. 1986. A strongly polynomial algorithm to solve combinatorial linear programs. Operations Research 34, 2 (1986), 250--256.

[36]

J. von Neumann. 1953. A certain zero-sum two-person game equivalent to the optimal assignment problem. In Contributions to the Theory of Games, W. Kuhn and A. W. Tucker (Eds.). Vol. 2. 5--12.

Cited By

Anandanarayanan RNath SVaish RDastani MSichman JAlechina NDignum V(2024)Charging Electric Vehicles Fairly and EfficientlyProceedings of the 23rd International Conference on Autonomous Agents and Multiagent Systems10.5555/3635637.3663082(2126-2128)Online publication date: 6-May-2024
https://dl.acm.org/doi/10.5555/3635637.3663082
Chaudhury BGarg JMehlhorn K(2024)EFX Exists for Three AgentsJournal of the ACM10.1145/361600971:1(1-27)Online publication date: 11-Feb-2024
https://dl.acm.org/doi/10.1145/3616009
Tao BWu XYu ZZhou S(2024)On the Existence of EFX (and Pareto-Optimal) Allocations for Binary ChoresFrontiers of Algorithmics10.1007/978-981-97-7752-5_3(33-52)Online publication date: 29-Dec-2024
https://doi.org/10.1007/978-981-97-7752-5_3
Show More Cited By

Index Terms

Leximin Allocations in the Real World

Recommendations

Finding Fair and Efficient Allocations for Matroid Rank Valuations
In this article, we present new results on the fair and efficient allocation of indivisible goods to agents whose preferences correspond to matroid rank functions. This is a versatile valuation class with several desirable properties (such as monotonicity ...
Leximin Allocations in the Real World
EC '15: Proceedings of the Sixteenth ACM Conference on Economics and Computation

As part of a collaboration with a major California school district, we study the problem of fairly allocating unused classrooms in public schools to charter schools. Our approach revolves around the randomized leximin mechanism. We extend previous work ...
Finding Fair and Efficient Allocations
EC '18: Proceedings of the 2018 ACM Conference on Economics and Computation

We study the problem of allocating a set of indivisible goods among a set of agents in a fair and efficient manner. An allocation is said to be fair if it is envy-free up to one good (EF1), which means that each agent prefers its own bundle over the ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on Economics and Computation

ACM Transactions on Economics and Computation Volume 6, Issue 3-4

Special Issue on EC'15

November 2018

249 pages

ISSN:2167-8375

EISSN:2167-8383

DOI:10.1145/3281297

Editors:
David Pennock
Microsoft
,
Ilya Segal
Stanford University

Issue’s Table of Contents

Copyright © 2018 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 the author(s) 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].

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 23 October 2018

Accepted: 01 May 2018

Revised: 01 July 2017

Received: 01 December 2015

Published in TEAC Volume 6, Issue 3-4

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed

Funding Sources

NSF
Sloan Research Fellowship
NSERC under the Discovery Grants program

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

21
Total Citations
View Citations
602
Total Downloads

Downloads (Last 12 months)226
Downloads (Last 6 weeks)22

Reflects downloads up to 03 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Anandanarayanan RNath SVaish RDastani MSichman JAlechina NDignum V(2024)Charging Electric Vehicles Fairly and EfficientlyProceedings of the 23rd International Conference on Autonomous Agents and Multiagent Systems10.5555/3635637.3663082(2126-2128)Online publication date: 6-May-2024
https://dl.acm.org/doi/10.5555/3635637.3663082
Chaudhury BGarg JMehlhorn K(2024)EFX Exists for Three AgentsJournal of the ACM10.1145/361600971:1(1-27)Online publication date: 11-Feb-2024
https://dl.acm.org/doi/10.1145/3616009
Tao BWu XYu ZZhou S(2024)On the Existence of EFX (and Pareto-Optimal) Allocations for Binary ChoresFrontiers of Algorithmics10.1007/978-981-97-7752-5_3(33-52)Online publication date: 29-Dec-2024
https://doi.org/10.1007/978-981-97-7752-5_3
Barman SNarayan VVerma PAgmon NAn BRicci AYeoh W(2023)Fair Chore Division under Binary Supermodular CostsProceedings of the 2023 International Conference on Autonomous Agents and Multiagent Systems10.5555/3545946.3599104(2863-2865)Online publication date: 30-May-2023
https://dl.acm.org/doi/10.5555/3545946.3599104
Roussel SPicard GPralet CMaqrot S(2023)Conflicting Bundle Allocation with Preferences in Weighted Directed Acyclic Graphs: Application to Orbit Slot Allocation ProblemsSystems10.3390/systems1106029711:6(297)Online publication date: 9-Jun-2023
https://doi.org/10.3390/systems11060297
Shah NElkind E(2023)Pushing the limits of fairness in algorithmic decision-makingProceedings of the Thirty-Second International Joint Conference on Artificial Intelligence10.24963/ijcai.2023/806(7051-7056)Online publication date: 19-Aug-2023
https://dl.acm.org/doi/10.24963/ijcai.2023/806
Allouah AKroer CZhang XAvadhanula VBohanon NDania AGocmen CPupyrev SShah PStier-Moses NTaarup KSingh ASun YAkoglu LGunopulos DYan XKumar ROzcan FYe J(2023)Fair Allocation Over Time, with Applications to Content ModerationProceedings of the 29th ACM SIGKDD Conference on Knowledge Discovery and Data Mining10.1145/3580305.3599340(25-35)Online publication date: 6-Aug-2023
https://dl.acm.org/doi/10.1145/3580305.3599340
Airiau SAziz HCaragiannis IKruger JLang JPeters D(2023)Portioning using ordinal preferences: Fairness and efficiencyArtificial Intelligence10.1016/j.artint.2022.103809314(103809)Online publication date: Jan-2023
https://doi.org/10.1016/j.artint.2022.103809
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

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

HTML Format

View this article in HTML Format.

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 Article

Figures

Tables

Media

View Issue’s Table of Contents