BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//project/author//NONSGML v1.0//EN
CALSCALE:GREGORIAN
BEGIN:VEVENT
DTEND:20220818T120000Z
UID:62c699ad477d02efd66cc9aee6cb2854-315
DTSTAMP:19700101T120018Z
DESCRIPTION:Decentralized Bandits in Matching Markets
URL;VALUE=URI:https://www.csa.iisc.ac.in/newweb/event/315/decentralized-bandits-in-matching-markets/
SUMMARY:In this talk we introduce the problem of decentralized bandits in matching markets, a model inspired by modern recommendation systems. We design algorithms for regret minimization in the two-sided matching market with one-sided bandit feedback. First, for general markets, for any ε>0, we design an algorithm that achieves a O(log1+ε(T)) regret t o the agent-optimal stable matching, with unknown time horizon T. Then, we look at a series of generalized assumptions on the market and provide algorithms that achieve the agent-optimal regret bound of O(log T).

We first start with the canonical serial dictatorship setting with uniform valuations and then extend it to markets satisfying uniqueness consistency -- markets where leaving participants dont alter the original stable matching. We propose a phase-based algorithm, wherein each phase, besides deleting the globally communicated dominated arms the agents locally delete arms with which they collide often. This local deletion is pivotal in breaking deadlocks arising from rank heterogeneity of agents across arms. These phase based algorithms are ideal for deploying in a semi-online/batch setting that are common in large scale production systems.

For more details please visit: https://www.csa.iisc.ac.in/iisc-msr-seminar/


Microsoft teams link:

https://teams.microsoft.com/l/meetup-join/19%3ameeting_ZGE3NDg5NzktMWQ0Zi00MzFmLTg5OTgtMTMyYWM4MWQyYjI2%40thread.v2/0?context=%7b%22Tid%22%3a%226f15cd97-f6a7-41e3-b2c5-ad4193976476%22%2c%22Oid%22%3a%227c84465e-c38b-4d7a-9a9d-ff0dfa3638b3%22%7d
DTSTART:20220818T120000Z
END:VEVENT
END:VCALENDAR