Strengthening Ex-Post Incentive Compatibility: Is It Possible?

One of the fundamental questions of Algorithmic Mechanism Design is whether there exists an inherent clash between incentive compatibility and tractability: specifically, whether communication-efficient ex-post incentive compatible mechanisms for welfare maximization in combinatorial auctions are provably weaker in approximation ratio than non incentive compatible algorithms. To date, mostly ex-post incentive compatible mechanisms have been considered, i.e., mechanisms where being truthful is an ex-post Nash equilibrium. Despite ample effort, there are substantial gaps in our understanding of these mechanisms. We begin by asking what happens for dominant strategy mechanisms, i.e., mechanisms where truthfulness is a dominant strategy equilibrium rather than a Nash equilibrium. Intuitively, one might suspect that dominant strategy mechanisms are significantly weaker than ex-post mechanisms. However, prior research provides only mixed evidence to support this. We present several impossibility results for dominant-strategy mechanisms.

In the second part of the talk, we present impossibility results for obviously strategy-proof mechanisms. We remind that when designing dominant strategy mechanisms, we aim to free participants from strategic considerations. However, if the participants fail to comprehend that they should follow their dominant strategies, the mechanism loses its desirable qualities. Thus, it is also important to design mechanisms with dominant strategies that are self-explanatory. In his seminal work, Li [American Economic Review '17] introduced such mechanisms and named them obviously strategy-proof. We show that even for simple classes of valuations such as additive and unit-demand valuations, obviously strategy-proof mechanisms are powerless. This impossibility holds even if we allow infinite communication and computation.

Based on joint works with Shahar Dobzinski and Jan Vondrak.