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

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

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

**Format: **

- Lectures by Prof. Sandholm. In addition, guest lectures by outside experts.
- 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.
- Three homework assignments, which will mostly consist of analytical questions.
- 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 20
^{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 8^{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:** 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.

__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
. (PDF)__New Palgrave Dictionary of Economics__

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

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

- Profit Maximization in Mechanism Design. By Hartline and Karlin. Chapter 13 of the book Algorithmic Game Theory. Read 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 winner determination algorithms". Chapter 14 of the Combinatorial Auctions book.
- Lehmann, D., Mueller, R., and Sandholm, T. 2006. The Winner Determination Problem. Chapter 12 of the Combinatorial Auctions book.
- 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. - A Kernel Method for Market Clearing. By Sebastien Lahaie. IJCAI-09.
- Bidding and allocation in combinatorial auctions [Nisan EC-00]
- CABOB: A fast optimal algorithm for combinatorial auctions [Sandholm et al, IJCAI-01]
- 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]
- 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]

- A Theory of Expressiveness in Mechanisms. Michael Benisch and Tuomas Sandholm. Draft, 2011. Very short early version in appeared in AAAI-08.
- Simplicity-Expressiveness Tradeoffs in Mechanism Design. Paul Dutting, Felix Fischer, and David Parkes. EC-11.
- 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. - Milgrom, P. Simplified Mechanisms with an Application to Sponsored-Search Auctions.
*Games and Economic Behavio*r, 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) - 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.

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

- 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. Self-Interested
Automated Mechanism Design and Implications for Optimal Combinatorial Auctions.In
Proceedings of the
*ACM Conference on Electronic Commerce (EC), pp. 132-141*. - 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. 2002. Complexity of Mechanism Design. In Proceedings of the
*18th Conference on Uncertainty in Artificial Intelligence (UAI)*, August 1-4, Edmonton, Canada. - 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.

- Automated Design of Revenue-Maximizing Combinatorial Auctions. Tuomas Sandholm, Anton Likhodedov, and Andrew Gilpin. Operations Research, to appear. Combines and extends over a AAAI-05 paper and a AAAI-04 paper.
- 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 - Likhodedov, A. and Sandholm, T. 2004.
__Mechanism for Optimally Trading Off Revenue and Efficiency in Multi-unit Auctions__.Short paper in proceedings of the*ACM Conference on Electronic Commerce*. Extended version. in Proceedings of the*AAMAS workshop on Agent-Mediated Electronic Commerce (AMEC V)*, Melbourne, Australia, 2003.) - On approximating optimal auctions [Ronen EC-01]
- 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.

- Mechanism Design via Machine Learning. 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)]

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

- 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 the
*Theoretical 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.)

- 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, 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, forthcoming 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, forthcoming 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]

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

__Online Stochastic Optimization in the Large: Application to Kidney Exchange__. Pranjal Awasthi and Tuomas Sandholm. In Proceedings of the*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. In Proceedings of the*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.

- 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. Automated Market-Making in the Large: The Gates Hillman Prediction Market. In Proceedings of the
*ACM Conference on Electronic Commerce (EC)*. - Othman, A., Pennock, D., Reeves, D., and Sandholm, T. 2010. A Practical Liquidity-Sensitive Automated Market Maker. In Proceedings of the
*ACM Conference on Electronic Commerce (EC)*. - 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.

- Walsh, W., Boutilier, C., Sandholm, T., Shields, R., Nemhauser, G., and Parkes, D., 2009.
__Automated Channel Abstraction for Advertising Auctions.__In Proceedings of the*Ad Auctions Workshop*. (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.
- Yield Optimization of Display Advertising with Ad Exchange. Santiago Balseiro, Jon Feldman, Vahab Mirrokni, and S. Muthukrishnan. Extended version of EC-11 paper.
- Near Optimal Online Algorithms and Fast Approximation Algorithms for Resource Allocation Problems. Nikhil Devanur, Kamal Jain, Balasubramanian Sivan, and Christopher A. Wilkens. EC-11.
- On Expressing Value Externalities in Position Auctions. Florin Constantin, Malvika Rao, Chien-Chung Huang, and David C. Parkes. AAAI-11.
- "Sponsored Search Auctions", by Lahaie/Pennock/Saberi/Vohra. Chapter 28 of the book
__Algorithmic Game Theory__, 2007. (PDF) - 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) - 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) __Google's auction for TV ads__, N. Nisan et al., ICALPS 2009 (PDF)__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)__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)- T. Roughgarden and M. Sundararajan,
__Is Efficiency Expensive?__, 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.
- OTHER PAPERS, e.g., on bid optimization

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

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

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

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

- Concordance among Holdouts. Scott Kommiers and E. Glen Weyl. EC-11.
- Many more papers exist on this topic -- ask me.

__Leveled commitment contracts and strategic breach__, Sandholm-Lesser GEB 2001 (PDF)- Sandholm, T. and Zhou, Y. 2002.
__Surplus Equivalence of Leveled Commitment Contracts.__*Artificial Intelligence*142, 239-264. (PDF) __Algorithms for optimizing leveled commitment contracts__Sandholm-Sikka-Norden IJCAI-99 (PS)- Efficient Mechanisms with Risky Participation. Ruggiero Cavallo. IJCAI-11. (Could this be applied to make leveled commitment contracts work without knowledge of possible futures?)

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

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

- 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. Noam Nisan, Michael Schapira, Gregory Valiant, and Aviv Zohar. EC-11.

- "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) __Constructing Speculative Demand Functions in Equilibrium Markets__Sandholm-Ygge 99 (PS)__Bargaining with deadlines__(Extended version of Sandholm-Vulkan AAAI-99) (PDF)- "Combinatorial auctions with false-name bidders" (Yokoo’s chapter in the MIT Press book
__Combinatorial Auctions__, 2006)

- Mehta, T. Roughgarden, and M. Sundararajan,
__Beyond Moulin Mechanisms__, EC '07. (PDF)

- Entire section on this in the book
__Algorithmic Game Theory__(PDF) __How bad is selfish routing?__Roughgarten & Tardos, 2001. (PDF)

- Sep 13: Course organization. Introduction. Automated negotiation in different
stages of an ecommerce transaction. Utility theory. 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.
- Sep 15: 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. Bayesian games.
Bayes Nash equilibrium. Perfect Bayesian equilibrium. Sequential equilibrium. Strong Nash equilibrium.
Coalition-proof Nash equilibrium. Ex post equilibrium. Slides.
- Sep 20: 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. Read Sections 9.1-9.2.3 of
Algorithmic Game Theory Slides.
- Sep 22: Homework 1 posted. Mechanism design. Revelation principle. Dominant strategy implementation. Gibbard-Satterthwaite impossibility
theorem. Groves mechanism for quasilinear environments. Read Sections 9.2.4-9.4.3 of Algorithmic Game Theory
Slides.
- Sep 27: 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. Read rest of Chapter 9 of
Algorithmic Game Theory Slides
Additional optional readings: review of
network view of incentive compatibility.
- Sep 29: Bayes-Nash implementation in incomplete information environments. Expected externality mechanism
for quasilinear environments. Budget balance. Participation constraints. Myerson-Satterthwaite impossibility for
exchanges. Additional optional readings: virtual
Bayesian implementation. Slides.
- Oct 4: Homework 1 due in the beginning of class. 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.
Revenue equivalence theorem.
Slides.
- Oct 6: More on auctioning a single item. Revenue non-equivalence. Revenue-maximizing (Myerson) auction.
Winner’s curse. Asymmetric information.
- Oct 11: More on auctioning a single item. 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.
- Oct 13: Guest lecture: Abe Othman. Prediction markets.
Slides.

- Oct 18: Homework 2 posted. Last-minute bidding (sniping) and its
strategic implications. Mobile bidder agents. 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).
Computational complexity of clearing auctions, reverse auctions, and exchanges under the different bidding
languages - with nondiscriminatory and discriminatory pricing. Slides.

- Oct 20: Project proposals due (by email to Prof. Sandholm) by the beginning of class.Multi-item auctions. Sequential auction mechanisms. Parallel auction mechanisms. Combinatorial
auctions. Approaches to winner determination in combinatorial auctions. Bidding languages.
Read Chapter 14 of Combinatorial Auctions book. Additional optional reading: Chapter 12 of Combinatorial Auctions
book.
Slides.

- Oct 25: Guest lecture: Ariel Procaccia.
Fair division:
allocation of divisible goods (cake cutting algorithms, allocation of multiple resources under proportional demands).
- Oct 27: Guest lecture: Ariel Procaccia.
Fair division:
allocation of indivisible goods
(communication requirements of minimizing envy, algorithms for minimizing envy, negotiation protocols that converge to envy-free and efficient allocations).
- Nov 1:
Homework 2 due in the beginning of class.
Tree search-based winner determination algorithms, including mixed integer programming. Generalized Vickrey auction.
Side constraints and non-price attributes in markets.
Branch-and-cut. Cutting planes.
- Nov 3:
More on tree search-based winner determination algorithms. Deriving the Gomory mixed integer cutting plane. Problem formulations. Identifying and using decomposition (and driving toward decomposition). Branching rules.
- Nov 8:
More on tree search-based winner determination algorithms. 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.
- Nov 10:
Preference elicitation in
combinatorial auctions. Read Chapter 10 of Combinatorial Auctions book.
Slides.
- Nov 15: Guest lecture: Avrim Blum.
Machine Learning for Online Decision Making + Applications to Online Pricing. Slides.
- Nov 17:
More on preference elicitation in combinatorial auctions. Ascending (and descending) combinatorial auctions. Primal-dual approaches. Read Chapter 2 of Combinatorial
Auctions book.
Slides.
- Nov 22:
Homework 3 posted. Automated mechanism design. Complexity. Applications. Revenue-maximizing combinatorial auctions.
Affine maximizer combinatorial auctions. Virtual valuations combinatorial auctions. Automated design
of multi-stage mechanisms.
Slides.
- Nov 24: NO CLASS: Thanksgiving break.
- Nov 29:
Bidding agents with hard valuation problems. Mechanism design for such agents. Nonexistence of
incentive-compatible mechanisms. Slides. 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. Slides.
- Dec 1: Homework 3 due in the beginning of class. Final project presentations: John Dickerson, Nisarg Shah.
- Dec 6: Final project presentations: Sidd Jain, Bill Garrison, Geoff Hasker.
- Dec 8: (last class): Final project presentations: Jeremiah Blocki, Gabriel Moreno, Patrick Xia. Final project writeups due: HARD DEADLINE.

Al Roth's Game Theory, Experimental Economics, and Market Design Page

Al Roth’s Market Design Ideas Page

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