COMP_SCI 496: Mechanism Design

Quarter Offered

None : 9:30-10:50 TuTh ; Hartline


Students should either have a solid algorithms background (E.g., COMP_SCI 336) or a solid auction theory background (a prior course in auction design or game theory).


This course combines game theory and economics with algorithms. Algorithms studies at simple processes for finding optimal or near optimal solutions to complicated optimization problems. The output of an algorithm is often an allocation of resources, e.g., which edges in a graph are in the shortest path or which tasks can be scheduled on a computer server. Game theory and economics study the outcome of systems of selfish agents, each optimizing their own objective. Algorithmic mechanism design combines the two fields and looks to find simple processes that result in good allocations of resources even when the input to these processes are provided by selfish agents who may try to game the system to get a more favorable outcome for themselves. These settings of selfish agents are especially relevant in computer networks such as the Internet. Unfortunately, optimal mechanisms are almost never simple enough to be implemented in practice, therefore, this course develops techniques for designing and analyzing simple mechanisms that approximate the optimal ones. From a computer science perspective, this course can be views as adding game theory to standard settings for approximation algorithms. From an economics perspective, this course can be viewed as adding approximation to standard settings in auction theory and mechanism design. Examples will be taken from eBay, Internet routing, Internet broadcast, FCC spectrum auction, and Internet advertising.

REQUIRED TEXTBOOK: course notes.

REFERENCE TEXTBOOKS: Algorithmic Game Theory, Nisan, Roughgarden, Tardos, and Vazirani, eds.

COURSE COORDINATOR: Prof. Jason Hartline 

COURSE GOALS: The goal of this course is to familiarize graduate students (and advanced undergraduates) with the current state-of-the-art in algorithmic mechanism design. Through lectures and reading of classic research papers, students will familiarize (if necessary) themselves with foundational theory from both approximation algorithms and auction theory. Through lectures and the reading of recent research papers, students will study the paradigmatic problems in the new field of algorithmic mechanism design. Students will explore at least one topic area deeply through readings.

DETAILED COURSE TOPICS: Nash equilibrium, Bayes-Nash equilibrium, dominant strategy equilibrium, games of incomplete information, single-item auctions, single-parameter mechanism design, welfare maximization and approximation (Bayesian and prior-free), revenue maximization and approximation (Bayesian and prior-free), revenue equivalence, all-pay mechanisms, structured procurement, multi-dimensional mechanism design, posted pricing, combinatorial auctions.

ASSIGNMENTS: paper reading, problem solving, survey paper.