Research Repository

Obvious strategyproofness needs monitoring for good approximations

Ferraioli, D and Ventre, C (2017) Obvious strategyproofness needs monitoring for good approximations. In: Proceedings of the Thirty-First AAAI Conference on Artificial Intelligence (AAAI-17), 2017-02-04 - 2017-02-10, San Francisco.

[img]
Preview
Text
osp-aaai17-2.pdf - Accepted Version

Download (258kB) | Preview

Abstract

Obvious strategyproofness (OSP) is an appealing concept as it allows to maintain incentive compatibility even in the presence of agents that are not fully rational, e.g., those who struggle with contingent reasoning (Li 2015). However, it has been shown to impose some limitations, e.g., no OSP mechanism can return a stable matching (Ashlagi and Gonczarowski 2015). We here deepen the study of the limitations of OSP mechanisms by looking at their approximation guarantees for basic optimization problems paradigmatic of the area, i.e., machine scheduling and facility location. We prove a number of bounds on the approximation guarantee of OSP mechanisms, which show that OSP can come at a significant cost. However, rather surprisingly, we prove that OSP mechanisms can return optimal solutions when they use monitoring?a novel mechanism design paradigm that introduces a mild level of scrutiny on agents? declarations (Kovács, Meyer, and Ventre 2015).

Item Type: Conference or Workshop Item (Paper)
Additional Information: Published proceedings: _not provided_
Uncontrolled Keywords: Obvious strategyproofness, machine scheduling, facility location
Subjects: Q Science > QA Mathematics > QA75 Electronic computers. Computer science
Divisions: Faculty of Science and Health > Computer Science and Electronic Engineering, School of
Depositing User: Jim Jamieson
Date Deposited: 13 Dec 2016 10:07
Last Modified: 17 Nov 2017 15:15
URI: http://repository.essex.ac.uk/id/eprint/18532

Actions (login required)

View Item View Item