Logarithmic Regret in Multisecretary and Online Linear Programs with Continuous Valuations

I study how the shadow prices of a linear program that allocates an endowment of nβ ∈ ℝm resources to n customers behave as n rightarrow ∞. I show the shadow prices (i) adhere to a concentration of measure, (ii) converge to a multivariate normal under central-limit-theorem scaling, and (iii) have a variance that decreases like Theta(1/n). I use these results to prove that the expected regret in citesLi2019b online linear program is Theta(log n), both when the customer variable distribution is known upfront and must be learned on the fly. I thus tighten citeauthorsLi2019b upper bound from O(log n log log n) to O(log n), and extend citesLueker1995 Omega(log n) lower bound to the multi-dimensional setting. I illustrate my new techniques with a simple analysis of citesArlotto2019 multisecretary problem.