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. Recent reports have shown that certain demographic groups may receive less favorable treatment under pure profit maximization. As a result, 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.
翻译:在线双向匹配平台无处不在,在诸如众包和搭车共享等重要领域都能找到应用。 最一般的形式是,平台由三个实体组成: 双方相匹配, 由平台操作员决定匹配。 这些平台的算法的设计传统上侧重于运营商(预期)的利润。 最近的报告显示,某些人口群体在纯利润最大化下可能得到不那么有利的待遇。 结果, 开发了一系列在线匹配算法, 为市场一方提供了公平待遇保障, 以降低运营商利润的下降为代价。 在本文中, 我们将现有的工作推广为市场双方同时提供公平待遇保障, 以计算出最差的情况, 向运营商利润下降。 我们考虑群体和个人Rawlsian公平标准。 此外, 我们的算法有理论保障, 并有可调整的参数, 以平衡三方公用事业之间的交易。 我们还得出硬性结果, 使任何算法的绩效都有明确的上限 。