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

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.

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

* "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

* "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

* "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

* "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 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

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