Introduction to Computational Economics (CPS 196.2), Spring 2007


Details
TuTh 4:25pm-5:40pm, North 306 (changed from before).
Instructor: Vincent Conitzer. (Please call me Vince.)

Office hour: Tu 2pm-3pm, LSRC D207.
Teaching Assistant: Mingyu Guo.
Office hour: We 1pm-2pm.
Description
In recent years, there has been a surge of interaction between computer scientists and economists. This interaction is driven both by necessity and opportunity. On the one hand, as computer systems become more interconnected, multiple parties must interact in the same environment and compete for scarce resources, which necessarily introduces economic phenomena. On the other hand, in the past, economic mechanisms (such as auctions and exchanges) have been designed to require very limited computing and communication resources, as they would otherwise be impractical. These days, computation and communication pose much less of a constraint, which presents an opportunity to create highly efficient, computationally intensive mechanisms.

In the first part of the course, we will study the design of expressive marketplaces. In such marketplaces, participant can express nontrivial valuations over outcomes: for example, a participant may express that a complete travel package to Las Vegas including a flight, hotel reservation, and entertainment is worth $700 to her, but any incomplete package is worth $0. This can greatly increase market efficiency, but clearing the market (deciding on the final outcome) becomes computationally hard. We will cover techniques for solving these problems.

In the second part of the course, we will study game theory. Game theory studies how to act optimally in strategic settings where each party's utility (happiness) depends on the actions of other parties. We will cover such definitions of optimality as well as techniques for computing optimal actions. We will study applications including bidding in auctions and building computer poker players.

In the third part of the course, we will draw on the first two parts and study how to design market mechanisms that are optimal when we take into account that agents will behave strategically (game-theoretically). Again, we will cover techniques for computing the optimal mechanisms.
Prerequisites
Students should be comfortable with probability. Background in computer science and/or economics will be helpful but neither is required; the goal is to bring together students from different backgrounds. While there are no other specific mathematical prerequisites, the course will probably not be enjoyable for students who dislike mathematics.
Book
We will use parts of a new book by Shoham and Leyton-Brown (SLB), an early draft of which can be found in a subdirectory of this directory called book/ under the name SLB.pdf. (I do not want to make a link to the draft. Access from within Duke only.) Please do not distribute the draft.

There will be additional readings for individual classes. The slides for the course are also part of the reading.
Grading (subject to change)
Participation: 10%
Programming assignments: 15%
Written assignments: 15%
Midterm: 15%
Small project: 20%
Final exam: 25%

Rules for assignments: You may discuss homework assignments with at most one other person, in person. However, you may not simply copy down the other person's solution (or any part thereof). Each person should do her/his own writeup, at which point you should derive the solution yourself. This also implies that you cannot copy any code (linear programs etc.) from each other. Copying code is considered a serious form of cheating, and there are ways of detecting copied code. If you have trouble with the programming assignments, just ask for help. On your writeup, you should acknowledge your partner (if any) and any other sources you used.

Rules for exams: Exams will be closed-book. However, you do not need to remember every detail of the modeling language (where the colons go, for example).

Rules for the project: You may work on the project in a team of size 1, 2, or 3. If there is a good reason to have even more people on the team, discuss this with Vince. Naturally, the larger the team, the more impressive your project should be. Unlike the assignments, in the project you are allowed to share everything, including code, within the project team.
The goal for the project is to allow you to get creative with some of the material in the course. For example, find an interesting problem related to computational economics and discuss how to solve it using LP/MIP (or other techniques). If you have trouble thinking of topics, Vince can help you, but try to come up with your own. More specific guidelines can be found here.
Schedule
Since this is the first time I am (or anyone else is) teaching this course, we will not plan the course down to the individual lecture. Dates will be added as the course progresses. Topics are given below (a topic need not take exactly one lecture to complete).

Date Topic Materials
8/28 Course at a glance. Slides: ppt, pdf.
Part 0: Basic techniques from computer science.
8/30, 9/4 Linear programming. (Mixed) integer linear programming. Slides: ppt, pdf.
Example files: class_example.lp, class_example2.lp, class_example3.lp, class_example4.lp, knapsack.lp, knapsack.mod, cell.lp, cell.mod, hotdog.mod, sudoku.mod.
SLB Appendices A, B.
Programming assignment 1 out (due 9/11).
Guide to the modeling language.
9/6 Computational problems. Algorithms. Runtime of algorithms. Easy and hard problems. Slides: ppt, pdf.
Sorting algorithms spreadsheet.
Example files: set_cover.mod, set_cover2.mod, matching.mod.
Part 1: Expressive marketplaces.
9/11, 9/13, 9/18 Single-item auctions. Combinatorial auctions. Bidding languages. Winner determination problem. Variants (reverse auctions, exchanges). Slides: ppt, pdf.
SLB 10 introduction, 10.1.1, 10.3 introduction, 10.3.2, 10.3.3.
9/18, 9/20 Expressive financial securities. Slides: ppt, pdf.
SLB 10.4.2.
Optional: Paper 1, paper 2.
9/20, 9/25 Barter exchanges/matching markets. Kidney exchange. Slides: ppt, pdf.
Paper (you do not need to understand all the details about constraint and column generation).
9/27 Expressive negotiation over donations. Slides: ppt, pdf.
Paper (you do not need to understand the incentive compatibility section at this point in the course).
Programming assignment 2 out. Partial solution to graph winner determination problem, for first problem.
10/2, 10/4 Voting and social choice. Slides: ppt, pdf.
SLB Chapter 8 (excluding 8.5).
Optional additional resource on social choice: section on voting.
10/4 Iterative mechanisms/preference elicitation. Slides: ppt, pdf.
Part 2: Game theory.
10/11 Risk neutrality and risk aversion. Expected utility theory. Games in normal form. Dominance and iterated dominance. Computing dominated strategies. Slides: ppt, pdf.
SLB Chapter 2 (excluding minimax regret, rationalizability, trembling-hand perfect equilibrium, epsilon-Nash equilibrium), Chapter 3 (excluding LCP/Lemke-Howson, computing NE of n-player games). Some of this runs into the next lecture.
Written assignment 1 out.
10/16, 10/18, 10/30Minimax strategies. Computing minimax strategies. Nash equilibrium. Computing Nash equilibria. Correlated equilibrium. Computing correlated equilibria.
10/23 Midterm review.
10/25Midterm.
10/30, 11/1 Games in extensive form. Backwards induction. Subgame perfect equilibrium. Imperfect information. Equilibrium refinements. Computing equilibria. Poker. Slides: ppt, pdf.
SLB Chapter 4 (excluding alpha-beta, sequence form, sequential equilibrium).
Programming assignment 3 out.
11/1, 11/6 Repeated games. Folk theorem. Stochastic games. Slides: ppt, pdf.
SLB Chapter 5 up to Bayesian games (excluding automata).
11/8, 11/13 Learning in games. Iterated best response. Fictitious play. Evolutionary game theory. Slides: ppt, pdf.
SLB Chapter 6.
SKIPPED Coalitional game theory. Core. Nucleolus. Shapley value. Computing solutions. SLB Chapter 11 (excluding compact representations).
Part 3: Mechanism design.
11/15, 11/20 Bayesian games. Auctions revisited. Slides: ppt, pdf.
For the next few lectures: SLB 5.3, Chapter 9 up to (not including) AGV, 10.1 (the parts we did not cover before).
Optional: Chapter on auctions.
11/27 Incentive compatibility. Individual rationality. Revelation principle. Clarke mechanism. Groves mechanisms. Slides: ppt, pdf.
Written assignment 2 out.
11/29, 12/4 Automated mechanism design. Slides: ppt, pdf.
Optional: Chapter on automated mechanism design, read up to and including 6.6.
12/4, 12/6 Proper scoring rules. Slides: ppt, pdf.
SLB 10.4.2.
12/6 Real-world applications. Slides: ppt, pdf.
12/13, 7pm-10pm Final exam.