COURSE:  CS 15-892  Foundations of Electronic Marketplaces

Fall 2007

 

NOTE: the Fall 2009 version of this course is here.

 

 

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-892F07/cs15-892.htm

 

Class times: TuTh 3-4:20pm, Wean Hall 4623.

 

Instructor’s office hour: Tu 4:30-5:30pm, Wean Hall 7127.

 

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:

  1. Lectures by Prof. Sandholm.  In addition, guest lectures by international 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, to print them, and to read the paper carefully before the lecture.   There may be surprise quizzes on the readings.
  3. 3 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.  2-page project plans are due on October 11th in the beginning of class.  Students are expected to present their final projects in the last few lectures.  The writeups of the final projects are due on December 6th (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: 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.

 

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.  To appear in the New Palgrave Dictionary in Economics.

·         Computational Mechanism Design (PDF) by David C. Parkes.  In Lecture notes of Tutorials at 10th Conf. on Theoretical Aspectsof Rationality and Knowledge (TARK-05), To appear., Institute of Mathematical Sciences, University of Singapore, 2008.

·         Combinatorial Auctions (a survey) by L. Blumrosen and N. Nisan. To appear in Algorithmic Game Theory, N. Nisan, T. Roughgarden, E. Tardos and V. Vazirani, editors, to be published by Cambridge University Press.

·         “Auctions: Theory” by Lawrence Ausubel.  To appear in the New Palgrave Dictionary of Economics.

 

Basics of mechanism design

·         Nisan, N.  2007.  Introduction to Mechanism Design (for Computer Scientists). To appear in Algorithmic Game Theory, N. Nisan, T. Roughgarden, E. Tardos and V. Vazirani, editors, to be published by Cambridge University Press.

·         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] [bibliography 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.

 

Auctioning a single item

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

·         Optimal winner determination algorithms. [Sandholm’s Chapter 14 in the book “Combinatorial Auctions”, 2006]

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

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

 

Incentive-compatible (IC) approximation by the auctioneer

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

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

·         Limitations of VCG-based Mechanisms by S. Dobzinski and N. Nisan. STOC 2007.

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

·         In designing IC approximation mechanisms, it may help to know what mechanisms are IC:

·         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. To appear in Econometrica.

·         Weak monotonicity suffices for truthfulness on convex domains [Saks & Yu EC-05]

·         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. By Ron Lavi and Chaitanya Swamy  In EC-07.

 

Automated mechanism design

            Work on the general problem

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

Work on auctions, other selling mechanisms, etc.

·         Likhodedov, A. and Sandholm, T.  2005.  Approximating Revenue-Maximizing Combinatorial Auctions. In Proceedings of the National Conference on Artificial Intelligence (AAAI), Pittsburgh, PA.

·         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, 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.  (Early version in Proceedings of the AAMAS workshop on Agent-Mediated Electronic Commerce (AMEC V), Melbourne, Australia, 2003.)

·         Mechanism design via machine learning.  By M. Balcan, A. Blum, J. Hartline, and Y. Mansour.  FOCS-05.  Paper.

·         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. [PS]

·         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. [PS]

 

Auction and exchange design without priors

·         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-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 forthcoming book “Combinatorial Auctions” 2006] [OLD: Parkes ACM-EC-99, AAAI-00a, AAAI-00b]

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

 

Bidding agents with hard valuation problems

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

·         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

·         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. [download]

·         E. Friedgut, G. Kalai, and N. Nisan.  2007.  Elections can be Manipulated Often.  Draft.

Online mechanisms for the auctioneer

·         Online Mechanisms, by David C. Parkes.  In Algorithmic Game Theory, Noam Nisan, Tim Roughgarden, Eva Tardos, and Vijay Vazirani (eds.) , Chapter 16, Cambridge University Press, 2007, to appear.

·         Online algorithms for clearing exchanges [Blum-Sandholm-Zinkevich JACM, 2006]

·         Hajiaghayi, M., Kleinberg, R., and Sandholm, T.  2007.  Automated Online Mechanism Design and Prophet Inequalities.  In Proceedings of the National Conference on Artificial Intelligence (AAAI).

·          An Ironing-Based Approach to Adaptive Online Mechanism Design in Single-Valued Domains (PDF)  by David C. Parkes and Quang Duong.
In the Proc. 22nd National Conference on Artificial Intelligence (AAAI'07), 2007.

·         Chain: A dynamic double auction framework (PDF) by Jonathan Bredin, David C. Parkes, and Quang Duong. In Journal of Artificial Intelligence Research, 2007, to appear.

·         Competitive analysis of incentive-compatible online auctions [Lavi-Nisan EC-00]

·         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 [Parkes and Singh NIPS-03]

·         The price of truth: frugality in truthful mechanisms [Talwar STOC-03]

 

 

Related exciting topics (which we will probably not have time to cover in class)

 

Privacy in mechanism design

·         Brandt, F. and Sandholm, T. 2008.  On the Existence of Unconditionally Privacy-Preserving Auction Protocols.  ACM Transactions on Information and System Security, to appear.  Conference version in AAMAS-04.

·         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. 2005. Efficient Privacy-Preserving Protocols for Multi-Unit Auctions.  In Proceedings of the International Conference on Financial Cryptography and Data Security (FC), published in Springer Lecture Notes in Computer Science LNCS 3570.

·         Brandt, F. and Sandholm, T. 2005.  Decentralized Voting with Unconditional Privacy.  In Proceedings of the International Joint Conference on Autonomous Agents and Multi-Agent Systems (AAMAS).

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

·         Sergei Izmalkov, Matt Lepinski and Silvio Micali. 2005.   Rational Secure Computation and Ideal Mechanism Design. Proceedings of the 46th Annual Symposium on Foundations of Computer Science (FOCS).  Relies on a ballot box.

·         Practical Secrecy-Preserving, Verifiably Correct and Trustworthy Auctions (PDF) by David C. Parkes, Michael O. Rabin, Stuart M. Shieber, and Christopher Thorpe.  In Electronic Commerce Research and Applications, 2007, to appear.

·         Cryptographic Securities Exchanges (PDF) by Christopher Thorpe and David C. Parkes.  In the Proc. 11th International Conference on Financial Cryptography and Data Security, Trinidad/Tobago, 2007.

 

Distributed implementation

·         MDPOP: Faithful Distributed Implementation of Efficient Social Choice Problems (PDF) by Adrian Petcu, Boi Faltings, and David C. Parkes.  In the Proc. 5th International Joint Conference on Autonomous Agents and Multiagent Systems (AAMAS'06), pages 1397-1404, 2006.

·         Specification Faithfulness in Networks with Rational Nodes (PDF) by Jeffrey Shneidman and David C. Parkes. 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).

·         J. Feigenbaum, C. Papadimitriou, R. Sami, and S. Shenker, “A BGP-based Mechanism for Lowest-Cost Routing,” Distributed Computing 18 (2005), pp. 61 - 72.  FPSS.pdf

·         J. Feigenbaum, M. Schapira, and S. Shenker, “Distributed Algorithmic Mechanism Design,” to appear in Algorithmic Game Theory, Cambridge University Press, 2007.

 

Sponsored search (e.g., search keyword auctions and banner ad markets; Google, Yahoo!, MSN,…)

·         Sponsored Search Auctions, by Lahaie/Pennock/Saberi/Vohra. Chapter 28 of the book Algorithmic Game Theory, to appear.

·         T. Roughgarden and M. Sundararajan, Is Efficiency Expensive?, 3rd Workshop on Sponsored Search, 2007.

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

·         Optimize-and-Dispatch Architecture for Expressive Ad Auctions (PDF) by David C. Parkes and Tuomas Sandholm. In the Proceedings of First Workshop on Sponsored Search Auctions, 2005.

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

·         OTHER PAPERS, e.g., on bid optimization

 

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.

 

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

·         Leveled commitment contracts and strategic breach [Sandholm-Lesser GEB 2001]

·         Sandholm, T. and Zhou, Y. 2002. Surplus Equivalence of Leveled Commitment Contracts.  Artificial Intelligence 142, 239-264.

·         Algorithms for optimizing leveled commitment contracts [Sandholm-Sikka-Norden IJCAI-99]

 

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

·         See entire section on this in the book Algorithmic Game Theory, 2007, to appear.

·         [Koutsoupias & Papadimitriou]

·         How bad is selfish routing?  [Roughgarten & Tardos]

 

 Coalition formation

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

·         Coalition structure generation [Sandholm et al AIJ-99]

·         Conitzer, V. and Sandholm, T. 2004.  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.

·         Marginal Contribution Nets: A Compact Representation Scheme for Coalitional Games. S. Ieong, Y. Shoham.  EC-05. [PDF]

·         Conitzer, V. and Sandholm, T. 2003. Complexity of Determining Nonemptiness of the Core.  International Joint Conference on Artificial Intelligence (IJCAI).

·         Coalition formation among agents whose computation is costly [Sandholm&Lesser AIJ-97]

·         Sharing 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, PA.

 

 Safe exchange

·         Sandholm, T. and Wang, X. 2002. (Im)possibility of Safe Exchange Mechanism Design. National Conference on Artificial Intelligence (AAAI).

·         Safe exchange planner [Sandholm-Ferrandon ICMAS-00]

·         Defection-free exchange mechanisms for information goods [Yokoo ICMAS-00]

·         Cryptographic safe exchange techniques

·         Automated escrow services

 

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, to appear.

·         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. 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. [PS]

 

Speculator agent for general equilibrium markets [Sandholm-Ygge 99]

 

Bargaining with deadlines [Extended version of Sandholm-Vulkan AAAI-99]

 

Combinatorial auctions with false-name bidders [Yokoo’s chapter in the MIT Press book “Combinatorial Auctions”, 2006]

 

Cost sharing

·         Mehta, T. Roughgarden, and M. Sundararajan, Beyond Moulin Mechanisms, EC '07.

 

Matching markets (there are lots of papers on this topic from several decades; ask me for more)

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

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

 

 

Course schedule (this will change during the semester)

 

  1. Sep 11: 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 regarding the topics in this course.   
  2. Sep 13: Extensive form and matrix form representations of games.  Solution concepts from noncooperative game theory.  Dominant strategy equilibrium.  Nash equilibrium.  Mixed strategy Nash equilibrium.  Subgame perfect equilibrium and credible threats. Software as a commitment device.  Other solution concepts.  Slides.  Homework 1 posted (to get the definitions related to iterated dominance, read Section 2 of this EC-05 paper).
  3. Sep 18:  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).  Slides.  Book chapter to read regarding social choice and mechanism design.   Three short proofs of Arrow’s theorem.
  4. Sep 20:  Mechanism design.  Revelation principle.  Dominant strategy implementation.  Gibbard-Satterthwaite impossibility theorem.  Slides.
  5. Sep 25:   Homework 1 due.  Groves mechanism for quasilinear environments.  Clarke tax.  When do these work?  When are these the only mechanisms that work?  Budget imbalance.  Collusion.
  6. Sep 27:    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.  Slide set 1.  Slide set 2.  Read rest of Noam’s book chapter.  Optional readings: review of network view of incentive compatibility, virtual Bayesian implementation.
  7. Oct 2:  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.  Formal proof of revenue equivalence.
  8. Oct 4:  More on auctioning a single item.  Revenue non-equivalence.  Revenue-maximizing (Myerson) auction.  Winner’s curse.  Asymmetric information.  Homework 2 posted.

·         Optional talk: Nicole Immorlica (CWI/Northwestern): “Balloon Popping with Applications to Ascending Auctions”, Friday October 5th, 3:30-4:30pm, Wean Hall 7200.

 

  1. Oct 9: More on auctioning a single item.  Collusion.  Auctions where bidders can invest effort/computation to determine their own valuations.  Last-minute bidding (sniping) and its strategic implications.  Mobile bidder agents. 
  2. Oct 11:  Project proposals due (by email to Prof. Sandholm).    Ecommerce research morning (9am-1pm) in McConomy auditorium, University Center.  NOTE UNUSUAL TIME AND PLACE (no class at the regular time).  Agenda:

·         9.00: Coffee

·         9.30: Welcome and Introduction.  Johannes Elling, Carnegie Bosch Institute and R Ravi, Tepper School of Business, Carnegie Bosch Professor.

·         9.45: Neel Sundaresan, Sr. Director and Head - Research Labs, eBay: "Community Computing: Tackling the Finding Challenge by its Long Tail".

·         10.45: Kourosh Gharachorloo, Traffic Quality Team, Google: "Click Fraud - Anecdotes from the Frontline"

·         11.45: Coffee Break

·         12.00: Prabhakar Raghavan, Head of Yahoo! Research: "The Web Economy and its Relevance to the Intersection of Computer Science and Economics".

·         For more information and registration, please visit http://www.tepper.cmu.edu/cbiconference or email ekrall@andrew.cmu.edu.

  1. Oct 16:   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. [Sandholm-Suri ISAAC-02 (this version is actually a bit extended from ISAAC, and appeared in the AAAI-02 workshop on Agent-Based B2B Electronic Commerce Applications)]  Slides. 

·         Also Michael Kearns’s lecture “Behavioral Games on networks”, Wean Hall 5409, 3:30-4:30pm.

  1. Oct 18:  Guest lecture by Andrew Gilpin.    Multi-item auctions. Sequential auction mechanisms.  Parallel auction mechanisms.  Combinatorial auctions.  Approaches to winner determination in combinatorial auctions.  Bidding languages.  Generalized Vickrey auction.  Review article on optimal winner determination algorithms.  Optional review article on the winner determination problem.   Slides.
  2. Oct 23:  Homework 2 due at the beginning of class.  Guest lecture by Andrew Gilpin.  Multi-unit combinatorial auctions.  Combinatorial reverse auctions.  Combinatorial exchanges.  Free disposal vs. not.  Complexity of clearing these markets.  Side constraints and non-price attributes in markets.  Complexity of clearing these markets.  Budget constraints violate quasilinearity.  Slides.  Homework 3 posted.
  3. Oct 25:  Guest lecture by Andrew Gilpin.  Algorithmic mechanism design, i.e., incentive-compatible approximation by the auctioneer.  Slides.
  4. Oct 30:   Guest lecture by Shahar Dobzinski (Hebrew University): The Power of VCG: On Algorithms that are Maximal in Range.  NOTE UNUSUAL TIME AND PLACE: 3:30-4:30 pm, Wean Hall 7220. 
  5. Nov 1:   Homework 3 due at the beginning of class.  Preference elicitation in combinatorial auctions.  Overview paper (Chapter 10 in the Combinatorial Auctions book).  Slides.
  6. Nov 6:  Guest lecture by Andrew Gilpin.  Ascending (descending) combinatorial auctions.  Primal-dual approaches.  Slides.
  7. Nov 8:  Guest lecture by Ben Lubin (Harvard). Iterative Combinatorial Exchanges.  Slides.
  8. Nov 13:  Guest lecture by Nina Balcan.  Mechanism design via machine learning.  Paper 1.  Paper 2.  Paper 3.  Slides.
  9. Nov 15:  Automated mechanism design.  Paper.  Slides.   
  10. Nov 20:  More on automated mechanism design.  Revenue-maximizing combinatorial auctions.  Affine maximizer combinatorial auctions.  Virtual valuations combinatorial auctions.  Paper.  Automated design of multi-stage mechanisms.    (Other related topics we won’t have time for in this lecture: Network view of incentive compatibility constraints; optimal mechanisms derived using that view.)
  11. Nov 27:  Bidding agents with hard valuation problems.  Mechanism design for such agents.  Nonexistence of incentive-compatible mechanisms.  Paper.  Slides.
  12. Nov 29: Benefits of non-truth-promoting mechanisms.  Second-chance mechanism.  Assuming agents can only solve problems that are worst-case polynomial time.  Easiness of typical cases of manipulation problems.  Paper1.   Paper 2.  Slides.
  13. Dec 4: Final project presentations (Abe, Elie, Ram).
  14. Dec 6 (last class): Final project presentations (Aaron, Sam, Varun).  Final project writeups due: HARD DEADLINE.

There will be no class on Nov 22nd due to Thanksgiving. 

 

 

Other resources

 

Tuomas Sandholm’s home page

 

Al Roth’s Game Theory, Experimental Economics, and Market Design Page at Harvard

 

Al Roth’s Market Design Ideas Page

 

Related courses at other universities

 

David Parkes’s course Computational Mechanism Design at Harvard

 

Al Roth and Peter Coles’s course Market Design at Harvard

 

Noam Nisan’s course at Hebrew University, Israel

 

Utku Ünver’s course Matching Market Design at University of Pittsburgh

 

Robert Wilson’s course Market Design at Stanford

 

Tim Roughgarden’s course Introduction to Algorithmic Game Theory at Stanford

 

Christos Papadimitriou’s course at University of California, Berkeley

 

Joan Feigenbaum’s course at Yale University

 

Amy Greenwald’s course at Brown University

 

Yoav Shoham’s course Computer Science and Game Theory at Stanford