arXiv:2503.09508 · v5
Gain-Sharing Optimization in Randomized Primal--Dual Analysis: Structure and Certification
摘要
Randomized primal--dual guarantees for online matching and allocation often depend on a gain-sharing function that determines how algorithmic gains are distributed among dual variables and, in some settings, also affects allocation decisions. We study the best certificate obtainable by optimizing this function within a specified algorithm--analysis template. For an admissible function class F, we formulate the problem as the functional optimization $Γ(F)=\sup_{f\in F} L[f]$, where $L[f]$ is the worst-case expected dual-feasibility factor. We develop two complementary certification methods: auxiliary linear programs with explicit finite-grid error bounds, and a continuous approach based on monotone Volterra comparison and residual-based numerical verification. We apply them to the vertex-weighted Stochastic Balance template for online matching with stochastic rewards under uniform vanishing success probabilities. For the configuration-LP benchmark and specified dual updates, we optimize over the full admissible class $F_0$ of continuous non-decreasing functions from $[0,\infty)$ to $[0,1]$, and prove $Γ(F_0)\in[0.5802,0.5805]$. We also show that the more tractable subclass used for auxiliary-LP certification attains the same optimum.
作者备注：Revised exposition and strengthened proofs, including explicit auxiliary-LP convergence and coarsening arguments; corrected numerical bounds and added independently verifiable LP certificates