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

              slides1 and slides2

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/10/10: Closed book exam in the class

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




List of projects

Project Topic

Group Members




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




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

·         Matroids, secretary problems, and online mechanisms

M Babaioff, N Immorlica, R Kleinberg. SODA 2007.

·         Secretary problems: Weights and discounts

M Babaioff, M Dinitz, A Gupta, N Immorlica, K Talwar. SODA 2009.

·         A multiple-choice secretary algorithm with applications to online auctions

R. Kleinberg. SODA 2005.

·         Improved Algorithms and Analysis for Secretary Problems and Generalizations

M Ajtai, N Megiddo, O Waarts. FOCS 1995.


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.

·         Online budgeted matching in random input models with applications to Adwords

Gagan Goel, Aranyak Mehta. SODA 2008.

·         Allocating Online Advertising Space with Unreliable Estimates

Mohammad Mahdian, Hamid Nazerzadeh, Amin Saberi. EC 2007.

·         Improved Approximation Algorithms for Budgeted Allocations

Y Azar, B Birnbaum, AR Karlin, C Mathieu. ICALP 2008.


3.      Stochastic Optimization in Ads.

·         Online Stochastic Matching: Beating 1-1/e

J. Feldman, A. Mehta, S. Muthukrishnan, V. Mirrokni. FOCS 2009

·         Stochastic Models for Budget Optimization in Search-Based Advertising

Muthukrishnan, Pal and Svitkina. WINE 2007.

·         The Ratio Index for Budgeted Learning with Applications

A Goel, S Khanna, B Null. SODA 2009.

·         Approximation algorithms for budgeted learning problems

Sudipto Guha, Kamesh Munagala. STOC 2007.

·         Topics in Stochastic Optimization

Ashish Goel

·         Algorithmic Decision Theory and Bayesian Optimization

Sudipto Guha


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

·         Non-cooperative multicast and facility location games.         

Chandra Chekuri, Julia Chuzhoy, Liane Lewin-Eytan, Joseph Naor, Ariel Orda, EC, 2006.

·         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


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.

·         Automated online mechanism design and Prophet inequalities.

M.T. Hajiaghayi, R.D. Kleinberg, T. Sandholm, AAAI, 2007.


6.      Differential Privacy via Mechanism Design.

·         Differential Privacy via Mechanism Design

Frank McSherry, Kunal Talwar. FOCS 2007.

·         Differential Privacy.

Cynthia Dwork.


7.      Price of Total Anarchy.

·         Intrinsic robustness of the price of anarchy.

Tim Roughgarden. STOC 2009

·         Regret minimization and the price of total anarchy.

A. Blum, M. T. Hajiaghayi, K. Ligett, and A. Roth. STOC 2008.


8.      Oscillations in BGP.

·         The complexity of game dynamics: BGP oscillations, sink equlibria, and beyond

Alex Fabrikant and Christos Papadimitriou. SODA 2008.


9.      Connections between Privacy and Economics.

·         Congestion games with malicious players

M. Babaioff, R. Kleinberg, and C. Papadimitriou

·         On the value of private information

J. Kleinberg, C. H. Papadimitriou, P. Raghavan. TARK 2001.


10.  Best-Reply Mechanisms.

·         Sink Equilibria and Convergence

M. Goemans, V. Mirrokni, A. Vetta, FOCS 2005                                 

·         Best-Reply Mechanisms

Nisan, Schapira, Zohar. INFORMS 2007.

·         Asynchronous Best Reply Dynamics

Nisan, Schapira, Zohar. WINE 2008.


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

·         On the computational complexity of coalitional resource games

Wooldridge and Dunne

Artificial Intelligence 2006

·         Parameterizing the winner determination problem for combinatorial auctions

D. Loker and K. Larson, AAMAS 2010

·         An investigation of representations of combinatorial auctions

D. Loker and K. Larson, AAMAS 2010


Tentative Course Topics and References:


See a similar course taught by the same instructor at Rutgers (more references might be added later).





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


Mohammad T. HajiAghayi


Wed 4pm-7pm


CSI 2118

Office hours:      

By appointment via e-mail OR the hour immediately following class.


A.V. Williams Bldg., Room 3249




The first 8 letters of instructor’s last name (AT) cs (DOT) umd (DOT)  edu