University of Pennsylvania
Instructor: Bo Waggoner
TAs: Zach Schutzman, Hadi Elzayn, Omar Paladines, Akilesh Tangella, and Ian Masters.
Time: Tuesday/Thursday 3:00-4:30
Room: Moore 216
News:
April 8: hw6 posted, due in two weeks.
April 2: The final exam is May 4, noon - 2pm.
Game theory is the study of systems of agents, each of which acts toward its own goals and is impacted by the decisions of the others.
In this course, we will study game theory and related problems from an algorithmic perspective.
We will consider questions such as: how should an auction for scarce goods
be structured if the seller wishes to maximize his revenue? How badly
will traffic be snarled if drivers each selfishly try to minimize their
commute time, compared to if a benevolent dictator directed traffic?
How can couples be paired so that no two couples wish to swap partners
in hindsight? How can we find kidney-exchange cycles to incentivize people to participate in the exchange, without using money? How can you be as successful at betting on horse races as
the best horse racing expert, without knowing anything about horse
racing?
Prerequisites:
This course will be theoretical and mathematical rigorous.
Ideally (though not mandatory), students will have taken, or be taking concurrently, a course on algorithms (such as CIS 320) and will be familiar with big-O notation.
"Mathematical maturity" and experience with proofs will be very helpful.
Experience with game theory is not assumed.
Goals and Grading:
The goal of this course is to give students a rigorous introduction to game theory
from a computer science perspective, and to prepare students to think
about economic and algorithmic interactions from the perspective of
incentives. Grading will be based on participation, problem sets, a
midterm, and a final exam.
Resources and Links:
Piazza will be used to discuss class material and ask and answer questions. Please ask all material-related questions on Piazza so everyone can benefit from and contribute to the answers and discussion.
Gradescope will be used to submit homeworks and receive grades. Entry code: MBPRR4
Optional, supplementary textbooks: Twenty Lectures in Algorithmic Game Theory by Tim Roughgarden; the Algorithmic Game Theory book edited by Nisan, Roughgarden, Tardos, and Vazirani, which can be found online; and much of Multiagent Systems by Shoham and Leyton-Brown, available here (pdf).
Office Hours:
Calendar for office hours.
If you cannot make office hours, please email the instructor, or ask a question on Piazza.
Thursday, Jan. 11 (no class): intro video (8min), readings Foreword, Ch 1.1 of the Algorithmic Game Theory book edited by Nisan, Roughgarden, Tardos, and Vazirani.