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

doi:10.7523/j.ucas.2025.031

摘要/Abstract

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

关键词: 公平性, 效率, 资源分配

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

中图分类号:

O221.7

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

YANG Wenguo, LIU Zhe, GAO Suixiang. Survey on fair and efficient allocations of indivisible resources[J]. Journal of University of Chinese Academy of Sciences, DOI: 10.7523/j.ucas.2025.031.

参考文献

[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.

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

Survey on fair and efficient allocations of indivisible resources

PDF (PC)

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

本文评价

访问统计

联系我们

[1]	王逸飞, 黄伟, 向俊彦, 贺晓赫, 梁旭文. 基于MPC的无人机辅助通信在线控制策略[J]. 中国科学院大学学报, 2025, 42(5): 655-665.
[2]	盛家华, 洪佩琳, 王航. 在网计算中资源受限的流汇聚算法[J]. 中国科学院大学学报, 2025, 42(2): 248-259.
[3]	王雪帆, 李宗旺, 梁旭文. 基于DQN的VDES异构星座兼容策略[J]. 中国科学院大学学报, 2024, 41(4): 550-557.
[4]	孙晨曦, 杜宏茹. 农村基础设施建设对农民增收的影响效率——以新疆南疆4地州为例[J]. 中国科学院大学学报, 2023, 40(4): 506-513.
[5]	靳婷婷, 段学军, 邹辉. 江苏省制造业能源效率与结构高级度耦合分析[J]. 中国科学院大学学报, 2023, 40(1): 59-68.
[6]	杨特, 洪佩琳, 李润洲. 蜂窝网络下的SWIPT-D2D通信资源分配[J]. 中国科学院大学学报, 2022, 39(6): 845-852.
[7]	张华明, 李强. 基于深度强化学习的低轨卫星下行功率分配方案[J]. 中国科学院大学学报, 2022, 39(4): 543-550.
[8]	王静, 陈岚, 张贺, 王海永. 基于EDA仿真软件的多资源调度算法[J]. 中国科学院大学学报, 2021, 38(5): 696-701.
[9]	王迪, 王明玉. 用于人工湿地的基质净水除磷静态实验与渗流模拟综合研究[J]. 中国科学院大学学报, 2021, 38(4): 478-485.
[10]	闫涛, 张晓平, 赵艳艳. 基于超效率SBM模型的中国城市生态效率时空演变及影响因素[J]. 中国科学院大学学报, 2021, 38(4): 486-493.
[11]	郭媛媛, 杨雪梅, 孙志华. 单指标分位回归模型估计的MM算法[J]. 中国科学院大学学报, 2021, 38(3): 289-296.
[12]	殷锋, 邱玲, 梁晓雯. 多用户毫米波大规模MIMO系统中收发端联合的混合波束成形设计[J]. 中国科学院大学学报, 2021, 38(2): 252-259.
[13]	张珍, 黄强, 胜献雷, 郑庆荣. 完全自旋极化电子器件TiCl₃/RhCl₃/TiCl₃的量子输运性质的第一性原理研究[J]. 中国科学院大学学报, 2020, 37(4): 458-464.
[14]	袁甲, 崔晨乙, 赵龙, 齐宝金, 魏进家. 铜基底特殊润湿性网膜的油水分离性能[J]. 中国科学院大学学报, 2020, 37(2): 177-185.
[15]	李维谦, 邱玲. 支持D2D多播的蜂窝网络分簇策略与资源分配[J]. 中国科学院大学学报, 2019, 36(1): 137-143.