Georgios Birmpas

When

Feb 23, 2021 16:00 Athens via Zoom

Title

Improving Distortion via Queries

Abstract

Aggregating the preferences of individuals into a collective decision is the core subject of study of social choice theory. In 2006, Procaccia and Rosenschein considered a utilitarian social choice setting, where the agents have explicit numerical values for the alternatives, yet they only report their linear orderings over them. To compare different aggregation mechanisms, Procaccia and Rosenschein introduced the notion of distortion, which quantifies the inefficiency of using only ordinal information when trying to maximize the social welfare, i.e., the sum of the underlying values of the agents for the chosen outcome. Since then, this research area has flourished and bounds on the distortion have been obtained for a wide variety of fundamental scenarios. However, the vast majority of the existing literature is focused on the case where nothing is known beyond the ordinal preferences of the agents. In this work, we take a more expressive approach, and consider mechanisms that are allowed to further ask a few cardinal queries in order to gain partial access to the underlying values of the agents. With this extra power, we design new deterministic mechanisms, for several problems, that achieve significantly improved distortion bounds and, in many cases, outperform the best-known randomized ordinal mechanisms. We paint an almost complete picture of the number of queries required to achieve specific distortion bounds.

About the Speaker

https://sites.google.com/site/gebirbas/ 

Georgios Birmpas got his first degree from the School of Applied Mathematics and Physics of National Technical University of Athens. After that, he completed his Master's degree on Logic and Theory of Algorithms at University of Athens, and he got his Ph.D. degree from the Department of Informatics of Athens University of Economics and Business. He then worked as a Research Associate at the department of Computer Science of the University of Oxford, and currently works as a Postdoctoral Researcher at the department of Computer, Control, and Management Engineering of Sapienza University of Rome. His research interests include Algorithmic Game Theory, Approximation Algorithms, Fair Division, and Computational Social Choice.