|
|
CSCI 599, Fall 2010
|
What's new?
Course Info:
|
|
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 Shang-Hua 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 anti-intellectual behavior will be dealt with severely. This includes the possibility of failing the course or being expelled from the University. |
Course Outline
(subject to changes)
| 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:265-290 (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 pure-strategy Nash equilibria." Int. Journal of Game Theory, 2:65-67, 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 "Worst-case equilibria". Computer Science Review 3(2): 65-69, 2009. G. Christodoulou and E. Koutsoupias. "The price of anarchy of finite congestion games." STOC, pages 67--73, Baltimore, MD,USA, 22--24 May, 2005 Tim Roughgarden and Eva Tardos. "How Bad is Selfish Routing?", Journal of the ACM, 49(2):236--259, 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 Arrow-Debreu'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 Two-Player Nash Equilibrium Arrow-Debreu Equilibrium in markets with additively separable utilities |
the textbook Search on the Web research papers |
pdf, latex |
|
10
|
10/27
|
Revenue-maximizing 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 Po-An |
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 |