Calum MacRury

Given an edge-colored graph, the goal of the proportional fair matching problem is to find a maximum weight matching while ensuring proportional representation (with respect to the number of edges) of each color. The colors may correspond to demographic groups or other protected traits where we seek to ensure roughly equal representation from each group. It is known that, assuming ETH, it is impossible to approximate the problem with ℓ colors in time subexponential in ℓ even on unweighted path graphs. Further, even determining the existence of a non-empty matching satisfying proportionality is NP-Hard. To overcome this hardness, we relax the stringent proportional fairness constraints to a probabilistic notion. We introduce a notion we call δ-PʀᴏʙᴀʙʟʏFᴀɪʀ where we ensure proportionality up to a factor of at most (1 ± δ) for some small δ > 0 with high probability. The violation δ can be brought arbitrarily close to 0 for some good instances with large values of matching size. We propose and analyze simple and fast algorithms for bipartite graphs that achieve constant-factor approximation guarantees, and return a δ-PʀᴏʙᴀʙʟʏFᴀɪʀ matching.

Online Contention Resolution Schemes for the Matching Polytope of Graphs Online contention resolution schemes (OCRSs) are used to select a subset of elements, subject to feasibility constraints. Originally developed as a randomized rounding tool for constrained submodular optimization, OCRSs have found numerous applications in online resource allocation and stochastic optimization. This includes problems such as prophet inequalities, stochastic probing, auction design, and matching in a gig economy. In “On (Random-Order) Online Contention Resolution Schemes for the Matching Polytope of (Bipartite) Graphs,” Calum MacRury, Will Ma, and Nathaniel Grammel study OCRSs when the feasibility constraints are defined by graph matchings. The authors consider when the elements are sequentially presented in adversarial or random order, as well as when the graph is bipartite or general. In each combination of variants, the authors improve the state of the art, both in terms of algorithmic guarantees and impossibility results.

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.

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 ≈ 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-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-selectable as g → ∞. This convergence happens very rapidly: for triangle-free graphs (i.e., g ≥ 5), we attain a 121/240 + 7/16 e² ≈ 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-competitive) algorithm for prophet secretary matching on general (respectively, bipartite) graphs under vertex arrivals.

Online Contention Resolution Schemes (OCRS's) represent a modern tool for selecting a subset of elements, subject to resource constraints, when the elements are presented to the algorithm sequentially. OCRS's have led to some of the best-known competitive ratio guarantees for online resource allocation problems, with the added benefit of treating different online decisions -- accept/reject, probing, pricing -- in a unified manner. This paper analyzes OCRS's for resource constraints defined by matchings in graphs, a fundamental structure in combinatorial optimization. We consider two dimensions of variants: the elements being presented in adversarial or random order; and the graph being bipartite or general. We improve the state of the art for all combinations of variants, both in terms of algorithmic guarantees and impossibility results. Some of our algorithmic guarantees are best-known even compared to Contention Resolution Schemes that can choose the order of arrival or are offline. All in all, our results for OCRS directly improve the best-known competitive ratios for online accept/reject, probing, and pricing problems on graphs in a unified manner.