research-article

Fair allocation of indivisible goods: : Beyond additive valuations

Authors:

Mohammad Ghodsi,

MohammadTaghi HajiAghayi,

Masoud Seddighin,

Saeed Seddighin,

Hadi YamiAuthors Info & Claims

Volume 303, Issue C

https://doi.org/10.1016/j.artint.2021.103633

Published: 01 February 2022 Publication History

Abstract

We conduct a study on the problem of fair allocation of indivisible goods when maximin share [1] is used as the measure of fairness. Most of the current studies on this notion are limited to the case that the valuations are additive. In this paper, we go beyond additive valuations and consider the cases that the valuations are submodular, fractionally subadditive, and subadditive. We give constant approximation guarantees for agents with submodular and XOS valuations, and a logarithmic bound for the case of agents with subadditive valuations. Furthermore, we complement our results by providing close upper bounds for each class of valuation functions. Finally, we present algorithms to find such allocations for submodular and XOS settings in polynomial time.

References

[1]

E. Budish, The combinatorial assignment problem: approximate competitive equilibrium from equal incomes, J. Polit. Econ. 119 (6) (2011) 1061–1103.

[2]

M. Ghodsi, M. HajiAghayi, M. Seddighin, S. Seddighin, H. Yami, Fair allocation of indivisible goods: improvements and generalizations, in: Proceedings of the 2018 ACM Conference on Economics and Computation, ACM, 2018, pp. 539–556.

[3]

S.J. Brams, A.D. Taylor, An envy-free cake division protocol, Am. Math. Mon. (1995) 9–18.

[4]

H. Steinhaus, The problem of fair division, Econometrica 16 (1) (1948).

[5]

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

[6]

L.E. Dubins, E.H. Spanier, How to cut a cake fairly, Am. Math. Mon. (1961) 1–17.

[7]

I. Bezáková, V. Dani, Allocating indivisible goods, ACM SIGecom Exch. 5 (3) (2005) 11–18.

[8]

D.K. Foley, Resource allocation and the public sector, Yale Economic Essays.

[9]

D. Kurokawa, A.D. Procaccia, J. Wang, Fair enough: guaranteeing approximate maximin shares, J. ACM 65 (2) (2018) 8.

[10]

R.J. Lipton, E. Markakis, E. Mossel, A. Saberi, On approximately fair allocations of indivisible goods, in: Proceedings of the 5th ACM Conference on Electronic Commerce, ACM, 2004, pp. 125–131.

[11]

W. Stromquist, How to cut a cake fairly, Am. Math. Mon. 87 (8) (1980) 640–644.

[12]

S. Even, A. Paz, A note on cake cutting, Discrete Appl. Math. 7 (3) (1984) 285–296.

[13]

V. Conitzer, R. Freeman, N. Shah, Fair public decision making, in: Proceedings of the 2017 ACM Conference on Economics and Computation, 2017.

[14]

I. Caragiannis, D. Kurokawa, H. Moulin, A.D. Procaccia, N. Shah, J. Wang, The unreasonable fairness of maximum Nash welfare, in: Proceedings of the 2016 ACM Conference on Economics and Computation, ACM, 2016, pp. 305–322.

[15]

J. Garg, S. Taki, An improved approximation algorithm for maximin shares, Artif. Intell. (2021).

[16]

G. Amanatidis, E. Markakis, A. Nikzad, A. Saberi, Approximation algorithms for computing maximin share allocations, ACM Trans. Algorithms 13 (4) (2017) 52.

[17]

S. Barman, S.K. Krishna Murthy, Approximation algorithms for maximin fair division, in: Proceedings of the 2017 ACM Conference on Economics and Computation, ACM, 2017, pp. 647–664.

[18]

J. Garg, S. Taki, An improved approximation algorithm for maximin shares, in: Proceedings of the 21st ACM Conference on Economics and Computation, 2020, pp. 379–380.

[19]

Feige, U.; Sapir, A.; Tauber, L. : A tight negative example for mms fair allocations. arXiv preprint arXiv:2104.04977.

[20]

J. Garg, P. Kulkarni, R. Kulkarni, Approximating Nash social welfare under submodular valuations through (un)matchings, in: Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SIAM, 2020, pp. 2673–2687.

[21]

Li, W.; Vondrák, J. : A constant-factor approximation algorithm for Nash social welfare with submodular valuations. arXiv preprint arXiv:2103.10536.

[22]

M. Bateni, M. Hajiaghayi, M. Zadimoghaddam, Submodular secretary problem and extensions, ACM Trans. Algorithms 9 (4) (2013) 32.

[23]

U. Feige, On maximizing welfare when utility functions are subadditive, SIAM J. Comput. 39 (1) (2009) 122–142.

[24]

U. Feige, V.S. Mirrokni, J. Vondrak, Maximizing non-monotone submodular functions, in: Foundations of Computer Science, 2007, FOCS'07, 48th Annual IEEE Symposium, IEEE, 2007, pp. 461–471.

[25]

D. Golovin, Max-min fair allocation of indivisible goods.

[26]

S. Dobzinski, N. Nisan, M. Schapira, Approximation algorithms for combinatorial auctions with complement-free bidders, in: Proceedings of the Thirty-Seventh Annual ACM Symposium on Theory of Computing, ACM, 2005, pp. 610–618.

[27]

U. Feige, J. Vondrak, Approximation algorithms for allocation problems: improving the factor of 1-1/e, in: Foundations of Computer Science, 2006, FOCS'06, 47th Annual IEEE Symposium, IEEE, 2006, pp. 667–676.

[28]

M. Feldman, N. Gravin, B. Lucier, Combinatorial auctions via posted prices, in: Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, Society for Industrial and Applied Mathematics, 2015, pp. 123–135.

[29]

R.P. Leme, Gross substitutability: an algorithmic survey, Games Econ. Behav. 106 (2017) 294–316.

[30]

J. Vondrák, Optimal approximation for the submodular welfare problem in the value oracle model, in: Proceedings of the Fortieth Annual ACM Symposium on Theory of Computing, ACM, 2008, pp. 67–74.

[31]

N. Buchbinder, M. Feldman, J. Naor, R. Schwartz, A tight linear time (1/2)-approximation for unconstrained submodular maximization, in: Foundations of Computer Science (FOCS), 2012 IEEE 53rd Annual Symposium, IEEE, 2012, pp. 649–658.

[32]

S. Fujishige, Submodular Functions and Optimization, vol. 58, Elsevier, 2005.

[33]

A. Gupta, A. Roth, G. Schoenebeck, K. Talwar, Constrained non-monotone submodular maximization: offline and secretary algorithms, in: International Workshop on Internet and Network Economics, Springer, 2010, pp. 246–257.

[34]

G. Kim, E.P. Xing, L. Fei-Fei, T. Kanade, Distributed cosegmentation via submodular optimization on anisotropic diffusion, in: Computer Vision (ICCV), 2011 IEEE International Conference, IEEE, 2011, pp. 169–176.

[35]

A. Krause, Sfo: a toolbox for submodular function optimization, J. Mach. Learn. Res. 11 (2010) 1141–1144.

[36]

J. Lee, V.S. Mirrokni, V. Nagarajan, M. Sviridenko, Non-monotone submodular maximization under matroid and knapsack constraints, in: Proceedings of the Forty-First Annual ACM Symposium on Theory of Computing, ACM, 2009, pp. 323–332.

[37]

M. Minoux, Accelerated greedy algorithms for maximizing submodular set functions, in: Optimization Techniques, Springer, 1978, pp. 234–243.

[38]

G. Christodoulou, A. Kovács, M. Schapira, Bayesian combinatorial auctions, in: International Colloquium on Automata, Languages, and Programming, Springer, 2008, pp. 820–832.

[39]

K. Bhawalkar, T. Roughgarden, Welfare guarantees for combinatorial auctions with item bidding, in: Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, Society for Industrial and Applied Mathematics, 2011, pp. 700–709.

[40]

L. Blumrosen, S. Dobzinski, Welfare maximization in congestion games, in: Proceedings of the 7th ACM Conference on Electronic Commerce, ACM, 2006, pp. 52–61.

[41]

Syrgkanis, V. : Bayesian games and the smoothness framework. arXiv preprint arXiv:1203.5155.

[42]

M. Feldman, H. Fu, N. Gravin, B. Lucier, Simultaneous auctions are (almost) efficient, in: Proceedings of the Forty-Fifth Annual ACM Symposium on Theory of Computing, 2013, pp. 201–210.

[43]

H. Fu, R. Kleinberg, R. Lavi, Conditional equilibrium outcomes via ascending price processes with applications to combinatorial auctions with item bidding, in: ACM EC, 2012.

[44]

I. Milchtaich, Congestion games with player-specific payoff functions, Games Econ. Behav. 13 (1) (1996) 111–124.

[45]

L. Epstein, A. Levin, An efficient polynomial time approximation scheme for load balancing on uniformly related machines, Math. Program. 147 (1–2) (2014) 1–23.

[46]

T. Heinen, N.-T. Nguyen, T.T. Nguyen, J. Rothe, Approximation and complexity of the optimization and existence problems for maximin share, proportional share, and minimax share allocation of indivisible goods, Auton. Agents Multi-Agent Syst. 32 (6) (2018) 741–778.

[47]

L. Gourvès, J. Monnot, Approximate maximin share allocations in matroids, in: International Conference on Algorithms and Complexity, Springer, 2017, pp. 310–321.

[48]

D. Kurokawa, A.D. Procaccia, J. Wang, When can the maximin share guarantee be guaranteed?, in: Proceedings of the AAAI Conference on Artificial Intelligence, Vol. 30, 2016.

[49]

A. Farhadi, M. Hajiaghayi, M. Ghodsi, S. Lahaie, D. Pennock, M. Seddighin, S. Seddighin, H. Yami, Fair allocation of indivisible goods to asymmetric agents, in: Proceedings of the 16th Conference on Autonomous Agents and MultiAgent Systems, International Foundation for Autonomous Agents and Multiagent Systems, 2017, pp. 1535–1537.

[50]

H. Aziz, G. Rauchecker, G. Schryen, T. Walsh, Algorithms for max-min share fair allocation of indivisible chores, in: Proceedings of the AAAI Conference on Artificial Intelligence, Vol. 31, 2017.

[51]

G. Amanatidis, G. Birmpas, G. Christodoulou, E. Markakis, Truthful allocation mechanisms without payments: characterization and implications on fairness, in: Proceedings of the 2017 ACM Conference on Economics and Computation, ACM, 2017, pp. 545–562.

[52]

G. Amanatidis, G. Birmpas, E. Markakis, On truthful mechanisms for maximin share allocations, in: Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence, AAAI Press, 2016, pp. 31–37.

[53]

S. Bouveret, M. Lemaître, Characterizing conflicts in fair division of indivisible goods using a scale of criteria, Auton. Agents Multi-Agent Syst. 30 (2) (2016) 259–290.

[54]

B. Plaut, T. Roughgarden, Almost envy-freeness with general valuations, in: Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SIAM, 2018, pp. 2584–2603.

[55]

S. Barman, S.K. Krishnamurthy, R. Vaish, Finding fair and efficient allocations, in: Proceedings of the 2018 ACM Conference on Economics and Computation, 2018, pp. 557–574.

[56]

S. Barman, S.K. Krishnamurthy, R. Vaish, Greedy algorithms for maximizing Nash social welfare, in: Proceedings of the 17th International Conference on Autonomous Agents and MultiAgent Systems, 2018, pp. 7–13.

[57]

N. Anari, T. Mai, S.O. Gharan, V.V. Vazirani, Nash social welfare for indivisible items under separable, piecewise-linear concave utilities, in: Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SIAM, 2018, pp. 2274–2290.

[58]

R. Cole, N. Devanur, V. Gkatzelis, K. Jain, T. Mai, V.V. Vazirani, S. Yazdanbod, Convex program duality, Fisher markets, and Nash social welfare, in: Proceedings of the 2017 ACM Conference on Economics and Computation, ACM, 2017, pp. 459–460.

Cited By

Montanari LSchmidt-Kraepelin USuksompong WTeh NWooldridge MDy JNatarajan S(2024)Weighted envy-freeness for submodular valuationsProceedings of the Thirty-Eighth AAAI Conference on Artificial Intelligence and Thirty-Sixth Conference on Innovative Applications of Artificial Intelligence and Fourteenth Symposium on Educational Advances in Artificial Intelligence10.1609/aaai.v38i9.28847(9865-9873)Online publication date: 20-Feb-2024
https://dl.acm.org/doi/10.1609/aaai.v38i9.28847
Li BWang FZhou YOh ANaumann TGloberson ASaenko KHardt MLevine S(2023)Fair allocation of indivisible choresProceedings of the 37th International Conference on Neural Information Processing Systems10.5555/3666122.3668490(54366-54385)Online publication date: 10-Dec-2023
https://dl.acm.org/doi/10.5555/3666122.3668490
Han QTao BXia L(2023)Average Envy-freeness for Indivisible ItemsProceedings of the 3rd ACM Conference on Equity and Access in Algorithms, Mechanisms, and Optimization10.1145/3617694.3623229(1-9)Online publication date: 30-Oct-2023
https://dl.acm.org/doi/10.1145/3617694.3623229
Show More Cited By

Index Terms

Fair allocation of indivisible goods: Beyond additive valuations
1. Applied computing
  1. Law, social and behavioral sciences
    1. Economics
2. Theory of computation
  1. Design and analysis of algorithms
    1. Approximation algorithms analysis

Index terms have been assigned to the content through auto-classification.

Recommendations

Fair Allocation of Indivisible Goods: Improvements and Generalizations
EC '18: Proceedings of the 2018 ACM Conference on Economics and Computation

We study the problem of fair allocation for indivisible goods. We use the maxmin share paradigm introduced by Budish~\citeBudish:first as a measure for fairness. \procacciafirst ~\citeProcaccia:first were the first to investigate this fundamental ...
On approximately fair allocations of indivisible goods
EC '04: Proceedings of the 5th ACM conference on Electronic commerce

We study the problem of fairly allocating a set of indivisible goods to a set of people from an algorithmic perspective. fair division has been a central topic in the economic literature and several concepts of fairness have been suggested. The ...
Improved maximin guarantees for subadditive and fractionally subadditive fair allocation problem
Abstract
In this work, we study the maximin share fairness notion (MMS) for allocation of indivisible goods in the subadditive and fractionally subadditive settings. While previous work refutes the possibility of obtaining an allocation which is better ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Artificial Intelligence

Artificial Intelligence Volume 303, Issue C

Feb 2022

299 pages

ISSN:0004-3702

Issue’s Table of Contents

Elsevier B.V.

Publisher

Elsevier Science Publishers Ltd.

United Kingdom

Publication History

Published: 01 February 2022

Author Tags

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

5
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 03 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Montanari LSchmidt-Kraepelin USuksompong WTeh NWooldridge MDy JNatarajan S(2024)Weighted envy-freeness for submodular valuationsProceedings of the Thirty-Eighth AAAI Conference on Artificial Intelligence and Thirty-Sixth Conference on Innovative Applications of Artificial Intelligence and Fourteenth Symposium on Educational Advances in Artificial Intelligence10.1609/aaai.v38i9.28847(9865-9873)Online publication date: 20-Feb-2024
https://dl.acm.org/doi/10.1609/aaai.v38i9.28847
Li BWang FZhou YOh ANaumann TGloberson ASaenko KHardt MLevine S(2023)Fair allocation of indivisible choresProceedings of the 37th International Conference on Neural Information Processing Systems10.5555/3666122.3668490(54366-54385)Online publication date: 10-Dec-2023
https://dl.acm.org/doi/10.5555/3666122.3668490
Han QTao BXia L(2023)Average Envy-freeness for Indivisible ItemsProceedings of the 3rd ACM Conference on Equity and Access in Algorithms, Mechanisms, and Optimization10.1145/3617694.3623229(1-9)Online publication date: 30-Oct-2023
https://dl.acm.org/doi/10.1145/3617694.3623229
Amanatidis GBirmpas GLazos PLeonardi SReiffenhäuser RLeyton-Brown KSamuelson LHartline J(2023)Round-Robin Beyond Additive Agents: Existence and Fairness of Approximate EquilibriaProceedings of the 24th ACM Conference on Economics and Computation10.1145/3580507.3597796(67-87)Online publication date: 9-Jul-2023
https://dl.acm.org/doi/10.1145/3580507.3597796
Feige UHuang XLeyton-Brown KSamuelson LHartline J(2023)On picking sequences for choresProceedings of the 24th ACM Conference on Economics and Computation10.1145/3580507.3597783(626-655)Online publication date: 9-Jul-2023
https://dl.acm.org/doi/10.1145/3580507.3597783

View Options

View options

Figures

Tables

Media

View Issue’s Table of Contents