AI Research Portal

This paper introduces Online Capacitated General Matching with Knapsack (OCGMK), a new online matching problem that extends the Online General Matching (OGM) problem by incorporating multi-capacity vertices and a knapsack constraint on total edge costs. To solve OCGMK, the authors propose the Online Capacity-Knapsack Assignment (OCKA) algorithm, which employs a novel Online Contention Resolution Scheme (OCRS) framework. OCKA achieves a competitive ratio of α = 2 / (3 + e⁻²) for OCGMK and α' = 1/2 when the knapsack constraint is not imposed, matching the best known result for single-capacity OGM. Trace-driven experiments on a real-world dating dataset demonstrate OCKA's superior performance in online dating applications.

The paper addresses several bottlenecks and challenges in online matching problems:

Multi-capacity constraint: Existing Online General Matching (OGM) models assume single-capacity vertices, meaning each vertex can only be matched once. Many real-world applications require vertices to be matched to multiple other vertices up to a certain capacity limit. This introduces a new dimension in optimization and can lead to invalid matching if not handled carefully.

Introduction of Online Capacitated General Matching with Knapsack (OCGMK), a generalization of OGM incorporating multi-capacity vertices and a knapsack constraint.
Development of the Online Capacity-Knapsack Assignment (OCKA) algorithm to solve OCGMK.
Design of a novel probabilistic matching approach within OCKA to manage vertex capacities, balancing instant and future rewards.
Design of a matching acceptance strategy within OCKA to align decisions with the cost budget, preventing early depletion or wastage.
Development of a new OCRS framework that integrates probabilistic matching and matching acceptance to counteract the coupled evolution of capacity usage and cost consumption.
Proof that OCKA achieves a competitive ratio of α = 2 / (3 + e⁻²) for OCGMK.
Proof that OCKA achieves a competitive ratio of α' = 1/2 when the knapsack constraint is not imposed, matching the best result for single-capacity OGM.
Trace-driven experiments on a real-world dating dataset demonstrating OCKA's superior practical performance.

The OCKA algorithm operates in three main phases:

Offline Preparation Phase Before any vertices arrive, OCKA calculates an average preference ye for each edge e ∈ E. This ye is the expectation of x*({ri(e')}) over edge reward distributions, where x*({ri(e')}) is the optimal solution to a relaxed version of the OCGMK problem (P*) without the knapsack and binary constraints. This phase helps determine the likelihood of selecting an edge in the online assignment phase.

Online Assignment Phase When a vertex v = σ(t) arrives at time slot t, OCKA calls the Assign function (Algorithm 2) to determine a capacity-friendly set qf. This phase uses a three-step probabilistic matching approach:

Reference Preference: For each edge e ∈ E-(v), a reference preference ŷt(e) is determined by solving the LP P*({r(e,t)}) with realized or sampled rewards.
Carathéodory Set: Using the reference preference ŷt(e), a Carathéodory set U* is constructed. This set is a subset of E(v) with cardinality at most cv, where each edge e ∈ E(v) is included in U* with a probability equal to ŷt(e).
Seesaw Probability: For each edge (u, σ(t)) ∈ U* ∩ E-(σ(t)), a seesaw probability φu(σ(t)) is calculated using the remaining capacity of vertex u and its total capacity. This probability balances consuming capacity for instant reward versus reserving it for future reward. Edges are included in qf with this probability.

Assignment Acceptance Phase After obtaining the capacity-friendly set qf, OCKA enters the Assignment Acceptance phase (Algorithm 3) to construct a knapsack-friendly set qt. This phase implements a matching acceptance approach:

Knapsack-friendly Set Construction: For each edge e ∈ E-(σ(t)), the Accept function decides whether to include it in qt. This involves evaluating the reference knapsack consumption Xj-1 and its distribution Xj-1.
Safe Range: A "safe range" [θ_j^L, θ_j^R] is determined based on Xj-1 and the cost budget K. This range judges whether it is safe to accept an edge given the current budget.
Decision Rules: An edge ej is included in qt with a probability of 1/β if Xj-1 ∈ (θ_j^L, θ_j^R], or with probability ψj if Xj-1 = θ_j^L. If Xj-1 is outside the safe range, ej is not included.
Update: The reference knapsack consumption Xj and its distribution Xj are updated based on the decision. Finally, OCKA accepts edges that are in the intersection Qt = qf ∩ qt.

Problem Formulation (P): max E[Σe∈E r(e)] s.t. Σe∈E(v) xe ≤ cv, ∀v ∈ V, (Capacity Constraint) Σe∈E xed(e) ≤ K, (Knapsack Constraint) xe ∈ {0,1}, ∀e ∈ E. (Binary Decision)
Relaxed Problem (P)**: P({ri(e)}): max xe, ∀e∈E Σe∈E ri(e) s.t. Σe∈E(v) xe ≤ cv, ∀v ∈ V, xe ∈ [0, 1], ∀e ∈ E.
Average Preference (ye): ye := E[x*({ri(e')})] for all e ∈ E. Calculated using Monte Carlo method and solving offline LP P*({ri(e)}) via interior point or simplex methods.
Seesaw Probability (φu(σ(t))): φu(σ(t)) = (nu(σ(t)) / cv) * (1 / (2 - Στ<t γ(u,σ(τ)) / cv)) where nu(σ(t)) is the remaining capacity of vertex u when σ(t) arrives.
Safe Range Boundaries (θ_j^L, θ_j^R): θ_j^L = b_l1 and θ_j^R = b_l2, where l1 = arg max_{l∈[L]} {l : b_l + d(e_j) ≤ K} and l2 = arg min_{l∈[L]} {Pr{X_{j-1} ∈ (b_l, K - d(e_j)]} ≤ γ}.
Probability (ψj): ψ_j = (γ - Σ_{i=l2+1}^{l1} Pr{X_{j-1} = b_i}) / (β × Pr{X_{j-1} = θ_j^L})
Competitive Ratios:
- OCGMK: α = 2 / (3 + e⁻²), where β = Σe∈E d(e) / K.
- OCGMK without knapsack constraint: α' = 1/2.
Implementation Details: Not stated in the paper.

Datasets:
- Hugging Face Matchmaking (HFM) dataset (dstam 2024), a curated version of the SpeedDating (SD) dataset (Fisman et al. 2006).
- Four traces collected from the HFM dataset.
Metrics:
- Average Total User Satisfaction (maximized).
- Runtime (minimized).
Baselines:
- Karp90 (Karp, Vazirani, and Vazirani 1990)
- Adaptive (Ada)
- Random (R)
- Ezra20 (Ezra et al. 2020)
- Jiang22 (Jiang, Ma, and Zhang 2022)
- Ezra24 (Ezra et al. 2024)
- Goyal22 (Goyal 2022)
Numeric Results:
- Performance (Average Total User Satisfaction): OCKA substantially outperforms all benchmarks in most settings, with its advantage increasing as the risk appetite (cost budget K) increases. For example, in Trace 1, OCKA achieves satisfaction values around 7.5, while Karp90 is around 5.0, Ada around 2.5, R around 5.0, Ezra20 around 2.5, Jiang22 around 5.0, Ezra24 around 40, and Goyal22 around 40. When K = ∞ (no knapsack), OCKA achieves satisfaction around 40, outperforming other baselines which are mostly below 20.
- Runtime: OCKA exhibits minimal runtime overhead compared to benchmarks. For example, in Trace 1, OCKA's runtime is consistently below 10⁻² (e.g., 10⁻³ to 10⁻⁴), similar to or better than most baselines which range from 10⁰ to 10⁻⁴.
Runtime/Training Cost: Experiments were conducted on a MacBook Air with an M2 chip.

Reduced Advantage with Limited Budget: When the knapsack budget is very limited, all algorithms, including OCKA, face a highly constrained decision space, which leaves little room for OCKA to gain a substantial reward advantage through optimizing decisions.

Method evidence: "To solve the OCGMK problem, we propose the Online Capacity-Knapsack Assignment (OCKA) algorithm, which constructs capacity-friendly sets and knapsack-friendly sets to simultaneously and effectively address both constraints." (section: Abstract)
Result evidence: "In most settings, OCKA substantially outperforms all benchmarks with minimal runtime overhead. We observe that the advantage of OCKA increases when the risk appetite increases." (section: 5 Trace-Driven Evaluation)
Limitation evidence: "When the knapsack budget is very limited, all algorithms face a highly constrained decision space, leaving little room for OCKA to gain a substantial reward advantage through optimizing decisions." (section: 5 Trace-Driven Evaluation)

Online Capacitated General Matching with Knapsack

Summary

Problem

Key Contributions

Method

Technical Details

Results

Weaknesses / Limitations

Evidence

Additional Figures