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.
Assignments
·
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)
|
Group
Members |
Scribe |
Slides |
|
|
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
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
Prerequisites
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
|
Instructor: |
|
|
Lectures: |
TuTh 2:00pm-3:15pm, Also Tu 4:50pm-6:00pm in CSI 3118 |
|
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 |
|
|
|