论文标题
在线匹配中的班级公平
Class Fairness in Online Matching
论文作者
论文摘要
在经典版本的在线双方匹配中，有一组给定的离线顶点（又称代理）和另一组在线到达的顶点（又称项目）。当每个项目到达时，其事件边缘 - 喜欢该物品的代理 - 被揭示，并且该算法必须不可撤销地将项目与此类代理相匹配。我们在此环境中启动阶级公平性的研究，在该环境中，代理被分配到一组类中，并且需要相对于课程公平。我们采用公平分裂文献中的普遍公平概念，例如嫉妒（最多一个项目），相称性和最大值与我们的环境共同。这些概念的班级版本要求所有班级，无论其大小如何都得到公平的待遇。我们研究了匹配不可分割的项目（导致积分匹配）和匹配可分割项目（导致分数匹配）的确定性和随机算法。我们设计和分析了三种新型算法。对于匹配不可分割的项目，我们提出了一种基于自适应的算法，匹配和换档，证明它可以实现1/2的同时嫉妒性，最多可达到一项and class maximin and Maximin共享公平性，并显示每种保证都很紧张。对于可分配的项目，我们设计了一种基于水的算法，相等的填充算法，可以实现（1-1/e） - 阶级嫉妒性和阶级比例的应用；我们证明（1-1/e）对于班级比例性要紧张，并建立了3/4的上限，以嫉妒性嫉妒。最后，我们基于等同填充，以设计一种随机算法，用于匹配不可分割的项目，即Eqaul填充ocs，该算法实现了班级比例的0.593-相关性。该算法及其分析至关重要地利用了最近引入的在线相关选择技术（OCS）[Fahrbach等，2020]。
In the classical version of online bipartite matching, there is a given set of offline vertices (aka agents) and another set of vertices (aka items) that arrive online. When each item arrives, its incident edges -- the agents who like the item -- are revealed and the algorithm must irrevocably match the item to such agents. We initiate the study of class fairness in this setting, where agents are partitioned into a set of classes and the matching is required to be fair with respect to the classes. We adopt popular fairness notions from the fair division literature such as envy-freeness (up to one item), proportionality, and maximin share fairness to our setting. Our class versions of these notions demand that all classes, regardless of their sizes, receive a fair treatment. We study deterministic and randomized algorithms for matching indivisible items (leading to integral matchings) and for matching divisible items (leading to fractional matchings). We design and analyze three novel algorithms. For matching indivisible items, we propose an adaptive-priority-based algorithm, MATCH-AND-SHIFT, prove that it achieves 1/2-approximation of both class envy-freeness up to one item and class maximin share fairness, and show that each guarantee is tight. For matching divisible items, we design a water-filling-based algorithm, EQUAL-FILLING, that achieves (1-1/e)-approximation of class envy-freeness and class proportionality; we prove (1-1/e) to be tight for class proportionality and establish a 3/4 upper bound on class envy-freeness. Finally, we build upon EQUAL-FILLING to design a randomized algorithm for matching indivisible items, EQAUL-FILLING-OCS, which achieves 0.593-approximation of class proportionality. The algorithm and its analysis crucially leverage the recently introduced technique of online correlated selection (OCS) [Fahrbach et al., 2020].
