** Instructors: ** Sergei Vassilvitskii,
Sébastien Lahaie (both at Yahoo! Research)

**E-mail**: { sergei, lahaies } at yahoo-inc.com

**Teaching Assistants**

- Etienne Vouga (evouga at gmail). Office Hours Sunday 4-5pm, Location 122 Mudd.
- Rajat Dixit (usa.rajat at gmail). Office Hours Thursday 11:45am-12:45pm. Location, 122 Mudd

** Time/Location: ** 4:10-6:00PM on Mondays in 233 Mudd. ~~253 Engineering
Terrace~~

** Course description: ** Algorithmic game theory is an emerging area
at the intersection of computer science and microeconomics. Motivated by
the rise of the internet and
electronic commerce, computer scientists have turned to models where
problem inputs are held by distributed, selfish agents (as opposed to the
classical model where the inputs are chosen adversarially). This new
perspective leads to a host of fascinating questions on the interplay
between
computation and incentives.

This course provides a broad survey of topics in algorithmic game theory, such as: algorithmic mechanism design; combinatorial and competitive auctions; congestion and potential games; computation of equilibria; network games and selfish routing; and sponsored search. No prior knowledge of game theory is necessary; the most important prerequisite is mathematical maturity.

** Prerequisites: ** Algorithms ( COMS 4231 ), Discrete Math ( COMS 3203 ).

** Optional Text: ** *Algorithmic Game Theory*. Nisan, Roughgarden, Tardos, Vazirani.
Cambridge University Press, 2007.

*** The book is available online for free! Thanks to the progressive-minded publisher,
you can read the entire book by clicking
here
(username=agt1user, password=camb2agt).

** Course requirements: **Two problem sets (25% each); a 10-15 page report
summarizing 1-3 research papers (40%); participation (10%). Pass/Fail students, select either the
problem sets or the project.

** Late Policy: ** You can hand in __one__ of the problem sets 3 days late (Thursday at 5pm).
No other late homeworks will be accepted. You cannot hand in the project late.

- Problem Set #1 (Out 9/29, due in class 10/13.)
- Problem Set #2 (Out 10/13, due in class 10/27.)
**Suggestions for project topics.****Instructions for the project.**- Report preferences: due Tue 11/11 by email.
- Report abstracts (1-2 pages): due Tue 11/18 by email.
- Final report: due Mon 12/8 in class.

**Homework policy:**
You are encouraged to discuss the course material and the homework
problems
with each other in small groups (2-3 people), but you must *list all
discussion
partners on your problem set*.
Discussion of homework problems may include
brainstorming and verbally walking through possible solutions, but should
not include one person telling the others how to solve the problem.
In addition, each person *must write up their solutions
independently;
you may not look at another student's written solutions*.
You may consult outside materials, but *all materials used must be
appropriately acknowledged*, and you must always write up your
solutions in your own words. **Violation of this policy will result
in a penalty to be assessed at the instructor's discretion. This may include
receiving a zero grade for the assignment in question AND a failing grade
for the whole course, even for the first infraction.**

**Schedule and references:**

- Mon 9/8 (SV, SL): What is Algorithmic Game Theory? Examples: auctions, selfish routing, complexity. Lecture notes [pdf]
- Mon 9/15 (SV): Selfish Routing and Price of Anarchy. Lecture notes [pdf]
- Chapter 18 of the textbook.
- T. Roughgarden. Selfish Routing and the Price of Anarchy. MIT Press, 2005.
- T. Roughgarden and E. Tardos. How Bad Is Selfish Routing? Journal of the ACM, 49(2):236-259, 2002.

- Mon 9/22 (SV): Shapley Network Design Games. Lecture notes [pdf]
- Chapter 19.3 of the textbook.
- E. Anshelevich, A. Dasgupta, J. Kleinberg, E. Tardos, T. Wexler, T. Roughgarden. The Price of Stability for Network Design with Fair Cost Allocation (FOCS 2004).
- E. Anshelevich, A. Dasgupta, E. Tardos, T. Wexler. Near Optimal Network Design with Selfish Agents (STOC 2003).

- Mon 9/29 (SL): Sealed-Bid Combinatorial Auctions. Lecture notes [pdf]
- Chapters 11.1-2 of the textbook.
- D. Lehmann, L. I. O'Callaghan, Y. Shoham. Truth Revelation in Approximately Efficient Combinatorial Auctions. Journal of the ACM, 49(5):577-602, 2002.

- Mon 10/6 (SL): Iterative Combinatorial Auctions. Lecture notes [pdf]
- Supplementary notes on linear programming [pdf]
- Chapter 11.7 of the textbook.
- S. de Vries, J. Schummer, R. Vohra. On Ascending Vickrey Auctions for Heterogeneous Objects. Journal of Economic Theory, 132(1):95-118, 2007.
- S. Bikhchandani, J. M. Ostroy. The Package Assignment Model. Journal of Economic Theory, 107(2):377-406, 2002.

- Mon 10/13 (SL): Communication Complexity of Combinatorial Auctions. Lecture notes [pdf]
- Chapter 11.6 of the textbook.
- N. Nisan, I. Segal. The Communication Requirements of Efficient Allocations and Supporting Prices. Journal of Economic Theory, 129(1):192-224, 2006.
- N. Nisan. The Communication Complexity of Approximate Set Packing and Covering (ICALP 2002).

- Mon 10/20 (SV): Digital Goods Auctions.
- Mon 10/27 (SL): Algorithms for Market Equilibrium.
- Chapter 5 of the textbook.
- R. Garg, S. Kapoor. Auction Algorithms for Market Equilibrium. Mathematics of Operations Research, 31(4):714-729, 2006.
- N. Devanur, C. Papadimitriou, A. Saberi, V. Vazirani. Market Equilibrium via a Primal-Dual-Type Algorithm (FOCS 2002).

- Mon 11/3: No class (Academic holiday---Elections).
- Mon 11/10 (SV): TBD.
- Mon 11/17 (SV) : Complexity of Computing Nash Equilibria.
- Mon 11/24: No class (Thanksgiving break).
- Mon 12/1 (SL): Sponsored Search I: Truthfulness. Lecture notes [pdf]
- Chapter 28 of the textbook.
- S. Lahaie. An Analysis of Alternative Slot Auction Designs for Sponsored Search (EC 2006).
- G. Aggarwal, A. Goel, R. Motwani. Truthful Auctions for Pricing Search Keywords (EC 2006).

- Mon 12/8 (SL): Sponsored Search II: Equilibrium Properties.
- See notes from the last lecture.
- H. Varian. Position auctions. International Journal of Industrial Organization, 25:1163-1178, 2007.
- B. Edelman, M. Ostrovsky, M. Schwarz. Internet Advertising and the Generalized Second-Price Auction: Selling Billions of Dollars Worth of Keywords. American Economic Review, 97(1):242-259, 2007.