CSCI 599, Fall 2010


This is a research oriented course in theoretical computer science and its interdisciplinary applications. This year, I will focus more on computational game theory and computational economics. 

Professor ShangHua Teng 
No TA is assignged for this class 

Textbook 
Algorithmic Game Theory Research papers 
Lectures 

Grades 
Term paper, notes taking, class presentation

Exams 
no exam 
Homework 
Term paper and class presentation 
Integrity 
Plagiarism and other antiintellectual behavior will be dealt with severely. This includes the possibility of failing the course or being expelled from the University. 
Lec# 
Date

Topic and/or Event  Reading  Notes 
1

8/25

Class organization:
Games and Optimization
Exchange Markets

the textbook Search on the Web "google Market Equilibrium" C. Papadimitriou "The Complexity of the Parity Argument and Other Inefficient proofs of Existence" (1991) "google Game Theory" K. J. Arrow and G. Debreu. "Existence of an equilibrium for a competitive economy". Econometrica 22:265290 (1954). "google Arrow, Debreu, McKenziey" 
pdf, latex 
2

9/1

Best response dynamics Graphs of best responses Types of games and equilibria Sinks in Potential games Fixed points Equilibria by chance 
the textbook Search on the Web "google Potential Games" Potential Games, D. Monderer, L. Shapley, 1994 "google Congestion Games" "google Scheduling Games" "google Nash equilibrium" Berthold Vocking, "Congestion Games: Optimization in Competition" 
pdf, latex 
3

9/8

Potential Games
Games of scheduling Congestion games Price of anarchy Coordination mechanisms 
the textbook Search on the Web Yossi Azar, Kamal Jain, Vahab Mirrokni: "(Almost) Optimal Coordination Mechanisms for Unrelated Machine Scheduling" "google Delaunay triangulation and flip algorithm" "google colation games" "google Price of Anarchy" R. W. Rosenthal. "A class of games possessing purestrategy Nash equilibria." Int. Journal of Game Theory, 2:6567, 1973. H. Ackermann, H. Roglin, and B. Vocking. "On the impact of combinatorial structure on congestion games." In FOCS, 613 622, 2006. 
pdf, Notes by Vasilis Natranos on cost sharing network routing game 
4

9/15

Price of anarchy Complexity of potential equilibrium: PLS
General Equilibrium Theorem

the textbook Search on the Web research papers "google Price of Anarchy" Elias Koutsoupias, Christos H. Papadimitriou "Worstcase equilibria". Computer Science Review 3(2): 6569, 2009. G. Christodoulou and E. Koutsoupias. "The price of anarchy of finite congestion games." STOC, pages 6773, Baltimore, MD,USA, 2224 May, 2005 Tim Roughgarden and Eva Tardos. "How Bad is Selfish Routing?", Journal of the ACM, 49(2):236259, March 2002. Tim Roughgarden, "Potential Functions and the Inefficiency of Equilibria", International Congress of Mathematicians, 2006.


5

9/22

Fixed Point Theorem
Sperner's Lemma Brouwer's Fixed Point Theorem Kakutani's Fixed Point Theorem 
the textbook Search on the Web research papers "google Sperner Lemma" "google Brouwer Fixed Point" "google Kakutani Fixed Point" 
pdf, latex 
6

9/29

Equilibrium Theorem
Nash's Equilibrium ArrowDebreu's Equilibrium Equilibrium in market with social influence 
the textbook Search on the Web research papers 

7

10/6

Auction and Mechanism Design  the textbook Search on the Web research papers 
pdf, latex 
8

10/13

Combinatorial Auction  the textbook Search on the Web research papers 

9

10/20

PPAD and the Complexity of Equilibrium Computation Guest lecture: by Xi Chen of Columbia University TwoPlayer Nash Equilibrium ArrowDebreu Equilibrium in markets with additively separable utilities 
the textbook Search on the Web research papers 
pdf, latex 
10

10/27

Revenuemaximizing auctions
Student Presentation 1:

the textbook Search on the Web research papers 

11

11/3

Student Presentation 3 Chakrit Yau: Game Theory and Emotion/Behavior (May move up to 10/27) Student Presentation 4 Joseph Bebel, Anand Narayanan, Henry Yuen: Sink equilibria and convergence (or better) Student Presentation 5 
the textbook Search on the Web research papers 

12

11/10

Student Presentation 6 Sasank Vijayan and Cheng Lu: Coordination mechanisms and potential games (congestion with time) Student Presentation 8 John Kim: Game theory in recreational games. Presentation 8 +1 PoAn 
the textbook Search on the Web research papers 

13

11/17

No Class due to travel  the textbook Search on the Web research papers 

14

11/24

No class  Happy Thanksgiving  
15

12/1

Student Presentation *:
Sumit Agarwal: Maximal Seller Profit with Minimal Buyer Regret in a Competitive Economy (may move up) Student Presentation *: Rachel Cummings and Mahyar Salek: Student Presentation * Arash Saber: Graphical Games 
the textbook Search on the Web research papers 

15

12/3

Place: SAL 222 (Notice the new classroom)
Student Presentation *:

the textbook Search on the Web research papers 