CaltechAUTHORS
  A Caltech Library Service

Decentralized, Communication- and Coordination-free Learning in Structured Matching Markets

Maheshwari, Chinmay and Mazumdar, Eric and Sastry, Shankar (2022) Decentralized, Communication- and Coordination-free Learning in Structured Matching Markets. . (Unpublished) https://resolver.caltech.edu/CaltechAUTHORS:20220715-171641949

[img] PDF - Submitted Version
See Usage Policy.

2MB

Use this Persistent URL to link to this item: https://resolver.caltech.edu/CaltechAUTHORS:20220715-171641949

Abstract

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.


Item Type:Report or Paper (Discussion Paper)
Related URLs:
URLURL TypeDescription
https://doi.org/10.48550/arXiv.2206.02344arXivDiscussion Paper
ORCID:
AuthorORCID
Mazumdar, Eric0000-0002-1815-269X
Additional Information:Research was partially supported by NSF under grant DMS 2013985 THEORINet: Transferable, Hierarchical, Expressive, Optimal, Robust and Interpretable Networks and U.S. Office of Naval Research MURI grant N00014-16-1- 2710.
Funders:
Funding AgencyGrant Number
NSFDMS-2013985
Office of Naval Research (ONR)N00014-16-1-2710
Record Number:CaltechAUTHORS:20220715-171641949
Persistent URL:https://resolver.caltech.edu/CaltechAUTHORS:20220715-171641949
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:115619
Collection:CaltechAUTHORS
Deposited By: George Porter
Deposited On:15 Jul 2022 23:31
Last Modified:15 Jul 2022 23:31

Repository Staff Only: item control page