**CSE691 / ECO606 Computational Game Theory (Spring
2014)**

**Course Description**

Computational game theory is a quickly developing area at the
interface of computer science and economics. It was largely motivated by the
emergence of the Internet and the trend of making strategic decisions online.
Indeed, more and more “entities” in our systems are switching from mindless
devices that honestly run whatever algorithms or protocols they have been
given, to strategic players. Examples include auctions, social networks, and
crowdsourcing systems.

Designing such systems is challenging, because it is unlikely for
the designer to have all the data needed to improve the performance of the
systems, and he or she must find reliable ways to elicit the correct data from
players who rationally and selfishly act so as to maximize their own utilities.
It is even more challenging when the computational resources of the designer or
the players are limited, when the players may form coalitions and coordinate
their strategies, or when the players may have privacy concerns about revealing
information about themselves.

This course is about analyzing and designing such systems using
ideas from algorithms, cryptography, and game theory. We shall start with fundamental
concepts and techniques in game theory, and gradually proceed to the state of
the art in computational game theory. On the way we shall see how Computer
Science and Economics are affecting each other. Topics include but not limited
to: games, equilibria, auctions, single-parameter games, mechanism design, and
crowdsourcing.

**Prerequisites **

Basic knowledge of probability, algorithms, and (very basic)
computational complexity. Interested students without a computational
background are encouraged to register, in particular students in economics and
mathematics. Such students should discuss with the instructor about background
issues before the course starts. Requirements may be adjusted to take
background disadvantages (and advantages) into account.

Instructor: Jing Chen

Office: 1416 Computer
Science Building

Spring 2014 Office
Hour: Tuesday, 2:00-3:00pm

Lecture: MW
4:00-5:20pm, Social and Behavioral Sciences Building S328

Useful references:

A
Course in Game Theory. M. J. Osborne and A. Rubinstein. MIT Press.

An
Introduction to Game Theory. M. J. Osborne. Oxford University Press.

Algorithmic
Game Theory. N. Nisan, T. Roughgarden, E. Tardos, and V. Vazirani (Eds). Cambridge University Press.

Tim
Roughgarden’s Algorithmic Game Theory
course.

Costis
Daskalakis and Silvio Micali’s
Games,
Decision, and Computation course.

·
If you haven’t
done this yet: please finish the Background
Questionnaire and return it in class on Monday, Feb. 3.

·
Please type your
solutions for exercises and problem sets, and submit either the pdf file by
email or the printout in class. You can use this template for LaTeX: tex, pdf.

·
We also have a
website in Blackboard. We’ll
put photos of our (real!) blackboard there.

·
Following the
university's announcement about make-up classes, we will have our last class on
May 12, and we'll use it for project presentation. Details will come later.

The
grade will be based on three parts.

·
Homework (45%)

There will be two types of
homework: exercises and problem sets.

Exercises review basic
concepts taught in class, roughly 1 problem per lecture. They will be graded as
C(correct)/PC(partially correct)/I(incorrect). You
should solve exercises independently.

Problem sets will be bi-weekly
or tri-weekly. You can discuss the problems with other students taking this class,
but I suggest you not do so until you have made serious effort trying to solve
them by yourself.

You ** must** write up and submit your
solution individually, and you

**Note!** For problem sets, if you really don’t know how
to solve a problem after making serious effort, write “I honestly don’t know
how to solve this problem” and you’ll get 25% of it. While if you “make up” a
solution by putting together some random sentences, you may get lower than
that. Indeed, I believe that to realize you don’t understand something is an
important step towards understanding it.

·
Project (45%)

Students will team up to work on a project. Each
team can be at most 3 persons. Single-person project is allowed but not
encouraged. The project can be either a survey of the research frontiers of
some topic in Computational Game Theory, or original research in CGT, or novel
applications of CGT ideas to other fields.

Checkpoints:

1. Project Proposal. A single
paragraph describing your proposed project, together with a list of relevant
papers.

2. In-class Presentation. A
10-15 minutes presentation by each team. Probably in the last lecture.

3. Written Report. Each
team must turn in a written report. It should be no more than 5 pages not
including references, with optional appendices that can be as long as you like
and will be read at my discretion.

Good ways of finding a project topic:

1. What we cover in class
and you want to see more.

2. What we don’t cover but
you want to see.

3. CGT problems coming up
from your own research.

4. CGT papers published in
CS conferences and Econ journals, such as STOC, FOCS, EC, ITCS, WINE, JET, GEB,
etc.

Timeline and more information on the project
will be given later.

·
Class participation (10%)

I encourage you to answer questions and to ask
questions in class, as I believe interaction is an efficient way of learning.

·
Exercises 1 and 2, due by Monday, Feb. 3, 4pm.

·
Exercises 3 and 4, due by Monday, Feb. 17, 4pm.

·
Exercises 5 and 6, due by Monday, Feb. 24, 4pm.

·
Exercises 7 and 8, due by Monday, Mar. 3, 4pm.

·
Exercises 9 and 10, due by Monday, Mar. 10,
4pm.

·
Exercises 11 and 12, due by Monday, Mar. 24,
4pm.

·
Exercises 13 and 14, due by Monday, Mar. 31,
4pm.

·
Exercises 15 and 16, due by Monday, Apr. 7,
4pm.

·
Exercises 17 and 18, due by Monday, Apr. 14,
4pm.

·
Exercises 19 and 20, due by Monday, Apr. 21,
4pm.

·
Pset1, due by Monday, Mar. 10, 4pm.

·
Pset2, due by Wednesday, Apr. 2,
4pm.

·
Pset3, due by Monday, Apr. 28, 4pm.

·
Project Proposal. A single paragraph describing your proposed
project, together with a list of relevant papers.

Due by **Friday, Mar. 21, 5pm**,
by email. Please discuss with Jing about your project before submitting the
proposal, and please do not wait until the last week.

·
Here is a (highly incomplete) list of candidate topics together
with one or two representative papers, updated gradually. Note that your
choices are by no means limited to those listed here: they are meant to give
you a starting point.

Ø Mechanism design in
single-parameter settings

A. Archer and E. Tardos. Truthful
Mechanisms for One-Parameter Agents. Proceedings of the 42nd IEEE symposium
on Foundations of Computer Science (FOCS’01), pages 482-491, 2001.

Ø Price of Anarchy

E. Koutsoupias
and C. H. Papadimitriou. Worst-case
equilibria. Proceedings of the 16th annual conference on Theoretical
Aspects of Computer Science (STACS’99), pages 404-413, 1999.

T. Roughgarden
and E. Tardos. How Bad is Selfish Routing? Journal of the ACM,
49(2):236-259, 2002.

Ø Ad Auctions

B. Edelman, M. Ostrovsky, and M. Schwarz. Internet
Advertising and the Generalized Second-Price Auction: Selling Billions of Dollars Worth of Keywords. American Economic Review
97(1), pp. 242-259, 2007.

S. Lahaie,
D. Pennock, A. Saberi, and
R. Vohra. In Algorithmic Game Theory, Chapter 28: Sponsored
search auctions. Pages 699-716. Cambridge University Press, 2007.

P. Dhangwatnotai.
Multi-keyword
sponsored search. 12th ACM conference on Electronic Commerce (EC 2011), pp.
91-100.

Ø Collusion in mechanism
design

J. Schummer.
Manipulation
through Bribes. J. of Economic Theory, 91(3):180-198, 2000.

J. Chen and S. Micali. Collusive
dominant-strategy truthfulness. J. of Economic Theory 147: 1300–1312, 2012.

Ø Rational proofs

P. Azar and S. Micali. Rational proofs. STOC 2012.

P. Azar and S. Micali. Super-Efficient
Rational Proofs. 14th ACM Conference on Electronic Commerce (EC 2013).

S. Guo, P. Hubacek, A. Rosen and M. Vald. Rational
Arguments: Single Round Delegation with Sublinear
Verification. ITCS 2014.

Ø Bayesian mechanism
design

R. B. Myerson. Optimal Auction Design.
Mathematics of Operations Research, Vol. 6, No. 1 (Feb., 1981), pp. 58-73.

J. Crémer
and R. P. McLean. Full
Extraction of the Surplus in Bayesian and Dominant Strategy Auctions. Econometrica, Vol. 56, No. 6 (Nov., 1988), pp. 1247-1257.

A. Ronen. On
Approximating Optimal Auctions. EC 2001.

P. Azar, J. Chen, and S.
Micali. Crowdsourced Bayesian Auctions. ITCS 2012.

·
The Foreword of the AGT book by Christos
Papadimitriou.

·
L. M. Ausubel and P. Milgrom. The
Lovely but Lonely Vickrey Auction. In P. Cramton, Y. Shoham and R.
Steinberg (eds), Combinatorial Auctions, MIT Press,
2006.

·
D. Lehmann, L.
I. O’Callaghan, and Y. Shoham. Truth
Revelation in Approximately Efficient Combinatorial Auctions. Journal of
the ACM (JACM), Vol. 49, Iss. 5, pages 577-602, Sep.
2002.

·
Tim Roughgarden’s lecture
notes on Myerson’s lemma.

·
A. Archer and E. Tardos. Truthful
Mechanisms for One-Parameter Agents. Proceedings of the 42nd IEEE symposium
on Foundations of Computer Science (FOCS’01), pages 482-491, 2001.

·
E. Maskin. Nash
Equilibrium and Welfare Optimality. The Review of Economic Studies, Vol.
66, No. 1, Special Issue: Contracts (Jan., 1999), pp. 23-38.

·
Tim Roughgarden’s lecture
notes on Price of Anarchy.

·
R. Paes Leme and É. Tardos. Pure
and Bayes-Nash Price of Anarchy for Generalized Second Price Auction. FOCS
2010.

·
R. B. Myerson. Optimal Auction Design.
Mathematics of Operations Research, Vol. 6, No. 1 (Feb., 1981), pp. 58-73.

·
P. Azar, J.
Chen, and S. Micali. Crowdsourced Bayesian Auctions. Innovations in
Theoretical Computer Science (ITCS), 2012.

·
A. Ronen. On
approximating optimal auctions. 3rd ACM Conference on Electronic Commerce,
pp. 11-17, 2001.

·
J. Chen and S.
Micali. Mechanism
Design with Set-Theoretic Beliefs. Symposium on Foundations of Computer
Science (FOCS), pp. 87-96, 2011.

"If
you have a physical, psychological, medical or learning disability that may
impact on your ability to carry out assigned course work, I would urge that you
contact the staff in the Disability Support
Services office (DSS), ECC Building (behind SAC), 632-6748/TDD. DSS will
review your concerns and determine, with you, what accommodations are necessary
and appropriate. All information and documentation of disability is confidential."

Students
who require assistance during emergency evacuation are encouraged to discuss
their needs with their professors and Disability Support Services. For
procedures and information go to this web site and search Fire Safety and Evacuation
and Disabilities.

Stony
Brook University expects students to respect the rights, privileges, and
property of other people. Faculty are required to report to the Office of
Judicial Affairs any disruptive behavior that interrupts their ability to
teach, compromises the safety of the learning environment, or inhibits
students' ability to learn.