Spring 2007, Carleton College

- 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.

- 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!

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

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!)

- 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.
- 30 March 2007 (F): more on notions of equilibrium.

ln -s /Accounts/courses/cs395/dlibenno-econ/submissions cs395

acroread ~/cs395/ultimatum/instructions.pdf &

The wikipedia entries on expectation and risk aversion.

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.
- 6 April 2007 (F): linear programming, finding Nash equilibria via LPs.

Christos Papadimitriou. "The Complexity of Finding Nash Equilibria" from

Bernard von Stengel. Three pages from "Equilibrium Computation for Two-Player Games" from

Christos Papadimitriou. "The Complexity of Finding Nash Equilibria" from

The wikipedia entries on the ellipsoid algorithm and the simplex algorithm.

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.

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.

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

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.
- 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.

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.

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.

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.

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)

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
copy.