有没有谁对这个感兴趣？CS286r: Computational Mechanism Design David C. Parkes, parkes@eecs.harvard.edu Syllabus, Spring 2002
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. [3/7]Combinatorial Auctions: Optimal Search Methods [SSGL01] pdfpsSandholm, 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 -->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/12]One Parameter Machine Scheduling [AT01] pdfpsAaron Archer and Eva Tardos, In Proceedings of the 42nd IEEE Symposium on Foundations ofComputer Science, 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 pdfpsParkes, D.C., Minimal Preference Elicitation: An Equilibrium Approach,Working paper, Harvard University, 2002 -->[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.
发帖
雷达卡
提升卡
置顶卡
沉默卡
变色卡
抢沙发
千斤顶
显身卡
京公网安备 11010802022788号
