Logarithmic Regret in Multisecretary and Online Linear Programs with Continuous Valuations

\cite{Arlotto2019} showed that regret in the multisecretary problem is bounded, both in the number of job openings, $ n $, and the number of applicants, $ k $, provided that the applicant valuations have finite support. I study what happens when applicant valuations have continuous support. Specifically, I show that the regret grows like $ \log(n) $ when valuations are drawn from a standard uniform distribution. So the regret, while not finite, still grows very slowly. However, the mechanism is completely different in this setting: the agent makes a finite number of costly mistakes in the discrete case, but makes an infinite number of nearly costless mistakes in the continuous case.

Paper

Similar papers

© 2026 NYSGPT2525 LLC