Novel paradigm for the design of obviously strategyproof mechanisms

Taking care of the incentives of people with limited rationality is a challenging research direction that requires novel paradigms to design mechanisms. 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 and a characterization of set system instances for which optimal OSP mechanisms 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. We prove that OSP encompasses careful interleaving of ascending and descending auctions.