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

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.

Homeworks

Exams

Schedule

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

Grading

Lectures

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:
   • "Position auctions", by Hal Varian
   • "Internet Advertising and the Generalized Second-Price Auction: Selling Billions of Dollars Worth of Keywords", by Benjamin Edelman, Michael Ostrovsky, and Michael Schwarz
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]