확률적 전조가 있는 비서 문제 (The Secretary Problem with a Stochastic Precursor)

학습 증강 온라인 알고리즘 (learning-augmented online algorithms)에서 예측은 일반적으로 그 내용, 즉 가치 추정치, 솔루션 또는 알고리즘 권장 사항으로서 가치를 인정받습니다. 본 논문은 예측이 단지 그 도착 시간만으로도 가치가 있을 수 있음을 보여줍니다. 우리는 확률적 전조 (stochastic precursor)로 증강된 근본적인 비서 문제 (secretary problem)를 연구합니다. 여기서 전조란 최적의 아이템보다 늦지 않게 도착하는 것이 보장되지만, 그 외의 시점은 확률적으로 결정되는 내용이 없는 신호 (content-free signal)를 의미합니다. 이 신호는 어떠한 추가 정보도 담고 있지 않지만, 그럼에도 불구하고 그 타이밍만으로 최적 정지 (optimal stopping)의 구조를 변화시킵니다. 우리는 무작위 순서 (random-order) 모델과 적대적 순서 (adversarial-order) 모델에서의 최적 정책을 규명합니다. 무작위 순서 모델에서는 균등하게 타이밍이 결정되는 단일 전조만으로도 최소 $\frac{1}{2}$ 이상의 성공 확률을 제공하며, 이는 고전적인 $\frac{1}{e}$ 벤치마크를 개선한 결과입니다. 전조가 점점 더 늦게 도착할수록 성공 확률은 $1$에 수렴합니다. 전통적인 모델에서는 강력한 보장을 제공하지 못하는 적대적 순서 모델의 경우, 충분히 집중된(concentrated) 전조를 통해 상수 수준의 성공 보장을 회복할 수 있습니다. 우리의 연구 결과는 이러한 새로운 형태의 비동기적 시간 정보 (asynchronous temporal information)가 온라인 의사 결정에서 독특하고 강력한 형태의 조언 (advice)이며, 다른 문제들에도 효과적일 수 있음을 보여줍니다.