Pith. sign in

REVIEW 3 major objections 5 minor 17 references

Greedy Dynamic Matching

T0 review · 3 major / 5 minor · reviewed 2026-08-06 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read For dynamic matching markets in which all agents share a common departure rate, a greedy policy selected by a linear program earns at least half of the omniscient reward, and no online policy can guarantee more than that half.

desk verdict Solid 1/2 lower bound for greedy matching under homogeneous departures, but the tightness claim rests on an admitted-buggy cited lemma and needs repair. read the letter →

arxiv 2507.04551 v2 pith:GFLJDQSE submitted 2025-07-06 cs.DS

Nick Arnosti , Felipe Simon This is my paper
classification cs.DS MSC 68W2760K2590C05
keywords dynamicmatchingmarketsgreedypoliciescompetitiveratioomniscientbenchmarklinearprogramminglowerboundsagentabandonmentMarkovianPoissonarrivals
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

Dynamic matching markets pair agents who arrive over time, earn a reward for each pair, and lose agents who wait too long and give up. This paper asks how much is lost by insisting on greedy policies, which fix a list of acceptable matches in advance and match as soon as both partners are present. The answer, for markets where all agents have the same patience, is that a greedy policy chosen by the authors' algorithm earns at least half of what an omniscient planner with full knowledge of the future earns, and no online policy can guarantee more than half. The proof works by building a linear program whose optimal value certifies the greedy policy's reward from below, a direction earlier LP-based analyses could not achieve. The same guarantee covers bipartite markets where patience is equal within each side, and it improves the previous general guarantee of $\frac{1}{8}$.

What carries the argument

The engine is the linear program $\mathrm{LP}^{\mathrm{ALG}}(I, M)$, whose variables are steady-state expected queue lengths $n_i$, match rates $x_{ij}$, and slacks $\psi_{Sj}$. Constraint (13) balances each type's arrivals against matches and abandonment, while constraint (14) caps the rate at which arriving type-$j$ agents match into a type set $S$ at $\lambda_j \gamma_S \sum_{i \in S} n_i$, using $\gamma_S = \frac{1 - e^{-\sum_{i\in S}\lambda_i/\mu_i}}{\sum_{i\in S}\lambda_i/\mu_i}$ as a deliberately pessimistic estimate of the probability that an $S$-agent is present. A 'suitable' basic feasible solution is one in which $\psi_{Sj} = 0$ forces $x_{ij} > 0$ for every $i \in S$; Lemma 3 shows that such a solution encodes the preference lists of a greedy policy, and Algorithm 1 removes matches until the optimal solution is suitable. The technical core is Lemma 1, a complement to Markov's inequality asserting that, for any Markovian policy and any set $S$ of types sharing one departure rate, the probability that at least one $S$-agent is present is at least $\gamma_S$ times the expected number present. Lemma 6 then shows the greedy policy's match-rate vector 'pierces' the LP's feasible region, so the LP value cannot exceed the policy's true reward, and Proposition 3 ties the bounds together so the chain closes at a factor of two.

What would settle it

On the two-type instance of Example 1 (arrival rate $\lambda_1 = 1$, departure rates $\mu_1 = \mu_2 = \mu$, rewards $r_{11} = 2+\mu$, $r_{12} = r_{21} = 1$, $r_{22} = 0$), take $\lambda_2$ very large and $\mu$ large, and compute via dynamic programming on a truncated state space the best reward rate any Markovian policy can achieve; beating $(\frac{1}{2}+\epsilon)\,\mathrm{OMN}(I)$ would refute Theorem 2. Independently, a numerical search for any instance without homogeneous departures in which $V(\mathrm{ALG}(I), I) < \frac{1}{2}\,\mathrm{OMN}(I)$ would refute Conjecture 1 and show the departure-rate assumption is doing real work; Section 5's random instances found no such case.

Watch

Extended reading notes

Core claim

The paper's central claim is Theorem 1: for any instance $I$ with homogeneous departures, the greedy policy $\mathrm{ALG}(I)$ produced by Algorithm 1 satisfies $V(\mathrm{ALG}(I), I) \geq \frac{1}{2}\,\mathrm{OMN}(I)$, where $\mathrm{OMN}(I)$ is the reward rate of the omniscient policy that knows the whole arrival and departure sequence. Theorem 2 says the factor is tight: for every $\epsilon > 0$ there is a homogeneous-departure instance on which every Markovian online policy earns less than $(\frac{1}{2}+\epsilon)\,\mathrm{OMN}(I)$. The route is a new family of linear programs $\mathrm{LP}^{\mathrm{ALG}}(I, M)$ whose optimal value is a lower bound on the reward rate of the greedy policy it encodes (Proposition 1), paired with a new linear program $\mathrm{LP}^{\mathrm{OMN}}_{\mathrm{REL}}(I)$ that upper bounds the omniscient benchmark (Proposition 2) and lies within a factor of two of $\mathrm{LP}^{\mathrm{ALG}}(I, M)$ (Proposition 3). These pieces close the chain $\frac{1}{2}\mathrm{LP}^{\mathrm{OMN}}(I) \leq \mathrm{LP}^{\mathrm{ALG}}(I,M) \leq V(\mathrm{ALG}(I),I) \leq \mathrm{OMN}(I) \leq \mathrm{LP}^{\mathrm{OMN}}(I)$; every inequality holds for arbitrary instances except the lower-bound step, which is exactly where the homogeneous-departure condition enters through Lemma 1.

Load-bearing premise

The claim that $\frac{1}{2}$ is the best any online policy can do leans on an upper bound imported from another paper whose proof the authors themselves describe as mistaken, and no corrected proof is supplied here; if that imported bound is wrong, the tightness claim is unsupported even though the guarantee of at least $\frac{1}{2}$ might still stand.

Editorial extensions

If this is right

  • In homogeneous-departure markets, a platform can secure half of the omniscient reward with a greedy policy whose preference lists come from one solve of a linear program; no lookahead or forecasting is needed.
  • The factor $\frac{1}{2}$ is a ceiling as well as a floor: Theorem 2 excludes any guarantee above $\frac{1}{2}$ for every online policy, so the greedy algorithm is optimal up to the best possible constant.
  • The new upper-bound LP (Proposition 2) is tighter than the bounds of Collina et al. (2020) and Kessel et al. (2022) and handles non-bipartite compatibility graphs; combined with an existing result it yields a $(e-1)/(2e)$ guarantee for bipartite instances (Appendix C.2).
  • With only two types the $\frac{1}{2}$ guarantee holds even without homogeneous departures (Theorem 3), and numerical evidence suggests the assumption may be unnecessary in general (Conjecture 1).

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The lower-bound LP technique is portable in spirit: any matching or queueing setting in which the probability of 'some agent from set $S$ being present' admits a lower bound proportional to the expected number present could inherit the same proof template, including markets with non-exponential patience or correlated arrivals.
  • The authors show Lemma 1's inequality fails for a hand-built generic Markovian policy (Appendix C.3) but have found no greedy counterexample; if the inequality holds for every greedy policy, then Conjecture 1 follows and the homogeneous-departure condition in Theorem 1 is an artifact of the proof rather than of the problem.
  • The tightness construction uses an omniscient policy that pairs adjacent future arrivals of the same type, information a greedy policy cannot see; that suggests the entire gap of $\frac{1}{2}$ is the value of knowing future departure times, consistent with earlier work where that information pushes guarantees above $\frac{1}{2}$.
  • A cheap test of the conjecture outside the proven regime: run $\mathrm{ALG}(I)$ on small instances with strongly asymmetric departure rates, comparing against $\frac{1}{2}\,\mathrm{OMN}(I)$; the experiments in Section 5 hint the algorithm survives, but a counterexample, if one exists, would likely be small and asymmetric.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 5 minor

Summary. The paper studies dynamic matching with Poisson arrivals, exponential abandonment, type-dependent rewards, and an omniscient benchmark that knows the full future. It introduces a family of linear programs, LP^ALG, whose suitable optimal solutions define greedy policies. Under homogeneous-departure assumptions, the paper proves that the resulting greedy policy earns at least half of the omniscient reward rate (Theorem 1), improving the previous 1/8 bound. The proof combines a lower-bound LP for the greedy policy (Lemma 1 and Proposition 1), an upper-bound LP for the omniscient policy (Proposition 2), and a factor-2 comparison between the two LPs (Proposition 3). The paper also claims that the 1/2 ratio is best possible for Markovian policies (Theorem 2), proves a two-type extension (Theorem 3), and reports numerical experiments suggesting the 1/2 guarantee may hold more broadly.

Significance. If Theorem 1 is correct, the paper gives a substantial quantitative improvement over the prior 1/8 competitive ratio and introduces a genuinely novel proof device: using a linear program as a lower bound on the value of a concrete greedy policy, rather than only as an upper bound. The proof chain is explicit, parameter-free, and the paper is careful to separate proven results from conjectures, including a counterexample showing that the key inequality in Lemma 1 can fail for general Markovian policies. However, the tightness claim currently rests on an imported lemma whose proof the authors themselves flag as incorrect, and the bipartite case of the homogeneous-departure theorem has a gap in the application of Lemma 1. These issues affect load-bearing claims and need to be resolved before the paper can be accepted.

major comments (3)
  1. [Appendix B.5, Theorem 2, Lemma 14, Footnote 1] The tightness result Theorem 2 is entirely mediated by Lemma 14, which is imported as Claim 3 of Aouad and Sarıtaç (2022). Footnote 1 admits that the original proof of this claim contains a mistake, and the manuscript supplies no corrected proof, no independent derivation, and no formal verification of the lemma. Since V(pi,I) <= LP^ON(I) is the only upper bound on online policies used in the proof of Theorem 2, the claimed upper bound of 1/2 + epsilon for all Markovian policies is unsupported if Lemma 14 is false or unproven. In addition, Lemma 14 is stated only for deterministic stationary policies, whereas Theorem 2 quantifies over all Markovian policies; the reduction from general Markovian policies to deterministic stationary ones is not given. This is a load-bearing gap in the tightness half of the paper's central claim.
  2. [Section 4.1, Lemma 1, Definition 2] The proof of Theorem 1 applies Lemma 1 to every set S with psi_Sj = 0, but Lemma 1 is stated only when all types in S have a common departure rate mu. In the bipartite case of Definition 2, departure rates are equal within each side but need not be equal across the two sides. The manuscript does not argue that the tight sets S arising in Proposition 1 are always contained in one side of the bipartition, nor does it prove an extension of Lemma 1 to sets that mix the two sides. As written, the claimed 1/2 guarantee for the bipartite setting with different side-specific departure rates does not follow from the lemmas stated in the paper.
  3. [Appendix C.1, Theorem 3] The proof of Theorem 3 contains an unsupported assertion in the equality case. It claims that if r12 - v1 - v2 = 0, then z_Sj = 0 for all S and j, so v1 = v2 = 0 and all rewards are zero. This does not follow from the dual constraints (42)-(43) as displayed: positive z_Sj can coexist with a zero score, because the z variables enter the constraints for v1 and v2 through equation (43). The case analysis therefore does not establish that the greedy policy matches in both directions, which is exactly what is needed to prove inequality (28) for S = {1,2}. The proof of the two-type extension is incomplete.
minor comments (5)
  1. [Abstract and Section 4] The abstract refers to '(Proposition 4)' for the 1/2 lower-bound claim and to '(Proposition 3)' for the new upper bound, but the numbered results in Section 4 are Proposition 2 for the upper bound and Proposition 3 for the factor-2 comparison. The numbering should be corrected.
  2. [Appendix B.5, Lemma 16] In the displayed computation of V(ADJ,I), the expression '2 - 2mu + 1/(1+mu)^2' appears to be a typo for '2 - (2mu+1)/(1+mu)^2'. The limiting argument as mu tends to infinity is correct, but the formula as printed is confusing.
  3. [Appendix B.2, Lemma 2] The compensated process X_Sj(t) - lambda_j * integral of 1(N_S(s) > 0) ds is called a submartingale in the proof of Lemma 2. For a non-prefix set S this process is a supermartingale, and the displayed inequality (72) has the correct direction. The terminology should be fixed.
  4. [Section 3.1, LP^ALG constraints (13)-(15)] Constraint (14) is written for S subset of T(M,j), but gamma_S is undefined when S is empty. The paper should state explicitly that the constraints range over nonempty subsets S, or otherwise define gamma_empty consistently.
  5. [Section 2.1, Definition 4] The quantity OMN(I) is defined as a limit as t tends to infinity, but the existence of this limit is not discussed. Since OMN(I) is the benchmark in Theorems 1 and 2, a brief justification of the limit's existence would make the statements fully rigorous.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the 1/2 lower-bound proof is self-contained, and the tightness proof imports an external (admittedly buggy) upper bound, which is a correctness risk, not circularity.

full rationale

Walking the derivation chain, Theorem 1 is obtained as V(ALG(I),I) >= LP_ALG(I,M) (Proposition 1), LP_OMN_REL(I) <= 2*LP_ALG(I,M) (Proposition 3), and OMN(I) <= LP_OMN_REL(I) (Proposition 2). Each inequality is proved rather than assumed: Proposition 1 relies on Lemma 1, an independent probabilistic inequality proved from cut balance equations in Appendix B.1, and on Lemma 6, which constructs a feasible point of LP_ALG from the greedy policy's match rates; Proposition 2 is an upper bound proved in Appendix B.4; Proposition 3 follows from strong duality and Lemmas 7-8. LP_ALG(I,M) is not defined in terms of V(ALG(I),I), and the greedy policy is constructed from a suitable basic feasible solution, not from the omniscient benchmark. No parameter is fitted to OMN(I) and the competitive ratio is proven, not enforced by construction. The one load-bearing external input is Lemma 14 (Aouad and Saritac 2022, Claim 3), used in Appendix B.5 to prove the tightness claim Theorem 2. The paper's own Footnote 1 in Section 1.1 states 'The original proof has a mistake but we still believe the result to hold true,' and no corrected proof or verification is supplied; additionally, the lemma is stated for deterministic stationary policies while Theorem 2 quantifies over all Markovian policies. These are genuine validity risks for the tightness claim, but they are not circularity: the cited result is external, its content is not equivalent to the paper's definitions or to Theorem 2, and the 1/2 guarantee of Theorem 1 does not depend on it. Under the given patterns, an admitted-buggy external lemma belongs to correctness risk, not to self-referential circularity.

Assumptions & free parameters 0 free parameters · 5 assumptions · 0 invented entities

The central claim rests only on the model primitives (Poisson arrivals, exponential abandonment), standard LP duality and Markov-chain ergodicity, and one cited external bound whose proof is acknowledged to be flawed. No free parameters are fitted and no new entities are postulated.

assumptions (5)
  • domain assumption Poisson arrivals with rates lambda_i and exponential abandonment with rates mu_i, independent across agents.
    Model in Section 2; all results are relative to this stochastic process.
  • standard math Every Markovian policy induces an ergodic CTMC with a unique steady state.
    Lemma 9, proved via a drift criterion from Prieto-Rumeau and Hernandez-Lerma (2016).
  • standard math Strong duality, complementary slackness, and the basic feasible solution structure of linear programs.
    Used in Sections 3-4 and Appendix A to map LP solutions to greedy policies and to prove Proposition 3.
  • domain assumption Aouad and Saritac (2022) Claim 3: LP_ON upper-bounds any stationary deterministic online policy.
    Used in Appendix B.5 for Theorem 2 and in Appendix C.2 for the bipartite ratio; the paper's footnote admits that the original proof has a mistake.
  • domain assumption Aouad and Saritac (2022) Lemma 17: LP_ON solutions can be converted to Markovian policies achieving kappa(1-1/e) of the LP value.
    Used only in Appendix C.2 for the bipartite competitive ratio, not for Theorem 1.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Greedy Dynamic Matching." pith.science (2026). https://pith.science/paper/GFLJDQSE

@misc{pith2026250704551,
  author       = {Pith},
  title        = {Pith review of: Greedy Dynamic Matching},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/GFLJDQSE}},
  note         = {Machine review of arXiv:2507.04551}
}
abstract

We study a foundational model of dynamic matching market with abandonment. This model has been studied by Collina et al (2020) and Aouad and Saritac (2022), and many other papers have considered special cases. We compare the performance of greedy policies -- which identify a set of "acceptable" matches up front, and perform these matches as soon as possible -- to that of an omniscient benchmark which knows the full arrival and departure sequence. We use a novel family of linear programs ($LP^{ALG}$) to identify which greedy policy to follow. We show that the value of $LP^{ALG}$ is a *lower bound* on the value of the greedy policy that it identifies in two settings of interest: -When all types have the same departure rate. -The bipartite case where types on the same side of the market have the same departure rate. The proofs of these results use a new result (Lemma 1), which relates the *probability* that at least one agent from a set of types is present in the system to the expected number of such agents. We also show that the value of $LP^{ALG}$ is at least 1/2 of the reward rate earned by the omniscient policy (Proposition 4). Therefore, for both settings above, our greedy policy provably earns at least half of the omniscient reward rate. This improves upon the bound of 1/8 from Collina (2020). In both settings our competitive ratio of 1/2 is the best possible: no online policy can provide a better guarantee (Theorem 2). To show these results we introduce a new linear program that upper bounds the objective value of the omniscient policy (Proposition 3). This improves upon the upper bounds presented by Collina et al (2020) and Kessel et al (2022).

Figures

Figures reproduced from arXiv: 2507.04551 by the authors.

Figure 1
Figure 1. Visualization of Lemma 6. The blue region represents the polytope of feasible so￾lutions to LPALG(I,M). The point x ∗ is a vertex of this polytope. The red line is deter￾mined by the rewards r, and represents the set of points which have the same objective value as x ∗ . Although x π may not component-wise dominate x ∗ , Lemma 6 shows that the “arrow” from x π to x ∗ “pierces” the feasible region, which implies that… view at source ↗
Figure 2
Figure 2. Comparison between LPALG(I,M), V (˜π(I), I, t), OMN(I, t) and LPOMN(I) for 100 simulations with |T | = 3 and t = 100000. 23 [PITH_FULL_IMAGE:figures/full_fig_p023_2.png] view at source ↗
Figure 3
Figure 3. Comparison between LPALG(I,M), V (˜π(I), I, t), OMN(I, t) and LPOMN(I) for 100 simulations with |T | = 6 and t = 100000 [PITH_FULL_IMAGE:figures/full_fig_p024_3.png] view at source ↗
Figures from the paper (1 more)
Figure 4
Figure 4. Figure 4: Comparison between LPALG(I,M), V (˜π(I), I, t), OMN(I, t) and LPOMN(I) for 100 simulations with |T | = 10 and t = 100000. 24 [PITH_FULL_IMAGE:figures/full_fig_p024_4.png]

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

17 extracted references · 17 canonical work pages

  1. [1]

    Akbarpour, M., Li, S., and Gharan, S. O. (2020). Thickness and information in dynamic matching markets. Journal of Political Economy , 128(3):783--815

    work page 2020

  2. [2]

    AmaniHamedani, A., Aouad, A., Pollner, T., and Saberi, A. (2024). Improved approximations for stationary bipartite matching: Beyond probabilistic independence. arXiv preprint arXiv:2411.08218

    work page Pith review arXiv 2024

  3. [3]

    and Sar ta c , \"O

    Aouad, A. and Sar ta c , \"O . (2022). Dynamic stochastic matching under limited time. Operations Research , 70(4):2349--2383

    work page 2022

  4. [4]

    Collina, N., Immorlica, N., Leyton-Brown, K., Lucier, B., and Newman, N. (2020). Dynamic weighted matching with heterogeneous arrival and departure rates. In Web and Internet Economics: 16th International Conference, WINE 2020, Beijing, China, December 7--11, 2020, Proceedings 16 , pages 17--30. Springer

    work page 2020

  5. [5]

    G., Wu, X., Zhang, Y., and Zhu, X

    Huang, Z., Kang, N., Tang, Z. G., Wu, X., Zhang, Y., and Zhu, X. (2018). How to match when all vertices arrive online. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of computing , pages 17--29

    work page 2018

  6. [6]

    G., Tao, R., Wu, X., and Zhang, Y

    Huang, Z., Peng, B., Tang, Z. G., Tao, R., Wu, X., and Zhang, Y. (2019). Tight competitive ratios of classic matching algorithms in the fully online model. In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms , pages 2875--2886

    work page 2019

  7. [7]

    G., Wu, X., and Zhang, Y

    Huang, Z., Tang, Z. G., Wu, X., and Zhang, Y. (2020). Fully online matching ii: Beating ranking and water-filling. In 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS) , pages 1380--1391. IEEE

    work page 2020

  8. [8]

    Kerimov, S., Ashlagi, I., and Gurvich, I. (2023). On the optimality of greedy policies in dynamic matching. Operations Research

    work page 2023

Show all 17 references
  1. [9]

    Kerimov, S., Ashlagi, I., and Gurvich, I. (2024). Dynamic matching: Characterizing and achieving constant regret. Management Science , 70(5):2799--2822

    2024

  2. [10]

    Kessel, K., Shameli, A., Saberi, A., and Wajc, D. (2022). The stationary prophet inequality problem. In Proceedings of the 23rd ACM Conference on Economics and Computation , pages 243--244

    2022

  3. [11]

    Kohlenberg, A. (2025). Greedy matching of impatient agents: The role of inventory

    2025

  4. [12]

    Li, Z., Wang, H., and Yan, Z. (2023). Fully online matching with stochastic arrivals and departures. In Proceedings of the AAAI Conference on Artificial Intelligence , volume 37, pages 12014--12021

    2023

  5. [13]

    Pang, G., Talreja, R., and Whitt, W. (2007). Martingale proofs of many-server heavy-traffic limits for markovian queues

    2007

  6. [14]

    and Wajc, D

    Patel, N. and Wajc, D. (2024). Combinatorial stationary prophet inequalities. In Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages 4605--4630. SIAM

    2024

  7. [15]

    and Hern \'a ndez-Lerma, O

    Prieto-Rumeau, T. and Hern \'a ndez-Lerma, O. (2016). Uniform ergodicity of continuous-time controlled markov chains: A survey and new results. Annals of Operations Research , 241:249--293

    2016

  8. [16]

    Wolfe, P. (1963). A technique for resolving degeneracy in linear programming. Journal of the Society for Industrial and Applied Mathematics , 11(2):205--211

    1963

  9. [17]

    Wolff, R. W. (1982). Poisson arrivals see time averages. Operations research , 30(2):223--231

    1982

Pith tools

Reviewed August 6, 2026 · model on record in the stance chip above.