Center for Social Information Sciences (CSIS) Seminar

Abstract: Matching markets arise in many domains like online advertising and delivery and ride-sharing services, yet many algorithms require agents to know their preferences over all of their matches. Recently, there has been much interest in designing algorithms for learning while matching, i.e., algorithms through which agents can simultaneously learn about their preferences while ensuring that they consistently get their best match possible. So far, all algorithms for such settings are either centralized--with one platform ultimately doing the matching-- or encode communication tacitly into the algorithm design. In this talk I will discuss the necessary building blocks for decentralized, coordination-free algorithms for learning while matching. I will show how using this blueprint for algorithm design results in algorithms with convergence guarantees in matching markets, and how one can achieve optimal convergence rates in structured matching markets.