CS 6840 : Algorithmic Game Theory

Spring 2017

**Resources**

·
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

**Course
Staff**

**Eva Tardos**** (Instructor)**

316
Gates Hall

Office hours: Monday 2:30-3:30, Thursday 9:30-10:30am

Email:
eva.tardos@cornell.edu

**Thodoris Lykouris**** (Teaching Assistant)**

Office
hours: Tuesday 5:30-6:30pm in G15 (in the basement of Gates)

Email:
teddlyk@cs.cornell.edu

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

**Prerequisites**

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.

**General
References**

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:**

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.

**Grading:**

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