Online Bipartitie Matching was first introduced by Karp, Vazirani and Vazirani (STOC’90). In their seminal paper they had inroduced the RANKING algorithm which admits a tight competitive ratio of 1-1/e. Since then multiple proofs of RANKING have been published. In this talk, we shall look at a simple Game Theoretic approach to proving the competitive ratio of RANKING, avoiding linear programming arguments. The proof is based on the paper by Eden, Feldman, Fiat and Segal (https://arxiv.org/abs/1804.06637).
