TY - JOUR
T1 - New Constructions of Obviously Strategyproof Mechanisms
AU - Ferraioli, Diodato
AU - Meier, Adrian
AU - Penna, Paolo
AU - Ventre, Carmine
N1 - Funding Information:
Funding: Diodato Ferraioli was partially supported by GNCS-INdAM, and by the Italian MIUR [PRIN 2017 Project ALGADIMAR] (Algorithms, Games, and Digital Markets). Carmine Ventre was parti-ally supported by the UKRI Trustworthy Autonomous Systems Hub [EP/V00784X/1].
Publisher Copyright:
Copyright: © 2022 INFORMS.
PY - 2023/2/28
Y1 - 2023/2/28
N2 - Catering to the incentives of people with limited rationality is a challenging research direction that requires novel paradigms to design mechanisms. 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. Here, we give the first set of tight results on the approximation guarantee of OSP mechanisms for scheduling related machines and a characterization of set system instances for which OSP mechanisms that return optimal solutions exist. 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, when private types belong to a set with few values. In essence, we prove that OSP encompasses careful interleaving of ascending and descending auctions.
AB - Catering to the incentives of people with limited rationality is a challenging research direction that requires novel paradigms to design mechanisms. 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. Here, we give the first set of tight results on the approximation guarantee of OSP mechanisms for scheduling related machines and a characterization of set system instances for which OSP mechanisms that return optimal solutions exist. 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, when private types belong to a set with few values. In essence, we prove that OSP encompasses careful interleaving of ascending and descending auctions.
UR - http://www.scopus.com/inward/record.url?scp=85152196518&partnerID=8YFLogxK
U2 - 10.1287/moor.2022.1264
DO - 10.1287/moor.2022.1264
M3 - Article
SN - 0364-765X
VL - 48
SP - 332
EP - 362
JO - MATHEMATICS OF OPERATIONS RESEARCH
JF - MATHEMATICS OF OPERATIONS RESEARCH
IS - 1
ER -