Matching Markets with Bandit Learners: Regret, Stability and Fairness

We consider two-sided matching markets (e.g., Uber, Thumbtack, or Tinder) in which agents must learn their preferences. In this setting, there are agents on opposite sides of the market that seek to be matched. However, contrary to the core assumption of the standard matching literature, in most real-world settings, the agents do not know their true preferences a priori. For example, individuals learn their dating preferences by repeatedly going on dates. To address this assumption, recent works propose to blend the matching and multi-armed bandit problems. They establish that it is possible to assign matchings that are stable (i.e., individually rational) at every time step while also allowing agents to learn enough so that the system converges to matchings that are stable under the agents' true preferences. However, while some agents may incur low regret under these matchings, others can incur high regret -- specifically, Ω(T) optimal regret where T is the time horizon. In this work, we incorporate costs and transfers in the two-sided matching market with bandit learners in order to faithfully model competition between agents. We prove that, under our framework, it is possible to simultaneously guarantee four desiderata: (1) individually rationality, i.e., stability, (2) low regret, i.e., O(log(T)) optimal regret, (3) fairness in the distribution of regret among agents, and (4) high social welfare.

Link: https://arxiv.org/pdf/2102.06246.pdf