Abstract / Description of output
We study matching settings in which a set of agents have private utilities over a set of items. Each agent reports a partition of the items into approval sets of different threshold utility levels. Given this limited information on input, the goal is to compute an assignment of the items to the agents (subject to cardinality constraints depending on the application) that (approximately) maximizes the social welfare (the total utility of the agents for their assigned items). We first consider the well-known, simple one-sided matching problem in which each of a set of agents is to be assigned exactly one item. We show tight bounds on distortion of deterministic and randomized matching algorithms that are functions of the number of threshold utility levels. We further show that our distortion bounds extend to a more general setting in which there are multiple copies of the items, each agent can be assigned a number of items (even copies of the same one) up to a capacity, and the utility of an agent for an item depends on the number of its copies that the agent is given.
Original language | English |
---|---|
Title of host publication | Proceedings of the Thirty-Third International Joint Conference on Artificial Intelligence |
Editors | Kate Larson |
Publisher | IJCAI Organization |
Pages | 2851-2859 |
Number of pages | 9 |
ISBN (Electronic) | 9781956792041 |
DOIs | |
Publication status | Published - 9 Aug 2024 |
Event | The 33rd International Joint Conference on Artificial Intelligence - ICC Jeju, Jeju Island, Korea, Republic of Duration: 3 Aug 2024 → 9 Aug 2024 Conference number: 33 https://ijcai24.org/ |
Publication series
Name | Proceedings of the International Conferences on Artificial Intelligence |
---|---|
Publisher | IJCAI |
ISSN (Electronic) | 2521-7860 |
Conference
Conference | The 33rd International Joint Conference on Artificial Intelligence |
---|---|
Abbreviated title | IJCAI 2024 |
Country/Territory | Korea, Republic of |
City | Jeju Island |
Period | 3/08/24 → 9/08/24 |
Internet address |
Keywords / Materials (for Non-textual outputs)
- game theory
- economic paradigms
- GTEP
- computational social choice
- mechanism design