CS395 (Computational Aspects of Economics)
Spring 2007, Carleton College
- Instructor: David
- 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
- 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
- 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!
There is a form for
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
Week 2: game theory, computation of equilibria
Problem Set #1 (the donor game) is due on
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.
- 4 April 2007 (W): mixed strategies, solving roshambo, and Nash's
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.
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
- 11 April 2007 (W): relating correlated and Nash equilibria; an introduction to auctions.
- 13 April 2007 (F): truthful mechanisms, the revelation principle,
and Vickery auctions.
Week 4: auctions and matching markets
Problem Set #5 (third-price sealed-bid auctions)
is due on Wednesday.
Week 6: more matching markets and more auctions
Week 7: network effects
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.
Week 8: network effects; the cost of selfish
Problem Set #6 (erroneous cascades) is due on
- 14 May 2007 (M): diffusion of innovation.
- 16 May 2007 (W): Braess's paradox and selfish routing.
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
- 18 May 2007 (F): more on the price of anarchy.
Week 9: the cost of selfish agents; project
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,
- 25 May 2007 (F): presentations (Jamie, Tom,
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)
By 7:00p on Sunday, 3 June 2007, submit to me the final paper in hard