Peeking Behind the Ordinal Curtain: Improving Distortion via Cardinal Queries

In this talk, I will present some recent results on the distortion of mechanisms for utilitarian social choice. The notion of distortion was introduced by Procaccia and Rosenschein (2006), to quantify the inefficiency of using only ordinal information when trying to maximise 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. In this work, we enhance the original framework of Procaccia and Rosenschein by considering mechanisms which are allowed to ask a few cardinal queries in order to gain partial access to the underlying values that the agents have for the alternatives. With this extra power, we design new deterministic mechanisms that achieve significantly improved distortion bounds, even compared to the best randomised ordinal mechanisms for the problem.

The talk will also serve as a brief introduction to the literature on the distortion in social choice and related settings.

Joint work with G. Amanatidis, G. Birmpas and A. A. Voudouris. To appear at AAAI '20