Decentralized, Communication- and Coordination-free Learning in Structured Matching Markets
We study the problem of online learning in competitive settings in the
context of two-sided matching markets. In particular, one side of the market,
the agents, must learn about their preferences over the other side, the firms,
through repeated interaction while competing with other agents for successful
matches. We propose a class of decentralized, communication- and
coordination-free algorithms that agents can use to reach to their stable match
in structured matching markets. In contrast to prior works, the proposed
algorithms make decisions based solely on an agent's own history of play and
requires no foreknowledge of the firms' preferences. Our algorithms are
constructed by splitting up the statistical problem of learning one's
preferences, from noisy observations, from the problem of competing for firms.
We show that under realistic structural assumptions on the underlying
preferences of the agents and firms, the proposed algorithms incur a regret
which grows at most logarithmically in the time horizon. Our results show that,
in the case of matching markets, competition need not drastically affect the
performance of decentralized, communication and coordination free online
learning algorithms.