An Economic-Based Analysis of RANKING for Online Bipartite Matching

Alon Eden, Michal Feldman, Amos Fiat, Kineret SegalarXiv 2018 · arXiv

Abstract

This paper provides a simplified, intuitive proof for the $1 - 1/e$ competitive ratio of the RANKING algorithm in online bipartite matching. By re-interpreting the algorithm through the lens of a market process, the authors replace traditional linear programming duality with economic arguments. In this model, incoming vertices are treated as utility-maximizing buyers and fixed vertices as priced items. This perspective clarifies the underlying mechanics of the algorithm and demonstrates that the competitive ratio emerges naturally from the decomposition of social welfare into buyer utility and seller revenue.

1. Introduction

The Online Bipartite Matching problem is a fundamental challenge in combinatorial optimization with significant applications in internet advertising, such as matching real-time search queries to a fixed set of advertisers. In the standard model, a set of "right" vertices ($R$) is known in advance, while "left" vertices ($L$) arrive sequentially. Upon arrival, each left vertex must be immediately and irrevocably matched to an available neighbor in $R$ or left unmatched. The objective is to maximize the size of the final matching.

In 1990, Karp, Vazirani, and Vazirani introduced the RANKING algorithm, which achieves a competitive ratio of $1 - 1/e \approx 0.632$. While this result is a cornerstone of online algorithm theory, the original proof was notoriously complex. Subsequent simplifications utilized Linear Programming (LP) duality, which, while effective, often lacks intuitive clarity. This paper proposes a "human-readable" alternative by framing the problem as an economic market.

2. The Market Process Model

The authors analyze the RANKING algorithm by mapping it to a market process with the following characteristics:

  • Items and Buyers: The fixed right vertices ($R$) are treated as items for sale. The incoming left vertices ($L$) are unit-demand buyers who seek to purchase exactly one item.
  • Random Pricing: Before the arrival of any buyers, each item $r_j \in R$ is assigned a random price $p_j$. This price is determined by drawing a value $w_j$ uniformly from $[0, 1]$ and setting $p_j = e^{w_j-1}$.
  • Utility Maximization: When a buyer $\ell_i$ arrives, they evaluate all currently available items to which they have an edge. The buyer selects the item that maximizes their utility, defined as $Value - Price$. Given that all items have a uniform value of 1 to a connected buyer, the buyer simply selects the available neighbor with the lowest price.

The authors demonstrate that this market process is mathematically equivalent to the RANKING algorithm. In RANKING, right vertices are assigned a random permutation (rank), and incoming vertices match with their highest-ranked available neighbor. In the economic model, the "lowest price" serves the same function as the "highest rank."

3. Key Insights and Analysis

The strength of this economic approach lies in how it decomposes the value of the matching. In this model, the total social welfare (the sum of values obtained by all buyers) is exactly equal to the size of the matching produced by the algorithm.

3.1 Value Decomposition

The proof hinges on dividing the value of each match into two components:

  1. Buyer Utility: The surplus gained by the buyer (1 - price).
  2. Seller Revenue: The price collected by the item (the right vertex).

By comparing a market containing an item $r_j$ to a hypothetical market where $r_j$ is absent, the authors analyze the expected contribution of each edge in the optimal matching. They show that for any edge $(l_i, r_j)$ in the optimal offline matching, the expected sum of the buyer's utility and the item's revenue is at least $1 - 1/e$.

3.2 The "Aha!" Moment

Summing these expected values over all edges in the optimal matching leads directly to the $1 - 1/e$ bound. This approach effectively bypasses the need to explicitly construct a dual program or prove its feasibility. Instead, the competitive ratio is shown to be a direct consequence of the chosen price distribution ($e^{w-1}$), which balances the trade-off between buyer utility and seller revenue across the random draws.

4. Discussion and Limitations

This work is primarily a theoretical re-analysis. It does not improve upon the $1 - 1/e$ limit, which is already known to be the optimal competitive ratio for any randomized online algorithm in this setting. Furthermore, the current proof focuses on the standard bipartite matching problem and does not immediately extend to more complex variations, such as vertex-weighted matching or general capacity constraints.

However, the pedagogical value is significant. By providing a transparent, economic intuition for a seminal result, the authors offer a framework that may make future extensions to more complex matching problems more accessible. The "RANKING as a Market" perspective suggests that many abstract dual variables in online optimization can be interpreted as prices in a hidden economy.

5. Conclusion

The economic-based analysis of the RANKING algorithm provides a refreshing simplification of a classic result. By framing the problem as a market of utility-maximizing buyers, the authors provide a clear, intuitive path to the $1 - 1/e$ competitive ratio, making the logic of online bipartite matching more transparent to the broader computer science community.

Summary updated

Abstract

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.
BibTeX
@misc{eden2018economic,
  author = {Alon Eden and Michal Feldman and Amos Fiat and Kineret Segal},
  title = {{An Economic-Based Analysis of RANKING for Online Bipartite Matching}},
  year = {2018},
  eprint = {1804.06637},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1804.06637},
}
Figure