Linear Correlations and Augmentations in Prophet Inequalities Study

PROPHET INEQUALITIES WITH LINEAR CORRELATIONS AND AUGMENTATIONS SAHIL SINGLA PRINCETON UNIVERSITY AND INSTITUTE FOR ADVANCED STUDY JOINT WORK WITH NICOLE IMMORLICA AND BO WAGGONER

BUYING A HOUSE Buyer Houses House values revealed one-by-one Help buyer select online a highly-valued house Challenges Irrevocably select one Online selection House values correlated by common features 1. 2. Xi High-Level Results Simple threshold-based rules don t suffice Instead, winnow some options and then use a threshold arriving online CANWEEVEN SOLVEFOR INDEPENDENT VALUES? 2

PROPHET INEQUALITIES Items n values drawn independently from known distributions: Xi Fi ?- -approx approx means: E reward 1/ E max Xi -threshold mechanism:Take first item with Xi Irrevocably Select one Xi Fi THEOREM: The following give 2-approximation Mean: Median: Pr maxXi = 1/2 Kleinberg-Weinberg 12 Samuel-Cahn 84 = E max Xi/2 EXTENSIONS: arriving online r items: 1 + (1/ r) approx Alaei 11 Matroid: 2-approx Kleinberg-Weinberg 12 WHATIFVALUES CORRELATED? n -approx Hill-Kertz 92 3

LINEAR CORRELATIONS MODEL Bateni-Dehghani-Hajighayi-Seddighin 15 Chawla-Malec-Sivan 15 value of feature VALUES value of item m features ? A ? X1 Y1 For a known matrixA 0,1n m and an unknown vector ?, with Yi Fi for known distributionsFi. n items Aij= degree to which item i exhibits feature j EXAMPLES: A is identity matrix or A {0,1} 0 n m (0 Aij 1) CANWESTILLGET?(?) APPROXIMATION? Xn SPARSITYOFA: ????: max # features affecting an item ????: max # items affected by a feature Ym drawn independently arriving online 4

MAIN RESULTS THM 1 (Single Item): ?(???{????,????}) approximation Remark: -threshold mechanisms have (n) approximation Remark: For A {0,1} 0 n m, we can get O(1) approximation THM 2 (Multiple Items): Selecting r items FOR? ????: FOR? ????: (? + ? ? ) approximation ?(????) approximation Main Ideas: 1. Inclusion-threshold mechanisms: Run -threshold on a ``random subset of items 2. Augmentation Lemma: Robust to positive noise 5

OUTLINE MODEL: PROPHET INEQUALITIESWITH LINEAR CORRELATIONS THRESHOLD-BASED MECHANISMSANDTHE AUGMENTATION PROBLEM SINGLE ITEM: COLUMNAND ROW SPARSITY MULTIPLE ITEMSAND CONCLUSION 6

LOWER BOUND: TOWER INSTANCE THM: -threshold mechanisms have (n) approximation, even for ????= ????= ? Distributions: Yj= nj with probability n j, else 0 Items: Xi= Yi+ Yi+1/n for i < n, and Xn= Yn Y1 X1 OPT= E maxXi E maxYj E jYj = (n) Claim: Any -threshold mechanism gets 2 Idea: ``Contribution from only one of the Yjs Xn Ym 7

MAIN SUBPROBLEM Augmentation Problem positive noise 1. Think of Xi s = independent part + dependent part:Xi=Zi+Wi Independent Correlated with past 2. Can we recover E max Zi given only Zi distributions? Note: Prophet inequality for Wi= 0 Illustrative Example X1 drawn uniformly from [0,1] X2 is 104 w.p. 1/100; zero otherwise +? WHATIFWE ADDSOME POSITIVE NOISE? all the time Median threshold: 1/2, picks X1 half the time. Mean threshold: 50 never picks X1. ARE MEAN THRESHOLDS ALWAYS ROBUST? 8

AUGMENTATION LEMMA LEMMA: Threshold = E maxZi/2 guarantees ? ???? ? ?????/? PROOF. LetP = Pr maxXi> , Qi= Pr Xi < , i < i Reaching i Someone selected ? ???? P + iQi E Zi + Qi P + 1 P E iZi + P + 1 P E max Zi = ? ?????/? Q.E.D. 9

OUTLINE MODEL: PROPHET INEQUALITIESWITH LINEAR CORRELATIONS THRESHOLD-BASED MECHANISMSANDTHE AUGMENTATION PROBLEM SINGLE ITEM: COLUMNAND ROW SPARSITY MULTIPLE ITEMSAND CONCLUSION 10

COLUMN SPARSITY THM (Single Item): ?(????) approximation Inclusion-Threshold Mechanism: Ignore each Xi independently w.p. (1 1/scol) Assign Yj to first survivingXi that contains it Y1 Define Zi= j iAijYj and use Augmentation Lemma Proof Idea: Show E max Zi E max Xi e scol 1. Max Xi survives with 1/scol probability Pr[Yj in Max Xi assigned to Zi] 1 1/scol Ym 2. scol 1 1/e 11

ROW SPARSITY THM (Single Item): ?(????) approximation Challenge: Yjs almost always assigned to Zi with a small Aij Y1 Inclusion-Threshold Mechanism: Primary Item: Assign Yj to some Xi where Aij= 1 Create a directed dependency graph on Yjs to randomly sample Use the Augmentation Lemma Ym 12

OUTLINE MODEL: PROPHET INEQUALITIESWITH LINEAR CORRELATIONS THRESHOLD-BASED MECHANISMSANDTHE AUGMENTATION PROBLEM SINGLE ITEM: COLUMNAND ROW SPARSITY MULTIPLE ITEMSAND CONCLUSION 13

MULTIPLE ITEMS THM (Multiple Items): Selecting r items FOR? ????: FOR? ????: (? + ? ? ) approximation ?(????) approximation Proof idea for ? ????: 1. Need a (1 + O 1 ) approx algorithm robust to augmentations Existing algorithms don t work 2. Partition the number line into buckets with different cardinality constraints 3. Use concentration of number of optimal items in each bucket OPT poly poly OPT r 14

CONCLUSION Prophet Inequalities with Linear Correlations ? A ? Single Item: Multiple Items: (min{srow,scol}) approximation (1 + O 1 ) approximation for r scol Techniques Inclusion-threshold algorithms Algorithms robust to augmentations Open Problems What are the optimal approximation ratios? Can we extend the results to matroid constraints? THANKS FOR LISTENING 15

FURTHER SLIDES 16

AUCTIONS Allocate to Maximize Welfare Bidders Item How well can we do using Posted-Prices? Nothing possible in general Assume a prior 17

X3 X1 X2 Z2 Z1 18