COMPSCI 323: Computational Microeconomics

COMPSCI 323: Computational Microeconomics, Spring 2020

Details
WF 10:05-11:20am (all times US Eastern), ~~Social Sciences 136~~ by zoom (recordings will be made available to the best of our ability).
M 10:05-11:20am, ~~Physics 128~~ by zoom (recordings will be made available to the best of our ability), 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.) OH (~~please check whether Vince is traveling~~ Vince won't be traveling): Wednesday 11:20-11:45am (catch me right after class), Friday 11:20-11:50am (catch me right after class), ~~Monday 8:55-10am (LSRC D207) or~~ by appointment.

Teaching Assistants: Caspar Oesterheld (office hours Thursdays 3-4pm, ~~LSRC B102~~ by zoom), Jiali Xing (office hours Tuesdays 8-9pm, ~~LSRC 3rd floor between D344 and D301~~ by zoom), and Hyoung-Yoon Kim (office hours Wednesdays 3-4 pm, ~~LSRC 3rd floor between D344 and D301~~ by zoom); by appointment is likely also possible.

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)
Updated grading instructions:

The default option is now S/U grading. To get an S, I will be looking for evidence of some degree of mastery and sustained effort. A good score on the midterm OR the final (or reasonable scores on both and the homework), in combination with effort made to reasonably participate in the entire course (taking into account difficulties faced), will get you an S grade.

If you really still want to receive a letter grade, the grading criteria will remain as before (though correcting for difficulties with participation), to, as much as possible, keep things consistent with past and future iterations of the course. Given the complexity of the situation and how hard it is to forecast what situation you will be in, e.g., at the time of the final, I would generally not recommend the letter grade option.

Participation: 10%
Programming and written assignments: 30%
Midterm: 20%
Final: 40%

The midterm and final will be takehome with much more time than you should need for them. Generally, for S/U, I don't intend for things to be hard and I don't expect students to have difficulty; I'll generally be lenient, with the exception of cheating. This is not a situation anyone ought to take advantage of by cheating; therefore, I will treat cheating more harshly and cheating will be penalized (at least) with failing the course. If you have trouble, please reach out. We are here to help. We don't want to make things hard for you.

Rules for assignments (not midterm and final): 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.

Updated rules for midterm and final: You may now use all the materials from the course website (slides, the book, etc.). On these, you may not work with any other person, or access the rest of the Internet. Do not communicate with anyone else about the midterm or the final (until everyone has turned them in). If you break these rules you will run the risk of being classified as cheating. If you feel you may have accidentally gotten input that you should not have had, you must report it immediately and proactively to not run the risk of being classified as cheating.

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-1/24	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.
1/25 (bonus lecture)	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. Optional: CACM article on P vs. NP.
	Part 1: Expressive marketplaces.
1/29-2/12	Single-item auctions. Combinatorial auctions. Bidding languages. Winner determination problem. Variants (reverse auctions, exchanges).	Slides: ppt, pdf. Slides for Sasa Pekec's guest lecture. Note: we are not going in the same order as the book on these topics. The book does mechanism design before getting into auctions. I'm pointing out the chapters that are associated with each topic, but for reading purposes you may prefer following the order of the book for the next few lectures, reading mechanism design (Ch. 10) before auctions (Ch. 11), and single-item auctions and their analysis before combinatorial auctions. SLB 11.3.1-11.3.4, 11.4.1. Optional: 11.2, 11.3.5, Conitzer chapter on auctions, Lehmann et al. chapter on winner determination, Sandholm chapter on optimal winner determination.
2/14-2/16	Expressive financial securities.	Slides: ppt, pdf. SLB 10.4.2. Programming assignment 2 out. Partial solution to graph winner determination problem, for first problem. Recitation notes. Optional: Paper 1, paper 2. Article about Predictalot.
2/19-2/21	Barter exchanges/matching markets. Kidney exchange.	Slides: ppt, pdf. Paper (you do not need to understand all the details about constraint and column generation). Recitation notes.
2/26 - 3/4	Voting and social choice.	Homework 3 out. Slides: ppt, pdf. SLB Chapter 9 (9.5 is optional). Recitation notes. Optional (if you really like this): chapter on computational social choice. A website aiming to do liquid democracy (presented without endorsement; seems legitimate as far as I can tell but I don't know the people involved, use your own judgment if you consider signing up).
3/6	Moral AI: kidney exchanges and social choice.	Slides: pptx, pdf. Optional: paper on kidney exchange, paper on social choice in these settings.
3/23 (bonus lecture)	Checking in with everyone. Time for questions about the course. A bonus topic, also to practice with zoom (Sleeping Beauty and imperfect recall).	Slides: ppt, pdf. Recitation notes.
3/25	Midterm review.	Practice midterm. More practice questions: ppt, pdf.
around 3/27	Midterm.
	Part 2: Game theory. (We will cut a few parts of this part of the course; topics likely to be skipped are indicated by parentheses.)
4/1	Risk neutrality and risk aversion. Expected utility theory.	Slides: ppt, pdf. SLB Section 3.1.
4/1 - 4/10	Games in normal form. Dominance and iterated dominance. Computing dominated strategies. Minimax strategies. Computing minimax strategies. Nash equilibrium. Computing Nash equilibria.	Homework 4 out. Slides: ppt, pdf. SLB 3.2, 3.4.3, 4.5; 3.3.1-3.3.3, 3.4.1, 4.1, 4.2.1, 4.2.3, 4.2.4, 4.4. Recitation notes. Optional (including the papers): 3.3.4, 4.2.2; 3.4.5, 4.6. Paper on computing dominated strategies. (You can skip the part on Bayesian games.) Paper on computing Nash equilibria. (You only need to read the part concerning 2-player games.) Paper on computing special kinds of Nash equilibria. (You can skip everything from Bayesian games on.)
4/10-4/15	Games in extensive form. Backwards induction. Subgame perfect equilibrium. Imperfect information. Equilibrium refinements. Computing equilibria. Poker.	Slides: ppt, pdf. SLB 5.1 (alpha-beta is optional), 5.2.1, 5.2.2. Recitation notes. Optional (including the paper): 5.2.3. Paper on finding optimal strategies to commit to.
	Part 3: Mechanism design. (We will cut fairly significantly from this part of the course; topics likely to be skipped are indicated by parentheses.)
4/15-4/17	Bayesian games. Auctions revisited.	Slides: ppt, pdf. SLB 6.3, 11.1.1-11.1.8. Optional: 11.1.9, 11.1.10.
4/17-4/20	Incentive compatibility. Individual rationality. Revelation principle. Clarke mechanism. Groves mechanisms.	Slides: ppt, pdf. SLB 10.1-10.4. Optional: rest of chapter 10. Article on the Swoopo auction.
SKIPPED	Automated mechanism design.	Slides: ppt, pdf. Optional: Chapter on automated mechanism design, read up to and including 6.6.
4/22	Final review.	Practice final.
from 4/22 to around the originally scheduled time for the final, which was Tuesday, April 28, 9am - noon.	Final.