Peeking Behind the Ordinal Curtain: Improving Distortion via Cardinal Queries

Authors

  • Georgios Amanatidis Sapienza University of Rome
  • Georgios Birmpas University of Oxford
  • Aris Filos-Ratsikas University of Liverpool
  • Alexandros Voudouris University of Oxford

DOI:

https://doi.org/10.1609/aaai.v34i02.5544

Abstract

The notion of distortion was introduced by Procaccia and Rosenschein (2006) to quantify the inefficiency of using only ordinal information when trying to maximize the social welfare. 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 outperform the best-known randomized ordinal mechanisms. We draw an almost complete picture of the number of queries required to achieve specific distortion bounds.

Downloads

Published

2020-04-03

How to Cite

Amanatidis, G., Birmpas, G., Filos-Ratsikas, A., & Voudouris, A. (2020). Peeking Behind the Ordinal Curtain: Improving Distortion via Cardinal Queries. Proceedings of the AAAI Conference on Artificial Intelligence, 34(02), 1782-1789. https://doi.org/10.1609/aaai.v34i02.5544

Issue

Section

AAAI Technical Track: Game Theory and Economic Paradigms