Promoting Fairness Among Dynamic Agents in Online-Matching Markets under Known Stationary Arrival Distributions

Abstract

Online (bipartite) matching under known stationary arrivals is a fundamental model that has been studied extensively with the objective of maximizing the total number of customers served. We instead study the objective of maximizing the minimum matching rate across all online types , which is referred to as long-run (individual) fairness. For Online Matching under long-run Fairness (OM-LF) with a single offline agent, we show that the first-come-first-serve (FCFS) policy is 1 -competitive, i.e., matching any optimal clairvoyant. For the general case of OM-LF: We present a sampling algorithm (SAMP) and show that (1) SAMP is of competitiveness of at least 1 − 1 /e and (2) it is asymptotically optimal with competitiveness approaching one in different regimes when either all offline agents have a sufficiently large matching capacity, or all online types have a sufficiently large arrival rate, or highly imbalance between the total offline matching capacity and the number of online arrivals. To complement the competitive results, we show the following hardness results for OM-LF: (1) Any non-rejecting policy (matching every arriving online agent if possible) is no more than 1 / 2 -competitive; (2) Any (randomized) policy is no more than ( √ 3 − 1) -competitive; (3) SAMP can be no more than (1 − 1 /e ) - competitive suggesting the tightness of competitive analysis for SAMP. We stress that all hardness results mentioned here are independent of any benchmarks. We also consider a few extensions of OM-LF by proposing a few variants of fairness metrics, including long-run group-level fairness and short-run fairness, and we devise related algorithms with provable competitive performance.