论文标题
在双面市场中几乎无嫉妒的重复匹配
Almost Envy-free Repeated Matching in Two-sided Markets
论文作者
论文摘要
一个双面市场由两组代理组成，每个代理都有对另一组偏好（Airbnb，Upwork，Lyft，Uber等）。我们提出和分析一个重复的匹配问题，在每个时间步骤中都会发生一组匹配，我们的目标是确保在无限时间范围内对累积分配的公平性。我们的主要结果是用于添加剂，对称（v_i（j）= v_j（i））的多项式时间算法和二进制（v_i（j）\ in \ {a，1 \}）的二进制（1）保证“嫉妒”的估值“（1）可以保证“（ef1）和（2）的最大体重匹配，请选择“（ef1）和（2）”。因此，对于这类估值，可以在不牺牲经济效率的情况下实现公平性。该结果甚至具有“动态估值”，即随着时间的流逝而变化的估值。尽管对称性是一个有力的假设，但我们表明，该结果不能扩展到不对称的二元估值：（1）和（2）即使估值不会随着时间的推移而变化，并且对于动态估值也是不可能的，即使（1）仅是不可能的。据我们所知，这是对重复匹配设置中嫉妒性的首次分析。
A two-sided market consists of two sets of agents, each of whom have preferences over the other (Airbnb, Upwork, Lyft, Uber, etc.). We propose and analyze a repeated matching problem, where some set of matches occur on each time step, and our goal is to ensure fairness with respect to the cumulative allocations over an infinite time horizon. Our main result is a polynomial-time algorithm for additive, symmetric (v_i(j) = v_j(i)), and binary (v_i(j) \in \{a,1\}) valuations that both (1) guarantees "envy-freeness up to a single match" (EF1) and (2) selects a maximum weight matching on each time step. Thus for this class of valuations, fairness can be achieved without sacrificing economic efficiency. This result holds even for "dynamic valuations", i.e., valuations that change over time. Although symmetry is a strong assumption, we show that this result cannot be extended to asymmetric binary valuations: (1) and (2) together are impossible even when valuations do not change over time, and for dynamic valuations, even (1) alone is impossible. To our knowledge, this is the first analysis of envy-freeness in a repeated matching setting.
