Matching Markets with Bandit Learners: Regret, Stability and Fairness

Wednesday, May 5, 2021 - 4:00pm to 4:30pm

Event Calendar Category

LIDS & Stats Tea

Speaker Name

Sarah Cen

Affiliation

LIDS

Zoom meeting id

969 2085 4406

Join Zoom meeting

https://mit.zoom.us/j/96920854406

Abstract

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

Biography

Sarah is a Ph.D. student in EECS at MIT, advised by Prof. Devavrat Shah. Her research uses tools from mathematical statistics and microeconomics to study the interaction between humans and machine learning algorithms. Topics she is currently working on include social media, market design, and individual fairness. Sarah has previously performed research in intelligent transportation, communication networks, reinforcement learning, and robotics. During her master's, she performed research on autonomous vehicles (a.k.a. self-driving cars) with Prof. Paul Newman at the University of Oxford. As an undergraduate, she studied control & decision systems with Prof. Naomi Leonard at Princeton University.