CMSC858F: Algorithmic Game Theory, Spring 2014


Instructor: Mohammad T. HajiAghayi


Latest Announcements (Last updated 03/23/14)

·      Notice the exam date of May 1, 2014 (Thu), 5-7pm in AVW 3258.

·      Topics of the projects should be checked with the instructor and finalized by Feb 28, 2014

·      See the course agenda

·         First lecture on January 28, 2014 at CSI 2118.

·        Templates .tex .sty to scribe.



·      Homework 3 due April 18, 4pm in my mailbox of the first floor of A.V. Williams. Solutions.

·      Homework 2 due April 4, 4pm in my mailbox of the first floor of A.V. Williams. Solutions.

·      Homework 1 due Feb 27 in the class. Solutions.


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.


Course Agenda:


            See the course agenda.

Main Reference Book:


Algorithmic Game Theory, edited by Nisan, Roughgarden, Tardos, and Vazirani, Cambridge University Press, 2007.

Schedule Material in order (see the references below):


01/28/2014: Review of course description, review of basic game theory and equilibrium concepts.


              Scanned handwritten notes

              Scribe notes by students

_______: Price of anarchy for selfish non-atomic routing games.

              Scanned handwritten notes

              Scribe notes by students

_______: Smooth games and price of anarchy

              Scanned handwritten notes

              Survey by Tim Roughgarden

_______: Market Clearing and Applications e.g. in wireless networks.

              Scanned handwritten notes and slides

              Scribe notes by students

_______: Interdomain routing and BGP

              Scanned handwritten notes

              Scribe notes by students

_______: VCG and combinatorial auctions

              Scanned handwritten notes

              Scribe notes by students

_______: Cooperative game theory: network bargaining games

               Scanned handwritten notes and slides

               Scribe notes by students

_______: Online auctions and Secretary Problem

              Slides and Scanned handwritten notes

              Scribe notes by students

_______:  Advertisement (Online) Auctions and Prophet Inequality Setting, Profit maximization, and frugality for auctions

              Slides and Scanned handwritten notes

              Scribe notes by students


Further Topics (As Reading Assignments):

_______: Adwords auctions and Online stochastic Ad allocation (cont’d)

              Scanned handwritten notes and slides

              Scribe notes by students

_______: Mechanism without money


_______: Convergence of equilibria


_______: The complexity of computing a Nash equilibrium: PPAD-completeness results

              Scanned handwritten notes

              Scribe notes y students

_______: network creation games

               Scanned handwritten notes and slides

               Scribe notes by students

05/06/2014: Paper and Project presentation

05/08/2014: Paper and Project presentation

05/13/2014: Paper and Project presentation see below (last day of the class)

              Written papers are due


List of projects for Spring 2014 (please see sample projects, scribe notes, and slides for the course in Fall 2010 here)

Project Topic

Group Members



Offline Optimal Ads Allocation in Social Network Advertising

Hui Miao and Peixin Gao



Maximizing the Spread of Influence Through a Social Network

Saeed Seddighin, Sina Dehghani and Milad Gholami



Combinatorial Optimization Games Arise in Social Networks

Rui Zhang and Mustafa Sahin



Data Clustering Through the Use of Competitive Game Mechanics

Ahmed Abdelkader, Ang Li, Nick Fung and Sohil Shah



Variational Inequalities for Computation of Equilibria

Melika Abolhasani and Anshul Sawant



Applications of Graph Matching: An Economic Approach

Reza Khani and Hossein Esfandiari



Rational Fairness in Crytpographic Protocol Design

Xiaong Fan and Kartik Nayak



Stochastic Matching on Hypergraphs

Amit Chavan, Srijan Kumar and Pan Xu




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





Though there is no official prerequisites for this course already passing a course in algorithms or economics is very important for this course. 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


See the course agenda for details.


            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


TuTh 2:00pm-3:15pm, Also Tu 4:50pm-6:00pm in CSI 3118


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