CSCI 1440/2440, Spring 2024 Final Project
CSCI 1440/2440 Final Project 1 Introduction
This course has focused on both the theory and practice of algorithmic game theory, particularly with regard to auctions. To that end, the final project has both a theoretical and practical component, as described below. Your job is to pick a game (either Spectrum Auctions or Ad Exchange), and then complete these theoretical, practical, and unifying tasks for your game. You should compile your theoretical results in a writeup (of length 3–5 pages), and your practical results in a fully operational agent. Before submitting your code, you test it against other agents to see how well yours fares.
2 Tasks
This project comprises both theoretical and practical tasks.
2.1 Theoretical
Construct a model of a simplified version of both the game and the behavior of other agents. Compute, and describe intuitively, an optimal strategy in your simplified version of the game. We leave the particular details of the simplification up to you, but ideally they would be simple enough that you can derive optimal behavior, but complicated enough that your model bears enough of a relationship to the original game so that your ideas will be meaningful when implemented in your agent.
Note: If you try out a model and it turns out not to be useful, feel free to include that in your writeup! We are interested to see (at least some of) your process, not just your conclusions.
Note also: You might want to complete this theory part of the project without regard for tractability. It is quite likely that any (relevant) optimal behavior you derive will be intractable. You should address this concern when designing and implementing your agent.
2.2 Practical
Construct an autonomous agent to participate in the game, using your theory to shape its design. Describe your agent’s strategy by answering the following questions: What assumptions did you make in constructing your game model that are violated by the actual game? Is there a way to relax them so that you can more accurately reason about the game? And likewise, for your assumptions about the other agents’ behaviors. For this part of the project, you are not required to solve for (even approximately) optimal behavior.1
Describe how your theoretical model combined with your answers to the practical questions led you to your agent’s design. For everything that your agent does, you should tell us whether doing so was a direct result of the optimal strategy you derived in your simplified game, or why you were forced to diverge from that strategy, and how any heuristics you implemented are intended to compensate for its deficiencies.
In addition to arguing about the correctness of your agent’s strategy, be sure to also include in your write up complexity analyses (either theoretical or empirical) of any heuristics you implement.
1If you manage to do so, then you should iterate on your solution to the project. That is, your response to this part should become part of your theory story, and you should have another go at this question!
CSCI 1440/2440, Spring 2024 Final Project
2.3 Oral Presentation
You should prepare an 8 minute oral presentation of your final agent design, with supporting slides, to be presented to the class. In this presentation, you should describe your model, and any theoretical analyses of your model you were able to complete, however simple. You should also explain your agent design, and how you came to this design based on your model. Your presentations should be engaging; they will be scored by your peers as well as by the course staff. (We will provide a Google Form for submitting peer feedback as you watch the presentations.) You should also be prepared to answer any questions that arise.
3 Capstone & Grad Course
If you are taking this course as a capstone, you must do this assignment twice; that is, you must complete both final project options. You can partner with two different people for your two projects.
There is no difference in the final project requirements for CSCI 1440 students and CSCI 2440 students. Moreover, students enrolled in the two courses are welcome to partner with one another.
4 Deadlines
This project has several intermediate deadlines.
1. Choose partner + project: Tuesday, April 9, 11:59 pm EDT
By this deadline, you must choose which of the two projects you will complete, and finalize your partnership. You may work in groups of size 1 or 2. Please fill out this link by the deadline. Please fill out only one form per group. If you are doing both projects, please fill it out twice, but again, only one form per group.
2. Friendly competition begins: Tuesday, April 16, 11:59 pm EDT
You are invited to submit a working (though not necessarily particularly intelligent) version of your agent at this time. Participation in the friendly competition during this preliminary week is strictly voluntary, but highly recommended.
3. First friendly competition deadline: Tuesday, April 23, 11:59 pm EDT
You must submit a working version of your agent by this deadline. At this time, the TAs will begin running your agents in a continuous class-wide competition.2 You will have the entire duration of the project to improve your agent. You can view this submission as a “rough draft.”
4. Second friendly competition deadline: Tuesday, April 30, 11:59 pm EDT
You should aim to submit a near-finished version of your agent to the class-wide competition by this deadline. Agents that finish at the top of these competitions will receive extra credit.
5. Writeup and final agent due: Tuesday, May 7, 11:59 pm
The writeup is due on Gradescope at this time, while your agent must be submitted via the handin script. We will not accept submissions after this deadline.
6. Oral Presentations: Wednesday, May 8, 9:00 am EDT
Oral presentations are scheduled during our class’ final exam slot. They will be held in the SWIG Boardroom (CIT 241). With luck, coffee and bagels or donuts will be served. Attendance is mandatory.
All deadlines listed are in Providence time (EDT).
2If there are enough earlier submissions, we may start the competitions earlier, just for fun, but this deadline won’t change.
CSCI 1440/2440, Spring 2024 Final Project
5 Mentor TAs
Each group will be assigned a mentor TA, who you will meet with periodically to assess your progress. You should discuss your current theoretical model and agent design, and brainstorm about ways to improve both.
The first check-in with mentor TAs must happen before the first friendly competition deadline, and the second, before the second friendly competition deadline. After that, you should arrange to meet your mentor TA based on everyone’s availability.
6 Grading
• Writeup (50%)
– 25% Model and analysis of simplified game
– 25% A description of any principles / theory, etc. that guided your agent design
• Agent (25%)
– 5% Submit a beta version of your agent for the first friendly competition
∗ Winners of the second friendly competition will receive extra credit – 20% Performance of your final agent against the TAs’ agents
∗ 10% Released Tier 1 Agent
∗ 10% Unreleased Tier 2 Agent • Presentation (25%)
– 15% Oral Presentation
– 10% Attendance & Participation
