Tight Competitive and Variance Analyses of Matching Policies in Gig Platforms

The gig economy features dynamic arriving agents and on-demand services provided. In this context, instant and irrevocable matching decisions are highly desirable due to the low patience of arriving requests. In this paper, we propose an online-matching-based model to tackle the two fundamental issues, matching and pricing, existing in a wide range of real-world gig platforms, including ride-hailing (matching riders and drivers), crowdsourcing markets (pairing workers and tasks), and online recommendations (offering items to customers). Our model assumes the arriving distributions of dynamic agents (e.g., riders, workers, and buyers) are accessible in advance, and they can change over time, which is referred to as Known Heterogeneous Distributions (KHD). In this paper, we initiate variance analysis for online matching algorithms under KHD. Unlike the popular competitive-ratio (CR) metric, the variance of online algorithms' performance is rarely studied due to inherent technical challenges, though it is well linked to robustness. We focus on two natural parameterized sampling policies, denoted by ATT( ) and SAMP( ), which appear as foundational bedrock in online algorithm design. We offer rigorous competitive ratio (CR) and variance analyses for both policies. Specifically, we show that ATT( ) with ∈ [0, 1/2] achieves a CR of and a variance of • (1 -) • on the total number of matches with being the total matching capacity. In contrast, SAMP( ) with ∈ [0, 1] accomplishes a CR of (1 -) and a variance of (1 -) • with = min( , 1/2). All CR and variance analyses are tight and unconditional of any benchmark. As a byproduct, we prove that ATT( = 1/2) achieves an optimal CR of 1/2. CCS CONCEPTS • Theory of computation → Online algorithms; • Applied computing → Marketing.