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.

osp_ictcs_cr.pdf - Accepted Version

Download (219kB) | Preview


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
Faculty of Science and Health > Computer Science and Electronic Engineering, School of
SWORD Depositor: Elements
Depositing User: Elements
Date Deposited: 20 Jul 2018 10:30
Last Modified: 23 Sep 2022 19:20

Actions (login required)

View Item View Item