Don’t Roll the Dice, Ask Twice: The Two-Query Distortion of Matching Problems and Beyond

Georgios Amanatidis, Georgios Birmpas, Aris Filos-Ratsikas, Alexandros A. Voudouris

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

Abstract

In most social choice settings, the participating agents express their preferences
over the different alternatives in the form of linear orderings. While this clearly
simplifies preference elicitation, it inevitably leads to poor performance with respect to optimizing a cardinal objective, such as the social welfare, since the values of the agents remain virtually unknown. This loss in performance because of lack of information is measured by the notion of distortion. A recent array of works put forward the agenda of designing mechanisms that learn the values of the agents for a small number of alternatives via queries, and use this limited extra information to make better-informed decisions, thus improving distortion. Following this agenda, in this work we focus on a class of combinatorial problems that includes most well-known matching problems and several of their generalizations, such as One-Sided Matching, Two-Sided Matching, General Graph Matching, and κ- Constrained Resource Allocation. We design two-query mechanisms that achieve the best-possible worst-case distortion in terms of social welfare, and outperform the best-possible expected distortion achieved by randomized ordinal mechanisms.
Original languageEnglish
Title of host publicationProceedings of NeurIPS 2022
Number of pages12
Publication statusAccepted/In press - 14 Sep 2022
EventThe 36th Conference on Neural Information Processing Systems, 2022 - New Orleans, United States
Duration: 28 Nov 20229 Dec 2022
Conference number: 36
https://neurips.cc/Conferences/2022

Conference

ConferenceThe 36th Conference on Neural Information Processing Systems, 2022
Abbreviated titleNeurIPS 2022
Country/TerritoryUnited States
CityNew Orleans
Period28/11/229/12/22
Internet address

Fingerprint

Dive into the research topics of 'Don’t Roll the Dice, Ask Twice: The Two-Query Distortion of Matching Problems and Beyond'. Together they form a unique fingerprint.

Cite this