The distortion of threshold approval matching

Mohamad Latifian, Alexandros A. Voudouris

Research output: Chapter in Book/Report/Conference proceedingConference contribution

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 languageEnglish
Title of host publicationProceedings of the Thirty-Third International Joint Conference on Artificial Intelligence
EditorsKate Larson
PublisherIJCAI Organization
Pages2851-2859
Number of pages9
ISBN (Electronic)9781956792041
DOIs
Publication statusPublished - 9 Aug 2024
EventThe 33rd International Joint Conference on Artificial Intelligence - ICC Jeju, Jeju Island, Korea, Republic of
Duration: 3 Aug 20249 Aug 2024
Conference number: 33
https://ijcai24.org/

Publication series

NameProceedings of the International Conferences on Artificial Intelligence
PublisherIJCAI
ISSN (Electronic)2521-7860

Conference

ConferenceThe 33rd International Joint Conference on Artificial Intelligence
Abbreviated titleIJCAI 2024
Country/TerritoryKorea, Republic of
CityJeju Island
Period3/08/249/08/24
Internet address

Keywords / Materials (for Non-textual outputs)

  • game theory
  • economic paradigms
  • GTEP
  • computational social choice
  • mechanism design

Fingerprint

Dive into the research topics of 'The distortion of threshold approval matching'. Together they form a unique fingerprint.

Cite this