Edge-weighted Online Stochastic Matching: Beating $1-\frac1e$

Basic Information

• Paper ID: 2210.12543
• Title: Edge-weighted Online Stochastic Matching: Beating $1-\frac1e$
• Author: Shuyi Yan (Department of Computer Science, University of Copenhagen)
• Categories: cs.DS (Data Structures and Algorithms), cs.GT (Game Theory)
• Publication Date: April 8, 2025 (arXiv preprint version 3)
• Paper Link: https://arxiv.org/abs/2210.12543

Abstract

This paper investigates the edge-weighted online stochastic matching problem. Since Feldman et al. proposed the Suggested Matching algorithm with a $(1-\frac1e)$-competitive ratio, there has been no improvement on the general edge-weighted online stochastic matching problem. This paper presents the first algorithm to break the $1-\frac1e$ barrier, achieving a competitive ratio of 0.645. Based on the linear programming formulation proposed by Jaillet and Lu, we design an algorithmic preprocessing that partitions all edges into two classes. Building upon the Suggested Matching algorithm, we adjust the matching strategy to improve performance for one class of edges in the early stage and for the other class in the late stage, while maintaining high independence among matching events across different edges. By balancing these operations, we guarantee the matching probability for each edge.

Research Background and Motivation

Problem Importance

The online bipartite matching problem, introduced by Karp et al. in 1990, has played an important role in the online algorithms field. Its most significant application is online advertising: when users search on search engines, appropriate advertisements must be selected for display. In this problem, advertisers are modeled as offline vertices (known at the start of the algorithm), and impressions (user searches) are modeled as online vertices (arriving one by one).

Limitations of Existing Methods

1. Worst-case Model: Karp et al.'s Ranking algorithm achieves a competitive ratio of $1-\frac1e \approx 0.632$ for unweighted matching and proves its optimality.
2. Online Stochastic Matching Model: The Suggested Matching algorithm proposed by Feldman et al. still only achieves a competitive ratio of $1-\frac1e$ in the general edge-weighted setting.
3. Improvements in Special Cases: While improvements have been achieved in special cases such as vertex-weighted matching and edge-weighted matching with free disposal, the general edge-weighted setting lacks these useful properties.

Research Motivation

The general edge-weighted setting is inherently more difficult because:

• Light edges may occupy offline vertices, preventing heavy edges from matching in the future
• Good competitive ratios cannot be simply obtained by lower-bounding the matching probability of each vertex or edge
• An upper bound of 0.703 indicates that this setting is indeed more difficult than special cases

Core Contributions

1. First Breakthrough of the $1-\frac1e$ Barrier: Proposes a polynomial-time algorithm with a competitive ratio of 0.645 for the general edge-weighted online stochastic matching problem
2. Innovative Preprocessing Technique: Designs preprocessing based on the Jaillet-Lu linear programming that partitions edges into two classes and simplifies the problem structure
3. Multi-stage Matching Strategy: Proposes the Multistage Suggested Matching algorithm that employs different strategies at different stages to optimize performance
4. Independence-Preserving Analysis: Develops an analytical framework that maintains high independence among matching events across different edges

Methodology Details

Problem Definition

Input:

• Set of online vertex types $I$ and set of offline vertices $J$
• Edge set $E = \{(i,j) : i \in I, j \in J_i\}$, where each edge $(i,j)$ has non-negative weight $w_{ij}$
• Arrival rate $\lambda_i$ for each online vertex type $i$

Process: Online vertices arrive according to a Poisson process, with each vertex independently selecting type $i$ with probability $\frac{\lambda_i}{\Lambda}$

Objective: Maximize the expected total weight of all matched edges

Core Technical Framework

1. Jaillet-Lu Linear Programming

Uses an improved linear programming to bound the offline optimal solution:

maximize ∑_{(i,j)∈E} w_{ij}x_{ij}
subject to:
∑_j x_{ij} ≤ λ_i  ∀i ∈ I
∑_i x_{ij} ≤ 1   ∀j ∈ J  
∑_i (2x_{ij} - λ_i)^+ ≤ 1 - ln 2  ∀j ∈ J
x_{ij} ≥ 0  ∀(i,j) ∈ E

2. Preprocessing Technique

Theorem 2: Any solution to the Jaillet-Lu linear programming can be transformed into an equivalent fractional matching satisfying:

• $\forall i \in I, x_i = λ_i$ (Constraint 2)
• $\forall j \in J, x_j = 1$ (Constraint 3)
• $\forall (i,j) ∈ E, x_{ij} \in \{0, \frac{1}{2}λ_i, λ_i\}$ (Constraint 4)

This partitions edges into two classes:

• Class 1 Edges: $x_{ij} = λ_i$ (online vertex type matches exactly one offline vertex)
• Class 2 Edges: $x_{ij} = \frac{1}{2}λ_i$ (online vertex type matches two offline vertices, each with probability $\frac{1}{2}$)

Model Architecture: Multistage Suggested Matching

The algorithm is divided into three temporal stages:

Stage 1 ($0 ≤ t ≤ t_0$):

• Class 1 vertices: Match to unique neighbor (if unmatched)
• Class 2 vertices: Discard directly

Stage 2 ($t_0 < t ≤ t_1$):

• Class 1 vertices: Match to unique neighbor (if unmatched)
• Class 2 vertices: Match to each unmatched neighbor with probability $\frac{1}{2}$

Stage 3 ($t_1 < t ≤ 1$):

• Class 1 vertices: Match to unique neighbor (if unmatched)
• Class 2 vertices:
  • If only one neighbor is unmatched at time $t_1$, match to that neighbor
  • Otherwise, match to each unmatched neighbor with probability $\frac{1}{2}$

Technical Innovations

1. Time-Segmented Strategy:
   • Sacrifice Class 2 edges early to improve matching probability of Class 1 edges
   • Adjust Class 2 edge strategy in later stages based on observed state
2. Independence Maintenance:
   • Observe offline vertex state only once at time $t_1$
   • Maintain high independence among matching events across different edges
3. Probabilistic Analysis:
   • Independently lower-bound the unmatched probability of each offline vertex at any time
   • Calculate matching probability for each edge based on exact matching rates

Experimental Setup

This paper is primarily theoretical, verifying algorithm performance through mathematical proof:

Parameter Settings

• Boundary times: $t_0 = 0.05$, $t_1 = 0.757$
• These parameters are obtained through numerical optimization; further adjustments only improve the competitive ratio at the fourth decimal place

Evaluation Metrics

Competitive Ratio: The ratio of the algorithm's expected objective value to the expected objective value of the offline optimal matching

Experimental Results

Main Results

Theorem 9: The Multistage Suggested Matching algorithm is 0.645-competitive for the edge-weighted online stochastic matching problem.

Detailed Analysis

For Class 1 edges $(i,j)$, the competitive ratio is: $\int_0^1 E[A_j(t)]dt ≥ \int_0^{t_0} e^{-y_j t}dt + \int_{t_0}^{t_1} e^{-y_j t_0-(t-t_0)}dt + \int_{t_1}^1 e^{-y_j t_0-(t_1-t_0)-(2-y_j)(t-t_1)}dt$

For Class 2 edges $(i,j)$, the competitive ratio is: $\int_{t_0}^{t_1} E[A_j(t)]dt + E[A_{j'}(t_1)]\int_{t_1}^1 E[A_j(t)|A_{j'}(t_1)=1]dt + 2(1-E[A_{j'}(t_1)])\int_{t_1}^1 E[A_j(t)|A_{j'}(t_1)=0]dt$

Key Findings

1. Worst Case: When $y_j = 1 - \ln 2$, the competitive ratio for both edge classes reaches the minimum value of 0.645
2. Balanced Design: By adjusting $t_0$ and $t_1$, the algorithm exceeds the competitive ratio of $1-\frac{1}{e} ≈ 0.632$ on every edge
3. Theoretical Guarantee: Rigorous mathematical proof ensures the algorithm's performance lower bound

Related Work

Development Timeline

1. Worst-case Model:
   • Karp et al. (1990): Ranking algorithm, $1-\frac{1}{e}$ competitive ratio
   • Aggarwal et al.: Vertex-weighted extension
2. Random Order Model:
   • Goel and Mehta: Greedy algorithm, $1-\frac{1}{e}$ competitive ratio
   • Mahdian and Yan: Improved to 0.696
3. Online Stochastic Matching:
   • Feldman et al. (2009): First breakthrough of $1-\frac{1}{e}$ (unweighted, integer assumption)
   • Vertex-weighted: 0.716 competitive ratio
   • Edge-weighted with free disposal: 0.706 competitive ratio
   • Edge-weighted under integer assumption: 0.705 competitive ratio

Paper Positioning

This paper is the first work to break the $1-\frac{1}{e}$ barrier in the general edge-weighted setting, filling an important gap in the field.

Conclusions and Discussion

Main Conclusions

1. Theoretical Breakthrough: First to achieve a competitive ratio exceeding $1-\frac{1}{e}$ in general edge-weighted online stochastic matching
2. Methodological Innovation: Multi-stage strategy and independence analysis provide new technical tools for the field
3. Performance Improvement: Improvement from 0.632 to 0.645, which while seemingly small, is theoretically significant

Limitations

1. Magnitude of Improvement: Compared to special cases (e.g., 0.716 for vertex-weighted), the improvement is relatively modest
2. Complexity: The algorithm requires precise time control and state observation
3. Theoretical Gap: Still has a gap from the theoretical upper bound of 0.703

Future Directions

1. Further Improvements: Seek better time-segmentation strategies or matching rules
2. Practical Applications: Apply theoretical algorithms to real-world scenarios such as online advertising
3. Model Extensions: Consider more general arrival patterns or constraint conditions

In-Depth Evaluation

Strengths

1. Important Theoretical Breakthrough: Solves an open problem in the field for over a decade
2. Technical Innovation:
   • Clever preprocessing technique simplifies problem structure
   • Multi-stage strategy balances performance across different edge types
   • Independence analysis framework has broad applicability
3. Mathematical Rigor:
   • Complete theoretical analysis and proofs
   • Precise probabilistic calculations and bound analysis
   • Detailed parameter optimization process
4. Accurate Problem Positioning: Clearly identifies the difficulties in the general edge-weighted setting

Weaknesses

1. Practical Limitations:
   • Requires precise Poisson arrival assumptions
   • Time parameters need precise control
   • Lacks validation on real data
2. Magnitude of Improvement: While theoretically important, the numerical improvement is relatively small
3. Complexity: Both algorithm design and analysis are quite complex, making implementation challenging

Impact

1. Theoretical Contribution: Provides important progress for online algorithms and matching theory
2. Methodological Value: Multi-stage analysis and independence maintenance techniques may apply to other problems
3. Inspirational Significance: Provides new ideas and tools for further improvements

Applicable Scenarios

1. Online Advertising: Search engine ad allocation
2. Resource Allocation: Dynamic cloud computing resource allocation
3. Matching Markets: Various online matching platforms

References

The paper cites important works in the field, including:

• Pioneering work by Karp et al.
• Online stochastic matching model by Feldman et al.
• Linear programming improvements by Jaillet and Lu
• Algorithm improvements in various special cases

Summary: This is a paper of significant theoretical importance in theoretical computer science. While the improvement appears modest, it solves an important open problem in the field, demonstrating profound technical insights and rigorous mathematical analysis.