• Abstract. In most social choice settings, the participating agents are typically required to express their preferences over the different alternatives in the form of linear orderings. While this simplifies preference elicitation, it inevitably leads to high distortion when aiming to optimize a cardinal objective such as the social welfare, since the underlying values of the agents remain virtually unknown. We deviate from previous work by designing deterministic mechanisms that can learn the values of the agents for a small number of alternatives via queries, and use this extra information to make better-informed decisions. We focus on the general single-winner social choice setting, as well as a class of combinatorial problems that includes most well-known matching problems, such as one-sided matching, two-sided matching, general graph matching, and (constrained) resource allocation. We show bounds on the best-possible tradeoffs between the necessary cardinal information required to achieve particular distortion bounds. Qualitatively, our results show that it is indeed possible to significantly improve the distortion by making only a relatively small number of queries per agent.

Alexandros Voudouris (Essex)

16 March '22

• Bio. Alexandros Voudouris is a Lecturer in the School of Computer Science and Electronic Engineering, University of Essex. His research interests fall at the intersection of theoretical computer science, artificial intelligence and microeconomic theory, and include the design and analysis of approximation algorithms, algorithmic game theory, computational social choice and fair division. He received his PhD in 2018 from the University of Patras, and then worked as a postdoctoral researcher at the University of Oxford until March 2020.

Historical Notes and Further Readings

• The notion of the distortion was defined by Procaccia and Rosenschein about 15 years ago [1], to quantify the loss in an aggregate objective (typically the utilitrial social welfare) due to the fact that the designer of a system, an algorithm, or a mechanism does not have full information about the preferences of the participants. The first works on the distortion (see [1, 2, 3]) considered a general social choice setting in which a set of agents have numerical, cardinal utilities over a set of possible outcomes, or alternatives, but the mechanism only has access to the preference rankings (known as the ordinal preferences) induced by those utilities. The goal of this literature is to design mechanisms (deterministic or randomised) that minimise the distortion. Since then, a large and rich literature on the distortion has developed, which can be summarised in a recent survey in [4]. Recently, Amanatidis et al. [5] considered a setting in which the capabilities of mechanisms go beyond merely ordinal information, and they can access limited cardinal information via queries to the utilities of the agents. They put forward the agenda of studying the tradeoffs between the distortion and the number of cardinal queries and applied this approach to the general setting of social choice theory, as well as several combinatorial problems, primarily problems related to matching [6,7]. The talk will give an overview of these results, the associated techniques as well as the most interesting open problems in the area.

• Related Work

1. Ariel D. Procaccia and Jeffrey S. Rosenschein. The distortion of cardinal preferences in voting. International Workshop on Cooperative Information Agents. Springer, Berlin, Heidelberg, 2006.
2. Craig Boutilier, Ioannis Caragiannis, Simi Haber, Tyler Lu, Ariel D. Procaccia and Or Sheffet. Optimal social choice functions: A utilitarian view. Artificial Intelligence, 227, 190-213.
3. Ioannis Caragiannis, Swaprava Nath, Ariel D. Procaccia and Nisarg Shah. Subset selection via implicit utilitarian voting. Journal of Artificial Intelligence Research 58 (2017): 123-152.
4. Elliot Anshelevich, E., Aris Filos-Ratsikas, Nisarg Shah and Alexandros A. Voudouris. Distortion in Social Choice Problems: The First 15 Years and Beyond. In Proceedings of the 30th International Joint Conference on Artificial Intelligence (IJCAI), Survey Track, 2021.
5. Georgios Amanatidis, Georgios Birmpas, Aris Filos-Ratsikas and Alexandros A. Voudouris. Peeking behind the ordinal curtain: Improving distortion via cardinal queries. Artificial Intelligence, 296, 103488.
6. Georgios Amanatidis, Georgios Birmpas, Aris Filos-Ratsikas and Alexandros A. Voudouris. A few queries go a long way: information-distortion tradeoffs in matching. In Proceedings of the 35th AAAI Conference on Artificial Intelligence (AAAI). 2021.
7. Georgios Amanatidis, Georgios Birmpas, Aris Filos-Ratsikas and Alexandros A. Voudouris. Don't Roll the Dice, Ask Twice: The Two-Query Distortion of Matching Problems and Beyond. arXiv preprint arXiv:2203.01872 (2022)