CSCI 7000: Topics in Algorithmic Game Theory

Spring 2020

University of Colorado, Boulder

Instructor: Bo Waggoner

Time: Mon/Wed/Fri 13:00 - 13:50
Room: HUMN 1B90

Course information and syllabus

News: Project guidelines page is here


This advanced graduate-level course will cover a number of topics at the interface of computer science and microeconomics, from a theoretical perspective. Examples of likely topics include online learning, mechanism design for approximate welfare and revenue maximization, information elicitation and aggregation, and/or computational social choice. The course will focus on reading papers and a final project.

Prerequisites: The course will have flexibility in allowing students to keep up at their own pace. Preprequisites encouraged, but not required, include multivariable calculus, linear algebra, probability, and analysis; and undergraduate algorithms and complexity theory. No economic prerequisites are assumed.

Resources and Links

To sign up for our class on NB, please paste these two strings together in your browser:


Mon, Jan 13

Intro to game theory


Osborne and Rubinstein Ch 1, Ch 2 - 2.4, and Ch 3 - 3.2; vN+M utility theorem discussed in class; risk aversion

Wed, Jan 15

Types of games - Bayesian, extensive form


Osborne and Rubinstein Ch 2.6-end, Ch 6 - 6.2

Fri, Jan 17

Computing equilibria - congestion games


Penn lecture notes on congestion games

Mon, Jan 20

MLK Day - No class

Wed, Jan 22

Computing equilibria - PPAD, Brouwer, etc


Roughgarden lecture notes

Fri, Jan 24

Generic sampling algorithm for NASH


Lipton, Markakis, Mehta. Playing Large Games Using Simple Strategies. Electronic Commerce (EC), 2003.

Mon, Jan 27

PPAD-hardness of NASH


Daskalakis, Goldberg, Papadimitriou. The Complexity of Computing a Nash Equilibrium. (circa 2006, simplified version).


Full version, Comm. of the ACM, 2009.

Wed, Jan 29

More on computational hardness, gadgets, circuits, etc

Fri, Jan 31

Hardness of NASH under ETH-like assumptions


Aviad Rubinstein. Settling the Complexity of Computing Approximate Two-Player Nash Equilibria. Foundations of Computer Science (FOCS), 2016.

Mon, Feb 03

Guest Presentation - Anson Kahng, Carnegie Mellon


Penn lecture notes on Voting as MLE.

Wed, Feb 05

Online learning - Polynomial Weights


Penn lecture notes on Polynomial Weights (skip page 1); Arora, Hazan, Kale. The Multiplicative Weights Update Method:A Meta-Algorithm and Applications. Theory of Comp., 2012 (survey paper).

Fri, Feb 07

Online Learning dynamics


Bailey, Gidel, Piliouras. Finite Regret and Cycles with Fixed Step-Size via Alternating Gradient Descent-Ascent. Working paper, 2019.

Mon, Feb 10

Zero-sum games


Freund, Shapire. Adaptive Game-Playing Using Multiplicative Weights. Games and Economic Behavior, 1999.


Penn lecture notes on Zero-Sum Games

Wed, Feb 12

Developments in solving zero-sum games

Fri, Feb 14

Online learning for game-solving


Brown, Lerer, Gross, Sandholm. Deep Counterfactual Regret Minimization. International Conference on Machine Learning (ICML), 2019.

Mon, Feb 17

Proper scoring rules


Brier. Verification of Forecasts Expressed in Terms of Probability. Monthly Weather Review, 1950.

Wed, Feb 19

Characterization of Proper Scoring Rules


Penn lecture notes on proper scoring rules

Fri, Feb 21

Proper Scoring Rules continued


Savage. Elicitation of Personal Probabilities and Expectations. Journal of the American Statistical Association, 1971.


Gneiting, Raftery. Strictly Proper Scoring Rules, Prediction,and Estimation. Journal of the American Statistical Association, 2007.

Mon, Feb 24

Prediction Markets


Hanson. Combinatorial Information Market Design. Information Systems Frontiers, 2003.


Wolfers, Zitzewitz. Prediction Markets. Journal of Economic Perspectives, 2004.

Wed, Feb 26

Further discussion on prediction markets; convex analysis basics

Fri, Feb 28

Computationally efficient prediction markets

Project proposal due


Abernethy, Chen, Wortman Vaughan. Efficient Market Making via Convex Optimization, and a Connection to Online Learning. Transactions on Economics and Computation, 2013.

Mon, Mar 02

Wagering mechanisms


Freeman, Pennock, Wortman Vaughan. An Equivalence Between Wagering and Fair-Division Mechanisms. AAAI, 2019.

Wed, Mar 04

Further discussion on wagering mechanisms and/or fair division

Fri, Mar 06

Information elicitation and online learning


Freeman, Pennock, Podimatra, Wortman Vaughan. No-Regret and Incentive-Compatible Online Learning. Working paper, 2019.


Poster summary

Mon, Mar 09

Persuasion and online decisionmaking


Immorlica, Mao, Slivkins, Wu. Bayesian Exploration with Heterogeneous Agents. The Web Conference (WWW), 2019.

Wed, Mar 11

Information elicitation without verification (a.k.a. peer prediction)


Miller, Resnick, Zeckhauser. Eliciting Informative Feedback: The Peer-Prediction Method. Management Science, 2005.

Fri, Mar 13

Frontiers of peer prediction


Kong. Dominantly Truthful Multi-Task Peer Prediction with a Constant Number of Tasks. Symposium on Discrete Algorithms (SODA), 2020.

Mon, Mar 16

Decision markets


Hanson "futarchy" post and: Teschner, Rothschild, Gimpel. Manipulation in Conditional Decision Markets. Group Decision and Negotiation, 2017.

Wed, Mar 18

Prediction markets, governance, and/or blockchain

Fri, Mar 20

Decentralized Prediction Markets

Project progress report due


van Shreven, N. Goel, Faltings. Infochain: A Decentralized System for Truthful Information Elicitation. Working paper, 2019.

Mon, Mar 23

Spring break - no class

Wed, Mar 25

Spring break - no class

Fri, Mar 27

Spring break - no class

Mon, Mar 30

Mechanism design, "social welfare", and price of anarchy


Roughgarden, Syrgkanis, Tardos. The Price of Anarchy in Auctions. Journal of AI Research, 2017 (survey paper). Sections 1-2


Mechanism Design and Approximation book by Hartline

Wed, Apr 01

Smoothness arguments and price of anarchy


Roughgarden, Syrgkanis, Tardos. The Price of Anarchy in Auctions. Journal of AI Research, 2017 (survey paper). Sections 4-5

Fri, Apr 03

Mechanism design as group decisionmaking for welfare maximization

Project progress report due


Fotakis, Tsipras, Tzamos, Zampetakis. Efficient Money Burning in General Domains. Theory of Computing Systems, 2016.


Prof. Bo blog post on VCG

Mon, Apr 06

Revenue maximization


Roughgarden lecture notes on revenue maximization

Wed, Apr 08

More on Myerson: revelation principle, truthfulness characterization


Penn lecture notes on single-parameter domains

Fri, Apr 10

Mechanism design and revenue


Kleinberg, Weinberg. Matroid Prophet Inequalities. Symposium on Theory of Computing (STOC), 2012.


Prof. Bo blog post on prophet inequalities

Mon, Apr 13

Competition improving revenue


Fu, Liaw, Randhawa. The Vickrey Auction with a Single Duplicate Bidder Approximates the Optimal Revenue. Economics and Computation (EC), 2019.

Wed, Apr 15

Automated mechanism design, learning theory prereqs for Friday

Fri, Apr 17

Learning auction rules and pseudodimension

Project progress report due


Morgenstern, Roughgarden. Learning Simple Auctions. Conference on Learning Theory (COLT), 2016. And 9-min video presentation

Mon, Apr 20

Learning auction rules, continued


Gonczarowski, Weinberg. The Sample Complexity of Up-to-ε Multi-Dimensional Revenue Maximization. Foundations of Computer Science (FOCS), 2018.

Wed, Apr 22

Project presentations

Fri, Apr 24

Project presentations

Mon, Apr 27

Project presentations

Wed, Apr 29

Project presentations

Sat, May 02: Final project writeups due.