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.

Staff

Instructor: Jing Chen

Office: 1416 Computer Science Building

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

Logistics

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.

Announcements

· 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.

Grading Policy

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 must acknowledge for each problem with whom you have discussed. If more than one student submits substantially the same writeup for a particular problem, or if there is some other evidence that the writeup you submit is not your own work, I will regard this as evidence that you are trying to get a higher grade without actually doing the required work and may choose either to make a corresponding deduction from your homework score or (in egregious cases) to pursue the matter as a case of academic dishonesty.

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

· 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.

Problem Sets

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

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

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

Projects

· 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.

Reading Materials

· 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.

Students with Disabilities

"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.

Critical Incident Management

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.