On the Power of Randomization for Obviously Strategy-Proof Mechanisms

We investigate the problem of designing randomized obviously strategyproof (OSP) mechanisms in several canonical auction settings. Obvious strategyproofness, introduced by Li [American Economic Review 2017], strengthens the well-known concept of dominant-strategy incentive compatibility (DSIC). Loosely speaking, it ensures that even agents who struggle with contingent reasoning can identify that their dominant strategy is optimal. Thus, one would hope to design OSP mechanisms with good approximation guarantees. Unfortunately, Ron [SODA 2024] has showed that deterministic OSP mechanisms fail to achieve an approximation better than the minimum of the number of items and the number of bidders, even for the simple settings of additive and unit-demand bidders. We circumvent these impossibilities by showing that randomized mechanisms that are obviously strategy-proof in the universal sense obtain a constant factor approximation for these classes. We show that this phenomenon occurs also for the setting of a multi-unit auction with single-minded bidders. Thus, our results provide a more positive outlook on the design of OSP mechanisms and exhibit a stark separation between the power of randomized and deterministic OSP mechanisms. To complement the picture, we provide lower bounds on the performance of randomized OSP mechanisms in each setting. This further demonstrates that OSP mechanisms are significantly weaker than dominant-strategy mechanisms: it is well known that the deterministic VCG mechanism outputs an optimal allocation in dominant-strategies, whereas we show that even randomized OSP mechanisms cannot obtain more than 87.5% of the optimal welfare.