Contents
Class
Home Page
Background papers
Introductory lectures
I: Optimal One-Shot Mechanism Design
II: Approximate One-Shot Mechanism Design
III: Iterative Mechanism Design
IV: Network Implementation
V: Open Problems
VI: Class Projects
Extra Reading!
|
Background Papers: Setting the Scene
|
[Var95] pdf ps
|
Varian, H. Mechanism Design for Computerized Agents In Proc.
USENIX Workshop on Electronic
Commerce, July 11-12, 1995, New York
|
|
[Nis99] pdf
ps
|
Noam Nisan, Algorithms for Selfish AgentsIn Proc. 16th Annual
Symposium on Theoretical Aspects of Computer Science (STACS'99),
pp.1--15, 1999.
|
|
[Pap01]
pdf
ps
|
Papadimitriou, C. H. Algorithms, Games, and the Internet In Proc. 33rd Annual ACM Symp. on the Theory of Computing} (STOC'01),
pp.749--753, 2001.
|
|
[ATY00]
pdf
ps
|
Andersson, A., M. Tenhunen, and F. Ygge. Integer Programming for Combinatorial
Auction Winner Determination. In Proc. of the Fourth International Conference on Multiagent Systems (ICMAS-00), 2000.
|
Introductory Lectures
|
[1/31]
|
Introduction.
[Handouts]
Syllabus ps
pdf REVISED: ps
pdf
Survey ps
Slides pdf
ps
|
|
[2/5]
|
On Interesting Problems.
Real world combinatorial auctions.
[Lecture Notes]pdf
ps
[FCC Comb Auction]ppt
Spectrum auction
[McM94] pdf
ps
John McMillan, Selling Spectrum Rights, Journal of
Econ. Perspectives, 8(3):145--162, 1994.
|
|
[2/7]
|
Game Theory Concept of Nash equilibrium; Strategies;
Rationality.
[Handout:] Drew Fudenberg and Jean
Tirole, Game Theory, MIT Press, 1991, pp.3--44, 209--216,
241--242.
[Lecture Notes:] pdf
ps
[Classics for the Curious]
[Nas51] pdf
psJohn F. Nash, Jr., Non-cooperative games, Annals of Mathematics,
54 (1951) 286-295.
[Nas50] pdf
ps
John F. Nash, Jr., The bargaining problem. Econometrica 18: 155-162,
1950.
[Homework 1] Distributed, due Thurs 2/14.
pdf
ps
|
|
[2/12]
|
Mechanism Design I Definition; Revelation Principle; Vickrey-Clarke-Groves.
[Par01a] pdf
ps
Parkes, D.C. Mechanism
Design. Chapter 2
in PhD dissertation, ``Iterative Combinatorial Auctions: Achieving Economic and
Computational Efficiency'', May 2001
Department of Computer and Information Science, University of
Pennsylvania
[Jac00] pdf
ps
Jackson, M. Mechanism Theory. Forthcoming in Encyclopedia of Life Support Stystems. 2000
[Classics for the Curious]
[GL77] pdf
ps
Jerry R. Green and Jean-Jacques Laffont, Characterization of
satisfactory mechanisms for the revelation of preferences for public
goods. Econometrica 45:427--438, 1977.
[Lecture Notes:] pdf
ps
|
|
[2/14]
|
Mechanism Design II Different solution concepts; Impossibility
and Possibility Results.
[Lecture notes:] pdf
ps
[Homework 2] Distributed, now due in class 2/26.
pdf
ps
|
|
[2/19]
|
Mechanism Design III VCG; group-stratetgy proofness.
[Lecture notes:] pdf
ps
Then, Auction Theory I Revenue equivalence; Definitions.
[Handout:]
[MM87] pdf
ps
R. Preston McAfee and John McMillan, Auctions and
bidding, J. of Economics Literature, 25:699-738, 1987.
[Classics for the Curious:]
[V61] pdf
psWilliam Vickrey, Counterspeculation, auctions, and competitive sealed
tenders, Journal of Finance, 16:8--37, 1961.
|
|
[2/21]
|
Auction Theory II: Variations;
Iterative vs. Sealed Bid; Real World examples.
Then, Linear Progamming I:
LP Duality, Solutions.
[Lecture notes:] pdf
ps
[Handouts:]
Vijay Vazirani, Approximation Algorithms,
Springer-Verlag, 2001, pp.93--107.
[Par01a] pdf
ps
Parkes, D.C. Iterative Combinatorial Auctions: Achieving
Economic and Computational Efficiency, Ph.D. Dissertation,
University of Pennsylvania, 2001, pp. 87--109.
[Classic for the Curious:]
[Handout]
George B. Dantzig, Linear Programming and Extensions, RAND
1963. pp. [vii--x], 12--31, Preface and Origins and
Influences.
[Homework 3] Distributed, due in class 3/5 pdf
ps.
|
|
[2/26]
|
Linear Programming II (& MicroEcon)
Competitive equilibrium, Welfare Theorems.
[Lecture notes:] pdf
ps
[Handout:]
Hal R. Varian, Microeconomic Analysis, W.W.Norton 1992,
pp. 313--337.
Then Integer Programming I:Formulations,
Solutions.
[Handout:]
Laurence A. Wolsey, Integer Programming, John
Wiley \& Sons, 1998, pp.1--65.
%
|
|
[2/28]
|
Integer Programming II
Relaxtions.
[Lecture notes:] pdf
ps
[Handout:]
[Par01b] pdf
ps
Parkes, D.C. Mechanism
Design. Chapter 3
in PhD dissertation, ``Iterative Combinatorial Auctions: Achieving Economic and
Computational Efficiency'', May 2001
Department of Computer and Information Science, University of
Pennsylvania
[Homework 4]distributed; due in class, 3/12,pdf
ps
.
|
I: Optimal One-Shot Mechanism Design
|
[3/5]
|
Algorithmic Mechanism Design: Shortest-Path
[HS01]
pdf
ps
Hershberger,
J. and S. Suri, Vickrey Prices and Shortest Paths: What is an edge
worth?
In Proc. 42nd Annual Symposium on Foundations of
Computer Science (FOCS'01), pp.129--140, 2001.
[Low-Esparza Slides] ppt
[Background motivations]
[Nis99] pdf
ps
Noam Nisan, Algorithms for Selfish Agents, In Proc. 16th Annual
Symposium on Theoretical Aspects of Computer Science (STACS'99), pp.1-15, 1999.
|
|
[3/7]
|
Combinatorial Auctions: Tractable Problems, Optimal Search.
[VV00]
pdf
ps
pp. 1-25, 44-66 only
de Vries, S. and R. Vohra, Combinatorial Auctions: A Survey,
Technial Report, MEDS, Kellogg School of Management, Northwestern,
2000
[ATY00] pdf
ps
Andersson, A., M. Tenhunen, and F. Ygge. Integer Programming for Combinatorial
Auction Winner Determination. In Proc. of the Fourth International Conference
on Multiagent Systems (ICMAS-00), 2000.
|
II: Approximate One-Shot Mechanism Design
|
[3/12]
|
Algorithmic Mechanism Design.
[pp. 1-21 only]
[NR01]
pdf
ps
Nisan, N and
A. Ronen, Algorithmic mechanism design, Games and Economic Behavior, 35:166-196, 2001.
|
|
[3/14]
|
Combinatorial Auctions: Approximations I
[pp. 1-16 only]
[NR00]
pdf
ps
Nisan, N. and A. Ronen, Computationally Efficient VCG Mechanisms,
In Proc. 2nd. ACM Conf. on Electronic commerce (EC'00), 242--252, 2000.
|
|
[3/19]
|
Combinatorial Auctions: Approximations II
[LCS01]
pdf
ps
Lehmann, D., L. O'Callaghan and Y. Shoham,
Truth Revelation in Rapid, Approximately Efficient Combinatorial
Auctions. Shorter version,
Proc. 1st ACM Conf. on E-commerce (EC'99), 96--102, 1999.
[Not for discussion.]
[KMT00-handout]
Kfir-Dahav, N., E., D. Monderer, and M. Tennenholtz,
Mechanism Design for Resource Bounded Agents,
Proc. International Multiagent Systems Conference (ICMAS-00), p.309-315, 2000
|
|
[3/21]
|
Combinatorial Auctions: Approximations III
[HKMT01] pdf
ps
Holzman, R., N. Kfir-Dahav, D. Monderer and M. Tennenholtz,
Bundling Equilibrium in Combinatorial Auctions, Working paper,
Technion and Stanford, 2001
|
Spring Break
III: Iterative Mechanism Design
|
[4/2]
|
Minimal Preference Elicitation
[Par99]
pdf
ps
Parkes, D.C.,
Optimal Auction Design for Agents with Hard Valuation Problems.
In Proc. IJCAI'99 Workshop on Agent Mediated Electronic Commerce
(AmEC-99).
|
|
[4/4]
|
Project Proposals Due (noon); to Arthur Cram, Maxwell-Dworkin 133.
Note: I am out of town afternoon 4/2-- evening 4/4, and there is NO CLASS TPDAY.
|
|
[4/9]
|
Assignment Problem
[DGS86] pdf
ps
Demange, G., D. Gale, and M.Sotomayor,
Multi-Item Auctions, Journal of Political Economy, 94, pp 863-872, 1986
[DGS86] pdf
ps
Leonard, H.B.,
Elicitation of Honest Preferences for the Assignment of Individuals to
Positions,
Journal of Poltical Economy 91, pp 463-479, 1983
|
|
[4/11]
|
Ascending-Price Combinatorial Auction
[PU00]
pdf
ps
Parkes, D. C. and
L. H. Ungar, Iterative Combinatorial Auctions: Theory and Practice,
In Proc. AAAI'00., 74--81, 2000
[Not for discussion]
[Ber90-handout]Bertsekas, D.P.,
The auction algorithm for assignment and network flow problems: A
tutorial. Interfaces, 20(4):133-149, 1990
|
|
[4/16]
|
Ascending-Price Generalized Vickrey Auction
[PU02]
pdf
Parkes, D. C. and
L. H. Ungar, Ascending Price Generalized Vickrey Auctions,
Working paper, Harvard University, 2002
[Not for discussion]
[BVVS01] pdf
ps
Bikchandani, S., S. de Vries, R. Vohra, and J. Schummer, Linear
Programming and Vickrey Auctions, Working paper, MEDS, Kellogg
School of Management, Northwestern University, 2001
|
|
[4/18]
|
Guest Lecture: Paul Milgrom
[M02] ps
pdf
P. Milgrom, Putting Auction Theory to Work, MIT Press, 2002 (ch. 1)
|
IV: Network Implementation
|
[4/23]
|
Distributed Algorithmic Mechanism Design
[S01]
pdf
ps
Scott Shenker, Open Problems in Distributed
Mechanism Design, Presentation to DIMACS Workshop on
Computational Issues in Game Theory and Mechanism Design, Oct. 31, 2001.
|
|
[4/25]
|
Multicast Cost Sharing
[FPS01]
pdf
ps
Feigenbaum, J., C. Papadimitriou and S. Shenker,
Sharing the Cost of Multicast Transmissions, Journal of Computer and
System Sciences 63 (2001), pp. 21-41. (Special issue on Internet
Algorithms.)
[Not for discussion.][JV01]
pdf
ps
Jain, K. and V. Vazirani, Applications of
approximation algorithms to cooperative games. In Proc. 33rd
Annual ACM Symp. on Theory of Computing, (STOC'01) pp.364--372, 2001.
|
|
[4/30]
|
Network Protocol Friendly Methods
[FPSS02] pdf
ps
Feigenbaum, J., C. Papadimitriou, R. Sami, and S. Shenker,
Incentive-Compatible Interdomain Routing, Working paper, Yale
University, 2002
|
V: Conclusions
|
[5/2]
|
Open Problems and Summary
[Pap01] pdf
ps
Papadimitriou, C. H. Algorithms, Games, and the Internet In Proc. STOC 2001 A survey of algorithmic problems related
to Game Theory and the Internet.
|
VI: Class Projects
|
[5/13]
|
Project Presentations
|
|
[5/15]
|
Project Reports Due
|
Additional Reading: Strictly Not For This Class!
|
[FKSS01-PDF]
|
Feigenbaum, J., A. Krishnamurty, R. Sami, and S. Shenker,
Approximation and Collusion in Multicast Cost Sharing, Submitted
for publication.
Abstract appears in Proceedings of the 3rd Conference on Electronic
Commerce, ACM Press, 2001
|
|
[NR00-PDF] |
Nisan, N. and A. Ronen, Computationally Efficient VCG Mechanisms,
In Proc. ACM E-commerce, 242--252, 2000, Section 4, discussion
of ``appeal functions''
|
|
[Ron01] |
A. Ronen, Mechanism Design with Incomplete Languages,
In Proc. ACM E-commerce, 105--114, 2001
|
|
[N01-PDF] |
Need to get the new citation Nisan, N.,
The Communication Complexity of Combinatorial Auctions,
Working paper, Hebrew University, 2001
|
|
[N00-PDF] | Nisan, N.,
Bidding and Allocation in Combinatorial Auctions, In Proc. ACM
E-commerce, 2000 |
| [HB00-PS] |
Hoos, H. and
C. Boutilier, Bidding Languages for Combinatorial Auctions, In IJCAI'01
|
|
[W93-PS] |
Wellman, M., A market-oriented programming environment and its application to
distributed multicommodity flow problems. Journal of Artificial
Intelligence Research, 1:1-23, 1993
|
|
[WWWMM00-PS] |
Wellman, M., W.E.Walsh, P.R.Wurman, J.K. MacKie-Mason, Auction protocols for
decentralized scheduling, Games and Economic Behavior, 2001
|
|
[S93-PS] |
Sandholm, T., An Implementation of the Contract Net Protocol Based on
Marginal Cost Calculations. In Proc. Eleventh National Conference on Artificial
Intelligence (AAAI-93), Washington DC, pp. 256-262.
|
|
[SSGL01] |
Sandholm, T., S. Suri, A. Gilpin, and D.Levine, CABOB: A
Fast Optimal Algorithm for Combinatorial Auctions, In Proc.
International
Joint Conference on Artificial Intelligence (IJCAI), Seattle,
WA. 2001
|
|
[Ron01] |
A. Ronen, Mechanism Design with Incomplete Languages,
In Proc. ACM E-commerce, 105--114, 2001
|
|
[Rab01]
|
Tal Rabin,
DIMACS
|
|
[LS01-PDF] |
Larson, K. and
T.Sandholm, Costly Valuation Computation in Auctions:
Deliberation Equilibrium. In Proc. Theoretical Aspects of Reasoning about Knowledge
(TARK), pp. 169-182, Siena, Italy, July 8-10.
|
|
[FLS99-PDF] |
Fujishjima, Leyton-Brown and Shoham,
Taming the Computational Complexity of Combinatorial Auctions:
Optimal and Approximate Approaches, In Proc. IJCAI'99
|
| [ZN01-PDF] |
Zurel, E. and N. Nisan, An Efficient Approximate Allocation Algorithm
for Combinatorial Auctions, In Proc. ACM Electronic Commerce Conf.,
Tampa FL, 2001
|
| [HB00-PS] |
Hoos, H. and C. Boutilier, Solving Combinatorial Auctions using
Stochastic Local Search, In. Proc. AAAI'00
|
|
[ORC01-PDF] | Orlin, J.,
R. Ramaswamy and N. Chakravarty, Sensitivity Analysis for Shortest
Path Problems and Maximum Capacity Path Problems in Undirected
Graphs, Operations Research Center Working Paper.
April 2001.
|
|
[CS01]
| Conen, W. and T. Sandholm,
Preference Elicitation in
Combinatorial Auctions, In Proc. ACM Conf. on Electronic
Commerce, 256--259, 2001
|
|
[Par01-PS] | Parkes, D. C.,
Bounded-Rational Compatible Auctions and Myopic best-response.
Chapter 8, Ph.D. Dissertation ``Iterative Combinatorial Auctions:
Achieving Economic and
Computational Efficiency'', May 2001.
Department of Computer and Information Science, University of Pennsylvania.
|
|