Announcements (assignments etc.)
 Sep 13: Welcome to CO 759.
 Oct 13: Assignment 1 is
available. (Last updated:
Oct 21 Oct 28 Oct 31.)
Due on Nov 1, 2010 Nov 3, 2010.
Here are the Solutions.
 Oct 21: A typo in Q2(d) has been corrected: the time allowed is
O((input size).log(1/ε)). The assignment has been updated.
 Oct 28: Some clarifications and corrections about Q2(d): the time allowed is
polynomial in the input size and log(1/ε). Also, you are given an oracle
that can solve polynomialsize setcover LPs, and each call to this oracle counts as one
operation.
The assignment has been updated, and the due date has been extended to
Nov 3.
 Oct 31: A minor, but crucial typo in Q4(a) has been corrected: it should be
δ(a,b)=inf{v_{i}(a)v_{i}(b):
f(v_{i},v_{i})=a}.
 Nov 26: Assignment 2 is
available.
Due by Dec 7, 2010. Here are the Solutions.
 Dec 7: The takehome final exam can be picked up from my office.
You can pick up the exam either on Wednesday, Dec 8, or Thursday, Dec 9. The
exam will be due 5 days from the pickup date.
So pick up: Dec 8 => due by Dec 13, 5pm;
pick up: Dec 9 => due by Dec 14, 5pm.
I will be in my office on Dec 8 from 122pm, and on Dec 9 from 26pm.
If you are unable to reach me in my office, then you may request to receive the final exam
via email (but please try to pick it up in person from me first).
 Dec 8: Solutions to Assignment 2 have been posted.
 Dec 12: Solutions to Assignment 1 have been posted.

Course Overview and Outline
Algorithmic game theory
applies algorithmic reasoning to gametheoretic settings. A prototypical motivating
example for the problems we will consider is the Internet, which is a fascinating
computational artifact in that it was not designed by any one central authority, or
optimized for one specific purpose, but rather emerged from the interaction of several
entities, such as network operators, ISPs, users, in varying degrees of coordination and
competition. This course will investigate a variety of questions that arise from looking
at problems (often classical optimization problems) from this point of view. We will
examine, in part, algorithmic issues in games, and in part, algorithmic problems that
arise in settings with strategic players.
See here for a tentative list of topics, and
here for a pdf version of the course outline containing a
list of topics.

Topics Covered (including relevant references)
 Sep 13: Course introduction. Some simple games and definitions of solution
concepts. See sections 1.11.3.
 Sep 15: Started with algorithmic mechanism design. See Chapter 9. Introduction to
mechanismdesign, definition of a mechanism, notions of truthfulness/dominmantstrategy
implementation, the singleitem auction problem and the secondprice auction. See sections
9.3.1, 9.3.2, 9.4.1, 9.4.2 (the definition of a mechanism here is slightly more general in
that it allows the designer to define arbitrary strategysets, utility functions; see
section 9.4.3 for why our definition is without loss of generality).
 Sep 20: The (algorithmic) implementation problem: which socialchoice functions (SCFs)
are (efficiently) implementable, or admit an approximation that is efficiently
implementable. The VCG mechanism: definition, proof of truthfulness, and examples. See
sections 9.3.39.3.5. The desirable features of VCG, and its limitation in the face of
computational intractability.
 Sep 22: Singledimensional domains: definition and examples. Characterization of
implementable SCFs: the necessity of weakmonotonicity (WMON) and its sufficiency for
singledimensional domains. See sections 9.5.2, 9.5.4; the definition in section 9.5.4
corresponds to the special case where α_{i} is a {0,1}vector.
See definition 12.1 in section 12.2 for the more general setting (there is a
typo in Theorem 12.2: the second integral should go from 0 to ∞).
 Sep 27: Applications involving singledimensional domains: the set cover problem.
Here are some references for the greedy algorithm for set cover.
 Approximation Algorithms, Vijay Vazirani. SpringerVerlag 2001. See Section
2.1; also Section 13.1 describes the same algorithm, but the algorithm is stated
and analyzed as a dualfitting algorithm.
 Algorithm Design, J. Kleinberg and É. Tardos. AddisonWesley, 2005. See
Section 11.3; the analysis here is also based on dual fitting, and is similar to the one
in Section 13.1 of the above book.
Started with metric facility location. (Section 15.4.2 gives a different interpretation of
the algorithm discussed in class, based on the primaldual method for approximation
algorithms.)
 Sep 29: Applications contd.: finished facility location. Started with
makespanminimization on machines with speeds (called "related machines" in the scheduling
literature). See section 12.2.1. Note: there are various typos in the proof of
Lemma 12.6.
 Oct 4: Finished with makespanminimization. Mechanism design in multidimensional
domains: combinatorial auctions (CAs). Some examples.
 Oct 6: CAs contd.: truthful, approximaton mechanisms with singleminded
valuations. See sections 11.1, 11.2.
 Oct 13: CAs contd.: finished the singleminded case. Truthful mechanisms for
subadditive valuations.
 Oct 15: CAs contd.: a general technique for combining VCG and approximation algorithms
to obtain truthful, approximation mechanisms. See section 12.3, and the following paper:
 Oct 20: CAs contd.: finished the proof showing the blackbox reduction form
LPbased approximation algorithms to truthful, approximation mechanisms.
 Oct 22: CAs contd.: blackbox reduction converting an FPAS for a packing problem with
polynomial dimension to a truthfulinexpectation FPAS. See the following paper:

Prerequisites
There is no official prerequisite for the course. I will assume some basic knowledge of
discrete structures like graphs, algorithms, and optimization. No prior knowledge of game
theory will be assumed. If you would like to take the course but are unsure about the
prerequisites, then come and talk to me.

Books and Supplementary Material
For many of the topics we will follow the book
 Algorithmic Game Theory, Noam Nisan, Tim Roughgarden, Éva Tardos, Vijay
Vazirani (editors). Cambridge University Press, 2007.
Thanks to the publishers, this book can be viewed online
here (username=agt1user,
password=camb2agt), and many of the individual chapters are also available online. Here is
a list of errata from the first printing. We will supplement this
book with various research papers, notes etc., as necessary, which will be posted online.

Tentative list of topics
Some subset of the following topics will be covered. This is a course that offers
plenty of flexibility. If there is a topic that is not in here and you would really like
to see covered, come and talk to me about it!
 Introduction to games and algorithms.
 Algorithmic Mechanism Design. The design of computationally
tractable games (called mechanisms) whose equilibria are efficient.
Topics include:
 Socialchoice functions and the implementation problem in dominant strategies:
truthful mechanism design with various socialchoice functions
 Combinatorial auctions: socialwelfare maximization
 Costsharing mechanisms
 (In)Efficiency of equilibria. Quantifying the efficiencyloss in gameversions
of various optimization problems due to uncoordinated behavior. Examples include:
 Network routing or congestion games: flow/traffic controlled by strategic agents is
routed between sourcesink pairs
 Network creation and connectivity games: agents are nodes/terminals that seek to
create a graph or subgraph with certain connectivity properties
 Load balancing games: agents are jobs that need to be distributed across machines
 Bandwidth sharing games: a common resource, e.g., bandwidth, is to be shared across
several agents
 Computational Aspects of Equilibria.
 Existence, complexity, and algorithmic aspects of Nash equilibria
 Graphical games
 Correlated equilibria and their computation
 Markets and the computation of market equilibria
