research-article

Approximating the Nash Social Welfare with Indivisible Items

Authors:

Vasilis GkatzelisAuthors Info & Claims

STOC '15: Proceedings of the forty-seventh annual ACM symposium on Theory of Computing

Pages 371 - 380

https://doi.org/10.1145/2746539.2746589

Published: 14 June 2015 Publication History

Abstract

We study the problem of allocating a set of indivisible items among agents with additive valuations, with the goal of maximizing the geometric mean of the agents' valuations, i.e., the Nash social welfare. This problem is known to be NP-hard, and our main result is the first efficient constant-factor approximation algorithm for this objective. We first observe that the integrality gap of the natural fractional relaxation is exponential, so we propose a different fractional allocation which implies a tighter upper bound and, after appropriate rounding, yields a good integral allocation.

An interesting contribution of this work is the fractional allocation that we use. The relaxation of our problem can be solved efficiently using the Eisenberg-Gale program, whose optimal solution can be interpreted as a market equilibrium with the dual variables playing the role of item prices. Using this market-based interpretation, we define an alternative equilibrium allocation where the amount of spending that can go into any given item is bounded, thus keeping the highly priced items under-allocated, and forcing the agents to spend on lower priced items. The resulting equilibrium prices reveal more information regarding how to assign items so as to obtain a good integral allocation.

References

[1]

G. Amanatidis, E. Markakis, A. Nikzad, and A. Saberi. Approximation algorithms for computing maximin share allocations. In ICALP, 2015 (to appear).

[2]

M. Andrews, L. Qian, and A. L. Stolyar. Optimal utility based multi-user throughput allocation subject to throughput constraints. In INFOCOM, pages 2415--2424, 2005.

[3]

C. Annamalai, C. Kalaitzis, and O. Svensson. Combinatorial algorithm for restricted max-min fair allocation. In ACM-SIAM Symposium on Discrete Algorithms, SODA, pages 1357--1372, 2015.

Digital Library

[4]

A. Asadpour and A. Saberi. An approximation algorithm for max-min fair allocation of indivisible goods. SIAM J. Comput., 39 (7): 2970--2989, 2010.

Digital Library

[5]

A. Asadpour, U. Feige, and A. Saberi. Santa Claus meets hypergraph matchings. ACM Transactions on Algorithms, 8 (3): 24, 2012.

Digital Library

[6]

N. Bansal and M. Sviridenko. The Santa Claus problem. In ACM Symposium on Theory of Computing, pages 31--40, 2006.

Digital Library

[7]

J. Barbanel. The Geometry of Efficient Fair Division. Cambridge University Press, 2004.

[8]

S. Bouveret and M. Lemaıtre. Characterizing conflicts in fair division of indivisible goods using a scale of criteria. AAMAS '14, pages 1321--1328, 2014.

Digital Library

[9]

S. Brams and A. Taylor. Fair Division: from cake cutting to dispute resolution. Cambridge University Press, Cambridge, 1996.

[10]

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

[11]

Y. Chevaleyre, U. Endriss, S. Estivie, and N. Maudet. Reaching envy-free states in distributed negotiation settings. In Int. Joint Conference on Artifical Intelligence, pages 1239--1244, 2007.

Digital Library

[12]

Cole, Gkatzelis, and Goel}CGG13R. Cole, V. Gkatzelis, and G. Goel. Positive results for mechanism design without money. In AAMAS '13, pages 1165--1166, 2013\natexlaba.

Digital Library

[13]

Cole, Gkatzelis, and Goel}Fair_CGG13R. Cole, V. Gkatzelis, and G. Goel. Mechanism design for fair division: allocating divisible items without payments. In ACM Conference on Electronic Commerce, EC '13, pages 251--268, 2013\natexlabb.

Digital Library

[14]

A. Darmann and J. Schauer. Maximizing nash product social welfare in allocating indivisible goods. 2014. URL http://ssrn.com/abstract=2410766.

[15]

N. Devanur, C. Papadimitriou, A. Saberi, and V. Vazirani. Market equilibrium via a primal-dual algorithm for a convex program. JACM., 55 (5): 1--22, 2008.

Digital Library

[16]

E. Eisenberg and D. Gale. Consensus of subjective probabilities: The pari-mutuel method. Ann. Math. Stat., 30: 165--168, 1959.

[17]

U. Feige. On allocations that maximize fairness. In ACM-SIAM Symposium on Discrete Algorithms, SODA, pages 287--293, 2008.

Digital Library

[18]

A. Hylland and R. Zeckhauser. The Efficient Allocation of Individuals to Positions. Journal of Political Economy, 87 (2): 293--314, April 1979.

[19]

M. Kaneko and K. Nakamura. The nash social welfare function. Econometrica, 47 (2): pp. 423--435, 1979.

[20]

F. P. Kelly. Charging and rate control for elastic traffic. European Transactions on Telecommunications, 8: 33--37, 1997.

[21]

F. P. Kelly, A. K. Maulloo, and D. K. H. Tan. Rate control in communication networks: shadow prices, proportional fairness and stability. Journal of Operational Research Society, 49: 237--252, 1998.

[22]

R. J. Lipton, E. Markakis, E. Mossel, and A. Saberi. On approximately fair allocations of indivisible goods. In Proceedings ACM Conference on Electronic Commerce (EC-2004), pages 125--131, 2004.

Digital Library

[23]

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

[24]

J. Nash. The bargaining problem. Econometrica, 18 (2): 155--162, April 1950.

[25]

N.-T. Nguyen, T. Nguyen, M. Roos, and J. Rothe. Computational complexity and approximability of social welfare optimization in multiagent resource allocation. AAMAS '14, 28 (2): 256--289, 2014.

Digital Library

[26]

T. Nguyen, M. Roos, and J. Rothe. A survey of approximability and inapproximability results for social welfare optimization in multiagent resource allocation. AMAI, 68 (1--3): 65--90, 2013.

Digital Library

[27]

T. T. Nguyen and J. Rothe. Minimizing envy and maximizing average nash social welfare in the allocation of indivisible goods. Discrete Applied Mathematics, 179 (0): 54 -- 68, 2014.

Digital Library

[28]

N. Nisan, T. Roughgarden, É. Tardos, and V. Vazirani. Algorithmic Game Theory. Cambridge University Press, New York, NY, USA, 2007.

[29]

J. B. Orlin. Improved algorithms for computing Fisher's market clearing prices: computing fisher's market clearing prices. In ph42nd ACM Symposium on Theory of Computing, STOC, pages 291--300, 2010.

Digital Library

[30]

A. Othman, C. H. Papadimitriou, and A. Rubinstein. The complexity of fairness through equilibrium. In ACM Conference on Economics and Computation, EC '14, pages 209--226, 2014.

Digital Library

[31]

A. D. Procaccia and J. Wang. Fair enough: guaranteeing approximate maximin shares. In ACM Conference on Economics and Computation, EC '14, pages 675--692, 2014.

Digital Library

[32]

S. Ramezani and U. Endriss. Nash social welfare in multiagent resource allocation. In Agent-Mediated Electronic Commerce, volume 59, pages 117--131. 2010.

[33]

J. Robertson and W. Webb. Cake-cutting algorithms - be fair if you can. A K Peters, 1998.

[34]

J. Uckelman and U. Endriss. Compactly representing utility functions using weighted goals and the max aggregator. Artif. Intell., 174 (15): 1222--1246, 2010.

Digital Library

[35]

H. Varian. Equity, envy, and efficiency. Journal of Economic Theory, 9 (1): 63--91, 1974.

[36]

H. Young. Equity. Princeton University Press, 1995.

Cited By

Liao WJin YWang ZWang XXia X(2024)Maximizing Nash Social Welfare Based on Greedy Algorithm and Estimation of Distribution AlgorithmBiomimetics10.3390/biomimetics91106529:11(652)Online publication date: 24-Oct-2024
https://doi.org/10.3390/biomimetics9110652
Dai SGao GLiu SLim BNing LXu YZhang Y(2024)Maximum Nash Social Welfare Under Budget-Feasible EFXIEEE Transactions on Network Science and Engineering10.1109/TNSE.2023.333210411:2(1810-1820)Online publication date: Mar-2024
https://doi.org/10.1109/TNSE.2023.3332104
Samieefar K(2023)A Meta-heuristic Approach for Strategic Fair Division ProblemsProceedings of the 2023 7th International Conference on Intelligent Systems, Metaheuristics & Swarm Intelligence10.1145/3596947.3596969(87-94)Online publication date: 23-Apr-2023
https://dl.acm.org/doi/10.1145/3596947.3596969
Show More Cited By

Index Terms

Approximating the Nash Social Welfare with Indivisible Items
1. Theory of computation
  1. Randomness, geometry and discrete structures

Recommendations

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 ...
Approximating the nash social welfare with indivisible items

In this letter we briefly discuss our main result from [Cole and Gkatzelis 2015]. Given a set of indivisible items and a set of agents having additive valuations, our goal is to allocate the items to the agents in order to maximize the geometric mean of ...
Approximating the Nash Social Welfare with Indivisible Items

We study the problem of allocating a set of indivisible items among agents with additive valuations, with the goal of maximizing the geometric mean of the agents' valuations, i.e., the Nash social welfare. This problem is known to be NP-hard, and our ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

STOC '15: Proceedings of the forty-seventh annual ACM symposium on Theory of Computing

June 2015

916 pages

ISBN:9781450335362

DOI:10.1145/2746539

General Chair:
Rocco Servedio
Columbia University
,
Program Chair:
Ronitt Rubinfeld
MIT and Tel Aviv University

Copyright © 2015 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

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 14 June 2015

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

Conference

STOC '15

Sponsor:

SIGACT

STOC '15: Symposium on Theory of Computing

June 14 - 17, 2015

Oregon, Portland, USA

Acceptance Rates

STOC '15 Paper Acceptance Rate 93 of 347 submissions, 27%;

Overall Acceptance Rate 1,469 of 4,586 submissions, 32%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

45
Total Citations
View Citations
620
Total Downloads

Downloads (Last 12 months)73
Downloads (Last 6 weeks)15

Reflects downloads up to 16 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Liao WJin YWang ZWang XXia X(2024)Maximizing Nash Social Welfare Based on Greedy Algorithm and Estimation of Distribution AlgorithmBiomimetics10.3390/biomimetics91106529:11(652)Online publication date: 24-Oct-2024
https://doi.org/10.3390/biomimetics9110652
Dai SGao GLiu SLim BNing LXu YZhang Y(2024)Maximum Nash Social Welfare Under Budget-Feasible EFXIEEE Transactions on Network Science and Engineering10.1109/TNSE.2023.333210411:2(1810-1820)Online publication date: Mar-2024
https://doi.org/10.1109/TNSE.2023.3332104
Samieefar K(2023)A Meta-heuristic Approach for Strategic Fair Division ProblemsProceedings of the 2023 7th International Conference on Intelligent Systems, Metaheuristics & Swarm Intelligence10.1145/3596947.3596969(87-94)Online publication date: 23-Apr-2023
https://dl.acm.org/doi/10.1145/3596947.3596969
Dobzinski SOren SVondrak JLeyton-Brown KSamuelson LHartline J(2023)Fairness and Incentive Compatibility via Percentage FeesProceedings of the 24th ACM Conference on Economics and Computation10.1145/3580507.3597810(517-535)Online publication date: 9-Jul-2023
https://dl.acm.org/doi/10.1145/3580507.3597810
Meskar ELiang B(2023)Fair Multi-Resource Allocation in Heterogeneous Servers With an External Resource TypeIEEE/ACM Transactions on Networking10.1109/TNET.2022.321342631:3(1244-1262)Online publication date: Jun-2023
https://doi.org/10.1109/TNET.2022.3213426
Garg JMurhekar A(2023)Computing fair and efficient allocations with few utility valuesTheoretical Computer Science10.1016/j.tcs.2023.113932962(113932)Online publication date: Jun-2023
https://doi.org/10.1016/j.tcs.2023.113932
Sun AChen BDoan X(2023)Fairness criteria for allocating indivisible chores: connections and efficienciesAutonomous Agents and Multi-Agent Systems10.1007/s10458-023-09618-537:2Online publication date: 31-Aug-2023
https://doi.org/10.1007/s10458-023-09618-5
Huang ZLi MShu XWei T(2023)Online Nash Welfare Maximization Without PredictionsWeb and Internet Economics10.1007/978-3-031-48974-7_23(402-419)Online publication date: 31-Dec-2023
https://doi.org/10.1007/978-3-031-48974-7_23
Dai SGao GLiu SLim BNing LXu YZhang Y(2023)EFX Under Budget ConstraintFrontiers of Algorithmic Wisdom10.1007/978-3-031-20796-9_1(3-14)Online publication date: 1-Jan-2023
https://doi.org/10.1007/978-3-031-20796-9_1
Brown ALaddha APittu MSingh MTetali P(2022)Determinant Maximization via Matroid Intersection Algorithms2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS)10.1109/FOCS54457.2022.00031(255-266)Online publication date: Oct-2022
https://doi.org/10.1109/FOCS54457.2022.00031
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