New Constructions of Obviously Strategyproof Mechanisms

Diodato Ferraioli (), Adrian Meier (), Paolo Penna () and Carmine Ventre ()
Additional contact information
Diodato Ferraioli: DIEM, Università degli Studi di Salerno, 84084 Fisciano, Italy
Adrian Meier: Department of Computer Science, ETH Zurich, 8092 Zurich, Switzerland
Paolo Penna: Department of Computer Science, ETH Zurich, 8092 Zurich, Switzerland
Carmine Ventre: Department of Informatics, King’s College London, London WC2B 4BG, United Kingdom

Mathematics of Operations Research, 2023, vol. 48, issue 1, 332-362

Abstract: 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.

Keywords: Primary: 91B03; secondary: 91B32; obviously strategyproof mechanisms; machine scheduling; set systems; deferred acceptance algorithms; extensive form mechanisms (search for similar items in EconPapers)
Date: 2023
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/moor.2022.1264 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ormoor:v:48:y:2023:i:1:p:332-362

Access Statistics for this article

More articles in Mathematics of Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().