SU\G(𝔸)/K·U
Sign Up for free Log In

Prophets and Secretaries with Overbooking

Authors

Tomer Ezra, Michal Feldman, Ilan Nehama
Type: Article
Publication Date: 2018-06-11
Citations: 12
DOI: https://doi.org/10.1145/3219166.3219211

Abstract

The prophet and secretary problems demonstrate online scenarios involving the optimal stopping theory. In a typical prophet or secretary problem, selection decisions are assumed to be immediate and irrevocable. However, many online settings accommodate some degree of revocability. To study such scenarios, we introduce the l-out-of- k setting, where the decision maker can select up to k elements immediately and irrevocably, but her performance is measured by the top l elements in the selected set. Equivalently, the decision makes can hold up to l elements at any given point in time, but can make up to k-l returns as new elements arrive. We give upper and lower bounds on the competitive ratio of l-out-of- k prophet and secretary scenarios. For l-out-of- k prophet scenarios we provide a single-sample algorithm with competitive ratio 1-l· e-Θ((k-l)2/k) . The algorithm is a single-threshold algorithm, which sets a threshold that equals the (l+k/2)th highest sample, and accepts all values exceeding this threshold, up to reaching capacity k . On the other hand, we show that this result is tight if the number of possible returns is linear in l (i.e., k-l =Θ(l)). In particular, we show that no single-sample algorithm obtains a competitive ratio better than 1 - 2-(2k+1)/k+1 . We also present a deterministic single-threshold algorithm for the 1-out-of- k prophet setting which obtains a competitive ratio of 1-3/2 · e-s/k 6, knowing only the distribution of the maximum value. This result improves the result of [Assaf & Samuel-Cahn, J. of App. Prob., 2000].

Locations

  • arXiv (Cornell University)
    View PDF

Ask a Question About This Paper

Summary

Login to see paper summary

Similar Works

Prophets and Secretaries with Overbooking

2018-05-14
Tomer Ezra , Michal Feldman , Ilan Nehama
The prophet and secretary problems demonstrate online scenarios involving the optimal stopping theory. In a typical prophet or secretary problem, selection decisions are assumed to be immediate and irrevocable. However, … The prophet and secretary problems demonstrate online scenarios involving the optimal stopping theory. In a typical prophet or secretary problem, selection decisions are assumed to be immediate and irrevocable. However, many online settings accommodate some degree of revocability. To study such scenarios, we introduce the $\ell-out-of-k$ setting, where the decision maker can select up to $k$ elements immediately and irrevocably, but her performance is measured by the top $\ell$ elements in the selected set. Equivalently, the decision makes can hold up to $\ell$ elements at any given point in time, but can make up to $k-\ell$ returns as new elements arrive. We give upper and lower bounds on the competitive ratio of $\ell$-out-of-$k$ prophet and secretary scenarios. These include a single-sample prophet algorithm that gives a competitive ratio of $1-\ell\cdot e^{-\Theta\left(\frac{\left(k-\ell\right)^2}{k}\right)}$, which is asymptotically tight for $k-\ell=\Theta(\ell)$. For secretary settings, we devise an algorithm that obtains a competitive ratio of $1-\ell e^{-\frac{k-8\ell}{2+2\ln \ell}} - e^{-k/6}$, and show that no secretary algorithm obtains a better ratio than $1-e^{-k}$ (up to negligible terms). In passing, our results lead to an improvement of the results of Assaf et al. [2000] for $1-out-of-k$ prophet scenarios. Beyond the contribution to online algorithms and optimal stopping theory, our results have implications to mechanism design. In particular, we use our prophet algorithms to derive {\em overbooking} mechanisms with good welfare and revenue guarantees; these are mechanisms that sell more items than the seller's capacity, then allocate to the agents with the highest values among the selected agents.
Chat View PDF

Prophets and Secretaries with Overbooking

2018-01-01
Tomer Ezra , Michal Feldman , Ilan Nehama
The prophet and secretary problems demonstrate online scenarios involving the optimal stopping theory. In a typical prophet or secretary problem, selection decisions are assumed to be immediate and irrevocable. However, … The prophet and secretary problems demonstrate online scenarios involving the optimal stopping theory. In a typical prophet or secretary problem, selection decisions are assumed to be immediate and irrevocable. However, many online settings accommodate some degree of revocability. To study such scenarios, we introduce the $\ell-out-of-k$ setting, where the decision maker can select up to $k$ elements immediately and irrevocably, but her performance is measured by the top $\ell$ elements in the selected set. Equivalently, the decision makes can hold up to $\ell$ elements at any given point in time, but can make up to $k-\ell$ returns as new elements arrive. We give upper and lower bounds on the competitive ratio of $\ell$-out-of-$k$ prophet and secretary scenarios. These include a single-sample prophet algorithm that gives a competitive ratio of $1-\ell\cdot e^{-\Theta\left(\frac{\left(k-\ell\right)^2}{k}\right)}$, which is asymptotically tight for $k-\ell=\Theta(\ell)$. For secretary settings, we devise an algorithm that obtains a competitive ratio of $1-\ell e^{-\frac{k-8\ell}{2+2\ln \ell}} - e^{-k/6}$, and show that no secretary algorithm obtains a better ratio than $1-e^{-k}$ (up to negligible terms). In passing, our results lead to an improvement of the results of Assaf et al. [2000] for $1-out-of-k$ prophet scenarios. Beyond the contribution to online algorithms and optimal stopping theory, our results have implications to mechanism design. In particular, we use our prophet algorithms to derive {\em overbooking} mechanisms with good welfare and revenue guarantees; these are mechanisms that sell more items than the seller's capacity, then allocate to the agents with the highest values among the selected agents.
Chat View PDF

Prophet Secretary: Surpassing the $1-1/e$ Barrier

2017-11-06
Yossi Azar , Ashish Chiplunkar , Haim Kaplan
In the Prophet Secretary problem, samples from a known set of probability distributions arrive one by one in a uniformly random order, and an algorithm must irrevocably pick one of … In the Prophet Secretary problem, samples from a known set of probability distributions arrive one by one in a uniformly random order, and an algorithm must irrevocably pick one of the samples as soon as it arrives. The goal is to maximize the expected value of the sample picked relative to the expected maximum of the distributions. This is one of the most simple and fundamental problems in online decision making that models the process selling one item to a sequence of costumers. For a closely related problem called the Prophet Inequality where the order of the random variables is adversarial, it is known that one can achieve in expectation $1/2$ of the expected maximum, and no better ratio is possible. For the Prophet Secretary problem, that is, when the variables arrive in a random order, Esfandiari et al. (ESA 2015) showed that one can actually get $1-1/e$ of the maximum. The $1-1/e$ bound was recently extended to more general settings (Ehsani et al., 2017). Given these results, one might be tempted to believe that $1-1/e$ is the correct bound. We show that this is not the case by providing an algorithm for the Prophet Secretary problem that beats the $1-1/e$ bound and achieves $1-1/e+1/400$ of the optimum value. We also prove a hardness result on the performance of algorithms under a natural restriction which we call deterministic distribution-insensitivity.
Chat View PDF

Prophet Secretary: Surpassing the $1-1/e$ Barrier

2017-01-01
Yossi Azar , Ashish Chiplunkar , Haim Kaplan
In the Prophet Secretary problem, samples from a known set of probability distributions arrive one by one in a uniformly random order, and an algorithm must irrevocably pick one of … In the Prophet Secretary problem, samples from a known set of probability distributions arrive one by one in a uniformly random order, and an algorithm must irrevocably pick one of the samples as soon as it arrives. The goal is to maximize the expected value of the sample picked relative to the expected maximum of the distributions. This is one of the most simple and fundamental problems in online decision making that models the process selling one item to a sequence of costumers. For a closely related problem called the Prophet Inequality where the order of the random variables is adversarial, it is known that one can achieve in expectation $1/2$ of the expected maximum, and no better ratio is possible. For the Prophet Secretary problem, that is, when the variables arrive in a random order, Esfandiari et al.\ (ESA 2015) showed that one can actually get $1-1/e$ of the maximum. The $1-1/e$ bound was recently extended to more general settings (Ehsani et al., 2017). Given these results, one might be tempted to believe that $1-1/e$ is the correct bound. We show that this is not the case by providing an algorithm for the Prophet Secretary problem that beats the $1-1/e$ bound and achieves $1-1/e+1/400$ of the optimum value. We also prove a hardness result on the performance of algorithms under a natural restriction which we call deterministic distribution-insensitivity.
Chat View PDF

Prophet Secretary

2015-07-05
Hossein Esfandiari , MohammadTaghi Hajiaghayi , Vahid Liaghat +1 more
Optimal stopping theory is a powerful tool for analyzing scenarios such as online auctions in which we generally require optimizing an objective function over the space of stopping rules for … Optimal stopping theory is a powerful tool for analyzing scenarios such as online auctions in which we generally require optimizing an objective function over the space of stopping rules for an allocation process under uncertainty. Perhaps the most classic problems of stopping theory are the prophet inequality problem and the secretary problem. The classical prophet inequality states that by choosing the same threshold OPT/2 for every step, one can achieve the tight competitive ratio of 0.5. On the other hand, for the basic secretary problem, the optimal strategy achieves the tight competitive ratio of 1/e. In this paper, we introduce Prophet Secretary, a natural combination of the prophet inequality and the secretary problems. An example motivation for our problem is as follows. Consider a seller that has an item to sell on the market to a set of arriving customers. The seller knows the types of customers that may be interested in the item and he has a price distribution for each type: the price offered by a customer of a type is anticipated to be drawn from the corresponding distribution. However, the customers arrive in a random order. Upon the arrival of a customer, the seller makes an irrevocable decision whether to sell the item at the offered price. We address the question of finding a strategy for selling the item at a high price. We show that by using a uniform threshold one cannot break the 0.5 barrier. However, we show that i) using n distinct non-adaptive thresholds one can obtain a competitive ratio that goes to (1-1/e) as n grows; and ii) no online algorithm can achieve a competitive ratio better than 0.75. Our results improve the (asymptotic) approximation guarantee of single-item sequential posted pricing mechanisms from 0.5 to (1-1/e) when the order of agents (customers) is chosen randomly.
Chat View PDF

Prophet Secretary

2015-01-01
Hossein Esfandiari , MohammadTaghi Hajiaghayi , Vahid Liaghat +1 more
Optimal stopping theory is a powerful tool for analyzing scenarios such as online auctions in which we generally require optimizing an objective function over the space of stopping rules for … Optimal stopping theory is a powerful tool for analyzing scenarios such as online auctions in which we generally require optimizing an objective function over the space of stopping rules for an allocation process under uncertainty. Perhaps the most classic problems of stopping theory are the prophet inequality problem and the secretary problem. The classical prophet inequality states that by choosing the same threshold OPT/2 for every step, one can achieve the tight competitive ratio of 0.5. On the other hand, for the basic secretary problem, the optimal strategy achieves the tight competitive ratio of 1/e. In this paper, we introduce Prophet Secretary, a natural combination of the prophet inequality and the secretary problems. An example motivation for our problem is as follows. Consider a seller that has an item to sell on the market to a set of arriving customers. The seller knows the types of customers that may be interested in the item and he has a price distribution for each type: the price offered by a customer of a type is anticipated to be drawn from the corresponding distribution. However, the customers arrive in a random order. Upon the arrival of a customer, the seller makes an irrevocable decision whether to sell the item at the offered price. We address the question of finding a strategy for selling the item at a high price. We show that by using a uniform threshold one cannot break the 0.5 barrier. However, we show that i) using n distinct non-adaptive thresholds one can obtain a competitive ratio that goes to (1-1/e) as n grows; and ii) no online algorithm can achieve a competitive ratio better than 0.75. Our results improve the (asymptotic) approximation guarantee of single-item sequential posted pricing mechanisms from 0.5 to (1-1/e) when the order of agents (customers) is chosen randomly.
Chat View PDF

The Competition Complexity of Prophet Secretary

2024-11-16
Tomer Ezra , Tamar Garbuz
We study the classic single-choice prophet secretary problem through a resource augmentation lens. Our goal is to bound the $(1-\epsilon)$-competition complexity for different classes of online algorithms. This metric asks … We study the classic single-choice prophet secretary problem through a resource augmentation lens. Our goal is to bound the $(1-\epsilon)$-competition complexity for different classes of online algorithms. This metric asks for the smallest $k$ such that the expected value of the online algorithm on $k$ copies of the original instance, is at least a $(1 - \epsilon)$-approximation to the expected offline optimum on the original instance (without added copies). We consider four natural classes of online algorithms: single-threshold, time-based threshold, activation-based, and general algorithms. We show that for single-threshold algorithms the $(1-\epsilon)$-competition complexity is $\Theta(\ln(\frac{1}{\epsilon}))$ (as in the i.i.d. case). Additionally, we demonstrate that time-based threshold and activation-based algorithms (which cover all previous approaches for obtaining competitive-ratios for the classic prophet secretary problem) yield a sub-optimal $(1-\epsilon)$-competition complexity of $\Theta\left(\frac{\ln(\frac{1}{\epsilon})}{\ln\ln(\frac{1}{\epsilon})}\right)$, which is strictly better than the class of single-threshold algorithms. Finally, we find that the $(1-\epsilon)$-competition complexity of general adaptive algorithms is $\Theta(\sqrt{\ln(\frac{1}{\epsilon})})$, which is in sharp contrast to $\Theta(\ln\ln(\frac{1}{\epsilon}))$ in the i.i.d. case.
Chat View PDF

Tight Guarantees for Static Threshold Policies in the Prophet Secretary Problem

2021-01-01
Nick Arnosti , Will Ma
In the prophet secretary problem, $n$ values are drawn independently from known distributions, and presented in a uniformly random order. A decision-maker must accept or reject each value when it … In the prophet secretary problem, $n$ values are drawn independently from known distributions, and presented in a uniformly random order. A decision-maker must accept or reject each value when it is presented, and may accept at most $k$ values in total. The objective is to maximize the expected sum of accepted values. We analyze the performance of static threshold policies, which accept the first $k$ values exceeding a fixed threshold (or all such values, if fewer than $k$ exist). We show that an appropriate threshold guarantees $\gamma_k = 1 - e^{-k}k^k/k!$ times the value of the offline optimal solution. Note that $\gamma_1 = 1-1/e$, and by Stirling's approximation $\gamma_k \approx 1-1/\sqrt{2 \pi k}$. This represents the best-known guarantee for the prophet secretary problem for all $k>1$, and is tight for all $k$ for the class of static threshold policies. We provide two simple methods for setting the threshold. Our first method sets a threshold such that $k \cdot \gamma_k$ values are accepted in expectation, and offers an optimal guarantee for all $k$. Our second sets a threshold such that the expected number of values exceeding the threshold is equal to $k$. This approach gives an optimal guarantee if $k > 4$, but gives sub-optimal guarantees for $k \le 4$. Our proofs use a new result for optimizing sums of independent Bernoulli random variables, which extends a classical result of Hoeffding (1956) and is likely to be of independent interest. Finally, we note that our methods for setting thresholds can be implemented under limited information about agents' values.
Chat View PDF

Sample-driven optimal stopping: From the secretary problem to the i.i.d. prophet inequality

2020-01-01
José R. Correa , Andrés Cristi , Boris Epstein +1 more
We take a unifying approach to single selection optimal stopping problems with random arrival order and independent sampling of items. In the problem we consider, a decision maker (DM) initially … We take a unifying approach to single selection optimal stopping problems with random arrival order and independent sampling of items. In the problem we consider, a decision maker (DM) initially gets to sample each of $N$ items independently with probability $p$, and can observe the relative rankings of these sampled items. Then, the DM faces the remaining items in an online fashion, observing the relative rankings of all revealed items. While scanning the sequence the DM makes irrevocable stop/continue decisions and her reward for stopping the sequence facing the item with rank $i$ is $Y_i$. The goal of the DM is to maximize her reward. We start by studying the case in which the values $Y_i$ are known to the DM, and then move to the case in which these values are adversarial. For the former case, we write the natural linear program that captures the performance of an algorithm, and take its continuous limit. We prove a structural result about this continuous limit, which allows us to reduce the problem to a relatively simple real optimization problem. We establish that the optimal algorithm is given by a sequence of thresholds $t_1\le t_2\le\cdots$ such that the DM should stop if seeing an item with current ranking $i$ after time $t_i$. Additionally we are able to recover several classic results in the area such as those for secretary problem and the minimum ranking problem. For the adversarial case, we obtain a similar linear program with an additional stochastic dominance constraint. Using the same machinery we are able to pin down the optimal competitive ratios for all values of $p$. Notably, we prove that as $p$ approaches 1, our guarantee converges linearly to 0.745, matching that of the i.i.d.~prophet inequality. Also interesting is the case $p=1/2$, where our bound evaluates to $0.671$, which improves upon the state of the art.
Chat View PDF

The Two-Sided Game of Googol and Sample-Based Prophet Inequalities

2019-07-13
José R. Correa , Andrés Cristi , Boris Epstein +1 more
The secretary problem or the game of Googol are classic models for online selection problems that have received significant attention in the last five decades. We consider a variant of … The secretary problem or the game of Googol are classic models for online selection problems that have received significant attention in the last five decades. We consider a variant of the problem and explore its connections to data-driven online selection. Specifically, we are given $n$ cards with arbitrary non-negative numbers written on both sides. The cards are randomly placed on $n$ consecutive positions on a table, and for each card, the visible side is also selected at random. The player sees the visible side of all cards and wants to select the card with the maximum hidden value. To this end, the player flips the first card, sees its hidden value and decides whether to pick it or drop it and continue with the next card. We study algorithms for two natural objectives. In the first one, as in the secretary problem, the player wants to maximize the probability of selecting the maximum hidden value. We show that this can be done with probability at least $0.45292$. In the second one, similar to the prophet inequality, the player maximizes the expectation of the selected hidden value. We show a guarantee of at least $0.63518$ with respect to the expected maximum hidden value. Our algorithms result from combining three basic strategies. One is to stop whenever we see a value larger than the initial $n$ visible numbers. The second one is to stop the first time the last flipped card's value is the largest of the currently $n$ visible numbers in the table. And the third one is similar to the latter but it additionally requires that the last flipped value is larger than the value on the other side of its card. We apply our results to the prophet secretary problem with unknown distributions, but with access to a single sample from each distribution. Our guarantee improves upon $1-1/e$ for this problem, which is the currently best known guarantee and only works for the i.i.d. case.
Chat View PDF

The Two-Sided Game of Googol and Sample-Based Prophet Inequalities

2019-01-01
José R. Correa , Andrés Cristi , Boris Epstein +1 more
The secretary problem or the game of Googol are classic models for online selection problems that have received significant attention in the last five decades. We consider a variant of … The secretary problem or the game of Googol are classic models for online selection problems that have received significant attention in the last five decades. We consider a variant of the problem and explore its connections to data-driven online selection. Specifically, we are given $n$ cards with arbitrary non-negative numbers written on both sides. The cards are randomly placed on $n$ consecutive positions on a table, and for each card, the visible side is also selected at random. The player sees the visible side of all cards and wants to select the card with the maximum hidden value. To this end, the player flips the first card, sees its hidden value and decides whether to pick it or drop it and continue with the next card. We study algorithms for two natural objectives. In the first one, as in the secretary problem, the player wants to maximize the probability of selecting the maximum hidden value. We show that this can be done with probability at least $0.45292$. In the second one, similar to the prophet inequality, the player maximizes the expectation of the selected hidden value. We show a guarantee of at least $0.63518$ with respect to the expected maximum hidden value. Our algorithms result from combining three basic strategies. One is to stop whenever we see a value larger than the initial $n$ visible numbers. The second one is to stop the first time the last flipped card's value is the largest of the currently $n$ visible numbers in the table. And the third one is similar to the latter but it additionally requires that the last flipped value is larger than the value on the other side of its card. We apply our results to the prophet secretary problem with unknown distributions, but with access to a single sample from each distribution. Our guarantee improves upon $1-1/e$ for this problem, which is the currently best known guarantee and only works for the i.i.d. case.
Chat View PDF

The two-sided game of googol and sample-based prophet inequalities

2020-01-05
José R. Correa , Andrés Cristi , Boris Epstein +1 more
The secretary problem or the game of Googol are classic models for online selection problems that have received significant attention in the last five decades. In this paper we consider … The secretary problem or the game of Googol are classic models for online selection problems that have received significant attention in the last five decades. In this paper we consider a variant of the problem and explore its connections to data-driven online selection. Specifically, we are given n cards with arbitrary nonnegative numbers written on both sides. The cards are randomly placed on n consecutive positions on a table, and for each card, the visible side is also selected at random. The player sees the visible side of all cards and wants to select the card with the maximum hidden value. To this end, the player flips the first card, sees its hidden value and decides whether to pick it or drop it and continue with the next card. We study algorithms for two natural objectives. In the first one, similar to the secretary problem, the player wants to maximize the probability of selecting the maximum hidden value. We show that this can be done with probability at least 0.45292. In the second objective, similar to the prophet inequality, the player wants to maximize the expectation of the selected hidden value. Here we show a guarantee of at least 0.63518 with respect to the expected maximum hidden value. Our algorithms result from combining three basic strategies. One is to stop whenever we see a value larger than the initial n visible numbers. The second one is to stop the first time the last flipped card's value is the largest of the currently n visible numbers in the table. And the third one is similar to the latter but to stop it additionally requires that the last flipped value is larger than the value on the other side of its card. We apply our results to the prophet secretary problem with unknown distributions, but with access to a single sample from each distribution. In particular, our guarantee improves upon 1 − 1/e for this problem, which is the currently best known guarantee and only works for the i.i.d. prophet inequality with samples.

Prophet Secretary Against the Online Optimal

2023-01-01
Paul Dütting , Evangelia Gergatsouli , Rojin Rezvan +2 more
We study the prophet secretary problem, a well-studied variant of the classic prophet inequality, where values are drawn from independent known distributions but arrive in uniformly random order. Upon seeing … We study the prophet secretary problem, a well-studied variant of the classic prophet inequality, where values are drawn from independent known distributions but arrive in uniformly random order. Upon seeing a value at each step, the decision-maker has to either select it and stop or irrevocably discard it. Traditionally, the chosen benchmark is the expected reward of the prophet, who knows all the values in advance and can always select the maximum one. %% In this work, we study the prophet secretary problem against a less pessimistic but equally well-motivated benchmark; the \emph{online} optimal. Here, the main goal is to find polynomial-time algorithms that guarantee near-optimal expected reward. As a warm-up, we present a quasi-polynomial time approximation scheme (QPTAS) achieving a $(1-\e)$-approximation in $O(n^{\text{poly} \log n\cdot f(\e)})$ time through careful discretization and non-trivial bundling processes. Using the toolbox developed for the QPTAS, coupled with a novel \emph{frontloading} technique that enables us to reduce the number of decisions we need to make, we are able to remove the dependence on $n$ in the exponent and obtain a polynomial time approximation scheme (PTAS) for this problem.
Chat View PDF

Prophets, Secretaries, and Maximizing the Probability of Choosing the Best

2019-10-09
Hossein Esfandiari , MohammadTaghi Hajiaghayi , Brendan Lucier +1 more
Suppose a customer is faced with a sequence of fluctuating prices, such as for airfare or a product sold by a large online retailer. Given distributional information about what price … Suppose a customer is faced with a sequence of fluctuating prices, such as for airfare or a product sold by a large online retailer. Given distributional information about what price they might face each day, how should they choose when to purchase in order to maximize the likelihood of getting the best price in retrospect? This is related to the classical secretary problem, but with values drawn from known distributions. In their pioneering work, Gilbert and Mosteller [\textit{J. Amer. Statist. Assoc. 1966}] showed that when the values are drawn i.i.d., there is a thresholding algorithm that selects the best value with probability approximately $0.5801$. However, the more general problem with non-identical distributions has remained unsolved. In this paper we provide an algorithm for the case of non-identical distributions that selects the maximum element with probability $1/e$, and we show that this is tight. We further show that if the observations arrive in a random order, this barrier of $1/e$ can be broken using a static threshold algorithm, and we show that our success probability is the best possible for any single-threshold algorithm under random observation order. Moreover, we prove that one can achieve a strictly better success probability using more general multi-threshold algorithms, unlike the non-random-order case. Along the way, we show that the best achievable success probability for the random-order case matches that of the i.i.d. case, which is approximately $0.5801$, under a no-superstars condition that no single distribution is very likely ex ante to generate the maximum value. We also extend our results to the problem of selecting one of the $k$ best values.
Chat View PDF

Prophets, Secretaries, and Maximizing the Probability of Choosing the Best

2019-01-01
Hossein Esfandiari , MohammadTaghi Hajiaghayi , Brendan Lucier +1 more
Suppose a customer is faced with a sequence of fluctuating prices, such as for airfare or a product sold by a large online retailer. Given distributional information about what price … Suppose a customer is faced with a sequence of fluctuating prices, such as for airfare or a product sold by a large online retailer. Given distributional information about what price they might face each day, how should they choose when to purchase in order to maximize the likelihood of getting the best price in retrospect? This is related to the classical secretary problem, but with values drawn from known distributions. In their pioneering work, Gilbert and Mosteller [\textit{J. Amer. Statist. Assoc. 1966}] showed that when the values are drawn i.i.d., there is a thresholding algorithm that selects the best value with probability approximately $0.5801$. However, the more general problem with non-identical distributions has remained unsolved. In this paper we provide an algorithm for the case of non-identical distributions that selects the maximum element with probability $1/e$, and we show that this is tight. We further show that if the observations arrive in a random order, this barrier of $1/e$ can be broken using a static threshold algorithm, and we show that our success probability is the best possible for any single-threshold algorithm under random observation order. Moreover, we prove that one can achieve a strictly better success probability using more general multi-threshold algorithms, unlike the non-random-order case. Along the way, we show that the best achievable success probability for the random-order case matches that of the i.i.d.\ case, which is approximately $0.5801$, under a "no-superstars" condition that no single distribution is very likely ex ante to generate the maximum value. We also extend our results to the problem of selecting one of the $k$ best values.
Chat View PDF

The Secretary Problem with Independent Sampling

2021-01-01
José R. Correa , Andrés Cristi , Laurent Feuilloley +2 more
In the secretary problem we are faced with an online sequence of elements with values. Upon seeing an element we have to make an irrevocable take-it-or-leave-it decision. The goal is … In the secretary problem we are faced with an online sequence of elements with values. Upon seeing an element we have to make an irrevocable take-it-or-leave-it decision. The goal is to maximize the probability of picking the element of maximum value. The most classic version of the problem is that in which the elements arrive in random order and their values are arbitrary. Here, the optimal algorithm picks the maximum value with probability at least 1/e. However, by varying the available information, new interesting problems arise. For instance, in the full information variant of the secretary problem the values are i.i.d. samples from a known distribution. Naturally, the best possible success probability increases and turns out to be approximately 0.58. Also, the case in which the arrival order is adversarial instead of random leads to interesting variants that have been considered in the literature.In this paper we study both the random order and adversarial order secretary problems with an additional twist. The values are arbitrary, but before starting the online sequence we independently sample each element with a fixed probability p. The sampled elements become our information or history set and the game is played over the remaining elements. We call these problems the random order secretary problem with p-sampling (ROSp for short) and the adversarial order secretary problem with p-sampling (AOSp for short). Our main result is to obtain best possible algorithms for both problems and all values of p. As p grows to 1 the obtained guarantees converge to the optimal guarantees in the full information case. In the adversarial order setting, the best possible algorithm turns out to be a simple fixed threshold algorithm in which the optimal threshold is a function of p only. Therefore, even knowledge of the total number of elements is unnecessary. Proving that this algorithm is optimal involves a novel technique, which boils down to analyzing a related game in a conflict graph over binary sequences. In the random order setting we prove that the best possible algorithm is characterized by a fixed sequence of time thresholds, dictating at which point in time we should start accepting a value that is both a maximum of the online sequence and has a given ranking within the sampled elements. Surprisingly, this sequence of time thresholds arises from a separable and convex optimization problem whose solution is independent of p.
Chat View PDF

Prophet Secretary for Combinatorial Auctions and Matroids

2017-01-01
Soheil Ehsani , MohammadTaghi Hajiaghayi , Thomas Keßelheim +1 more
The secretary and the prophet inequality problems are central to the field of Stopping Theory. Recently, there has been a lot of work in generalizing these models to multiple items … The secretary and the prophet inequality problems are central to the field of Stopping Theory. Recently, there has been a lot of work in generalizing these models to multiple items because of their applications in mechanism design. The most important of these generalizations are to matroids and to combinatorial auctions (extends bipartite matching). Kleinberg-Weinberg \cite{KW-STOC12} and Feldman et al. \cite{feldman2015combinatorial} show that for adversarial arrival order of random variables the optimal prophet inequalities give a $1/2$-approximation. For many settings, however, it's conceivable that the arrival order is chosen uniformly at random, akin to the secretary problem. For such a random arrival model, we improve upon the $1/2$-approximation and obtain $(1-1/e)$-approximation prophet inequalities for both matroids and combinatorial auctions. This also gives improvements to the results of Yan \cite{yan2011mechanism} and Esfandiari et al. \cite{esfandiari2015prophet} who worked in the special cases where we can fully control the arrival order or when there is only a single item. Our techniques are threshold based. We convert our discrete problem into a continuous setting and then give a generic template on how to dynamically adjust these thresholds to lower bound the expected total welfare.
Chat View PDF

Prophet Secretary for Combinatorial Auctions and Matroids

2024-11-12
Soheil Ehsani , MohammadTaghi Hajiaghayi , Thomas Keßelheim +1 more
The secretary and the prophet inequality problems are central to the field of Stopping Theory. Recently, there has been a lot of work in generalizing these models to multiple items … The secretary and the prophet inequality problems are central to the field of Stopping Theory. Recently, there has been a lot of work in generalizing these models to multiple items because of their applications in mechanism design. The most important of these generalizations are to matroids and to combinatorial auctions (extends bipartite matching). Kleinberg-Weinberg \cite{KW-STOC12} and Feldman et al. \cite{feldman2015combinatorial} show that for adversarial arrival order of random variables the optimal prophet inequalities give a $1/2$-approximation. For many settings, however, it's conceivable that the arrival order is chosen uniformly at random, akin to the secretary problem. For such a random arrival model, we improve upon the $1/2$-approximation and obtain $(1-1/e)$-approximation prophet inequalities for both matroids and combinatorial auctions. This also gives improvements to the results of Yan \cite{yan2011mechanism} and Esfandiari et al. \cite{esfandiari2015prophet} who worked in the special cases where we can fully control the arrival order or when there is only a single item. Our techniques are threshold based. We convert our discrete problem into a continuous setting and then give a generic template on how to dynamically adjust these thresholds to lower bound the expected total welfare.
Chat View PDF

Tight Guarantees for Static Threshold Policies in the Prophet Secretary Problem

2022-12-29
Nick Arnosti , Will Ma
In the prophet secretary problem, n values are drawn independently from known distributions and presented in a uniformly random order. A decision maker must accept or reject each value when … In the prophet secretary problem, n values are drawn independently from known distributions and presented in a uniformly random order. A decision maker must accept or reject each value when it is presented and may accept at most k values in total. The objective is to maximize the expected sum of accepted values. We analyze the performance of static threshold policies, which accept the first k values exceeding a fixed threshold (or all such values, if fewer than k exist). We show that an appropriate threshold guarantees [Formula: see text] times the value of the offline optimal solution. Note that [Formula: see text], and by Stirling’s approximation, [Formula: see text]. This represents the best-known guarantee for the prophet secretary problem for all k > 1 and is tight for all k for the class of static threshold policies. We provide two simple methods for setting the threshold. Our first method sets a threshold such that [Formula: see text] values are accepted in expectation, and offers an optimal guarantee for all k. Our second sets a threshold such that the expected number of values exceeding the threshold is equal to k. This approach gives an optimal guarantee if k > 4 but gives suboptimal guarantees for [Formula: see text]. Our proofs use a new result for optimizing sums of independent Bernoulli random variables, which extends a result of Hoeffding from 1956 and could be of independent interest. Supplemental Material: The online appendices are available at https://doi.org/10.1287/opre.2022.2419 .
Chat View PDF

Prophet Secretary Against the Online Optimal

2023-07-07
Paul Dütting , Evangelia Gergatsouli , Rojin Rezvan +2 more
We study the prophet secretary problem, a well-studied variant of the classic prophet inequality, where values are drawn from independent known distributions but arrive in uniformly random order. Upon seeing … We study the prophet secretary problem, a well-studied variant of the classic prophet inequality, where values are drawn from independent known distributions but arrive in uniformly random order. Upon seeing a value at each step, the decision-maker has to either select it and stop or irrevocably discard it. Traditionally, the chosen benchmark is the expected reward of the prophet, who knows all the values in advance and can always select the maximum one. In this work, we study the prophet secretary problem against a less pessimistic but equally well-motivated benchmark; the online optimal. Here, the main goal is to find polynomial-time algorithms that guarantee near-optimal expected reward. As a warm-up, we present a quasi-polynomial time approximation scheme (QPTAS) achieving a (1 − ε)-approximation in O(npoly log n· f(ε)) time through careful discretization and non-trivial bundling processes. Using the toolbox developed for the QPTAS, coupled with a novel frontloading technique that enables us to reduce the number of decisions we need to make, we are able to remove the dependence on n in the exponent and obtain a polynomial time approximation scheme (PTAS) for this problem.
Chat View PDF

Cited by (9)

Online Stochastic Max-Weight Matching: Prophet Inequality for Vertex and Edge Arrival Models

2020-07-09
Tomer Ezra , Michal Feldman , Nick Gravin +1 more
We provide prophet inequality algorithms for online weighted matching in general (non-bipartite) graphs, under two well-studied arrival models, namely edge arrival and vertex arrival. The weight of each edge is … We provide prophet inequality algorithms for online weighted matching in general (non-bipartite) graphs, under two well-studied arrival models, namely edge arrival and vertex arrival. The weight of each edge is drawn independently from an a-priori known probability distribution. Under edge arrival, the weight of each edge is revealed upon arrival, and the algorithm decides whether to include it in the matching or not. Under vertex arrival, the weights of all edges from the newly arriving vertex to all previously arrived vertices are revealed, and the algorithm decides which of these edges, if any, to include in the matching. To study these settings, we introduce a novel unified framework of batched prophet inequalities that captures online settings where elements arrive in batches; in particular it captures matching under the two aforementioned arrival models. Our algorithms rely on the construction of suitable online contention resolution schemes (OCRS). We first extend the framework of OCRS to batched-OCRS, we then establish a reduction from batched prophet inequality to batched OCRS, and finally we construct batched OCRSs with selectable ratios of 0.337 and 0.5 for edge and vertex arrival models, respectively. Both results improve the state of the art for the corresponding settings. For vertex arrival, our result is tight. Interestingly, pricing-based prophet inequalities with comparable competitive ratios are unknown.
Chat View PDF

Analyzing and Forecasting of COVID-19 Situation Using FbProphet Model Algorithms

2022-05-16
S. Geetha , M. Farida Begam , Ayush Dubey +2 more
SARS-CoV-2 (n-coronavirus) is a global pandemic that has killed millions of people all over the world. In severe situations, it can induce pneumonia and severe acute respiratory syndrome (SARS), which … SARS-CoV-2 (n-coronavirus) is a global pandemic that has killed millions of people all over the world. In severe situations, it can induce pneumonia and severe acute respiratory syndrome (SARS), which can lead to death. It's an asymptomatic sickness that makes life and work more difficult for us. This research focused on the current state of the coronavirus pandemic and forecasted the global situation, as well as its impacts and future status. The authors used the FbProphet model to forecast new covid cases and deaths for the month of August utilizing various information representation and machine learning algorithms. They hope the findings will aid scientists, researchers, and laypeople in predicting and analyzing the effects of the epidemic. Finally, they conclude that the virus's second wave was around four times stronger than the first. They also looked at the trajectory of COVID-19 instances (monthly and weekly) and discovered that the number of cases rises more during the weekdays, which could be due to the weekend lockout.

Choosing Behind the Veil: Tight Bounds for Identity-Blind Online Algorithms

2024-07-08
Tomer Ezra , Michal Feldman , Zhihao Gavin Tang
Chat View PDF

Online Stochastic Max-Weight Matching: prophet inequality for vertex and edge arrival models

2020-02-23
Tomer Ezra , Michal Feldman , Nick Gravin +1 more
We provide prophet inequality algorithms for online weighted matching in general (non-bipartite) graphs, under two well-studied arrival models, namely edge arrival and vertex arrival. The weight of each edge is … We provide prophet inequality algorithms for online weighted matching in general (non-bipartite) graphs, under two well-studied arrival models, namely edge arrival and vertex arrival. The weight of each edge is drawn independently from an a-priori known probability distribution. Under edge arrival, the weight of each edge is revealed upon arrival, and the algorithm decides whether to include it in the matching or not. Under vertex arrival, the weights of all edges from the newly arriving vertex to all previously arrived vertices are revealed, and the algorithm decides which of these edges, if any, to include in the matching. To study these settings, we introduce a novel unified framework of batched prophet inequalities that captures online settings where elements arrive in batches; in particular it captures matching under the two aforementioned arrival models. Our algorithms rely on the construction of suitable online contention resolution scheme (OCRS). We first extend the framework of OCRS to batched-OCRS, we then establish a reduction from batched prophet inequality to batched OCRS, and finally we construct batched OCRSs with selectable ratios of 0.337 and 0.5 for edge and vertex arrival models, respectively. Both results improve the state of the art for the corresponding settings. For the vertex arrival, our result is tight. Interestingly, a pricing-based prophet inequality with comparable competitive ratios is unknown.
Chat View PDF

On a Competitive Secretary Problem with Deferred Selections

2021-08-01
Tomer Ezra , Michal Feldman , Ron Kupfer
We study the secretary problem in multi-agent environments. In the standard secretary problem, a sequence of arbitrary awards arrive online, in a random order, and a single decision maker makes … We study the secretary problem in multi-agent environments. In the standard secretary problem, a sequence of arbitrary awards arrive online, in a random order, and a single decision maker makes an immediate and irrevocable decision whether to accept each award upon its arrival. The requirement to make immediate decisions arises in many cases due to an implicit assumption regarding competition. Namely, if the decision maker does not take the offered award immediately, it will be taken by someone else. We introduce a novel multi-agent secretary model, in which the competition is explicit. In our model, multiple agents compete over the arriving awards, but the decisions need not be immediate; instead, agents may select previous awards as long as they are available (i.e., not taken by another agent). If an award is selected by multiple agents, ties are broken either randomly or according to a global ranking. This induces a multi-agent game in which the time of selection is not enforced by the rules of the games, rather it is an important component of the agent's strategy. We study the structure and performance of equilibria in this game. For random tie breaking, we characterize the equilibria of the game, and show that the expected social welfare in equilibrium is nearly optimal, despite competition among the agents. For ranked tie breaking, we give a full characterization of equilibria in the 3-agent game, and show that as the number of agents grows, the winning probability of every agent under non-immediate selections approaches her winning probability under immediate selections.
Chat View PDF

Learning to Screen

2019-02-13
Alon Cohen , Avinatan Hassidim , Haim Kaplan +2 more
Imagine a large firm with multiple departments that plans a large recruitment. Candidates arrive one-by-one, and for each candidate the firm decides, based on her data (CV, skills, experience, etc), … Imagine a large firm with multiple departments that plans a large recruitment. Candidates arrive one-by-one, and for each candidate the firm decides, based on her data (CV, skills, experience, etc), whether to summon her for an interview. The firm wants to recruit the best candidates while minimizing the number of interviews. We model such scenarios as an assignment problem between items (candidates) and categories (departments): the items arrive one-by-one in an online manner, and upon processing each item the algorithm decides, based on its value and the categories it can be matched with, whether to retain or discard it (this decision is irrevocable). The goal is to retain as few items as possible while guaranteeing that the set of retained items contains an optimal matching. We consider two variants of this problem: (i) in the first variant it is assumed that the $n$ items are drawn independently from an unknown distribution $D$. (ii) In the second variant it is assumed that before the process starts, the algorithm has an access to a training set of $n$ items drawn independently from the same unknown distribution (e.g. data of candidates from previous recruitment seasons). We give tight bounds on the minimum possible number of retained items in each of these variants. These results demonstrate that one can retain exponentially less items in the second variant (with the training set).
Chat View PDF

Bayesian and Randomized Clock Auctions

2022-07-12
Michal Feldman , Vasilis Gkatzelis , Nick Gravin +1 more
In a single-parameter mechanism design problem, a provider is looking to sell some service to a group of potential buyers. Each buyer i has a private value vi for receiving … In a single-parameter mechanism design problem, a provider is looking to sell some service to a group of potential buyers. Each buyer i has a private value vi for receiving this service, and some feasibility constraint restricts which subsets of buyers can be served simultaneously. Recent work in economics introduced (deferred-acceptance) clock auctions as a superior class of auctions for this problem, due to their transparency, simplicity, and very strong incentive guarantees. Subsequent work in computer science focused on evaluating these auctions with respect to their social welfare approximation guarantees, leading to strong impossibility results: in the absence of prior information regarding the buyers' values, no deterministic clock auction can achieve a bounded approximation, even for simple feasibility constraints with only two maximal feasible sets.
Chat View PDF

On a Competitive Secretary Problem with Deferred Selections

2020-07-14
Tomer Ezra , Michal Feldman , Ron Kupfer
We study secretary problems in settings with multiple agents. In the standard secretary problem, a sequence of arbitrary awards arrive online, in a random order, and a single decision maker … We study secretary problems in settings with multiple agents. In the standard secretary problem, a sequence of arbitrary awards arrive online, in a random order, and a single decision maker makes an immediate and irrevocable decision whether to accept each award upon its arrival. The requirement to make immediate decisions arises in many cases due to an implicit assumption regarding competition. Namely, if the decision maker does not take the offered award immediately, it will be taken by someone else. The novelty in this paper is in introducing a multi-agent model in which the competition is endogenous. In our model, multiple agents compete over the arriving awards, but the decisions need not be immediate; instead, agents may select previous awards as long as they are available (i.e., not taken by another agent). If an award is selected by multiple agents, ties are broken either randomly or according to a global ranking. This induces a multi-agent game in which the time of selection is not enforced by the rules of the games, rather it is an important component of the agent's strategy. We study the structure and performance of equilibria in this game. For random tie breaking, we characterize the equilibria of the game, and show that the expected social welfare in equilibrium is nearly optimal, despite competition among the agents. For ranked tie breaking, we give a full characterization of equilibria in the 3-agent game, and show that as the number of agents grows, the winning probability of every agent under non-immediate selections approaches her winning probability under immediate selections.

Prophet Inequalities with Cancellation Costs

2024-06-10
Farbod Ekbatani , Rad Niazadeh , Pranav Nuti +1 more
Most of the literature on online algorithms and sequential decision-making focuses on settings with "irrevocable decisions" where the algorithm's decision upon arrival of the new input is set in stone … Most of the literature on online algorithms and sequential decision-making focuses on settings with "irrevocable decisions" where the algorithm's decision upon arrival of the new input is set in stone and can never change in the future. One canonical example is the classic prophet inequality problem, where realizations of a sequence of independent random variables X1, X2,… with known distributions are drawn one by one and a decision maker decides when to stop and accept the arriving random variable, with the goal of maximizing the expected value of their pick. We consider "prophet inequalities with recourse" in the linear buyback cost setting, where after accepting a variable Xi, we can still discard Xi later and accept another variable Xj, at a buyback cost of f × Xi. The goal is to maximize the expected net reward, which is the value of the final accepted variable minus the total buyback cost. Our first main result is an optimal prophet inequality in the regime of f ≥ 1, where we prove that we can achieve an expected reward 1+f/1+2f times the expected offline optimum. The problem is still open for 0<f<1 and we give some partial results in this regime. In particular, as our second main result, we characterize the asymptotic behavior of the competitive ratio for small f and provide almost matching upper and lower bounds that show a factor of 1−Θ(flog(1/f)). Our results are obtained by two fundamentally different approaches: One is inspired by various proofs of the classical prophet inequality, while the second is based on combinatorial optimization techniques involving LP duality, flows, and cuts.
Chat View PDF

References (0)