Pranav Nuti

We study stochastic dynamic matching with abandonment, a fundamental model in which agents of different types arrive over time, may abandon the market while waiting, and can be matched in pairs for rewards that depend on their types. No online policy can guarantee more than 0.5 of the omniscient benchmark, which knows all arrival and departure times. Whether this guarantee is achievable has been a central open problem, even in special cases. We resolve this problem by showing that, on every instance, a simple static priority policy, which is computable in polynomial time, earns at least 0.5 of the omniscient benchmark. This establishes that the optimal competitive ratio is exactly 0.5, improving the previous best guarantee of 0.192 for the general model (Li et al. 2026, Collina et al. 2020). Our analysis rests on a key stochastic result, which is a new lower bound on the probability that some agent from a given set of types is available. Building on this bound, we develop two approaches: a primal approach that reads the priorities from an optimal solution of a novel linear program, and a dual approach that assigns a "value" to each type, and prioritizes matches with high "surplus" (reward minus value of involved agents). These values are the unique solution of a fixed-point equation derived from linear programming duality. We also show that the two approaches are closely connected.

Online contention resolution schemes (OCRSs) are a central tool in Bayesian online selection and resource allocation: they convert fractional ex-ante relaxations into feasible online policies while preserving each marginal probability up to a constant factor. Despite their importance, designing (near) optimal OCRSs is often technically challenging, and many existing constructions rely on indirect reductions to prophet inequalities and LP duality, resulting in algorithms that are difficult to interpret or implement. In this paper, we introduce ``stationary online contention resolution schemes (S-OCRSs),'' a permutation-invariant class of OCRSs in which the distribution of the selected feasible set is independent of arrival order. We show that S-OCRSs admit an exact distributional characterization together with a universal online implementation. We then develop a general `maximum-entropy' approach to construct and analyze S-OCRSs, reducing the design of online policies to constructing suitable distributions over feasible sets. This yields a new technical framework for designing simple and possibly improved OCRSs. We demonstrate the power of this framework across several canonical feasibility environments. In particular, we obtain an improved (3-\sqrt{5})/2-selectable OCRS for bipartite matchings, attaining the independence benchmark conjectured to be optimal and yielding the best known prophet inequality for this setting. We also obtain a (1-\sqrt{2/(\pi k)} + O(1/k))-selectable OCRS for k-uniform matroids and a simple, explicit 1/2-selectable OCRS for weakly Rayleigh matroids (including all C-representable matroids such as graphic and laminar). These guarantees match the best known bounds, and our framework yields concrete and systematic constructions, providing transparent algorithms in settings where previous OCRSs were implicit or technically involved. We leave the investigation of other feasibility environments to future work.

Many modern online platforms allocate "reusable" capacity, where a resource unit is occupied for some duration and then becomes available again. Examples include cloud and edge computing platforms allocating compute or GPU memory to jobs, rental marketplaces, and service systems in which capacity cycles between busy and idle states. Motivated by these applications, we study a Bayesian online resource allocation problem with reusable resources. There are k units of each resource, and demand requests of heterogeneous types (i.e., rewards and usage durations) arrive according to non-stationary Poisson processes. Upon arrival, each request must be irrevocably assigned at most one unit of a resource. The goal is to maximize the total expected reward. Our main result is a simple online algorithm that obtains a 1-\sqrt{2/\pi k} + O(1/k) fraction of the reward obtained by the optimal omniscient algorithm. Our results advance the existing literature by directly generalizing the non-reusable setting of Wang et al. (2018) to the reusable setting, matching the best known bound in the non-reusable case, and hence solving an open problem by improving upon the best previously known guarantee of 1-O(\sqrt{\log k/k}) for reusable resources due to Feng, Niazadeh, and Saberi (2024). Our results are obtained through a now-standard propose--then--admit framework. We upper bound the performance of the optimal omniscient algorithm by a fluid LP approximation, and then round the optimal fluid solution. Each request first proposes to a resource type according to the LP assignment probabilities, and then each resource runs an online admission-control policy to enforce ex-post capacity feasibility. Our main contribution is a simple and novel state-dependent admission-control policy for reusable resources that yields a constant per-proposal admission probability of Pr[Poisson(k)<= k-1 | Poisson(k) <= k] independent of time, rewards, or durations, which immediately leads to our main result. Our policy equalizes conditional admission probabilities (conditional on a request being made) among all potential requests. To this end, it synthetically increases the load at each time (so that the total load is exactly equal to the capacity) by adding "imaginary" requests when necessary, and then greedily accepting real and imaginary requests.

We study the performance of sequential contention resolution and matching algorithms on random graphs with vanishing edge probabilities. When the edges of the graph are processed in an adversarially-chosen order, we derive a new OCRS that is 0.382-selectable, attaining the "independence benchmark" from the literature under the vanishing edge probabilities assumption. Complementary to this positive result, we show that no OCRS can be more than 0.390-selectable, significantly improving upon the upper bound of 0.428 from the literature. We also derive negative results that are specialized to bipartite graphs or subfamilies of OCRS's. Meanwhile, when the edges of the graph are processed in a uniformly random order, we show that the simple greedy contention resolution scheme which accepts all active and feasible edges is 1/2-selectable. This result is tight due to a known upper bound. Finally, when the algorithm can choose the processing order, we show that a slight tweak to the random order---give each vertex a random priority and process edges in lexicographic order---results in a strictly better contention resolution scheme that is 1 - ln(2 - 1/e) ≈ 0.510-selectable. Our positive results also apply to online matching on 1-uniform random graphs with vanishing (non-identical) edge probabilities, extending and unifying some results from the random graphs literature. A full version of this paper can be found at https://arxiv.org/abs/2406.14506.

Most of the literature on online algorithms and sequential decision-making focuses on settings with “irrevocable decisions” where the algorithm’s decision upon arrival of the new input is set in stone and can never change in the future. One canonical example is the classic prophet inequality problem, where realizations of a sequence of independent random variables X₁, X₂,… with known distributions are drawn one by one and a decision maker decides when to stop and accept the arriving random variable, with the goal of maximizing the expected value of their pick. We consider “prophet inequalities with recourse” in the linear buyback cost setting, where after accepting a variable X_i, we can still discard X_i later and accept another variable X_j, at a buyback cost of f × X_i. The goal is to maximize the expected net reward, which is the value of the final accepted variable minus the total buyback cost. Our first main result is an optimal prophet inequality in the regime of f ≥ 1, where we prove that we can achieve an expected reward 1+f/1+2f times the expected offline optimum. The problem is still open for 0<ff and provide almost matching upper and lower bounds that show a factor of 1−Θ(flog(1/f)). Our results are obtained by two fundamentally different approaches: One is inspired by various proofs of the classical prophet inequality, while the second is based on combinatorial optimization techniques involving LP duality, flows, and cuts.

This paper discusses several linear algebra activities designed to help enhance students' skills in collaborating, exploring mathematics, and linking together abstract and visual ways of approaching mathematics. Most of these activities are short, accessible, engaging, and easy to incorporate into any classroom. In addition, we discuss some questions instructors can ask themselves to design novel and engaging activities when constrained to teaching from a particular curriculum.

We study a variant of the secretary problem where candidates come from independent, not necessarily identical distributions known to us, and show that we can do at least as well as in the IID setting. This resolves a conjecture of Esfandiari et al.