COMPSCI 323: Computational Microeconomics, Spring 2020



Details
WF 10:05-11:20am, Social Sciences 136.
M 10:05-11:20am, Physics 128 recitation slot -- we will occasionally use this slot for lectures due to scheduling constraints.
First class: Friday, January 10, 2020.
Instructor: Vincent Conitzer. (Please call me Vince.) Office hours: TBD.

Teaching Assistants: Caspar Oesterheld, Jiali Xing, and Hyoung-Yoon Kim. Office hours: TBD.

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, building computer poker players, and security.

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. The formal requirement is at least one of the following: Computer Science 230, 200-level Mathematics course, or 200-level Statistical Science course. But you should know or be able to quickly pick up some basic probability. Generally, the course will probably not be enjoyable for students who dislike mathematics.

Book
We will use parts of a book by Shoham and Leyton-Brown (SLB), Multiagent Systems. A free electronic copy is available at that link though the printed version is very reasonably priced as well.
There will be additional readings for individual classes. The slides for the course are also part of the reading.

Grading (tentative and subject to change)
Participation: 10%
Programming assignments: 15%
Written assignments: 15%
Midterm: 20%
Final exam: 40%

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).
Schedule
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 and we may not cover all topics).

Date Topic Materials
1/10 Course at a glance. Slides: ppt, pdf.
Homework 0 out (due 1/17 before class).
Week 1 recitation materials.
Optional: CACM overview article.
Part 0: Basic techniques from computer science.
1/15-? Linear programming. (Mixed) integer linear programming. Slides: ppt, pdf.
Example files: painting.lp, knapsack.lp, knapsack_simple.mod, knapsack.mod, cell.lp, cell.mod, hotdog.mod, sudoku.mod.
SLB Appendices A, B.
Programming assignment 1 out (due 1/31 before class).
Guide to the modeling language. Here are also lecture notes I wrote those for a course on linear and integer programming; if you want to learn more about these topics there may be some useful resources on that course's website.
Part 1: Expressive marketplaces.
Part 2: Game theory.
Part 3: Mechanism design.
Tuesday, April 28, 9am - noon. Final exam.