Fall 2008

Office: 4130
Upson
657

phone: 255-0984 255-4195

email: eva at cs.cornell.edu thanh at cs.cornell.edu

Office Hours: Tuesdays 3-4. Wednesdays 5-6

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

**Office hours for the final weeks**

Friday May 2:
3:30-4:30pm
Eva in 4130 Upson

Monday, May 5.
4-5pm
Thanh in 657
Rhodes

Tuesday, May 6
3-4pm
Eva 4130 Upson

Wednesday, May 7.
4-5pm
Thanh in 657
Rhodes

Thursday, May 8
3-4pm
Eva 4130 Upson

Friday, May 9.
4-5pm
Thanh in 657
Rhodes

Monday, May 12
3-4pm
Eva 4130 Upson

Tuesday, May 13.
4-5pm
Thanh in 657
Rhodes

Wednesday, May 14
4-5pm
Eva 4130 Upson

Thursday, May 15
1-2pm
Eva 4130 Upson

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 many chapters. See table of contents, as well as many chapters are available online.

Book

Topics include some of the following (subject to change):

- Introduction to Algorithms and Games: (Chapter 1)
- Quantifying the Inefficiency of Equilibria: (Part III: Chapters 17-21)
- Routing Games and other congestion games: Nash equilibria
- Facility Location, Network Design
- Cooperative equilibria
- Selfish Routing and Wardrop equilibria
- Other Network design games
- Randomized load balancing games
- Bandwidth sharing Games
- Algorithmic Aspects of Equilibria (Part I: Chapters 2,3 and 7)
- existence and complexity of equilibria
- correlated equilibrium and games with many players
- graphical games
- Extensive form games
- Mechanism and Protocol Design (Part II: some of Chapters 9-14)
- algorithmic mechanism design
- Stable Matching
- Combinatorial Auctions
- frugality and alternate auction mechanisms
- Distributed Auctions and BGP
- auctions for digital goods

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 482. No prior knowledge of game theory
or economics will be assumed.

**Problem Sets**

Problem set 1 was due on Thursday February 21st. It is now graded, and solutions are available on CMS.

Problem Set 2 was due on Thursday March 13th. It is now graded, and solutions are available on CMS.

**Project Proposal was due Thursday March 27th.** The project proposal is a
few paragraph long explanation on what you are hoping to accomplish. The goal of
asking for the proposals is to get each group started on thinking about
the projects, and also to allow early feedback on the plans. Project group may
contain 2-3 students.

There are many different types of projects possible. You can consider a game
motivated by some computer science and/or network problem, and propose to work
on understanding the algorithmic issues associated with this game, such as how
to find an equilibria, are there many equilibria, do natural plays find such
equilibria, what are the quality of the worst or best equilibria, etc. Projects
may be theoretical or experimental in nature.

Alternatively, your project may choose to understand, explain and possibly
extend 2-3 papers from the literature. There are many references in the book for
interesting related papers to read. For such a proposal, you should make sure
that you understand the papers well, and can explain compare the results, and
techniques of different papers, explain their advantages and disadvantages.

**Problem Set 3 was due on Tuesday April 15th. **Problems 2 and 4 updated on April 2

- Problem 2 is asking about finding a Nash, that can be possibly mixed (not pure)
- Problem 4 I changed the notation to match the facility location notation
we used in class. p
_{i }is the value for user i, the cost c_{ij }is the cost to connect user i to facility at location j, and we assume the user pay this cost, and p_{i }is the price paid by user i.

**The final project will be due Thursday May 1st**

**The class final can be taken any time after May 1st. **Final can be
picked up from Eva or Than** **(stop by or send us email to ask) .You will
have 3 days to finish the final, starting when you picked it up.

Topics week by week, references, etc.

- Tuesday, Jan 22: class overview, definitions and examples prisoner dilemma, and tragedy of the commons. See sections 1.1-1.3.
- Thursday, Jan 24: potential games ( See Section 19.3.1) and the grouping game.
- Tuesday, Jan 27: congestion games. See Section 19.3.2.
- Thursday, Jan 29: price of anarchy and stability in potential games. See Section 19.3.3-4.
- Tuesday, Feb 5: lecture by Thành Nguyen: congestion games with player dependent payoffs. See paper

Igal Milchtaich**: **
Congestion Games with Player-Specific Payoff
Functions, *Games and Economic Behavior
***13** (1996), 111–124*.*

- Thursday, Feb 7: non-atomic selfish routing, sections 18. Nash flow compared to optimally routing twice the flow (Section18.5.2).
- Tuesday, Feb 12: non-atomic routing as a potential game ( See Section 18.3) . Nash vs optimality conditions
- Thursday Feb 14: price of anarchy in non-atomic routing (section 18.4).
- Tuesday, Feb 19: resource allocation; proportional fair sharing (section 21.2)
- Thursday, Feb 21: proportional fair sharing, existence of equilibrium and price of Anarchy (section 21.2)
- Tuesday, Feb 26: Local connection game (Section 19.2)
- Thursday, Feb 28: More on the Local connection game (Section 19.2)
- Tuesday, March 4: Cooperative local connection game

Nir Andelman, Michal Feldman and Yishay Mansour

Strong Price of Anarchy

Seventeenth ACM-SIAM Symposium on Discrete Algorithms (SODA), 2007For proof of Lemma 4.1 see Appendix B of

S. Albers, S. Eilts, E. Even-Dar, Y. Mansour and L. Roditty.

On Nash Equilibria for a Network Creation Game.

Seventeenth ACM-SIAM Symposium on Discrete Algorithms (SODA), 2006

- Thursday, March 6: Cooperative fair sharing game:

Amir Epstein, Michal Feldman and Yishay Mansour

Strong Equilibrium in Cost-Sharing Connection Game

In Proceedings of the 8th ACM Conference on Electronic Commerce (EC'07)

- Tuesday, March 11: Randomized Load Balancing (Chapter 20: uniform machines)
- Thursday, March 13: Randomized Load Balancing cont. (Chapter 20: uniform machines)
- March 17-21 spring break
- Tuesday March 25: Facility location game and PoA (Chapter 19)
- Thursday March 27: outcome of repeated best response in the facility location game (Chapter 19)
- Tuesday April 1st: 2 person 0 sum games and no-regret learning behavior in games (Sections 1.4.2 and 4.2)
- Thursday April 3rd: swap regret and correlated equilibrium (Sections 1.3.6 and 4.2)
- Tuesday April 8th: lecture by Thành Nguyen: A no-regret learning algorithm (Section 4.3)
- Thursday April 10th: swap regret (section 4.5)
- Tuesday April 15: finding correlated equilbria in graphical games (section 7.4)
- Thursday April 17: lecture by Sid Suri: evolutionary games (sections 29.1 and 3)
- Tuesday April 22: Brouwer fixed point theorem.
- Thursday April 24: Existence of Nash and Brouwer fixed points. Variants of Nash that are NP-complete. (chapter 2). For details on the latter see also

Vincent Conitzer and Tuomas Sandholm. New Complexity Results about Nash Equilibria. To appear in Games and Economic Behavior.

- Tuesday April 29: finding Nash equilbria and PPAD( Chapter 2). see also the colloquium talk by Costis Daskalakis on Thursday May 1st, in Upson B17 at 4:15 pm.

There will be **3 homework sets during the semester, a final, and a final project**.
You may work in **pairs** on
homeworks and on the project, and hand in a shared homework.**
The final is a non-cooperative version of the homework. **Grades
and solutions to the homeworks will be kept in
CMS.

For the class project students can propose independent projects, or read, critically evaluate and try to extend or modify some papers that were not covered in class, in an area related to the course. The first step in the project will be a short (1 page) "proposal", suggesting the project topic, or papers you want to read, and an outline of your plans. The final project should contain a summary of the problem and model considered in the papers, your critical evaluation of the problem, summary of the result, your attempts to extend/modify the solution, and intuitive explanation and proof of why some of the results are true, and why it does or does not extend.

There are many similar course offered at other schools too: Game Theory . net offers a wide range of game theory courses.