Understanding Prophet Inequality and the Secretary Problem

Slide Note

Explore the concepts of Prophet Inequality and the Secretary Problem, including optimal stopping, decision-making strategies in online processes, and the gambler's problem. Learn about the theorem, optimal algorithms, and competitive ratios in online algorithms. Discover how to find optimal thresholds and policies for maximizing rewards in decision-making scenarios.

kbrit Follow

Uploaded on Sep 26, 2024 | 0 Views

Download Presentation

Please find below an Image/Link to download the presentation.

The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.

E N D

Presentation Transcript

Prophet Inequality & Secretary Problem NICK GRAVIN, ITCS SHUFE

The Plan 1. Introduction to Prophet Inequalities 2. Connections to Pricing and Mechanism Design 3. Solution to single-choice setting 4. Introduction to Secretary problem 5. Solution to basic setting

Prophet inequality 1. Originally: optimal stopping problem. [Krengel Sucheston 74] 2. Online process: One-by-one see a sequence of random variables ?? ?? Decision @ step i: Stop (get ??) or continue (get 0) 3. Multiple choice settings In some order see a sequence of random variables ?? ?? Decision @ step i: take e (add ??) or discard e (get 0) Can take many ? ?, but S must be a feasible set (? ?)

Prophet Inequality The gambler s problem: ?1 ?2 ?3 ?4 ?5

Prophet Inequality The gambler s problem: $20 ?1 ?2 ?3 ?4 ?5 Keep: win $20, game stops. Discard: prize is lost, game continues with next box.

Lets Play 2.87 1.14 2.67 3.16 ?[2,4] ?[2,4] ?[1,5] ?[0,7]

Prophet Inequality Theorem: [Krengel, Sucheston, Garling 77] There exists a strategy for the gambler such that ? ????? 1 2? max ?? ? and the factor 2 is tight. [Samuel-Cahn 84] a fixed threshold strategy: choose a single threshold ?, accept first prize ?.

Online Algorithms Expected value of the optimal offline algorithm ? ????? 1 2? max ?? ? Expected value of the online algorithm Competitive ratio

Lower Bound: 2 is Tight 1 ? w.p. ? 1 0 otherwise

Optimal online policy What is optimal online algorithm? 1. If we get to box ?: ?? before j (? < ?) are irrelevant 2. Threshold rule ?? @?: stop if and only if ?? ?? How to find optimal thesholds (?1, ,??)? ?[??] ??= 0 ?? 1? -- take ?? 1 ?? 1 is better than expected future Backward induction: ??= ???+1[max(??+1,??+1)]

Online Optimum (cons) 1. Thresholds change (decrease) with time. Non trivial functions of the distributions 2. To find each ?? we need to know arrival order. 3. Prophet inequality: offline optimum (max ??) arrival order irrelevant ? Online -competitive policy does not know the order

Application: Posted Pricing A mechanism design problem: 1 item to sell, n buyers, independent values ?? ~ ??. Buyers arrive sequentially, in an arbitrary order. For each buyer: interact according to some protocol, decide whether or not to trade, and at what price. ?1 ~ ?1 ?2 ~ ?2 ?3 ~ ?3 ?4 ~ ?4 Corollary of Prophet Inequality: Posting an appropriate take-it-or-leave-it price yields at least half of the expected optimal social welfare. [Hajiaghayi Kleinberg Sandholm 07]

Applications (Cont) What about revenue? [Chawla Hartline Malec Sivan 10]: Can apply prophet inequality to virtual values to achieve half of optimal revenue. Virtual value: ??? = ? 1 ??(?) ??(?), where ?? cdf and ?? is pdf. +] Revenue maximizing auction: Ev ?1 ??[max [Myerson 81]: 1. value ?? virtual value ???? 2. Sell to ? : with maximum ?? ?? , if ?? ?? 0 3. ? pays p - threshold value to win: ? = max j ? ???? ? 1???? 1(0) ?? ,??

Prophet Inequality Multiple choices of ? that achieve the 2-approx. Here s one due to [Kleinberg Weinberg 12]: Theorem (prophet inequality): for one item, setting threshold p =1 2? max ? ?? yields expected value 1 2? max ??. ? Example: 10 w.p. 1/2 8 w.p. 1/4 6 w.p. 1/8 2 w.p. 1/8 OPT = 1 or 6 0 or 8 2 or 10 E[OPT] = 8 accept first prize 4 (each box: prizes equally likely)

Prophet Inequality: Proof Theorem (prophet inequality): for one item, setting threshold p =1 2? max ? ?? yields expected value 1 2? max ??. ? What can go wrong? If threshold is Too low: we might accept a small prize, preventing us from taking a larger prize in a later round. Too high: we don t accept any prize.

A Proof for Full Information ?1= 10 ?2= 50 ?3= 80 ?4= 15 Idea: price 1 2max ??is balanced ? ??. Let ?? = max ? Case 1: Somebody ? < ? buys the item. revenue 1 2?? Case 2: Nobody ? < ? buys the item. utility of ? ?? 1 In either case: welfare = revenue + buyer utilities 1 2?? =1 2?? 2??

Extending to Stochastic Setting Thm: setting price p =1 ?? yields value 1 2? max 2? max ??. i i ? = max Proof. Random variable: ??= ??? i 1. REVENUE = ? Pr item is sold =1 2E[? ] Pr item is sold 2. SURPLUS= ?E utility of buyer ? ?E ?? p+ ? ? sees item = ?E ?? p+ Pr ? sees item ?E ?? p+ Pr item not sold E max ?? p Pr item not sold i 2E[? ] Pr item not sold 1 3. Total Value = REVENUE + SURPLUS 1 2E[v ].

Prophet Inequality: Proof Thm: for one item, price p =1 2? ??? yields value 1 2? ??? . Summary: Price is high enough that expected revenue offsets the opportunity cost of selling the item. Price is low enough that expected buyer surplus offsets the value left on the table due to the item going unsold.

Multiple-Prize Prophet Inequality Prophet inequality, but gambler can keep up to ? prizes ? = 1: original prophet inequality: 2-approx [Alaei 11] [Alaei Hajiaghayi Liaghat 12] Can be improved to 1 + ? ? using a randomized strategy, and this is tight. 1

Prophet Inequality: feasibility constraints Constraint Upper Bound Lower Bound 2 Single item 2 1 1 1 + ? 1 + ? items ? ? 2 Matroid 2 [Kleinberg Weinberg 12] ? (? + 1) ? + 1 of ? matroids [Feldman Svensson Zenklusen 15] [Kleinberg Weinberg 12] 3 7/3 Matching [G., Wang 19] [Alon, Polner, Weinberg 21] log? loglog? [Babaioff Immorlica Kleinberg 07] Downward-closed, max set size ? ?(log?log?) [Rubinstein 16] Directly imply posted-price mechanisms for welfare, revenue

Secretary problem Want to hire 1 secretary. Interview ? candidates for a position one at a time. interview: see if candidate is better than everyone before. accept & stop search/reject & continue process rejected candidates are gone (take another job). Assume: candidates arrive in a random order ? chosen uniformly at random. Goal: maximize probability of choosing the best candidate.

Accept or reject? 1st n = 6 candidates, 5 more to see.

1st 2nd <

Maybe someone better will appear in the future? 1st 2nd 3rd < <

1st 2nd 3rd 4th Marge is still the best so far < < <

So we made a mistake. 1st 2nd 3rd 4th 5th < < < <

The best 1st 2nd 3rd 4th 5th 6th < < < < <

What if adversary chooses the order? Then we cannot do better than 1/n. Argument. Adversary picks arrival order ?~?{?1, ,??}: 1. ?1:2?? < 3?? < ?? < 1?? 2. ?2:3??< 4? < ?? < 1??< 2?? 3. 4. ??:? + 1? < 4? < ?? < 1??< 2?? < < ?? 5. 6. ??:1??< 2?? < < ?? Proof on the board. Why?

Observations 1. Do not hire candidate who is not the best so far. 2. Interview i-th candidate: 1 ? Pr ? ?? ???? = Pr ? ?? ???? ?? ??? =1 ? 3. If we hire top among k candidates, Pr ?? ???? =? ? does not matter: when this top candidate appears among k does not matter: the relative order of these k people

Analysis How to achieve probability 1 4: Exploration phase Ignore first ? 1. 2 candidates Among remaining ? 2. 2 pick any that is best so far Exploitation phase Pr ???? ??? Pr ??? ?????? ? 2 2 ??? 2?? ???? ??????? ? 2 2 Pr 2?? ???? ? =1 2 1 2=1 = Pr ??? > 2 | ??? > 4

Theorem. There is a simple strategy to pick the best with probability at least 1/e. Proof. On the board. Plan: policy explore ? & exploit ? ? candidates is optimal Optimal ? ? ?