Pranav Nuti

Amit Ganz, Pranav Nuti, Roy Schwartz

In this paper we consider the online Submodular Welfare (SW) problem. In this problem we are given $n$ bidders each equipped with a general (not necessarily monotone) submodular utility and $m$ items that arrive online. The goal is to assign each item, once it arrives, to a bidder or discard it, while maximizing the sum of utilities. When an adversary determines the items' arrival order we present a simple randomized algorithm that achieves a tight competitive ratio of $\nicefrac{1}{4}$. The algorithm is a specialization of an algorithm due to [Harshaw-Kazemi-Feldman-Karbasi MOR`22], who presented the previously best known competitive ratio of $3-2\sqrt{2}\approx 0.171573 $ to the problem. When the items' arrival order is uniformly random, we present a competitive ratio of $\approx 0.27493$, improving the previously known $\nicefrac{1}{4}$ guarantee. Our approach for the latter result is based on a better analysis of the (offline) Residual Random Greedy (RRG) algorithm of [Buchbinder-Feldman-Naor-Schwartz SODA`14], which we believe might be of independent interest.

Mohammad Reza Aminian, Rad Niazadeh, Pranav Nuti

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/(πk)} + O(1/k)$-selectable OCRS for $k$-uniform matroids and a simple, explicit $1/2$-selectable OCRS for weakly Rayleigh matroids (including all $\mathbb{C}$-representable matroids such as graphic and laminar). While these guarantees match the best known bounds, our framework also yields concrete and systematic constructions, providing transparent algorithms in settings where previous OCRSs were implicit or technically involved.

Pranav Nuti, Peter Westbrook

In this paper, we study $k$-unit single sample prophet inequalities. A seller has $k$ identical, indivisible items to sell. A sequence of buyers arrive one-by-one, with each buyer's private value for the item, $X_i$, revealed to the seller when they arrive. While the seller is unaware of the distribution from which $X_i$ is drawn, they have access to a single sample, $Y_i$ drawn from the same distribution as $X_i$. What strategies can the seller adopt for selling items so as to maximize social welfare? Previous work has demonstrated that when $k = 1$, if the seller sets a price equal to the maximum of the samples, they can achieve a competitive ratio of $\frac{1}{2}$ of the social welfare, and recently Pashkovich and Sayutina established an analogous result for $k = 2$. In this paper, we prove that for $k \geq 3$, setting a (static) price equal to the $k^{\text{th}}$ largest sample also obtains a competitive ratio of $\frac{1}{2}$, resolving a conjecture Pashkovich and Sayutina pose. We also consider the situation where $k$ is large. We demonstrate that setting a price equal to the $(k-\sqrt{2k\log k})^{\text{th}}$ largest sample obtains a competitive ratio of $1 - \sqrt{\frac{2\log k}{k}} - o\left(\sqrt{\frac{\log k}{k}}\right)$, and that this is the optimal possible ratio achievable with a static pricing scheme with access to a single sample. This should be compared against a competitive ratio $1 - \sqrt{\frac{\log k}{k}} - o\left(\sqrt{\frac{\log k}{k}}\right)$, which is the optimal possible ratio achievable with a static pricing scheme with knowledge of the distributions of the values.