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 10-11:20
Venue: Room 4480 (lifts 25-26)
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 106-113. Presentation Slides (pdf) |
|
Zhang, Yan |
Vickrey Prices and Shortest Paths: What Is an Edge Worth? John Hershberger, Subhash Suri. FOCS 2001, Pages 252-259. (Erratum in FOCS 2002, Page 809.) Presentation Slides (ppt) |
|
Xu, Jing |
Near-Optimal Network Design with Selfish Agents. Elliot Anshelevich, Anirban Dasgupta, Eva Tardos, Tom Wexler. STOC 2003, Pages 511-520. Presentation Slides (ppt) |
|
Jian Xia |
On a Network Creation Game. Alex Fabrikant, Ankur Luthra, Elitza Maneva, Christos H. Papadimitriou, Scott Shenker. PODC 2003, Pages 347-351. Presentation Slides (pdf) |
|
Wang, Yajun |
How Bad is Selfish Routing? Tim Roughgarden, Eva Tardos. Journal of the ACM, 49(2): 236-259, 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 57-66. Presentation Slides (pdf) |
|
Xu, Jing |
Complexity Results about Nash Equilibria. Vincent Conitzer, Tuomas Sandholm. IJCAI 2003, Pages 765-771. Presentation Slides (ppt) |
|
|
No Class (mid-semester break) |
|
|
No Class (mid-semester break) |
Friday, April 21 Note this is during theory seminar slot Room 3464 Lifts 25-26 |
Mak, Wah Sung Vincent |
Rational Learning Leads to Nash Equilibrium. Ehud Kalai, Ehud Lehrer. Econometrica, 61(5): 1019-1045, 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): 129-150, 2003. Presentation Slides (ppt) |
|
Leung, Yiu Cho |
Computing Equilibria in Multi-Player Games. Christos H. Papadimitriou, Tim Roughgarden. SODA 2005, Pages 82-91. Presentation Slides (pdf) |
Friday, April 28 Note this is during theory seminar slot Room 3464 Lifts 25-26 |
Li, Xi |
Competitive Analysis of Incentive Compatible On-Line Auctions. Ron Lavi, Noam Nisan Theoretical Computer Science, 310(1-3): 159-180, 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 1050-1059. 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): 284-309, 2003. Presentation Slides (pdf) (version for printing) |
Friday, May 12 Note this is during theory seminar slot Room 3464 Lifts 25-26 |
Zhang, Yan | Sharing the Cost of Multicast Transmissions. Joan Feigenbaum, Christos H. Papadimitriou, Scott Shenker. Journal of Computer and System Sciences, 63(1): 21-41, 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): 284-309, 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 74-81. Presentation Slides (pdf) |
9:00-10: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, Ming-Yang Kao. In E. J. Kontoghiorghes, B. Rustem, S. Siokos (Eds), Applied Optimization 74: Computational Methods in Decision-Making, Economics and Finance, Kluwer Academic Publishers, 2002, Pages 455-479. 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.