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.