Project Description:  

Think about the last time you had to make a real decision without knowing what was coming next — accepting an internship offer before hearing back from other places, saying yes to weekend plans before knowing what else might come up. Many important decisions share this same frustrating shape: you don't get to see all your options and then pick the best one. Instead, options arrive one at a time, you must accept or reject each immediately, and once you say no, it's gone for good — usually while working under some kind of fixed budget or limited capacity.

This project studies Online Contention Resolution Schemes (OCRS) — algorithms built for exactly this situation, which guarantee results close to what you'd get if you could see every option in advance. The team will first build a solid understanding of how these algorithms work and why their guarantees hold, using examples like the ones above to build intuition. This groundwork will involve working through the key ideas together, implementing simple versions of these algorithms, and testing them on simulated data to see the guarantees play out firsthand. Then, the real project begins: identify a new, real-world scenario — one that hasn't been studied through this lens before — that shares this same "decide now, limited budget, no take-backs" structure, and study how OCRS-style algorithms perform there, both by analyzing them and by testing them with simulations.

Learning Objectives:  

By the end of the project, students should be able to:

Explain the core framework of online decision-making under uncertainty, including what makes these problems fundamentally different from offline optimization.

Formalize a new, previously-unstudied real-world scenario as a well-posed algorithmic problem within this framework.

Implement OCRS-style algorithms and baseline heuristics, design experiments to compare their empirical performance, and provide theoretical guarantees for the algorithms developed for the new application.

Communicate technical findings clearly, both in writing and through a final presentation/poster.

Skills needed:  

Ability to read and work through mathematical arguments at a basic level — comfort with proofs, logical reasoning, and abstract problem-solving, since a core part of this project involves understanding and eventually contributing to theoretical guarantees.

Comfort with basic probability and discrete mathematics — ideas like expected value, independence, reasoning about randomness, and basic combinatorics.

Basic programming (Python preferred), for implementing algorithms and running simulations.

Comfort with open-ended, exploratory problem-solving, since part of the project involves identifying a new research direction rather than following a fixed roadmap.

Students are encouraged to use AI tools to help build intuition and understand background material, but the core research contribution — identifying and analyzing a new application — should be their own thinking.