Almost Envy-free Repeated Matching in Two-sided Markets

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 each time step consists of a single match, and our goal is to ensure fairness with respect to the cumulative allocations over an infinite time horizon. We prove several positive results, our main one being that for additive, symmetric ($v_i(j) = v_j(i)$), and binary ($v_i(j) \in \{a,1\}$) valuations, we can simultaneously (1) guarantee \emph{envy-freeness up to a single match} (EF1) and (2) select a maximum weight matching for each ``stage". Thus for this class of valuations, fairness can be achieved without sacrificing efficiency. This result holds even for \emph{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 almost envy-freeness for two-sided preferences.

• Algorithms and Theory

• Economics and Electronic Commerce