COMPSCI 590.7, Fall 2020
Computational Microeconomics: Game Theory, Social Choice, and Mechanism Design




Details
TuTh, 10:15-11:30am. Location: online.

Instructor: Vincent Conitzer. (Please call me Vince.)

Graduate teaching assistants: Caspar Oesterheld, Hanrui Zhang.
Graduate teaching assistant (organizational): Qingying Luo.
Undergraduate teaching assistants: Robert Lordi, Griffin Malm, Yikai Wu.
The use of Piazza for questions (or insights or other comments) is highly encouraged.
Office hours (in regular zoom meeting room):
Caspar: Tu 5pm; Griffin: M 3:30pm; Hanrui: W 10am; Qingying: by appointment for nontechnical concerns; Robert: Th 5pm; Vince: Tu and Th immediately after class and by appointment if needed; Yikai: Tu 9pm

Optional additional resources:
We may occasionally have cs-econ seminars that are interesting from the perspective of this course; traditionally these are at noon on Fridays (but not every Friday). You can sign up for the mailing list here, where I will also advertise other events. Attending these is completely optional but may help you find a project!

Description
Computer scientists are increasingly confronted with settings where multiple self-interested parties interact. Two prominent examples are electronic marketplaces and networked computer systems.

To act optimally in such settings, each party (or "agent") must take into account how the other agents are likely to act. Game theory studies how this should be done, and it provides various solution concepts which prescribe how agents should act when the actions of other agents affect their utilities. For example, agents are said to play in Nash equilibrium if no single agent can benefit by deviating. In this course, we will review these concepts and study algorithms to compute the solutions. This will allow us to write software that performs well in multiagent settings (as well as to create good computer players for game-theoretically nontrivial games, such as poker).

Playing the game is only half the story. As computer scientists, we often get to design the game (the rules of the electronic marketplace, the system protocols, etc.). While we cannot directly control the behavior of (self-interested) users, we can give them incentives to behave in a desirable way. Mechanism design studies how to design the game (or "mechanism") so that self-interested behavior will lead to good outcomes. In this course, we will review basic results in social choice and mechanism design, including standard mechanisms as well as impossibility results. We will also study computational aspects of social choice and mechanism design, including efficiently eliciting information from the agents, computing the outcomes of mechanisms in various settings, and even optimizing the mechanism itself.

Throughout the course, we will consider applications such as (combinatorial) auctions, exchanges, and voting.

Recommended for:
1. Anyone in computer science who is interested. The amount of research on these topics in both the AI and theory communities has surged in recent years. There is also increasing interest in the systems community.

2. The course will also be open to interested students outside of computer science, for example students in economics or mathematics. Such students should talk to Vince before the start of the course to discuss background issues and what they hope to get out of the course.

Prerequisites
Basic knowledge of probability, algorithms, and (very basic) computational complexity. Undergraduates are welcome provided they have the required background. Interested students without computer science backgrounds (e.g., students in economics or mathematics) should talk to Vince first. I plan to teach a bonus ridiculously short intro to algorithms and complexity lecture. Strong math background helpful.

Grading
Participation: 10%
Assignments: 20%
Midterm (Oct. 22-29): 20%
Project: 50%

Rules for assignments (not the midterm): You must show all your work, even if this is not specifically indicated. You may discuss assignments with at most one other person. Each person must do her or his own writeup, and at that point derive the solution on her/his own. You may present things to each other on a (virtual) whiteboard, but you may not copy anything from the whiteboard, or take screenshots, or take notes during the meeting, or anything like that. The only thing you should take from the meeting is what you remember from it. 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. You should always acknowledge your homework partner (if any), as well as all other sources, on the writeup.

Rules for midterm: You must show all your work, even if this is not specifically indicated. The midterm will be a takehome midterm. You may use all the materials from the course website (slides, the book, also your homework, etc.). You may not work with any other person, or access the rest of the Internet. Do not communicate with anyone else about the midterm (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.

Struggling / cheating: Sometimes, students fall behind, for example due to personal difficulties. These days, there are many additional challenges. You should try hard to keep up, because it will be easiest to learn the material that way; but if you are struggling, please reach out to the teaching team as soon as possible. We will be very understanding about difficult situations. But, do not get tempted to break the rules. Attempting to take advantage of the generally difficult situation by cheating is wrong, and hurts other students. We will pursue any and all cheating cases to the full extent. You should be aware that we will pursue various ways to detect cheating, some of them noticeable and some of them not noticeable. You may find that something in an assignment or midterm occasionally looks a bit funny. You do not need to worry about this, and you also do not need to worry if you do not see anything like that -- as long as you are following the rules.

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.

Some additional books that you could use as references (very much optional):

Noam Nisan, Tim Roughgarden, Eva Tardos, Vijay V. Vazirani, Algorithmic Game Theory.

General microeconomic theory:
Andreu Mas-Colell, Michael D. Whinston, Jerry R. Green, Microeconomic Theory. (Especially Part 2: Game Theory, and Part 5: Welfare Economics and Incentives (which studies mechanism design).)

Game theory:
Martin J. Osborne and Ariel Rubinstein, A Course in Game Theory. ((used to be?) freely available online)
Drew Fudenberg and Jean Tirole, Game Theory.

Combinatorial auctions:
Peter Cramton, Yoav Shoham, Richard Steinberg, Combinatorial Auctions. (Some of the chapters of this book can be found online.)

Schedule
In the below, SLB refers to the Shoham/Leyton-Brown book. We will not cover all of this book, we will not always go in the same order as the book, and we will cover some things not in the book. The below tries to line up our lectures with the book, but of course you are welcome to read the book in its original order, read other parts of book, etc. If you would like advice on further reading on some topic, talk to Vince.

The course will be divided into roughly two halves. The first half is primarily a crash course in game theory, social choice, and mechanism design (where we will consider some computational aspects along the way). At the end of this first half we will have a midterm to make sure everyone understands the basics.

In the second half of the course, we will consider a few more basic topics for which we didn't have time in the first half, as well as more advanced topics. During this half of the course, you should also be working intensively on your project (if not sooner).

In the below, one topic will not necessarily take one lecture to finish.

Date Topic Materials
8/18, 8/20 Course at a glance. What problems are we trying to solve? Example applications: game playing, security, elections, electronic marketplaces, resource allocation, ... Slides: ppt, pdf.
Optional readings:
Some CACM articles: Computer Science and Game Theory, Making Decisions Based on the Preferences of Multiple Agents, Designing the Perfect Auction.
EC 2020 proceedings.
8/25, 8/27, 9/1 Linear, integer, and mixed integer programs. Slides: ppt, pdf.
SLB Appendices A and B (if you need them).
GNU Linear Programming Kit.
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.
Example files: painting.lp, painting.mod. knapsack.lp, knapsack_simple.mod, knapsack.mod. cell.lp, cell.mod, hotdog.mod.
9/3 ("Bonus" lecture.) Ridiculously brief introduction to theoretical computer science: computational problems, algorithms, runtime, complexity. Slides: ppt, pdf.
Modeling files: set_cover.mod, set_cover2.mod, matching.mod.
Sorting spreadsheet.
CACM article on P vs. NP.
9/8 Risk neutrality and risk aversion. Expected utility theory. Slides: ppt, pdf.
SLB Section 3.1.
9/8-9/24 Games in normal form. Dominance and iterated dominance. Computing dominated strategies. Minimax strategies. Computing minimax strategies. Nash equilibrium. Computing Nash equilibria. Correlated equilibrium. Computing correlated equilibria. Slides: ppt, pdf.
SLB 3.2, 3.4.3, 4.5; 3.3.1-3.3.3, 3.4.1, 3.4.5, 4.1, 4.2.1, 4.2.3, 4.2.4, 4.4, 4.6.
Optional: 3.3.4, 4.2.2.
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.)
9/24 - 9/29 Games in extensive form. Backward induction. Subgame perfect equilibrium. Imperfect information. Equilibrium refinements. Slides: ppt, pdf.
SLB 5.1 (alpha-beta is optional), 5.2.1, 5.2.2.
Optional: 5.2.3.
Paper on finding optimal strategies to commit to.
10/1 - 10/6 (Computational) social choice. Voting rules. Desirable properties of voting rules. Arrow's impossibility theorem. Muller-Satterthwaite impossibility theorem. Manipulation. Gibbard-Satterthwaite impossibility theorem. Single-peaked preferences. Slides: ppt, pdf.
SLB Chapter 9.1-9.4.
Optional: 9.5.
Chapter on computational social choice.
10/8-10/15 Auctions. English, Japanese, Dutch, first-price sealed-bid, second-price sealed-bid (Vickrey). Combinatorial auctions. Winner determination. Combinatorial reverse auctions and exchanges. Bidding languages. Slides: ppt, pdf.
Note: we won't go in the same order as the book in the next few lectures. I'm pointing out the chapters that are associated with each lecture, 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.
Lehmann et al. chapter on winner determination.
Sandholm chapter on optimal winner determination.
Analyzing auction mechanisms: Bayesian games, Bayes-Nash equilibrium, revenue equivalence, revenue-maximizing (Myerson) auctions, redistribution auctions. Slides: ppt, pdf.
SLB 6.3, 11.1.1-11.1.8.
Optional: 11.1.9, 11.1.10.
Article on swoopo.
10/15- Mechanism design. Incentive compatibility. Individual rationality. Revelation principle. Clarke mechanism. Generalized Vickrey Auction. Groves mechanisms. Myerson-Satterthwaite impossibility. Computational topics. Slides: ppt, pdf.
Chapter 10.1-10.4.
Optional: rest of chapter 10.
Alternative resources:
Chapter on mechanism design + chapter on revelation principle.
Parkes chapter on mechanism design.
10/22 Midterm review. Practice midterm.
Just in case we have some extra time during the review (or in case you're interested after): practice questions: ppt, pdf.
11/3 Special optional Election Day bonus lecture / hangout with Dan Reeves. Meanwhile please watch assigned video. Beeminder, PredictIt, article about Dan Reeves' and Bethany Soule's approach to their personal life.
Repeated games. Folk theorem. Stochastic games. Slides: ppt, pdf.
SLB 6.1, 6.2.
Optional:
Paper on computing a Nash equilibrium in repeated games.
Paper on stochastic games and learning.


Projects
As you can see from the grading, the project is an important part of this course. You may work on it alone or in a team (please check with Vince first if you want to have a team of six or more people). We will have some checkpoints (e.g., project proposal) during the course, but feel free to discuss possible project ideas with Vince earlier.

The goal of the project is to try to do something novel, rather than merely a survey of existing work. Projects may be theoretical, experimental (based on simulations), experimental (based on real-world data), a useful software artifact, or any combination thereof. Creativity is encouraged. The only real constraint is that it has something to do with the material of the course. Talk to Vince if you are not sure about whether something is an appropriate project.

The final product is a writeup (in the form of a short 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 your project proposal (due on Oct. 20), you 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. Something related to your own research is definitely OK as long as it also has something to do with the course material. An intermediate project progress report may also be 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.

Because everything is online and not everyone is in the same time zone, we will do some creative new things for project presentations. Specifically, we will allow you to constructively comment on each other's presentations; this will contribute towards the participation component of the course.