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.

We study the communication complexity of truthful combinatorial auctions, and in particular the case where valuations are either subadditive or single-minded, which we denote with SubAddUSingleM. We show that for three bidders with valuations in SubAddUSingleM, any deterministic truthful mechanism that achieves at least a 0.366-approximation requires$\exp(m)$communication. In contrast, a natural extension of [Fei09] yields a non-truthful$\text{poly}(m)-\mathbf{communication}$protocol that achieves a$\frac{1}{2}-\mathbf{approximation}$, demonstrating a gap between the power of truthful mechanisms and non-truthful protocols for this problem. Our approach follows the taxation complexity framework laid out in [Dob16b], but applies this framework in a setting not encompassed by the techniques used in past work. In particular, the only successful prior application of this framework uses a reduction to simultaneous protocols which only applies for two bidders [AKSW20], whereas our three-player lower bounds are stronger than what can possibly arise from a two-player construction (since a trivial truthful auction guarantees a$\frac{1}{2}- \mathbf{approximation}$for two players).

We explore the approximation power of deterministic obviously strategy-proof mechanisms in auctions, where the objective is welfare maximization. A trivial ascending auction on the grand bundle guarantees an approximation of min{m, n} for all valuation classes, where m is the number of items and n is the number of bidders. We focus on two classes of valuations considered “simple”: additive valuations and unit-demand valuations. For additive valuations, Bade and Gonczarowski [EC’17] have shown that exact welfare maximization is impossible. No impossibilities are known for unit-demand valuations.

We explore the performance of polynomial-time incentive-compatible mechanisms in single-crossing domains. Single-crossing domains were extensively studied in the economics literature. Roughly speaking, a domain is single crossing if monotonicity characterizes incentive compatibility (intuitively, an algorithm is monotone if a bidder that "improves" his valuation is allocated a better outcome). That is, single-crossing domains are the standard mathematical formulation of domains that are informally known as "single parameter". In all major single-crossing domains studied so far (e.g., welfare maximization in various auctions with single-minded bidders, makespan minimization on related machines), the performance of the best polynomial-time incentive-compatible mechanisms matches the performance of the best polynomial-time non-incentive-compatible algorithms. Our two main results make progress in understanding the power of incentive-compatible polynomial-time mechanisms in single-crossing domains:

We study the communication complexity of dominant strategy implementations of combinatorial auctions. We start with two domains that are generally considered “easy”: multi-unit auctions with decreasing marginal values and combinatorial auctions with gross substitutes valuations. For both domains we have fast algorithms that find the welfare-maximizing allocation with communication complexity that is poly-logarithmic in the input size. This immediately implies that welfare maximization can be achieved in ex-post equilibrium with no significant communication cost, by using VCG payments. In contrast, we show that in both domains the communication complexity of any dominant strategy implementation that achieves the optimal welfare is polynomial in the input size.

Let (f,P) be an incentive compatible mechanism where f is the social choice function and P is the payment function. In many important settings, f uniquely determines P (up to a constant) and therefore a common approach is to focus on the design of f and neglect the role of the payment function. Fadel and Segal [JET, 2009] question this approach by taking the lenses of communication complexity: can it be that the communication complexity of an incentive compatible mechanism that implements f (that is, computes both the output and the payments) is much larger than the communication complexity of computing the output? I.e., can it be that ccIC(f)>>cc(f)? Fadel and Segal show that for every f, ccIC(f)≤ exp(cc(f)). They also show that fully computing the incentive compatible mechanism is strictly harder than computing only the output: there exists a social choice function f such that ccIC(f)=cc(f)+1. In a follow-up work, Babaioff, Blumrosen, Naor, and Schapira [EC’08] provide a social choice function f such that ccIC(f)=Θ(n· cc(f)), where n is the number of players. The question of whether the exponential upper bound of Fadel and Segal is tight remained wide open. In this paper we solve this question by explicitly providing a function f such that ccIC(f)= exp(cc(f)). In fact, we establish this via two very different proofs. In contrast, we show that if the players are risk-neutral and we can compromise on a randomized truthful-in-expectation implementation (and not on deterministic ex-post implementation) gives that ccTIE(f)=poly(n,cc(f)) for every function f, as long as the domain of f is single parameter or a convex multi-parameter domain. We also provide efficient algorithms for deterministic computation of payments in several important domains.