Regret, stability & fairness in matching markets with bandit learners
  Making an informed decision -- for example, when choosing a career or housing
-- requires knowledge about the available options. Such knowledge is generally
acquired through costly trial and error, but this learning process can be
disrupted by competition. In this work, we study how competition affects the
long-term outcomes of individuals as they learn. We build on a line of work
that models this setting as a two-sided matching market with bandit learners. A
recent result in this area states that it is impossible to simultaneously
guarantee two natural desiderata: stability and low optimal regret for all
agents. Resource-allocating platforms can point to this result as a
justification for assigning good long-term outcomes to some agents and poor
ones to others. We show that this impossibility need not hold true. In
particular, by modeling two additional components of competition -- namely,
costs and transfers -- we prove that it is possible to simultaneously guarantee
four desiderata: stability, low optimal regret, fairness in the distribution of
regret, and high social welfare.
