Computer Science/Discrete Mathematics Seminar I

Over the last three decades, the online bipartite matching (OBM) problem has emerged as a central problem in the area of Online Algorithms. Perhaps even more important is its role in the area of Matching-Based Market Design.  The resurgence of this area, with the revolutions of the Internet and mobile computing, has opened up novel, path- breaking applications, and OBM has emerged as its paradigmatic algorithmic problem.  In a 1990 joint paper with Richard Karp and Umesh Vazirani, we gave an optimal algorithm, called RANKING, for OBM, achieving a competitive ratio of (1 – 1/e); however, its analysis was difficult to comprehend. Over the years, several researchers simplified the analysis.  We will start by presenting a “textbook quality” proof of RANKING. Its simplicity raises the possibility of extending RANKING all the way to a generalization of OBM called the adwords problem.  This problem is both notoriously difficult and very significant, the latter because of its role in the AdWords marketplace of Google.  We will show how far this endeavor has gone and what remains.  We will also provide a broad overview of the area of Matching-Based Market Design and pinpoint the role of OBM.

Based on: https://arxiv.org/pdf/2107.10777.pdf