Resource Sharing through Multi-Round Matchings
Authors
- Yohai TrabelsiBar-Ilan University
- Abhijin AdigaBiocomplexity Institute and Initiative, Univ. of Virginia
- Sarit KrausBar-Ilan University
- S. S. RaviBiocomplexity Institute and Initiative, Univ. of VirginiaUniversity at Albany – SUNY
- Daniel J. RosenkrantzBiocomplexity Institute and Initiative, Univ. of VirginiaUniversity at Albany – SUNY
DOI:
https://doi.org/10.1609/aaai.v37i10.26380Keywords:
MAS: Other Foundations of Multiagent Systems, MAS: Coordination and CollaborationAbstract
Applications such as employees sharing office spaces over a workweekcan be modeled as problems where agents are matched to resourcesover multiple rounds. Agents' requirements limit the set of compatibleresources and the rounds in which they want to be matched. Viewing such anapplication as a multi-round matching problem on a bipartite compatibilitygraph between agents and resources, we show that a solution (i.e., a set of matchings, with one matching per round) can be foundefficiently if one exists. To cope with situations where a solution does not exist, we consider two extensions. Inthe first extension, a benefit function is defined for each agent and theobjective is to find a multi-round matching to maximize the total benefit. For ageneral class of benefit functions satisfying certain properties (includingdiminishing returns), we show that this multi-round matching problem isefficiently solvable. This class includes utilitarian and Rawlsian welfarefunctions. For another benefit function, we show that the maximizationproblem is NP-hard. In the second extension, the objective is to generate advice toeach agent (i.e., a subset of requirements to be relaxed) subject to abudget constraint so that the agent can be matched.We show that this budget-constrained advice generation problem is NP-hard.For this problem, we develop an integer linear programming formulation as wellas a heuristic based on local search. We experimentally evaluate our algorithms onsynthetic networks and apply them to two real-world situations: sharedoffice spaces and matching courses to classrooms.
Downloads
Published
2023-06-26
How to Cite
Trabelsi, Y., Adiga, A., Kraus, S., Ravi, S. S., & Rosenkrantz, D. J. (2023). Resource Sharing through Multi-Round Matchings.Proceedings of the AAAI Conference on Artificial Intelligence,37(10), 11681-11690. https://doi.org/10.1609/aaai.v37i10.26380
Issue
Section
AAAI Technical Track on Multiagent Systems
