Download

Algorithms & Adaptivity Gaps for stochastic probing

Upload
0
Embed
Share
Upload and view presentations on any device and embed the player to your website! --- > >
Upload PPT
Upload PPT

Download this Presentation

channing

2021-9-26 published at HR&Recruiting category

Presentation Transcript

1.Optimal Online Contention Resolution SchemesVIA Ex-Ante Prophet Inequalities Sahil Singla (Carnegie Mellon University ➞ Princeton University) Joint Work with euiwoong Lee (22nd August, 2018)
2.Online Rounding AlgorithmsUSING Prophet Inequalities Sahil Singla (Carnegie Mellon University ➞ Princeton University) Joint Work with euiwoong Lee (22nd August, 2018)
3.Diamond-Selling Problem Sell One Diamond: Multiple potential buyers Buyers Arrive and Make a Take-it-or-Leave-it Bid Decide Immediately and Irrevocably Goal: Maximize value of the accepted bid Cannot go back to a declined bid Similar Examples Selling ad-slots Finding a secretary/marriage partner 3
4.Prophet Inequality Model 4 Given Indep Distributions on Values 𝑋 1 , 𝑋 2 , .. , 𝑋 𝑛 Irrevocably decide if picking: Known adversarial order Objective: Maximize value of picked buyer 𝐄[𝐀𝐥𝐠] Compare to 𝐄[𝐌𝐚𝐱], i.e., 𝐄[𝐀𝐥𝐠] 𝐄[𝐌𝐚𝐱] X3=0.2 X2=0.6 X1=0.3 X1~Unif(0,1) X2~Exp(2) X3∼0.2 X4=0.9 Picked X4~Unif(0,1) Cannot Beat ½-Approx Let 𝑋 1 =1 w.p. 1 Let 𝑋 2 = 1 𝜖 w.p. 𝜖 0 otherwise 𝐄[𝐌𝐚𝐱] =𝜖⋅ 1 𝜖 + 1−𝜖 ⋅1≈2 𝐄[𝐀𝐥𝐠 ] ≤1 𝑿 𝒊 = 𝒗 𝒊 w.p. 𝒑 𝒊 𝟎 otherwise Krengel-Sucheston’77 gave 1 2 -approx
5.PROOF: Pr i considered = Pr Reach i ⋅Pr i considered| reach i ≥ Pr Reach n ⋅ 1 2 ≥ 1 4 5 Lemma: 𝐄[𝐌𝐚𝐱] is at most ex-ante relaxation max: 𝑖 𝑦 𝑖 ⋅ v 𝑖 s.t. 𝑖 𝑦 𝑖 ≤1 𝑦 𝑖 ∈[0, 𝑝 𝑖 ] Suffices: Any algorithm that picks every i w.p. 𝑦 𝑖 2 while 𝑋 𝑖 = v 𝑖 At most 1 item Probability i is max 1 2 -OCRS (Magician’s problem Alaei’11) because, implies 𝐄 𝐀𝐥𝐠 ≥ 1 2 ⋅ 𝑖 𝑦 𝑖 ⋅ v 𝑖 ⟹ 1 2 -prophet inequality Thm ( 1 4 -OCRS): Consider i w.p. 1 2 on reaching, and pick if 𝑋 𝑖 = v 𝑖 . Prophet Ineq to OCRS 𝑿 𝒊 = 𝐯 𝒊 w.p. 𝒑 𝒊 𝟎 otherwise WLOG 𝑦 𝑖 = 𝑝 𝑖 by reducing 𝑝 𝑖 ≥(1− 1 2 ∑ 𝑦 𝑗 ) ≥ 1 2
6.6 Lemma: 𝐄[𝐌𝐚𝐱 𝐈𝐧𝐝𝐞𝐩 𝐒𝐞𝐭] is at most ex-ante relaxation max: 𝑖 𝑦 𝑖 ⋅ v 𝑖 s.t. 𝐲∈Matroid Polytope 𝑦 𝑖 ∈[0, 𝑝 𝑖 ] Probability i in offline max Matroid Prophet Inequality 𝑿 𝒊 = 𝐯 𝒊 w.p. 𝒑 𝒊 𝟎 otherwise Constraints = Matroid Function = Additive Given Indep Distributions on Values 𝑋 1 , 𝑋 2 , .. , 𝑋 𝑛 Irrevocably decide if picking: Known adversarial order Goal: Maximize sum of values of Indep Set Compare to 𝐄[𝐌𝐚𝐱 𝐈𝐧𝐝𝐞𝐩 𝐒𝐞𝐭] i.e., 𝐄[𝐀𝐥𝐠] 𝐄[𝐌𝐚𝐱 𝐈𝐧𝐝𝐞𝐩 𝐒𝐞𝐭] 𝛼-OCRS ⟹ 𝛼-Approx Ex-Ante Prophet Inequality Compares to relaxation instead of 𝐄[𝐌𝐚𝐱 𝐈𝐧𝐝𝐞𝐩 𝐒𝐞𝐭]
7.Given 𝒚∈ ℛ 𝑛 inside matroid polytope Each element 𝑖 active independently w.p. 𝑦 𝑖 : Revealed one-by-one Decide immediately and irrevocably to select current active 𝑖 7 Online Contention Resolution Scheme Defn (𝜶-OCRS): An online rounding algorithm that always remains feasible and ensures∀𝒊: 𝐏𝐫 𝒊 𝐢𝐬 𝐬𝐞𝐥𝐞𝐜𝐭𝐞𝐝 & 𝐚𝐜𝐭𝐢𝐯𝐞 ≥𝜶⋅ 𝒚 𝒊 Introduced by Feldman-Svenson-Zenklusen’16: Gave ¼-OCRS for matroids Applications: Stochastic problems with “commitment constraints” Getting 1 2 -OCRS?
8.8 Our Main Results Corollary: There Exists a 𝟏 𝟐 -OCRS for a Matroid Thm 2: There Exists a 𝟏 𝟐 -Ex-Ante Prophet Inequality for a Matroid Thm 1: 𝜶-Ex-Ante Proph-Ineq ⟹ 𝜶-OCRS We can also design OCRSs from prophet inequalities.
9.Introduction What is a Prophet Inequality and an OCRS Why OCRS implies Prophet Inequality Our Main Results Why Ex-ante Prophet Inequality implies OCRS CVZ Style LP for OCRS Using LP Duality How to Design Ex-ante Prophet Inequalities Challenges Proof Ideas Conclusions Extension to Random Order Open Problems 9 Outline
10.Introduction What is a Prophet Inequality and an OCRS Why OCRS implies Prophet Inequality Our Main Results Why Ex-ante Prophet Inequality implies OCRS CVZ Style LP for OCRS Using LP Duality How to Design Ex-ante Prophet Inequalities Challenges Proof Ideas Conclusions Extension to Random Order Open Problems 10 Outline
11.11 Let 𝜙∈Φ denote deterministic online rounding scheme Let 𝑞 𝑖,𝜙 =Pr[𝑖 selected by 𝜙] and 𝜆 𝜙 =Pr[ϕ is running] 𝐦𝐚 𝐱 𝝀,𝑐 : 𝑐 s.t. ∀𝑖: 𝜙 𝑞 𝑖,𝜙 𝜆 𝜙 ≥ 𝑦 𝑖 ⋅𝑐 𝜙 𝜆 𝜙 =1 ∀𝜙: 𝜆 𝜙 ≥0 CVZ Style LP for OCRS Thm 1: 𝜶-Ex-Ante Proph-Ineq ⟹ 𝜶-OCRS CVZ style exponential sized LP: c-selectability Valid distribution over Φ Suffices to show LP value = Dual LP value ≥𝛼 because implies 𝛼-OCRS
12.Using LP Duality 12 𝐦𝐢𝐧 𝒛,𝜇 : 𝜇 s.t. ∀𝜙: 𝑖 𝑞 𝑖,𝜙 ⋅ 𝑧 𝑖 ≤𝜇 𝑖 𝑦 𝑖 𝑧 𝑖 =1 ∀𝑖: 𝑧 𝑖 ≥0 𝐦𝐚 𝐱 𝝀,𝑐 : 𝑐 s.t. ∀𝑖: 𝜙 𝑞 𝑖,𝜙 𝜆 𝜙 ≥ 𝑦 𝑖 ⋅𝑐 𝜙 𝜆 𝜙 =1 ∀𝜙: 𝜆 𝜙 ≥0 Suffices to show for every feasible 𝒚 and 𝒛, ∃𝜙 s.t. 𝑖 𝑞 𝑖,𝜙 ⋅ 𝑧 𝑖 ≥𝛼 Let 𝑋 𝑖 equals 𝑧 𝑖 w.p. 𝑦 𝑖 : Algo 𝜙 value = 𝑖 𝑧 𝑖 ⋅ 𝑞 𝑖,𝜙 ≥ 𝛼⋅ 𝑖 𝑦 𝑖 𝑧 𝑖 = 𝛼 Thm 1: 𝜶-Ex-Ante Proph-Ineq ⟹ 𝜶-OCRS Ex-ante objective Claim: 𝜶-Ex-Ante Proph-Ineq ⟹ Optimal LP value ≥𝛼
13.Introduction What is a Prophet Inequality and an OCRS Why OCRS implies Prophet Inequality Our Main Results Why Ex-Ante Prophet Inequality implies OCRS CVZ Style LP for OCRS Using LP Duality How to Design Ex-Ante Prophet Inequalities Challenges Proof Ideas Conclusions Extension to Random Order Open Problems 13 Outline
14.Challenges Standard proph-ineq compares to 𝐄[𝐌𝐚𝐱 𝐈𝐧𝐝𝐞𝐩 𝐒𝐞𝐭] Ex-ante proph-ineq compares to 𝑖 𝑦 𝑖 𝑣 𝑖 In general 1− 1 𝑒 ⋅ Ex-Ante Relax ≤ 𝐄[𝐌𝐚𝐱 𝐈𝐧𝐝𝐞𝐩 𝐒𝐞𝐭] ≤ Ex-Ante Relax Implies a 1 2 ⋅ 1− 1 𝑒 ex-ante prophet inequality 14 THM [KW’12]: There Exists 𝟏 𝟐 -Matroid Prophet Inequality Correlation Gap Thm 2: There Exists a 𝟏 𝟐 -Ex-Ante Prophet Inequality for a Matroid
15.Proof Ideas 15 Find probability distribution 𝓓 over independent sets s.t.𝒚= 𝑆 is Independent 𝓓 𝑆 ⋅ 𝟏 𝑆 Ex-ante objective is 𝑖 𝑦 𝑖 𝑣 𝑖 = 𝑆 is Independent 𝓓 𝑆 ⋅ 𝑖∈𝑆 𝑣 𝑖 Modify KW’12 to compare to correlated distrib 𝓓 instead of product distrib Corollary: There Exists a 𝟏 𝟐 -OCRS for a Matroid Thm 2: There Exists a 𝟏 𝟐 -Ex-Ante Prophet Inequality for a Matroid
16.Introduction What is a Prophet Inequality and an OCRS Why OCRS implies Prophet Inequality Our Main Results Why Ex-ante Prophet Inequality implies OCRS CVZ Style LP for OCRS Using LP Duality How to Design Ex-ante Prophet Inequalities Challenges Proof Ideas Conclusions Extension to Random Order Open Problems 16 Outline
17.Optimal RCRS 17 THM [EHKS’18]: There exists (1− 𝟏 𝒆 )-Prophet-Secretary for Constraints = Matroid Function = Additive Proof uses Two Ideas Exponential LP with variables all deterministic online algorithms Show dual is at least (1− 𝟏 𝒆 ), which is an ex-ante prophet-secretary inequality QUES: Better than 𝟏 𝟐 -OCRS for uniformly random arrival? THM 3: There exists a (1− 𝟏 𝒆 )-RCRS for a Matroid
18. Connections between OCRS and Prophet Inequalities OCRS ⟹ Prophet Ineq Ex-ante Prophet Ineq ⟹ OCRS Designing Ex-Ante Prophet Inequalities 1 2 -approx for adversarial order over a matroid 1− 1 𝑒 -approx for random order over a matroid Open Questions Can we avoid assuming adversarial order is known? Can we get “greedy” OCRSs that are useful for submodular functions? 18 Questions? Summary and Open Problems
19.References S. Alaei. `Bayesian combinatorial auctions: Expanding single buyer mechanisms to many buyers’. FOCS’11 C. Chekuri, J. Vondrak, and R. Zenklusen. `Submodular function maximization via the multilinear relaxation and contention resolution schemes’. SICOMP’14. S. Ehsani, T. Kesselheim, M.T. Hajiaghayi, and S. Singla. `Prophet Secretary for Matroids and Combinatorial Auctions’. SODA’18. M. Feldman, O. Svensson, and R. Zenklusen. `Online contention resolution schemes’. SODA’16 R.D. Kleinberg and M. Weinberg. `Matroid prophet inequalities’. STOC’12 U. Krengel and L. Sucheston. `Semiamarts and finite values’. Bull. Amer. Math. Soc.’77 E. Lee and S. Singla. `Optimal Online Contention Resolution Schemes via Ex-Ante Prophet Inequalities'. ESA’18. 19

Latest Release