Delegated Stochastic Probing

on YouTube ↗25m

" summary

Defines a game-theoretic model of delegated stochastic probing and gives an explicit single-proposal mechanism that is as powerful as general signaling, reduces delegation to greedy profit-inequalities against an almighty adversary, and removes outer constraints losing only an adaptivity-gap factor. Consequences: constant-factor approximations for many inner constraints via contention-resolution results, and a tight 1/2 approximation for the heterogeneous distributional (single-choice) setting; lotteries can beat deterministic mechanisms on some instances but match the 1/2 worst-case. Tools: profit inequalities, adaptivity gaps, contention resolution, Samuel–Cahn threshold rules.

AI-written summary · about

" chapters (13)

1. 0:00Motivation - Transportation
2. 0:51Delegated Search
3. 2:01Overview of Results
4. 5:10Delegated Stochastic Probing
5. 7:22Notation
6. 9:21Example
7. 10:56Single-Proposal Lemma
8. 12:49Detour - Prophet Inequalities
9. 15:21Inner Constraint Delegation
10. 18:26Detour - Adaptivity Gap
11. 20:21General Delegation
12. 22:15Lottery Mechanisms
13. 23:41Open Questions