CSCI 357

CSCI 357 - Spring 2025

Algorithmic Game Theory

Final Project

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

Markets with money: Auctions, matching markets with money, resource allocation etc.
Markets without money: school choice, kidney exchange, one or two-sided matching, voting, fair division, incentives in tournaments, etc.
Decentralized systems: Incentives in P2P systems, network routing etc.
Game theory: Any problem that can modeled as game and can be analyzed using equilibrium concepts.

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

Sample Projects and Timeline See timeline and rubric for the checkpoints and grading rubric. See Project Ideas and Sample Student Projects.

Related Research Papers

Before you settle on an exact project topic, it is a good idea to first explore one or two research papers in the topic(s) of your interest to build background knowledge. Below is a curated list of accessible research papers that are related to the topics covered in the course that can helpful to find a project topic.

Sponsored Search Auctions:

Stable Matchings:

Incentives in Voting:

Strategic Behavior in BitTorrent:

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.