CSE 691 Advanced Topics in Computer Science -- Computational Game Theory and Economics
Fall 2008
Schedule
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.
- Algorithmic Game Theory. Edited by Noam Nisan (Hebrew University),
Tim Roughgarden (Stanford), Éva Tardos (Cornell), and Vijay
V. Vazirani (Georgia Tech).
An electronic version of the book is freely available online (see Tim Roughgarden's webpage for
more info)
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.
Topics
- Game theory fundamentals: noncooperative game theory, classical game
representations, zero-sum and general-sum games, stochastic games,
solution concepts such as Nash and correlated equilibria, existence
theorems
- Basic concepts in mathematical economics: abstract economies, Fisher
and Arrow-Debreu models of competitive economies, general (market)
equilibria and the existence of equilibrium prices in exchange markets
- Compact representations of large-population games: graphical games,
potential games
- Graphical economies and the effect of network structure on market prices
- Computational complexity and algorithms for classical and modern
game-theoretic models
- Connections to artificial intelligence and probabilistic graphical
models (e.g., Bayesian and Markov networks) and inference methods
(e.g., belief propagation) for reasoning under uncertainty
- Learning in games: fictitious play, best-response (gradient)
dynamics, no-regret learning
- Evolutionary game theory: classical and network models
- Revealed preferences and learning games
- Mechanism design and combinatorial auctions
- Applications: network routing, network formation, interdependent
security, vaccination, computational biology, multi-agent systems,
(online) auctions, sponsored search
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.
Prerequisites
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.
Schedule
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)
- John Nash. Non-Cooperative Games. The Annals of Mathematics, Second Series, Vol. 54, No. 2 (Sep., 1951), pp. 286-295
Nash's original existence proof based on Brower's fixpoint theorem
- Kenneth J. Arrow and Gerard Debreu. Existence of an Equilibrium for a Competitive Economy. Econometrica, Vol. 22, No. 3 (Jul., 1954), pp. 265-290
Arrow and Debreu's proof of the existence of an equilibrium price in a competitive economy based on the concept of an abstract economy, which is a genralization of a normal-form game, and a corresponding generalization of Nash's result
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)
- Julia Robinson. An Iterative Method of Solving a Game. The Annals of Mathematics, Second Series, Vol. 54, No. 2 (Sep., 1951), pp. 296-301.
Robinson's proof that "fictitious play" converges to a Nash equilibrium in 2-player zero-sum games
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:
- Mohammad - PPAD-completeness and Nash Eq. Computation
- Lokesh - Cryptography & Game Theory
- Abhinav - Interdependent Security Games
- Dengpan - Routing Games
Fri Nov 21
DUE: Reports for Fri Nov 14 (last week) topic presentations
Topic Presentations:
- Pralhad - Distributed Algorithmic Mechanism Design
- Utpal - Game Theory in Wireless Networks
- Irina - Peer-to-Peer File Sharing Games
- Dmytro - Sponsored Search
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:
- Srivani - Computational Evolutionary Game Theory
- Sangwoo - ???
- Mark - ???
Mon Dec 8
DUE: Project Progress Report 2
Fri Dec 12
DUE: Reports for Fri Dec 5 (last week) topic presentations
Project Presentations: TBD