Research Repository

Peeking Behind the Ordinal Curtain: Improving Distortion via Cardinal Queries

Amanatidis, Georgios and Birmpas, Georgios and Filos-Ratsikas, Aris and Voudouris, Alexandros A (2021) 'Peeking Behind the Ordinal Curtain: Improving Distortion via Cardinal Queries.' Artificial Intelligence. ISSN 0004-3702

[img] Text
queries.artint.revision.pdf - Accepted Version
Restricted to Repository staff only until 25 February 2022.
Available under License Creative Commons Attribution Non-commercial No Derivatives.

Download (640kB) | Request a copy

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 over the alternatives. In this paper, 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 that the agents have for the alternatives. With this extra power, we design new deterministic mechanisms 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 by deterministic mechanisms to achieve specific distortion bounds.

Item Type: Article
Divisions: Faculty of Science and Health > Computer Science and Electronic Engineering, School of
Faculty of Science and Health > Mathematical Sciences, Department of
Depositing User: Elements
Date Deposited: 02 Mar 2021 14:31
Last Modified: 02 Mar 2021 15:15
URI: http://repository.essex.ac.uk/id/eprint/29956

Actions (login required)

View Item View Item