2026-07-22T01:32:47Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:11167 2024-03-06T10:47:36Z ddc:004 open_access

Obviously Strategyproof Mechanisms for Machine Scheduling Ferraioli, Diodato Meier, Adrian Penna, Paolo Ventre, Carmine Bounded Rationality Extensive-form Mechanisms Approximate Mechanism Design 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 strategyproof (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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Diodato Ferraioli and Adrian Meier and Paolo Penna and Carmine Ventre 2019 Is Part Of LIPIcs, Volume 144, 27th Annual European Symposium on Algorithms (ESA 2019) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2019.46 urn:nbn:de:0030-drops-111677 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2019.46 eng https://creativecommons.org/licenses/by/3.0/legalcode