EC'07 ACM Conference on Electronic Commerce

Tutorial Schedule

    Jump To:
  • 6
  • 7
Monday July 6, 2009
9:00AM - 12:30PM

Convergence of Nash Dynamics: Equilibria and Nearly-Optimal Solutions (download slides)


Vahab Mirrokni
Google Research, New York

Heiko Roeglin
Department of Quantitative Economics, Maastricht University

In recent years, a lot of effort has been devoted to analyzing response
dynamics in various games. Often static properties like the social
quality of Nash equilibria (e.g., price of anarchy) are studied, but
also questions about the dynamics themselves and their convergence
properties have attracted a great deal of attention. This includes
questions like "How long do uncoordinated agents need to reach a (pure)
Nash equilibrium?" and "Do uncoordinated agents quickly reach a state
with low social cost?". These dynamic properties are important as they
often have a crucial impact on the performance of uncoordinated
decentralized systems.

In this tutorial, we will present a comprehensive survey on the results
on convergence properties that have been obtained during the previous
years. The focus will be laid on Nash dynamics, in which players start
in an arbitrary state and consecutively improve their strategies. We
will first explain relations between the computational complexity of
local search and the convergence time of Nash dynamics, and then survey
results on the convergence to Nash and other types of equilibria. In the
second part, we consider convergence to approximately optimal solutions.
Here, we address the question of how long it takes uncoordinated agents
reach states with low social cost. Finally, we report results on other
natural dynamics studied in game theory, and compare those results with
convergence results for Nash Dynamics.

2:00PM - 5:30PM

A Computational Perspective on Game-Theoretic Solution Concepts (download slides)

Tutors: Costis Daskalakis and Kevin Leyton-Brown

This tutorial provides a broad introduction to the recent literature
on the computation of equilibria of simultaneous-move games, weaving
together both theoretical and applied viewpoints. It is aimed at
members of the EC community with an interest in understanding recent
results on the complexity of equilibrium computation and on
representation and reasoning methods for compactly represented games.
It will also be suitable for those with little experience with game
theory (as distinct, e.g., from auction theory). The tutorial will
focus on the computational problem of identifying a Nash equilibrium
in different game models. We will also more briefly consider
approximate equilibria, correlated equilibria, pure-strategy Nash
equilibria, and equilibria of two-player zero-sum games.

The tutorial is divided into two parts. The first will focus on
normal-form games. It will begin with a brief discussion of game
theoretic solution concepts and fundamental computational results. We
will then turn to the complexity of equilibrium computation,
explaining in detail the result that NASH (the problem of computing a
Nash equilibrium) is PPAD-complete. We will end this section by
considering the complexity of approximating NASH.

The second part considers compact game representations. We will begin
by explaining the importance and challenges of compact representation,
giving some foundational theoretical results. We will then describe a
variety of compact game representations (symmetric, anonymous,
congestion, graphical, and action-graph games), illustrating each with
motivating examples. Finally, we will survey algorithms for computing
the equilibria of compactly-represented games, and conclude by
identifying some open research challenges.

Tuesday July 7, 2009
9:00AM - 12:30PM

Information Exchange, Bidding Languages and Competition in Sponsored Search (download pub) (download tutorial)

Tutors: Jon Feldman and S. Muthukrishnan

Auction systems have been studied extensively in Economics. An
exciting new source of auctions arises in sponsored search, where
search engines display advertisements while responding to user
queries. They rely on market mechanisms to elicit prices for these
advertisements using real-time auctions, billions of which take place
each day. Sponsored search thus represents an opportunity to study
economics and game theory at a great scale. The game here involves
three sets of parties: the search engines, the users and the

Users in general are not gaming agents, rather they seek information,
products or services. In the process, users interact with both search
results as well as ads, and their behavior defines the value of the
"products" (the ad placements) being sold in the auction.

The interaction between the auctioneer and the advertisers has many
game-theoretic components and is the focus of this tutorial. The
auctioneer sets up the interaction with the advertisers by specifying
a structured auction framework and providing information, reports, and
valuable tools; the advertisers compile their goals into this
framework and use the information to formulate, execute and evaluate
their bidding strategies. A lot of research has focused on the
underlying auction at a fairly abstract level; eg., the study of the
Generalized Second Price (GSP) auction as a one-shot game.
Understanding the true detailed interaction between the search engines
and advertisers will reveal a rich set of new research problems in
auctioning, bidding, optimization and analysis. In this tutorial, we
use the Google ad system as the basis to expose details of this
interaction and our goal is to inspire the community on this research


2:00PM - 5:30PM

Mechanism Design in Dynamic Settings (Cavallo Slides) (Athey Slides)

Tutors: Susan Athey and Ruggiero Cavallo

The field of mechanism design addresses the challenges posed by agent
self-interest in social decision-making settings with private
information. So-called direct revelation mechanisms use monetary
transfer payments to incentivize agents to report private information
truthfully so that a decision can be determined that is optimal
according to some metric such as social welfare. Traditionally, the
established context has been a static setting where a decision is
either singular ("one-shot") or else not related to future decisions
in important ways. But this is severely limiting, and in the past
several years researchers have come to address the more general
problem of dynamic mechanism design -- that of achieving an optimal
sequence of decisions over time, where the private information held by
agents in one time period is contingent on the decisions that have
come before, but in a non-deterministic way. Because agents are
continually acquiring new private information, incentives must be
provided successively over time rather than just once.

This tutorial will provide a comprehensive introduction to dynamic
mechanism design theory, focusing on social-welfare maximizing
(efficient) mechanisms. We will begin by introducing the standard
models of dynamic type and utility, as well as dynamic equilibrium
concepts. We will then provide a review of major results to date,
including: dynamic mechanisms that implement an efficient decision
policy in an ex post Nash equilibrium (including a dynamic analog of
the VCG mechanism); a strongly budget-balanced mechanism that is
efficient in Bayes-Nash equilibrium; and a dynamic redistribution
mechanism for a repeated resource-allocation setting. We will review
important application areas and describe the significant computational
challenges of the dynamic setting, emphasizing tractable special cases
such as multi-armed bandit problems. Finally we will call attention to
extensions of the standard model, including settings in which monetary
payments are not possible and settings in which the population of
agents is changing over time.