Research Repository

Obvious strategyproofness needs monitoring for good approximations (extended abstract)

Ferraioli, D and Ventre, C (2017) Obvious strategyproofness needs monitoring for good approximations (extended abstract). In: ICTCS 2017 and CILC 2017 Italian Conference on Theoretical Computer Science and Italian Conference on Computational Logic, 2017-09-26 - 2017-09-28, Naples.

[img]
Preview
Text
osp_ictcs_cr.pdf - Accepted Version

Download (219kB) | 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 [10]. However, it has been shown to impose some limitations, e.g., no OSP mechanism can return a stable matching [3] . We here deepen the study of the limitations of OSP mechanisms by look-ing 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 signifificant cost. How-ever, rather surprisingly, we prove that OSP mechanisms can return opti-mal solutions when they use monitoring|a mechanism design paradigm that introduces a mild level of scrutiny on agents' declarations [9] .

Item Type: Conference or Workshop Item (Paper)
Additional Information: Published proceedings: CEUR Workshop Proceedings
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: Elements
Date Deposited: 20 Jul 2018 10:30
Last Modified: 20 Jul 2018 11:15
URI: http://repository.essex.ac.uk/id/eprint/21818

Actions (login required)

View Item View Item