About This Course

The first half of the course will provide a broad introduction to games and market models, solution concepts, classical as well as recent developments in the field on equilibrium computation & complexity, price of anarchy, auctions, and others. The second half will address a selection of advanced topics and research projects.

Coursework:

Course grades are based on

3 Homeworks (10% each)
Project (50%)
Final Exam (15%)
Class participation (5%)

There may be opportunities for extra credit with the homeworks. (The extra credit earned will be applied after the curve.)

Prerequisites

This is a graduate level class and some background in algorithms and discrete mathematics will be assumed. Knowledge of some probability and linear programming would be useful. Attempt will be made to make the material accessible to interested non-theory students. Consult the instructor if you have questions.

For review of the prerequisite material, we strongly recommend the following online resources.

Building Blocks for Theoretical Computer Science by Margaret Fleck, written specifically for CS 173.
CS 473 taught by Jeff Ericson. Review the notes on linear programming and duality.
Mathematics for Computer Science by Eric Lehman, Tom Leighton, and Albert Meyer, written for the Mathematics for Computer Science course at MIT.

Reading Material

There is no required textbook. Pointers to existing lecture notes from various sources will be posted to the course web site as the semester progresses.

Course materials elsewhere

Textbooks:

N. Nisan, T. Roughgarden, E. Tardos, and V. Vazirani (editors), Algorithmic Game Theory, 2007. (Book available for free online.)
T. Roughgarden, Twenty Lectures on Algorithmic Game Theory, 2016
M. Osborne and A. Rubinstein, A Course in Game Theory, 1994.
R. Myerson, Game Theory: Analysis of conflict, 1991.

Homeworks, Exam and grading

Tentative homework schedule:

Submission	Date Posted	Due date
Homework 1	9/01	9/15
Homework 2	9/22	10/09
Homework 3	10/11	10/30

Homework submissions:

Homeworks must be submitted on Gradescope (link on course home page). Type-written submissions are preferred, but hand-written are acceptable only if your handwriting is extremely pretty to look at.
No late submissions unless any deadline extension is announced. For any regrade requests, please go to office hours.

Projects

Tentative project and exam timeline:

Submission	Rough due date
Project topic+summary	mid-september
Mid-project meetings	end of october/first week of november
Project presentations	last two weeks of lectures
Project report	last day of semester
Final Exam	last day of semester

Project report

The format to be used is LLNCS. You can fin the package's class(.cls) file as well as an example template here.
The report should start with a title, author names, and the abstract. The page limit is 8 pages excluding references. More material should go in the appendix. Do not change the margins or font size (11pt). Reports that deviate too much from the specified format may lose points.

Final Exam Format

TBA

CS 580 RM: Administrivia