Tightness without Counterexamples: A New Approach and New Results for Prophet Inequalities

Jiashuo Jiang, Will Ma, Jiawei Zhang

Prophet inequalities consist of many beautiful statements that establish tight performance ratios between online and offline allocation algorithms. Typically, tightness is establis…