Economics and Computation

Lectures

Course information

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

Reading Materials

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.

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.

Homework 3 (Due Tuesday, November 4th)

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.

Exams

Exam 1 in ECON 425/563 // CPSC 455/555 will be given in class on Oct 16, 2008.

It will cover five basic topics:

1. Different types of equilibria or solution concepts
2. Finding solutions (in the sense of 1 above) of specific games
3. Combinatorial auctions
4. The Internet as an economy, as exemplified by interdomain routing
5. 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 in ECON 425/563 // CPSC 455/555 will be held in class on December 4, 2008 and will cover the following topics:

1. Sponsored search auctions
2. Recommender systems and collaborative filtering
3. Reputation and trust
4. 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.