| paper | Online Matching with Delays and Stochastic Arrival Times |
| authors | — |
| venue | AAMAS 2023 |
| filed under | coalition · matching |
| judged by | gpt-5.6-terra / high (triple__gpt-5.6-terra__high__ctx2r8-rejudge1) |
| judge confidence | high |
| authors would recognise it | no |
The paper has a named computational result, but the proposed mirror does not continuize its population: \(\mu\) specifies a stochastic arrival distribution, not masses that can be matched as a society. A literal mass-flow version eliminates the atomic waiting and parity effects that generate the paper's objective, while adding constraints to restore them would no longer be Theorem 2's problem.
fails bit b — no continuous question survives
The proposed construction restates the stochastic Poisson-input setting behind Theorem 2 and leaves Theorems 1, 25, and 26 aside.
The strongest honest mirror is a long-horizon, high-multiplicity one—not a simultaneous fluid market.
Call the lead question Stochastic-Flow MPMD\(_\infty\). An instance consists of a finite metric \((X,d)\), a continuous society \(\mu\in\Delta(X)\), and a throughput \(\Lambda>0\). Type \(x\) means “a request with this complete compatibility/location/skill bucket”; all type-\(x\) requests have the same distances to every other type and the same arrival mechanism. The population is the rate distribution: type \(x\) supplies mass \(\mu_x\) of society, at rate \(\lambda_x=\Lambda\mu_x\). Requests are realized by independent Poisson streams of those rates.
A feasible solution is a causal matching policy: after each realized arrival it may irrevocably match any two pending requests, and it may not use future arrivals. Its objective is the paper’s long-run ratio of expectations,
\[ \limsup_{m\to\infty} \frac{\mathbb E[\mathrm{cost}_\pi(\sigma_m)]} {\mathbb E[\mathrm{OPT}(\sigma_m)]}. \]
The computational problem is: given rational \((X,d,\mu,\Lambda)\), synthesize a policy with a guaranteed constant ratio, or, more ambitiously, decide whether a policy of ratio at most \(K\) exists. At the macroscopic level a policy induces a flow of mass from pending age-and-location states into matched pairs; the individual Poisson events are the microscopic realization of that continuous society, rather than an adversarial discrete profile with noise added afterward.
My anchor is Theorem 2, proved in this paper (using Lemmas 12 and 13): for MPMD under Poisson arrivals, the Radius algorithm has ratio-of-expectations
\[ 8/(1-e^{-2}). \]
This is the strongest anchor, and I would not pad it with Theorem 1: it is the same mirror with a weaker guarantee. The theorem directly answers the constant-approximation/synthesis version of Stochastic-Flow MPMD\(_\infty\). The Radius policy is computable from the continuous input: its radii are determined by the rate masses \(\lambda_x\) and metric balls, then the policy uses those values online. I would therefore put this in Class A at the approximation level. Exact optimal-policy computation, and the threshold question for a given \(K\), remain genuine follow-up complexity questions.
The regime is a large, continuing platform with a stable, coarse taxonomy—say, a national gaming or service-matching platform whose requests fall into a few hundred skill/region/mode classes over millions of sessions. The number of realized agents over the operating horizon is enormous, while the type set is fixed by the product taxonomy. “23% of incoming requests are type \(x\)” is the natural primitive description; an observed sequence of requests is merely one realization. This is especially close to the authors’ own motivation that historical data estimates arrival frequency by skill level, and to their own asymptotic definition, which takes \(m\to\infty\) while the Poisson rates stay fixed. Rewriting \((\lambda_x)_{x\in X}\) as \((\mu,\Lambda)\) does not alter their mathematical problem; it makes explicit that the input is a continuous society plus its activity level.
The mirror covers the paper’s stochastic MPMD result represented by Theorem 2, not the whole paper. A useful extension would mirror Theorem 25 by replacing linear waiting cost with a supplied nondecreasing \(f\), asking for a policy with constant ratio whenever the relevant exponential expectation is finite. I would leave that as a follow-up rather than a second anchor, because its computational input model for \(f\) needs care.
The weak point is real: this is not the strongest kind of fluid limit. If one instead scales all arrival rates to infinity at fixed time scale and allows literal fractional matching, same-location mass can match immediately at zero metric cost; much of MPMD’s delay tradeoff collapses. The meaningful continuization keeps rates fixed and lets the population grow through a long operating horizon, so Poisson timing and temporary imbalance remain economically real. That makes this a narrower and less automatic high-multiplicity case than election control—but it is still a credible one: it is exactly the continuing-market regime the paper models, expressed with the society \(\mu\) rather than a named list of requests.
Theorem 2 does not supply a continuous-population mirror; it supplies a stochastic, continuous-*time* model of individual requests. Writing its real rate vector as \(\lambda_x=\Lambda\mu_x\) is only a reparameterization. The input and policy are still a finite metric plus Poisson point processes, and every decision is over particular pending requests with particular arrival times. Indeed, the proposed “synthesis” question is already answered by the paper itself: compute radii from the rates and run Radius. That is not a new high-multiplicity relaxation of MPMD.
The more fundamental problem is that a request’s location is not its complete type for this optimization problem. Two requests at the same \(x\) but with different arrival times have different current delay liabilities and can rationally be treated differently. If age/arrival time is included in the type, then under continuous-time Poisson arrivals essentially no two live requests share a type. The supposed coarse taxonomy is useful for estimating a stochastic input distribution, but it does not make the online decision state high-multiplicity.
Trying to repair that by genuinely replacing requests with a mass flow destroys the MPMD tradeoff. In the paper’s non-bipartite model, mass arriving at each location can be paired with contemporaneous mass at that same location, at zero connection and waiting cost. The positive cost analysed in Theorem 2 comes from indivisible Poisson arrivals, temporary oddness, and the need to choose among individually aged pending requests. Those are exactly the features a fluid population limit averages away. The resulting zero/degenerate benchmark is not a useful continuization of the competitive-ratio problem.
There is a real fork here, and neither branch yields the programme’s object. Keep fixed Poisson rates over a long horizon, as the proponent does, and one has the paper’s existing stochastic online model with individual events—not a continuous society. Scale to literal population mass, and the matching-with-delay objective collapses. One can invent a nontrivial fluid model by imposing incompatibility classes, aggregate capacity constraints, deadlines, or persistent supply-demand imbalance, but then it is a different dynamic matching/control problem; Theorem 2 no longer anchors it, and its computational question is not inherited from this paper.
Theorem 25 inherits the same issue: changing the delay function does not change the fact that all meaningful delay is caused by atomic, time-stamped requests. So the negative case is strong here: MPMD is a worthwhile stochastic online-matching model, but its informative asymptotic is a long sequence of individuated events, not a high-multiplicity society.
The adversarial triple: the proponent anchors on up to three named results; the opponent sees that case and must defeat every anchor; the judge decides which case convinced it. These are the pipeline’s own outputs, generated by tools/triple_run.py — no human edited them. The paper’s own text is not reproduced here beyond the quoted statement above.