Theory Seminar, Wednesday Jan 15: Shiri Ron (Weizmann) - Revisiting Combinatorial Auctions: Navigating a Hierarchy of "Truthfulness" Notions

[Arnold Filtser]

Hi all,

Next week (Wed Jan 15, at 12) we will meet for our theory seminar.

Location: Building 503 room 226.

See you all there,

Arnold

https://theory.cs.biu.ac.il/

Speaker: Shiri Ron (Weizmann)
Title: Revisiting Combinatorial Auctions: Navigating a Hierarchy of "Truthfulness" Notions
Abstract: 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. Auctions provide an illustrative example of this scenario. 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 notion of robustness against strategic manipulation, namely towards ex-post incentive compatible mechanisms, which are mechanisms that can be implemented in a Nash equilibrium.
 
In this talk, we consider two additional notions of mechanisms that capture robustness against strategic manipulation. These notions are dominant-strategy mechanisms and obviously strategy-proof mechanisms (both will be explained during the talk). By that, we bring to the forefront a hierarchy of incentive compatibility notions, in addition to the already recognized hierarchy of valuation classes of Lehmann, Lehmann and Nisan [EC '01]. Therefore, all of our results will be with respect to a specific class of valuations and a specific notion of incentive compatibility.

First, we consider the class of dominant-strategy mechanisms, which are mechanisms that can be implemented in a dominant-strategy equilibrium. We show that classes of valuations previously considered "easy" are in fact not "easy" from the point of view of dominant-strategy mechanism design. Second, we examine the class of obviously strategy-proof mechanisms, introduced by Li [American Economic Review ‘17]. Roughly speaking, these mechanisms have dominant strategies that are “self-explanatory”. We show that even for bidders with simple valuations (e.g., additive or unit-demand), obviously strategy-proof mechanisms are provably powerless.

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

[Arnold Filtser]

This happens tomorrow!