CPSC455/555 // ECON425/563: Economics and Computation

Time: TTh, 2:30 - 3:45
Location: AKW 200
Instructor: Joan Feigenbaum
Assistant: Judi Paige (AKW 507A, Judi.Paige@yale.edu, 203-436-1267)
Instructor Office Hours: Thurs 11:30 a.m. to 12:30 p.m. in AKW 512, or by appointment
TA: David Costanzo
TA Office Hours: Weds 2:30-3:30pm in AKW 301, or by appointment
Textbook: Algorithmic Game Theory, by Nisan, Roughgarden, Tardos, & Vazirani - available at the Yale bookstore
     Errata for the textbook can be found here.

Note: Do not send email to Professor Feigenbaum, who suffers from RSI. Contact her through Ms. Paige or the TA.

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 algorithmic 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.

This course was last taught in Fall 2008; more information can be found here.

For additional background reading about algorithms, please see Kleinberg and Tardos's book entitled "Algorithm Design." It is on reserve at the Becton library. Chapters 2 through 6 are the most important. Slides for this book are available here.

For additional background reading about interdomain routing, please see the first three chapters of Vijay Ramachandran's PhD thesis.


HW1 (due in class on Tues, Sept 20):
  Chapter 14: 2, 3, 6, 7
  Chapter 19: 3, 4, 6, 9

HW2 (due in class on Tues, Oct 11):
  Chapter 11: 1, 3, 5
  Chapter 28: 2, 4, 5

HW3 (due in class on Thurs, Oct 27):
  Chapter 23: 1, 2
  Chapter 27: 1, 2, 3, 5

HW4 (due in class on Thurs, Nov 17):
  Chapter 27: 4, 6, 7, 8
  Chapter 26: 4, Z*
* 26.Z is not from the textbook, but is related to the material of Chapter 26. Here's the problem:

HW5 - due in class on Tues, Nov 29


Exam 1 in CPSC 455/555 // ECON 425/563 will be given in class on Thursday, October 13, 2011.
Exam 2 in CPSC 455/555 // ECON 425/563 will be given in class on Thursday, December 1, 2011. It will be a 1.25-hour, closed-book exam and will cover the following material:


Tues, Sept 20: HW1 due
Tues, Oct 11: HW2 due
Thurs, Oct 13: Exam 1
[Fri, Oct 21: Drop date]
Thurs, Oct 27: HW3 due
Thurs, Nov 17: HW4 due
[Nov 19 - Nov 27: Thanksgiving break]
Tues, Nov 29: HW5 due
Thurs, Dec 1: Exam 2

Note: There is no final exam during exam period at the end of the semester.


Homeworks: 50% (5 homeworks, 10% each)
Exam 1: 25%
Exam 2: 25%


  1. September 1, 2011: Course Overview, Introduction. [slides]
  2. September 6, 2011: Introduction to game-theoretic concepts and their relevance to routing and network formation. Nash equilibrium, dominant-strategy equilibrium, price of anarchy, price of stability. See Chapters 1 and 17 of Nisan et al.
  3. September 8, 2011: Price of Stability and Price of Anarchy in local and global connection games. See Sections 19.2 and 19.3 of Nisan et al.
  4. September 13, 2011: Algorithmic mechanism design, strategyproofness, second-price auctions, and lowest-cost-path mechanisms
  5. September 15, 2011: Distributed algorithmic mechanism design, interdomain routing, and ex-post Nash equilibrium. See Chapter 14 of Nisan et al. Thanks to Yale alumnus Vijay Ramachandran, we have this introduction to interdomain routing and the Gao-Rexford framework.
  6. September 20, 2011: VCG mechanisms, the Clarke pivot rule, combinatorial auctions (CAs), and a strategyproof, approximately optimal, polynomial-time mechanism for single-minded bidder CAs. See Sections 9.3, 11.1 and 11.2 of Nisan et al.
  7. September 22, 2011: Guest lecture by Professor Dirk Bergemann of the Yale Economics Department, based on the following papers:
  8. September 27, 2011: Bidding languages and communication complexity in CAs. See Sections 11.4 and 11.6 of Nisan et al.
  9. September 29, 2011: Guest lecture [.pptx, .pdf] by Shaili Jain of the Yale Computer Science department on iterative CAs and the query model. See Section 11.5 of Nisan et al.
  10. October 4, 2011: More detailed look at material needed for HW2 problems from Chapter 11: algorithmic techniques, demand queries, value queries, and OR* bids.
  11. October 6, 2011: More detailed look at material needed for HW2 problems from Chapter 28: Generalized Second Prize (GSP) ad auctions, full-information Nash Equilibrium conditions, and locally envy-free equilibrium conditions. We also reviewed the relationship of the generalized English auction and the GSP and took an interesting detour into a discussion of user privacy in advertiser-supported search and email.
  12. October 11, 2011: Review for Exam 1. Introduction to Peer-To-Peer (P2P) systems. See Sections 23.1 and 23.2 of Nisan et al.
  13. October 13, 2011: [Exam 1][Solutions]
  14. October 18, 2011: A minimal P2P model and introduction to the BitTorrent system. See Section 23.3 of Nisan et al. and Section 3.2 of http://www.seas.harvard.edu/courses/cs186/doc/3-P2P-file-sharing.pdf.
  15. October 20, 2011: Extensive form games, subgame-perfect equilibria, and repeated PD. See Section 27.2 of Nisan et al. and Sections 2.4 and 2.5 of http://www.seas.harvard.edu/courses/cs186/doc/2-game-theory.pdf.
  16. October 25, 2011: Strategic analysis of BitTorrent. See Sections 3.2.3, 3.3, and 3.4 of http://www.seas.harvard.edu/courses/cs186/doc/3-P2P-file-sharing.pdf.
  17. October 27, 2011: Introduction to the Pay-Your-Dues (PYD) strategy for repeated Prisoners' Dilemma and to peer prediction in reputation systems. See Sections 27.3 and 27.4 of Nisan et al.
  18. November 1, 2011: More about peer prediction and reputation functions. See Sections 27.4 and 27.5 of Nisan et al.
  19. November 3, 2011: Value sybilproofness and rank sybilproofness of reputation functions; see Section 27.5 of Nisan et al. The optimality of the PYD strategy in repeated Prisoners' Dilemma games with whitewashing; see this paper by Friedman and Resnick.
  20. November 8, 2011: Guest lecture by Georgios Zervas of the Yale Computer Science Department, based on this paper.
  21. November 10, 2011: Introduction to prediction markets. See Section 26.5 of Nisan et al. and this paper.
  22. November 15, 2011: Weighted-threshold functions and the Shapley-Shubik market game (Theorems 5 and 6 of this paper).
  23. November 17, 2011: The complexity of the matching problem in Combinatorial Prediction Markets; see Section 26.3 of Nisan et al. In the Shapley-Shubik market game, n rounds of trading suffice for weighted threshold functions of n Boolean variables; see Theorem 8 of this paper.
  24. November 29, 2011: Review for Exam 2
  25. December 1, 2011: [Exam 2][Solutions]