COS 445: Economics and Computation
Spring 2024
Resources
In this course we will study a variety of topics on the cusp between economics and computation. Topics to be covered include: game theory, auctions, mechanism design and cryptocurrencies.
The aim of the course is two-fold: (1) to understand the game-theoretic issues behind systems involving computation such as online networks, and (2) to learn how algorithms and algorithmic thinking can help with designing better decision and allocation mechanisms in the offline world.
Staff
Instructors: Matt Weinberg (smweinberg@), Marcel Dall'Agnol (dallagnol@)
Graduate TAs: Eric Xue (ex3782@), Jingyi Liu (jingyi.liu@), Qianfan Zhang (qianfan@), Stephen Newman (stephen.newman@), Pachara (Akin) Sawettamalya (pachara@), Chenghan Zhou (chenghanzh@), Cindy Zhang (cindyz@)
Undergraduate Course Staff: Amir Touil, Ananya Parashar, Anika Agarwal, Arsh Banerjee, Arjun Jagjivan, Amanda Wang, Andrew Tao, Dimitar Chakarov, Chenhan Zhang, Clara Toujas-Bernate, Crystal Pan, Diya Dalia, Dwaipayan (Dwip) Saha, Donna Wang, Erin Lee, Emmy Song, Foyez Alauddin, Garner Thompson, Hervé Ishimwe, Ijay Narang, Louis Viglietta, Mahmudul Rapi, Mary Tsahas, Noam Borgnia, Nicole Klausner, Richard Li, Saumya Malik, Sung Cho, Victoria Graf, Vicky Feng, Yash Parikh, Yenet Tafesse
Course Links
- What to expect from this course: FAQ
- Prerequisite skills/math: cheatsheet on background skills/math required for this course
- Discussion and announcements: Ed
- Assignment submissions: codePost
- Course policies
Schedule
| Lecture | Tuesday/Thursday | 1:30pm-2:50pm | Friend 101 | Matt/Marcel |
|---|---|---|---|---|
| Precept P01 | Wednesday | 1:30pm-2:20pm | Friend 008 | Eric |
| Precept P02 | Wednesday | 1:30pm-2:20pm | Friend 009 | Cindy |
| Precept P03 | Wednesday | 3:30pm-4:20pm | Friend 008 | Jingyi |
| Precept P04 | Wednesday | 3:30pm-4:20pm | McCosh 64 | Qianfan |
| Precept P05 | Wednesday | 7:30pm-8:20pm | Friend 008 | Stephen |
| Precept P06 | Friday | 1:30pm-2:20pm | Friend 009 | Marcel |
| Precept P07 | Friday | 1:30pm-2:20pm | Friend 109 | Chenghan |
Office Hours
| Monday | 11am-12pm | CS 302* | Cindy & Chenghan |
| Monday | 3-4pm | CS 401 & 402* | Stephen & Jingyi |
| Monday | 4-5pm | CS 401 & 402* | Akin & Jingyi |
| Tuesday | 9-10am | CS 302* | Dwip (No PSet) |
| Tuesday | 10-11am | CS 302* | Chenghan |
| Tuesday | 3-4pm | CS 201* | Matt |
| Wednesday | 10-11am | Corwin 034 | Marcel |
| Wednesday | 2:30-3:30pm | CS 201 | Cindy |
| Wednesday | 4:30-5:30pm | CS 302 | Qianfan (No PSet) |
| Wednesday | 6:30-7:30pm | CS 201 | Stephen & Victoria |
| Thursday | 10-11am | CS 302 | Eric |
| Thursday | 3-4pm | CS 201 | Marcel |
| Friday | 2:30-3:30pm | CS 402 | Andrew (No PSet) |
| Friday | 3:30-4:30pm | CS 402 | Qianfan |
| Friday | 4:30-5:30pm | CS 402 | Eric |
| Sunday | 4pm-6pm | CS 302* | Akin |
Homework and Exams
Your homework must be submitted as a PDF file. You can use LaTeX or another math-document-editor to produce your homework PDF. If you have never used LaTeX, here is a short guide. You might also want to use Overleaf, which is an online LaTeX editor and compiler. Feel free to visit office hours for help installing/setting up LaTeX.
Here is a LaTeX template you may use for the homework, and a template for the collaboration statement here (thanks to Jude Muriithi'24 for this template!)
| Due Date | Assignment |
|---|---|
| 02/05 | Warmup PSet |
| 02/12 | PSet 1 |
| 02/19 | SD 1 | Leaderboard |
| 02/26 | PSet 2 |
| 03/01 | SD 2 | Leaderboard |
| 03/11* | Midterm |
| 03/25 | PSet 3 |
| 04/01 | SD 3 | Leaderboard |
| 04/08 | PSet 4 |
| 04/15 | SD 4 | Leaderboard |
| 04/22 | PSet 5 |
| 04/29 | SD 5 | Files | Leaderboard |
| 05/15 | Final |
Lectures
Some shorthand for the reading material:
- Rx = Tim Roughgarden's lecture notes x
- KPx = Karlin and Peres chapter x
- EKx = Easley and Kleinberg chapter x
- NRTVx = Nisan, Roughgarden, Tardos and Vazirani chapter x (Click link --> resources --> Algorithmic Game Theory --> Algorithmic Game Theory)
- BCELPx = Brandt, Conitzer, Endriss, Lang, Procaccia chapter x (Click link --> resources --> resources --> online version. To find the password, visit Vince Conitzer's webpage)
| Date | Topic | Supplemental Reading Material |
|---|---|---|
| 01/30 | Braess' Paradox, Stable Matching I | R1, R2, KP10.1, KP10.2, NRTV10.4, Wikipedia |
| 02/01 | Stable Matching II | R1, R2, KP10.3, NRTV10.4 |
| 02/06 | Matching III | KP10.4, NRTV10.3 |
| 02/08 | Matching IV | This paper |
| 02/13 | Voting Theory I | KP13, BCELP2 |
| 02/15 | Voting Theory II | R4, BCELP2, EK23.6, NRTV10.2 |
| 02/20 | Game Theory I | KP4, R5, EK6 |
| 02/22 | Game Theory II | KP4, KP6, R5 |
| 02/27 | Linear Programming | Sections 1 & 4 here |
| 02/29 | Game Theory III | KP2 |
| 03/05 | Information Cascades | EK16 |
| 03/07 | No Lecture | |
| 03/12 | Spring Break | |
| 03/14 | Spring Break | |
| 03/19 | Auction Theory I | R13, EK9.1-9.5 |
| 03/21 | Auction Theory II | R14, R15, KP 15.1-15.3 |
| 03/26 | Auction Theory III | R14, R16, EK9.7 |
| 03/28 | Auction Theory IV | KP14.4, KP14.6 |
| 04/02 | Cryptocurrencies I | Chapter 1 |
| 04/04 | Cryptocurrencies II | "Selfish Mining" attack, notes on Ed |
| 04/09 | Scoring Rules | R17 |
| 04/11 | Cake Cutting | BCELP13, KP11 | 04/16 | Price of Anarchy I | R7, NRTV18.1-18.3, KP8.1, KP8.4 |
| 04/18 | Price of Anarchy II | R7, NRTV18.1-18.3, KP8.1, KP8.4 |
| 04/23 | Behavioral Game Theory I | Notes on Ed, R19 |
| 04/25 | Behavioral Game Theory II | R19 |