CS 6840 : Algorithmic Game Theory
· Click here for lecture by lecture schedule and scribe notes
· Homeworks and grades will be posted at CMS
· For questions and discussions we will use Piazza
Time and Place
Monday, Wednesday, Friday, 1:25-2:15pm.
101 Phillips Hall
Eva Tardos (Instructor)
Office hours: Monday 2:30-3:30, Thursday 9:30-10:30am
Thodoris Lykouris (Teaching Assistant)
Office hours: Tuesday 5:30-6:30pm in G15 (in the basement of Gates)
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
This is a theory course requiring being comfortable with proofs, probability, and basic combinatorial structures, at the level covered in CS 4820 or equivalent, i.e. an advanced undergraduate-level algorithms course. Prior knowledge of game theory is not assumed. If you are unsure whether you satisfy the prerequisite, please talk to the instructor.
There will be no required textbook, but the following is a very useful source with a lot of the material we will cover: Twenty Lectures on Algorithmic Game Theory, by Tim Roughgarden, Cambridge University Press, 2016. See also the Amazon page.
We will also use the recent survey The Price of Anarchy in Auctions by Tim Roughgarden, Vasilis Syrgkanis, Eva Tardos
The following collection is older, but is still useful for several topics. Algorithmic Game Theory, Cambridge University Press, 2007. Read the entire book online by clicking here (look under the "Resources" tab).
We will also draw on the following books for some of the lectures, we will post the corresponding sections on CMS: Parkes and Seuken, Economics and Computation 2016.
Course work consists of 4 homework sets, a final, a final project, and scribe notes.
· You are encouraged work on homework in pairs. Each pair of students can submit a single shared homework. You may discuss homework questions with other groups at a high level. It may be OK to have groups of 3 people by agreeing with the instructor on extra work. You can have 4 late days during the semester, using at most 2 days on any one homework.
· The final project can be done in pairs or in groups of 3 people.
· The final exam will be take home, it is a non-cooperative version of the homework.
· Each student is required to sign up to scribe one lecture. The lecture notes should be available within 24 hours of the lecture.
· Extra credit will be available for improving wikipedia pages about topics discussed in class.
The project should be a research-like experience (understand what is known 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).
We will use CMS for homeworks and other class materials.
Course grade is determined roughly as
· Homeworks: 10% each
· Scribe notes: 4%
· project proposal 4%
· project 24%
· take home final 28%
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
Rough Course Outline (subject to change). For lecture-by-lecture schedule and scribe notes click here.
Outcomes in games and Price of Anarchy
· Games, equilibria, examples of games,
· price of anarchy in routing games,
· no-regret learning, and 2 person 0-sum games
· smooth games and learning outcomes, maybe also best response dynamic
· best Nash and strong price of anarchy
Auction as Gates
· Basics of mechanism design: single item auctions
· Revenue equivalence
· Simple auctions for more complex settings: ad-auctions, simultaneous single item auctions, spectrum auction
Auction design using data
· Simple vs optimal auction: learning optimal auction from data
· A/B testing in auctions
· Inference in discrete games: econometrics for best response and for no-regret learners