  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.
