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 (sandholm@cs.cmu.edu) and John Dickerson

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

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.

Format:

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 5^th 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 9^th (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. M
12. ctions. Read Chapter 2 of Combinatorial Auctions. Slides.
13. Nov 16: Automated mechanism design. Complexity. Applications. Revenue-maximizing combinatorial auctions. Affine maximizer combinatorial auctions. Virtual valuations combinatorial auctions.
14. 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.
15. Nov 23: Homework 3 posted. Exchanges for human organs. Kidney exchange slides.
16. ulti-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.
17. Oct 19: More on multi-item auctions. Approaches to winner determination in combinatorial auctions.
18. 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.
19. 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.
20. 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.
21. Nov 2: Guest lecture: Nina Balcan on Mechanism Design, Machine Learning, and Pricing Problems. Slides.
22. Nov 4: Guest lecture: Ariel Procaccia on cake cutting. Slides.
23. Nov 9: Preference elicitation in combinatorial auctions. Read Chapter 10 of Combinatorial Auctions. Slides.
24. Nov 11: Demand queries. Ascending (and descending) combinatorial auctions. Primal-dual and subgradient combinatorial au
25. Nov 25: THANKSGIVING HOLIDAY: NO CLASS.
26. Nov 30: Exchanges for human organs.
27. Dec 2: Homework 3 due by the beginning of class. Lecture topic TBD.
28. Dec 7: Final project presentations: Brendan, Junxing.
29. Dec 9 (last class): Final project presentations: Ellen, Spencer. Final project writeups due: HARD DEADLINE.

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

• Computing in Mechanism Design. by T. Sandholm. In the New Palgrave Dictionary in Economics, 2008. (PDF)
• Computational Mechanism Design by David C. Parkes. In Lecture notes of Tutorials at 10th Conf. on Theoretical Aspects of Rationality and Knowledge (TARK-05), Institute of Mathematical Sciences, University of Singapore, 2008. (PDF)
• "Combinatorial Auctions (a survey)" by Blumrosen and Nisan. Chapter 11 of the book Algorithmic Game Theory.
• “Auctions: Theory” by Lawrence Ausubel. To appear in the New Palgrave Dictionary of Economics. (PDF)

Basics of mechanism design

• Nisan, N. 2007. Introduction to Mechanism Design (for Computer Scientists). Chapter 9 of the book Algorithmic Game Theory.
• Mas-Colell, Whinston & Green. Microeconomic theory., Chapter 23. Oxford University Press, 1995. (Includes the Myerson-Satterthwaite theorem, but does not cover virtual implementation).
• Review article [Parkes 01 (PS)] [bibliography for this article (PS)]
• Review article Implementation Theory (PDF) by Maskin & Sjostrom, 2001 (Does not cover dominant strategy implementation; first 80% is for complete information environments; focuses on implementation that does not have bad equilibria also).
• Osborne and Rubinstein. A Course in Game Theory, MIT Press, 1994.

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

• Truthful germs are contagious: A local to global characterization of truthfulness. A. Archer and R. Kleinberg, EC-08.
• A Modular Approach to Roberts' Theorem. Dobzinski and Nisan, SAGT-09.
• Two Simplified Proofs for Roberts' Theorem. Ron Lavi, Ahuva Mu'alem, and Noam Nisan. Social Choice and Welfare, 32, pp. 407 -- 423,  2009.
• The Limits of Ex Post Implementation. Philippe Jehiel, Moritz Meyer-ter-Vehn, Benny Moldovanu, and William R. Zame Econometrica, 2006.
• Ex post implementation. Dirk Bergemann and Stephen Morris. Games and Economic Behavior 63 (2008) 527-566.
• Multi-Unit Auctions with Budget Limits. Shahar Dobzinski, Ron Lavi, and Noam Nisan. FOCS-08.
• On Characterizations of Truthful Mechanisms for Combinatorial Auctions and Scheduling. Shahar Dobzinski and Mukund Sundararajan. EC-08. See also the addendum.
• Paths, Cycles and Mechanism Design , by Vohra, 2007.
• Weak Monotonicity characterizes deterministic dominant strategy implementation by S. Bikhchandani, S. Chatterji, R. Lavi, A. Mu'alem, N. Nisan, and A. Sen. Econometrica, 74(4), pp. 1109 -- 1132, 2006. See also the supplementary material for this paper.
• Characterization of Revenue Equivalence, by B. Heydenreich, Rudolf Muller, Marc Uetz, and Rakesh Vohra, 2007.
• Characterizing Dominant Strategy Mechanisms with Multi-Dimensional Types. [Gui, Mueller, Vohra 2004 draft]
• Truthful Mechanism Design for Multi-Dimensional Scheduling via Cycle Monotonicity. Ron Lavi and Chaitanya Swamy. EC-07.

Auctioning a single item

• Mechanism Design and Approximation. Draft of book by Jason Hartline. Available for free. Especially Chapter 3.
• Auction Theory. Book by Vijay Krishna. (I don't think this is available for free, but it is available on Amazon.)
• Profit Maximization in Mechanism Design. By Hartline and Karlin. Chapter 13 of the book Algorithmic Game Theory. Sections 13.1-13.2.
• Bayesian Optimal No-deficit Mechanism Design. By Shuchi Chawla, Jason Hartline, Uday Rajan and R. Ravi, WINE'06.
• Review article Auctions: An Introduction, Wolfstetter 1994
• Advanced material on non-private value auctions [Dasgupta & Maskin QJE-00], [Jehiel & Moldovanu 1998]

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

• Sandholm, T. 2006. Optimal Winner Determination Algorithms. Chapter 14 of the book Combinatorial Auctions, Cramton, Shoham, and Steinberg, eds., MIT Press.
• Sandholm, T. 2013. Very-Large-Scale Generalized Combinatorial Multi-Attribute Auctions: Lessons from Conducting $60 Billion of Sourcing. Chapter 16 in The Handbook of Market Design, edited by Nir Vulkan, Alvin E. Roth, and Zvika Neeman, Oxford University Press.
• Sandholm, T., Suri, S., Gilpin, A., and Levine, D. 2005. CABOB: A Fast Optimal Algorithm for Winner Determination in Combinatorial Auctions. Management Science 51(3), 374-390.
• Lehmann, D., Mueller, R., and Sandholm, T. 2006. The Winner Determination Problem. Chapter 12 of the book Combinatorial Auctions, Cramton, Shoham, and Steinberg, eds., MIT Press. A Kernel Method for Market Clearing. By Sebastien Lahaie. IJCAI-09.
• Gilpin, A. and Sandholm, T. 2011. Information-Theoretic Approaches to Branching in Search. Discrete Optimization, 8, 147-159.
• Bidding and allocation in combinatorial auctions [Nisan EC-00]
• Winner determination in combinatorial auction generalizations. [Sandholm et al AAMAS-02]
• Side constraints and non-price attributes in markets. [Sandholm et al IJCAI-01 workshop: Distributed constraint reasoning]; short later version appeared in Games and Economic Behavior.
• Computational complexity of clearing exchanges with supply-demand curves [Sandholm-Suri ISAAC-01]
• Computational complexity of clearing multi-unit auctions [Sandholm-Suri IJCAI-01]
• Fast Vickrey-Clarke-Groves computation in networks [Suri-Hirschberg FOCS-01]

Expressiveness of mechanisms

• A Theory of Expressiveness in Mechanisms. Michael Benisch and Tuomas Sandholm. Draft, 2011. Very short early version in appeared in AAAI-08.
• Very-Large-Scale Generalized Combinatorial Multi-Attribute Auctions: Lessons from Conducting $60 Billion of Sourcing. Sandholm, T. Chapter 16 in The Handbook of Market Design, edited by Nir Vulkan, Alvin E. Roth, and Zvika Neeman, Oxford University Press.
• P. Dütting, F. Fischer, D. C. Parkes, Expressiveness and Robustness of First-Price Position Auctions, EC’14
• Simplicity-Expressiveness Tradeoffs in Mechanism Design. Paul Dütting, Felix Fischer, and David Parkes. EC-11.
• Milgrom, P. Simplified Mechanisms with an Application to Sponsored-Search Auctions. Games and Economic Behavior, Sept 2010, vol 70, Issue 1: 62-70..
• Multi-Keyword Sponsored Search. Peerapong Dhangwatnotai. EC-11.
• Benisch, M., Sadeh, N., and Sandholm, T. Methodology for Designing Reasonably Expressive Mechanisms with Application to Ad Auctions In Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI). (PDF)
• Sandholm, T. 2007. Expressive Commerce and Its Application to Sourcing: How We Conducted $35 Billion of Generalized Combinatorial Auctions. AI Magazine, 28(3), 45-58.
• Boutilier, C., Parkes, D., Sandholm, T., and Walsh, W. 2008. Expressive Banner Ad Auctions and Model-Based Online Optimization for Clearing. In Proceedings of the National Conference on Artificial Intelligence (AAAI). (PDF)
• Position Auctions with Budgets: Existence and Uniqueness. By Itai Ashlagi, Mark Braverman, Avinatan Hassidim, Ron Lavi, and Moshe Tennenholtz.Draft 2009. (PDF)
• Optimize-and-Dispatch Architecture for Expressive Ad Auctions by David C. Parkes and Tuomas Sandholm. In the Proceedings of First Workshop on Sponsored Search Auctions, 2005.(PDF)
• On Expressing Value Externalities in Position Auctions. Florin Constantin, Malvika Rao, Chien-Chung Huang, and David C. Parkes. AAAI-11.
• Externalities in Keyword Auctions: An Empirical and Theoretical Assessment, R. Gomes, N. Immorlica and E. Markakis, in Proc. 5th Workshop on Ad Auctions (2009). (PDF)
• Sponsored Search with Contexts. Eyal Even-Dar, Michael Kearns, and Jennifer Wortman. WWW-07.

Multi-stage market designs with preference elicitation

• Preference elicitation in combinatorial auctions [Sandholm-Boutilier Chapter 10 in the book “Combinatorial Auctions”, 2006]
• Iterative combinatorial auctions (iBundle etc.) [Parkes’s chapter in the book “Combinatorial Auctions” 2006] [OLD: Parkes ACM-EC-99, AAAI-00a, AAAI-00b]
• A Kernel-Based Iterative Combinatorial Auction. Sebastien Lahaie, EC-11.
• The Communication Requirements of Combinatorial Allocation Problems. By Ilya Segal, Chapter 11 of the book Combinatorial Auctions, 2006.
• Ascending Price Vickrey Auctions for General Valuations (PDF) by Debasis Mishra and David C. Parkes. Journal of Economic Theory 132, 2007.
• Exponential Communication Inefficiency of Demand Queries by N. Nisan and I. Segal. TARK 2005.
• Multi-Item Vickrey-Dutch Auctions (PDF) Draft by Debasis Mishra and David C. Parkes, 2007.
• Communication complexity of approximate set packing and covering [Nisan 01]
• Linear programming and Vickrey auctions [Vohra et al. draft 01]
• Dynamic auction for multiple distinguishable items [Ausubel 00] (slides from Nisan’s course)
• AkBA [Wurman et al ACM-EC-00]
• Auction Design with Costly Preference Elicitation (PDF) by David C. Parkes. In Annals of Mathematics and AI 44, 2005, pages 269-302.

Automated mechanism design (AMD)

...for the general problem

• Conitzer, V. and Sandholm, T. 2002. Complexity of Mechanism Design. In Proceedings of the 18th Conference on Uncertainty in Artificial Intelligence (UAI).
• Sandholm, T. 2003. Automated mechanism design: A New Application Area for Search Algorithms. In Proceedings of the International Conference on Principles and Practice of Constraint Programming (CP).
• Conitzer, V. and Sandholm, T. 2004. Self-Interested Automated Mechanism Design and Implications for Optimal Combinatorial Auctions.In Proceedings of the ACM Conference on Electronic Commerce (EC), pp. 132-141.
• Sui, X., Boutilier, C., and Sandholm, T. 2013. Analysis and Optimization of Multi-dimensional Percentile Mechanisms. In Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI).
  
• Sandholm, T., Conitzer, V., and Boutilier, C. 2007. Automated Design of Multistage Mechanisms. In Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI).
• Conitzer, V. and Sandholm, T. 2007. Incremental Mechanism Design. In Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI).
• Conitzer, V. and Sandholm, T. 2004. An Algorithm for Automatically Designing Deterministic Mechanisms without Payments. In Proceedings of the International Joint Conference on Autonomous Agents and Multiagent Systems (AAMAS), pp. 128-135, New York, July 19-23.
• Conitzer, V. and Sandholm, T. 2003. Applications of automated mechanism design. In Proceedings of the UAI Bayesian Modeling Applications Workshop, Acapulco, Mexico. Extended version.
• Conitzer, V. and Sandholm, T. 2003. Automated mechanism design with a structured outcome space. Draft.
• Conitzer, V. and Sandholm, T. 2003.Automated Mechanism Design: Complexity Results Stemming from the Single-Agent Setting. In Proceedings of the International Conference on Electronic Commerce (ICEC), Pittsburgh, September 30 – October 3.

...for auctions and other selling mechanisms

• Sandholm, T. and Likhodedov, A. 2015. Automated Design of Revenue-Maximizing Combinatorial Auctions. Operations Research 63(5), 1000-1025. (Subsumes and extends over a AAAI-05 paper and a AAAI-04 paper.)
• Daskalakis, C. Multi-Item Auctions Defying Intuition? Newsletter of the ACM Special Interest Group on E-commerce, 14(1), 2015. pdf
  
• Cai, Y., Daskalakis, C., and Weinberg, M. Reducing Bayesian Mechanism Design to Algorithm Design. Encyclopedia of Algorithms, 2015. pdf
• Sandholm, T. and Gilpin, A. 2003. Sequences of Take-It-or-Leave-It Offers: Near-Optimal Auctions without Full Valuation Revelation. In Proceedings of the AAMAS workshop on Agent-Mediated Electronic Commerce (AMEC V), Melbourne,Australia.
• Cai, Y., Daskalakis, C., and Weinberg, M. 2013. Understanding Incentives: Mechanism Design becomes Algorithm Design. In FOCS.
• Cai, Y., Daskalakis, C., and Weinberg, M. 2012. Optimal Multi-Dimensional Mechanism Design: Reducing Revenue to Welfare Maximization. In FOCS. arxiv
• Tang, P. and Sandholm, T. 2012. Mixed-bundling auctions with reserve prices. In Proceedings of the International Conference on Autonomous Agents and Multi-Agent Systems (AAMAS).
• Tang, P. and Sandholm, T. 2011. Approximating Optimal Combinatorial Auctions for Complements Using Restricted Welfare Maximization. In Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI).
• Othman, A. and Sandholm, T. 2009. How Pervasive is the Myerson-Satterthwaite Impossibility? In Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI).
• On approximating optimal auctions [Ronen EC-01]

...for other applications

• R. Jurca and B. Faltings. Collusion Resistant, Incentive Compatible Feedback Payments. Proceedings of the ACM Conference on E-Commerce (EC'07), pp. 200-209, San Diego June 11-15 2007.
• R. Jurca and B. Faltings. Minimum Payments that Reward Honest Reputation Feedback. Proceedings of the ACM Conference on Electronic Commerce (EC2006), pp. 190-199, Ann Arbor, Michigan, June 11-15 2006.

Auction and exchange design without priors

• Mechanism Design via Machine Learning. [Balcan, Blum, Hartline, Mansour], JCSS, 2008.
• Competitive generalized auctions [Fiat, Goldberg, Hartline, Karlin]
• Truthful and Competitive Double Auctions [Deshmukh, Goldberg, Hartline, Karlin]
• Pricing without demand curves [Segal, American Economic Review]
• Market research and Market Design [Vohra & Baliga]
• [OLD READINGS (paper1, paper2) (slides from Nisan’s course)]

Incentive-compatible (IC) approximation by the auctioneer

• Multi-Unit Auctions: Beyond Roberts. Shahar Dobzinski and Noam Nisan. EC-11.
• VC v. VCG: Inapproximability of Combinatorial Auctions via Generalizations of the VC Dimension. Elchanan Mossel, Christos Papadimitriou, Michael Schapira, and Yaron Singer.
• Computation and Incentives in Combinatorial Public Projects. Dave Buchfuhrer, Michael Schapira, and Yaron Singer.
• Bayesian Mechanism Design for Budget-Constrained Agents. Shuchi Chawla, David Malec, and Azarakhsh Malekian. EC-11.
• Computationally-Efficient Approximation Mechanisms. Chapter by Lavi in the book Algorithmic Game Theory.
• Algorithmic mechanism design [Nisan-Ronen GEB 2001]
• Truth revelation in rapid approximately efficient combinatorial auctions [Lehman-O’Callaghan-Shoham JACM-02]
• Truthful and Near-optimal Mechanism Design via Linear Programming, by Ron Lavi and Chaitanya Swamy (early version in FOCS-05).
• On the Power of Randomization in Algorithmic Mechanism Design, FOCS-09. Shahar Dobzinski and Shaddin Dughmi.
• Truthful Randomized Mechanisms for Combinatorial Auctions by S. Dobzinski, N. Nisan, and M. Schapira. STOC 2006.
• Impersonation-Based Mechanisms, By Moshe Babaioff, Ron Lavi, and Elan Pavlov, AAAI-06.
• Two Randomized Mechanisms for Combinatorial Auctions by S. Dobzinski, APPROX-08.
• Limitations of VCG-based Mechanisms by S. Dobzinski and N. Nisan. STOC 2007.
• Mechanisms for Multi-Unit Auctions by S. Dobzinski and N. Nisan. EC-07.
• Algorithms for selfish agents [Nisan 01]
• Computationally feasible VCG mechanism [Nisan-Ronen 00]
• Algorithms for rational agents [Ronen] – Section 7 (if not subsumed by Ronen’s EC-01 paper)
• Mechanism design for resource-bounded agents [Monderer-Tennenholtz-Kfir Dahav ICMAS-00]

Bidding agents with hard valuation problems

• Dominant-Strategy Auction Design for Agents with Uncertain, Private Values. David R. M. Thompson and Kevin Leyton-Brown. AAAI-11.
• Efficient Metadeliberation Auctions.Cavallo and Parkes, AAAI-08.
• Larson, K. and Sandholm, T. 2005. Mechanism Design and Deliberative Agents. Proceedings of the International Joint Conference on Autonomous Agents and Multi-Agent Systems (AAMAS)
• Larson, K. and Sandholm, T. 2001. Costly Valuation Computation in Auctions. In Proceedings of theTheoretical Aspects of Reasoning about Knowledge (TARK)
• Larson, K. and Sandholm, T. 2001. Computationally Limited Agents in Auctions. In Proceedings of the International Conference on Autonomous Agents, Workshop on Agent-based Approaches to B2B.
• Issues in computational Vickrey auctions [Sandholm IJEC-00 (originally ICMAS-96)]
• Valuation complexity explains last-minute bidding [Eric Rasmusen draft-03]
• Computationally feasible VCG mechanism [Nisan-Ronen 00] (This paper contains the second-chance mechanism and the maximal-in-range approach.)
• Ben-Sasson, E., Kalai, A., and Kalai E. An Approach to Bounded Rationality. NIPS. (This is not really about valuation calculation, but has some results about strategies with costs.)

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

• Approximately Strategy-Proof Voting. Eleanor Birrell and Rafael Pass. IJCAI-11.
• Othman, A. and Sandholm, T. 2009. Better with Byzantine: Manipulation-Optimal Mechanisms. In Proceedings of the Symposium on Algorithmic Game Theory (SAGT).
• Conitzer, V. and Sandholm, T. 2003. Computational Criticisms of the Revelation Principle. In Proceedings of the Workshop on Agent Mediated Electronic Commerce (AMEC V). Newer draft.
• Conitzer, V., Sandholm, T., and Lang, J. 2007. When Are Elections with Few Candidates Hard to Manipulate? Journal of the ACM, 54(3).
• Conitzer, V. and Sandholm, T. 2003. Universal Voting Protocol Tweaks to Make Manipulation Hard. In Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI).
• Conitzer, V. and Sandholm, T. 2006. Nonexistence of Voting Rules That Are Usually Hard to Manipulate. In Proceedings of the National Conference on Artificial Intelligence (AAAI)
• Ariel D. Procaccia and Jeffrey S. Rosenschein. 2007. Junta Distributions and the Average-Case Complexity of Manipulating Elections. Journal of Artificial Intelligence Research. Volume 28, pages 157-181. [PDF]
• The Geometry of Manipulation - a Quantitative Proof of the Gibbard Satterthwaite Theorem. Marcus Isaksson, Guy Kindler, and Elchanan Mossel. FOCS-10. This is for 4 or more candidates.
• A Quantitative Version of the Gibbard-Satterthwaite theorem for Three Alternatives. E. Friedgut, G. Kalai, N. Keller and N. Nisan. Preliminary version titled "Elections can be Manipulated Often" appeared in FOCS 2008.

Online mechanisms

• Online Mechanisms, by David Parkes. Chapter in Algorithmic Game Theory.
• Self-Correcting Sampling-Based Dynamic Multi-Unit Auctions. By Florin Constantin and David C. Parkes. Bonn workshop on mechanism design, 2009.
• Self-Correcting Sampling-Based Dynamic Multi-Unit Auctions. by Florin Constantin and David C. Parkes. EC-09.
• Learning About The Future and Dynamic Efficiency, Alex Gershkov and Benny Moldovanu, in American Economic Review.
• Dynamic Revenue Maximization with Heterogeneous Objects: A Mechanism Design Approach. Alex Gershkov and Benny Moldovanu, American Economic Journal: Microeconomics, Vol. 1, No. 2, 2009.
• An Efficient Dynamic Mechanism, Susan Athey and Ilya Segal, 2007.
• The Dynamic Pivot Mechanism. Dirk Bergemann and Juuso Välimäki. Econometrica, (2010) 78: 771-789.
• Efficient Sequential Assignment with Incomplete Information, Alex Gershkov and Benny Moldovanu, in Games and Economic Behaviour.
• Efficiency Levels in Sequential Auctions with Dynamic Arrivals Lavi and Segev. Draft 2009.
• Prompt Mechanisms for Online Auctions. Richard Cole, Shahar Dobzinski, and Lisa Fleischer. SAGT-08
• Online algorithms for market clearing Blum-Sandholm-Zinkevich. JACM, 2006
• Automated Online Mechanism Design and Prophet Inequalities. Hajiaghayi, M., Kleinberg, R., and Sandholm, T., AAAI-07.
• An Ironing-Based Approach to Adaptive Online Mechanism Design in Single-Valued Domains by David C. Parkes and Quang Duong, AAAI-07.
• Chain: A dynamic double auction framework by Jonathan Bredin, David C. Parkes, and Quang Duong. In Journal of Artificial Intelligence Research, 2007.
• Competitive Analysis of Incentive Compatible On-Line Auctions by Ron Lavi and Noam Nisan. Theoretical Computer Science 310(1), pp. 159-180, 2004.
• Online auctions with reusable goods [Hajiaghayi et al. EC-05]
• Reducing truth-telling online mechanisms to online optimization [Awerbuch et al. STOC-03]
• Online learning in online auctions [Blum et al. SODA-03
• Pricing WiFi at Starbucks: Issues in online mechanism design [Friedman & Parkes EC-03]
• Adaptive limited-supply online auctions Hajiaghayi et al. EC-04
• Approximately efficient online mechanism design Parkes, Singh and Yanovsky NIPS-04
• An MDP-Based Approach to Online Mechanism Design D. C. Parkes and S. Singh, Proc. NIPS'03, 2003.
• The price of truth: frugality in truthful mechanisms [Talwar STOC-03]

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

Kidney exchange and exchanges for other organs

• Dickerson, J. and Sandholm, T. 2015. FutureMatch: Combining Human Value Judgments and Machine Learning to Match in Dynamic Environments. AAAI Conference on Artificial Intelligence. Extended version with appendix.
• Blum, A., Dickerson, J., Haghtalab, N., Procaccia, A., and Sandholm, T. 2015. Ignorance is Almost Bliss: Near-Optimal Stochastic Matching With Few Queries. ACM Conference on Economics and Computation (EC).
• Leishman, R., Stewart, D., Kucheryavaya, A., Callahan, L., Sandholm, T., Aeder, M. 2015. Reasons for Match Offer Refusals and Efforts to Reduce them in the OPTN/UNOS Kidney Paired Donation Pilot Program (KPDPP). American Transplant Congress (ATC). Slides.
• Dickerson, J. and Sandholm, T. 2014. Multi-Organ Exchange: The Whole is Greater than the Sum of its Parts. AAAI Conference on Artificial Intelligence.
• Dickerson, J., Procaccia, A., and Sandholm, T. 2014. Price of Fairness in Kidney Exchange. International Conference on Autonomous Agents and Multiagent Systems (AAMAS).
• Dickerson, J. and Sandholm, T. 2014. Balancing Efficiency and Fairness in Dynamic Kidney Exchange. Modern Artificial Intelligence for Health Analytics (MAIHA) workshop at AAAI-14.
• Dickerson, J., Procaccia, A., and Sandholm, T. 2014. Empirical Price of Fairness in Failure-Aware Kidney Exchange. Towards Better and more Affordable Healthcare: Incentives, Game Theory, and Artificial Intelligence (HCAGT) workshop at AAMAS-14.
• Leishman, R., Stewart, D., Monstello, C., Cherikh, W., Sandholm, T., Formica, R., Aeder, M. 2014. The OPTN Kidney Paired Donation Pilot Program (KPDPP): Reaching the Tipping Point in 2013. World Transplant Congress (WTC). Abstract, presentation.
• Aeder, M., Stewart, D., Leishman, R., Sandholm, T., Formica, R. 2014. Early Outcomes of Transplant Recipients in the OPTN Kidney Paired Donation Pilot Program. World Transplant Congress (WTC). Abstract, presentation.
• Stewart, D., Leishman, R., Kucheryavaya, A., Formica, R., Aeder, M., Bingaman, A., Gentry, S., Sandholm, T., and Ashlagi, I. 2014. Exploring the Candidate/Donor Compatibility Matrix to Identify Opportunities to Improve the OPTN KPD Pilot Program's Priority Point Schedule. World Transplant Congress (WTC). Abstract, poster.
• A Non-asymptotic Approach to Analyzing Kidney Exchange Graphs. Ding, Y., Ge, D., He, S., and Ryan, C. ACM Conference on Electronic Commerce (EC), 2015.
• Design and Analysis of Multi-Hospital Kidney Exchange Mechanisms using Random Graphs. Toulis, P. and Parkes, D. In Games and Economic Behavior, 2015.
• A Dynamic Model of Barter Exchange. Anderson, R., Ashlagi, I., Gamarnik, D., and Kanoria, Y. ACM-SIAM Symposium on Discrete Algorithms (SODA), 2015. (Long working paper available here.)
• Mix and Match: A Strategyproof Mechanism for Multi-hospital Kidney Exchange. Ashlagi, I., Fischer, F., Kash, I., and Procaccia, A. In Games and Economic Behavior, 2015.
• An Improved 2-agent Kidney Exchange Mechanism. Caragiannis, I., Filos-Ratsikas, A., and Procaccia, A. In Theoretical Computer Science, 2015.
• Dynamic Matching Market Design. Akbarpour, M., Li, S., and Gharan, S. ACM Conference on Electronic Commerce (EC), 2014. (Long working paper available here.)
• Free Riding and Participation in Large Scale, Multi-hospital Kidney Exchange. Ashlagi, I. and Roth, A. In Theoretical Economics, 2014.
• Kidney Exchange in Dynamic Sparse Heterogenous Pools. Ashlagi, I., Jaillet, P., and Manshadi, V. ACM Conference on Electronic Commerce (EC), 2013.
• Finding Long Chains in Kidney Exchange using the Traveling Salesman Problem. Anderson, R., Ashlagi, I., Gamarnik, D., and Roth, A. In Proceedings of the National Academy of Sciences, 2015.
• Mechanism Design and Implementation for Lung Exchange. Luo, S. and Tang, P. International Joint Conference on Artificial Intelligence (IJCAI), 2015.
• Paired and Altruistic Donation in the UK: Algorithms and Experimentation. Manlove, D. and O'Malley, G. In ACM Journal of Experimental Algorithmics, 2014.
• An Efficient Pricing Algorithm for Clearing Barter Exchanges with Branch-and-Price. Glorie, K., van de Klundert, J., and Wagelmans, A. In Manufacturing & Service Operations Management, 2014.
• Egalitarian Pairwise Kidney Exchange: Fast Algorithms via Linear Programming and Parametric Flow. Li, J., Liu, Y., Huang, L., and Tang, P.  International Conference on Autonomous Agents and Multi-Agent Systems (AAMAS), 2014.
• New Insights on Integer Programming Models for the Kidney Exchange Problem. Constantino, M., Klimentova, X., Viana, A., and Rais, A. In European Journal of Operations Research, 2013.
• Failure-Aware Kidney Exchange. Dickerson, J., Procaccia, A., and Sandholm, T. ACM Conference on Electronic Commerce (EC), 2013.
• Dynamic Matching via Weighted Myopia with Application to Kidney Exchange. Dickerson, J., Procaccia, A., and Sandholm, T. 2012. AAAI Conference on Artificial Intelligence (AAAI), 2012.
• Optimizing Kidney Exchange with Transplant Chains: Theory and Reality. Dickerson, J., Procaccia, A., and Sandholm, T. International Conference on Autonomous Agents and Multiagent Systems (AAMAS), 2012.
• Online Stochastic Optimization in the Large: Application to Kidney Exchange. Pranjal Awasthi and Tuomas Sandholm. International Joint Conference on Artificial Intelligence (IJCAI), 2009. (PDF)
• Dynamic Kidney Exchange. Utku Unver. Review of Economic Studies, 2010.
• A Nonsimultaneous, Extended, Altruistic-Donor Chain. Rees, M., Kopke, J., Pelletier, R., Segev, D., Rutter, M., Fabrega, A., Rogers, J., Pankewycz, O., Hiller, J., Roth, A., Sandholm, T., Ünver, U., and Montgomery, R. New England Journal of Medicine 360(11), 1096-1101, 2009. (PDF)
• Clearing Algorithms for Barter Exchange Markets: Enabling Nationwide Kidney Exchanges. Abraham, D., Blum, A., and Sandholm, T. ACM Conference on Electronic Commerce (EC), 2007. (PDF)
• Individual Rationality and Participation in Large Scale, Multi-hospital Kidney Exchange.  Itai Ashlagi and Alvin E. Roth. EC-11.
• Al Roth’s Game Theory, Experimental Economics, and Market Design Page. This page has lots of pointers to other matching markets as well.

Incentive auctions and holdouts

• Nguyen, T.and Sandholm, T. 2015. Multi-Option Descending Clock Auction. Draft, August 2015.
• Nguyen, T.and Sandholm, T. 2014. Optimizing Prices in Descending Clock Auctions. In Proceedings of the ACM Conference on Economics and Computation (EC). Newer extended version.
• Deferred-Acceptance Auctions and Radio Spectrum Reallocation,”, Paul Milgrom and Ilya Segal, draft, August 2015.
• P. Dütting, V. Gkatzelis, T. Roughgarden, The Performance of Deferred-Acceptance Auctions. In Proceedings of the ACM Conference on Economics and Computation (EC).
• Solving the Station Repacking Problem. A. Frechette, N. Newman, K. Leyton-Brown. International Joint Conference on Artificial Intelligence (IJCAI), 2015.
• Incentive auction plans at the FCC.
• Deferred-Acceptance Heuristic Auctions. Milgrom, P. and Segal, I. Draft, 2013.
• Concordance among Holdouts. Scott Kommiers and E. Glen Weyl. EC-11.

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

• Finding Approximate Competitive Equilibria: Efficient and Fair Course Allocation. Othman, A., Budish, E., and Sandholm, T. International Conference on Autonomous Agents and Multi-Agent Systems (AAMAS), 2010.
• Changing the Course Allocation Mechanism at Wharton. Budish, E. and Kessler, J. Working paper, 2015.
• Course Match: A Large-Scale Implementation of Approximate Competitive Equilibrium from Equal Incomes for Combinatorial Allocation. Budish, E., Cachon, G., Kessler, J., and Othman, A. Working paper, 2015.
• Othman, A., Papadimitriou, C., and Rubinstein, A. 2014. The Complexity of Fairness through Equilibrium. In Proceedings of the ACM Conference on Economics and Computation (EC). (pdf).
• The Combinatorial Assignment Problem: Approximate Competitive Equilibrium from Equal Incomes. Budish, E. In Journal of Political Economy, 2011.

Prediction markets

• Nicolas S. Lambert, John Langford, Jennifer Wortman Vaughan, Yiling Chen, Daniel Reeves, Yoav Shoham, and David M. Pennock. An Axiomatic Characterization of Wagering Mechanisms. Journal of Economic Theory.
• Yiling Chen, Mike Ruberry, and Jennifer Wortman Vaughan. Cost Function Market Makers for Measurable Spaces. EC, 2013. [Long Version]
• Xi Alice Gao, Andrew Mao, and Yiling Chen. Trick or Treat: Putting Peer Prediction to the Test. Workshop on Crowdsourcing and Online Behavioral Experiments (COBE), in conjunction with ACM EC’13, Philadelphia, PA, June 2013.
• Jacob Abernethy, Yiling Chen, and Jennifer Wortman Vaughan. Efficient Market Making via Convex Optimization, and a Connection to Online Learning. ACM Transactions on Economics and Computation. Vol. 1, no. 2, pp. 12:1-12:39, May 2013
• Othman, A., Pennock, D., Reeves, D., and Sandholm, T. 2013. A Practical Liquidity-Sensitive Automated Market Maker. ACM Transaction on Economics and Computation (TEAC), to appear. (Conference version in EC-10.)
• Othman, A. and Sandholm, T. 2013. The Gates Hillman prediction market. Review of Economic Design, 17(2), 95-128. (Conference version "Automated Market-Making in the Large: The Gates Hillman Prediction Market" in EC-10.)
• Othman, A. and Sandholm, T. 2012. Profit-Charging Market Makers with Bounded Loss, Vanishing Bid/Ask Spreads, and Unlimited Market Depth. In Proceedings of the ACM Conference on Electronic Commerce (EC).
• Othman, A. and Sandholm, T. 2012. Rational Market Making with Probabilistic Knowledge. In Proceedings of the International Conference on Autonomous Agents and Multiagent Systems (AAMAS).
• Othman, A. and Sandholm, T. 2011. Inventory-based versus Prior-based Options Trading Agents. Algorithmic Finance 1:95-121.
• Othman, A. and Sandholm, T. 2011. Liquidity-Sensitive Automated Market Makers via Homogeneous Risk Measures. Workshop on Internet And Network Economics (WINE).
• An Efficient Monte-Carlo Algorithm for Pricing Combinatorial Prediction Markets for Tournaments. Lirong Xia and David M. Pennock. IJCAI-11.
• An Optimization-Based Framework for Automated Market-Making.  Jacob Abernethy, Yiling Chen, and Jennifer Wortman Vaughan. EC-11.
• Only Valuable Experts Can Be Valued. Moshe Babaioff, Liad Blumrosen, Nicolas Lambert, and Omer Reingold. EC-11.
• Othman, A. and Sandholm, T. 2011. Automated Market Makers That Enable New Settings: Extending Constant-Utility Cost Functions. In Proceedings of the Conference on Auctions, Market Mechanisms and Their Applications (AMMA).
• Othman, A. and Sandholm, T. 2010. Decision Rules and Decision Markets. In Proceedings of the International Conference on Autonomous Agents and Multiagent Systems (AAMAS).
• Othman, A. and Sandholm, T. 2010. When Do Markets with Simple Agents Fail? In Proceedings of the International Conference on Autonomous Agents and Multiagent Systems (AAMAS).
• Computational Aspects of Prediction Markets, Chapter 26 of Algorithmic Game Theory.

Bundling

• Kroer, C. and Sandholm, T. 2015. Computational Bundling for Auctions. In Proceedings of the International Conference on Autonomous Agents and Multiagent Systems (AAMAS). Also: Computational Bundling for Auctions, CMU Computer Science Department Technical Report CMU-CS-13-111, 2013.
• Signaling schemes for revenue maximization. Emek, Y., Feldman, M., Gamzu, I., Paes Leme, R., and Tennenholtz, M. EC-12.
• Send Mixed Signals – Earn More, Work Less. Miltersen, P., and Sheffet, O. EC-12.
• Revenue Maximization via Hiding Item Attributes. Guo, M. and Deligkas, A. IJCAI-13.
• Automated Channel Abstraction for Advertising Auctions. Walsh, W., Boutilier, C., Sandholm, T., Shields, R., Nemhauser, G., and Parkes, D. In Proceedings of the Ad Auctions Workshop, 2009. (PDF)

Externalities

• Money for Nothing: Exploiting Negative Externalities. Changrong Deng and Saša Pekec. EC-11.
• Krysta, P., Michalak, T., Sandholm, T., and Wooldridge, M. 2010. Combinatorial Auctions with Externalities. Extended version of AAMAS-10 paper.
• Conitzer, V. and Sandholm, T. Computing Optimal Outcomes under an Expressive Representation of Settings with Externalities. Journal of Computer and System Sciences (JCSS), special issue on Knowledge Representation and Reasoning, to appear. Early version in AAAI-05.
• Conitzer, V. and Sandholm, T. 2011. Expressive Markets for Donating to Charities. Artificial Intelligence, 175(7-8), 1251-1271, special issue on Representing, Processing, and Learning Preferences: Theoretical and Practical Challenges. Early version in EC-04.
• Boutilier, C., Parkes, D., Sandholm, T., and Walsh, W. 2008. Expressive Banner Ad Auctions and Model-Based Online Optimization for Clearing. In Proceedings of the National Conference on Artificial Intelligence (AAAI). (PDF)
• Optimize-and-Dispatch Architecture for Expressive Ad Auctions by David C. Parkes and Tuomas Sandholm. In the Proceedings of First Workshop on Sponsored Search Auctions, 2005.(PDF)
• Externalities in Keyword Auctions: An Empirical and Theoretical Assessment, R. Gomes, N. Immorlica and E. Markakis, in Proc. 5th Workshop on Ad Auctions (2009). (PDF)
• On Expressing Value Externalities in Position Auctions. Florin Constantin, Malvika Rao, Chien-Chung Huang, and David C. Parkes. AAAI-11.

Advertising markets

Sponsored search

• Methodology for Designing Reasonably Expressive Mechanisms with Application to Ad Auctions. Benisch, M., Sadeh, N., and Sandholm, T. In Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI). (PDF)
• Multi-Keyword Sponsored Search. Peerapong Dhangwatnotai. EC-11.
• Reserve Prices in Internet Advertising Auctions: A Field Experiment. Michael Ostrovsky and Michael Schwarz. EC-11.
• Machine Learning in an Auction Environment. International Conference on the World Wide Web (WWW), 2014. Hummel, P. and McAfee, P.
• On Expressing Value Externalities in Position Auctions. Florin Constantin, Malvika Rao, Chien-Chung Huang, and David C. Parkes. AAAI-11.
• Computational analysis of perfect-information position auctions, D. Thompson and K. Leyton-Brown, in Proc. ACM EC'09, 2009. (PDF)
• Position Auctions with Budgets: Existence and Uniqueness. By Itai Ashlagi, Mark Braverman, Avinatan Hassidim, Ron Lavi, and Moshe Tennenholtz.Draft 2009. (PDF)
• Is Efficiency Expensive? Roughgarden, T. and Sundararajan, M. 3rd Workshop on Sponsored Search, 2007. (PDF)
• H. Varian. Position Auctions To appear in International Journal of Industrial Organization. (A theoretical and empirical analysis of the search keyword auction used by Google and Yahoo.) (PDF)
• Internet Advertising and the Generalized Second Price Auction: Selling Billions of Dollars Worth of Keywords. By M. Schwartz, B. Edelman and M. Ostrovsky. (PDF)
• Optimize-and-Dispatch Architecture for Expressive Ad Auctions by David C. Parkes and Tuomas Sandholm. In the Proceedings of First Workshop on Sponsored Search Auctions, 2005. (PDF)
• J. Tomlin, Z. Abrams and O. Mendelevitch. Optimal delivery of sponsored search advertisements subject to budget constraints. In Proc. ACM Conference on Electronic Commerce (EC'07), pp. 272-278, 2007. (PDF)
• Externalities in Keyword Auctions: An Empirical and Theoretical Assessment, R. Gomes, N. Immorlica and E. Markakis, in Proc. 5th Workshop on Ad Auctions (2009). (PDF)
• Sponsored search auctions with Markovian users, G. Aggarwal, J. Feldman, S. Muthukrishnan, and M. Pal. In Proc. 4th Workshop on Ad Auctions (2008). (PDF)
• Sponsored Search with Contexts. Eyal Even-Dar, Michael Kearns, and Jennifer Wortman. WWW-07.
• Bid Optimization for Broad Match Ad Auctions. Eyal Even-Dar, Yishay Mansour, Vahab S. Mirrokni, S. Muthukrishnan, Uri Nadav. WWW-09.
• Sponsored Search Auctions. Lahaie, S., Pennock, D., Saberi, A., and Vohra, R. Chapter 28 of the book Algorithmic Game Theory, 2007. (PDF)

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

• When Does Improved Targeting Increase Revenue? International Conference on the World Wide Web (WWW), 2015. Hummel, P. and McAfee, P.
• Display Advertising Auctions with Arbitrage. Transactions in Economics and Computation, to appear. Cavallo, R, McAfee, P., and Vassilvitskii, S.
• To Match or Not to Match: Economics of Cookie Matching in Online Advertising, Transactions in Economics and Computation, To Appear (with Arpita Ghosh, Mohammad Mahdian and Sergei Vassilvitskii).
• Signaling schemes for revenue maximization. Emek, Y., Feldman, M., Gamzu, I., Paes Leme, R., and Tennenholtz, M. EC-12.
• Send Mixed Signals – Earn More, Work Less. Miltersen, P., and Sheffet, O. EC-12.
• Revenue Maximization via Hiding Item Attributes. Guo, M. and Deligkas, A. IJCAI-13.
• Yield Optimization of Display Advertising with Ad Exchange. Santiago Balseiro, Jon Feldman, Vahab Mirrokni, and S. Muthukrishnan. Extended version of EC-11 paper.

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

• Automated Channel Abstraction for Advertising Auctions. Walsh, W., Boutilier, C., Sandholm, T., Shields, R., Nemhauser, G., and Parkes, D. In Proceedings of the Ad Auctions Workshop, 2009. (PDF)
• Near Optimal Online Algorithms and Fast Approximation Algorithms for Resource Allocation Problems. Nikhil Devanur, Kamal Jain, Balasubramanian Sivan, and Christopher A. Wilkens. EC-11.
• Boutilier, C., Parkes, D., Sandholm, T., and Walsh, W. 2008. Expressive Banner Ad Auctions and Model-Based Online Optimization for Clearing. In Proceedings of the National Conference on Artificial Intelligence (AAAI). (PDF)
• Optimize-and-Dispatch Architecture for Expressive Ad Auctions by David C. Parkes and Tuomas Sandholm. In the Proceedings of First Workshop on Sponsored Search Auctions, 2005.(PDF)

TV advertising, print ads, etc.

• Google's auction for TV ads, N. Nisan et al., ICALPS 2009. (PDF). (This auction has been discontinued.)
• Pricing guidance in ad sale negotiations: The PrintAds example, A. Juda, S. Muthukrishnan and A. Ratogi, in 3rd. Int. W. on Data Mining and Audience Intelligence for Advertising, 2009. (PDF)

Core-selecting combinatorial auctions

• New Core-Selecting Payment Rules with Better Fairness and Incentive Properties. Benjamin Lubin, Benedikt Bünz, and Sven Seuken. August 2015. [pdf]
• A Faster Core Constraint Generation Algorithm for Combinatorial Auctions. Benedikt Bünz, Sven Seuken, and Benjamin Lubin. AAAI Conference on Artificial Intelligence (AAAI), 2015. [pdf]
• Envy Quotes and the Iterated Core-Selecting Combinatorial Auction. Abe Othman and Tuomas Sandholm. In Proceedings of the National Conference on Artificial Intelligence (AAAI), 2010.
• Core-Selecting Package Auctions. Robert Day and Paul Milgrom. International Journal of Game Theory, 36, 2008, 393-407
• Optimal Incentives in Core-Selecting Auctions. Robert Day and Paul Milgrom, 8/25/2010. In the Handbook of Market Design, Oxford University Press.
• Fair Payments for Efficient Allocations in Public Sector Combinatorial Auctions. Robert Day and S. Raghavan. Management Science. 53(9), September 2007, pp. 1389-1406. PDF.
• Core-Selecting Auctions with Incomplete Information. Lawrence M. Ausubel and Oleg V. Baranov. Draft, August 2010.

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

• A General Framework for Clearing Auction of Wireless Spectrum. Sorabh Gandhi, Chiranjeeb Buragohain, Lili Cao, Haitao Zheng and Subhash Suri. IEEE DySPAN'07, 2007.

Distributed implementation

• MDPOP: Faithful Distributed Implementation of Efficient Social Choice Problems by Adrian Petcu, Boi Faltings, and David C. Parkes. In the Proc. 5th International Joint Conference on Autonomous Agents and Multiagent Systems(AAMAS), pages 1397-1404, 2006.(PDF)
• Specification Faithfulness in Networks with Rational Nodes by Jeffrey Shneidman and David C. Parkes. In the Proc. 23rd ACM Symp. on Principles of Distributed Computing (PODC), St. John's, Canada, pages 88-97, 2004.(PDF)
• Distributed computing meets game theory: robust mechanisms for rational secret sharing and multiparty computation, Proceedings of the Twenty-Fifth Annual ACM Symposium on Principles of Distributed Computing, 2006, pp. 53-62 (J. Halpern, I. Abraham, D. Dolev, and R. Gonen). (PDF)
• Rational secret sharing and multiparty computation, Proceedings of 36th ACM Symposium on Theory of Computing, 2004, pp. 623-632 (J. Halpern and V. Teague). (PDF)
• J. Feigenbaum, C. Papadimitriou, R. Sami, and S. Shenker, A BGP-based Mechanism for Lowest-Cost Routing, Distributed Computing 18 (2005), pp. 61-72. (PDF)
• J. Feigenbaum, M. Schapira, and S. Shenker, Distributed Algorithmic Mechanism Design, to appear in Algorithmic Game Theory, Cambridge University Press, 2007. (PDF)

Privacy in mechanism design

• Selling Privacy at Auction. Arpita Ghosh and Aaron Roth. EC-11.
• Efficiency and Privacy Tradeoffs in Mechanism Design. Xin Sui and Craig Boutilier. AAAI-11.
• Brandt, F. and Sandholm, T. 2008.On the Existence of Unconditionally Privacy-Preserving Auction Protocols. ACM Transactions on Information and System Security.(PDF)
• Brandt, F. and Sandholm, T. 2005. Unconditional Privacy in Social Choice. In Proceedings of the Theoretical Aspects of Reasoning about Knowledge (TARK) conference.
• Brandt, F. and Sandholm, T. Efficient Privacy-Preserving Protocols for Multi-Unit Auctions. International Conference on Financial Cryptography and Data Security (FC), LNCS 3570. (PDF)
• Brandt, F. and Sandholm, T. 2005. Decentralized Voting with Unconditional Privacy. AAMAS-05.(PDF)
• Brandt, F. and Sandholm, T. 2004. On Correctness and Privacy in Distributed Mechanisms In Proceedings of the Agent-Mediated Electronic Commerce(AMEC) workshop, Springer LNAI 3937. (PDF)
• Sergei Izmalkov, Matt Lepinski and Silvio Micali. 2005. Rational Secure Computation and Ideal Mechanism Design. FOCS. Relies on a ballot box.
• Practical Secrecy-Preserving, Verifiably Correct and Trustworthy Auctions by David C. Parkes, Michael O. Rabin, Stuart M. Shieber, and Christopher Thorpe., In Electronic Commerce Research and Applications, 2007, to appear. (PDF)
• Cryptographic Securities Exchanges by Christopher Thorpe and David C. Parkes. In Proc. International Conference on Financial Cryptography and Data Security, 2007.

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

• Leveled commitment contracts and strategic breach, Sandholm, T. and Lesser, V., Games and Economic Behavior, 2001 (PDF)
• Surplus Equivalence of Leveled Commitment Contracts. Sandholm, T. and Zhou, Y., Artificial Intelligence 142, 239-264, 2002. (PDF)
• Algorithms for optimizing leveled commitment contracts Sandholm-Sikka-Norden IJCAI-99 (PS)
• Efficient Mechanisms with Risky Participation. Cavallo, R.. IJCAI-11. (Could this be applied to make leveled commitment contracts work without knowledge of possible futures?)

Coalition formation

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

• Rahwan, T., Michalak, T., Wooldridge, M., Jennings, N. Coalition structure generation: A survey. Artificial Intelligence 229: 139–174, 2015.
• Minimum Search To Establish Worst-Case Guarantees in Coalition Structure Generation. Talal Rahwan, Tomasz Michalak, and Nicholas R. Jennings. IJCAI-11.
• Coalition structure generation with worst case guarantees. Sandholm et al AIJ-99 (PDF)
• Computing Shapley values, manipulating value division schemes, and checking core membership in multi-issue domains. In Proceedings of the National Conference on Artificial Intelligence (AAAI), pp. 219-225, 2004. Conitzer and Sandholm.(PDF)
• Marginal Contribution Nets: A Compact Representation Scheme for Coalitional Games. S. Ieong, Y. Shoham., EC-05. (PDF)
• Complexity of Constructing Solutions in the Core Based on Synergies Among Coalitions. Artificial Intelligence, 170: 607-619, 2006, Conitzer and Sandholm. (PDF)
• Coalition formation among agents whose computation is costly. Sandholm & Lesser AIJ-97 (PDF)
• Sharing the cost of multicast transmissions. Feigenbaum et al. (PDF)
• Coalition-proof implementation via LP duality. Vazirani et al
• Yokoo, M., Conitzer, V., Sandholm, T., Ohta., N., and Iwasaki, A., 2005. Coalitional Games in Open Anonymous Environments. In Proceedings of the National Conference on Artificial Intelligence (AAAI), Pittsburgh, PA. (PDF)
• Ohta, N., Iwasaki, A., Yokoo, M., Maruono, K., Conitzer, V., and Sandholm, T., 2006. A Compact Representation Scheme for Coalitional Games in Open Anonymous Environments. In Proceedings of the National Conference on Artificial Intelligence (AAAI). (PDF)

Social networks and multi-level marketing

• Mechanisms for Multi-Level Marketing. Yuval Emel, Ron Kardi, Moshe Tennenholtz, and Aviv Zohar. EC-11.

Safe exchange

• Incentive-Compatible Escrow Mechanisms. Jens Witkowski, Sven Seuken, and David C. Parkes. AAAI-11.
• Sandholm, T. and Wang, X. 2002. (Im)possibility of Safe Exchange Mechanism Design. National Conference on Artificial Intelligence (AAAI). (PDF)
• Safe exchange planner, Sandholm-Ferrandon ICMAS-00 (PDF)
• Defection-free exchange mechanisms for information goods Yokoo ICMAS-00 (IEEE Link)
• Cryptographic safe exchange techniques
• Automated escrow services

Best-response auctions

• Best-Response Auctions.  Noam Nisan, Michael Schapira, Gregory Valiant, and Aviv Zohar. EC-11.

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

• "Manipulation-Resistant Reputation Systems", by Friedman/Resnick/Sami., Chapter 27 of the book Algorithmic Game Theory, Nisan, Roughgarden, Tardos, and Vazirani (eds.),Cambridge University Press, 2007. (PDF)
• R. Jurca and B. Faltings. Collusion Resistant, Incentive Compatible Feedback Payments. Proceedings of the ACM Conference on E-Commerce (EC'07), pp. 200-209, 2007. (PDF)
• R. Jurca and B. Faltings. Minimum Payments that Reward Honest Reputation Feedback. Proceedings of the ACM Conference on Electronic Commerce (EC2006), pp.190-199, 2006. (PDF)
• "Combinatorial auctions with false-name bidders" (Yokoo’s chapter in the MIT Press book Combinatorial Auctions, 2006)

Cost sharing

• Mehta, Roughgarden, and Sundararajan, Beyond Moulin Mechanisms, EC '07. (PDF)

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

• Vasilis Syrgkanis, Eva Tardos. Composable and Efficient Mechanisms, Symposium on the Theory of Computing, STOC'13.
• Entire section on this in the book Algorithmic Game Theory (PDF)
• How bad is selfish routing? Roughgarten & Tardos, 2001. (PDF)

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