Prophet Secretary for Combinatorial Auctions and Matroids

Prophet Secretary for Combinatorial Auctions and Matroids SOHEIL EHSANI JANUARY 2018 Joint work with M. Hajiaghayi, T. Kesselheim , S. Singla

Online Decision Making The problem consists of an initial setting and a sequence of events. We have to take particular actions during time. The goal is maximize expected reward or minimize expected cost. Two important fundamental problems are Secretary problem and Prophet Inequality.

Secretary Problem There is an unknown set of numbers ?1, ,?? and an unknown random permutation ?. In an online fashion and at each step ? we observe the value of ???. The goal is to select one value ??, such that Pr[??= max 1 ? ???] is maximized. First introduced by Dynkin in 1960 s and first studied in mechanism design by Hajiaghayi, Kleinberg and Parkes, EC 04 (introduced the value version v.s. the classic rank version and obtained the first bound for the general multi-choice version).

Prophet Inequalities Given known probability distributions ?1, ,??. In an online fashion and at each step ?, we observe a value ?? ??. The goal is to select one value ??, upon its arrival, such that ? ??/?[max??] is maximized. First introduced by Krengel and Sucheston in 1970 s and first studied in computer science by Hajiaghayi, Kleinberg and Sandholm, AAAI 07 (introduced the first bound for the general multi- choice version).

A Simple Tight Algorithm! Compute a threshold (virtual price) p =1 2?[?????]. Select the first item ? where ?? ?. ? max ?? 1 ? ?? The above method -approximation (guarantees 2). And is tight! ? max?? = 2 ? 1 ? with probability ? ?1 ?2 1 with probability 1 Worst Order ? ?? = 1 0 otherwise Best Order ? ?? = 2 ?

Prophet Secretary Similar to prophet inequality, but the boxes arrive in a random permutation. Given ? known distributions ?1, ,?? and unknown random permutation ?1, ,?? . At each time ?, we observe ?? and randomly draw ??? ???. The goal is to make an irrevocable and immediate selection such that ? ??/?[max??] is maximized. Can we achieve an approximation factor better than for prophet secretary? There is a 1 1/? 0.63 approximation algorithm using different thresholds [EHLM ESA 15]. There is a 0.74-approximation algorithm for i.i.d. and large market instances [AEEHKL STOC 17].

Our Contribution Prophet Inequality has been generalized to many settings: -approximation for matroids [KW STOC 12]. -approximation for combinatorial auctions [FGL SODA 15]. (1 1/?)-approximation for best-order matroids [YAN SODA 11]. Is there a better than -approximation for prophet inequality in random order? YES Combinatorial Auctions: we show a 1 1/? approximation algorithm (incentive-compatible for unit demand). Matroids: we show a 1 1/? approximation algorithm. Single Items: we show a single threshold 1 1/? approximation algorithm (tight).

Generalization: Combinatorial Auctions Combinatorial Auctions: There is a set ? of items and ? of buyers, each with a valuation function ??:2? ?. We want allocate items to buyers to maximize social welfare, i.e. ???(??). Valuation functions are XOS, i.e. ??? = max ?(?) for some additive functions ?? 1, ,?? ?. 1 ? ??? Prophet Inequality Variant: We know distributions ?1, ,??for buyers valuations. Buyers arrive one by one and we have to allocate a bundle to them immediately.

Our Approach Achieving 1 1/? for Prophet Secretary First we convert the problem into a continuous-time setting. Assume each buyer arrives at time ?? [0,1] (independently at random). Then we focus on designing dynamic-pricing algorithms: if we serve buyer ? with assignment ?? Her gain is ????. time-dependent discount function Her virtual payment is ????,?? = ? ??.? ?? . time-independent base price This approach allows us to split the objective function ?[ ???(??)] into revenue and utility: ??????? ?????,?? , ??????? = ???= [???? ??(??,??)].

Lower bounding Social Welfare The goal is to maximize social welfare, i.e. ? ??? = ?[ ???(??)] = ? ??????? + ? ??????? . We define a residual function to capture the expected remaining value at time ?. Residual function is defined for a given instance of prophet secretary and a dynamic-pricing algorithm. Definition: a residual function ? ? : 0,1 ? 0 has following properties: ? 0 =? Opt , 1? ? .? ? .??, ? Revenue 0 11 ? ? .? ? .??. ? Utility 0

Proof Template Let ?? be a prophet secretary instance Propose a dynamic pricing algorithm ??? based on ?(?) and ?? Show there exists a residual function ?(?) for ???, ??, and any ?(?) Using a good discount function ?(?) prove ??? is 0.63 approximation

Tuning the Discount Function Lemma: If an algorithm has a residual function then setting ? ? = 1 ?? 1 results in a 0.63-approximation algorithm. Proof: Second property of residual functions says: ? ??????? ? ? .? ? .??. From integration by parts we know: ? ? .? ? .?? = ? ? .? ? ? ? .? ? .??. 1? ? .? ?.?? . 1 0 Therefore, ? ??????? ? ? .? ? 0 Now by adding Revenue and Utility we get: 1 1 . ? ? . 1 ? ? + ? ? .?? ? ? .? ? ? ??? = ? ??? + ? ???? 0 0

Algorithm: Combinatorial Auctions Preprocess: Set a base price for each item based on its contribution to the optimum, ??= ? ?????,?. Draw ? numbers 0 ?1< < ?? 1 independently and uniformly at random from [0,1]. Assignments: Buyer ? selects each remaining item ?if ??,? ??(1 ??? 1). Lemma: The following function is a residual for the algorithm: ? ? = ?Pr[???? ? ??? ???? ?????? ?].?? .

Conclusion Present 1 1/? approximation algorithms for most important generalizations of single item. Can we beat this barrier? [ACK arXiv 2017] improve by 1/400 for single item. What about the i.i.d. case? [AEEHKL STOC 17] present 0.74 approximation algorithm for single item. Thanks to my co-authors! Thomas Kesselheim (TUD) Sahil Singla (CMU) Mohamad Hajiaghayi (UMD)