Announcements (assignments etc.)
 Apr 29: Welcome to CO 759.
 Jun 4: Assignment 1 is
available. (Last update on Jun 4: some minor notational changes, the ordering of Q2
and Q3 was reversed.)
Due by Jun 25, 2015.
 Jun 4: Starting Jun 9, the lectures will be from 10:30am12:30pm. There will be a
break of 510min. around 11:30am. The classroom will remain unchanged, i.e., MC 6486.
 Jun 16: There is no lecture on Jun 16, 18. We will resume our 2hourly meetings
on Jun 23.
 Jun 16: Clarifications about Assignment 1:
 In Q2(b), you may assume that the alternative set A is finite.
 In Q4(e), the approximation guarantee of 2ρ only needs to hold with respect
to the optimal integral schedule; that is, we seek an implementable algorithm that
returns a fractional schedule of makespan at most 2ρ times the optimal
makespan (wrt. integral schedules).
 Jul 13: There is no lecture on Jul 14, 16. We will resume our 2hourly meetings
on Jul 21.
 Jul 20: The "Topics Covered" section has been updated and made current.
 Jul 21: Here is the missing bit from the
proof of Nash's theorem using Brouwer's fixedpoint theorem.
 Jul 21: Assignment 2 is
available. (Last update on Aug 4: Q8 added)
Due by Aug 14, 2015.
Note: You may answer any 5 questions on the assignment (or answer more for
bonus marks). There are currently 7 8 questions on the
assignment; a couple more questions will be posted in the coming week;
Q8 was added on Aug 4. All questions carry equal weightage.
 Jul 28: No lecture. There will be an extra lecture on Jul 30 (which will be the last
lecture).
 Jul 28: Clarifications about Assignment 2:
 There was a typo in Q1: in the definition of A', each x_{i}'s is
either m or a multiple of the ceiling of m/n^{2}
(not the floor).
 The wording in the first sentence of Q7(b) has slightly changed. The part asks you to
prove a contrapositive (qualitatively speaking) of Q7(a).

Course Overview and Outline
This is a graduatelevel, introductory course on algorithmic game theory.
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 below 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)
 May 5, 7: Course introduction and overview. Some simple games and definitions of
solution concepts. See sections 1.11.3.
 May 12: Started with algorithmic mechanism design. See Chapter 9. Introduction to
mechanismdesign, definition of a mechanism, notions of truthfulness/dominmantstrategy
incentive compatibility, 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).
 May 14: 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.
 May 19: The desirable features of VCG, and its limitation in the face of computational
intractability. The necessary condition of weakmonotonicity (WMON) for truthfulness.
Singledimensional domains: definition and examples.
 May 21: Characterization of implementable SCFs: the equivalence of WMON with the
monotonicity condition for singledimensional domains, 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 ∞).
 May 26: 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.
 The Design of Approximation Algorithms by David Williamson and David
Shmoys. Cambridge University Press, 2011. See Theorem 1.11. Theorem 1.12 proves a stronger
guarantee for the same algorithm via a dualfitting analysis.
Started with metric facility location and the MettuPlaxton algorithm. (Section 15.4.2
gives a different interpretation of the MettuPlaxton algorithm, based on the primaldual
method for approximation algorithms.) Here is the MettuPlaxton paper:
"The Online Median Problem", SIAM
Journal on Computing, 32:816832, 2003.
 May 28: 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.
 Jun 2: Finished with makespanminimization and introduced truthfulinexpectation
mechanisms. Started with mechanism design in multidimensional domains. Defined
combinatorial auctions (CAs). Gave some motivation and examples, and discussed issues
arising from a combination of computational and gametheoretic concerns.
 Jun 4: Described truthful, approximaton mechanisms for CAs with singleminded
valuations. See sections 11.1, 11.2.
Described a truthful mechanism for subadditive valuations based on constructing
a maximalinrange (MIR) mechanism, where we exactly optimize over a subset of
allocations.
 Jun 9: Started with a general technique for combining VCG and approximation algorithms
to obtain truthful, approximation mechanisms. See section 12.3, and the following paper:
Outlined the ellipsoid method and stated a theorem summarizing its performance. Here are
the slides on ellipsoid method used in lecture.
 Jun 11: Finished the proof showing the blackbox reduction from LPbased
approximation algorithms to truthful, approximation mechanisms. Showed various mechanisms
that one obtains as a corollary of this result. Observed that this construction can be
viewed as using an LPbased ρapproximation algorithm to
identify a subset (called the range) of the convex hull of integer allocations such that:
(a) one can (exactly) optimize efficiently over this subest; and
(b) the optimum over the subset is within a ρfactor of the optimal social
welfare.
This type of construction is often called a maximalindistributionalrange (MIDR)
mechanism, and implies that a approximation algorithm can sometimes be viewed
as exactly optimizing over a certain (large, meaningful) subset.
Started with another construction showing that a similar blackbox transformation (from
approximation algorithms to MIDR mechanisms) can be obtained from FPTASes for packing
problems. Defined packing problems, and the concept of an FPTAS.
 Jun 16, 18: No lecture.
 Jun 23: Described the blackbox reduction converting an FPTAS for a packing problem
with polynomial dimension to a truthfulinexpectation FPTAS using tools from smoothed
complexity. See the following paper:
 Jun 25: Nontruthful mechanisms for CAs. Defined simultaneous itembidding auctions
and gave some examples. Defined the (completeinformation) price of anarchy (PoA) and
nonoverbidding strategies. Proved a PoA bound of 2 for simultaneous secondprice auctions
with nonoverbidding subadditive players. See the following paper:
Stated that with submodular players a nonoverbidding pure NE (i.e., a pure NE with
nonoverbidding strategies) always exists.
 Jun 30: Described a greedy algorithm that computes a nonoverbidding pure NE
for simultaneous secondprice auctions with submodular players. See the following paper
(Section 3.2):
Defined loadbalancing games. Proved existence of pure NE. Considered the objective of
minimizing of maximum player cost (equivalently, the minimum makespan objective),
defined the concepts of price of anarchy (PoA) and price of stability (PoS), and
obtained PoA and PoS bounds. See sections 20.1, 20.2 (unfortunately the
book uses the reverse notation of i to index jobs and j to index machines);
the notes at the end of Chapter 20 give pointers to work in other models.
See also the following paper, which is the source of Theorem 20.6 on the fast convergence
to a Nash equilibrium via (carefully chosen) improving moves, and which also studies the
convergence time of improving moves in other related load balancing games:
Started with atomic (unsplittable) routing games: definition and examples. See section
18.2.2.
 Jul 2: Atomic routing games contd. Existence of pure NE via a potential function.
Defined potential games. See sections 18.2.2, 18.3.2 for atomic routing games, and
sections 19.3.2, 19.3.3 for potential games and potential functions.
Analysis of PoA and PoS for the sumofplayers'costs objective.
Used the potential function to obtain PoS bounds.
Proved a PoA bound of 5/2 for linear latency functions (which we later
reinterpret using the smoothness framework), and showed that this is tight.
See section 18.4.2 and the following paper:
 George Christodoulou, Elias Koutsoupias.
The price of anarchy of finite congestion
games. Proceedings, STOC 2005.
This considers atomic congestion games (which generalize atomic routing games). The proof
of the 5/2bound on the PoA with linear latencies is taken from here.
See example 18.6 for the PoA lower bound of 5/2 for linear latencies; here are the
slides used to illustrate in lecture to
illustrate this.
Showed that pure NE in single sourcesink atomic routing games can be computed via a
mincost flow computation.
 Jul 7: Defined the concept of (λ μ)smooth games. Defined the notions
of correlated equilibria (CE) and coarsecorrelated equilibria (CCE), and gave some
examples of CE. Proved that the PoA with respect to even CCE is at
most λ/(1μ) in (λ μ)smooth games.
Observed that the PoA bound of 5/2 for atomic routing games with linear latencies obtained
previously implies that these games are (5/3,1/3)smooth, and hence yields a 5/3PoA
bound with respect to CCE. The following paper introduced this smoothness framework and
contains many other results.
Started with nonatomic routing games: definition, examples, and definition of a Nash
flow. See section 18.2.1.
 Jul 9: Stated convex optimization theorem. Defined (convex) potential function for
nonatomic routing games and used the convex optimization theorem to prove existence and
uniqueness (in terms of edge latencies) of a Nash flow. See section 18.3.1.
Proved tight PoA bounds for any class of latency functions containing all constant
functions. See section 18.4.1.
 Jul 14, 16: no lecture.

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. Dominantstrategy incentive
compatibility, Bayesian incentive compatibility, truthful mechanism design with various
socialchoice functions
 Combinatorial auctions: socialwelfare maximization and profit maximization
 Mechanisms with good Nash equilibria: Simultaneous first and secondprice auctions
 Costsharing mechanisms
 (In)Efficiency of equilibria. Quantifying the efficiencyloss in gameversions
of various optimization problems due to uncoordinated behavior. Topics include:
 Network routing or congestion games: flow/traffic controlled by strategic agents is
routed between sourcesink pairs
 Smoothness analysis of price of anarchy
 Load balancing games, bandwidth sharing games
 Computational Aspects of Equilibria.
 Existence, complexity, and algorithmic aspects of Nash equilibria
 Correlated equilibria and their computation
 Markets and the computation of market equilibria
