Instructor:
Mordecai Golin
golin@cs.ust.hk
Course description:
A quick and dirty introduction to the basic concepts of modern game theory
followed by a survey of recent work in computer science that uses game theory.
The course will start with the instructor giving two or three introductory lessons on the basics of game theory. The remainder of the course will be students presenting papers. All students will be expected to
A list of which papers have been chosen for presentation by which students is available here.
Similar Courses:
A list of similar courses is available here.
We've mirrored a lot of their web pages + notes
here.
Class schedule:
Time: Monday and Wednesday 1011:20
Venue: Room 4480 (lifts 2526)
Date 
Presenter 
Topic 

M. J. Golin 
Introduction to Class 

M. J. Golin 
Introduction to game theory & Nash Equilibria 

M. J. Golin 
Continuation of Introduction 


No Class 


No Class 

Leung, Yiu Cho 


Mak, Wah Sung Vincent 


Zhou, Zhen 
Oblivious AQM and Nash Equilibria. Debojyoti Dutta, Ashish Goel, John Heidemann. INFOCOM 2003, Pages 106113. Presentation Slides (pdf) 

Zhang, Yan 
Vickrey Prices and Shortest Paths: What Is an Edge Worth? John Hershberger, Subhash Suri. FOCS 2001, Pages 252259. (Erratum in FOCS 2002, Page 809.) Presentation Slides (ppt) 

Xu, Jing 
NearOptimal Network Design with Selfish Agents. Elliot Anshelevich, Anirban Dasgupta, Eva Tardos, Tom Wexler. STOC 2003, Pages 511520. Presentation Slides (ppt) 

Jian Xia 
On a Network Creation Game. Alex Fabrikant, Ankur Luthra, Elitza Maneva, Christos H. Papadimitriou, Scott Shenker. PODC 2003, Pages 347351. Presentation Slides (pdf) 

Wang, Yajun 
How Bad is Selfish Routing? Tim Roughgarden, Eva Tardos. Journal of the ACM, 49(2): 236259, 2002 Presentation Slides (pdf) 


No Class (Ching Ming) 

Wang, Yajun 
The Price of Routing Unsplittable Flow. Baruch Awerbuch, Yossi Azar, Amir Epstein. STOC 2005, Pages 5766. Presentation Slides (pdf) 

Xu, Jing 
Complexity Results about Nash Equilibria. Vincent Conitzer, Tuomas Sandholm. IJCAI 2003, Pages 765771. Presentation Slides (ppt) 


No Class (midsemester break) 


No Class (midsemester break) 
Friday, April 21 Note this is during theory seminar slot Room 3464 Lifts 2526 
Mak, Wah Sung Vincent 
Rational Learning Leads to Nash Equilibrium. Ehud Kalai, Ehud Lehrer. Econometrica, 61(5): 10191045, 1993. Presentation Slides (ppt) 

Yang, Yin 
An Approximate Truthful Mechanism for Combinatorial Auctions with Single Parameter Agents. Aaron Archer, Christos Papadimitriou, Kunal Talwar, Eva Tardos. Internet Mathematics, 1(2): 129150, 2003. Presentation Slides (ppt) 

Leung, Yiu Cho 
Computing Equilibria in MultiPlayer Games. Christos H. Papadimitriou, Tim Roughgarden. SODA 2005, Pages 8291. Presentation Slides (pdf) 
Friday, April 28 Note this is during theory seminar slot Room 3464 Lifts 2526 
Li, Xi 
Competitive Analysis of Incentive Compatible OnLine Auctions. Ron Lavi, Noam Nisan Theoretical Computer Science, 310(13): 159180, 2004 Presentation Slides (pdf) 


No Class (Labor Day) 

Zhou, Zhen 
Fair and Efficient Router Congestion Control. Xiaojie Gao, Kamal Jain, Leonard J. Schulman. SODA 2004, Pages 10501059. Presentation Slides (pdf) 

Jian Xia 

Wed May 10, 2006 
James Lee  Combinatorial Auctions: A Survey (Part I). Sven de Vries, Rakesh V. Vohra. INFORMS Journal on Computing, 15(3): 284309, 2003. Presentation Slides (pdf) (version for printing) 
Friday, May 12 Note this is during theory seminar slot Room 3464 Lifts 2526 
Zhang, Yan  Sharing the Cost of Multicast Transmissions. Joan Feigenbaum, Christos H. Papadimitriou, Scott Shenker. Journal of Computer and System Sciences, 63(1): 2141, 2001. Presentation Slides (ppt) 
Mon May 15, 2006 
James Lee  Combinatorial Auctions: A Survey (Part II). Sven de Vries, Rakesh V. Vohra. INFORMS Journal on Computing, 15(3): 284309, 2003. Presentation Slides (pdf) (version for printing) 
Wed May 17, 2006 
Li, Xi  Iterative Combinatorial Auctions: Theory and Practice. David C. Parkes, Lyle H. Ungar. AAAI 2000, Pages 7481. Presentation Slides (pdf) 
9:0010:30 Thursday, May 18 This is a makeup class. Venue is the usual room, 4480. 
Yang, Yin  Opportunity Cost Algorithms for Combinatorial Auctions. Karhan Akcoglu, James Aspnes, Bhaskar DasGupta, MingYang Kao. In E. J. Kontoghiorghes, B. Rustem, S. Siokos (Eds), Applied Optimization 74: Computational Methods in DecisionMaking, Economics and Finance, Kluwer Academic Publishers, 2002, Pages 455479. Presentation Slides (ppt) 
Choosing papers:
Each student should choose two papers to present.
The papers can be chosen from the papers lists of the courses
here (see also the mirrors we have of many
of the courses + a combined paper list
here)
or can be something else that you've found that you think is appropriate.
I will maintain another page here listing possible
papers that are not on any of the course lists.