King's College London

Research portal

Obvious Strategyproofness, Bounded Rationality and Approximation

Research output: Contribution to journalConference paper

Diodato Ferraioli, Adrian Meier, Paolo Penna, Carmine Ventre

Original languageEnglish
Article number46
Pages (from-to)1-15
JournalLeibniz International Proceedings in Informatics, LIPIcs
Volume144
Early online date17 Sep 2019
DOIs
Accepted/In press1 Jul 2019
E-pub ahead of print17 Sep 2019
Published2019
Event27th Annual European Symposium on Algorithms - Munich/Garching, Germany
Duration: 9 Sep 201911 Sep 2019

Documents

King's Authors

Abstract

Catering to the incentives of people with limited rationality is a challenging research direction that requires novel paradigms to design mechanisms and approximation algorithms. Obviously strategy proof(OSP) mechanisms have recently emerged as the concept of interest to this research agenda. However,the majority of the literature in the area has either highlighted the shortcomings of OSP or focused on the“right” definition rather than on the construction of these mechanisms.We here give the first set of tight results on the approximation guarantee of OSP mechanisms for scheduling related machines. By extending the well-known cycle monotonicity technique, we are able to concentrate on the algorithmic component of OSP mechanisms and provide some novel paradigms for their design.

Download statistics

No data available

View graph of relations

© 2020 King's College London | Strand | London WC2R 2LS | England | United Kingdom | Tel +44 (0)20 7836 5454