Spring 2010

Office: 4130 Upson 4139 Upson Hall

phone: 255-0984 255 9296

email: eva at cs.cornell.edu e-mails: renatoppl or hufu [at] cs [dot] cornell [dot] edu

Office hour during the final weeks (starting May 4th)

- Tuesday, May 4th Eva: 10-11am
- Thursday, May 6th Hu Fu 5:15-6:15pm
- Friday, May 7th Renato 11am-12pm
- Saturday, May 8th and Sunday, May 9th, Renato, call 607-280-5528 or email to make an appointment any time between 1-4pm.
- Monday May 10th Renato 3:30- 5 pm
- Tuesday, May 11th Hu Fu 11am-12pm
- Wednesday May 12th Eva 1:30-2:30 pm
- Thursday, May 13th Hu Fu 11am-12pm
- Friday May 14th Eva 1:30-2:30 pm
- Sunday May 16th Hu fu 10:30-11:30am
- Monday May 17th Eva 10:30-11:30am
- Tuesday May 18th Hu Fu 10:30-11:30am
- Wednesday May 19th Eva 10:30-11:30

starting on Wednesday, May 12th, Renato will hold office hours on Skype by appointment. Send him email to make an appointment.

You can also send us email to make an appointment..

Algorithmic Game Theory combines algorithmic thinking with game-theoretic, or, more generally, economic concepts. The course will focus on problems arising from, and motivated by, the Internet and other decentralized computer networks. The most defining characteristic of the Internet is that it was not designed by a single central entity, but emerged from the complex interaction of many economic agents, such as network operators, service providers, designers, users, etc., in varying degrees of collaboration and competition. The course will focus on some of the many questions at the interface between algorithms and game theory that arise from this point of view.

We will use the book

- Algorithmic Game Theory. (eds. Nisan, Roughgarden, Tardos, Vazirani)

and supplement it with additional papers. The book
is in reserve in the engineering library, and thanks to our progressive-minded
publisher you can read the entire book Algorithmic Game Theory (eds. Nisan,
Roughgarden, Tardos, Vazirani) online by clicking here (username=agt1user,
password=camb2agt)

Another excellent textbook that covers several of the course's topics is Shoham
and Leyton-Brown, Multiagent Systems,
Cambridge, 2008.

- Problem set 1 was Due Wednesday. Solutions are available on CMS
- Problem set 2 was Due Monday, March 8th. Solutions are available on CMS
- Problem set 3 was Due Monday April 5th. Solutions are available on CMS.
- Problem set 4 was Due Monday, April 26. Solutions are available on CMS
- Final is be take home and require individual work. You have 7 days to do the final, and can chose any day between Monday. May 3rd and Wednesday, May 12th to start. The final will be available here starting 4:35pm Wednesday on the 12th.

If the problem set deadline is causing problems, please let me know at least a few days ahead of the deadline.

(Lecture topics, references and pointers to additional papers are posted here each week.)

- Monday, Jan 25: Introduction (Chapter 1, pp 1-13)
- Wednesday, Jan 27 congestion games, potential games, and existence of Nash. See Sections 17, 1, 8.2.1, 19.3.2.
- Monday, Feb 1, price of anarchy and stability in potential games. See Section 19.3.3-4, and 18.4.2. The proof we only sketched in class is proof of Theorem 18.23 on page 477.
- Wednesday, Feb 3, non-atomic selfish routing, sections 18: existence of Nash, potential function, and consequences.
- Monday, Feb 8: Price of Anarchy for nonatomic congestion games: Section 18.4.1.
- Wednesday, Feb 10: applications to springs, and capacity augmentation of Section 18.5.2
- Monday, Feb 15: proportional resource allocation: sections 5.2-5.3 or see notes from earlier year: part 1, and the first part of part 2.
- Wednesday, Feb 17: proportional sharing price of anarchy on a link, and characterization of OPT and Nash on networks, see also the part 3 of the notes.
- Monday, Feb 22: The local connection game, section 19.2
- Wednesday Feb 24: Facility location games are potential games Section 19.4
- Monday, March 1: Price of Anarchy for facility location games
- Wednesday, March 3: randomized Nash and Load balancing. See Section 1.3.4 and also Chapter 20
- Monday, March 8. Coarse correlated equilibrium. See Section 1.3.6. and Chapter 4
- Wednesday, March 10. Weighted majority algorithm. See notes.
- Monday, March 15: Prince of
anarchy bounds for correlated equilibria for utililiy. See the paper
*Intrinsic Robustness of the Price of Anarchy*, by T. Roughgarden from STOC '09. - Wednesday, March 17: Prince of anarchy bounds for correlated equilibria continued: congestion games.
- Monday, March 29. external regret and internal regret, and algorithms for external regret, section 4.5
- Wednesday, March 31. Nash equilibria, and no-regret algorithms in two person 0-sum games, section 4.4
- Monday, April 5 and Wednesday April 7. Blackwell approachability and the learning algorithm regret matching. See the paper A Simple Adaptive Procedure Leading to Correlated Equilibrium by Hart and Mas-Colell.
- Monday, April 12 and
Wednesday, April 14: are correlated equilibria computable? See
*Computing Correlated Equilibria in Multi-Player Games*, by Papadimitriou and Roughgarden, - Monday April 19 through Monday May 26, Nash equilibria and the Brauwer fixed point theorem, and Sperner lemma, See Chapter 2.
- Wednesday April 28 and Monday May 3rd: complexity classes FNP, and PPAD, and hardness of Nash. See Chapter 2.
- Wednesday May 5th. Networked
0-sum games. See Daskalakis and Papadimitriou,
*On a Network Generalization of the Minmax Theorem*.

- 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
- Other 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
- correlated equilibria and connection to learning in games
- Quantifying the Inefficiency of learning outcomes

- Extensive form games
- Market equilibria

We may also consider a subset of the Part IV chapters depending on time available and the interest of participants.

The course pre-requisites is background in
algorithms and graphs at the level of CS 4820. No prior knowledge of game
theory or economics will be assumed.

There will be **4 homework sets during the semester, and a final**. You
may work in **pairs** on homeworks, 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. **Grades
and solutions to the homeworks will be kept in CMS.

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

ˇ Earlier version of this course

ˇ Algorithmic Aspects of Game Theory by Christos Papadimitriou

ˇ Topics in Algorithmic Game Theory by Tim Roughgarden and Jason Hartline

ˇ Algorithmic Mechanism Design by Jason Hartline

ˇ Topics in Algorithmic Game Theory by Costis Daskalakis