Spring 2012

Office: 4141 Upson 4139 Upson Hall and 340 Upson hall

phone: 255-0984

email: eva at cs.cornell.edu e-mails: renatoppl and vasilis [at] cs [dot] cornell [dot] edu

**We also have a Piazza
page**. Piazza is a web-based discussion forum for communication with
classmates and the course staff. Except for confidential matters, Piazza is
preferred over email, as anyone can answer and everyone can benefit from the
answer. The coure staff weill monitor questions and answers and endorse good
answers in a timely manner. If you know the answer to a question, feel free to
post a reply yourself, but please avoid giving away any hints on the homework
or posting any part of a solution.

Algorithmic Game Theory combines algorithmic thinking with game-theoretic, or, more generally, economic concepts. The course will study a range of topics at this interface. The only prerequisite to the course is mathematical thinking at the level of doing well at CS 4820.

We will mainly use the books

*Algorithmic Game Theory*. eds. Nisan, Roughgarden, Tardos, Vazirani (username=agt1user, password=camb2agt), Cambridge, 2007.

- the
manuscript
*Approximation in Economic Design*by Jason Hartline

and supplement these with additional papers. Another excellent textbook that covers several of the course's topics is Shoham and Leyton-Brown, Multiagent Systems, Cambridge, 2008. For a nice introduction to Game Theory look at Ken Binmore: Game Theory: a Very Short Introduction, Oxford University Press.

- Problem set 1 was due Wednesday, February 15th. It is now graded. See solutions and grades at CMS.
- Problem set 2 was due Wednesday, February 29. It is now graded. See solutions and grades at CMS.
- Problem set 3 was due Friday, March 16. It is now graded. See solutions and grades at CMS.
- project proposal was due Wednesday April 4. It is now graded. See comments and grades at CMS.
- Problem set 4 was due Wednesday, April 18.
- Project is due Friday, May 4th
- Take-home final during the week of finals (between May 8-18). Final is cumulative, and is a non-cooperative version of the homeworks. You can choose any 72 hour period to do the final during May 8-18. Office hours during the final week will be posted here and also on Piazza.

The tex version of the notes for lecture 1 for suggested format.

- Notes for lecture 1:Monday, Jan 23 introduction and Breass paradox.
- Notes for lecture 2 Wednesday, Jan 25 on discrete congestion games and the existence of equilibria
- Notes for lecture 3, Friday, Jan 27 on non-atomic congestion games and equilibria
- Notes for lecture 4, Monday Jan 30 price of anarchy for non-atomic congestion games coming soon
- Notes for lecture 5, Wednesday Feb 1 on price of anarchy for smooth games
- Notes for lecture 6, Friday, Feb 3, utility games and the facility location game
- Notes for lecture 7, Monday Feb 6, price of anarchy for facility location
- Notes for lecture 8, Wednesday Feb 8 on quality solutions without reaching equilibria .
- Notes for lecture 9, Friday Feb 10 (by Vasilis Syrgkanis) on Price of Stability in cost-sharing game
- Notes for lecture 10, Monday, Feb 13 on strong Nash equilibria, and the strong price of anarchy for the cost-sharing games,
- Notes for lecture 11, Wednesday, Feb 15 on no-regret learning and the privce of anarchy,
- Notes for lecture 12, Frida, Feb 17 y on correlated equilibia and coarse correlated equilibria in games
- Notes for lecture 13, Monday, Feb 20 on the multiplicative weight algorithm for learning, coming soon
- Notes for lecture 14, Wednesday, Feb 22 on coarse correlated equilibria, and connection to Nash in 2-person 0-sum games.
- Notes for lecture 15, Friday, Feb 24 on single item auction, 2nd price, and fixed price in Bayesian setting,
- Notes for lecture 16, Monday, Feb 27 on Bayesian Nash equilibrium, and the first price auction for a single item.
- Notes for lecture 18, Wednesday, Feb 29 on the VCG mechanism
- Notes for lecture 19, Friday, March 2 on Bayesian Nash equilibria in single-parameter environments and revenue equivalence
- Notes for lecture 20, Monday, March 5 revenue equivalence continued, and the quantile space
- Notes for lecture 21,Wednesday, March 7 on Meyerson optimal auction.
- Notes for lecture 22, Friday, March 9 approximately optimal auction via monopoly reserve prices.
- Notes for lecture 23, Monday, March 12 non-regular distributions and the ironed virtual value
- Notes for lecture 25, Wednesday, March 14, Revenue optimal auction when values are independent, but may not be regular, coming soon.
- Notes for lecture 26, Friday, March 16, Matroid environments, and optimal auctions in such environments
- SPRING BREAK
- Notes for lecture 27, Monday, March 26 greedy auctions for single minded bidders coming soon. (Truth Revelation in Approximately Efficient Combinatorial Auctions
*.*D. Lehmann, L. I. O'Callaghan, Y. Shoham. Journal of the ACM , 49 (5), September 2002, 577-602. - Notes for lecture 28, Wednesday, March 28 greedy auctions and approximation algorithms. (Price of Anarchy for Greedy Auctions B. Lucier and A. Borodin.SODA 2010)
- Notes for lecture 29, Friday, March 30 on second price item auctions
- Notes for lecture 30, Monday, April 2nd on greedy auction and second price item auction as a smooth game
- Notes for lecture 31, Wednesday, April 4th on Price of anarchy for Second price item auctions and learning outcomes
- Notes for lecture 32, Friday, April 6th on Generalized second price auction.
- Notes for lecture 33, Monday, April 9th on the Prize of anarchy in Generalized second price auction
- Notes for lecture 34, Wednesday, April 11st, on Bandwidth sharing in a single link, and price equilibrium.
- Notes for lecture 35, Friday, April 13th, on game theoretical analysis of fair sharing on a single link, coming soon
- Notes for lecture 36, Monday April 16th, on fair sharing on a network. See also R. Johari and J.N. Tsitsiklis (2004). Efficiency loss in a network resource allocation game.
- Notes for lecture 37, Wednesday April 18. End of our fair sharing discussion, and starting market equilibria.
- Notes for lecture 38, Friday April 20, on Arrow-Debreu model of markets.
- Notes for lecture 39, Monday, April 23, existence of Nash equilibria in finite games
- Notes for lecture 40, Wednesday, April 25 on Sperner lemma in the plane and Brouwer fixed point theorem
- Notes for lecture 41, Friday, April 27 on high dimensional Sperner lemma and deriving Brouwer fixed point theorem
- Notes for lecture 42, Monday, April 30 on complexity of finding equilibria
- Notes for lecture 43, Wednesday May 2nd on NP completeness of deciding if a game has two Nash equilibria

Video of all previous classes are available at www.videonote.com/Cornell

A LaTex tutorial last year can be found at http://www.cs.cornell.edu/courses/cs4820/2011sp/handouts/tutorial2.html

Course outline (subject to change):

- Introduction to Algorithms and Games: (Chapter 1) games, Nash equilibria, solution concepts, and examples
- Quantifying the Inefficiency of Equilibria: (Part III: Chapters 17-21)
- Routing Games and other congestion games: Nash equilibria
- Potential games: Facility Location, Network Design
- Selfish Routing and Wardrop equilibria
- Network design games
- Bandwidth sharing Games
- Algorithmic Aspects of Equilibria (Part I: Chapters 2-7)
- existence and complexity of equilibria

- graphical games
- Learning in games fictitious play, experts algorithm, no-regret algorithms; convergence for zero-sum games
- Quantifying the Inefficiency of learning outcomes
- correlated equilibria and connection to learning in games
- Extensive form games
- Mechanism design and pricing games (Part II, and Hartline manuscipt)
- Social Choice Theory: Arrow's impossibility theorem, the Gibbard-Satterthwaite theorem;
- Mechanisms with Money: second-price auction, digital goods, Vickrey-Clarke-Groves mechanism;
- Combinatorial Auctions:; Auction Games, Generalized Second Prize
- Bayesian Mechanism Design:
- prior-independent mechanisms;

Course work consists of **4 homework sets, a final, a project, and scribe
notes.** You may work in **pairs** on homeworks and the project, and hand in a shared homework.
You may discuss homework questions with other students, but closely collaborate
only with your partner.** The final is a non-cooperative version of the
homework. **Extra credit will be available for solving more homework
problemsthan required or by improving wikipedia pages about topics discussed in
class. Grades and solutions to the homeworks will be kept in CMS.

The project should be a research-like experience (understand what is known about about a research problem, and try to advance knowledge). You can base projects on recent research papers: understanding what they are doing, and attempting to improve the model or result. Or you can base projects on your own research interests. You need to write your project result in format of a paper, expected to be 6-10 pages long (definitely no longer than 10).

Course grade is determined roughly as

- Homeworks: 10% each
- Scribe notes 5%
- project proposal 5%
- project 25%
- take home final 25%

Extra credit can be earned by solving all problem on the problem set, or by improving pages on wikipedia related to the course. Extra credit is very useful for getting an A+, and can also be used can to partially make up missing credit on homeworks, and the final.

**Classes on similar topics at other
universities: **

ˇ Earlier version of this course

ˇ Algorithmic Game Theory by Christos Papadimitriou

ˇ Algorithmic Game Theory by Tim Roughgarden

ˇ Algorithmic Mechanism Design by Jason Hartline

ˇ Topics in Algorithmic Game Theory by Costis Daskalakis