COURSE: CS 15-892 Foundations of Electronic Marketplaces
course covers classic and state-of-the-art results on computational and
game-theoretic questions related to electronic marketplaces.
Tuomas Sandholm (email@example.com)
This page: http://www.cs.cmu.edu/~sandholm/cs15-892F09/cs15-892.htm
Class times: TuTh 10:30-11:50 am, in Gates Hillman
Center (GHC) room 4211.
Instructor’s office hour: Tu noon-1 pm, GHC 9205.
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.
by Prof. Sandholm. In addition,
guest lectures by outside experts.
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
homework assignments, which will mostly consist of analytical
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. 2-page
project plans are due on October 27th 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 3rd (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
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
General review articles
in Mechanism Design. by T.
Sandholm. In the New Palgrave Dictionary in Economics, 2008.
Computational Mechanism Design (PDF) 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.
Combinatorial Auctions (a survey) by Blumrosen
and Nisan. Chapter 11 of the book Algorithmic Game Theory.
Theory” by Lawrence Ausubel. To
appear in the New Palgrave Dictionary of
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.
University Press, 1995. (Includes the Myerson-Satterthwaite
theorem, but does not cover virtual implementation).
Review article [Parkes
for this article]
Review article [Maskin & Sjostrom
01] (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
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.
Proofs for Roberts' Theorem. By 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,
and William R. Zame, Econometrica, 2006.
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 an addendum.
Paths, Cycles and Mechanism Design , by
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
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]
Mechanism Design for Multi-Dimensional Scheduling via Cycle Monotonicity.
By Ron Lavi and Chaitanya Swamy In
Auctioning a single item
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 [Wolfstetter 94]
Advanced material on non-private value auctions
[Dasgupta & Maskin QJE-00], [Jehiel & Moldovanu 1998]
Optimal (offline) clearing of multi-item and/or multi-unit
determination algorithms. Chapter 14 of the Combinatorial Auctions book.
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
CABOB: A fast optimal algorithm for
combinatorial auctions [Sandholm et al
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
Computational complexity of clearing exchanges
with supply-demand curves [Sandholm-Suri ISAAC-01]
Computational complexity of clearing multi-unit
Fast Vickrey-Clarke-Groves computation in
networks [Suri-Hirschberg FOCS-01]
Expressiveness of mechanisms
Benisch, M., Sadeh, N.,
and Sandholm, T. A Theory of Expressiveness in Mechanisms. AAAI-08.
Milgrom, P. 2009. Simplified
mechanisms with applications to Sponsored Search and Package Auctions,
Games and Economic Behavior, forthcoming.
Multi-stage market designs with preference elicitation
in combinatorial auctions [Sandholm-Boutilier
Chapter 10 in the book “Combinatorial Auctions”, 2006]
auctions (iBundle etc.) [Parkes’s
chapter in the forthcoming book “Combinatorial Auctions” 2006] [OLD:
The Communication Requirements of Combinatorial
Allocation Problems. By Ilya Segal,
Chapter 11 of the book Combinatorial
Ascending Price Vickrey Auctions for
General Valuations (PDF)
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
Communication complexity of approximate set packing
and covering [Nisan
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) In Annals of Mathematics and AI 44, 2005,
Automated mechanism design
Work on the
Sandholm, T., Conitzer, V., and Boutilier,
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.
Work on auctions, other selling
Likhodedov, A. and
Sandholm, T. 2005. Approximating Revenue-Maximizing Combinatorial Auctions.
In Proceedings of the National Conference on Artificial
Intelligence (AAAI), Pittsburgh,
Likhodedov, A. and Sandholm, T. 2004. Methods
for Boosting Revenue in Combinatorial Auctions. In
Proceedings of the National Conference on
Artificial Intelligence (AAAI), pp. 232-237, San Jose, California.
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,
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. (Early version in Proceedings of the AAMAS
workshop on Agent-Mediated Electronic Commerce (AMEC V), Melbourne, Australia,
On approximating optimal auctions [Ronen
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. [PS]
R. Jurca and B.
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. [PS]
Auction and exchange design without priors
Mechanism Design via
Machine Learning. JCSS, 2008.
Competitive generalized auctions [Fiat, Goldberg, Hartline,
Truthful and Competitive Double Auctions [Deshmukh,
Goldberg, Hartline, Karlin]
Pricing without demand curves [Segal, American Economic Review]
Market research and Market Design [Vohra &
from Nisan’s course)]
Incentive-compatible (IC) approximation by the auctioneer
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
On the Power of
Randomization in Algorithmic Mechanism Design, FOCS-09. Shahar Dobzinski and Shaddin Dughmi.
Mechanisms for Combinatorial Auctions by S. Dobzinski, N. Nisan, and M.
Schapira. STOC 2006.
Mechanisms, By Moshe Babaioff, Ron
Lavi, and Elan Pavlov, AAAI-06.
Two Randomized Mechanisms
for Combinatorial Auctions by S. Dobzinski, APPROX-08.
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
Auctions. Cavallo and Parkes,
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
Valuation complexity explains last-minute
bidding [Eric Rasmusen draft-03]
Computationally feasible VCG mechanism [Nisan-Ronen 00] (This paper contains the second-chance
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
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.
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. [download]
Friedgut, G. Kalai, and N. Nisan. 2007. Elections can be Manipulated Often.
mechanisms for the auctioneer
Online Mechanisms, by David Parkes. Chapter 16 of the book Algorithmic Game Theory.
· Self-Correcting Sampling-Based Dynamic Multi-Unit Auctions. By Florin Constantin and David C.
Parkes. Bonn workshop on mechanism
Sampling-Based Dynamic Multi-Unit Auctions. B
About The Future and Dynamic Efficiency, Alex Gershkov and Benny
Moldovanu, forthcoming in American Economic Review.
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.
Dynamic Marginal Contribution Mechanisms. Dirk Bergemann and Juuso Välimäki. Mimeo, 2007.
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
algorithms for clearing exchanges [Blum-Sandholm-Zinkevich
Online Mechanism Design and Prophet Inequalities. Hajiaghayi, M., Kleinberg, R., and Sandholm, T. AAAI-07.
Ironing-Based Approach to Adaptive Online Mechanism Design in Single-Valued
A dynamic double auction framework (PDF) In Journal
of Artificial Intelligence Research, 2007, to appear.
Competitive Analysis of Incentive Compatible On-Line
Auctions by Ron Lavi and Noam Nisan. Theoretical Computer Science 310(1),
pp. 159-180, 2004.
auctions with reusable goods [Hajiaghayi et al. EC-05]
truth-telling online mechanisms to online optimization [Awerbuch et al.
learning in online auctions [Blum et al. SODA-03]
WiFi at Starbucks: Issues in online mechanism design [Friedman & Parkes
limited-supply online auctions [Hajiaghayi et al. EC-04]
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.
price of truth: frugality in truthful mechanisms [Talwar STOC-03]
exciting topics (which we will probably not have time to cover in class)
Faithful Distributed Implementation of Efficient Social Choice Problems (PDF) In the Proc. 5th
International Joint Conference on Autonomous Agents and Multiagent Systems
(AAMAS'06), pages 1397-1404, 2006.
Faithfulness in Networks with Rational Nodes (PDF) In the Proc. 23rd ACM
Symp. on Principles of Distributed Computing (PODC'04), St. John's, Canada,
pages 88-97, 2004.
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).
Rational secret sharing and multiparty computation,
Proceedings of 36th ACM Symposium on Theory of Computing, 2004, pp.
623-632 (J. Halpern and V. Teague).
Feigenbaum, C. Papadimitriou, R. Sami, and S. Shenker, “A BGP-based Mechanism
for Lowest-Cost Routing,” Distributed
Computing 18 (2005), pp. 61 -
Feigenbaum, M. Schapira, and S. Shenker, “Distributed Algorithmic Mechanism
Design,” to appear in Algorithmic Game
Theory, Cambridge University Press, 2007.
markets (e.g., sponsored search auctions, display ad markets, TV ad markets,
print ad markets)
Sponsored Search Auctions, by
Lahaie/Pennock/Saberi/Vohra. Chapter 28 of the book Algorithmic
Game Theory, 2007.
W., Boutilier, C., Sandholm, T., Shields, R., Nemhauser, G., and Parkes,
Automated Channel Abstraction for Advertising Auctions. In Proceedings of the Ad Auctions Workshop.
M., Sadeh, N., and Sandholm, T.
2009. Methodology for Designing Reasonably Expressive Mechanisms
with Application to Ad Auctions. In Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI).
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).
Google's auction for TV ads, N. Nisan et
al., ICALPS 2009
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.
Computational analysis of perfect-information position
auctions, D. Thompson and K. Leyton-Brown, in Proc. ACM
Position Auctions with Budgets: Existence and Uniqueness. By Itai Ashlagi, Mark Braverman, Avinatan
Hassidim, Ron Lavi, and Moshe Tennenholtz.
Roughgarden and M. Sundararajan, Is Efficiency Expensive?, 3rd
Workshop on Sponsored Search, 2007.
Varian. Position Auctions [PDF] To appear in International
Journal of Industrial Organization. (A theoretical and empirical analysis
of the search keyword auction used by Google and Yahoo.)
Internet Advertising and the Generalized Second Price
Auction: Selling Billions of Dollars Worth of Keywords. By M. Schwartz, B. Edelman and M. Ostrovsky.
Architecture for Expressive Ad Auctions (PDF) In the Proceedings of
First Workshop on Sponsored Search Auctions, 2005.
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).
Sponsored search auctions with Markovian users,
G. Aggarwal, J. Feldman, S. Muthukrishnan, and M. Pal. In Proc. 4th Workshop on
Ad Auctions (2008).
OTHER PAPERS, e.g., on bid optimization
in mechanism design
F. and Sandholm, T. 2008. On the Existence of Unconditionally Privacy-Preserving
Auction Protocols. ACM Transactions on Information and System
F. and Sandholm, T. 2005. Unconditional Privacy in Social Choice. In Proceedings of the Theoretical Aspects of Reasoning about
Knowledge (TARK) conference.
F. and Sandholm, T. 2005. Efficient Privacy-Preserving Protocols for Multi-Unit
Auctions. International Conference on Financial
Cryptography and Data Security (FC), LNCS 3570.
F. and Sandholm, T. 2005. Decentralized Voting with Unconditional Privacy. AAMAS-05.
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.
Izmalkov, Matt Lepinski and Silvio Micali.
2005. Rational Secure Computation and Ideal Mechanism Design.
Relies on a ballot box.
Secrecy-Preserving, Verifiably Correct and Trustworthy Auctions (PDF) In Electronic Commerce
Research and Applications, 2007, to appear.
Securities Exchanges (PDF)
In Proc. International
Conference on Financial Cryptography and Data Security, 2007.
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
Gandhi, Chiranjeeb Buragohain, Lili Cao, Haitao Zheng and Subhash Suri. IEEE
contract types (“It’s not the figures lying, it’s the liars figuring”)
commitment contracts and strategic breach [Sandholm-Lesser GEB 2001]
T. and Zhou, Y. 2002. Surplus Equivalence of Leveled Commitment Contracts. Artificial Intelligence 142, 239-264.
for optimizing leveled commitment contracts [Sandholm-Sikka-Norden IJCAI-99]
Nash equilibrium (what’s the price of anarchy?)
section on this in the book Algorithmic
[Koutsoupias & Papadimitriou]
bad is selfish routing? [Roughgarten & Tardos]
core, Shapley value, Sandholm’s network routing example, iterative payoff
structure generation [Sandholm et al AIJ-99]
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
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.
formation among agents whose computation is costly [Sandholm&Lesser AIJ-97]
the cost of multicast [Feigenbaum et al]
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,
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
T. and Wang, X. 2002. (Im)possibility of Safe Exchange Mechanism Design.
National Conference on Artificial Intelligence (AAAI).
exchange planner [Sandholm-Ferrandon ICMAS-00]
exchange mechanisms for information goods [Yokoo ICMAS-00]
safe exchange techniques
systems (these systems are prevalent - e.g., eBay - but they are all
Manipulation-Resistant Reputation Systems,
by Friedman/Resnick/Sami. Chapter 27 of the book
Game Theory, Nisan, Roughgarden, Tardos, and Vazirani (eds.),
Cambridge University Press, 2007.
Jurca and B. Faltings. Collusion Resistant, Incentive Compatible Feedback Payments.
Proceedings of the ACM Conference on E-Commerce (EC'07), pp. 200-209,
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. [PS]
agent for general equilibrium markets [Sandholm-Ygge 99]
with deadlines [Extended version of Sandholm-Vulkan AAAI-99]
auctions with false-name bidders [Yokoo’s chapter in the MIT Press book
“Combinatorial Auctions”, 2006]
T. Roughgarden, and M. Sundararajan, Beyond Moulin Mechanisms, EC '07.
markets (there are lots of papers on this topic from several decades; ask me
for more), and especially kidney exchange
P. and Sandholm, T. 2009. Online Stochastic Optimization in the Large: Application to
In Proceedings of the International
Joint Conference on Artificial Intelligence (IJCAI).
Unver. Dynamic Kidney Exchange, Review of Economic Studies,
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,
A Nonsimultaneous, Extended, Altruistic-Donor Chain. New
England Journal of Medicine 360(11), 1096-1101.
Abraham, D., Blum, A., and Sandholm, T. 2007. Clearing Algorithms for Barter Exchange Markets: Enabling
Nationwide Kidney Exchanges.
In Proceedings of the ACM
Conference on Electronic Commerce (EC).
Roth’s Game Theory, Experimental Economics, and Market Design Page.
- Sep 8: 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 10: 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 15: Guest lecture by Abe Othman: Prediction
markets. Read Chapter 26 of Algorithmic Game Theory.
- Sep 17: Guest lecture by Abe Othman: Prediction
- Sep 22: NO CLASS: Gates Hillman Complex Opening
- Sep 24: 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 29: Mechanism design. Revelation principle. Dominant strategy implementation. Gibbard-Satterthwaite impossibility
theorem. Read Sections 9.2.4-9.4.3
of Algorithmic Game Theory. Slides.
- Oct 1: Groves mechanism for quasilinear
environments. Clarke tax. When do these work? When are these the only mechanisms that
work? Budget imbalance. Collusion. Read rest of Chapter 9 of Algorithmic Game Theory. Homework1 posted.
- Oct 6: More on characterizing dominant-strategy
implementation in quasilinear environments. 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: review of
network view of incentive compatibility, virtual
Bayesian implementation. Slides on characterising dominat-strategy implementability. Slides on Bayes-Nash implementation.
- Oct 8: Guest lecture by David Parkes (Harvard):
Dynamic Knapsack Auctions through Computational Ironing. Paper to read in advance.
- Oct 13: Guest lecture by Michael Benisch:
Theory of Expressiveness in Mechanisms. Slides.
- Oct 15: Sponsored search auctions. Guest lecture by Michael Benisch:
Applying Expressiveness Theory to Evaluate and Improve Efficiency in
Sponsored Search Auctions. Paper to read in advance. Guest
lecture by Amin Sayedi: Expressive Auctions for Externalities in Online Advertising.
- Oct 20:
Homework 1 due by 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 22:
More on auctioning a single item.
Revenue-maximizing (Myerson) auction. Winner’s curse. Asymmetric information.
- Oct 27:
Project proposals due (by email to Prof. Sandholm) by the beginning of class. More on auctioning a single
item. Single-crossing property and its implications. Linkage principle. Collusion. Auctions where bidders can invest
effort/computation to determine their own valuations. Homework 2 posted.
- Oct 29:
Auctions with multi-dimensional signals. Last-minute bidding (sniping) and its
strategic implications. Mobile
- Nov 3:
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.
- Nov 5:
Homework 2 due at the beginning of class. Multi-item auctions. Sequential auction
mechanisms. Parallel auction
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
- Nov 10:
Tree search-based winner determination algorithms, including MIP. Generalized Vickrey auction. Side constraints and non-price
attributes in markets.
- Nov 12:
More on tree search-based winner determination algorithms. Multi-unit combinatorial auctions. Combinatorial reverse auctions. Combinatorial exchanges. Free disposal vs. not. Complexity
of clearing these markets. Preference elicitation in combinatorial auctions. Read Chapter 10 of Combinatorial
Auctions book. Slides. Homework 3 posted.
- Nov 17:
More on preference elicitation in combinatorial auctions.
- Nov 19:
Ascending (and descending) combinatorial auctions. Primal-dual approaches. Read Chapter 2 of Combinatorial
Auctions book. Slides. Automated mechanism design. Complexity. Applications. Revenue-maximizing combinatorial auctions. Affine maximizer combinatorial
auctions. Virtual valuations
combinatorial auctions. Automated design
of multi-stage mechanisms. Slides. (Other
related topics we won’t have time for in this lecture: Network view of
incentive compatibility constraints; optimal mechanisms derived using that
view.) Algorithmic mechanism design, i.e., incentive-compatible
approximation by the auctioneer.
- Nov 24: Homework 3 due at the beginning of class. 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
mechanism. Assuming agents can only
solve problems that are worst-case polynomial time. Easiness of typical cases of
manipulation problems. Slides.
- Nov 26: NO CLASS: Thanksgiving break.
- Dec 1: Final project presentations.
- Dec 3: (last class): Final project
presentations. Final project
writeups due: HARD DEADLINE.
Tuomas Sandholm’s home page
Roth’s Game Theory, Experimental Economics, and Market Design Page
Roth’s Market Design Ideas Page
Parkes’s course Computational Mechanism Design at Harvard
Roth and Peter Coles’s course Market Design at Harvard
Noam Nisan’s course at Hebrew University, Israel
Utku Ünver’s course Matching Market Design at University of
Wilson’s course Market Design at Stanford
Roughgarden’s course Introduction to Algorithmic Game Theory at
Christos Papadimitriou’s course at University of California,
Joan Feigenbaum’s course at Yale University
Amy Greenwald’s course at Brown University
Yoav Shoham’s course Computer Science and Game Theory at