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 closedbook.
· Notice
the place of the class on Oct 20, 45 in CSIC 3117, 5:207 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 ``incentiveaware 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 wellpoised 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, revenuemaximizing, 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 nonatomic 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: PPADcompleteness 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 

Fixedparametertractable
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 multiplechoice
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 PrimalDual
Algorithms for Maximizing AdAuctions 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/gm08adwords.pdf
·
Allocating
Online Advertising Space with Unreliable Estimates
Mohammad Mahdian, Hamid Nazerzadeh, Amin Saberi. EC 2007.
www.stanford.edu/~saberi/hamidadwords.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 11/e
J. Feldman, A. Mehta, S. Muthukrishnan, V. Mirrokni. FOCS 2009
http://arxiv.org/abs/0905.4100
·
Stochastic
Models for Budget Optimization in SearchBased 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
·
Noncooperative
multicast and facility location games.
Chandra Chekuri, Julia Chuzhoy, Liane LewinEytan, 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/focs04game.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/enus/projects/databaseprivacy/dwork.pdf
7.
Price of
Total Anarchy.
·
Intrinsic
robustness of the price of anarchy.
Tim Roughgarden. STOC 2009
http://wwwcs.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://wwwmath.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. BestReply Mechanisms.
·
Sink Equilibria and Convergence
M. Goemans, V. Mirrokni, A. Vetta, FOCS 2005
http://people.csail.mit.edu/mirrokni/sink.ps
·
BestReply
Mechanisms
Nisan, Schapira, Zohar. INFORMS 2007.
http://www.cs.huji.ac.il/~mikesch/bestreplyMDshort.pdf
·
Asynchronous
Best Reply Dynamics
Nisan, Schapira, Zohar. WINE 2008.
http://www.cs.huji.ac.il/~mikesch/wine2008short_submission_38.pdf
11. Fixedparametertractable 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/krausfpt.pdf
·
On the
computational complexity of coalitional resource games
Wooldridge and Dunne
Artificial Intelligence 2006
http://www.cs.umd.edu/~hajiagha/AGT10/wooldridgecrg.pdf
·
Parameterizing
the winner determination problem for combinatorial auctions
D. Loker and K. Larson, AAMAS 2010
http://www.cs.umd.edu/~hajiagha/AGT10/fptgametheory.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 email 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 4pm7pm 
Location: 
CSI 2118 
Office hours: 
By appointment via email OR the hour immediately
following class. 
Office: 
A.V. Williams Bldg., Room 3249 
Phone: 
3014052741 
Email: 
The first 8 letters of instructor’s last name
(AT) cs (DOT) umd
(DOT) edu 
TA: 
None 