Improved maximin guarantees for subadditive and fractionally subadditive fair allocation problem. (English) Zbl 1533.91257
Summary: 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 than \(1/2\)-MMS, the only positive result for the subadditive setting states that when the number of items is equal to \(m\), there always exists an \(\Omega (1 / \log m)\)-MMS allocation. Since the number of items may be larger than the number of agents \((n)\), such a bound can only imply a weak bound of \(\Omega (\frac{1}{n \log n})\)-MMS allocation in general.
In this work, we improve this bound exponentially to \(\Omega (\frac{1}{\log n \log \log n})\)-MMS guarantee. In addition to this, we prove that when the valuation functions are fractionally subadditive, a 0.2192235-MMS allocation is guaranteed to exist. This also improves upon the previous bound of 1/5-MMS guarantee for the fractionally subadditive setting.
In this work, we improve this bound exponentially to \(\Omega (\frac{1}{\log n \log \log n})\)-MMS guarantee. In addition to this, we prove that when the valuation functions are fractionally subadditive, a 0.2192235-MMS allocation is guaranteed to exist. This also improves upon the previous bound of 1/5-MMS guarantee for the fractionally subadditive setting.
MSC:
| 91B32 | Resource and cost allocation (including fair division, apportionment, etc.) |
References:
| [1] | Moulin, H., Fair Division and Collective Welfare (2004), MIT Press |
| [2] | Budish, E., The combinatorial assignment problem: approximate competitive equilibrium from equal incomes. J. Polit. Econ., 6, 1061-1103 (2011) |
| [3] | Budish, E.; Cantillon, E., The multi-unit assignment problem: theory and evidence from course allocation at Harvard. Am. Econ. Rev., 5, 2237-2271 (2012) |
| [4] | Budish, E.; Gao, R.; Othman, A.; Rubinstein, A.; Zhang, Q., Practical algorithms and experimentally validated incentives for equilibrium-based fair division (a-ceei), arXiv preprint |
| [5] | Ghiasi, A.; Seddighin, M., Approximate competitive equilibrium with generic budget, 236-250 · Zbl 1492.91144 |
| [6] | Brams, S. J.; Taylor, A. D., An envy-free cake division protocol. Am. Math. Mon., 9-18 (1995) · Zbl 0824.90142 |
| [7] | Brams, S. J.; Taylor, A. D., Fair Division: From Cake-Cutting to Dispute Resolution (1996), Cambridge University Press · Zbl 0991.91019 |
| [8] | Brams, S. J.; Taylor, A. D., Fair division and politics. PS Polit. Sci. Polit., 4, 697-703 (1995) |
| [9] | Dubins, L. E.; Spanier, E. H., How to cut a cake fairly. Am. Math. Mon., 1-17 (1961) · Zbl 0108.31601 |
| [10] | Bogomolnaia, A.; Moulin, H., Guarantees in fair division: general or monotone preferences. Math. Oper. Res., 1, 160-176 (2023) · Zbl 1534.91069 |
| [11] | Aziz, H.; Chan, H.; Li, B., Weighted maxmin fair share allocation of indivisible chores, 46-52 |
| [12] | Amanatidis, G.; Birmpas, G.; Markakis, E., On truthful mechanisms for maximin share allocations, 31-37 |
| [13] | Kurokawa, D.; Procaccia, A. D.; Wang, J., Fair enough: guaranteeing approximate maximin shares. J. ACM, 2, 8 (2018) · Zbl 1410.91314 |
| [14] | Lipton, R. J.; Markakis, E.; Mossel, E.; Saberi, A., On approximately fair allocations of indivisible goods, 125-131 |
| [15] | Kurokawa, D.; Procaccia, A. D.; Wang, J., When can the maximin share guarantee be guaranteed?, 523-529 |
| [16] | Chaudhury, B. R.; Garg, J.; Mehta, R., Fair and efficient allocations under subadditive valuations, 5269-5276 |
| [17] | Aziz, H.; Rauchecker, G.; Schryen, G.; Walsh, T., Algorithms for max-min share fair allocation of indivisible chores, 335-341 |
| [18] | Barman, S.; Sundaram, R. G., Uniform welfare guarantees under identical subadditive valuations, 46-52 |
| [19] | Bouveret, S.; Endriss, U.; Lang, J., Fair division under ordinal preferences: computing envy-free allocations of indivisible goods, 387-392 · Zbl 1211.68378 |
| [20] | Bouveret, S.; Lang, J., Efficiency and envy-freeness in fair division of indivisible goods: logical representation and complexity. J. Artif. Intell. Res., 525-564 (2008) · Zbl 1183.68570 |
| [21] | Seddighin, M.; Saleh, H.; Ghodsi, M., Maximin share guarantee for goods with positive externalities. Soc. Choice Welf., 2, 291-324 (2021) · Zbl 1475.91128 |
| [22] | Aziz, H.; Li, B.; Moulin, H.; Wu, X., Algorithmic fair allocation of indivisible items: a survey and new questions. ACM SIGecom Exch., 1, 24-40 (2022) |
| [23] | Amanatidis, G.; Aziz, H.; Birmpas, G.; Filos-Ratsikas, A.; Li, B.; Moulin, H.; Voudouris, A. A.; Wu, X., Fair division of indivisible goods: a survey, arXiv preprint · Zbl 07732234 |
| [24] | Ghodsi, M.; HajiAghayi, M.; Seddighin, M.; Seddighin, S.; Yami, H., Fair allocation of indivisible goods: improvements and generalizations, 539-556 |
| [25] | Garg, J.; Taki, S., An improved approximation algorithm for maximin shares, 379-380 |
| [26] | Barman, S.; Krishna Murthy, S. K., Approximation algorithms for maximin fair division, 647-664 |
| [27] | Li, Z.; Vetta, A., The fair division of hereditary set systems, 297-311 · Zbl 1443.91177 |
| [28] | Uziahu, G. B.; Feige, U., On fair allocation of indivisible goods to submodular agents, arXiv preprint |
| [29] | Barman, S.; Verma, P., Existence and computation of maximin fair allocations under matroid-rank valuations, 169-177 |
| [30] | Kulkarni, P.; Kulkarni, R.; Mehta, R., Maximin share allocations for assignment valuations, 2875-2876 |
| [31] | Cousins, C.; Viswanathan, V.; Zick, Y., Dividing good and better items among agents with submodular valuations, arXiv preprint |
| [32] | Feige, U., On maximizing welfare when utility functions are subadditive. SIAM J. Comput., 1, 122-142 (2009) · Zbl 1185.68855 |
| [33] | Vondrák, J., Optimal approximation for the submodular welfare problem in the value oracle model, 67-74 · Zbl 1231.91094 |
| [34] | Feige, U.; Vondrak, J., Approximation algorithms for allocation problems: improving the factor of 1-1/e, 667-676 |
| [35] | Barman, S.; Bhaskar, U.; Krishna, A.; Sundaram, R. G., Tight approximation algorithms for p-mean welfare under subadditive valuations · Zbl 07651150 |
| [36] | Chaudhury, B. R.; Garg, J.; Mehta, R., Fair and efficient allocations under subadditive valuations, 5269-5276 |
| [37] | Li, W.; Vondrák, J., A constant-factor approximation algorithm for Nash social welfare with submodular valuations, 25-36 |
| [38] | Garg, J.; Husić, E.; Végh, L. A., Approximating Nash social welfare under Rado valuations, 1412-1425 · Zbl 07765258 |
| [39] | Barman, S.; Verma, P., Approximating Nash social welfare under binary xos and binary subadditive valuations, 373-390 · Zbl 1533.91189 |
| [40] | Dobzinski, S.; Nisan, N.; Schapira, M., Approximation algorithms for combinatorial auctions with complement-free bidders. Math. Oper. Res., 1, 1-13 (2010) · Zbl 1216.68338 |
| [41] | Bhawalkar, K.; Roughgarden, T., Welfare guarantees for combinatorial auctions with item bidding, 700-709 · Zbl 1377.91102 |
| [42] | Dütting, P.; Kesselheim, T.; Lucier, B., An o (log log m) prophet inequality for subadditive combinatorial auctions. ACM SIGecom Exch., 2, 32-37 (2020) |
| [43] | Assadi, S.; Kesselheim, T.; Singla, S., Improved truthful mechanisms for subadditive combinatorial auctions: breaking the logarithmic barrier, 653-661 · Zbl 07788378 |
| [44] | Plaut, B.; Roughgarden, T., Almost envy-freeness with general valuations. SIAM J. Discrete Math., 2, 1039-1068 (2020) · Zbl 1437.91237 |
| [45] | Dror, A.; Feldman, M.; Segal-Halevi, E., On fair division under heterogeneous matroid constraints. J. Artif. Intell. Res., 567-611 (2023) · Zbl 07732091 |
| [46] | Amanatidis, G.; Markakis, E.; Nikzad, A.; Saberi, A., Approximation algorithms for computing maximin share allocations. ACM Trans. Algorithms, 4, 52 (2017) · Zbl 1407.68540 |
| [47] | Schechtman, G., Concentration, results and applications, 1603-1634 · Zbl 1057.46011 |
| [48] | Feige, U.; Mirrokni, V. S.; Vondrak, J., Maximizing non-monotone submodular functions, 461-471 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
