Schedule

Abstracts, Slides, and Videos

Itai Ashlagi: "Market Design" [ slides 1 | slides 2 | video 1 | video 2 ]

Many issues arise in the design of economic institutions which often need special care in order to achieve desired goals. Entrepreneurs, managers as well as market makers are all involved in some way in the design of such institutions. Game theory and mechanism design have provided substantial insight into rules, behavior, and the achievability of various goals. However, only in the last decade or two has this knowledge reached the level at which game theorists can provide practical design advice. Market design has emerged as a field in economics, a field which also attracts computer scientists due to natural computational/informational issues that arise in many (complex) economic environments.

In this tutorial I will provide an overview on some market design literature focusing on matching topics such as matching residents (NRMP) and kidney exchange.

Avrim Blum: "On-Line Learning and Game Theory" [ slides | video 1 | video 2 ]

I will talk about some simple online learning algorithms and their connections to important concepts in game theory, as well as ways they can be used for online mechanism design. Topics include the Randomized Weighted Majority algorithm for regret minimization and connections to minimax optimality, internal regret minimization and connections to correlated equilibria, bandit algorithms, and the use of such algorithms for online auction and pricing problems. I will also discuss the use of advertising to guide myopic learning dynamics to higher quality equilibria.

Vincent Conitzer: "Computational Social Choice" [ slides | video 1 | video 2 ]

In many environments with multiple agents, the agents need to make collective decisions in spite of having different preferences over the alternatives. What are principled approaches for doing so? Can we aggregate their preferences to this end? These are questions asked in social choice theory, which is closely related to mechanism design. Much work in social choice concerns voting over the alternatives. Computational social choice considers questions such as: How computationally hard is it to execute a given voting rule? How many bits of communication are needed? Can we use computational hardness as a barrier against the manipulation of voting rules? What if the set of alternatives is exponential in size?

I will give a brief introduction to computational social choice in this tutorial. An introductory chapter with exercises can be found here.

Costis Daskalakis: "Computational Complexity in Games and Auctions" [ slides 1 | slides 2 | video 1 | video 2 ]

This tutorial will discuss computational problems in mechanism design (i.e. the design of games) and equilibria (i.e. the analysis of games).

In the first part of the tutorial, we will overview algorithmic results in the design of welfare- and revenue-maximizing auctions, identifying algorithmic challenges in this area. We will present recent progress on the computational complexity of reduced-forms, and use these results to extend Myerson's influential work on revenue-optimal, single-item auctions to multi-item settings.

The second part of the tutorial will discuss the computational complexity of the Nash equilibrium, and more broadly equilibrium concepts. We will show that Nash equilibrium is an intractable problem, casting doubt on whether it truly always capture the behavior of computationally bounded agents. We will then discuss ways to overcome the intractability barrier, including approximation, restricted families of games, and dynamics.

Jason Hartline: "Approximation in Mechanism Design" [ slides 1 | slides 2 | video 1 | video 2 | homework ]

In the first part, I will review classical auction theory. Topics covered include: Bayes-Nash equilibrium (BNE), characterization of BNE, revenue equivalence, solving for BNE, and revenue maximization (virtual values and marginal revenue). This theory provides a basis for all of auction theory.

In the second part, I will survey the role approximation plays in addressing several of the short-comings of the classical theory. First, when the optimal auction is complex, I will describe simple mechanisms that are approximately optimal. These results are especially important when agents' preferences are multi-dimensional. Second, when the optimal auction is highly dependent on distributional assumptions, I will describe mechanisms with little or no dependence on the distribution that are approximately optimal.

Students can find these topics discussed in course notes here.

Herve Moulin: "Fair Division" [ slides1 | slides 2 | video 1 | video 2 ]

Two central microeconomic models of fair division are reviewed from the point of view of mechanism design: can we find division rules selecting only efficient allocations, eliciting truthful report of individual characteristics (strategyproofness), and meeting certain tests of fairness going beyond basic horizontal equity (equal treatment of equals)?

For fair division of unproduced commodities we start from the Arrow Debreu model of pure consumption, and focus on the Unanimity Lower Bound, the No Envy property, Resource Monotonicity and Population Monotonicity. The two benchmark rules are the Egalitarian Equivalent allocation and the Competitive Equilibrium under Equal Incomes. We pay special attention to special subdomains of preferences: homogeneous, linear, Cobb Douglas and Leontief , where the normative properties of the benchmark rules do improve. We also discuss several variants of the basic model: non disposable single commodity; assignment with lotteries; monetary compensations and quasi-linear utilities. We uncover a handful of open directions of research for Algorithmic GT.

For cost and surplus sharing, we start by reviewing the axiomatic literature on the division of a single commodity according to individual claims or liabilities, then take into account counterfactual coalitional costs (or surplus) leading to fairness properties such as the Stand Alone tests and Coalitional Monotonicity, and to the two benchmark rules, Shapley value and the Dutta Ray egalitarian core selection. The special case of submodular costs allows a variety of fair strategyproof mechanisms with a modest efficiency loss, a tradeoff that the Algorithmic GT literature discusses in some detail.

Eva Tardos: "Auctions as Games: Equilibria and Efficiency" [ slides 1 | slides 2 | video 1 | video 2 ]

The design and analysis of Internet and web applications requires careful consideration of possible strategic behavior of the users of the system. The economic theory of mechanism design gives foundations for these sorts of design questions; however, the mechanisms it proposes tend to be complex and therefore impractical. To address this shortcoming, the simplicity of a mechanism should be held at least as important as the quality of outcomes it produces. Given the prevalence of very simple mechanisms in practice, it is fundamental to understand properties of these mechanisms and the environments in which they perform well. Over the last decade computer scientists and game theorists have developed good understanding of the impact of strategic user behavior on system performance in many environments including selfish traffic routing, service location, and bandwidth sharing. We will consider simple but not truthful auctions mechanisms from this perspective, studying the degradation of quality of solution caused by the selfish behavior of users using different solution concepts.

Rakesh Vohra: "Linear Programming and Mechanism Design" [ slides | video 1 | video 2 ]

The the theme of both sessions will be on the usefulness of linear programming methods in mechanism design. In the first session I will introduce the reduced form representation of auctions. This representation allows one to formulate some auction design problems as polymatroid optimization problems (with some additional constraints). In the second session I will describe the use of rounding methods to obtain mechanisms for allocating indivisible objects with many attractive features.

Leeat Yariv: "Diffusion and Strategic Interaction on Social Networks" [ slides 1 | slides 2 | video 1 | video 2 ]

Situations in which agents' choices depend on choices of those in close proximity, be it social or geographic, are ubiquitous. Selecting a new computer platform, signing a political petition, or even catching the flu are examples in which social interactions have a significant role. My goal for these lectures is to provide a pedestrian overview of some of the models and techniques used to study outcomes in environments in which interactions occur through potentially complex social networks. We will consider both static and dynamic models, as well as how the strategic interactions that take place impact the networks that form to begin with.

Special events

Tour of the Nationality Rooms

We will tour the Nationality Rooms at the University of Pittsburgh's Cathedral of Learning, a 10-15 minute walk from CMU.

Dinner at the Carnegie Museum of Natural History

This dinner will be held in the Hillman Hall of Minerals and Gems at the Carnegie Museum of Natural History. We will walk to the museum (roughly 10 minutes).

Dinner at Google Pittsburgh

This dinner is sponsored by Google, and will be held at the Google Pittsburgh office. We will arrive via charter bus.