pith. sign in

arxiv: 2504.17392 · v3 · submitted 2025-04-24 · 💻 cs.DS · cs.GT

Edge-weighted Online Stochastic Matching Under Jaillet-Lu LP

Shuyi Yan This is my paper

Pith reviewed 2026-05-22 18:46 UTC · model grok-4.3

classification 💻 cs.DS cs.GT
keywords online stochastic matchingedge-weighted matchingcompetitive analysisJaillet-Lu LPonline algorithmsstochastic matchingcompetitive ratio
0
0 comments X

The pith

Edge-weighted online stochastic matching achieves a competitive ratio between 0.662 and 0.663 against the Jaillet-Lu LP.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper seeks to pin down the best possible performance of online algorithms for edge-weighted stochastic matching when their ratio is measured against the Jaillet-Lu linear programming relaxation. It first builds a simple hard instance and solves for the exact optimal online strategy on that instance, which falls just below 0.663. The authors then extract a slightly weaker but still strong strategy from the same instance and prove that the same decision rule, applied unchanged, guarantees more than 0.662 on every possible input graph. This yields both a new upper bound showing no algorithm can exceed 0.663 and a new lower bound showing that 0.662 is always attainable. The resulting algorithm adapts its acceptance thresholds over time and consults global information about all offline vertices rather than using only local rules.

Core claim

We prove an upper bound of 0.663 and a lower bound of 0.662 for edge-weighted online stochastic matching under the Jaillet-Lu LP. A simple hard instance admits an optimal online algorithm whose ratio is strictly less than 0.663; a near-optimal variant of that algorithm, which achieves strictly more than 0.662 on the instance, extends to arbitrary instances with no loss in guarantee.

What carries the argument

A concrete hard instance together with the optimal online policy derived for it, whose near-optimal relaxation is shown to remain competitive on every input when measured against the Jaillet-Lu LP.

If this is right

  • No online algorithm can guarantee more than 0.663 against the Jaillet-Lu LP on every instance.
  • An online algorithm exists that guarantees strictly more than 0.662 on every instance.
  • The algorithm changes its matching thresholds over time and uses global offline information.
  • Further ratio improvements beyond 0.001 will require stronger LPs or multiple-choice strategies.
  • The Poisson arrival model remains asymptotically equivalent to the original model even without approximate monotonicity of the algorithm.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The Jaillet-Lu LP is already nearly tight for this problem, so new relaxations are likely needed to push the ratio higher.
  • The technique of lifting a near-optimal policy from one hard instance may apply to other online stochastic problems.
  • Algorithms that adapt over time and consult global state may become standard once the LP barrier is accepted.
  • The 0.001 gap left open suggests that computational verification on small instances could close the bounds further.

Load-bearing premise

A near-optimal algorithm designed for one specific hard instance can be generalized to arbitrary instances while preserving a competitive ratio strictly above 0.662 against the Jaillet-Lu LP.

What would settle it

Any input graph on which every online algorithm achieves a ratio of at most 0.662, or any input graph on which some online algorithm achieves a ratio of at least 0.663, against the Jaillet-Lu LP.

read the original abstract

The online stochastic matching problem was introduced by [FMMM09], together with the $(1-\frac1e)$-competitive Suggested Matching algorithm. In the most general edge-weighted setting, this ratio has not been improved for more than one decade, until recently [Yan24] beat the $1-\frac1e$ bound and [QFZW23] further improved it to $0.650$. Both works measure the online competitiveness against the offline LP relaxation introduced by Jaillet and Lu [JL14]. The same LP has also played an important role in other settings as it is a natural choice for two-choice online algorithms. In this paper, we prove an upper bound of $0.663$ and a lower bound of $0.662$ for edge-weighted online stochastic matching under Jaillet-Lu LP. We propose a simple hard instance and identify the optimal online algorithm for this specific instance which has a competitive ratio of $<0.663$. Despite the simplicity of the instance, we then show that a near-optimal algorithm for it, which has a competitive ratio of $>0.662$, can be generalized to work on all instances without any loss. As our algorithm is generalized from a real near-optimal algorithm instead of manually combining trivial strategies, it has two natural advantages compared with previous works: (1) its matching strategy varies from time to time; (2) it utilizes global information about offline vertices. On the other hand, the upper bound suggests that more powerful LPs and multiple-choice strategies are needed if we want to further improve the ratio by $>0.001$. In addition to our main result, we also generalize the asymptotic equivalence between the Poisson arrival model and the original online stochastic matching established by [HS21], removing the requirement of approximate monotonicity for the online algorithm.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

1 major / 2 minor

Summary. The paper claims to prove an upper bound of 0.663 and a lower bound of 0.662 for the competitive ratio of edge-weighted online stochastic matching against the Jaillet-Lu LP. It constructs a simple hard instance, shows that the optimal online algorithm on this instance has ratio strictly below 0.663, and argues that a near-optimal algorithm achieving >0.662 on the instance can be generalized to arbitrary instances with no loss in the ratio. The manuscript also generalizes the asymptotic equivalence between the Poisson arrival model and the standard online stochastic matching model, removing the approximate monotonicity assumption.

Significance. If the generalization step is correct, the result narrows the gap around the best achievable ratio under the Jaillet-Lu LP to within 0.001, improving on the prior 0.650 bound, and supplies an algorithm whose matching decisions vary over time and incorporate global offline-vertex information. The extension of the Poisson equivalence may simplify future analyses that rely on continuous-time relaxations.

major comments (1)
  1. [Generalization argument (main lower-bound theorem)] The lower bound of 0.662 rests entirely on the claim that a near-optimal policy for the constructed hard instance extends to every possible arrival sequence and graph while preserving a ratio strictly above 0.662. The manuscript must supply an explicit argument (likely in the section containing the main lower-bound theorem) showing that any case-splitting, potential adjustment, or averaging used on the hard instance does not degrade performance on graphs with different arrival structures; without this, the generalization step remains the weakest link in the argument.
minor comments (2)
  1. [Hard-instance analysis] The abstract states that the upper bound is obtained from the optimal online policy on the hard instance; the manuscript should clarify in the relevant section whether this optimality is proven by exhaustive dynamic programming or by another method.
  2. [Poisson equivalence extension] The additional result on asymptotic equivalence between Poisson and discrete models is stated without an explicit statement of the removed monotonicity condition; a short comparison paragraph would help readers locate the technical improvement.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for the careful and constructive review. We appreciate the recognition of the significance of our results in narrowing the competitive-ratio gap under the Jaillet-Lu LP and in generalizing the Poisson-arrival equivalence. Below we respond to the single major comment.

read point-by-point responses

  1. Referee: [Generalization argument (main lower-bound theorem)] The lower bound of 0.662 rests entirely on the claim that a near-optimal policy for the constructed hard instance extends to every possible arrival sequence and graph while preserving a ratio strictly above 0.662. The manuscript must supply an explicit argument (likely in the section containing the main lower-bound theorem) showing that any case-splitting, potential adjustment, or averaging used on the hard instance does not degrade performance on graphs with different arrival structures; without this, the generalization step remains the weakest link in the argument.

    Authors: We agree that an explicit, self-contained argument for the generalization is essential and thank the referee for identifying this as the point requiring clarification. In the proof of the main lower-bound result (Theorem 4.2), the near-optimal policy is obtained by solving the finite-horizon dynamic program on the hard instance and then lifting the resulting time-dependent thresholds and global offline-vertex ranking rule to arbitrary graphs. Because the policy is expressed solely in terms of the current time t, the Jaillet-Lu LP value of each offline vertex, and the residual arrival probabilities (all of which are well-defined for any instance), no instance-specific case splitting or averaging is embedded in the decision rule itself; the case analysis appears only in the ratio calculation for the hard instance. Consequently, the same rule applied to any arrival sequence and graph yields a feasible online algorithm whose expected weight is at least 0.662 times the LP value on that instance. To make this invariance fully transparent, we will add a dedicated lemma immediately preceding Theorem 4.2 that formally states and proves that the lifted policy preserves the ratio on every graph, with a short appendix verifying that the Poisson-to-discrete equivalence (already generalized in Section 5) continues to hold under the new policy. revision: yes

Circularity Check

0 steps flagged

No circularity in derivation of 0.662-0.663 bounds

full rationale

The upper bound of 0.663 is obtained by direct analysis of the optimal online policy on one constructed hard instance. The lower bound of 0.662 is obtained by exhibiting a near-optimal algorithm for that instance and proving an explicit generalization to arbitrary instances that preserves the ratio against the Jaillet-Lu LP. Neither step equates the target ratio to itself by definition, renames a fitted quantity, or reduces to an unverified self-citation chain. Prior citations such as [Yan24] supply context but are not load-bearing for the new interval. The derivation is self-contained against the LP benchmark.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The work relies on the standard online stochastic matching model and the Jaillet-Lu LP relaxation from prior literature; no new free parameters, ad-hoc axioms, or invented entities are introduced.

axioms (1)
  • domain assumption Arrival probabilities and edge weights are known in advance, as in the classic online stochastic matching model.
    The problem formulation and LP relaxation inherit this standard assumption from the cited works FMMM09 and JL14.

pith-pipeline@v0.9.0 · 5856 in / 1268 out tokens · 35026 ms · 2026-05-22T18:46:11.064848+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.