CS395 (Computational Aspects of Economics)
Spring 2007, Carleton College

[Jump to current week]

Basic information:

Instructor: David Liben-Nowell
Lecture: 4a (MW 12:30–1:40p, F 1:10–2:10p), CMC 209.
Office Hours: see my homepage.
Always feel free to email for an appointment if the scheduled times aren't good for you.
Official catalogue description: Consider a network where there is a cost for using each link. Suppose we compute the cheapest path connecting a source to a destination, and, for every link L used in the path, pay L's owner some profit plus L's cost. What happens if L's owner is in charge of reporting the cost of L? Can we design "incentive-compatible" algorithms so link owners have no reason to lie about their costs? Topics include this interplay between computer science and economics, the "price of anarchy", and algorithms to compute optimal strategies for competing individuals. Game theory will be a focus throughout. Prerequisites: Programming experience roughly equivalent to Computer Science 117, plus at least one of the following: Computer Science 177, Mathematics 232, or Economics 111. These prerequisites reflect an approximate desired level of familiarity with the course material, and there is considerable flexibility for students with other background; contact the instructor for permission.

Announcements:

There is an anonymous feedback form available for any comments that you have about the course. If you have any suggestions or comments on the class (style, content, workload, etc.), please feel free to use this form to let me know.
The Carleton Sentinel is the mailing list of the CS community here at Carleton. We'll use it to send occasional updates on things that might be of interest. Sign up here!

Resources:

Official Python documentation. (See also Dive Into Python.)
A LaTeX tutorial.
Michael Mitzenmacher's notes on how to read a research paper.

Course Materials:

Week 0:

There is a form for office-hours scheduling available. Please fill it out by Tuesday, 20 March 2007, and I'll schedule office hours soon thereafter. (Be sure to include your email address!)

Week 1: introduction to game theory

26 March 2007 (M): course overview and a sample game.
acroread /Accounts/courses/cs395/dlibenno-econ/submissions/simple_routing/instructions.pdf &

Reading:
Jeff Ondich's guide to programming in Python.
The wikipedia entry on game theory.
Eva Tardos, Vijay Vazirani. "Basic Solution Concepts and Computational Issues" from Algorithmic Game Theory, §1.1–1.3.
Don Ross. Game Theory, from Stanford Encyclopedia of Philosophy, 2006, §1 ("Philosophical and Historical Motivation").
28 March 2007 (W): another sample game and an introduction to game theory.

cd ln -s /Accounts/courses/cs395/dlibenno-econ/submissions cs395 acroread ~/cs395/ultimatum/instructions.pdf &

30 March 2007 (F): more on notions of equilibrium.

Reading:
(skim.) John Nash. Non-cooperative games. Annals of Mathematics, 54(2):286-295, September 1951.
The wikipedia entries on expectation and risk aversion.
(optional.) Ignacio Palacios-Huerta. Professionals Play Minimax. Review of Economic Studies, 70, 395-415, 2003.
(optional.) T. Post, M. van den Assem, G. Baltussen, R. Thaler. Deal Or No Deal? Decision Making Under Risk in a Large-Payoff Game Show, 2007.

Week 2: game theory, computation of equilibria

Problem Set #1 (the donor game) is due on Monday.

Problem Set #2 (computation of various types of equilibria) is due on Wednesday. You should have been assigned a partner by email last Friday; let me know you didn't get a note.

2 April 2007 (M): a crash course on probability and an introduction to mixed strategies.
Reading:
Eva Tardos, Vijay Vazirani. "Basic Solution Concepts and Computational Issues" from Algorithmic Game Theory, §1.4–1.6.
The wikipedia entry on linear programming.
(optional.) Robert Aumann. Subjectivity and Correlation in Randomized Strategies. J. Mathematical Economics, 1:67–96, 1974.
4 April 2007 (W): mixed strategies, solving roshambo, and Nash's theorem.

Reading:
Christos Papadimitriou. "The Complexity of Finding Nash Equilibria" from Algorithmic Game Theory, §1.1, 1.2, 1.5.
Bernard von Stengel. Three pages from "Equilibrium Computation for Two-Player Games" from Algorithmic Game Theory.

6 April 2007 (F): linear programming, finding Nash equilibria via LPs.

Reading:
Christos Papadimitriou. "The Complexity of Finding Nash Equilibria" from Algorithmic Game Theory, §1.7.
The wikipedia entries on the ellipsoid algorithm and the simplex algorithm.

Week 3: auctions

Problem Set #3 (Nash equilibria for two-by-two two-player games) is due on Monday.

If you're looking for more Python references, a good place to look is the online book Dive Into Python.

Problem Set #4 (correlated equilibria for a participation game) is due on Friday.

9 April 2007 (M): LPs for Nash equilbria for zero-sum games and correlated equilibria.
11 April 2007 (W): relating correlated and Nash equilibria; an introduction to auctions.
Reading:
ESPN.com news service article and Boston Globe article on the Daisuke Matsuzaka auction.
Vijay Krishna. "Introduction" (Chapter 1) from Auction Theory, Elsevier, 2002.
13 April 2007 (F): truthful mechanisms, the revelation principle, and Vickery auctions.
Reading:
Tim Roughgarden. Lectures on Combinatorial Auctions, §1–2.

Week 4: auctions and matching markets

Problem Set #5 (third-price sealed-bid auctions) is due on Wednesday.

16 April 2007 (M): sequential auctions, the VCG mechanism.
18 April 2007 (W): truthfulness of VCG, introduction to matching markets.
20 April 2007 (F): two-sided markets with threshold preferences.

Reading:
D. Gale, L. Shapley. College admissions and the stability of marriage. American Math. Monthly, January 1962.

Week 5: matching markets

A one-page single-spaced written summary of the Gale–Shapley paper is due on Monday. (See Michael Mitzenmacher's notes on reading research papers.)

23 April 2007 (M): stable marriage and the Gale–Shapley proposal algorithm.
25 April 2007 (W): matching markets with prices.
Reading:
David Easley, Jon Kleinberg. Matching buyers and sellers.
27 April 2007 (F): matching markets with prices, Arrow's Theorem.
Reading:
B. Edelman, M. Ostrovsky, M. Schwarz. Internet Advertising and the Generalized Second Price Auction.

Week 6: more matching markets and more auctions

A one-page single-spaced written summary of the Edelman–Ostrovsky–Schwarz paper is due on Wednesday.

30 April 2007 (M): midterm break!
2 May 2007 (W): proof of Arrow's Theorem; sponsored search.
Reading:
David Easley, Jon Kleinberg. Keyword-based Advertising.
Hal Varian. Position Auctions, International Journal of Industrial Organization, to appear.
N Vidyasagar, India's secret army of online ad 'clickers'. Times of India, 2004.
John Geanakoplos. Three Brief Proofs of Arrow's Impossibility Theorem, Economic Theory, 2005.
4 May 2007 (F): sponsored-search auctions, an experiment on information cascades.

Week 7: network effects

A form for submitting your bids for final project presentations has been posted. You should fill it out by Friday, 11 May 2007, at 11:59p. I'll schedule presentations and let you know the schedule early next week.

7 May 2007 (M): class cancelled!
9 May 2007 (W): information cascades.
Reading:
David Easley, Jon Kleinberg. Information Cascades.
Matthew Jackson, Leet Yariv. Social Networks and the Diffusion of Behavior. Yale Economic Review, to appear.
11 May 2007 (F): discussion of Steven Levitt's convo talk. If you missed convo, I'll have DVDs of the talk available early next week.

Week 8: network effects; the cost of selfish agents

Problem Set #6 (erroneous cascades) is due on Monday.

14 May 2007 (M): diffusion of innovation.
16 May 2007 (W): Braess's paradox and selfish routing.
Reading:
T. Roughgarden, E. Tardos. How Bad is Selfish Routing? J. ACM, 49(2):236-259, March 2002.
(optional.) J. Cohen, P. Horowitz. Paradoxical behaviour of mechanical and electrical networks. Nature 352:699-701, 22 August 1991.
18 May 2007 (F): more on the price of anarchy.

Week 9: the cost of selfish agents; project presentations

By 11:59p on Sunday, 20 May 2007, email me a plain-text outline of your paper.

21 May 2007 (M): course wrapup; presentations (Ben, Khanh, Jacob)
23 May 2007 (W): presentations (Ty, Max, Arthur, John, Janara)
25 May 2007 (F): presentations (Jamie, Tom, Ethan, Erik)

Week 10: project presentations

By 11:59p on Sunday, 27 May 2007, email me a PDF of a draft of your paper.

The last assignment of the term, to rewrite the course description (100 words or fewer, though justifications beyond that word count are welcome) and describe the appropriate prerequisites for the class, is due on Wednesday.

28 May 2007 (M): presentations (Anna, Jake/Dave, Lauren/George, Isao)
30 May 2007 (W): presentations (Nathan, Ed/Wain, Henry)

Finals Period:

By 7:00p on Sunday, 3 June 2007, submit to me the final paper in hard copy.

CS395 (Computational Aspects of Economics) Spring 2007, Carleton College