Regret, stability & fairness in matching markets with bandit learners
This addresses the challenge of fair and efficient long-term outcomes for individuals in competitive learning environments, such as career or housing choices, with incremental improvements to existing models.
The paper tackles the problem of competition disrupting learning in two-sided matching markets, showing that by modeling costs and transfers, it is possible to simultaneously guarantee stability, low optimal regret, fairness in regret distribution, and high social welfare, overcoming a previous impossibility result.
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.