Secretary Problems and Online Selection with A Priori Information

on YouTube ↗48m

" summary

Classic secretary generalizes to matroids and to K‑choice; geometric bucketing gives a log‑rank reduction (random sampling + run unweighted algorithm on one bucket) and yields O(log rank) competitive ratios. A constructive decomposition plus contraction yields an online contention‑resolution scheme that, under product activation and adversarial order, guarantees each active element is chosen with one quarter probability. Main failures: greedy improving‑element rule breaks on recursive “hat” examples and the decomposition needs improving‑probabilities from a sample (open: fractional secretary and constant‑factor for network/streaming matroid cases).

AI-written summary · about

" chapters (20)

1. 0:00Intro
2. 1:32Classic secretary problem
3. 3:18Best strategy?
4. 3:29An optimal strategy
5. 5:37Increased interest in generalized versions
6. 8:14Selling server connections
7. 11:56Formal definition of Matroid
8. 13:07Roadmap of talk
9. 13:32Results on special cases
10. 15:44Results on general case
11. 19:15Similar guarantee in much more general setting
12. 23:32Good/Safe Improving Elements
13. 24:47What's the problem with the hat?
14. 28:28The Setting
15. 31:13Further motivation
16. 32:55Recall we wish to decompose problem so that each element is good with constant probability
17. 34:20Example all elements active with probability
18. 38:27Almost the complete proof
19. 41:56Summary of Result
20. 42:15Candidate algorithm

" related talks

• 01h 14mCompetitive Analysis Meets Stochastic Input: Secretary Problems And Prophet InequalitiesShuchi Chawla · Data-Driven Decision Processes Boot Camp 2022
• 33mRobust Algorithms for Secretaries and BanditsAnupam Gupta · Mathematics of Online Decision Making 2020
• 01h 04mSubmodularity: Theory and Applications IIAndreas Krause · Foundations of Machine Learning Boot Camp 2017
• 43mLearning about AuctionsAvrim Blum · Uncertainty in Computation 2016
• 48mA Simple Condition for Constant Regret in Online Decision-MakingDaniel Freund · Matching and Objectives
• 01h 04mCompetitive Analysis of Online Algorithms (Part 2)Anupam Gupta · Data-Driven Decision Processes Boot Camp 2022
• 01h 10mMulti-Dimensional and Non-Linear Mechanism Design and Approximation IIJason Hartline · Economics and Computation Boot Camp 2015
• 56mCompetitive Analysis of Online Algorithms (Part 1)Anupam Gupta · Data-Driven Decision Processes Boot Camp 2022