Prophet Inequalities: A Crash Course on Gambling Strategies

Delve into the fascinating world of Prophet Inequalities, where strategic decision-making meets gambling scenarios. Explore theories, theorems, and practical applications in pricing, mechanism design, and social welfare optimization. Uncover the secrets behind maximizing gains and making informed choices in uncertain situations.

• Prophet Inequalities
• Gambling Strategies
• Pricing
• Mechanism Design
• Social Welfare Optimization

toothman_k Follow

Uploaded on Feb 26, 2025 | 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.If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.

You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.

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.

Presentation Transcript

1. Prophet Inequalities A Crash Course BRENDAN LUCIER, MICROSOFT RESEARCH EC18: ACM CONFERENCEON ECONOMICSAND COMPUTATION MENTORING WORKSHOP, JUNE 18, 2018

3. The Plan 1. Introduction to Prophet Inequalities 2. Connections to Pricing and Mechanism Design 3. Variations I: Secretaries and Prophet Secretaries 4. Variations II: Multiple Prizes

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

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.

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

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 ?.

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

9. Theorem: [Samuel-Cahn 84] Given distributions ?1, ,?? where ??~??, there exists a fixed threshold strategy (accept first prize ?) such that ??????? 1 2??max ?? ? Proof: On the board.

10. 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]

11. Applications What about revenue? [Chawla Hartline Malec Sivan 10]: Can apply prophet inequality to virtual values to achieve half of optimal revenue. ?[???] = ?? ??? = ?? ??????? ? ? +] (for single item) = ??[max Auction w/ E[Rev] 1 2??? ???? ? + using ?? on ?? ???? + ? Distribution ?? on ???? Compute ? s.t. Pr max 1. + ? = 1/2(t s.t. Prob. Of selling is ) 2. ? Give to an agent with ???? With highest value Payment = max{?? 3. 1(?), second highest bid} 4.

12. Prophet Inequality Multiple choices of ? that achieve the 2-approx of total value. 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)

13. 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.

14. 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??

15. 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 ].

16. 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.

17. Secretaries and Prophet Secretaries

18. A Variation Prophet Inequality: Prizes drawn from distributions, order is arbitrary A Related Problem: Prizes are arbitrary, order is uniformly random

19. Lets Play 1099 5.21 0.003 682,918 ? ? ? ? The game of googol [Gardner 60]

20. Secretary Problem Theorem: [Lindley 61, Dynkin 63, Gilbert and Mosteller 66] There exists a strategy for the secretary problem such that ?? ?????? ??????? 1 ? and the factor ? is tight as ? grows large. Strategy: observe the first ?/? values, then accept the next value that is larger than all previous.

21. Prophets vs Secretaries Prophet Inequality: Prizes drawn from distributions, order is arbitrary Secretary Problem / Game of Googol: Prizes are arbitrary, order is uniformly random Prophet Secretary: Prizes drawn from distributions, order is uniformly random known [Esfandiari, Hajiaghayi, Liaghat, Monemizadeh 15] and revealed online

22. Recall: ?[2,4] ?[2,4] ?[1,5] ?[0,7]

23. Recall: ?[0,7] ?[1,5] ?[2,4] ?[2,4]

24. Prophet Secretary Theorem: [Esfandiari, Hajiaghayi, Liaghat, Monemizadeh 15] There exists a strategy for the gambler such that ? ????? 1 1 ? max ??. ? ? [Azar, Chiplunkar, Kaplan EC 18]: A strategy for the gambler that beats 1 1 ?.

25. Prophet Secretary threshold value prize round 5 6 7 8 1 2 3 4

26. Prophet Secretary Higher threshold: more revenue when we sell the item to this buyer. value Lower threshold: More surplus for this buyer. round 5 6 7 8 1 2 3 4

27. Extension: Multiple Prizes

28. Multiple-Prize Prophet Inequality Prophet inequality, but gambler can keep up to ? prizes ? = 1: original prophet inequality: 2-approx ? 1: [Hajiaghayi, Kleinberg, Sandholm 07] There is a threshold ? such that picking the first k values ? gives a 1 + ?( log?/?) approximation. Idea: choose ? s.t. expected # of prizes taken is ? Then w.h.p. # prizes taken lies between ? 2?log?. 4?log? and ?. [Alaei 11] [Alaei Hajiaghayi Liaghat 12] Can be improved to 1 + ? ? using a randomized strategy, and this is tight. 1

29. Aside: Beyond Cardinality Constraint Upper Bound Lower Bound 2 Single item 2 1 1 1 + ? 1 + ? items ? ? 2 Matroid 2 [Kleinberg Weinberg 12] ? (? + 1) ? + 1 ? matroids [Feldman Svensson Zenklusen 15] [Kleinberg Weinberg 12] 5 Knapsack 2 [Duetting Feldman Kesselheim L. 17] log? loglog? Downward-closed, max set size ? ?(log?log?) [Rubinstein 16] [Babaioff Immorlica Kleinberg 07] Directly imply posted-price mechanisms for welfare, revenue

30. Multiple-Prize Prophet Inequality A different variation on cardinality: The gambler can choose up to ? 1 prizes Afterward, gambler can keep the largest of the prizes chosen Theorem [Assaf, Samuel-Cahn 00]: There is a strategy for the gambler such that ? ????? 1 1 ?+1? max ?? ? [Ezra, Feldman, Nehama EC 18]: An extension to settings where gambler can choose up to ? prizes and keep up to . Includes an improved bound for = 1!

31. Combinatorial Variants More general valuation functions: Reward for accepting a set of prizes ? is a function ?(?). Example: arbitrary submodular. [Rubinstein, Singla 17] Multiple prizes per round: Multiple boxes arrive each round. Revealed in round ?: valuation function ??(?) for accepting set of prizes ?? on round ?. (Note: possible correlation!) Application: posted-price mechanisms for selling many goods [Alaei, Hajiaghayi, Liaghat 12], [Feldman Gravin L 13], [Duetting Feldman Kesselheim L 17]

32. Summary Prophet Inequalities: analyzing the power of sequential decision-making, vs an offline benchmark. Recent connections to pricing and mechanism design MANY variations! A very active area of research Open Challenge: Best-Order Prophet Inequality Suppose the gambler can choose which order to open boxes. What fraction of ? max ?? can the gambler guarantee? ? Can the best order be computed efficiently? Thanks!

33. Bonus: Multi-Dimensional Prophets

34. Buyers: Goods: A General Model 1 1 2 2 Combinatorial allocation Set M of ? resources (goods) ? buyers, arrive sequentially online Buyer ? has valuation function ??:2? ? 0 Each ?? is drawn indep. from a known distribution ?? Allocation: ? = ?1, ,??. There is a downward-closed set ? of feasible allocations. n m Goal: feasible allocation maximizing ???(??)

35. Posted Price Mechanism 1. For each bidder in some order ?: 2. Seller chooses prices ??(??) 3. Bidder ? s valuation is realized: ?? ?? 4. ? chooses some ?? argmax ???? ???? Notes: Obviously strategy proof [Li 2015] Tie-breaking can be arbitrary Prices: static vs dynamic, item vs. bundle Special case: oblivious posted-price mechanism (OPM) prices chosen in advance, arbitrary arrival order

36. Applications Problem Approx. Price Model Combinatorial auction, XOS valuations 2 Static item prices Bounded complements (MPH-k) [Feige et al. 2014] 4? 2 Static item prices 2 (existential) 4 (polytime) Submodular valuations, matroid constraints Dynamic prices Knapsack constraints 5 Static prices d-sparse Packing Integer Programs 8d Static prices [Feldman Gravin L 13], [Duetting Feldman Kesselheim L 17]