COS 445: Economics and Computation
Spring 2023
Resources
In this course we will study a variety of topics on the cusp between economics and computation. Topics to be covered include: games on networks, auctions, mechanism and market design, reputation, computational social choice.
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@), Pedro Paredes (pparedes@)
Graduate TAs: Sacheth Sathyanarayanan (sacheths@), Chenghan Zhou (chenghanzh@), Nikhil Pimpalkhare (nikhil.pimpalkhare@), Yuanhao Wang (yuanhao@), Alex Guerra (ag5008@), Anjian Li (anjianl@)
Undergraduate Course Staff: Adam Rebei, Aditya Mehta, Alex Zhang, Ameya Vaidya, Amir Touil, Ananya Grover, Andrew Chen, Austen Mazenko, Autumn Tan, Ben Zenker, Camila Vasquez, Crystal Pan, Dimitar Chakarov, Dwaipayan Saha, Emre Parmaksiz, Frederick Qiu, Garner Thompson, Grant Lu, Ijay Narang, Ioana Marinescu, Isabella Pu, Janum Shah, Jeremy Chen, Julio Lins, Nadia Rodriguez, Nika Belova, Quan Shi, Richard Huang, Riya Gandhi, Saumya Malik, Ty Kay, Victoria Graf
Course Links
- What to expect from this course: "FAQ"
- Prerequisite skills/math: "cheatsheet" on prereq skills/math required for this course New: ChatGPT example usage
- Discussion and announcements: Ed (if you are not in Ed email Matt or Pedro to be added)
- Assignment submissions: codePost (see Ed for enroll link)
- Course policies New ChatGPT rules
Schedule
| Lecture | Tuesday/Thursday | 1:30pm-2:50pm | Friend 101 | Matt/Pedro |
|---|---|---|---|---|
| Precept P01 | Wednesday | 7:30pm-8:20pm | Friend 008 | Pedro |
| Precept P02 | Wednesday | 7:30pm-8:20pm | CS 104 | canceled |
| Precept P03 | Thursday | 7:30pm-8:20pm | Friend 108 | Alex / Anjian |
| Precept P04 | Thursday | 7:30pm-8:20pm | Friend 109 | canceled |
| Precept P05 | Friday | 1:30pm-2:20pm | Friend 109 | Sacheth |
| Precept P06 | Friday | 1:30pm-2:20pm | Friend 008 | Nikhil |
| Precept P07 | Wednesday | 7:30pm-8:20pm | Friend 004 | Chenghan / Yuanhao |
Office Hours
| Monday | 3-4pm | CS 402 | Nikhil |
| Monday | 3-4pm | CS 402 | Chenghan |
| Monday | 4-5pm | CS 402 | Alex |
| Monday | 4-5pm | CS 402 | Yuanhao |
| Monday | 5-6pm | CS 402 | Anjian |
| Monday | 5-6pm | CS 402 | Sacheth |
| Tuesday | 10-11am | CS 301 | Chenghan |
| Tuesday | 3-4pm | CS 317 | Matt |
| Wednesday | 3-5pm | Corwin Hall 041 | Pedro |
| Wednesday | 5-6pm | CS 301 | Anjian |
| Thursday | 3-4pm | CS 317 | Matt |
| Thursday | 6:30-7:30pm | CS 301 | Alex |
| Friday | 3-5pm | CS 201 (Tea Room) | Dwaipayan |
| Friday | 3-4pm | CS 201 (Tea Room) | Nikhil |
| Friday | 4-5pm | CS 201 (Tea Room) | Sacheth |
| Friday | 5-6pm | CS 201 (Tea Room) | Yuanhao |
Homework and Exams
Your homework must be submitted as a pdf. 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 to LaTeX. You might also want to use overleaf, which is an online LaTeX editor. 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/06 | Warmup Pset |
| 02/13 | Pset 1 |
| 02/20 | SD 1 | Files |
| 02/27 | Pset 2 |
| 03/03 | SD 2 | Files |
| 03/13* | Midterm |
| 03/27 | Pset 3 |
| 04/03 | SD 3 | Files |
| 04/10 | Pset 4 |
| 04/17 | SD 4 | Files |
| 04/24 | Pset 5 |
| 05/01 | SD 5 | Files |
| 05/17 | Final new |
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 |
|---|---|---|
| 1/31 | Braess' Paradox, Stable Matching I | R1, R2, KP10.1, KP10.2, NRTV10.4, Wikipedia |
| 2/02 | Stable Matching II | R1, R2, KP10.3, NRTV10.4 |
| 2/07 | Matching III | KP10.4, NRTV10.3 |
| 2/09 | Matching IV | This paper |
| 2/14 | Voting Theory I | KP13, BCELP2 |
| 2/16 | Voting Theory II | R4, BCELP2, EK23.6, NRTV10.2 |
| 2/21 | Game Theory I | KP4, R5, EK6 |
| 2/23 | Game Theory II | KP4, KP6, R5 |
| 2/28 | Linear Programming | Sections 1 & 4 here |
| 3/02 | Game Theory III | KP2 |
| 3/07 | Information Cascades | EK16 |
| 3/09 | No Lecture | |
| 3/14 | Spring Break | |
| 3/16 | Spring Break | |
| 3/21 | Auction Theory I | R13, EK9.1-9.5 |
| 3/23 | Auction Theory II | R14, R15, KP 15.1-15.3 |
| 3/28 | Auction Theory III | R14, R16, EK9.7 |
| 3/30 | Auction Theory IV | KP14.4, KP14.6 |
| 4/04 | Scoring Rules | R17 |
| 4/06 | Cake Cutting | BCELP13, KP11 |
| 4/11 | Price of Anarchy I | R7, NRTV18.1-18.3, KP8.1, KP8.4 |
| 4/13 | Price of Anarchy II | R7, NRTV18.1-18.3, KP8.1, KP8.4 |
| 4/18 | Cryptocurrencies I | Chapter 1 |
| 4/20 | Cryptocurrencies II | "Selfish Mining" attack, notes on Ed |
| 4/25 | Behavioral Game Theory I | Notes on Ed, R19 |
| 4/27 | Behavioral Game Theory II | R19 |