CSCI 357

CSCI 357 - Spring 2022

Algorithmic Game Theory

Final Project

Overview. In the final project, you must analyze the role of incentives and strategic behavior in a particular system or class of algorithms. The domain you choose can be similar to ones we studied in class, for example:

Markets with money: Auctions, Decentralized matching markets, etc
Markets without money: school choice, kidney exchange, two-sided matching, voting, fair division, etc.
Game theory: Problems that can modeled as a normal or extensive-form game.

Learning Goals There are several learning goals of the final project:

To dig deeper in one of the areas of algorithmic game theory.
To read and understand recent research papers in the field.
To apply the framework and concepts developed in class to a new regime.

Choosing a Topic. As you choosing a project topic, keep the following in mind:

Pick a topic you will enjoy working on (something fun!)
Pick a topic that you will learn a lot from (something useful!)
Pick a topic that is relevant to the course (something relevant!)
Pick a topic with the scope in mind (~3 weeks)
Pick a topic that is technical interesting: relevant research is published in CS/Econ conferences.

Theory vs Implementation. Your project may be purely implementation or purely theoretical (or anywhere in between). If you are choosing an implementation project, keep in mind:

Scope and effort should match the timeline (3x a regular assignment)
Even when implementing an algorithm, it is important to understand the theoretical foundations behind the work and put the implementation in context with the theory in your write up.

If you choose to work on a purely theoretical topic, keep in mind that you are expected to go above and beyond summarizing existing results. You do not need to solve an open problem to do this, your contribution can take many forms:

Really understanding the literature in a way that you can recreate the results
Filling in details and providing context and examples that the papers may have overlooked
Finding something new to say about the existence work
Identifying interesting directions to take the literature forward (even if there is not enough time to pursue them)

It is important to note that purely theoretical projects can often be more challenging and open-ended, with a final product that may feel less tangible. As a result, most projects in the past were somewhere in the middle: understanding the theory behind a market or algorithms and evaluating its properties through a series of simulations.

Project Timeline and Rubric. See assignment page for deadlines. See Grading Rubric.

Topics and Research Papers

The following document provides examples of projects you may pursue. The first idea (Incentives in BitTorrent) is more structured and intended to serve a default option that you may pursue or use as an example for your own custom project.

Strategic Behavior in BitTorrent:

Incentives in School Choice:

Incentives in Two-Sided Matching Markets:

Incentives in Voting & Social Choice:

Incentives in Sponsored-Search Auctions:

Miscellaneous Topics:

If you have a project idea is different from the above topics, drop me a note and I can help you find relevant research papers.