אירועים והרצאות בפקולטה למדעי המחשב ע"ש הנרי ומרילין טאוב

In the basic setting of algorithmic mechanism design, the goal is to design an algorithm that solves an optimization problem whose input is distributed among rational agents. We assume that the output of the algorithm matters to the agents, so game theoretic considerations should be taken into account. An example that effectively illustrates this scenario is provided by auctions. We focus on auctions where the goal is to maximize the collective value for all participating parties, an objective formally known as the social welfare.

In this talk, we ask: Can we design auctions that satisfy three key desiderata – social welfare optimization, robustness to strategic manipulation (also termed “truthfulness” and incentive compatibility) and polynomial communication complexity? Despite ample effort, the answer to this question has remained elusive. We note that most of the attention has been directed towards one means of robustness against strategic manipulation, namely towards mechanisms that can be implemented in a Nash equilibrium, namely ex-post incentive compatible mechanisms.

We consider two additional properties of mechanisms that capture robustness against strategic manipulation. We start by considering the more restricted class of dominant-strategy mechanisms, which are mechanisms that can be implemented in a dominant-strategy equilibrium. We show several impossibilities for them.

We then examine the class of obviously strategy-proof mechanisms. This class was introduced by Li [American Economic Review ’17] and it describes mechanisms with dominant strategies that are also self-explanatory. We show that even for bidders with simple valuations such as additive and unit-demand valuations, obviously strategy-proof mechanisms are powerless.

The talk is based on joint works with Shahar Dobzinski, Dan Schoepflin and Jan Vondrák.