CMSC858F: Algorithmic Game Theory, Fall 2010
Instructor: Mohammad T. HajiAghayi
Latest Announcements (Last updated 10/27/10)
· Notice the written project due date of Dec 08, 2010 in the class.
· Notice
the exam date on Nov 10, 2010 at class. The exam is closed-book.
· Notice
the place of the class on Oct 20, 4-5 in CSIC 3117, 5:20-7 in the regular class
(CSI 2118).
· The topics of the projects should be checked with the instructor and finalized by Sep 29, 2010
· Scribe notes should be submitted by the first Monday after the lecture.
· See
the updated course agenda
· First
lecture on September 1, 2010 at CSI 2118.
· Templates
.tex .sty to scribe.
Course Description
Mechanism Design in particular Algorithmic Game Theory, which can be viewed as ``incentive-aware algorithm design'', have become an increasingly important part of (theoretical) computer science in recent years. Recent results show a strong relation between computer science (esp. networking) and economics (esp. game theory), and techniques from each seem well-poised to help with key problems of the other. My first goal in this course is to study these connections which produce powerful mechanisms for adaptive and networked environments and several other applied areas, and improve the experience of users of the Web and internet. To this end, the course would be a broad survey of topics such as: algorithmic mechanism design; auctions (efficient, revenue-maximizing, sponsored search, etc.); congestion and potential games; cost sharing; existence, computation, and learning of equilibria; game theory in the Internet; network games; price of anarchy; selfish routing, etc.
Main Reference Book:
Algorithmic
Game Theory, edited by Nisan, Roughgarden, Tardos, and Vazirani, Cambridge
University Press, 2007.
Detailed Schedule (see the references below):
09/01/10: Review of course
description, review of basic game theory and equilibrium concepts.
Scanned handwritten notes
Scribe notes by students
09/08/10: Price of anarchy for selfish non-atomic routing games.
Scanned handwritten notes
Scribe notes by
students
09/015/10: Market Clearing and Applications e.g. in wireless
networks.
Scanned handwritten notes
and
slides
Scribe notes by
students
09/022/10: Auctions: classical stuff, single item first
price/second price, VCG auctions, and combinatorial auctions.
Scanned handwritten notes
Scribe notes by
students
09/29/10: Profit maximization and frugality for auctions
Scanned handwritten notes
Scribe notes by
students
10/06/10: Profit maximization (cont’d), Adwords
auctions, Mechanism without money
Scanned handwritten notes
and slides
Scribe notes by
students
10/13/10: Secretary problem, online
auctions
Scanned handwritten notes
and slides
Scribe notes by
students
10/20/10: Guest Lecturer: Vahab
Mirrokni,
Online stochastic Ad allocation, convergence of equilibria
10/27/10: The complexity of computing a Nash
equilibrium: PPAD-completeness results
Scanned handwritten notes
Scribe notes by
students
11/03/10: Interdomain routing and BGP
Scanned handwritten notes
Scribe notes by
students
11/17/10: Cooperative game theory, network bargaining games,
network creation games
Scanned handwritten notes
and slides
Scribe notes by
students
11/24/10: Thanksgiving, No Class
12/1/10: Paper and Project presentation see below
12/8/10: Paper and Project presentation see below (last
day of the class)
Written papers are due
Projects
List of
projects
|
Project Topic |
Group Members |
Scribe |
Slides |
|
12/1/2010 |
|||
|
Multicast and
Network Formation Games |
Ioana Bercea |
||
|
Fixed-parameter-tractable
Algorithms and Game Theory |
Yuk Hei Chan, Rajesh Chitnis, Kanthi Kiran Sarpatwar |
||
|
Connections
between Privacy and Economics |
Hyoungtae Cho, Jay Pujara, Naomi Utgoff |
||
|
12/8/2010 |
|||
|
Differential
Privacy via Mechanism Design |
Adam Groce, Ateeq Sharfuddin, Aishwarya Thiruvengadam |
||
|
Price of Total
Anarchy & Online/Offline Adwords Matching |
Vahid Liaghat, Barna Saha |
||
Potential Project
Topics:
1. Further Secretary Problems and Their
Applications.
·
Matroid Secretary
Problem in the Random Assignment Model
José A. Soto
http://arxiv.org/abs/1007.2152
·
Matroids, secretary
problems, and online mechanisms
M Babaioff, N Immorlica, R Kleinberg. SODA 2007.
http://people.ischool.berkeley.edu/~moshe/matsec.pdf
·
Secretary
problems: Weights and discounts
M Babaioff, M Dinitz, A Gupta, N Immorlica, K Talwar. SODA 2009.
http://zeno.siam.org/proceedings/soda/2009/SODA09_135_babaioffm.pdf
·
A multiple-choice
secretary algorithm with applications to online auctions
R. Kleinberg. SODA 2005.
http://www.cs.ucla.edu/~awm/cs289/MultSec.pdf
· Improved Algorithms and Analysis for Secretary Problems and Generalizations
M Ajtai, N Megiddo, O Waarts. FOCS 1995.
http://theory.stanford.edu/~megiddo/pdf/secrfin.pdf
2.
Online /
Offline Adwords Matching.
·
Online Primal-Dual
Algorithms for Maximizing Ad-Auctions Revenue
Niv Buchbinder, Kamal Jain, Joseph Naor. ESA 2007
·
AdWords and
generalized online matching
Aranyak Mehta, Amin Saberi, Umesh V. Vazirani, Vijay V. Vazirani. JACM 2007.
http://www.stanford.edu/~saberi/adwords.pdf
· Online budgeted matching in random input models with applications to Adwords
Gagan Goel, Aranyak Mehta. SODA 2008.
http://www.cc.gatech.edu/~aranyak/docs/gm08-adwords.pdf
·
Allocating
Online Advertising Space with Unreliable Estimates
Mohammad Mahdian, Hamid Nazerzadeh, Amin Saberi. EC 2007.
www.stanford.edu/~saberi/hamid-adwords.pdf
·
Improved
Approximation Algorithms for Budgeted Allocations
Y Azar, B Birnbaum, AR Karlin, C Mathieu. ICALP 2008.
http://www.cs.washington.edu/homes/birnbaum/budgetedallocation.pdf
3.
Stochastic
Optimization in Ads.
·
Online
Stochastic Matching: Beating 1-1/e
J. Feldman, A. Mehta, S. Muthukrishnan, V. Mirrokni. FOCS 2009
http://arxiv.org/abs/0905.4100
·
Stochastic
Models for Budget Optimization in Search-Based Advertising
Muthukrishnan, Pal and Svitkina. WINE 2007.
www2007.org/workshops/paper_80.pdf
·
The Ratio
Index for Budgeted Learning with Applications
A Goel, S Khanna, B Null. SODA 2009.
http://www.stanford.edu/%7Eashishg/papers/budgeted_ratio.pdf
·
Approximation
algorithms for budgeted learning problems
Sudipto Guha, Kamesh Munagala. STOC 2007.
http://portal.acm.org/citation.cfm?id=1250807&dl=&coll=
·
Topics in
Stochastic Optimization
Ashish Goel
http://www.stanford.edu/~ashishg/msande325_09/
·
Algorithmic
Decision Theory and Bayesian Optimization
Sudipto Guha
http://www.cis.upenn.edu/~sudipto/cis677_09.html
4.
Multicast
and Network Formation Games.
·
Online
Multicast
Online multicast with egalitarian cost sharing.
Moses Charikar, Howard J. Karloff, Claire Mathieu, Joseph Naor, Michael E. Saks, SPAA, 2008
http://www.cs.brown.edu/~claire/Publis/spaa08.pdf
·
Non-cooperative
multicast and facility location games.
Chandra Chekuri, Julia Chuzhoy, Liane Lewin-Eytan, Joseph Naor, Ariel Orda, EC, 2006.
http://ttic.uchicago.edu/~cjulia/papers/ec.pdf
·
The Price
of Stability for Network Design with Fair Cost Allocation.
Elliot Anshelevich, Anirban Dasgupta, Jon M. Kleinberg, Iva Tardos, Tom Wexler, Tim Roughgarden, FOCS, 2004
http://www.cs.cornell.edu/home/kleinber/focs04-game.pdf
5.
Topics in
Automated Mechanism Design and Online Auctions.
· Automated mechanism design: A new application area for search algorithms.
Thomas Sandholm, International Conference on Principles and Practice of Constraint Programming, 2003.
www.cs.cmu.edu/~sandholm/amd_overview.cp03.pdf
·
Automated
online mechanism design and Prophet inequalities.
M.T. Hajiaghayi, R.D. Kleinberg, T. Sandholm, AAAI, 2007.
http://www.cs.cmu.edu/~sandholm/www/prophet.aaai07.pdf
6.
Differential
Privacy via Mechanism Design.
·
Differential
Privacy via Mechanism Design
Frank McSherry, Kunal Talwar. FOCS 2007.
http://research.microsoft.com/pubs/65075/mdviadp.pdf
·
Differential
Privacy.
Cynthia Dwork.
research.microsoft.com/en-us/projects/databaseprivacy/dwork.pdf
7.
Price of
Total Anarchy.
·
Intrinsic
robustness of the price of anarchy.
Tim Roughgarden. STOC 2009
http://www-cs.stanford.edu/~tim/papers/robust.pdf
·
Regret
minimization and the price of total anarchy.
A. Blum, M. T. Hajiaghayi, K. Ligett, and A. Roth. STOC 2008.
http://www-math.mit.edu/~hajiagha/regretprice
8. Oscillations in BGP.
·
The
complexity of game dynamics: BGP oscillations, sink equlibria,
and beyond
Alex Fabrikant and Christos Papadimitriou. SODA 2008.
http://www.cs.berkeley.edu/~alexf/papers/fp08.pdf
9.
Connections
between Privacy and Economics.
·
Congestion
games with malicious players
M. Babaioff, R. Kleinberg, and C. Papadimitriou
http://www.cs.cornell.edu/~rdk/papers/ec197.pdf
·
On the
value of private information
J. Kleinberg, C. H. Papadimitriou, P. Raghavan. TARK 2001.
http://www.cs.berkeley.edu/~christos/tark.ps
10. Best-Reply Mechanisms.
·
Sink Equilibria and Convergence
M. Goemans, V. Mirrokni, A. Vetta, FOCS 2005
http://people.csail.mit.edu/mirrokni/sink.ps
·
Best-Reply
Mechanisms
Nisan, Schapira, Zohar. INFORMS 2007.
http://www.cs.huji.ac.il/~mikesch/best-reply-MD-short.pdf
·
Asynchronous
Best Reply Dynamics
Nisan, Schapira, Zohar. WINE 2008.
http://www.cs.huji.ac.il/~mikesch/wine2008short_submission_38.pdf
11. Fixed-parameter-tractable Algorithms and Game Theory.
·
Easy and
Hard Coalition Resource Game Formation problems – A parameterized complexity
analysis
Shrot, Aumann and Kraus
AAMAS 2009
http://www.cs.umd.edu/~hajiagha/AGT10/kraus-fpt.pdf
·
On the
computational complexity of coalitional resource games
Wooldridge and Dunne
Artificial Intelligence 2006
http://www.cs.umd.edu/~hajiagha/AGT10/wooldridge-crg.pdf
·
Parameterizing
the winner determination problem for combinatorial auctions
D. Loker and K. Larson, AAMAS 2010
http://www.cs.umd.edu/~hajiagha/AGT10/fpt-gametheory.pdf
·
An
investigation of representations of combinatorial auctions
D. Loker and K. Larson, AAMAS 2010
http://www.cs.umd.edu/~hajiagha/AGT10/representignauctions.pdf
Tentative Course Topics and
References:
See a similar course taught by the same instructor at Rutgers (more references might be added later).
Prerequisites
No specific prerequisites. Already passing a course in algorithms, economics, or networking can be quite helpful. If you are unsure of whether you have sufficient background for this course or not, please e-mail the instructor in the first week of the class or before.
Tentative Grading &
Evaluation
Each student will be expected to scribe 1 lecture (10%) and participate in class discussions (10%). There will be two homeworks (7.5% each), one exam (20%), a paper presentation in the class (15%) and a (possibly collaborative) project and its brief presentation in the class (30%). A strong project can potentially compensate the low grades in other parts. Details about the project and ideas will be given in the second week of the class, though the general ideas can be seen from the course topics in here.
Other Resources (from here)
Tips for good technical writing
• The elements of style by William Strunk Jr. and E. B. White (follow the "External links" at the bottom of this page for online copies of this book).
• Writing a technical paper, by Professor Michael Ernst.
• Tips for writing technical papers, by Professor Jennifer Widom.
• Writing suggestions, by Professor Barton Miller.
• How to write a dissertation, by Professor Douglas Comer (most of the content on this page applies to all forms of technical writing).
Tips for effective
presentation
• Giving a technical talk, by Professor Michael Ernst.
• Tips for a good conference talk, by Professor Jennifer Widom.
• Oral presentation advice, by Professor Mark Hill.
General Information
|
Instructor:
|
|
|
Lectures: |
Wed 4pm-7pm |
|
Location: |
CSI 2118 |
|
Office hours: |
By appointment via e-mail OR the hour immediately
following class. |
|
Office: |
A.V. Williams Bldg., Room 3249 |
|
Phone: |
301-405-2741 |
|
Email: |
The first 8 letters of instructor’s last name
(AT) cs (DOT) umd
(DOT) edu |
|
TA: |
None |