COURSE: CS 15-892 Foundations of Electronic Marketplaces

Fall 2015

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

Abstract: This PhD-level course covers classic and state-of-the-art results on computational and game-theoretic questions related to electronic marketplaces.  We will start with classic and recent results in mechanism design.  We will then cover integer programming algorithms for scalable market clearing.  Further topics include expressiveness in mechanisms, preference elicitation from multiple parties, multi-stage mechanisms, communication complexity, automated mechanism design, mechanism design for computationally limited agents, online (i.e., dynamic) mechanisms, and revenue maximization techniques. Applications discussed vary from year to year, and may include combinatorial auctions, kidney exchange, sponsored search, display advertising markets, incentive auctions, prediction markets, and automated market making.

Instructors: Prof. Tuomas Sandholm ( and John Dickerson

This page:

Class times: MoWe 10:30-11:50 am in GHC 4101.

Tuomas Sandholm's office hours: By appointment.

John Dickerson's office hours: By appointment.

Reading materials:

There is no book that adequately covers all of the covered topics. We will be using the book Combinatorial Auctions (MIT Press 2006). 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 Tuomas Sandholm and John Dickerson. 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, 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 5th 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 9th (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: No background is required in game theory, mechanism design, or integer programming.  Basic knowledge of probability theory, algorithms, and computational complexity is needed. 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.


COURSE SCHEDULE (this will change during the semester)

  1. Sep 9: Course organization. Introduction. Example applications. Automated negotiation in different stages of an ecommerce transaction. Utility theory. Prescriptive bounded rationality. Measures of how good an interaction mechanism is. Slides. Read this brief overview paper from the Palgrave Dictionary of Economics 2008 regarding the topics in this course.
  2. Sep 14: Extensive form and matrix form representations of games. Dominant strategy equilibrium. Nash equilibrium. Mixed strategy Nash equilibrium. Subgame perfect equilibrium and credible threats. Software as a commitment device. Coalitional solution concepts: strong Nash equilibrium, coalition-proof Nash equilibrium. Ex post equilibrium. Slides on game representations and solution concepts.
  3. Sep 16: Bayes-Nash equilibrium, perfect Bayesian equilibrium, sequential equilibrium, extensive-form trembling hand perfect equilibrium, extensive-form proper equilibrium, normal-form perfect equilibrium, quasi-perfect equilibrium, normal-form proper equilibrium.
  4. Sep 21: Social choice theory (preference aggregation). Binary protocol. Plurality rule. Borda count. Paradoxes in social choice. Arrow’s impossibility theorem (weak version). Arrow’s impossibility theorem (strong version). Voting protocols that circumvent Arrow’s impossibility. Slides on social choice.
  5. Sep 23: Homework 1 posted. Mechanism design. Revelation principle. Dominant strategy implementation. Gibbard-Satterthwaite impossibility theorem. Groves mechanism for quasilinear environments. Slides on mechanism design and dominant-strategy implementation. Read Chapter 9 of Algorithmic Game Theory.
  6. Sep 28: When is the Groves mechanism the only family that works? Clarke tax. Budget imbalance. Collusion. More on characterizing dominant-strategy implementation in quasilinear environments: Robert's theorem, single-parameter environments, weak monotonicity, essential uniqueness of prices. Slides. Additional optional readings: review of network view of incentive compatibility.
  7. Sep 30: Bayes-Nash implementation in incomplete information environments. Expected externality mechanism for quasilinear environments. Budget balance. Participation constraints. Myerson-Satterthwaite impossibility for exchanges. Full implementation. Virtual implementation. Slides on Bayes-Nash implementation in incomplete information environments. Optional reading: Maskin-Sjostrom review on implementation theory.
  8. Oct 5: Project proposals due by email to Prof. Sandholm by the beginning of class. Moore-Repullo mechanism. Auctioning a single item. Private vs. correlated vs. common value auction settings. English, Japanese, Dutch, first-price sealed-bid, and second-price sealed bid (Vickrey) auction mechanisms. Slides on 1-item auctions.
  9. Oct 7: Homework 1 due by email to Prof. Sandholm by the beginning of class. More on auctioning a single item. Revenue equivalence theorem. Revenue non-equivalence. Revenue-maximizing (Myerson) auction.
  10. Oct 12: More on auctioning a single item. Winner’s curse. Asymmetric information. Single-crossing property and its implications. Linkage principle. Auctions with multi-dimensional signals. Collusion. Auctions where bidders can invest effort/computation to determine their own valuations. Last-minute bidding (sniping) and its strategic implications.
  11. Oct 14: Homework 2 posted. Multi-unit auctions. Uniform-price auction. Demand reduction lie. Multi-unit Vickrey auctions. Bidding languages (price bids; PQ bids; PQ bids with XORs, with OR-of-XORs, with XOR-of-ORs, and with OR*; price-quantity graph bids). Slides on multi-unit auctions. Multi-item auctions. Sequential auction mechanisms. Parallel auction mechanisms. Combinatorial auctions. Bidding languages. Slides on multi-item auctions and exchanges. Read Chapter 14 of Combinatorial Auctions book. Additional optional reading: Chapter 12 of Combinatorial Auctions.
  12. Oct 19: More on multi-item auctions. Approaches to winner determination in combinatorial auctions.
  13. Oct 21: Tree search-based winner determination algorithms, including mixed integer programming. Generalized Vickrey auction. Side constraints and non-price attributes in markets. Branch-and-cut.
  14. Oct 26: More on tree search-based winner determination algorithms. Cutting planes. Deriving the Gomory mixed integer cutting plane. Problem formulations. Identifying and using decomposition (and driving toward decomposition). Branching rules.
  15. Oct 28: Homework 2 due by email to Prof. Sandholm by the beginning of class. More on tree search-based winner determination algorithms. Entropic branching, strong branching, reliability branching. Multi-variate branching. Identifying and solving polynomial cases at tree nodes. Multi-unit combinatorial auctions. Combinatorial reverse auctions. Combinatorial exchanges. Free disposal versus not. Combinatorial reserve prices. Partially acceptable bids. Complexity of clearing these generalized markets.
  16. Nov 2: Guest lecture: Nina Balcan on Mechanism Design, Machine Learning, and Pricing Problems. Slides.
  17. Nov 4: Guest lecture: Ariel Procaccia on cake cutting. Slides.
  18. Nov 9: Preference elicitation in combinatorial auctions. Read Chapter 10 of Combinatorial Auctions. Slides.
  19. Nov 11: Demand queries. Ascending (and descending) combinatorial auctions. Primal-dual and subgradient combinatorial auctions. Read Chapter 2 of Combinatorial Auctions. Slides.
  20. Nov 16: Automated mechanism design. Complexity. Applications. Revenue-maximizing combinatorial auctions. Affine maximizer combinatorial auctions. Virtual valuations combinatorial auctions. Slides.
  21. Nov 18: More on automated mechanism design. Using ex interim allocations with a separation oracle for feasibility. Automated design of multi-stage mechanisms. Bidding agents with hard valuation problems. Mechanism design for such agents. Nonexistence of incentive-compatible mechanisms. Benefits of non-truth-promoting mechanisms. Possibility and impossibility of manipulation-optimal mechanisms. Second-chance mechanism. Assuming agents can only solve problems that are worst-case polynomial time. Easiness of typical cases of manipulation problems.
  22. Nov 23: Homework 3 posted. Exchanges for human organs. Kidney exachnge. Slides.
  24. Nov 30: More on exchanges for human organs. Dynamics.
  25. Dec 2: Homework 3 due by the beginning of class. Sponsored search. Slides.
  26. Dec 7: Final project presentations: Brendan, Junxing, Swaprava.
  27. Dec 9 (last class): Final project presentations: Ellen, Spencer, Rolando. Final project writeups due: HARD DEADLINE.



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 (batch) clearing of multi-item and/or multi-unit markets

Expressiveness of mechanisms

Multi-stage market designs with preference elicitation

Automated mechanism design (AMD)

...for the general problem

...for auctions and other selling mechanisms

...for other applications

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 extensively in class)

Kidney exchange and exchanges for other organs

Incentive auctions and holdouts

Combinatorial auctions with "funny money" artificial currency: course allocation as a canonical application

Prediction markets



Advertising markets

Sponsored search

Display advertising "exchanges", i.e., spot markets for remnant inventory where selling is one impression at a time

Display advertising for premium inventory -- typically sold manually in campaigns but automatically dispatched

TV advertising, print ads, etc.

Core-selecting combinatorial auctions

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

Distributed implementation

Privacy in mechanism design

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?)


Other resources

Tuomas Sandholm’s home 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
Scott Kominer's market design course
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 Theory at 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