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

 

  1. Basic Social choice theory (Arrow)
  2. Introduction to mechanism design (Vickery-Clarke-Groves, Gibbard-Satterthwaite)
  3. Introduction to Auctions (private value)
  4. Combinatorial Auctions
  5. Online markets
  6. 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 25th.  (Comment: two corrections were made in question 3c on December 13.)
  2. Exercise 2, due date: February 5th.

 

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.