Events

National Center for Supercomputing Applications master calendar

View Full Calendar

NCSA staff who would like to submit an item for the calendar can email newsdesk@ncsa.illinois.edu.

C3.ai DTI Colloquium: Decentralized, Communication- and Coordination-free Learning in Structured Matching Markets

Event Type
Seminar/Symposium
Sponsor
C3.ai Digital Transformation Institute
Date
May 12, 2022   3:00 - 4:00 pm  
Speaker
Chinmay Maheshwari
Registration
Required.
Views
17
Originating Calendar
NCSA-related events

Overview
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 with preferred firms. We propose a class of decentralized, communication- and coordination-free algorithms that agents can use to reach 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 require no foreknowledge of the firms’ preferences. Our algorithms are constructed by splitting up the statistical problem of learning one’s preferences, via noisy observations, from the problem of competing for firms. We present two specific algorithms — one based on Upper Confidence Bounds and other based on Thompson sampling — both of which, under realistic structural assumptions on the underlying preferences of the agents and firms, 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 online learning algorithms.

About the Speaker
Chinmay Maheshwari is pursuing his doctoral studies at the University of California, Berkeley, with Professor Shankar Sastry. Maheshwari received his Bachelor of Technology (B.Tech) and Master of Technology (M.Tech) degrees from the Indian Institute of Technology, Bombay. His research focuses on using tools from game theory, control theory, online learning, and optimization for the design of robust and efficient societal-scale systems comprised of strategic and adversarial entities.

 

link for robots only