An Experimental Study of Fast Greedy Algorithms for Fair Allocation Problems

  • Trung Thanh Nguyen Phenikaa university
  • Le Dang Nguyen
Keywords: Fair allocation, exact algorithm, greedy algorithm, mixed-integer linear program, NP-hard

Abstract

This paper is concerned with two salient allocation
problems in fair division of indivisible goods, aiming at
maximizing egalitarian and Nash product social welfare.
These problems are computationally NP-hard, meaning that
achieving polynomial time algorithms is impossible, unless
P = NP. Approximation algorithms, which return near-optimal
solution with a theoretical guarantee, have been widely used
for tackling the problems. However, most of them are often of
high computational complexity or not easy to implement. It is
therefore of great interest to explore fast greedy methods that
can quickly produce a good solution. This paper presents an
empirical study of the performance of several such methods.
Interestingly, the obtained results show that fair allocation
problems can be practically approximated by greedy algorithms.
Keywords: Fair allocation, exact algorithm, greedy algorithm,
mixed-integer linear program, NP-hard.
I. INTRODUCTION
In this paper, we study the fair allocation problem, which
has shown its growing interest during last decades, with a
wide range of real-world applications [1]. In short, this is a
combinatorial optimization problem which asks to allocate
???? discrete items amongst a set of ???? agents (or players)
so as to meet a certain notion of fairness. It is assumed
that every item is “indivisible” and “non-sharable”, that
is, i) it cannot be broken in pieces before allocating to
agents, and ii) it cannot be shared by two or more agents.
For example, laptops and cell-phones are indivisible items
which agents might not want to share with others. An
allocation of items to agents is simply a partition of the
whole set of items into ???? disjoint subsets. There are up to
???????? such partitions, making the solution space large enough
so that an exhaustive search for an optimal solution is
impossible.
It now remains to define what a fair allocation is, a
concept that is of independent interest in the field of
Economic and Social Choice Theory [2, 3]. In general, there
are many different ways of defining fairness, depending on
particular applications. The most common way is to either
use a so-called Collective Utility Function (CUF), which is
a function for aggregating individual agents’ utilities in a
fair manner, or to follow an orthogonal method relying on
determining the fair share of agents. Since we are focusing
on the first method in this paper, we refer the reader to
the paper [4] and the references therein for more details of
the second method. Suppose that every agent evaluates the
value of items through a utility function, which maps each
subset of items to a numerical value representing the utility
of the agent for the subset. Then, one can define a maxmin fair allocation to be the one that maximizes the

References

Y. Chevaleyre, P. E. Dunne, U. Endriss, J. Lang, M. Lemaˆıtre, N. Maudet, J. A. Padget, S. Phelps, J. A. R.-Aguilar, and P. Sousa, “Issues in multiagent resource allocation,” Informatica (Slovenia), vol. 30, no. 1, pp. 3–31,

M. Fleurbaey and F. Maniquet, A Theory of Fairness and Social Welfare. Cambridge University Press, 2011.

H. Moulin, Handbook of Computational Social Choice, F. Brandt, V. Conitzer, U. Endriss, J. Lang, and A. D. Procaccia, Eds. Cambridge University Press, 2016.

S. Bouveret and M. Lemaˆıtre, “Characterizing conflicts in fair division of indivisible goods using a scale of criteria,” Auton. Agents Multi Agent Syst., vol. 30, no. 2, pp. 259–290, 2016.

J. Rawls, A Theory of Justice. London: Oxford University Press, 1971.

M. Kaneko and K. Nakamura, “The nash social welfare function,” Econometrica, vol. 47, no. 2, pp. 423–435, 1979.

H. Moulin, Axioms of cooperative decision making. Cambridge: Cambridge University Press, 1988.

N. Nguyen, T. T. Nguyen, M. Roos, and J. Rothe, “Computational complexity and approximability of social welfare optimization in multiagent resource allocation,” Auton. Agents Multi Agent Syst., vol. 28, no. 2, pp. 256–289, 2014.

M. Garey and D. Johnson, Computers and intractability: A guide to the theory of NP-completeness. New York: W. H. Freeman and Company, 1979.

I. Bezakov ´ a and V. Dani, “Allocating indivisible goods,” ´ SIGecom Exch., vol. 5, no. 3, pp. 11–18, 2005.

A. Asadpour and A. Saberi, “An approximation algorithm for max-min fair allocation of indivisible goods,” SIAM J. Comput., vol. 39, no. 7, pp. 2970–2989, 2010.

M. Bateni, M. Charikar, and V. Guruswami, “Maxmin allocation via degree lower-bounded arborescences,” in Proceedings of the 41st Annual ACM Symposium on Theory of Computing, STOC 2009, Bethesda, MD, USA, May 31 - June 2, 2009, M. Mitzenmacher, Ed. ACM, 2009, pp. 543–552.

D. Chakrabarty, J. Chuzhoy, and S. Khanna, “On allocating goods to maximize fairness,” in 50th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2009, October 25-27, 2009, Atlanta, Georgia, USA. IEEE Computer Society, 2009, pp. 107–116.

T. T. Nguyen and J. Rothe, “Minimizing envy and maximizing average nash social welfare in the allocation of indivisible goods,” Discret. Appl. Math., vol. 179, pp. 54–68, 2014.

N. Anari, S. O. Gharan, A. Saberi, and M. Singh, “Nash social welfare, matrix permanent, and stable polynomials,” in 8th Innovations in Theoretical Computer Science Conference, ITCS 2017, January 9-11, 2017, Berkeley, CA, USA, ser. LIPIcs, C. H. Papadimitriou, Ed., vol. 67. Schloss Dagstuhl - Leibniz-Zentrum fur Informatik, 2017, pp. 36:1– ¨ 36:12.

R. Cole, N. R. Devanur, V. Gkatzelis, K. Jain, T. Mai, V. V. Vazirani, and S. Yazdanbod, “Convex program duality, fisher markets, and nash social welfare,” in Proceedings of the 2017 ACM Conference on Economics and Computation, EC ’17, Cambridge, MA, USA, June 26-30, 2017, C. Daskalakis, M. Babaioff, and H. Moulin, Eds. ACM, 2017, pp. 459– 460.

S. Barman, S. K. Krishnamurthy, and R. Vaish, “Finding fair and efficient allocations,” in Proceedings of the 2018 ACM Conference on Economics and Computation, Ithaca, NY, USA, June 18-22, 2018, E. Tardos, E. Elkind, and R. Vohra, ´ Eds. ACM, 2018, pp. 557–574.

R. Cole and V. Gkatzelis, “Approximating the nash social welfare with indivisible items,” in Proceedings of the FortySeventh Annual ACM on Symposium on Theory of Computing, STOC 2015, Portland, OR, USA, June 14-17, 2015, R. A. Servedio and R. Rubinfeld, Eds. ACM, 2015, pp. 371–380.

E. Lee, “Apx-hardness of maximizing nash social welfare with indivisible items,” Inf. Process. Lett., vol. 122, pp. 17– 20, 2017.

G. J. Woeginger, “A polynomial-time approximation scheme for maximizing the minimum machine completion time,” Oper. Res. Lett., vol. 20, no. 4, pp. 149–154, 1997.

A. Darmann and J. Schauer, “Maximizing nash product social welfare in allocating indivisible goods,” Eur. J. Oper. Res., vol. 247, no. 2, pp. 548–559, 2015.

D. Baumeister, S. Bouveret, J. Lang, N. Nguyen, T. T. Nguyen, J. Rothe, and A. Saffidine, “Positional scoringbased allocation of indivisible goods,” Auton. Agents Multi Agent Syst., vol. 31, no. 3, pp. 628–655, 2017.

S. Barman, S. K. Krishnamurthy, and R. Vaish, “Greedy algorithms for maximizing nash social welfare,” in Proceedings of the 17th International Conference on Autonomous Agents and MultiAgent Systems, AAMAS 2018, Stockholm, Sweden, July 10-15, 2018. International Foundation for Autonomous Agents and Multiagent Systems Richland, SC, USA / ACM, 2018, pp. 7–13.

G. Amanatidis, G. Birmpas, A. Filos-Ratsikas, A. Hollender, and A. A. Voudouris, “Maximum nash welfare and other stories about EFX,” in Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence, IJCAI 2020, C. Bessiere, Ed. ijcai.org, 2020, pp. 24–30.

A. Ben-Tal and A. Nemirovski, “On polyhedral approximations of the second-order cone,” Math. Oper. Res., vol. 26, no. 2, pp. 193–205, 2001.

R. L. Graham, “Bounds on multiprocessing timing anomalies,” SIAM Journal of Applied Mathematics, vol. 17, no. 2, pp. 416–429, 1969.

B. Y. Wu, “An analysis of the LPT algorithm for the maxmin and the min-ratio partition problems,” Theor. Comput. Sci., vol. 349, no. 3, pp. 407–419, 2005.

J. Garg, P. Kulkarni, and R. Kulkarni, “Approximating nash social welfare under submodular valuations through (un)matchings,” in Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, SODA 2020, Salt Lake City, UT, USA, January 5-8, 2020, S. Chawla, Ed. SIAM, 2020, pp. 2673–2687.

E. A. Dinic and M. A. Kronrod, “An algorithm for the solution of the assignment problem,” Math. Dokl., vol. 10, no. 6, pp. 1324–1326, 1969.

Y. T. Lee and A. Sidford, “Efficient inverse maintenance and faster algorithms for linear programming,” in IEEE 56th Annual Symposium on Foundations of Computer Science, FOCS 2015, Berkeley, CA, USA, 17-20 October, 2015, V. Guruswami, Ed. IEEE Computer Society, 2015, pp. 230–249.

S. Bouveret and J. Lang, “A general elicitation-free protocol for allocating indivisible goods,” in IJCAI 2011, Proceedings of the 22nd International Joint Conference on Artificial Intelligence, Barcelona, Catalonia, Spain, July 16-22, 2011, T. Walsh, Ed. IJCAI/AAAI, 2011, pp. 73–78.

G. Amanatidis, E. Markakis, A. Nikzad, and A. Saberi, “Approximation algorithms for computing maximin share allocations,” in Automata, Languages, and Programming - 42nd International Colloquium, ICALP 2015, Kyoto, Japan, July

-10, 2015, Proceedings, Part I, ser. Lecture Notes in Computer Science, M. M. Halldorsson, K. Iwama, N. Kobayashi, ´ and B. Speckmann, Eds., vol. 9134. Springer, 2015, pp. 39–51.

I. Caragiannis, D. Kurokawa, H. Moulin, A. D. Procaccia, N. Shah, and J. Wang, “The unreasonable fairness of maximum nash welfare,” in Proceedings of the 2016 ACM Conference on Economics and Computation, EC ’16, Maastricht, The Netherlands, July 24-28, 2016, V. Conitzer, D. Bergemann, and Y. Chen, Eds. ACM, 2016, pp. 305– 322.

H. Aziz, G. Rauchecker, G. Schryen, and T. Walsh, “Algorithms for max-min share fair allocation of indivisible

chores,” in Proceedings of the Thirty-First AAAI Conference on Artificial Intelligence, February 4-9, 2017, San Francisco, California, USA, S. P. Singh and S. Markovitch, Eds. AAAI Press, 2017, pp. 335–341.

Published
2022-09-30