论文标题
在线双方匹配中的小组级公平最大化
Group-level Fairness Maximization in Online Bipartite Matching
论文作者
论文摘要
我们考虑以有限的资源分配给以在线方式到达的异质客户。我们想“公平地”分配资源，以便没有任何一群客户从其总体服务率方面被边缘化。我们研究是否可以以在线方式进行，如果是这样，那么在线分配政策是什么。 我们使用在固定式Arrivals下的在线双方匹配对这个问题进行建模，这是一种基本模型，通常是根据最大化服务总数的目的而研究的。相反，我们研究了最大化所有组的最低服务率的目的，并提出了两个公平概念：长期和短期。 对于这些公平的目标，我们分析了与离线算法相比，在线算法的竞争性在线算法的情况，这些算法提前知道需求顺序。为了长期公平，我们提出了两种在线启发式方法（采样和汇集），它们在不同的制度（没有专业用品，没有稀有需求类型或不平衡的供应/需求）中建立渐近最优性。相比之下，在所有这些制度之外，我们表明在线算法的竞争比率在0.632至0.732之间。对于短期公平，我们显示完整的两分图表明，在线算法的竞争比率在0.863至0.942之间；我们还得出了一种概率排斥算法，该算法在总需求中渐近最佳。 根据资源的整体稀缺性，我们的抽样或汇总启发式方法是可取的。当总供应足以满足总需求时，在线分配最困难的情况。 我们在公共乘车数据集上模拟了算法，这都证明了我们的启发式方法的功效并验证了我们的管理洞察力。
We consider the allocation of limited resources to heterogeneous customers who arrive in an online fashion. We would like to allocate the resources "fairly", so that no group of customers is marginalized in terms of their overall service rate. We study whether this is possible to do so in an online fashion, and if so, what a good online allocation policy is. We model this problem using online bipartite matching under stationary arrivals, a fundamental model in the literature typically studied under the objective of maximizing the total number of customers served. We instead study the objective of maximizing the minimum service rate across all groups, and propose two notions of fairness: long-run and short-run. For these fairness objectives, we analyze how competitive online algorithms can be, in comparison to offline algorithms which know the sequence of demands in advance. For long-run fairness, we propose two online heuristics (Sampling and Pooling) which establish asymptotic optimality in different regimes (no specialized supplies, no rare demand types, or imbalanced supply/demand). By contrast, outside all of these regimes, we show that the competitive ratio of online algorithms is between 0.632 and 0.732. For short-run fairness, we show for complete bipartite graphs that the competitive ratio of online algorithms is between 0.863 and 0.942; we also derive a probabilistic rejection algorithm which is asymptotically optimal in the total demand. Depending on the overall scarcity of resources, either our Sampling or Pooling heuristics could be desirable. The most difficult situation for online allocation occurs when the total supply is just enough to serve the total demand. We simulate our algorithms on a public ride-hailing dataset, which both demonstrates the efficacy of our heuristics and validates our managerial insights.
