extended-abstract

Public Access

Online Stochastic Max-Weight Bipartite Matching: Beyond Prophet Inequalities

Authors:

Christos Papadimitriou,

Tristan Pollner,

Amin Saberi,

David WajcAuthors Info & Claims

EC '21: Proceedings of the 22nd ACM Conference on Economics and Computation

Pages 763 - 764

https://doi.org/10.1145/3465456.3467613

Published: 18 July 2021 Publication History

PDF eReader

Abstract

The rich literature on online Bayesian selection problems has long focused on so-called prophet inequalities, which compare the gain of an online algorithm to that of a "prophet" who knows the future. An equally-natural, though significantly less well-studied benchmark is the optimum online algorithm, which may be omnipotent (i.e., computationally-unbounded), but not omniscient. What is the computational complexity of the optimum online? How well can a polynomial-time algorithm approximate it?

Motivated by applications in ride hailing, we study the above questions for the online stochastic maximum-weight matching problem under vertex arrivals. This problem was recently introduced by Ezra, Feldman, Gravin and Tang (EC'20), who gave a 1/2-competitive algorithm for it. This is the best possible ratio, as this problem is a generalization of the original single-item prophet inequality.

We present a polynomial-time algorithm which approximates optimal online within a factor of 0.51---beating the best-possible prophet inequality. At the core of our result are a new linear program formulation, an algorithm that tries to match the arriving vertices in two attempts, and an analysis that bounds the correlation resulting from the second attempts. In contrast, we show that it is PSPACE-hard to approximate this problem within some constant α < 1.

References

[1]

Anne Condon, Joan Feigenbaum, Carsten Lund, and Peter Shor. 1997. Random debaters and the hardness of approximating stochastic functions. SIAM Journal on Computing (SICOMP), Vol. 26, 2 (1997), 369--400.

Digital Library

Google Scholar

[2]

Tomer Ezra, Michal Feldman, Nick Gravin, and Zhihao Gavin Tang. 2020. Online Stochastic Max-Weight Matching: prophet inequality for vertex and edge arrival models. In Proceedings of the 21st ACM Conference on Economics and Computation (EC). 769--787.

Digital Library

Google Scholar

[3]

Michal Feldman, Nick Gravin, and Brendan Lucier. 2014. Combinatorial auctions via posted prices. In Proceedings of the 26th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 123--135.

Google Scholar

[4]

Amin Saberi and David Wajc. 2021. The Greedy Algorithm is not Optimal for Online Edge Coloring. In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021) .

Google Scholar

[5]

Alfredo Torrico and Alejandro Toriello. 2017. Dynamic Relaxations for Online Bipartite Matching. arXiv preprint arXiv:1709.01557 (2017).

Google Scholar

Cited By

View all

Ezra TReiffenhauser RRusso MTsigonias-Dimitriadis ALeonardi S(2025)Prophet Inequalities via the Expected Competitive RatioACM Transactions on Economics and Computation10.1145/3717076Online publication date: 26-Feb-2025
https://dl.acm.org/doi/10.1145/3717076
Sankararaman KSrinivasan AXu PSalakhutdinov RKolter ZHeller KWeller AOliver NScarlett JBerkenkamp F(2024)Promoting external and internal equities under ex-ante/ex-post metrics in online resource allocationProceedings of the 41st International Conference on Machine Learning10.5555/3692070.3693834(43328-43345)Online publication date: 21-Jul-2024
https://dl.acm.org/doi/10.5555/3692070.3693834
Hayderi ASaberi AVitercik EWikum ASalakhutdinov RKolter ZHeller KWeller AOliver NScarlett JBerkenkamp F(2024)MAGNOLIAProceedings of the 41st International Conference on Machine Learning10.5555/3692070.3692781(17759-17782)Online publication date: 21-Jul-2024
https://dl.acm.org/doi/10.5555/3692070.3692781
Show More Cited By

Index Terms

Online Stochastic Max-Weight Bipartite Matching: Beyond Prophet Inequalities
1. Theory of computation
  1. Design and analysis of algorithms
    1. Online algorithms

Recommendations

Max-Weight Online Stochastic Matching: Improved Approximations Against the Online Benchmark
EC '22: Proceedings of the 23rd ACM Conference on Economics and Computation

In this paper, we study max-weight stochastic matchings on online bipartite graphs under both vertex and edge arrivals. We focus on designing polynomial time approximation algorithms with respect to the online benchmark, which was first considered by ...
Edge-Weighted Online Bipartite Matching
Online bipartite matching is one of the most fundamental problems in the online algorithms literature. Karp, Vazirani, and Vazirani (STOC 1990) gave an elegant algorithm for unweighted bipartite matching that achieves an optimal competitive ratio of 1-1/e ...
Online Stochastic Max-Weight Matching: Prophet Inequality for Vertex and Edge Arrival Models
EC '20: Proceedings of the 21st ACM Conference on Economics and Computation

We provide prophet inequality algorithms for online weighted matching in general (non-bipartite) graphs, under two well-studied arrival models, namely edge arrival and vertex arrival. The weight of each edge is drawn independently from an a-priori known ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

EC '21: Proceedings of the 22nd ACM Conference on Economics and Computation

July 2021

950 pages

ISBN:9781450385541

DOI:10.1145/3465456

General Chair:
Péter Biró
Hungarian Academy of Sciences
,
Program Chairs:
Shuchi Chawla
University of Wisconsin-Madison and University of Texas at Austin
,
Federico Echenique
California Institute of Technology

Permission to make digital or hard copies of part or all of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for third-party components of this work must be honored. For all other uses, contact the Owner/Author.

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 18 July 2021

Check for updates

Author Tags

Qualifiers

Extended-abstract

Funding Sources

Conference

EC '21

Sponsor:

SIGecom

EC '21: The 22nd ACM Conference on Economics and Computation

July 18 - 23, 2021

Budapest, Hungary

Acceptance Rates

Overall Acceptance Rate 664 of 2,389 submissions, 28%

Upcoming Conference

EC '25

Sponsor:
sigecom

The 25th ACM Conference on Economics and Computation

July 7 - 11, 2025

Stanford , CA , USA

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

21
Total Citations
View Citations
486
Total Downloads

Downloads (Last 12 months)235
Downloads (Last 6 weeks)74

Reflects downloads up to 09 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

Ezra TReiffenhauser RRusso MTsigonias-Dimitriadis ALeonardi S(2025)Prophet Inequalities via the Expected Competitive RatioACM Transactions on Economics and Computation10.1145/3717076Online publication date: 26-Feb-2025
https://dl.acm.org/doi/10.1145/3717076
Sankararaman KSrinivasan AXu PSalakhutdinov RKolter ZHeller KWeller AOliver NScarlett JBerkenkamp F(2024)Promoting external and internal equities under ex-ante/ex-post metrics in online resource allocationProceedings of the 41st International Conference on Machine Learning10.5555/3692070.3693834(43328-43345)Online publication date: 21-Jul-2024
https://dl.acm.org/doi/10.5555/3692070.3693834
Hayderi ASaberi AVitercik EWikum ASalakhutdinov RKolter ZHeller KWeller AOliver NScarlett JBerkenkamp F(2024)MAGNOLIAProceedings of the 41st International Conference on Machine Learning10.5555/3692070.3692781(17759-17782)Online publication date: 21-Jul-2024
https://dl.acm.org/doi/10.5555/3692070.3692781
Ezra TFeldman MTang ZKleinberg RSaban DBergemann D(2024)Choosing Behind the Veil: Tight Bounds for Identity-Blind Online AlgorithmsProceedings of the 25th ACM Conference on Economics and Computation10.1145/3670865.3673620(136-158)Online publication date: 8-Jul-2024
https://dl.acm.org/doi/10.1145/3670865.3673620
Chen LSun NTang ZKleinberg RSaban DBergemann D(2024)Setting Targets is All You Need: Improved Order Competitive Ratio for Online SelectionProceedings of the 25th ACM Conference on Economics and Computation10.1145/3670865.3673487(263-277)Online publication date: 8-Jul-2024
https://dl.acm.org/doi/10.1145/3670865.3673487
Ekbatani FNiazadeh RNuti PVondrák JMohar BShinkar IO'Donnell R(2024)Prophet Inequalities with Cancellation CostsProceedings of the 56th Annual ACM Symposium on Theory of Computing10.1145/3618260.3649786(1247-1258)Online publication date: 10-Jun-2024
https://dl.acm.org/doi/10.1145/3618260.3649786
Chen ZHuang ZSun E(2024)Stochastic Online Correlated Selection2024 IEEE 65th Annual Symposium on Foundations of Computer Science (FOCS)10.1109/FOCS61266.2024.00133(2275-2294)Online publication date: 27-Oct-2024
https://doi.org/10.1109/FOCS61266.2024.00133
Hathcock DJin BPatton KSarkar SZlatin M(2024)The Online Submodular Assignment Problem2024 IEEE 65th Annual Symposium on Foundations of Computer Science (FOCS)10.1109/FOCS61266.2024.00026(291-313)Online publication date: 27-Oct-2024
https://doi.org/10.1109/FOCS61266.2024.00026
DeHaan IPashkovich K(2024)Matroid Bayesian Online SelectionAlgorithmic Game Theory10.1007/978-3-031-71033-9_23(405-422)Online publication date: 3-Sep-2024
https://dl.acm.org/doi/10.1007/978-3-031-71033-9_23
Chen YKanoria YKumar AZhang W(2023)Feature Based Dynamic MatchingSSRN Electronic Journal10.2139/ssrn.4451799Online publication date: 2023
https://doi.org/10.2139/ssrn.4451799
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Index Terms

Recommendations

Max-Weight Online Stochastic Matching: Improved Approximations Against the Online Benchmark

Edge-Weighted Online Bipartite Matching

Online Stochastic Max-Weight Matching: Prophet Inequality for Vertex and Edge Arrival Models