EconCS Seminar

 

Lecturer: 

Shiri Ron (Weizmann)

Title: 

On the Computational Complexity of Mechanism Design in "Single-Parameter" Settings

Abstract: 

In this talk, we explore the performance of polynomial-time incentive-compatible mechanisms in single-crossing domains. 

Single-crossing domains were extensively studied in the economics literature and are the standard mathematical formulation of domains that are informally known as "single parameter''. Roughly speaking, a domain is single crossing if monotonicity characterizes incentive compatibility. In particular, the definition of single-crossing captures all previous definitions of single-parameter domains. 

In all single-crossing domains studied, the performance of polynomial-time incentive-compatible mechanisms matches the performance of polynomial-time non-incentive-compatible algorithms.  We provide the first proof of a gap in the power of polynomial-time incentive-compatible mechanisms and polynomial-time non-incentive-compatible algorithms in any single-crossing domain.  However,  the objective function used is not natural. 

We show that, to some extent, this is unavoidable by providing a sweeping positive result for the most natural objective function in multi-unit auctions, that of welfare maximization. We present an incentive-compatible FPTAS mechanism for every multi-unit auction with single-crossing domains. Thus, incentive-compatible and non-incentive-compatible algorithms have the same approximation power for this setting.

Based on joint work with Moshe Babaioff and Shahar Dobzinski.

Location: 

Room 130, Feldman Building, Edmond J. Safra Campus.

 

Click here to add the EconCS Seminar to your Google Calendar