Abstracts

Computational Aspects of Equilibria

Mihalis Yannakakis, PhD, Columbia University

Many models from a variety of areas involve the computation of an equilibrium or fixed point of some kind. Examples include Nash equilibria in games; price equilibria in markets; optimal strategies and the values of competitive games (stochastic and other games); stable configurations of neural networks; analysis of the evolution of various types of dynamic stochastic models. It is not known whether these problems can be solved in polynomial time. Despite their broad diversity, there are certain common computational principles that underlie different types of equilibria and connect many of these problems to each other. In this talk we will discuss some of these common principles and the corresponding complexity classes that capture them; the effect on the complexity of the underlying computational framework; and the relationship with other open questions in computation.

Optimal Dynamic Mechanism Design with Minimal Information Disclosure

Sham Kakade, PhD, University of Pennsylvania

Consider the problem of profit maximization (i.e. revenue-optimal dynamic mechanism design) in settings where an item is repeatedly sold over time. A central issue is how can the seller incentivize a buyer to reveal her (dynamically evolving) private information so as to maximize revenue.

We provide a simple optimal dynamic mechanism for rather general settings. The mechanism optimally balances exploration and exploitation, taking incentives into account. Furthermore, while the (abstract) optimal "direct" mechanism may collect arbitrarily complicated private statistics about the buyer, we provide a simple implementation which is both revenue optimal and has desirable privacy preserving properties. We also discuss applications to online ad auctions.

Joint work with: Ilan Lobel & Hamid Nazerzadeh

Portfolios from Sorts

Robert Almgren, PhD, New York University and Quantitative Brokers

Modern portfolio theory, initially developed by Markowitz in 1952 and much extended, gives us a rich and powerful framework for generating optimal investment portfolios. The classic theory requires that we supply precise numerical values for the expected returns of each asset, and a complete covariance matrix. In practice, managers do not have a complete set of expected return values, but they may have qualitative information or beliefs regarding the expected *relative* performance of various assets or subsets of the investment universe.

We present a method for portfolio optimization based on replacing expected returns with ordering information, that is, beliefs about the relative performance of different assets or sectors. We give a simple and economically rational definition of optimal portfolios that extends Markowitz' mean variance optimality condition in a natural way; in particular, our construction allows full use of covariance information. The formulation we develop is very general and is easily extended to a variety of cases, for example assets are divided into multiple sectors or there are multiple sorting criteria available.

Converting any Algorithm into an Incentive-compatible Mechanism

Robert Kleinberg, PhD, Cornell University

Does algorithm design become harder in the presence of incentive constraints? The theory of algorithmic mechanism design is largely founded on the presumption that the answer is affirmative, a presumption that has been rigorously confirmed under various interpretations of the question. This is unfortunate, since it would be very convenient if there existed generic procedures to convert any algorithm into an incentive-compatible mechanism with little or no computational overhead.

In this talk I will identify two broad settings in which such generic procedures exist. First, I will present a reduction that removes the computational overhead of computing payments in truthful mechanisms: it transforms any monotone allocation function into a randomized, truthful-in-expectation mechanism that evaluates the allocation function only once. Second, I will present a polynomial-time reduction transforming an arbitrary algorithm into a Bayesian incentive-compatible mechanism, given a suitable amount of information about the type distributions of agents.

The first result is joint work with Moshe Babaioff and Alex Slivkins; the second result is joint work with Jason Hartline and Azarakhsh Malekian.

Mechanism Design Double Feature

Hal Varian, PhD, University of California, Berkeley and Google

Ad Auctions Without Position Normalizers: How to design an incentive compatible sponsored search auction without using information about position clickthrough rates.

Approximate Implementation of Envy-Free Outcomes: Some thoughts about incentive-compatible mechanisms that provide approximate implementations of certain envy-free outcomes. Examples include second-degree price discrimination and competitive equilibria.