论文标题
罗尔西亚公平在线二手匹配：双面，小组和个人
Rawlsian Fairness in Online Bipartite Matching: Two-sided, Group, and Individual
论文作者
论文摘要
在线双方匹配平台无处不在，并在众包和乘车共享等重要领域找到应用程序。在最通用的形式中，该平台由三个实体组成：要匹配的两个侧面以及决定匹配的平台操作员。传统上，用于此类平台的算法的设计集中在运营商的（预期）利润上。由于公平性已成为一个重要的考虑因素，在现有算法中被忽略了，因此已经开发了一系列在线匹配算法，为市场的一方提供公平的治疗保证，而牺牲了运营商的利润下降。在本文中，我们将现有的工作概括为同时为市场的两面提供公平的治疗保证，而最坏的情况下则是对运营商的利润。我们考虑团体和个人Rawlsian公平标准。此外，我们的算法具有理论保证，并且具有可调节的参数，可以根据需要调整，以平衡这三个方面的公用事业之间的权衡。我们还得出硬度结果，使任何算法的性能都具有明显的上限。
Online bipartite-matching platforms are ubiquitous and find applications in important areas such as crowdsourcing and ridesharing. In the most general form, the platform consists of three entities: two sides to be matched and a platform operator that decides the matching. The design of algorithms for such platforms has traditionally focused on the operator's (expected) profit. Since fairness has become an important consideration that was ignored in the existing algorithms a collection of online matching algorithms have been developed that give a fair treatment guarantee for one side of the market at the expense of a drop in the operator's profit. In this paper, we generalize the existing work to offer fair treatment guarantees to both sides of the market simultaneously, at a calculated worst case drop to operator profit. We consider group and individual Rawlsian fairness criteria. Moreover, our algorithms have theoretical guarantees and have adjustable parameters that can be tuned as desired to balance the trade-off between the utilities of the three sides. We also derive hardness results that give clear upper bounds over the performance of any algorithm.
