Multi resource allocation with partial preferences. (English) Zbl 07638296
Summary: We provide efficient, fair, and non-manipulable mechanisms for the multi-type resource allocation problems (MTRAs) and multiple assignment problems where agents have partial preferences over bundles consisting of multiple divisible items. We uncover a natural reduction from multiple assignment problems to MTRAs, which preserves the properties of MTRA mechanisms. We extend the well-known random priority (RP) and probabilistic serial (PS) mechanisms to MTRAs with partial preferences as multi-type PS (MPS) and multi-type RP (MRP) and propose a new mechanism, multi-type general dictatorship (MGD), which combines the ideas of MPS and MRP. We show that for the unrestricted domain of partial order preferences, unfortunately, no mechanism satisfies both sd-efficiency and sd-envy-freeness, even as they each satisfy different weaker notions of the desirable properties of efficiency, fairness, and non-manipulability we consider. Notwithstanding this impossibility result, our main message is positive: When agents’ preferences are represented by acyclic CP-nets, MRP satisfies ex-post-efficiency, sd-strategyproofness, and upper invariance, while MPS satisfies sd-efficiency, sd-envy-freeness, ordinal fairness, and upper invariance, recovering the properties of RP and PS; the MGD satisfies sd-efficiency, equal treatment of equals, and decomposability under the unrestricted domain of partial preferences. We introduce a natural domain of bundle net preferences, which generalizes previously studied domain restrictions of partial preferences for multiple assignment problems and is incomparable to the domain of acyclic CP-nets. We show that MRP and MPS satisfy all properties of the RP and PS under bundle net preferences as well.
MSC:
| 68Txx | Artificial intelligence |
Keywords:
computational social choice; multi resource allocation; partial preference; probabilistic serial; random prioritySoftware:
CP-netsReferences:
| [1] | Abdulkadiroğlu, A.; Sönmez, T., Random serial dictatorship and the core from random endowments in house allocation problems, Econometrica, 66, 689-702 (1998) · Zbl 1019.91016 |
| [2] | Abdulkadiroğlu, A.; Sönmez, T., House allocation with existing tenants, J. Econ. Theory, 88, 233-260 (1999) · Zbl 0939.91068 |
| [3] | Alcalde-Unzu, J.; Molis, E., Exchange of indivisible goods and indifferences: The Top Trading Absorbing Sets mechanisms, Games Econ. Behav., 73, 1-16 (2011) · Zbl 1236.91106 |
| [4] | Athanassoglou, S.; Sethuraman, J., House allocation with fractional endowments, Int. J. Game Theory, 40, 481-513 (2011) · Zbl 1274.91328 |
| [5] | Aziz, H.; De Keijzer, B., Housing markets with indifferences: a tale of two mechanisms, (Proceedings of the Twenty-Sixth AAAI Conference on Artificial Intelligence (2012)), 1249-1255 |
| [6] | Aziz, H.; Gaspers, S.; Mackenzie, S.; Walsh, T., Fair assignment of indivisible objects under ordinal preferences, Artif. Intell., 227, 71-92 (2015) · Zbl 1346.68106 |
| [7] | Aziz, H.; Kasajima, Y., Impossibilities for probabilistic assignment, Soc. Choice Welf., 49, 255-275 (2017) · Zbl 1392.91100 |
| [8] | Beviá, C., Fair allocation in a general model with indivisible goods, Rev. Econ. Des., 3, 195-213 (1998) |
| [9] | Bogomolnaia, A.; Moulin, H., A new solution to the random assignment problem, J. Econ. Theory, 100, 295-328 (2001) · Zbl 1134.91357 |
| [10] | Booth, R.; Chevaleyre, Y.; Lang, J.; Mengin, J.; Sombattheera, C., Learning conditionally lexicographic preference relations, (Proceeding of the 2010 Conference on 19th European Conference on Artificial Intelligence. Proceeding of the 2010 Conference on 19th European Conference on Artificial Intelligence, Amsterdam, the Netherlands (2010)), 269-274 · Zbl 1211.68223 |
| [11] | Boutilier, C.; Brafman, R.; Domshlak, C.; Hoos, H.; Poole, D., CP-nets: a tool for representing and reasoning with conditional ceteris paribus statements, J. Artif. Intell. Res., 21, 135-191 (2004) · Zbl 1080.68685 |
| [12] | Boutilier, C.; Brafman, R.; Domshlak, C.; Hoos, H.; Poole, D., Preference-based constrained optimization with CP-nets, Comput. Intell., 20, 137-157 (2004) |
| [13] | Bouveret, S.; Endriss, U.; Lang, J., Conditional importance networks: a graphical language for representing ordinal, monotonic preferences over sets of goods, (Proceedings of the 21st International Jont Conference on Artifical Intelligence. Proceedings of the 21st International Jont Conference on Artifical Intelligence, Pasadena, California, USA (2009)), 67-72 |
| [14] | Bouveret, S.; Endriss, U.; Lang, J., Fair division under ordinal preferences: computing envy-free allocations of indivisible goods, (Proceedings of the 19th European Conference on Artificial Intelligence (ECAI-2010) (2010)), 387-392 · Zbl 1211.68378 |
| [15] | Brams, S. J.; Jones, M. A.; Klamler, C., Better ways to cut a cake, Not. Am. Math. Soc., 53, 1314-1321 (2006) · Zbl 1142.91025 |
| [16] | Brams, S. J.; Taylor, A. D., Fair Division: From Cake-Cutting to Dispute Resolution (1996), Cambridge University Press · Zbl 0991.91019 |
| [17] | Budish, E., The combinatorial assignment problem: approximate competitive equilibrium from equal incomes, J. Polit. Econ., 119, 1061-1103 (2011) |
| [18] | Budish, E.; Che, Y. K.; Kojima, F.; Milgrom, P., Designing random allocation mechanisms: theory and applications, Am. Econ. Rev., 103, 585-623 (2013) |
| [19] | Chatterji, S.; Liu, P., Random assignments of bundles, J. Math. Econ., 87, 15-30 (2020) · Zbl 1433.91096 |
| [20] | Chevaleyre, Y.; Dunne, P. E.; Endriss, U.; Lang, J.; Lemaitre, M.; Maudet, N.; Padget, J.; Phelps, S.; Rodríguez-Aguilar, J. A.; Sousa, P., Issues in multiagent resource allocation, Informatica, 30, 3-31 (2006) · Zbl 1152.91455 |
| [21] | W.J. Cho, Probabilistic assignment: a two-fold axiomatic approach, 2012, Unpublished manuscript 3. |
| [22] | Cloutier, J.; Nyman, K. L.; Su, F. E., Two-player envy-free multi-cake division, Math. Soc. Sci., 59, 26-37 (2010) · Zbl 1200.91146 |
| [23] | Cohler, Y. J.; Lai, J. K.; Parkes, D. C.; Procaccia, A. D., Optimal envy-free cake cutting, (Twenty-Fifth AAAI Conference on Artificial Intelligence (2011)), 626-631 |
| [24] | Ehlers, L.; Klaus, B., Coalitional strategy-proof and resource-monotonic solutions for multiple assignment problems, Soc. Choice Welf., 21, 265-280 (2003) · Zbl 1073.91596 |
| [25] | Elster, J., Local Justice: How Institutions Allocate Scarce Goods and Necessary Burdens (1992), Russell Sage Foundation |
| [26] | Emanuel, E. J.; Persad, G.; Upshur, R.; Thome, B.; Parker, M.; Glickman, A.; Zhang, C.; Boyle, C.; Smith, M.; Phillips, J. P., Fair allocation of scarce medical resources in the time of covid-19, N. Engl. J. Med., 382, 2049-2055 (2020) |
| [27] | Erel, S. H., Fair Division of Land (2017), The Senate of Bar Ilan University, Ph.D. thesis |
| [28] | Fujita, E.; Lesca, J.; Sonoda, A.; Todo, T.; Yokoo, M., A complexity approach for core-selecting exchange with multiple indivisible goods under lexicographic preferences, (Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence (2015)), 907-913 |
| [29] | Ghodsi, A.; Sekar, V.; Zaharia, M.; Stoica, I., Multi-resource fair queueing for packet processing, (Proceedings of the ACM SIGCOMM 2012 Conference on Applications, Technologies, Architectures, and Protocols for Computer Communication. Proceedings of the ACM SIGCOMM 2012 Conference on Applications, Technologies, Architectures, and Protocols for Computer Communication, Helsinki, Finland (2012)), 1-12 |
| [30] | Ghodsi, A.; Zaharia, M.; Hindman, B.; Konwinski, A.; Shenker, S.; Stoica, I., Dominant resource fairness: fair allocation of multiple resource types, (Proceedings of the 8th USENIX Conference on Networked Systems Design and Implementation. Proceedings of the 8th USENIX Conference on Networked Systems Design and Implementation, Boston, MA, USA (2011)), 323-336 |
| [31] | Grandl, R.; Ananthanarayanan, G.; Kandula, S.; Rao, S.; Akella, A., Multi-resource packing for cluster schedulers, Comput. Commun. Rev., 44, 455-466 (2015) |
| [32] | Guo, X.; Sikdar, S.; Wang, H.; Xia, L.; Cao, Y.; Wang, H., Probabilistic serial mechanism for multi-type resource allocation, Auton. Agents Multi-Agent Syst., 35, 15 (2021) |
| [33] | Hashimoto, T.; Hirata, D.; Kesten, O.; Kurino, M.; Ünver, M. U., Two axiomatic approaches to the probabilistic serial mechanism, Theor. Econ., 9, 253-277 (2014) · Zbl 1395.91264 |
| [34] | Hatfield, J. W., Strategy-proof, efficient, and nonbossy quota allocations, Soc. Choice Welf., 33, 505-515 (2009) · Zbl 1190.91078 |
| [35] | Heo, E. J., Probabilistic assignment problem with multi-unit demands: a generalization of the serial rule and its characterization, J. Math. Econ., 54, 40-47 (2014) · Zbl 1308.91095 |
| [36] | Heo, E. J.; Yılmaz, Ö., A characterization of the extended serial correspondence, J. Math. Econ., 59, 102-110 (2015) · Zbl 1320.91099 |
| [37] | Hosseini, H.; Igarashi, A.; Searns, A., Fair division of time: multi-layered cake cutting (2020), arXiv preprint |
| [38] | Hosseini, H.; Larson, K., Multiple assignment problems under lexicographic preferences, (Proceedings of the 18th International Conference on Autonomous Agents and Multiagent Systems (AAMAS-19) (2019)), 837-845 |
| [39] | Hosseini, H.; Menon, V.; Shah, N.; Sikdar, S., Necessarily optimal one-sided matchings, (Proceedings of the AAAI Conference on Artificial Intelligence (2021)), 5481-5488 |
| [40] | Hylland, A.; Zeckhauser, R., The efficient allocation of individuals to positions, J. Polit. Econ., 87, 293-314 (1979) |
| [41] | Jaramillo, P.; Manjunath, V., The difference indifference makes in strategy-proof allocation of objects, J. Econ. Theory, 147, 1913-1946 (2012) · Zbl 1247.91101 |
| [42] | Katta, A. K.; Sethuraman, J., A solution to the random assignment problem on the full preference domain, J. Econ. Theory, 131, 231-250 (2006) · Zbl 1142.90481 |
| [43] | Kesten, O.; Kurino, M.; Ünver, M. U., On characterizations of the probabilistic serial mechanism involving incentive and invariance properties, Math. Soc. Sci., 90, 56-62 (2017) · Zbl 1415.91180 |
| [44] | Kojima, F., Random assignment of multiple indivisible objects, Math. Soc. Sci., 57, 134-142 (2009) · Zbl 1155.91408 |
| [45] | Lang, J., Vote and aggregation in combinatorial domains with structured preferences, (Proceedings of the Twentieth International Joint Conference on Artificial Intelligence (IJCAI). Proceedings of the Twentieth International Joint Conference on Artificial Intelligence (IJCAI), Hyderabad, India (2007)), 1366-1371 |
| [46] | Lang, J.; Mengin, J.; Xia, L., Aggregating conditionally lexicographic preferences on multi-issue domains, (Proceedings of the 18th International Conference on Principles and Practice of Constraint Programming (2012)), 973-987 |
| [47] | Lang, J.; Xia, L., Voting in combinatorial domains, (Brandt, F.; Conitzer, V.; Endriss, U.; Lang, J.; Procaccia, A., Handbook of Computational Social Choice (2016), Cambridge University Press), 197-222, chapter 9 · Zbl 1452.91129 |
| [48] | Lebert, N.; Meunier, F.; Carbonneaux, Q., Envy-free two-player m-cake and three-player two-cake divisions, Oper. Res. Lett., 41, 607-610 (2013) · Zbl 1287.91101 |
| [49] | Mackin, E.; Xia, L., Allocating indivisible items in categorized domains, (Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence (2016)), 359-365 |
| [50] | Monte, D.; Tumennasan, N., Centralized allocation in multiple markets, J. Math. Econ., 61, 74-85 (2015) · Zbl 1368.91118 |
| [51] | Moulin, H., Cooperative Microeconomics: A Game-Theoretic Introduction (1995), Prentice Hall |
| [52] | Moulin, H., Fair division in the Internet Age, Annu. Rev. Econ., 11, 407-441 (2019) |
| [53] | Nguyen, T.; Peivandi, A.; Vohra, R., Assignment problems with complementarities, J. Econ. Theory, 165, 209-241 (2016) · Zbl 1371.91117 |
| [54] | Nyman, K.; Su, F. E.; Zerbib, S., Fair division with multiple pieces, Discrete Appl. Math., 283, 115-122 (2020) · Zbl 1437.91234 |
| [55] | Pápai, S., Strategyproof multiple assignment using quotas, Rev. Econ. Des., 5, 91-105 (2000) |
| [56] | Pápai, S., Strategyproof and nonbossy multiple assignments, J. Public Econ. Theory, 3, 257-271 (2001) |
| [57] | Procaccia, A. D., Cake cutting: not just child’s play, Commun. ACM, 56, 78-87 (2013) |
| [58] | Quint, T.; Wako, J., On houseswapping, the strict core, segmentation, and linear programming, Math. Oper. Res., 29, 861-877 (2004) · Zbl 1082.91021 |
| [59] | Rossi, F.; Venable, K. B.; Walsh, T., mCP nets: representing and reasoning with preferences of multiple agents, (Proceedings of AAAI-04 (2004)), 729-734 |
| [60] | Roth, A. E., Incentive compatibility in a market with indivisibilities, Econ. Lett., 9, 127-132 (1982) · Zbl 0722.90009 |
| [61] | Saban, D.; Sethuraman, J., A note on object allocation under lexicographic preferences, J. Math. Econ., 50, 283-289 (2014) · Zbl 1284.91288 |
| [62] | Sandomirskiy, F.; Segal-Halevi, E., Fair division with minimal sharing (2019), arXiv preprint · Zbl 1496.90088 |
| [63] | Shapley, L.; Scarf, H., On cores and indivisibility, J. Math. Econ., 1, 23-37 (1974) · Zbl 0281.90014 |
| [64] | Sikdar, S.; Adali, S.; Xia, L., Mechanism design for multi-type housing markets, (Proceedings of the 31st AAAI Conference on Artificial Intelligence (2017)), 684-690 |
| [65] | Sikdar, S.; Adali, S.; Xia, L., Mechanism design for multi-type housing markets with acceptable bundles, (Proceedings of the 33rd AAAI Conference on Artificial Intelligence (2019)), 2165-2172 |
| [66] | Sikdar, S.; Guo, X.; Wang, H.; Xia, L.; Cao, Y., Sequential mechanisms for multi-type resource allocation, (Proceedings of the 20th International Conference on Autonomous Agents and MultiAgent Systems, International Foundation for Autonomous Agents and Multiagent Systems. Proceedings of the 20th International Conference on Autonomous Agents and MultiAgent Systems, International Foundation for Autonomous Agents and Multiagent Systems, Richland, SC (2021)), 1209-1217 |
| [67] | Supady, A.; Curtis, J. R.; Abrams, D.; Lorusso, R.; Bein, T.; Boldt, J.; Brown, C. E.; Duerschmied, D.; Metaxa, V.; Brodie, D., Allocating scarce intensive care resources during the covid-19 pandemic: practical challenges to theoretical frameworks, Lancet, 2213-2600 (2021), Respiratory medicine |
| [68] | Svensson, L. G., Strategy-proof allocation of indivisible goods, Soc. Choice Welf., 16, 557-567 (1999) · Zbl 1066.91571 |
| [69] | Tadenuma, K., Trade-off between equity and efficiency in a general economy with indivisible goods, Soc. Choice Welf., 13, 445-450 (1996) · Zbl 0855.90013 |
| [70] | Wang, H.; Sikdar, S.; Guo, X.; Xia, L.; Cao, Y.; Wang, H., Multi-type resource allocation with partial preferences, (Proceedings of the 34th AAAI Conference on Artificial Intelligence (2020)), 2260-2267 |
| [71] | WHO Working Group on Ethics and COVID-19, Ethics and COVID-19: resource allocation and priority-setting (2020), 25 August |
| [72] | World Health Organization, WHO SAGE values framework for the allocation and prioritization of COVID-19 vaccination (2020), 14 September |
| [73] | Xia, L.; Conitzer, V., Strategy-proof voting rules over multi-issue domains with restricted preferences, (International Workshop on Internet and Network Economics (2010), Springer), 402-414 |
| [74] | Yılmaz, Ö., The probabilistic serial mechanism with private endowments, Games Econ. Behav., 69, 475-491 (2010) · Zbl 1230.91088 |
| [75] | Zhong, H.; Wang, Y.; Zhang, Z. L.; Liu, Y. X.; Le, K. J.; Cui, M.; Yu, Y. T.; Gu, Z. C.; Gao, Y.; Lin, H. W., Efficacy and safety of current therapeutic options for covid-19 - lessons to be learnt from sars and mers epidemic: a systematic review and meta-analysis, Pharmacol. Res., 157, Article 104872 pp. (2020) |
| [76] | Zhou, L., On a conjecture by Gale about one-sided matching problems, Econ. Theory, 52, 123-135 (1990) · Zbl 0725.90003 |
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.
