On the Power of Randomization for Obviously Strategy-Proof Mechanisms

We investigate the problem of designing randomized obviously strategy-proof (OSP) mechanisms in several canonical auction settings. Obvious strategy-proofness, introduced by Li [Li17], 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, deterministic OSP mechanisms fail to achieve an approximation better than minm, n where m is the number of items and n is the number of bidders, even for the simple settings of additive and unit-demand bidders [Ron24]. 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 impossibilities for randomized OSP mechanisms in each setting. While the deterministic VCG mechanism is well known to output an optimal allocation in dominant strategies, we show that even randomized OSP mechanisms cannot obtain more than 87.5% of the optimal welfare. This further demonstrates that OSP mechanisms are significantly weaker than dominant-strategy mechanisms. 1 We also provide a 400 approximation to the optimal welfare for multi-unit auctions with bidders whose valuations satisfy decreasing marginal utilities (Theorem 14). This is the only multi-parameter domain for which the power of deterministic mechanisms is not known. In Subsection 3.2.1, we describe a non-monotonicity effect that illustrates a barrier towards proving impossibilities for this class.