There are growing concerns that algorithms, which increasingly make or influence important decisions pertaining to individuals, might produce outcomes that discriminate against protected groups. We study such fairness concerns in the context of a two-sided market, where there are two sets of agents, and each agent has preferences over the other set. The goal is producing a matching between the sets. This setting has been the focus of a rich body of work. The seminal work of Gale and Shapley formulated a stability desideratum, and showed that a stable matching always exists and can be found efficiently. We study this question through the lens of metric-based fairness notions (Dwork et al., Kim et al.). We formulate appropriate definitions of fairness and stability in the presence of a similarity metric, and ask: does a fair and stable matching always exist? Can such a matching be found in polynomial time? Our contributions are as follows: (1) Composition failures for classical algorithms: We show that composing the Gale-Shapley algorithm with fair hospital preferences can produce blatantly unfair outcomes. (2) New algorithms for finding fair and stable matchings: Our main technical contributions are efficient new algorithms for finding fair and stable matchings when: (i) the hospitals' preferences are fair, and (ii) the fairness metric satisfies a strong "proto-metric" condition: the distance between every two doctors is either zero or one. In particular, these algorithms also show that, in this setting, fairness and stability are compatible. (3) Barriers for finding fair and stable matchings in the general case: We show that if the hospital preferences can be unfair, or if the metric fails to satisfy the proto-metric condition, then no algorithm in a natural class can find a fair and stable matching. The natural class includes the classical Gale-Shapley algorithms and our new algorithms.
翻译:越来越多的人担心,日益产生或影响与个人相关的重要决定的算法可能会产生歧视受保护群体的结果。 我们从双面市场的角度研究这种公平问题, 即存在两组代理商, 每个代理商都优于另一组。 目标是在各组之间产生匹配。 这个设置是丰富工作的重点。 Gale 和 Shapley 的开创性工作形成了一种稳定性, 并表明, 稳定地匹配总是存在, 并且可以有效地找到。 我们通过基于标准的公平概念( Dwork et al., Kim et al.) 的透镜来研究这一问题。 我们在存在类似性指标的情况下, 研究公平性和稳定性的适当定义, 并询问: 公平与稳定的匹配总是存在吗? 这样的匹配能否在一个丰富的工作体系中找到? 我们的贡献如下:(1) 谷-Shapley的算法失败: 我们把具有公平性医院偏好选择的Gal- Shaply算法可以产生明显的不公平的结果。 (2) 找到公平与稳定的匹配的新算法: 我们的主要技术贡献, 也就是一个持续的算法, 正确性, 当找到一个稳定的医院和正确性, 一种正常的正确性, 当一种稳定的, 一种稳定的, 一种稳定的, 一种正常的, 一种正常的算法则, 显示一种正常的。