Errata for the textbook can be found here.

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.

Chapter 14: 2, 3, 6, 7

Chapter 19: 3, 4, 6, 9

Chapter 11: 1, 3, 5

Chapter 28: 2, 4, 5

Chapter 23: 1, 2

Chapter 27: 1, 2, 3, 5

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:

- (a) Show how to use the simple model of Section 26.5 to predict the results of a referendum in which 60% of the voters must vote "yes" for the ballot proposition to pass. That is, give a Boolean function f that captures the semantics of such a referendum and prove that it satisfies the sufficient condition under which the equilibrium price of F will reveal the true value of f(x).
- (b) For the Boolean function f that you provided in part (a), show how the price-formation process reveals the value of f(x) on the input vector (0, 1, 0, 0, 1) and the uniform common prior. That is, give the bids of each agent in each round and the clearing price in each round, give the equilibrium price, and explain why the process terminates when it does.

Exam 1 in CPSC 455/555 // ECON 425/563 will be given in class on Thursday,
October 13, 2011.

- It will be a closed book exam and will cover the following material:
- Notes and slides from classes on Sept. 1 through Oct. 6
- Homeworks 1 and 2
- The following parts of Algorithmic Mechanism Design, by Nisan et al:
- Sections 1.1, 1.2, and 1.3
- Sections 9.3 and 9.4
- Chapter 11 (except 11.3 and 11.7)
- Chapter 14
- Sections 19.1, 19.2, and 19.3.1
- Chapter 28

- Most of the exam problems will be similar (but not identical) to homework problems. You may also be asked to provide definitions, examples, theorem statements, and/or (short) proofs that are given in the textbook sections above.

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:

- Notes and slides from classes on Oct. 11 through Nov. 17, inclusive (except for the part of Oct. 11 that was devoted to review for Exam 1 and the guest lecture on Nov. 8 by Georgios Zervas)
- Homeworks 3, 4, and 5
- The following parts of Algorithmic Mechanism Design, by Nisan et al:
- Sections 23.1, 23.2, 23.3
- Sections 26.4, 26.5
- Chapter 27

- The paper "Computation in a Distributed Information Market," by Feigenbaum, Fortnow, Pennock, and Sami
- Sections 2.4, 2.5, 3.2, 3.3, and 3.4 of the lecture notes from Professor Parkes's cs186 at Harvard
- As on Exam 1, some of the exam problems will be similar (but not identical) to homework problems. You may also be asked to provide definitions, examples, theorem statements, and/or (short) proofs that are given in the lectures, notes, paper, and textbook sections and chapter listed above.

[**Fri, Oct 21**: Drop date]

[**Nov 19 - Nov 27**: Thanksgiving break]

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

- September 1, 2011: Course Overview, Introduction. [slides]
- 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.
- 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.
- September 13, 2011: Algorithmic mechanism design, strategyproofness, second-price auctions, and lowest-cost-path mechanisms
- 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.
- 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.
- September 22, 2011: Guest lecture by Professor Dirk Bergemann of the Yale Economics Department, based on the following papers:
- September 27, 2011: Bidding languages and communication complexity in CAs. See Sections 11.4 and 11.6 of Nisan et al.
- 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.
- October 4, 2011: More detailed look at material needed for HW2 problems from Chapter 11: algorithmic techniques, demand queries, value queries, and OR* bids.
- 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.
- 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.
- October 13, 2011: [Exam 1][Solutions]
- 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.
- 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.
- 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.
- 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.
- November 1, 2011: More about peer prediction and reputation functions. See Sections 27.4 and 27.5 of Nisan et al.
- 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.
- November 8, 2011: Guest lecture by Georgios Zervas of the Yale Computer Science Department, based on this paper.
- November 10, 2011: Introduction to prediction markets. See Section 26.5 of Nisan et al. and this paper.
- November 15, 2011: Weighted-threshold functions and the Shapley-Shubik market game (Theorems 5 and 6 of this paper).
- 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.
- November 29, 2011: Review for Exam 2
- December 1, 2011: [Exam 2][Solutions]