Topics on the border of Economics and Computation

Instructor: Noam Nisan

Scope

Recently we have seen research that combines topics and points of view of economic theory, game theory, and theoretical computer science. Part of the motivation for this combination is the Internet which, on one hand, carries complex computer-assisted economic transactions, and, on the other hand, involves cooperation and competition between technological systems that are owned and operated by different players with different goals. Studying and designing such systems and applications requires integrating the economic and computational considerations. This course will introduce some of the issues on this border of computation, economics, and game-theory.

Tentative Syllabus

Part I. Computation and Games

1. Zero-sum games, LP-duality, and randomized algorithms
2. Game-tree evaluation
3. Introduction to (non-cooperative) game-theory and the Nash equilibrium
4. Potential Games 
5. The price of Anarchy
6. Coordinated equilibrium and regret minimization
7. Graphical games

Part II.  Computation and Auctions

8. Basic Social choice theory (Arrow)
9. Introduction to mechanism design (Vickery-Clarke-Groves, Gibbard-Satterthwaite)
10. Introduction to Auctions (private value)
11. Combinatorial Auctions
12. Online markets
13. Digital Goods

Lecture Notes

Each student is expected to prepare scribe notes for one lecture.  Here is a basic LaTeX template to use. Here are various LaTeX tutorials.  

Scribe notes:

Lecture	Date	Topic	Scribes
1	30.10	Introduction; zero-sum games	Michael Schapira
2	6.11	Min-max theorem; randomized algorithms; game-tree evaluation	Ariel Procaccia
3	13.11	Game-tree evaluation; General-sum games Pure Nash equilibrium;	Maor Ben-Dayan
4	20.11	Potential Games and PLS	Shahar Dobzinski
5	27.11	Congestion games and Price of stability	Robby Lampert
6	4.12	Price of anarchy and Mixed Nash equilibrium	-
7	11.12	Nash's Theorem, Computational hardness, and Correlated equilibrium	Yoram Bachrach
8	18.12	Social choice, Arrow's theorem, Gibbard-Satterswaite theorem	Ofer Dekel
9	25.12	Arrow + Gibbard-Satterswaite proofs	Ilan Nehama
10	1.1	Hanukah vacation – you can go the Israeli seminar on game-theory in Ra’anana	-
11	8.1	Games with incomplete information, Mechanism design	Michael Zuckerman
12	15.1	Mechanism design, truthfulness, revelation principle	-
13	22.1	VCG mechanism, Combinatorial auctions	-
14	29.1	Combinatorial auctions	-

Exercises

1. Exercise 1, due date: December 25^th. (Comment: two corrections were made in question 3c on December 13.)
2. Exercise 2, due date: February 5^th.

Grades

Here is the current list of grades. I will wait a little more to get the lecture notes from those who have not handed them in yet. The formula for final grade is 34% for each exercise and 34% for the lecture notes.