Group-level Fairness Maximization in Online Bipartite Matching
Group-level Fairness Maximization in Online Bipartite Matching
复制标题
DOI：
10.5555/3535850.3536077
复制
发表时间：
2020-11
期刊：
影响因子：
--
通讯作者：
Will Ma;Pan Xu
中科院分区：
文献类型：
--
作者：
Will Ma;Pan Xu
在典型的在线匹配问题中，目标是最大化匹配数量。本文从群体层面公平性的角度研究在线双向匹配，目标是平衡不同群体的在线节点之间的匹配数量。我们假设在线节点的组所有物在到达时就会显示，并根据最后匹配的节点的最小部分的组来衡量性能。我们区分两个不同的目标：长期公平性，即在同一实例的许多实现中审核算法的公平性；以及短期公平性，即在单个实现上审核算法的公平性。我们关注在线到达的已知独立同分布模型，并在两个目标下分析两类算法的竞争比：非拒绝算法，只要邻居可用，它就必须匹配在线节点；以及通用在线算法，允许拒绝在线节点以提高公平性。为了长期公平，我们分析了两种在线算法（抽样和池化），它们在许多不同的制度（没有专门的供给、没有罕见的需求类型或不平衡的供需）中建立渐近最优性。相比之下，在所有这些制度之外，我们发现在线算法的竞争比在 0.632 到 0.732 之间。为了短期公平性，我们关注完全二分图的情况，并表明在线算法的竞争比在 0.863 到 0.942 之间；我们还推导出了一种概率拒绝算法，该算法随着总需求的增加而渐近最优。
In typical online matching problems, the goal is to maximize the number of matches. This paper studies online bipartite matching from the perspective of group-level fairness, and the goal is to balance the number of matches made across different groups of online nodes. We assume that an online node's group belongings are revealed upon arrival, and measure performance based on the group with the smallest fraction of its nodes matched at the end. We distinguish between two different objectives: long-run fairness, where the algorithm is audited for its fairness over many realizations from the same instance; and short-run fairness, where the algorithm is audited for its fairness on a single realization. We focus on the known-IID model of online arrivals and analyze, under both objectives, the competitive ratio for two classes of algorithms: non-rejecting algorithms, which must match an online node as long as a neighbor is available; and general online algorithms, which are allowed to reject online nodes to improve fairness. For long-run fairness, we analyze two online algorithms (sampling and pooling) which establish asymptotic optimality across many 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 for online algorithms is between 0.632 and 0.732. For short-run fairness, we focus on the case of a complete bipartite graph and show that the competitive ratio for online algorithms is between 0.863 and 0.942; we also derive a probabilistic rejection algorithm which is asymptotically optimal as total demand increases.