CPSC455b: Economics and Computation


Instructor: Joan Feigenbaum (http://www.cs.yale.edu/~jf)
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 (judi.paige@yale.edu) Telephone: 203-436-1267

TA: Sheng Zhong (sheng.zhong@yale.edu)
Office: AKW412; Telephone: 203-432-7037


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. If you are unsure about whether you have the  necessary background, you should read the paper "Algorithmic Mechanism Design," by Nisan and Ronen (http://www.cs.huji.ac.il/~noam/selfishJ.ps) and the thesis chapter "Interactive Combinatorial Auctions: Achieving Economic and Computational Efficiency," by Parkes  (http://www.eecs.harvard.edu/~parkes/pubs/ch2.pdf). If you have trouble understanding either of these, then you should not enroll in CPSC455.
 

Rough topic outline:

Rather than survey the entire potential intersection of economic theory and computational theory, we will concentrate on four or five topics of current interest. Following is a list of topics and a set of papers for each. Not all of these papers will be required reading. Conversely, some of the required reading may not be on the list below.  Exactly which papers will be required will be determined as the course progresses. If you want to read ahead, start with the papers marked *;  it is likely that many of them will be required.
 


Homeworks and Exam

First written homework assignment.   word format  pdf format

Solution set for first Homework Assignment.  word format  pdf format

Second written homework assignment.  ps format  pdf format

Solution set for second Homework Assignment.  ps format   pdf format

Third written homework assignment. word format  pdf format

Solution set for third Homework Assignment.  word format  pdf format

Hour Exam.  ps format  pdf format

Solution set for Hour Exam.  ps format  pdf format


Introduction:


* "Algorithmic Mechanism Design," by N. Nisan and A. Ronen
http://www.cs.huji.ac.il/~noam/selfishJ.ps

* "Algorithms for Selfish Agents -- Mechanism Design for Distributed Computation," by N. Nisan
http://www.cs.huji.ac.il/~noam/expoself.ps

* "Interactive Combinatorial Auctions: Achieving Economic and Computational Efficiency," by D. Parkes
http://www.eecs.harvard.edu/~parkes/pubs/ch2.pdf

"Algorithms, Games, and the Internet," by C. Papadimitriou
http://www.cs.berkeley.edu/~christos/stoc01.ps.ps


Routing:


* "Algorithmic Mechanism Design," by N. Nisan and A. Ronen
http://www.cs.huji.ac.il/~noam/selfishJ.ps

* "Vickrey Prices and Shortest Paths: What is an Edge Worth," by J. Hershberger and S. Suri
http://www.cs.berkeley.edu/~christos/games/readings/vickreypaths.ps

* "Incentive-Compatible Interdomain Routing," by J. Feigenbaum, C. Papadimitriou, R. Sami, and S. Shenker
http://www.cs.yale.edu/~jf/FPSS-draft.ps

"How Bad is Selfish Routing?" by T. Roughgarden and E. Tardos
http://www.cs.cornell.edu/timr/papers/routing_full.ps

"Worst-Case Equilibria," by E. Koutsoupias and C. Papadimitriou
http://www.cs.berkeley.edu/~christos/nash.ps

"Frugal Path Mechanisms," by A. Archer and E. Tardos
http://www.orie.cornell.edu/~aarcher/Research/fpSODAproc.ps


Auctions:


* "On approximating optimal auctions," by A. Ronen
http://robotics.stanford.edu/~amirr/aproxAuct7.ps

* "Competitive Auctions," by A. Goldberg, J. Hartline, A. Karlin, and A. Wright
http://www.avglab.com/andrew/pub/auction.ps

"Competitive Generalized Auctions," by A. Fiat, A. Goldberg, J. Hartline and A. Karlin
http://www.math.tau.ac.il/~fiat/stocauc.ps

"Combinatorial Auctions: A Survey," S. de Vries and R. Vohra
http://www-m9.ma.tum.de/~devries/comb_auction_supplement/comauction.pdf

* "Interactive Combinatorial Auctions: Achieving Economic and Computational Efficiency," by D. Parkes
http://www.eecs.harvard.edu/~parkes/pubs/ch2.pdf

* "The Communication Complexity of Efficient Allocation Problems," by N. Nisan and I. Segal
http://www.cs.yale.edu/~jf/NisanSegal02.ps

"Computationally Feasible VCG Mechanisms," by N. Nisan and A. Ronen
http://www.cs.huji.ac.il/~noam/vcgbased.ps

"Truth Revelation in Rapid, Approximately Efficient Combinatorial Auctions," by D. Lehmann, L. O'Callaghan, and Y. Shoham
http://www.cs.huji.ac.il/~noam/econcs/los.ps


Multicast Cost Sharing:


* "Sharing the Cost of Multicast Transmission," by J. Feigenbaum, C. Papadimitriou, and S. Shenker
http://www.cs.yale.edu/~jf/FPS.ps

* "Hardness Results for Multicast Cost Sharing," by J. Feigenbaum, A. Krishnamurthy, R. Sami, and S. Shenker
http://www.cs.yale.edu/~jf/FKSS2-draft.ps

"Approximation and Collusion in Multicast Cost Sharing," by J. Feigenbaum, A. Krishnamurthy, R. Sami, and S. Shenker
http://www.cs.yale.edu/~jf/FKSS.ps

"Pricing Multicasting in More Practical Network Models," by M. Adler and D. Rubenstein
http://www.cs.umass.edu/~micah/pubs/pricing.ps

"Applications of Approximation to Cooperative Games," by K. Jain and V. Vazirani
http://www.cc.gatech.edu/fac/Vijay.Vazirani/econ.ps


Graphical Models for Games:


"Graphical Models for Game Theory," by M. Kearns, M. Littman, and S. Singh
http://www.cis.upenn.edu/~mkearns/papers/graphgames.ps

"Nash Convergence of Gradient Dynamics in General-Sum Games," by M. Kearns, Y. Mansour, and S. Singh
http://www.cis.upenn.edu/~mkearns/papers/gradgames.ps

"Fast Planning in Stochastic Games," by M. Kearns, Y. Mansour, and S. Singh
http://www.cis.upenn.edu/~mkearns/papers/sparsegame.ps


Other Related Papers, Talks, and Web Pages:

Scott Shenker's DIMACS Talk on Foundations of Distributed Mechanism Design
http://www.cs.yale.edu/~jf/shenker-dimacs-talk.ps

Christos Papadimitriou's Tutorial on A TCS Introduction to Game Theory and Mathematical Economics
http://www.cs.berkeley.edu/~christos/games/focs01.ppt

Yoav Shoham's talk on Combinatorial Auctions
http://www.cs.yale.edu/~jf/YS1.pdf

Yoav Shoham's Survey of Auction Types
http://www.cs.yale.edu/~jf/YS2.pdf

Yoav Shoham's talk on The Auction Space: Beyond Zoology
http://www.cs.yale.edu/~jf/YS3.pdf

Yoav Shoham's talk on Elements of Auction Theory
http://www.cs.yale.edu/~jf/YS4.pdf

Noam Nisan's Course on CS, Game Theory, and Economics
http://www.cs.huji.ac.il/~noam/econcs/index.html

David Parkes's Course on Computational Mechanism Design
http://www.eecs.harvard.edu/~parkes/cs286r/syllabus.html

Christos Papadimitriou's Course on Algorithmic Aspects of Game Theory
http://www.cs.berkeley.edu/~christos/games/cs294.html

"Strategyproof Sharing of Submodular Costs: Budget Balance vs. Efficiency," by H. Moulin and S. Shenker
http://www.icir.org/shenker/cost.ps

"Group Strategyproofness and No Subsidy via LP Duality," by K. Jain and V. Vazirani
http://www.cs.huji.ac.il/~noam/econcs/jv.ps

"Designing Networks for Selfish Users is Hard," by T. Roughgarden
http://www.cs.cornell.edu/timr/papers/nd_hard.ps

"How Unfair is Optimal Routing?," by T. Roughgarden
http://www.cs.cornell.edu/timr/papers/unfair.ps

"Stackelberger Scheduling Strategies," by T. Roughgarden
http://www.cs.cornell.edu/timr/papers/stack.ps

"Truthful Mechanisms for One-Parameter Agents," by A. Archer and E. Tardos
http://www.orie.cornell.edu/~aarcher/Research/oneparamFOCSproc.ps

"Rationality as a Paradigm for Internet Computing," by N. Nisan
http://www.cs.huji.ac.il/~noam/rationality.ppt

"Statistical Learnability and Rationality of Choice," by G. Kalai
http://zoo.cs.yale.edu/classes/2002/L.pdf