Amanatidis, Georgios and Birmpas, Georgios and Filos-Ratsikas, Aris and Voudouris, Alexandros (2022) A Few Queries Go a Long Way: Information-Distortion Tradeoffs in Matching. Journal of Artificial Intelligence Research, 74. pp. 227-261. DOI https://doi.org/10.1613/jair.1.12690
Amanatidis, Georgios and Birmpas, Georgios and Filos-Ratsikas, Aris and Voudouris, Alexandros (2022) A Few Queries Go a Long Way: Information-Distortion Tradeoffs in Matching. Journal of Artificial Intelligence Research, 74. pp. 227-261. DOI https://doi.org/10.1613/jair.1.12690
Amanatidis, Georgios and Birmpas, Georgios and Filos-Ratsikas, Aris and Voudouris, Alexandros (2022) A Few Queries Go a Long Way: Information-Distortion Tradeoffs in Matching. Journal of Artificial Intelligence Research, 74. pp. 227-261. DOI https://doi.org/10.1613/jair.1.12690
Abstract
We consider the One-Sided Matching problem, where n agents have preferences over n items, and these preferences are induced by underlying cardinal valuation functions. The goal is to match every agent to a single item so as to maximize the social welfare. Most of the related literature, however, assumes that the values of the agents are not a priori known, and only access to the ordinal preferences of the agents over the items is provided. Consequently, this incomplete information leads to loss of efficiency, which is measured by the notion of distortion. In this paper, we further assume that the agents can answer a small number of queries, allowing us partial access to their values. We study the interplay between elicited cardinal information (measured by the number of queries per agent) and distortion for One-Sided Matching, as well as a wide range of well-studied related problems. Qualitatively, our results show that with a limited number of queries, it is possible to obtain significant improvements over the classic setting, where only access to ordinal information is given.
Item Type: | Article |
---|---|
Uncontrolled Keywords: | game theory, mathematical foundations, preferences |
Divisions: | Faculty of Science and Health Faculty of Science and Health > Computer Science and Electronic Engineering, School of Faculty of Science and Health > Mathematics, Statistics and Actuarial Science, School of |
SWORD Depositor: | Unnamed user with email elements@essex.ac.uk |
Depositing User: | Unnamed user with email elements@essex.ac.uk |
Date Deposited: | 31 May 2022 11:42 |
Last Modified: | 30 Oct 2024 19:32 |
URI: | http://repository.essex.ac.uk/id/eprint/32487 |
Available files
Filename: 12690-Article (PDF)-30593-1-10-20220516.pdf