不可分资源的公平和高效分配问题研究&#x0002A;

杨文国; 刘哲; 高随祥

doi:10.7523/j.ucas.2025.031

中国科学院大学学报 >

0 5 - 5

DOI: https://doi.org/10.7523/j.ucas.2025.031

不可分资源的公平和高效分配问题研究^*

杨文国 ,
刘哲 ,
高随祥

展开

中国科学院大学数学科学学院,北京 100190

收稿日期: 2025-02-19

修回日期: 2025-04-29

网络出版日期: 2025-05-26

基金资助

^*国家自然科学基金项目（12071459）资助

收起

Survey on fair and efficient allocations of indivisible resources

YANG Wenguo ,
LIU Zhe ,
GAO Suixiang

Expand

School of Mathematical Sciences, University of Chinese Academy of Sciences, Beijing 100049, China

Received date: 2025-02-19

Revised date: 2025-04-29

Online published: 2025-05-26

Fold

摘要

资源分配问题是一类基本的组合优化问题,在经济学、计算机科学等领域有着广泛应用;在这些场景中,诸如商品和任务等资源必须在各局中人之间进行分配。本文关注在寻找分配方案时资源不可分割性带来的挑战,分别考虑无嫉妒、成比例、公平的、最大最小收益、帕累托最优和它们的松弛形式等公平和效率准则,全面梳理了相关文献中满足各种公平标准的存在性结果、算法及其近似方法的最新进展,进而讨论了同时实现公平性和追求效率的算法。本文还研究了所列算法的计算复杂度和找到公平且高效的分配的可能性,总结了不可分资源分配问题算法设计技术和研究中的开放性问题。

关键词： 公平性; 效率; 资源分配

本文引用格式

杨文国 , 刘哲 , 高随祥 . 不可分资源的公平和高效分配问题研究^*[J]. 中国科学院大学学报, 0 : 5 -5 . DOI: 10.7523/j.ucas.2025.031

Abstract

Resource allocation problem is a basic class of combinatorial optimization problem and has found widespread application across various fields, such as economics and computer science where resources like goods and chores must be allocated among agents. In our survey, we focus on the challenges caused by indivisible resources. We consider fairness and efficiency criteria, including envy-freeness, proportionality, equitability, maximin share, Pareto optimality, and their relaxations. And we survey the recent progress of existential results, algorithms, and approximations that satisfy various fairness criteria in related literature. Additionally, we discuss algorithms that achieve both fairness and efficiency, such as envy free up to one item and Pareto optimality. We also study the computational complexity of these algorithms, and the likelihood of finding fair and efficient allocations. And we summarize the common algorithm design techniques, and open questions for future research.

Key words： fairness; efficiency; resource allocation

参考文献

[1] Steinhaus H. The problem of fair division[J/OL]. Econometrica, 1948, 16: 101-104. (1948-01) [2025-04-21]. https://www.jstor.org/stable/1914289.
[2] Steinhaus H.Sur la division pragmatique[J]. Econometrica, 1949, 17: 315-319. DOI: 10.2307/1907319.
[3] Foley D K. Resource allocation and the public sector[D/OL]. Yale University, 1966. (1966-05-20) [2025-04-21] https://www.proquest.com/dissertations-theses/resource-allocation-public-sector/docview/302230213/se-2
[4] Varian H R.Equity, envy, and efficiency[J]. Journal of Economic Theory, 1974, 9(1): 63-91. DOI: 10.1016/0022-0531(74)90075-1.
[5] Dubins L E, Spanier E H.How to cut a cake fairly[J]. The American Mathematical Monthly, 1961, 68(1): 1-17. DOI: 10.2307/2311357.
[6] Budish E.The combinatorial assignment problem: Approximate competitive equilibrium from equal incomes[J]. Journal of Political Economy, 2011, 119(6): 1061-1103. DOI: 10.1086/664613.
[7] Hylland A, Zeckhauser R.The efficient allocation of individuals to positions[J]. Journal of Political Economy, 1979, 87(2): 293-314. DOI: 10.1086/260757.
[8] Bogomolnaia A, Moulin H.A new solution to the random assignment problem[J]. Journal of Economic Theory, 2001, 100(2): 295-328. DOI: 10.1006/jeth.2000.2710.
[9] Garg J, Husić E, Végh L A.Approximating Nash social welfare under rado valuations[J]. ACM SIGecom Exchanges, 2021, 19(1): 45-51. DOI: 10.1145/3476436.3476444.
[10] Lipton R J, Markakis E, Mossel E, et al.On approximately fair allocations of indivisible goods[C]//Proceedings of the 5th ACM Conference on Electronic Commerce. New York, NY, USA. Association for Computing Machinery, 2004: 125-131. DOI: 10.1145/988772.988792.
[11] Caragiannis I, Kurokawa D, Moulin H, et al.The unreasonable fairness of maximum Nash welfare[J]. ACM Transactions on Economics and Computation, 2019, 7(3): 1-32. DOI: 10.1145/3355902.
[12] Gourvès L, Monnot J, Tlilane L.Near fairness in matroids[C]//Proceedings of the Twenty-First: European Conference on Artificial Intelligence. IOS Press, 2014: 393-398. DOI: 10.3233/978-1-61499-419-0-393.
[13] Aziz H, Huang X, Mattei N, et al.Computing welfare-maximizing fair allocations of indivisible goods[J]. European Journal of Operational Research, 2023, 307(2): 773-784. DOI: 10.1016/j.ejor.2022.10.013.
[14] Aziz H, Gaspers S, Mackenzie S, et al.Fair assignment of indivisible objects under ordinal preferences[J]. Artificial Intelligence, 2015, 227: 71-92. DOI: 10.1016/j.artint.2015.06.002.
[15] Hosseini H, Sikdar S, Vaish R, et al.Fair division through information withholding[J]. Proceedings of the AAAI Conference on Artificial Intelligence, 2020, 34(2): 2014-2021. DOI: 10.1609/aaai.v34i02.5573.
[16] Plaut B, Roughgarden T.Almost envy-freeness with general valuations[J]. SIAM Journal on Discrete Mathematics, 2020, 34(2): 1039-1068. DOI: 10.1137/19M124397X.
[17] Chaudhury B R, Garg J, Mehlhorn K.EFX exists for three agents[C]//Proceedings of the 21st ACM Conference on Economics and Computation. Virtual Event Hungary. Association for Computing Machinery, 2020: 1-19.DOI: 10.1145/3391403.3399511.
[18] Vishwa Prakash H V, Ghosal P, Nimbhorkar P, et al. EFX exists for three types of agents[EB/OL].2024. arXiv: 2410.13580.(2024-11-07) [2025-04-21] https://arxiv.org/abs/2410.13580.
[19] Chan H, Chen J, Li B, et al.Maximin-aware allocations of indivisible goods[C]//Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence. August 10-16, 2019. Macao, China. International Joint Conferences on Artificial Intelligence Organization, 2019: 137-143. DOI: 10.24963/ijcai.2019/20.
[20] Amanatidis G, Markakis E, Ntokos A.Multiple birds with one stone: Beating 1/2 for EFX and GMMS via envy cycle elimination[J]. Proceedings of the AAAI Conference on Artificial Intelligence, 2020, 34(2): 1790-1797. DOI: 10.1609/aaai.v34i02.5545.
[21] Caragiannis I, Gravin N, Huang X.Envy-freeness up to any item with high Nash welfare: the virtue of donating items[C]//Proceedings of the 2019 ACM Conference on Economics and Computation. Phoenix AZ USA. Association for Computing Machinery, 2019: 527-545. DOI: 10.1145/3328526.3329574.
[22] Chaudhury B R, Kavitha T, Mehlhorn K, et al.A little charity guarantees almost envy-freeness[M]. New York, NY, USA. Association for Computing Machinery, 2020: 2658-2672. DOI: 10.1137/1.9781611975994.162.
[23] Berger B, Cohen A, Feldman M, et al.Almost full EFX exists for four agents[J]. Proceedings of the AAAI Conference on Artificial Intelligence, 2022, 36(5): 4826-4833. DOI: 10.1609/aaai.v36i5.20410.
[24] Chaudhury B R, Garg J, Mehlhorn K, et al.Improving EFX guarantees through rainbow cycle number[C]//Proceedings of the 22nd ACM Conference on Economics and Computation. Budapest Hungary. Association for Computing Machinery, 2021: 310-311. DOI: 10.1145/3465456.3467605.
[25] Conitzer V, Freeman R, Shah N.Fair public decision making[C]//Proceedings of the 2017 ACM Conference on Economics and Computation. Cambridge Massachusetts USA. Association for Computing Machinery, 2017: 629-646. DOI: 10.1145/3033274.3085125.
[26] Aziz H, Caragiannis I, Igarashi A, et al.Fair allocation of indivisible goods and chores[J]. Autonomous Agents and Multi-Agent Systems, 2021, 36(1): 3. DOI: 10.1007/s10458-021-09532-8.
[27] Aziz H, Moulin H, Sandomirskiy F.A polynomial-time algorithm for computing a Pareto optimal and almost proportional allocation[J]. Operations Research Letters, 2020, 48(5): 573-578. DOI: 10.1016/j.orl.2020.07.005.
[28] Baklanov A, Garimidi P, Gkatzelis V, et al.Achieving proportionality up to the maximin item with indivisible goods[J]. Proceedings of the AAAI Conference on Artificial Intelligence, 2021, 35(6): 5143-5150. DOI: 10.1609/aaai.v35i6.16650.
[29] Baklanov A, Garimidi P, Gkatzelis V, et al.PROPm allocations of indivisible goods to multiple agents[C]//Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence. August 19-27, 2021. Montreal, Canada. International Joint Conferences on Artificial Intelligence Organization, 2021: 24-30. DOI: 10.24963/ijcai.2021/4.
[30] Barman S, Bhaskar U, Pandit Y, et al.Nearly equitable allocations beyond additivity and monotonicity[J]. Proceedings of the AAAI Conference on Artificial Intelligence, 2024, 38(9): 9494-9501. DOI: 10.1609/aaai.v38i9.28804.
[31] Bouveret S, Lemaître M.Characterizing conflicts in fair division of indivisible goods using a scale of criteria[J]. Autonomous Agents and Multi-Agent Systems, 2016, 30(2): 259-290. DOI: 10.1007/s10458-015-9287-3.
[32] Kurokawa D, Procaccia A D, Wang J.When can the maximin share guarantee be guaranteed? [C/OL]// Proceedings of the Thirtieth AAAI Conference on Artificial Intelligence. AAAI Press, 2016: 523-529. (2016-02-12) [2025-04-21] http://dl.acm.org/doi/10.5555/3015812.3015891.
[33] Kurokawa D, Procaccia A D, Wang J X.Fair enough: Guaranteeing approximate maximin shares[J]. Journal of the ACM, 2018, 65(2): 1-27. DOI: 10.1145/3140756.
[34] Akrami H, Garg J.Breaking the 3/4 barrier for approximate maximin share[M]. 2024: 74-91. DOI: 10.1137/1.9781611977912.4.
[35] Akrami H, Garg J, Sharma E, et al.Improving approximation guarantees for maximin share[C]//Proceedings of the 25th ACM Conference on Economics and Computation. New Haven, CT, USA: Association for Computing Machinery, 2024: 198-198. DOI: 10.1145/3670865.3673544.
[36] Barman S, Krishnamurthy S K.Approximation algorithms for maximin fair division[J]. ACM Transactions on Economics and Computation, 2020, 8(1): 1-28. DOI: 10.1145/3381525.
[37] Ghodsi M, Hajiaghayi M T, Seddighin M, et al.Fair allocation of indivisible goods: Improvement[J]. Mathematics of Operations Research, 2021, 46(3): 1038-1053. DOI: 10.1287/moor.2020.1096.
[38] Amanatidis G, Birmpas G, Markakis E. On truthful mechanisms for maximin share allocations[C/OL]// Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence. 2016: 31-37. (2016-07-09) [2025-04-21] http://dl.acm.org/doi/10.5555/3060621.3060626.
[39] Amanatidis G, Markakis E, Nikzad A, et al.Approximation algorithms for computing maximin share allocations[J]. ACM Transactions on Algorithms, 2017, 13(4). DOI: 10.1145/3147173.
[40] Garg J, Taki S.An improved approximation algorithm for maximin shares[J]. Artificial Intelligence, 2021, 300: 103547. DOI: 10.1016/j.artint.2021.103547.
[41] Feige U, Sapir A, Tauber L.A tight negative example for MMS fair allocations[C]//Web and Internet Economics. Cham: Springer International Publishing, 2022: 355-372. DOI: 10.1007/978-3-030-94676-0_20.
[42] Garg J, Hoefer M, Mehlhorn K.Satiation in Fisher markets and approximation of Nash social welfare[J]. Mathematics of Operations Research, 2024, 49(2): 1109-1139. DOI: 10.1287/moor.2019.0129.
[43] Barman S, Krishnamurthy S K, Vaish R.Finding fair and efficient allocations[C]//Proceedings of the 2018 ACM Conference on Economics and Computation. Ithaca, NY, USA. Association for Computing Machinery, 2018: 557-574. DOI: 10.1145/3219166.3219176.
[44] Garg J, Husić E, Li W Z, et al.Approximating Nash social welfare by matching and local search[C]//Proceedings of the 55th Annual ACM Symposium on Theory of Computing. Orlando, FL, USA: Association for Computing Machinery, 2023: 1298-1310. DOI: 10.1145/3564246.3585255.
[45] Garg J, Kulkarni P, Kulkarni R.Approximating Nash social welfare under submodular valuations through (un)matchings[J]. ACM Transactions on Algorithms, 2023, 19(4): 1-25. DOI: 10.1145/3613452.
[46] Bhaskar U, Sricharan A R, Vaish R. On Approximate Envy-Freeness for Indivisible Chores and Mixed Resources[C]//Approximation, Randomization,Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM2021): Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021, 207: 1:1-1:23. DOI: 10.4230/LIPIcs.APPROX/RANDOM.2021.1.
[47] Zhou S W, Wu X W.Approximately EFX allocations for indivisible chores[J]. Artificial Intelligence, 2024, 326: 104037. DOI: 10.1016/j.artint.2023.104037.
[48] Li B, Li Y K, Wu X W.Almost (weighted) proportional allocations for indivisible chores**[C]//Proceedings of the ACM Web Conference 2022. Virtual Event, Lyon, France. Association for Computing Machinery, 2022: 122-131. DOI: 10.1145/3485447.3512057.
[49] Aziz H, Rauchecker G, Schryen G, et al.Algorithms for max-min share fair allocation of indivisible chores[C/OL]//Proceedings of the Thirty-Firs AAAI Conference on Artificial Intelligence. AAAI Press, 2017: 335-341. (2017-02-04) [2025-04-21] http://dl.acm.org/doi/10.5555/3298239.3298291
[50] Huang X, Lu P Y.An algorithmic framework for approximating maximin share allocation of chores[C]//Proceedings of the 22nd ACM Conference on Economics and Computation. Budapest Hungary. ACM, 2021: 630-631. DOI: 10.1145/3465456.3467555.
[51] Huang X, Segal-Halevi E.A reduction from chores allocation to job scheduling[C]//Proceedings of the 24th ACM Conference on Economics and Computation. London, United Kingdom: Association for Computing Machinery, 2023: 908-908. DOI: 10.1145/3580507.3597676.
[52] Coffman E G Jr, Garey M R, Johnson D S. An application of Bin-packing to multiprocessor scheduling[J]. SIAM Journal on Computing, 1978, 7(1): 1-17. DOI: 10.1137/0207001.
[53] Cole R, Devanur N, Gkatzelis V, et al.Convex program duality, Fisher markets, and Nash social welfare[C]//Proceedings of the 2017 ACM Conference on Economics and Computation. Cambridge, Massachusetts, USA. Association for Computing Machinery, 2017: 459-460. DOI: 10.1145/3033274.3085109.
[54] Cole R, Gkatzelis V.Approximating the Nash social welfare with indivisible items[J]. SIAM Journal on Computing, 2018, 47(3): 1211-1236. DOI: 10.1137/15M1053682.
[55] Mas-Colell A, Whinston M D, Green J R.Microeconomic Theory[M]. Oxford University Press, 1995.
[56] Garg J, Murhekar A.Computing Pareto-optimal and almost envy-free allocations of indivisible goods[J]. Journal of Artificial Intelligence Research, 2024, 80: 1-25. DOI: 10.1613/jair.1.15414.
[57] Barman S, Krishnamurthy S K.On the proximity of markets with integral equilibria[C]//Proceedings of the Thirty-Third AAAI Conference on Artificial Intelligence and Thirty-First Innovative Applications of Artificial Intelligence Conference and Ninth AAAI Symposium on Educational Advances in Artificial Intelligence. AAAI Press, 2019, 33(1): 1748-1755. DOI: 10.1609/aaai.v33i01.33011748.
[58] Freeman R, Sikdar S, Vaish R, et al.Equitable allocations of indivisible goods[C/OL]//Proceedings of the 28th International Joint Conference on Artificial Intelligence. Macao, China. AAAI Press, 2019: 280-286. (2019-08-10) [2025-04-21] http://dl.acm.org/doi/10.5555/3367032.3367073.
[59] Amanatidis G, Birmpas G, Filos-Ratsikas A, et al.Maximum Nash welfare and other stories about EFX[J]. Theoretical Computer Science, 2021, 863: 69-85. DOI: 10.1016/j.tcs.2021.02.020.
[60] Brânzei S, Sandomirskiy F.Algorithms for competitive division of chores[J]. Mathematics of Operations Research, 2024, 49(1): 398-429. DOI: 10.1287/moor.2023.1361.
[61] Ebadian S, Peters D, Shah N. How to fairly allocate easy and difficult chores[C/OL]//Proceedings of the 21st International Conference on Autonomous Agents and Multiagent Systems. Virtual Event, New Zealand. International Foundation for Autonomous Agents and Multiagent Systems, 2022: 372-380. (2022-05-09) [2025-04-21] http://dl.acm.org/doi/10.5555/3535850.3535893.
[62] Garg J, Murhekar A, Qin J.New algorithms for the fair and efficient allocation of indivisible chores[C]// Proceedings of the Thirty-Second International Joint Conference on Artificial Intelligence. August 19-25, 2023. Macao, China. International Joint Conferences on Artificial Intelligence Organization, 2023: 2710-2718. DOI: 10.24963/ijcai.2023/302.
[63] Garg J, Murhekar A, Qin J.Weighted EF1 and PO allocations with few types of agents or chores[C]//Proceedings of the Thirty-Third International Joint Conference on Artificial Intelligence. August 3-9, 2024. Jeju, South Korea. International Joint Conferences on Artificial Intelligence Organization, 2024: 2799-2806. DOI: 10.24963/ijcai.2024/310.
[64] Freeman R, Sikdar S, Vaish R, et al. Equitable allocations of indivisible chores[C/OL]//Proceedings of the 19th International Conference on Autonomous Agents and MultiAgent Systems. Auckland, New Zealand. International Foundation for Autonomous Agents and Multiagent Systems, 2020: 384-392. (2020-05-13) [2025-04-21] http://dl.acm.org/doi/10.5555/3398761.3398810.

Options

文章导航

摘要

本文引用格式

Abstract

参考文献

访问统计

联系我们

模态框（Modal）标题

摘要

本文引用格式

Abstract

参考文献

访问统计

联系我们