Algorithms & Adaptivity Gaps for stochastic probing

Download this Presentation

0

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