Prophet Inequality for Bipartite Matching: Merits of Being Simple and Nonadaptive

Nick Gravin () and Hongao Wang ()
Additional contact information
Nick Gravin: Institute for Theoretical Computer Science, School of Information Management and Engineering, Shanghai University of Finance and Economics, Shanghai 200433, China
Hongao Wang: Department of Computer Science, Purdue University, West Lafayette, Indiana 47907

Mathematics of Operations Research, 2023, vol. 48, issue 1, 38-52

Abstract: We consider the Bayesian online selection problem of a matching in bipartite graphs, that is, the weighted online matching problem where the edges arrive online and edge weights are generated from a known distribution. This setting corresponds to the intersection of two matroids in the work of Kleinberg and Weinberg [ 40 ] and Feldman et al. [ 27 ]. We study a simple class of nonadaptive policies that we call vertex-additive policies. A vertex-additive policy assigns static prices to every vertex in the graph and accepts only those edges whose weight exceeds the sum of the prices on the edge endpoints. We show that there exists a vertex-additive policy with the expected payoff of at least one-third of the prophet’s payoff and present a gradient descent algorithm that quickly converges to the desired vector of vertex prices. Our results improve on the adaptive online policies of Kleinberg and Weinberg and Feldman et al. for the intersection of two matroids in two ways: our policy is nonadaptive and has a better approximation guarantee of 3 instead of the previous guarantees of 5.82 in Kleinberg and Weinberg and 5.43 in Feldman et al. We give a complementary lower bound of 2.25 for any online algorithm in the bipartite matching setting.

Keywords: Primary: 68W27; secondary: 90C27; 68Q87; prophet inequality; online matching; edge arrivals; nonadaptive thresholds (search for similar items in EconPapers)
Date: 2023
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/moor.2022.1251 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ormoor:v:48:y:2023:i:1:p:38-52

Access Statistics for this article

More articles in Mathematics of Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().