ECON 425/563 and CPSC 455/555
Lectures | Course Information | Reading Materials | Homework | Exams
Lectures
| 1. | September 4, 2008: Course Overview, Introduction. [slides] |
| 2. | September 9, 2008: Games with Complete Information, Pure Strategies, Mixed Strategies, Nash Equilibrium. (AGT Chapter 1) [notes] |
| 3. | September 11, 2008: Dominance Solvability, Rationalizability, Correlated Equilibrium, Bayesian Games. (AGT Chapter 1) [notes] |
| 4. | September 16, 2008: Mechanism Design, Auctions, Vickrey-Clark-Groves Mechanism. (AGT Chapters 9 and 10) [notes] |
| 5. | September 18, 2008: Theory of Computation, Computational Complexity, P, NP, PSPACE. [notes] |
| 6. | September 23, 2008: Coping with NP-hardness: Special Cases and Approximation Algorithms. |
| 7. | September 25, 2008: Internet History, Architecture, and Routing. [slides] |
| 8. | September 30, 2008: Routing Games. [slides] |
| 9. | October 2, 2008: Distributed algorithmic mechanism design and interdomain routing. |
| 10. | October 7, 2008: Network-formation games. |
| 11. | October 9, 2008: Combinatorial Auction: Complements and Substitutes, Vickrey-Clarke-Groves mechanism [notes] |
| 12. | October 14, 2008: Combinatorial Auctions: Ascending Price Algorithm, Gross Substitute Property [notes] |
| 13. | October 16, 2008: Exam 1: Questions and Answers |
| 14. | October 21, 2008: Combinatorial Auctions: Linear Programming, Duality, Walrasian Equilibrium. [notes] |
| 15. | October 23, 2008: Sponsored Search Auction: VCG and Generalized Second Price Auction |
| 16. | October 28, 2008: Sponsored Search Auction: Envy Freeness and Linear Programming |
| 17. | October 30, 2008: Sponsored Search Auction: Incomplete Information and Ascending Auction |
| 18. | November 4, 2008: Online Privacy [slides] |
| 19. | November 6, 2008: Digital Copyright [slides] |
| 20. | November 11, 2008: An Economic Analysis of DRM [paper] |
| 21. | November 13, 2008: Recommender Systems and Collaborative Filtering [slides] |
| 22. | November 18, 2008: Reputation and Trust [notes] |
| 23. | November 20, 2008: Friedman and Resnick’s “Pay Your Dues” strategy for repeated games with cheap pseudonyms (AGT Chapter 27) and overview of information markets (see Pennock’s tutorial slides). |
| 24. | December 2, 2008: Guest lecture on real combinatorial auctions by William Walsh of CombinetNet. Overview and background reading can be found here. |
| 25. | December 4, 2008: Exam 2: Questions and Answers |
Course information
Time and location: TTh 2:30 – 3:45 pm, BCT 102
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. Some familiarity with basic computational theory and basic microeconomic theory is helpful but not a formal prerequisite. The course both satisfies the QR requirement and counts as a CS-major elective.
Instructors: Dirk Bergemann and Joan Feigenbaum
Note: Professor Feigenbaum suffers from repetitive-strain injury and cannot handle large amounts of email. Students should not send her email about this course but rather should contact her through the TA, through her assistant (Judi.Paige@yale.edu, x6-1267), during class, or during her office hour.
Textbook: Algorithmic Game Theory, eds.: Noam Nisan, Tim Roughgarden, Eva Tardos, and Vijay Vazirani, Cambridge University Press, 2007. This book is available at Labyrinth Books (290 York St.). On this page, it’s referred to as “AGT.”
TA: Aaron Johnson
Office hours:
| Professor Dirk Bergemann: | Tuesdays, 1:00 to 2:30 pm |
| Professor Joan Feigenbaum: | Thursdays, 11:30 am to 12:30 pm and by appointment |
| TA Aaron Johnson: | Wednesdays, 2:30 to 3:30 pm and by appointment |
Topic outline:
- Review of basic microeconomic theory and basic computational theory
- Routing in data networks
- Combinatorial auctions
- Sponsored search
- Privacy and security
- Reputation management
Schedule:
| October 2, 2008: | First HW due |
| October 14, 2008: | Second HW due |
| October 16, 2008: | First Exam (in class) |
| October 24, 2008: | Fall semester drop date |
| October 30, 2008: | Third HW due |
| November 13, 2008: | Fourth HW due |
| December 2, 2008: | Fifth HW due |
| December 4, 2008: | Second Exam (in class) |
Reading Materials
Textbook
Algorithmic Game Theory, eds.: Noam Nisan, Tim Roughgarden, Eva Tardos, and Vijay Vazirani, Cambridge University Press, 2007. This is the textbook for the course. It is available at Labyrinth Books (290 York St.)
Alternative introductory material (on reserve in Becton Library)
An Introduction to Game Theory, by Martin J. Osborne, Oxford University Press, 2004.
A Course in Game Theory by Martin J. Osborne and Ariel Rubinstein, MIT Press.
Computers and Intractibility: A Guide to the Theory of NP-Completeness by M.R. Garey and D.S. Johnson, Freeman, 1979.
Introduction to Algorithms (2nd ed.) by T.H. Cormen, C.E. Leiserson, and R.L. Rivest. MIT Press and McGraw Hill, 2001. (1st edition published in 1990)
Leisure reading
John Von Neumann: The Scientific Genius Who Pioneered the Modern Computer, Game Theory, Nuclear Deterrence, and Much More by Norman MacRae.
A Beautiful Mind: The Life of Mathematical Genius and Nobel Laureate John Nash by Sylvia Nasar.
Breaking the Code by Hugh Whitemore. Amber Lane Press, 1987. First performed in London’s West End in 1986 and NY’s Broadway in 1987.
Homework
- Homework 1a (Due Thursday, October 2nd)
- This is the first half of the first homework. The second part will be posted on Tuesday, Sept 23 (after the second CS-review lecture), and both parts of HW1 are due on 10/2.
- Homework 1b (Due Thursday, October 2nd)
- This is the second half of the first homework.
Solutions for Homework 1
- Homework 2 (Due Tuesday, October 14th)
-
Ch 11, # 3, 7, and 8(Pushed to HW3.)
Ch 14 # 5 and 7 [Errata]
Ch 19 # 1, 4
Problem on selfish routing.
Solutions for Homework 2 - Homework 3 (Due Tuesday, November 4th)
Solutions for Homework 3 - Homework 4 (Due Thursday, November 13th)
- Homework 5a (Due Tuesday, December 2nd)
- This is the first part of the fifth homework. There is a second part that will be posted by Tuesday, Nov. 18. Both parts of HW5 are due on 12/2.
- Homework 5b (Due Tuesday, December 2nd)
- This is the second and final part of the fifth homework.
Solutions for Homework 5
Exams
Exam 1
Exam 1 in ECON 425/563 // CPSC 455/555 will be given in class on Oct 16, 2008.
It will cover five basic topics:
- Different types of equilibria or solution concepts
- Finding solutions (in the sense of 1 above) of specific games
- Combinatorial auctions
- The Internet as an economy, as exemplified by interdomain routing
- Games on graphs (routing games and graph-formation games)
This material is covered in
- AGT Chapters 1, 9, 11.1, 11.2, 11.3, 11.7, 14.1, 14.3, 18.1, 18.2, 18.3, 18.4, 19.1, and 19.2
- Notes and slides from September 9, September 11, September 16, September 25, and September 30, and
- Homework assignments 1 and 2.
Exam 2
Exam 2 in ECON 425/563 // CPSC 455/555 will be held in class on December 4, 2008 and will cover the following topics:
- Sponsored search auctions
- Recommender systems and collaborative filtering
- Reputation and trust
- Information markets
To study for this exam, you should review:
- Lecture notes and slides for October 23, 2008 through November 20, 2008
- Homework assignments 3 and 5
- The survey articles by Resnick et al. mentioned in homework assignment 5a
- Sections 26.1, 26.2, 26.5, 27.1, 27.2, 27.3, 28.1, 28.2, and 28.3 of AGT
- Practice Questions for Information Markets [Solutions]
These questions about information markets should be useful in studying for Exam 2. This is just a study aid, not an assignment; you need not hand it in and won’t be graded on it.