CPS 296.3 - Topics in Computational Economics

Topics in Computational Economics (CPS 296.3), Spring 2007

Details
Tu-Th 4:25PM-5:40 PM, LSRC D243
Instructor: Vincent Conitzer. (Please call me Vince.)

Office hour: Tu 3-4, LSRC D207.

Description
In recent years, computer scientists' interest in techniques from economics has surged. This interest 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.

This course will introduce students to various topics in computational economics. A key objective is to demonstrate the tremendous diversity of these topics, and to encourage students to think creatively about new applications.

The topics covered in this course are related to those covered in CPS 296.2 Fall 2006, but the goal is to have minimal to no overlap with that course (so that taking both courses, or only this course, makes sense). A wider range of topics will be covered in this course, and there will be more of a focus on applications. Also, unlike CPS 296.2 Fall 2006, this course will be a seminar-style course in which recent research papers are discussed, and students will be involved in the presentation and possibly even the selection of these papers.

Possible topics include:
Computer poker and other imperfect-information games
Economic solutions to spam
Human-computer interaction issues in e-commerce
Incentive compatible rating systems
Information markets
Job scheduling with selfish agents
Keyword auctions
Kidney exchanges
Market-based computer systems
Matching
Multiagent learning
Real-world combinatorial (reverse) auctions
Selfish routing
Trading agent competitions
Web ranking systems (e.g. PageRank) and connections to social choice theory
...

Prerequisites
If you took (or sat in on) CPS 296.2 Fall 2006, you should be very well-prepared for this course. If not, you are still welcome to take the course, but you should be prepared to do some extra reading during the first few "review" lectures: please start reading the materials for the first few lectures, labeled "review", as soon as possible.

Undergraduates, as well as interested students without computer science backgrounds (e.g. students in economics or mathematics), are welcome in principle but should talk to Vince first.

Grading
Subject to change based on course enrollment.
You will have a choice between doing a course project, and not doing a course project. The former is encouraged but not required. If you do the latter, you will be required to perform additional course duties, perhaps including giving additional presentations or writing up notes for a lecture.

"Course project" option:
Participation: 25%
Course presentations: 25%
Project: 50%

"No course project" option:
Participation: 35%
Course presentations & other course duties: 65%

You will be required to decide between these options on or before 2/6.

Because there will be no exams, a mature attitude is expected of the students in this course. You should be very self-motivated in reading the materials and paying attention in class. If you do so, towards the end of the course, it will definitely show.

Auditing: Auditors that attend a significant portion of the course will probably be required to fulfill the same requirements as the "no course project" option, but this may change based on enrollment.

"Course project" option
For those of you doing projects (which is encouraged!), the project will be a major component of your grade. The goal is to try to do something novel (not merely doing a survey of existing work) -- this is not as hard it may sound! You may work on a project alone, or with multiple people. Projects may be theoretical, experimental (based on simulations), experimental (based on real-world data), a useful software artifact, or any combination thereof. Be creative! Any topic covered in this course, or in CPS 296.2 Fall 2006, is fair game. If you have another topic that is you feel is sufficiently related to the course, this will probably be OK as well, but talk to Vince first. The final product is a writeup (in the form of a research paper) and a class presentation (all team members must participate in the presentation). Some projects may well lead to publishable papers (perhaps with some additional work).

In order to produce a strong project, it is important to start thinking about the project early. An initial proposal is due early in the course. This proposal should explain the topic of your project, what types of results you hope to obtain, and what some of the technical issues are that you will need to address. If necessary, Vince can help with finding topics. Some general suggestions for finding topics:

1. Look at the course topics that sound interesting to you early on. If materials on that topic are not yet available, talk to Vince for pointers (perhaps he can even make the slides for that topic a little early for you).

2. Consider your own research and its relationship to the course. Do you work on techniques that can be applied to any of the course's problems? Can techniques in the course help your work?

3. Take some result in the course that you like, and change the setting. Do things become easier (harder) if we look at a more restricted (more general) version of the problem? Do analogous results hold in similar settings?

Some more specific ideas are provided here.

An intermediate project progress report is also required. This report should explain what results you have obtained already, what (if any) difficulties you encountered, and what you plan to do to complete your project. Ideally, at this point, you should already have some good results, so that you can spend the rest of your time on answering questions generated by your results, as well as preparing your writeup and presentation.

Important dates:
2/6: Decision between "course project" and "no course project" options due.
2/22: Project proposal (1+ pages) due.
3/22: Project progress report (~2 pages) due.
4/17: Final project writeup due.
Last few lectures of the course: students will present their projects in class.

"No course project" option
You can also choose to not do a project. In this case, you will be required to be significantly more involved in other aspects of the course. What exactly this means will be determined once everyone has decided on whether to do a project, but the basic guideline is that this option should be as much work as the other option. One possibility that "no course project" option students will be required to present 2 or more times as often in class. Other additional tasks may also be required.

Presenting in class
Before your class presentation, you should do the following:
1. Decide exactly which material you will cover, and let Vince know well ahead of time so that he can assign readings to the class.
2. Decide how you will present the material. You may use slides or just the whiteboard; the important thing is that the presentation is clear. Use lots of examples, try to get the class involved.
3. Prepare your presentation well. Practice. Make sure that you will be presenting for the appropriate amount of time. You should understand the material that you are covering very well and be able to answer questions about it.

Book
For the review lectures, 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. (Just append book/SLB.pdf to the URL in your browser -- I do not want to make a link to the draft. Access from within Duke only -- let me know if you want to start reading but you are away from campus and cannot access it.) The draft appears to be very good, but let me know if you find anything that does not seem to be accurate. Please do not distribute the draft.

Schedule
Note: the first few lectures will review basic concepts in game theory and mechanism design that we will use. These topics (as well as many other related ones) were covered in much more detail in CPS 296.2 Fall 2006. If you are unfamiliar with these topics, or feel that you could use a refresher, you should start reading the materials for these review lectures as soon as possible. Everyone should be comfortable with these basics after the review lectures.

For this review stage, if you want more detail/additional resources/homework and exam problems to challenge yourself, you can also look at the materials on the web page of CPS 296.2 Fall 2006, up to and including the 9/26/2006 lecture (and perhaps the midterm). Please let me know if you need additional help.

Date	Topic	Materials
1/16	Course at a glance. Topics at the border of computer science and economics. Course organization and requirements.	Slides. Please start reading the materials for the review lectures below.
1/18	Review: Expected utility theory. (Noncooperative) game theory.	Slides. SLB Appendices B and C, Chapter 3 up to and including 3.3.5, Chapter 5 up to and including 5.2.2 (you can skip alpha-beta). Optional/recommended: remainder of Chapter 3; Chapter 4 (computing solutions); remainder of Chapter 5 (computing solutions).
1/23	Review: Game theory continued: extensive-form games, repeated and stochastic games.	SLB Sections 6.1, 6.2.
1/25	Review: Social choice theory. Mechanism design.	Slides. SLB Section 6.3, Chapter 7, Chapter 8 up to and including 8.6. Optional/recommended additional resource on social choice: section on voting. Optional/recommended alternative resources on mechanism design: Chapter on mechanism design + chapter on revelation principle. Parkes chapter on mechanism design.
1/30	Review: Auctions. Combinatorial auctions.	Slides. SLB Chapter 9. Optional/recommended additional resources on combinatorial auctions: Lehmann et al. chapter on winner determination. Sandholm chapter on optimal winner determination.
2/1	Class starts early for brief algorithms/complexity review, as e-mailed. Auctions continued.
2/6	More detailed overview of topics in the course.	We will begin assigning topics to students for presentation around this point.
2/8	Automated mechanism design.	Slides. Chapter on automated mechanism design, read up to and including 6.6.
2/13	Guest lecture: Pino Lopomo (Fuqua). Mechanism design, solving individual instances using automated mechanism design to help conjecture the general form of the optimal mechanism.
2/15	Learning in games. Evolutionary game theory.	Slides. SLB 14.1, 14.2, 14.5, 14.6, 14.7.1, 14.7.2.
2/20	Yi: ranking systems. Dongdong: computation in a distributed information market.	PageRank axioms paper. Computation in a distributed information market paper.
2/21, LSRC D106	Special lecture: Nicole Immorlica. Algorithmic Game Theory with Applications to Online Auctions.	Paper.
2/22	Ed: matching. Nihshanka: kidney exchanges.	Gale-Shapley paper. Kidney exchange paper.
2/27	Guest lecture: Atila Abdulkadiroglu (economics). Matching students to schools.
3/1	Matt and Meng: automated trading.	Project proposal due. Paper 1, paper 2.
3/6	Joe: CAPTCHAs. Nikhil: games with a purpose.	See papers below on these topics.
3/8	Mingyu and Yi: sponsored search, keyword auctions.	Paper on equilibria in position auctions. Generalized second price auction analysis paper.
3/13	Spring Break, no class.
3/15	Spring Break, no class.
3/20	Adam: incentive compatible rating. Vinod: information/prediction markets.	Paper on minimizing payments to encourage truthful feedback. Paper on partial information elicitation. Dynamic parimutuel market paper.
3/22	Aaron and Yi: multiagent learning.	Project progress report due (Friday 5pm in my office at the latest). Paper on stochastic games as a framework for multi-agent reinforcement learning and minimax Q-learning. Paper on Q-learning in general-sum stochastic games. Paper on RoboCup soccer keepaway.
3/27	No class.
3/29	Ming: multiagent learning. Vinod: neuroeconomics.	Paper on coordinating actions in multiagent systems. Neuroeconomics: 1, 2, 3.
4/3	(Vince) Public goods, charitable donations, cost sharing.	An example of matching students to presentation slots worked out by hand, code used to match students to presentation slots, example, actual bids. Slides. Paper on expressive donation matching. Paper on cost sharing.
4/5	Student project presentations and discussion. Ed, Nikhil.
4/9, 4pm-5pm, 130A North Building	Special lecture: Tuomas Sandholm. Solving imperfect-information games.
4/10	Student project presentations and discussion. Dongdong, Matt.
4/12	Student project presentations and discussion. Aaron, Joe, Meng.
4/17	Student project presentations and discussion. Mingyu, Nihshanka, Vinod.	Final project writeup due.

Resources
Note: these are resources for some interesting topics that were not already covered in CPS296.2 Fall 2006, or in the review part of this class.
Some of the references below are (sections of) web pages with lists of publications; as a general guideline, it's best to first look at papers closest to the top of the page.
It is also a good idea to look at the papers that these papers cite.

Sponsored search and keyword auctions
Michael Kearns' course on sponsored search.
Brief history of sponsored search paper.
Paper on equilibria in position auctions.
Paper analyzing different slot auction designs.
Generalized second price auction analysis paper.
Truthful keyword auctions paper.
Paper on optimize-and-dispatch architecture for expressive ad auctions.

Information/prediction markets
David Pennock's publications page.
Paper comparing information markets and opinion pools.
Computation in a distributed information market paper.
Dynamic parimutuel market paper.
Securities based on logical formulas paper.

Ranking systems (e.g. PageRank) and social choice
Alon Altman's page.
QuickRank paper.
PageRank axioms paper.
Axiomatic foundations of ranking systems paper.
Incentive compatible ranking systems paper.
Quantifying incentive compatibility paper.

A few human-computer interaction issues/opportunities
Luis von Ahn's research page.
CAPTCHA page.
Paper on CAPTCHAs.
Another paper on CAPTCHAs.
Paper on breaking CAPTCHAs.
Paper on games with a purpose.
ESP game paper.
Paper on Peekaboom.

Matching and kidney exchanges
Al Roth's page, kidney exchange section.

Incentive compatible rating
Wikipedia entry on proper scoring rules.
Paper on minimizing payments to encourage truthful feedback.
Paper on partial information elicitation.

Multiagent (reinforcement) learning
Also see review lecture on learning in games above for more references.
Paper on stochastic games as a framework for multi-agent reinforcement learning and minimax Q-learning.
Paper on Q-learning in general-sum stochastic games.
Paper on correlated Q-learning.
Paper on no-regret algorithms.
Paper on learning to play an optimal Nash equilibrium in team Markov games.

Online mechanism design (i.e. mechanisms where decisions have to be made over time)
Harvard EconCS bibliography, online mechanism design section (other sections are also interesting!).
Mechanism design for online real-time scheduling paper.
Paper on online algorithms for market clearing.

Paper on the sequential auction problem on eBay.

Automated trading
Penn-Lehmann Automated Trading Project (PLAT).
Paper on PLAT.

Mechanism design and machine learning
Mechanism design and machine learning paper.