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


Overview

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:
https://nb.mit.edu/subscribe?key=OeSCswNgU5dl4eh5p
hmU981ksHM1GuDZ0veU7p1o1OFFLumFuL


Schedule

Mon, Jan 13

Intro to game theory

Resources

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

Resources

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

Fri, Jan 17

Computing equilibria - congestion games

Resources

Penn lecture notes on congestion games

Mon, Jan 20

MLK Day - No class

Wed, Jan 22

Computing equilibria - PPAD, Brouwer, etc

Resources

Roughgarden lecture notes

Fri, Jan 24

Generic sampling algorithm for NASH

Reading

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

Mon, Jan 27

PPAD-hardness of NASH

Reading

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

Resources

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

Reading

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

Resources

Penn lecture notes on Voting as MLE.

Wed, Feb 05

Online learning - Polynomial Weights

Resources

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

Reading

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

Reading

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

Resources

Penn lecture notes on Zero-Sum Games

Wed, Feb 12

Developments in solving zero-sum games

Fri, Feb 14

Online learning for game-solving

Reading

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

Mon, Feb 17

Proper scoring rules

Reading

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

Wed, Feb 19

Characterization of Proper Scoring Rules

Resources

Penn lecture notes on proper scoring rules

Fri, Feb 21

Proper Scoring Rules continued

Reading

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

Resources

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

Mon, Feb 24

Prediction Markets

Reading

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

Resources

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

Reading

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

Reading

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

Reading

Freeman, Pennock, Podimatra, Wortman Vaughan. No-Regret and Incentive-Compatible Prediction with Expert Advice. Working paper, 2019.

Mon, Mar 09

Persuasion and online decisionmaking

Reading

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)

Resources

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

Fri, Mar 13

Frontiers of peer prediction

Reading

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

Mon, Mar 16

Decision markets

Reading

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

Reading

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

Reading

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

Resources

Mechanism Design and Approximation book by Hartline

Wed, Apr 01

Smoothness arguments and price of anarchy

Resources

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

Reading

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

Resources

Prof. Bo blog post on VCG

Mon, Apr 06

Revenue maximization

Reading

Roughgarden lecture notes on revenue maximization

Wed, Apr 08

More on Myerson: virtual values, revelation principle

Fri, Apr 10

Mechanism design and revenue

Reading

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

Resources

Prof. Bo blog post on prophet inequalities

Mon, Apr 13

Competition improving revenue

Reading

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

Reading

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

Mon, Apr 20

Learning auction rules, continued

Reading

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.