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.

**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

- 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

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 |

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 |

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!)

The
information marked in red is subject to change, the course
staff reserves the right to modify it necessary.

SD5 is
posted: SD5. Submit your writeup to
codePost. Submit your
code to
TigerFile here. If
you wish to try out the leaderboard, you can submit code
here
and view
results here.

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 |

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)

All the
information below is subject to change, the course
staff reserves the right to modify it necessary.

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 |