CSE 691 Advanced Topics in Computer Science -- Computational Game Theory and Economics

Fall 2008



Section Information

Date: Friday
Time: 9:00am-12:00pm
Room: P124 (Physics Bldg)

Instructor Information

Instructor: Luis Ortiz
Email: le [last name] at cs followed by .sunysb and finally .edu
Office: 2313-c
Phone: (631) 632-1805
Office Hours: To be determined; for now, by appointment (please e-mail me in advance)

Course Description

Computational game theory and economics is an emerging yet quickly developing area at the interface of computer science and economics. The area seeks to build on classical results in game theory to provide practical models and effective algorithms better suited to study and solve problems in large complex systems in modern society. Of major interest are compact models and efficient algorithms to understand and predict the complex global behavior that emerges from local interactions. Auctions, the Internet, social networks, computational biology, and interdependent security are some example application domains.

Course Objectives

This course provides an introduction to computational game theory (and its applications) and study the latest developments in this recent research area. A major objective of the course is to identify open problems and opportunities for future research, as well as potential, novel application domains.

Course Organization

The course format involves formal lectures, discussions and presentations, some led by the students themselves. Classical and recent research papers, possibly supplemented with textbook readings in the area, represent a large portion of the reading material for the course. The following recently published book, which serves as a survey of the area, is also required.

Course Project

Students complete a research project on a relevant topic. The specific problem requires the instructor's approval. The project can be theoretical or experimental in nature. Ideally, the problem will address an open research question and the report will lead to a submission to a scientific conference. Students periodically submit progress reports to monitor the project's development. Students give a presentation and submit a written report on the results of the project by the end of the course.

Student Evaluations

The instructor will base the evaluations of the students performance on their level of participation during the discussions, and the quality of their project's presentation and final written report.


NOTE: The list of topics, as well as the emphasis on each topic, will likely vary depending on the background and interests of the course participants.


No prior knowledge of game theory or economics is needed or expected. Some knowledge of basic probability and statistics is desirable, but also not needed or expected. However, some knowledge of basic computational concepts will be assumed (e.g., basic techniques in algorithms, such as dynamic programming, runtime analysis and basic concepts in computational complexity such as NP-completeness). Interested students without such a computational background are still welcomed and encouraged to register for the course but should contact the instructor to get a consent.


Wed Sep 3

Organizational Meeting 6:30pm-7:45pm in Computer Science Bldg. Rm 2311 (Wireless Seminar Room)

Fri Sep 5

Introduction to Game Theory and Computational Issues

Textbook Reading: Ch. 1, Sect. 1.1-1.3.4

Fri Sep 12

Introduction to Game Theory and Computational Issues (Continued)

Textboook Reading: Ch. 1, Sect. 1.3.5-1.8

Paper Reading: (available via Stony Brook University Library E-journal access)

Fri Sep 19

Computing Nash Equilibrium in 2-Player Games

Textboook Reading: Sect. 2.1-2.6 and Ch. 3

Recommended Reading:

Fri Sep 26

Computing Market Equilibria

Textbook Reading: Ch. 5-6

Fri Oct 3

Learning in Games

Textbook Reading: Ch. 4

Recommended Reading: (available via Stony Brook University Library E-journal access)

Fri Oct 10

Graphical Games

Textbook Reading: Ch. 7 and Sect. 2.7

Fri Oct 17

Graphical economies and social networks

Paper reading:

Fri Oct 24

Introduction to Mechanism Design

Textbook Reading: Ch. 9

Fri Oct 31

Introduction to the Inefficiency of Equilibria

Textbook Reading: Ch. 17

Fri Nov 7

Applications: Interdependent Security and Protein-DNA Binding

Fri Nov 14

Topic Presentations:

Fri Nov 21

DUE: Reports for Fri Nov 14 (last week) topic presentations

Topic Presentations:

Mon Nov 24

DUE: Project Progress Report 1

Fri Nov 28

Thanksgiving Break: No Meeting!

Mon Dec 1

DUE: Reports for Fri Nov 21 topic presentations

Fri Dec 5

Topic Presentations:

Mon Dec 8

DUE: Project Progress Report 2

Fri Dec 12

DUE: Reports for Fri Dec 5 (last week) topic presentations

Project Presentations: TBD