Tight Bounds for Downward-Closed Prophet and Secretary Problems
cs.GT, cs.DS
Submitted: 2026-11-12
Updated: 2026-11-12
Terminology
Sources
- Prophet Secretary: Surpassing the $1-1/e$ Barrier
- Sample-Based Matroid Prophet Inequalities
- Adaptivity Gaps for Stochastic Probing with Subadditive Functions
- Beyond matroids: Secretary Problem and Prophet Inequality with general constraints
- Secretary, Prophet, and Stochastic Probing via Big-Decisions-First
Related papers
- How Many Votes is a Lie Worth? Measuring Strategyproofness through Resource Augmentation
- Effective Horizons for Prophet Inequalities with Discounted I.I.D. Rewards
- Truthful-in-Expectation Mechanism with Constant Maximin-Share Guarantee
- The Power of Recruiting the Smaller Side: Two Additional Traders Suffice in Two-Sided Markets
- From signaling to interviews in random matching markets
- Optimizing Social Utility in Sequential Experiments