Instructor: Joan Feigenbaum
Office: AKW 512; Telephone: 203-432-6432
Professor Feigenbaum suffers from Repetitive
Strain Injury and cannot handle large amounts of email. Do NOT send her email
about CPSC455; instead, please contact her through her assistant:
Judi
Paige Telephone: 203-436-1267
TA: Sheng Zhong
Office: AKW412; Telephone: 203-432-7037
Announcement:
Course description:
A mathematically rigorous investigation of
the interplay of economic theory and computer science with an emphasis on the
relationship of incentive compatibility and computational efficiency.
Particular attention is paid to the formulation and solution of
mechanism-design problems that are relevant to data networking and
Internet-based commerce. Suitable for mathematically inclined advanced
undergraduates and first- or second-year graduate students in Computer Science,
Economics, or closely related fields.
CPSC365 or equivalent background in algorithms and complexity
theory is an essential prerequisite.
Note on the prerequisite:
It really is essential that students have a firm
grounding in the basics of theoretical computer science before enrolling in
CPSC455/555. If you are unsure about whether you have the necessary background, you should read the
paper "Algorithmic
Mechanism Design," by Nisan and Ronen and the thesis chapter "Interactive
Combinatorial Auctions: Achieving Economic and Computational Efficiency,"
by Parkes. If you have trouble understanding either of these, then you should
not enroll in CPSC455/555.
Rough topic outline:
Rather than survey the entire potential
intersection of economic theory and computational theory, we will concentrate
on four topics of current interest: routing, multicast cost sharing,
digital-goods auctions, and information markets. Below, you will find a list of
papers on each topic, plus some other related material. Required reading for each class will be
posted as the semester progresses and will be drawn primarily from the list
below.
Requirements:
Every student is required to do a final paper
or programming project, due in class on the last day (April 24, 2003). Topics must be discussed with and approved
by Professor Feigenbaum before Spring break.
In addition, undergraduates will have to do a PowerPoint presentation to
the class of one of the required papers, and graduate students will have to do
two such presentations.
Student Presentations:
Jan. 30, 2003: "How Bad is Selfish Routing?" by T. Roughgarden and E. Tardos, JACM 49 (2): 236-259. 2002. Presented by Hadi Salmasian.
Feb. 4, 2003: "On Cheating in Sealed-Bid Auctions, " by R. Porter and Y. Shoham, to appear in EC 2003. Presented by Hong Jiang.
Feb. 11, 2003: "Competitive Generalized Auctions," by A. Fiat, A. Goldberg, J. Hartline and A. Karlin, STOC 2002: 72-81. Presented by Gus Fuldner.
Feb. 18, 2003: "Oblivious AQM and Nash Equilibria," by Debojyoti Dutta, Ashish Goel, and John Heidemann, to appear in INFOCOM 2003. Presented by Zheng Ma.
Feb. 20, 2003: "Best-Effort versus Reservations: A Simple Comparative Analysis", by L. Breslau and S. Shenker, SIGCOMM 1998: 3-16; "Fundamental Design Issues for the Future Internet," by Scott Shenker, IEEE Journal on Selected Areas in Communications 13 (7): 1176-1188. 1995. Presented by Aleksandr Yampolskiy.
Feb. 25, 2003 and Feb. 27, 2003: "Betting Boolean-style: A Framework for Trading in Securities Based on Logical Formulas," by L. Fortnow, J. Kilian, D. Pennock, and M. Wellman, NEC Laboratories America Technical Report #2002-L010N. 2002; "NP Markets, or How to Get Everyone else to Solve Your Intractable Problems," by D. Pennock, Workshop on Economic Agents, Models, and Mechanisms at IJCAI 2001: 89-98. 2001.Presented by David Goldenberg.
Mar. 4, 2003: "Combinatorial Information Market Design," by R. Hanson, Information Systems Frontiers 5 (1): 105-117. 2003. Presented by Yukai Wang.
Mar. 6, 2003: "Asset
Pricing Under Endogenous Expectations in an Artificial Stock Market," by
W. Arthur, J. Holland, B. LeBaron, R. Palmer, and P. Talyer, 1996. Presented by
Daniel Pfeiffer.
Mar. 27, 2003: "Computationally Feasible VCG Mechanisms," by N. Nisan and A. Ronen, EC 2000: 242-252. Presented by Kevin Chang.
Apr. 1, 2003: "Achieving Budget-Balance with Vickrey-Based Payment Schemes in Exchanges, " by D. Parkes, J. Kalagnanam, and M. Eso, IJCAI 2001: 1161-1168. Presented by Jeffrey Sarnat.
Apr. 3, 2003: "Applications of Approximation to Cooperative Games," by K. Jain and V. Vazirani, STOC 2001: 364-372. Presented by Jiang Chen.
Apr. 8, 2003: "Modeling
Information Incorporation in Markets with Application to Detecting and
Explaining Events," by D. Pennock, S. Debnath, E. Glover, and C.
Giles, UAI 2002: 405-413. Presented by Chetan Jindal.
Introduction:
"Algorithmic Mechanism
Design," by N. Nisan and A. Ronen, Games and Economic Behavior 35
(1-2) : 166--196. 2001.
"Algorithms for Selfish
Agents -- Mechanism Design for Distributed Computation," by N. Nisan, STACS
1999: 1-15.
"Interactive
Combinatorial Auctions: Achieving Economic and Computational Efficiency,"
by D. Parkes, AAAI/IAAI
2000: 74-81.
"Algorithms,
Games, and the Internet," by C. Papadimitriou, ICALP
2001: 1-3.
"Distributed Algorithmic Mechanism
Design: Recent Results and Future Directions," by J. Feigenbaum and S.
Shenker, DIALM 2002: 1-13.
Routing:
"Algorithmic Mechanism Design," by N. Nisan and A. Ronen, Games and Economic Behavior 35 (1-2) : 166--196. 2001.
"Vickrey
Prices and Shortest Paths: What is an Edge Worth," by J. Hershberger
and S. Suri, FOCS
2001: 252-259.
"A
BGP-based Mechanism for Lowest-Cost Routing," by J. Feigenbaum, C.
Papadimitriou, R. Sami, and S. Shenker, PODC
2002: 173-182.
"How Bad is
Selfish Routing?" by T. Roughgarden and E. Tardos, JACM
49 (2): 236-259. 2002.
"Worst-Case
Equilibria," by E. Koutsoupias and C. Papadimitriou, STACS
1999: 404-413.
"Frugal
Path Mechanisms," by A. Archer and E. Tardos, SODA
2002: 991-999.
"Selfish
Routing," by T. Roughgarden, PhD thesis, Cornell University, May 2002.
"The Price of
Anarchy is Independent of the Network Topology," by T. Roughgarden, Invited
to special issue of JCSS. Conference version appears in STOC 2002: 428--437.
"How Unfair is
Optimal Routing?" by T. Roughgarden, SODA
2002: 991-999.
Multicast Cost Sharing:
"Sharing
the Cost of Multicast Transmission," by J. Feigenbaum, C.
Papadimitriou, and S. Shenker, JCSS
63 (1): 21-41. 2001.
"Hardness
Results for Multicast Cost Sharing," by J. Feigenbaum, A. Krishnamurthy,
R. Sami, and S. Shenker, FSTTCS
2002: 133-144.
"Approximation
and Collusion in Multicast Cost Sharing," by A. Archer, J. Feigenbaum,
A. Krishnamurthy, R. Sami, and S. Shenker.
"Pricing
Multicasting in More Practical Network Models," by M. Adler and D.
Rubenstein, SODA
2002: 981-990.
"Applications
of Approximation to Cooperative Games," by K. Jain and V. Vazirani, STOC
2001: 364-372.
Digital-Goods Auctions:
"Competitive
Auctions," by A. Goldberg, J. Hartline, A. Karlin, and A. Wright.
"Competitive Generalized
Auctions," by A. Fiat, A. Goldberg, J. Hartline and A. Karlin, STOC
2002: 72-81.
Information Markets:
"Extracting
collective probabilistic forecasts from web games," by D. Pennock,
S. Lawrence, F. Nielsen, and C. Giles, KDD
2001: 174-183.
"Computation in a
Distributed Information Market," by J. Feigenbaum, L. Fortnow, D.
Pennock, and R. Sami, NEC Laboratories America Technical Note 2002-L011N.
"The
Arbitrage Principle in Financial Economics," by H. Varian, J. Economic
Perspectives 1(2): 55-72. 1987.
"Parimutuel
Betting Markets as Information Aggregation Devices: Experimental Results,"
by C. Plott, J. Wit and W. Yang, Social Science Working Paper 986, CalTech.
1997.
"Wishes,
expectations, and actions: A survey on price formation in election stock
markets," by R. Forsythe, T.
Rietz, and T. Ross, J. Economic Behavior & Organization 39(1):
83-110. 1999.
"Could
Gambling Save Science? Encouraging an Honest Consensus," by R. Hanson,
Social Epistemology 9 (1): 3-33. 1995.
"Combinatorial
Information Market Design," by R. Hanson, Information Systems
Frontiers 5 (1):105-117. 2003.
"Inducing
Liquidity In Thin Financial Markets Through Combined-Value Trading
Mechanisms," by P. Bossaerts, L. Fine, and J. Ledyard, Social Science
Working Paper 1095R, CalTech. 2000.
"Effect
of the Internet on Financial Markets," by H. Varian, 1998.
"Behavior of Trading Automata in a
Computerized Double Auction Markets," by J. Rust, J. Miller, and R.
Palmer, In The
Double Auction Market: Institutions, Theories, and Evidence, 155-198. 1993.
"An Artificial
Stock Market," by R. Palmer, W. Arthur, J. Holland, and B. LeBaron,
Artificial Life and Robotics. 1998.
"Betting
Boolean-style: A Framework for Trading in Securities Based on Logical
Formulas," by L. Fortnow, J. Kilian, D. Pennock, and M. Wellman, NEC
Laboratories America Technical Report #2002-L010N. 2002.
"Compact
securities markets for Pareto optimal reallocation of risk," by D.
Pennock and M. Wellman, UAI
2000: 481-488. 2000.
"NP
Markets, or How to Get Everyone else to Solve Your Intractable Problems,"
by D. Pennock, Workshop on Economic Agents, Models, and Mechanisms at IJCAI
2001: 89-98. 2001.
"Modeling
Information Incorporation in Markets with Application to Detecting and
Explaining Events," by D. Pennock, S. Debnath, E. Glover, and C.
Giles, UAI 2002: 405-413.
"Information
Dissemination and Aggregation in Asset Markets with Simple Intelligent
Traders," by N. Chan, B. LeBaron, A. Lo, and T. Poggio, Technical
Report AIM-1646, MIT. 1998.
"Asset
Pricing Under Endogenous Expectations in an Artificial Stock Market,"
by W. Arthur, J. Holland, B. LeBaron, R. Palmer, and P. Talyer, 1996.
Related Online Resources:
Joan Feigenbaum's DIALM'02 Talk on Distributed Algorithmic Mechanism
Design.
Scott Shenker's DIMACS Talk on Foundations of
Distributed Mechanism Design.
Christos Papadimitriou's Tutorial on A TCS Introduction
to Game Theory and Mathematical Economics.
Yoav Shoham's talk on Combinatorial Auctions.
Yoav Shoham's Survey of Auction Types.
Yoav Shoham's talk on The Auction Space: Beyond Zoology.
Yoav Shoham's talk on Elements of Auction Theory.
Noam Nisan's talk on Rationality as a Paradigm
for Internet Computing.
The Spring 2002
rendition of CPSC455/555.
Noam Nisan's Course on CS, Game Theory, and
Economics.
David Parkes's Course on Computational
Mechanism Design.
Christos Papadimitriou's Course on Algorithmic
Aspects of Game Theory.
Homepages: (These web pages contain relevant talks and papers by the following
people and their collaborators.)
Aaron Archer Joan
Feigenbaum Amos Fiat Andrew Goldberg Jason Hartline Noam
Nisan Christos Papadimitriou David Parkes David
Pennock Amir Ronen Tim
Roughgarden Yoav Shoham Eva Tardos Moshe Tennenholtz Vijay Vazirani