An Economics-Based Analysis of RANKING for Online Bipartite Matching
Alon Eden, Michal Feldman, Amos Fiat, Kineret Segal · Society for Industrial and Applied Mathematics eBooks · 2021
In their seminal paper, Karp, Vazirani and Vazirani (STOC'90) introduce the online bipartite matching problem, and the RANKING algorithm, which admits a tight 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.