Skip to content
DraconiticResearch
Search Sources API
197,688 studies31 sourcesUpdated 21 min ago
PreprintarXiv licencearXiv

Online Matching with Arbitrary Stochastic Rewards

  • Rajan Udwani
Open at sourcePDFDOICite

Abstract

Online matching with stochastic rewards is a generalization of online bipartite matching in which an attempt to match an online arrival to an offline resource may fail with some probability. Each arrival allows at most one attempt and the success probabilities of its edges are revealed when it arrives. Greedy is 0.5-competitive, which is the best possible for deterministic algorithms. While better competitive ratios are known in several special cases, beating 0.5 for arbitrary probabilities has remained open. We show that, against the adaptive offline benchmark and for arbitrary probabilities, a randomized Perturbed Greedy algorithm is at least 0.591-competitive in the unweighted setting and at least 0.531-competitive with vertex weights. The perturbation functions combine Greedy with scaled versions of the classic exponential function.

Related

  1. Learning to Solve Stochastic Controls with Unknown Drifts and Running Rewards: Theory, Algorithms and Convergence
    Jin Ma, Gaozhan Wang, Jianfeng Zhang +1
    arXivPreprintarXiv licenceFull textNumerical analysis & scientific computingOptimisation & controlarXiv
  2. Optimal Multiclass Online Regret with Arbitrary Label Spaces
    Sajad Ashkezari, Shai Ben-David
    arXivPreprintCC BY 4.0Full textStatisticsarXiv
  3. Robust and Learned Online Matching in Growing Trees
    Marek Gałązka, Hanna Wdowicka
    arXivPreprintCC BY 4.0Full textProbabilityarXiv
  4. Online Non-Monotone DR-Submodular Maximization Matching the Offline $0.401$ Factor
    Vaneet Aggarwal, Yiyang Lu
    arXivPreprintarXiv licenceFull textStatisticsarXiv
  5. Stochastic Gradient Methods with Online Scaling
    Wanyu Zhang, Wenzhi Gao, Yinyu Ye +1
    arXivPreprintCC BY 4.0Full textOptimisation & controlarXiv

Cite

BibTeXRIS
BibTeX
@misc{udwani2026online,
  title = {{Online Matching with Arbitrary Stochastic Rewards}},
  author = {Rajan Udwani},
  howpublished = {arXiv},
  year = {2026},
  month = nov,
  doi = {10.48550/arxiv.2611.03598},
  eprint = {2611.03598},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2611.03598},
}
RIS
TY  - UNPB
TI  - Online Matching with Arbitrary Stochastic Rewards
AU  - Rajan Udwani
PY  - 2026
DA  - 2026/11/02
PB  - arXiv
DO  - 10.48550/arxiv.2611.03598
UR  - https://arxiv.org/abs/2611.03598
AB  - Online matching with stochastic rewards is a generalization of online bipartite matching in which an attempt to match an online arrival to an offline resource may fail with some probability. Each arrival allows at most one attempt and the success probabilities of its edges are revealed when it arrives. Greedy is 0.5-competitive, which is the best possible for deterministic algorithms. While better competitive ratios are known in several special cases, beating 0.5 for arbitrary probabilities has remained open. We show that, against the adaptive offline benchmark and for arbitrary probabilities, a randomized Perturbed Greedy algorithm is at least 0.591-competitive in the unweighted setting and at least 0.531-competitive with vertex weights. The perturbation functions combine Greedy with scaled versions of the classic exponential function.
ER  -