In the Network Revenue Management (NRM) problem, products composed of up to L resources are sold to stochastically arriving customers. We take a randomized rounding approach to NRM, motivated by the modern tool of Online Contention Resolution Schemes (OCRS). The goal is to take a fractional solution to NRM that satisfies the resource constraints in expectation, and implement it in an online policy that satisfies the resource constraints with probability 1, while (approximately) preserving all of the sales that were prescribed by the fractional solution. In NRM and revenue management problems, customer substitution induces a negative correlation between products being demanded, making it difficult to apply the standard definition of OCRS. We start by deriving a more powerful notion of "random-element" OCRS that achieves a guarantee of 1/(1+L) for NRM with customer substitution, matching a common benchmark in the literature. We show this benchmark is unbeatable for all integers L that are the power of a prime number, using a construction based on finite affine planes. We then show how to beat this benchmark under any of three assumptions: 1) no customer substitution (i.e., in the standard OCRS setting); 2) products comprise one item from each of up to L groups; or 3) customers arrive in a uniformly random (instead of fixed adversarial) order. Finally, we show that under both assumptions 1) and 3), it is possible to do better than offline CRS when L ≥ 5. Our results have corresponding implications for Online Combinatorial Auctions, in which buyers bid for bundles of up to L items, and buyers being single-minded is akin to having no substitution. Our result under assumption 1) or 2) implies that 1/(1+L) can be beaten for Prophet Inequality on the intersection of L partition matroids, a problem of interest. In sum, our paper shows how to apply OCRS to all of these problems and establishes a surprising separation in the achievable guarantees when substitution is involved, under general resource constraints parametrized by L.

We use contention resolution schemes (CRS) to derive algorithms for the fair rationing of a single resource when agents have stochastic demands. We aim to provide ex-ante guarantees on the level of service provided to each agent, who may measure service in different ways (Type-I, II, or III), calling for CRS under different feasibility constraints (rank-1 matroid or knapsack). We are particularly interested in two-order CRS where the agents are equally likely to arrive in a known forward order or its reverse, which is motivated by online rationing at food banks. Indeed, for a mobile pantry driving along cities to ration food, it is equally efficient to drive that route in reverse on half of the days, and we show that doing so significantly improves the service guarantees that are possible, being more "fair" to the cities at the back of the route.

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.

We introduce a new approach for designing Random-order Contention Resolution Schemes (RCRS’s) via exact solution in continuous time. Given a function c(y):[0,1] → [0,1], we show how to select each element which arrives at time y ∈ [0,1] with probability exactly c(y). We provide a rigorous algorithmic framework for achieving this, which discretizes the time interval and also needs to sample its past execution to ensure these exact selection probabilities. We showcase our framework in the context of online contention resolution schemes for matching with random-order vertex arrivals. For bipartite graphs with two-sided arrivals, we design a (1+e−2)/2 ≈ 0.567-selectable RCRS, which we also show to be tight. Next, we show that the presence of short odd-length cycles is the only barrier to attaining a (tight) (1+e−2)/2-selectable RCRS on general graphs. By generalizing our bipartite RCRS, we design an RCRS for graphs with odd-length girth g which is (1+ e−2)/2-selectable as g → ∞. This convergence happens very rapidly: for triangle-free graphs (i.e., g ≥ 5), we attain a 121/240 + 7/16 e2 ≈ 0.563-selectable RCRS. Finally, for general graphs we improve on the 8/15 ≈ 0.533-selectable RCRS of (Fu et al., 2021) and design an RCRS which is at least 0.535-selectable. Due to the reduction of (Ezra et al., 2020), our bounds yield a 0.535-competitive (respectively, (1+ e−2)/2-competitive) algorithm for prophet secretary matching on general (respectively, bipartite) graphs under vertex arrivals.

We present new results for online contention resolution schemes for the matching polytope of graphs, in the random-order (RCRS) and adversarial (OCRS) arrival models. Our results include improved selectability guarantees (i.e., lower bounds), as well as new impossibility results (i.e., upper bounds). By well-known reductions to the prophet (secretary) matching problem, a c-selectable OCRS (RCRS) implies a c-competitive algorithm for adversarial (random order) edge arrivals. Similar reductions are also known for the query-commit matching problem. For the adversarial arrival model, we present a new analysis of the OCRS of Ezra et al. (EC, 2020). We show that this scheme is 0.344-selectable for general graphs and 0.349-selectable for bipartite graphs, improving on the previous 0.337 selectability result for this algorithm. We also show that the selectability of this scheme cannot be greater than 0.361 for general graphs and 0.382 for bipartite graphs. We further show that no OCRS can achieve a selectability greater than 0.4 for general graphs, and 0.433 for bipartite graphs. For random-order arrivals, we present two attenuation-based schemes which use new attenuation functions. Our first RCRS is 0.474-selectable for general graphs, and our second is 0.476-selectable for bipartite graphs. These results improve upon the recent 0.45 (and 0.456) selectability results for general graphs (respectively, bipartite graphs) due to Pollner et al. (EC, 2022). On general graphs, our 0.474-selectable RCRS provides the best known positive result even for offline contention resolution, and also for the correlation gap. We conclude by proving a fundamental upper bound of 0.5 on the selectability of RCRS, using bipartite graphs. * The full version of the paper can be accessed at https://arxiv.org/abs/2209.07520

Abstract. Motivated by the Beck–Fiala conjecture, we study the discrepancy problem in two related models of random hypergraphs on [Formula: see text] vertices and [Formula: see text] edges. In the first model, each of the [Formula: see text] edges is constructed by placing each vertex into the edge independently with probability [Formula: see text], where [Formula: see text] is a parameter satisfying [Formula: see text] and [Formula: see text]. In the second model, each vertex independently chooses a subset of [Formula: see text] edge labels from [Formula: see text] uniformly at random. Edge [Formula: see text] is then defined to be exactly those vertices whose [Formula: see text]-subsets include label [Formula: see text]. In the sparse regime, i.e., when [Formula: see text], we show that with high probability a random hypergraph from either model has discrepancy at least [Formula: see text]. In the dense regime, i.e., when [Formula: see text], we show that with high probability a random hypergraph from either model has discrepancy at least [Formula: see text], where [Formula: see text]. Furthermore, we obtain nearly matching asymptotic upper bounds on the discrepancy. Specifically, we apply the partial coloring lemma of Lovett and Meka to show that, in the dense regime, with high probability the two random hypergraph models each have discrepancy [Formula: see text]. In fact, in a significant parameter range we can tighten our analysis to get an upper bound which matches our lower bound up to a constant factor. This result is algorithmic, and together with the work of Bansal and Meka [ On the discrepancy of random low degree set systems, in Proceedings of the 2019 Annual ACM-SIAM Symposium on Discrete Algorithms, 2019, pp. 2557–2564] characterizes how the discrepancy of each random hypergraph transitions from [Formula: see text] to [Formula: see text] as [Formula: see text] increases from [Formula: see text] to [Formula: see text].

We consider the online bipartite stochastic matching problem with known i.d. (independently distributed) online vertex arrivals. In this problem, when an online vertex arrives, its weighted edges must be probed (queried) to determine if they exist, based on known edge probabilities. Our algorithms operate in the probe-commit model, in that if a probed edge exists, it must be used in the matching. Additionally, each online node has a downward-closed probing constraint on its adjacent edges which indicates which sequences of edge probes are allowable. Our setting generalizes the commonly studied patience (or time-out) constraint which limits the number of probes that can be made to an online node’s adjacent edges. Most notably, this includes non-uniform edge probing costs (specified by knapsack/budget constraint). We extend a recently introduced configuration LP to the known i.d. setting, and also provide the first proof that it is a relaxation of an optimal offline probing algorithm (the offline adaptive benchmark). Using this LP, we establish the following competitive ratio results against the offline adaptive benchmark: 1) A tight 1/2 ratio when the arrival ordering π is chosen adversarially. 2) A 1-1/e ratio when the arrival ordering π is chosen u.a.r. (uniformly at random). If π is generated adversarially, we generalize the prophet inequality matching problem. If π is u.a.r., we generalize the prophet secretary matching problem. Both results improve upon the previous best competitive ratio of 0.46 in the more restricted known i.i.d. (independent and identically distributed) arrival model against the standard offline adaptive benchmark due to Brubach et al. We are the first to study the prophet secretary matching problem in the context of probing, and our 1-1/e ratio matches the best known result without probing due to Ehsani et al. This result also applies to the unconstrained bipartite matching probe-commit problem, where we match the best known result due to Gamlath et al.

The semi-random graph process is a single player game in which the player is initially presented an empty graph on $n$ vertices. In each round, a vertex $u$ is presented to the player independently and uniformly at random. The player then adaptively selects a vertex $v$, and adds the edge $uv$ to the graph. For a fixed monotone graph property, the objective of the player is to force the graph to satisfy this property with high probability in as few rounds as possible. We focus on the problem of constructing a Hamiltonian cycle in as few rounds as possible. In particular, we present an adaptive strategy for the player which achieves it in $αn$ rounds, where $α< 2.01678$ is derived from the solution to some system of differential equations. We also show that the player cannot achieve the desired property in less than $βn$ rounds, where $β> 1.26575$. These results improve the previously best known bounds and, as a result, the gap between the upper and lower bounds is decreased from 1.39162 to 0.75102.

The semirandom graph process is a single player game in which the player is initially presented an empty graph on $n$ vertices. In each round, a vertex $u$ is presented to the player independently and uniformly at random. The player then adaptively selects a vertex $v$ and adds the edge $uv$ to the graph. For a fixed monotone graph property, the objective of the player is to force the graph to satisfy this property with high probability in as few rounds as possible. We focus on the problem of constructing a perfect matching in as few rounds as possible. In particular, we present an adaptive strategy for the player which achieves a perfect matching in $\beta n$ rounds, where the value of $\beta < 1.206$ is derived from a solution to some system of differential equations. This improves upon the previously best known upper bound of $(1+2/e+o(1)) \, n < 1.736 \, n$ rounds. We also improve the previously best lower bound of $(\ln 2 + o(1)) \, n > 0.693 \, n$ and show that the player cannot achieve the desired property in less than $\alpha n$ rounds, where the value of $\alpha > 0.932$ is derived from a solution to another system of differential equations. As a result, the gap between the upper and lower bounds is decreased roughly four times.

We consider the online bipartite matching problem within the context of stochastic probing with commitment. This is the one-sided online bipartite matching problem where edges adjacent to an online node must be probed to determine if they exist based on edge probabilities that become known when an online vertex arrives. If a probed edge exists, it must be used in the matching. We consider the competitiveness of online algorithms in the adversarial order model (AOM) and the secretary/random order model (ROM). More specifically, we consider an unknown bipartite stochastic graph G = (U,V,E) where U is the known set of offline vertices, V is the set of online vertices, G has edge probabilities (p_{e})_{e ∈ E}, and G has edge weights (w_{e})_{e ∈ E} or vertex weights (w_u)_{u ∈ U}. Additionally, G has a downward-closed set of probing constraints (𝒞_{v})_{v ∈ V}, where 𝒞_v indicates which sequences of edges adjacent to an online vertex v can be probed. This model generalizes the various settings of the classical bipartite matching problem (i.e. with and without probing). Our contributions include the introduction and analysis of probing within the random order model, and our generalization of probing constraints which includes budget (i.e. knapsack) constraints. Our algorithms run in polynomial time assuming access to a membership oracle for each 𝒞_v. In the vertex weighted setting, for adversarial order arrivals, we generalize the known 1/2 competitive ratio to our setting of 𝒞_v constraints. For random order arrivals, we show that the same algorithm attains an asymptotic competitive ratio of 1-1/e, provided the edge probabilities vanish to 0 sufficiently fast. We also obtain a strict competitive ratio for non-vanishing edge probabilities when the probing constraints are sufficiently simple. For example, if each 𝒞_v corresponds to a patience constraint 𝓁_v (i.e., 𝓁_v is the maximum number of probes of edges adjacent to v), and any one of following three conditions is satisfied (each studied in previous papers), then there is a conceptually simple greedy algorithm whose competitive ratio is 1-1/e. - When the offline vertices are unweighted. - When the online vertex probabilities are "vertex uniform"; i.e., p_{u,v} = p_v for all (u,v) ∈ E. - When the patience constraint 𝓁_v satisfies 𝓁_v ∈ {[1,|U|} for every online vertex; i.e., every online vertex either has unit or full patience. Finally, in the edge weighted case, we match the known optimal 1/e asymptotic competitive ratio for the classic (i.e. without probing) secretary matching problem.