COURSE: CS 15-892 Foundations of Electronic Marketplaces

Fall 2011

Summary:The course covers classic and state-of-the-art results on computational and game-theoretic questions related to electronic marketplaces.

Instructor: Prof. Tuomas Sandholm (

This page:

Class times: TuTh 10:30-11:50 am, in Gates Hillman Center (GHC) room 4303.

Instructor’s office hour: Tuesdays, noon-1 pm, GHC 9205.

Reading materials:

There is no book that adequately covers all of the covered topics. However, we will be using the book Combinatorial Auctions (MIT Press 2006); each student should acquire that book. In addition, we will use a collection of readings from recent research papers, chapters that are about to appear in other books, and slides by the instructor. Some of these papers are brand new, and have not even appeared publicly yet.


  1. Lectures by Prof. Sandholm. In addition, guest lectures by outside experts.
  2. In advance of each lecture, each student is expected to download the paper and the slides for that lecture from the course web page, to print them, and to read the paper carefully before the lecture. There may be surprise quizzes on the readings.
  3. Three homework assignments, which will mostly consist of analytical questions. 
  4. Final project. Each student is expected to complete an original final project (alone, or for a larger project, in a pair). The students are free to pick the topics of the final projects, but they have to be related to the topic of the course. The projects can involve analytical work, computer experiments, building a prototype, etc. The project might also involve applying some of the techniques learned in this course to the student’s research in another area. Two-page project plans are due on October 20th by the beginning of class. Students are expected to present their final projects in the last couple of lectures. The writeups of the final projects are due on December 8th (i.e., last class) in the beginning of class.These are hard deadlines.

Evaluation: Participation 10%, homework assignments and quizzes 40%, final project 50%. The course must be taken for credit: there is no audit option.

Prerequisites: Knowledge of algorithms and computational complexity. Knowledge of basic probability theory. This is a full-semester course given by the Computer Science Department primarily to Ph.D. candidates. However, others may also take it with the instructor's permission.


Here is the set of topics that we will cover, and a list of papers for each topic. Only some of the papers will be covered (the papers most likely to be covered are marked in red). THIS LIST WILL BE UPDATED DYNAMICALLY DURING THE SEMESTER.

General review articles

Basics of mechanism design

In designing (exact or approximate) mechanisms, it can help to know what mechanism families are incentive compatible, and what is (im)possible:

Auctioning a single item

Optimal (offline) clearing of multi-item and/or multi-unit markets

Expressiveness of mechanisms

Multi-stage market designs with preference elicitation

Automated mechanism design

Work on the general problem

Work on auctions, other selling mechanisms, etc.

Auction and exchange design without priors

Incentive-compatible (IC) approximation by the auctioneer

Bidding agents with hard valuation problems

Avoiding manipulation using computational complexity; Mechanism design for computationally limited agents; Non-truth-promoting mechanisms

Online mechanisms


RELATED EXCITING TOPICS (which we will probably not have time to cover in class)




Kidney exchange (there are lots of papers on other matching markets; ask me for more)

Prediction markets

Advertising markets (e.g., sponsored search auctions, display ad markets, TV ad markets, print ads, etc.)

Core-selecting combinatorial auctions

Distributed implementation

Privacy in mechanism design

Dynamically auctioning wireless spectrum (by the way, Google advocates dynamic provisioning to the FCC, and there is talk of such in Ireland as well)

Holdouts, eminent domain, corporate takeovers, and how to get old inefficient holders of radio spectrum to release it

Exotic contract types (“It’s not the figures lying, it’s the liars figuring” -- Mark Twain)

Coalition formation

Basics: core, Shapley value, Sandholm’s network routing example, iterative payoff division schemes

Social networks and multi-level marketing

Safe exchange

Best-response auctions

Reputation systems (these systems are prevalent - e.g., eBay - but they are all manipulable)

Cost sharing

Worst-case Nash equilibrium (what’s the price of anarchy?)


COURSE SCHEDULE (this will change during the semester)

Other resources

Tuomas Sandholm’s home page
Al Roth's Game Theory, Experimental Economics, and Market Design Page
Al Roth’s Market Design Ideas Page

Related courses at other universities

David Parkes’s course Computational Mechanism Design at Harvard
Al Roth and Peter Coles’s course Market Design at Harvard
Noam Nisan’s course at Hebrew University, Israel
Utku Ünver’s Homepage at Boston College
Robert Wilson’s course Multiperson Decision Theory at Stanford
Tim Roughgarden’s course Introduction to Algorithmic Game Theory at Stanford
Christos Papadimitriou’s course Algorithmic Game Theoryat University of California, Berkeley
Joan Feigenbaum’s courses at Yale University
Amy Greenwald’s at Brown University
Yoav Shoham’s course Multi Agent Systems at Stanford