Algorithmic Game Theory

Computer Science 6840
Spring 2014

218 Olin, MWF 1:25-2:15 

Instructor: …va Tardos                 TAsPooya Jalaly and Rad Niazadeh

Office:         316 Gates Hall                                                                   †††††††††† 336and 324 Gates Hall 

phone:         255-0984                                                              

email:           eva at cs.cornell.edu                                                e-mails: jalaly@cs.cornell.eduand rad@cs.cornell.edu

 

 

Office hours and Piazza

         Eva Tardos:Wednesdays 2:30-3:30 in 316 Gates Hall

         Pooya Jalaly: Monday 11-12 in G11 Gates Hall

         Rad Niazadeh: Friday 4-5 in G21 Gates Hall††††

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 course staff will 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.††††††††††††††††††††††† ††††††††††††††††††††††††††††††††††††††††

Class topics week-by-week

Notes for lecture from a previous year.

Notes for lecture   from a previous year.

Additional reference:Alex Fabrikant, Christos Papadimitriou, and Kunal Talwar On the complexity of pure Nash equilibria

Notes from a previous year

Please try the online Rock-Paper-Scissor game.

See sections 3-4 of the notes from 2007.

See sections 5 of notes and some of sections 4 of notes from 2007.

See section 2 of the notes from 2007, and the first page of the notes from 2012.

See notes from 2012

See notes from 2012.

See notes from 2012

See notes from 2012

Notes from Vasilis. See also the paper Intrinsic Robustness of the Price of Anarchy by Tim Roughgarden

See notes from 2012

See notes from 2012

See notes from 2012

See notes from 2012

Similar notes from 2012

Notes from 2012

Notes from 2012

Notes by Chris Liu

Notes by Jiayang Gao

Notes by Cathy Fan

         Friday, March 21, smooth games and the Bayesian Price of Anarchy

Notes by Xiaodong Wang

         Monday, March 24, Generalized second price action (GSP)

Notes by Daniel Freund

         Wednesday, March 26, price of anarchy for GSP

Notes by Jonathan DiLorenzo improved in April 14.

         Friday, March 28, price of anarchy for mechanisms based on greedy algorithms

Notes by Theodoros Lykouris

         Monday, April 7, smoothness, and second price item auction with unit demand bidders

Notes by Sam Park

         Wednesday, April 9, second price item auction with fractionally submodular valuations

Notes by Bryce Evans

         Friday, April 11, classes of valuations: submodular, subadditive and fractionally subadditive

See notes

         Monday, April 14, on Bandwidth sharing in a single link, and price equilibrium of the fair sharing game.

See notes from 2012.

         Wednesday, April 16, price of anarchy analysis for fair sharing on a single link.

See notes from 2012.

         Friday, April 18, on Bandwidth sharing in a network.

See notes from 2012.

         Monday, April 21, more on Bandwidth sharing in a network.

See notes, from 2012, and also the paper R. Johari and J.N. Tsitsiklis (2004). Efficiency loss in a network resource allocation game.

         Wednesday, April 23, Walrasian pricing equilibrium.

         Friday, April 25, Walrasian pricing equilibrium, and existence of optimal Nash in the GSP game.

         Monday, April 28, Vasilis Syrgkanis on sequential auction games

See the paper Sequential Auctions and Externalities

         Wednesday, April 30, Arrow-Debreu market equilibrium

         Friday, May 2, Arrow-Debreu market equilibrium cont, and Fischer markets

See notes from 2012. See also the course on Computation of equilibria by Amin Saberi

         Monday, May 5, revenue equivalence

See notes from 2012

         Wednesday, May 7th, Revenue versus an extra bidder: Bulow Klemperer

See notes from 2012, and the paper by Bulow Klemperer Auctions versus negotiations.

See also the courses

 

 

 

 

Problem sets

Problem set 1 was due Friday, February 14, it is now graded and solutions and comments are available on CMS.

Problem set 2 was due Wednesday, March 5, it is now graded and solutions and comments are available on CMS.

Problem set 3 was due Tuesday, March 24, 2014, it is now graded and solutions and comments are available on CMS.

Proposal for the final project was due, Friday March 28.

Problem set 4 was due Monday, April 21st, it is now graded and solutions and comments are available on CMS.

Final project is due Wednesday, May 7th. See more details at Course work below.

Take home final is available starting May 12th. 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 12-20, but need to be finished by 5pm on Tuesday the 20th. Office hours during the final week are posted on Piazza.

Other Useful resources:

         Sample tex file from Chris Liuís notes

         Video of all previous run of this class are available at www.videonote.com/Cornell


Rough course outline (subject to change): 

         Games we will discuss include

Course work

Course work consists of 4 homework sets, a final, a final project, and possibly scribe notes. You may discuss homework questions with other students, but need to write down the solutions on your own. The final is a non-cooperative version of the homework. Extra credit will be available for solving more homework problems than 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).

Grading

Course grade is determined roughly as

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.

Overview and Prerequisites

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 maturity. An A- or better in CS 4820 is great, or a course at a similar level in a different department.

 

Classes on similar topics at other universities:

         Earlier version of this course

         Price of Anarchy by Jason Hartline

         Algorithmic Mechanism Design by Jason Hatrline

         Algorithmic Game Theory by Tim Roughgarden

         Games, Decision, and Computation by Costis Daskalakis and Silvio Micali