## Invited Speakers

Elias Koutsoupias, University of Oxford

Herve Moulin, University of Glasgow

Tim Roughgarden, Stanford University

**Multidimensional auctions: duality and virtual values **

We develop a general duality-theory framework for revenue maximization
in additive Bayesian auctions which generalises the virtual values of
Myerson. The framework extends linear programming duality and
complementarity to constraints with partial derivatives. The dual
system reveals the geometric nature of the problem and highlights its
connection with the theory of bipartite graph matchings. We give
optimal auctions for a large class of distributions for two items in
the monopoly setting, and we resolve the case of the uniform
distribution for up to six items. The duality framework is used not
only for proving optimality, but perhaps more importantly, for
deriving the optimal mechanism itself.

**One dimensional mechanism design **

We prove a general possibility result for collective decision problems where
individual allocations are one-dimensional, preferences are single-peaked
(strictly convex), and feasible allocation profiles cover a closed convex set.
Special cases include the celebrated median voter theorem and the division
of a non disposable commodity by the uniform rationing rule. We construct a
canonical peak-only rule equalizing in the leximin sense individual gains
from an arbitrary benchmark allocation: it is efficient, group-strategyproof,
fair, and (for most problems) continuous. These properties leave room for many
other rules, except for symmetric non disposable division problems.

**Complexity Theory and Algorithmic Game Theory: Some New Connections**

We survey three recent applications of complexity theory to
algorithmic game theory. First, we explain when and how communication
and computational lower bounds for algorithms for an optimization
problem translate to lower bounds on the price of anarchy (POA) in
games derived from the problem. This is a new approach to POA lower
bounds, based on reductions in lieu of explicit constructions. These
lower bounds are particularly significant for problems of designing
games that have only near-optimal equilibria ? ranging from the design
of simple combinatorial auctions to the existence of effective tolls for routing networks.

Second, we study "the borders of Border's theorem," a fundamental
result in auction design that gives an intuitive linear
characterization of the feasible interim allocation rules of a
Bayesian single-item environment. We explain a complexity-theoretic
barrier that indicates, assuming standard complexity class
separations, that Border's theorem cannot be extended significantly
beyond the state-of-the-art.

Finally, we explain "why prices need algorithms," in the sense that
the guaranteed existence of pricing equilibria (like Walrasian
equilibria) is inextricably connected to the computational complexity
of related optimization problems: demand oracles,
revenue-maximization, and welfare-maximization. This connection
implies a host of impossibility results, and suggests a
complexity-theoretic explanation for the lack of useful extensions of
the Walrasian equilibrium concept.

Includes joint work with Parikshit Gopalan, Noam Nisan, and Inbal Talgam-Cohen.