15326: Computational Microeconomics

15326: Computational Microeconomics, Fall 2024

Details
MW 11:00 - 12:20 WeH 5312. Instructor: Vincent Conitzer. (Please call me Vince.) OH immediately after class on W.
TA: Jiayuan Liu. OH every Thursday 4-5pm on the 5th floor of Gates Hillman Center.

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
(21127 or 21128 or 15151 or 80210 or 80211) and (21235 or 36218 or 36225 or 36235)

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 and written assignments: 30%
Midterms: 30%
Final: 30%

Rules for assignments: You may discuss homework assignments with at most one other person, and that other person must be a student currently taking the course, unless you have explicit approval otherwise. However, you may not simply copy down the other person's solution (or any part thereof). Instead, you could together work at a whiteboard, but then at the end erase the whiteboard and take home no notes, only your memory of the conversation. Each person should do their own writeup, at which point you should derive the solution yourself from scratch. This of course 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.

External tools, including but not limited to the use of generative AI, should generally be treated similarly to a person outside the course. If you happen to find it effective, you may use them, for example, to get more familiar with the MathProg language or topics in the course in general. But in the end, you need to do your assignments on your own, without any help from these tools. You may not pass specific information from the assignments to these tools. (This is of course also good practice for exam questions, as you will not have access to such tools on exams at all.) To the extent you use these tools, you are also responsible for ensuring that information from these external tools makes sense; "I got this question on the exam wrong because ChatGPT told me something false while studying" is not a valid excuse, just as "I got this question on the exam wrong because a person on the Internet told me something false while studying" is not a valid excuse.

If you have trouble with the assignments, just ask for help. When in doubt about whether something you did or are doing is allowed, you must reach out immediately. We are all still figuring out how new AI tools should be used in education, and are happy to discuss, but you may not simply assume on your own that a particular use is allowed. On your writeup, you must acknowledge your partner (if any) and all other sources and tools you used; if you worked on your own and used no other sources and tools, state this explicitly. (You do not need to declare basic text/code editors -- emacs, vim, ... -- without the use of generative AI.)

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
8/28, 8/30	Course at a glance.	Slides: ppt, pdf. Homework 0 out. Optional: CACM overview article. Just in case it's of interest: vision paper for our lab.
	Part 0: Basic techniques from computer science.
8/30-9/11	Linear programming. (Mixed) integer linear programming.	Slides: ppt, pdf. Example files: painting.lp, painting.mod, knapsack.lp, knapsack_simple.mod, knapsack.mod, cell.lp, cell.mod, hotdog.mod, sudoku.mod. SLB Appendices A, B. Programming assignment 1 out. 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.
9/11-9/18	Computational problems. Algorithms. Runtime of algorithms. Easy and hard problems.	Slides: ppt, pdf. Sorting algorithms spreadsheet. Example files: set_cover.mod, set_cover2.mod Optional: CACM article on P vs. NP.
	Part 1: Expressive marketplaces.
9/18-9/25	Single-item auctions. Combinatorial auctions. Bidding languages. Winner determination problem. Variants (reverse auctions, exchanges).	Slides: ppt, pdf. 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.
9/25, 9/30	Expressive financial securities.	Slides: ppt, pdf. SLB 10.4.2. Programming assignment 2 out. Partial solution to graph winner determination problem, for first problem. Practice midterm 1. Optional: Paper 1, paper 2, paper 3. Article about Predictalot.
10/9	Barter exchanges/matching markets. Kidney exchange.	Slides: ppt, pdf. Paper (you do not need to understand all the details about constraint and column generation).
10/20, 10/28	Voting and social choice.	Homework 3 out. Slides: ppt, pdf. SLB Chapter 9 (9.5 is optional). Optional (if you really like this): chapter on computational social choice. If you like it even more then there is also this textbook.
	Part 2: Game theory.
10/28	Risk neutrality and risk aversion. Expected utility theory.	Slides: ppt, pdf. SLB Section 3.1.
10/30-11/11	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. Practice midterm 2. 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.)
11/11-11/18	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. Optional (including the paper): 5.2.3. Paper on finding optimal strategies to commit to.
	Part 3: Mechanism design.
11/18-	Bayesian games. Auctions revisited.	Homework 5 out. Slides: ppt, pdf. SLB 6.3, 11.1.1-11.1.8. Optional: 11.1.9, 11.1.10.
12/2-	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.
"bonus topic"	Automated mechanism design.	Slides: ppt, pdf. Optional: Chapter on automated mechanism design, read up to and including 6.6.
"bonus topic"	Foundations of cooperative AI.	Slides: ppt, pdf. Optional: foundations of cooperative AI vision paper. More publications from FOCAL.
	(Practice final exams.)	Practice final 1. Solutions: 1, 2. Practice final 2. Solutions: 1, 2, 3.