Prophet Inequality for Bipartite Matching: Merits of Being Simple and Nonadaptive
成果类型：
Article
署名作者：
Gravin, Nick; Wang, Hongao
署名单位：
Shanghai University of Finance & Economics; Purdue University System; Purdue University
刊物名称：
MATHEMATICS OF OPERATIONS RESEARCH
ISSN/ISSBN：
0364-765X
DOI：
10.1287/moor.2022.1251
发表日期：
2023
页码：
38-52
关键词：
摘要：
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 prophets 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 non-adaptive 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.