A Unified Model for Bi-objective Online Stochastic Bipartite Matching with Two-sided Limited Patience

Bi-objective online stochastic bipartite matching can capture a wide range of real-world problems such as online ride-hailing, crowdsourcing markets, and internet adverting, where the vertices in the left side are known in advance and that in the right side arrive from a known identical independent distribution (KIID) in an online manner. Mutual interest and limited attention-span are two common conditions and can be modeled as the edge existence probability and two-sided limited patience. Existing works fail to take them into bi-objective online optimization. This paper establishes a unified model for bi-objective online stochastic bipartite matching that can provide a general tradeoff among the matched edges (OBJ-1) and vertices (OBJ-2). We formulate two linear programs (LP) and accordingly design four LP-based parameterized online algorithms to tradeoff OBJ-1 and OBJ-2, with the best competitive ratio of (0.3528α, 0.3528β), where α, β are two positive input parameters and α + β = 1. Our hardness analysis proves that any non-adaptive algorithm cannot achieve (δ1, δ2)-competitive such that ${\delta _1} + {\delta _2} > 1 - \frac{1}{e}$. Trace-driven experiments show that our algorithms can always achieve better performance and provide a flexible tradeoff.