An Economic-Based Analysis of RANKING for Online Bipartite Matching

In their seminal paper, Karp, Vazirani and Vazirani (STOC’90) introduce the online bipartite matching problem, and the RANKING algorithm, which admits a tight $1-\frac{1}{e}$ competitive ratio. Since its publication, the problem has received considerable attention, including a sequence of simplified proofs. In this paper we present a new proof that gives an economic interpretation of the RANKING algorithm – further simplifying the proof and avoiding arguments such as duality. The new proof gives a new perspective on previous proofs.