Incentivized Exploration in Two-Sided Matching Markets

Abstract

We study incentivized exploration (IE) in centralized two-sided matching markets where all agents and arms are myopic human decision-subjects with preferences over their potential matches. The platform can leverage information asymmetry to encourage all sequentially arriving agents and arms to explore alternative options. In particular, we use inverse-gap weighting, a technique studied in reinforcement learning and contextual bandits, as the theoretical underpinning for our novel recommendation policy. We obtain the first set of results for incentivized exploration in two-sided matching markets with dual incentive-compatibility constraints and asymptotically match the regret guarantee for combinatorial semi-bandits.