COMP670O -- Spring 2006

Topics in Theory: Game Theoretic Applications in CS

 

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


Wed
Feb 22, 2006
 

M. J. Golin

Introduction to Class


Mon
Feb 27, 2006
 

M. J. Golin

Introduction to game theory & Nash Equilibria


Wed
March 1, 2006
 

M. J. Golin

Continuation of Introduction
The minmax theorem for 2-person zero-sum games
(From Linear Programming by Vasek Chvatal)


Mon
March 6, 2006
 

 

No Class


Wed
March 8, 2006
 

 

No Class


Mon
March 13, 2006
 

Leung, Yiu Cho


Graphical Models for Game Theory.
Michael Kearns, Michael L. Littman, Satinder Singh.
UAI 2001, Pages 253-260.
Presentation Slides (ps)
 


Wed
March 15, 2006
 

Mak, Wah Sung Vincent


Worst-Case Equilibria.
Elias Koutsoupias, Christos Papadimitriou.
STACS 1999, Pages 404-413.
Presentation Slides (ppt)
 


Mon
March 20, 2006
 

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


Wed
March 22, 2006
 

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)
 


Mon
March 27, 2006
 

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)
 


Wed
March 29, 2006
 

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)
 


Mon
April 3, 2006
 

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


Wed
April 5, 2006
 

 

No Class (Ching Ming)


Mon
April 10, 2006
 

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


Wed
April 12, 2006
 

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


Mon
April 17, 2006
 

 

No Class (mid-semester break)


Wed
April 19, 2006
 

 

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)
 


Mon
April 24, 2006
 

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)
 


Wed
April 26, 2006
 

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)
 


Mon
May 1, 2006
 

 

No Class (Labor Day)


Wed
May 3, 2006
 

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


Mon
May 8, 2006
 

Jian Xia


Query Incentive Networks.
Jon Kleinberg, Prabhakar Raghavan.
FOCS 2005, Pages 132-141.
Presentation Slides (pdf)
 


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.