COURSE: CS 15-892 Foundations of Electronic Marketplaces

Fall 2013

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, sponsored search, display advertising markets, kidney exchange, prediction markets, and automated market making.

Instructor: Prof. Tuomas Sandholm (sandholm@cs.cmu.edu)

This page: http://www.cs.cmu.edu/~sandholm/cs15-892F13/cs15-892.htm

Class times: MoWe 10:30-11:50 am in GHC 4101.  First lecture is on September 9th.

Instructor’s office hour: By appointment.

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

Format:

  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, 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 2nd 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 4th (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)

TOPICS

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)

Bundling

Externalities

Kidney exchange

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

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

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