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

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

Authors

José R. Correa, Andrés Cristi, Boris Epstein, José A. Soto
Type: Book-Chapter
Publication Date: 2019-12-23
Citations: 14
DOI: https://doi.org/10.1137/1.9781611975994.127

Abstract

Previous chapter Next chapter Full AccessProceedings Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms (SODA)The Two-Sided Game of Googol and Sample-Based Prophet InequalitiesJosé R. Correa, Andrés Cristi, Boris Epstein, and José A. SotoJosé R. Correa, Andrés Cristi, Boris Epstein, and José A. Sotopp.2066 - 2081Chapter DOI:https://doi.org/10.1137/1.9781611975994.127PDFBibTexSections ToolsAdd to favoritesExport CitationTrack CitationsEmail SectionsAboutAbstract 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. Previous chapter Next chapter RelatedDetails Published:2020eISBN:978-1-61197-599-4 https://doi.org/10.1137/1.9781611975994Book Series Name:ProceedingsBook Code:PRDA20Book Pages:xxii + 3011

Locations

  • arXiv (Cornell University)
    View PDF
  • Society for Industrial and Applied Mathematics eBooks
    View

Ask a Question About This Paper

Summary

Login to see paper summary

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.

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.

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.

Single-Sample Prophet Inequalities via Greedy-Ordered Selection

2022-01-01
Constantine Caramanis , Paul Dütting , Matthew Faw +6 more
Previous chapter Next chapter Full AccessProceedings Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)Single-Sample Prophet Inequalities via Greedy-Ordered SelectionConstantine Caramanis, Paul Dütting, Matthew Faw, Federico Fusco, Philip … Previous chapter Next chapter Full AccessProceedings Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)Single-Sample Prophet Inequalities via Greedy-Ordered SelectionConstantine Caramanis, Paul Dütting, Matthew Faw, Federico Fusco, Philip Lazos, Stefano Leonardi, Orestis Papadigenopoulos, Emmanouil Pountourakis, and Rebecca ReiffenhäuserConstantine Caramanis, Paul Dütting, Matthew Faw, Federico Fusco, Philip Lazos, Stefano Leonardi, Orestis Papadigenopoulos, Emmanouil Pountourakis, and Rebecca Reiffenhäuserpp.1298 - 1325Chapter DOI:https://doi.org/10.1137/1.9781611977073.54PDFBibTexSections ToolsAdd to favoritesExport CitationTrack CitationsEmail SectionsAboutAbstract We study single-sample prophet inequalities (SSPIs), i.e., prophet inequalities where only a single sample from each prior distribution is available. Besides a direct, and optimal, SSPI for the basic single choice problem [Rubinstein et al., 2020], most existing SSPI results were obtained via an elegant, but inherently lossy reduction to order-oblivious secretary (OOS) policies [Azar et al., 2014]. Motivated by this discrepancy, we develop an intuitive and versatile greedy-based technique that yields SSPIs directly rather than through the reduction to OOSs. Our results can be seen as generalizing and unifying a number of existing results in the area of prophet and secretary problems. Our algorithms significantly improve on the competitive guarantees for a number of interesting scenarios (including general matching with edge arrivals, bipartite matching with vertex arrivals, and certain matroids), and capture new settings (such as budget additive combinatorial auctions). Complementing our algorithmic results, we also consider mechanism design variants. Finally, we analyze the power and limitations of different SSPI approaches by providing a partial converse to the reduction from SSPI to OOS given by Azar et al. Previous chapter Next chapter RelatedDetails Published:2022eISBN:978-1-61197-707-3 https://doi.org/10.1137/1.9781611977073Book Series Name:ProceedingsBook Code:PRDA22Book Pages:xvii + 3771
View PDF Chat

The Two-Sided Game Of Googol And Sample-Based Prophet Inequalities

2020-01-01
Epstein Von Loebenstein , Boris Alexander

Prophet Inequality: Order selection beats random order

2022-01-01
Archit Bubna , Ashish Chiplunkar
In the prophet inequality problem, a gambler faces a sequence of items arriving online with values drawn independently from known distributions. On seeing an item, the gambler must choose whether … In the prophet inequality problem, a gambler faces a sequence of items arriving online with values drawn independently from known distributions. On seeing an item, the gambler must choose whether to accept its value as her reward and quit the game, or reject it and continue. The gambler's aim is to maximize her expected reward relative to the expected maximum of the values of all items. Since the seventies, a tight bound of 1/2 has been known for this competitive ratio in the setting where the items arrive in an adversarial order (Krengel and Sucheston, 1977, 1978). However, the optimum ratio still remains unknown in the order selection setting, where the gambler selects the arrival order, as well as in prophet secretary, where the items arrive in a random order. Moreover, it is not even known whether a separation exists between the two settings. In this paper, we show that the power of order selection allows the gambler to guarantee a strictly better competitive ratio than if the items arrive randomly. For the order selection setting, we identify an instance for which Peng and Tang's (FOCS'22) state-of-the-art algorithm performs no better than their claimed competitive ratio of (approximately) 0.7251, thus illustrating the need for an improved approach. We therefore extend their design and provide a more general algorithm design framework, using which we show that their ratio can be beaten, by designing a 0.7258-competitive algorithm. For the random order setting, we improve upon Correa, Saona and Ziliotto's (SODA'19) 0.732-hardness result to show a hardness of 0.7254 for general algorithms - even in the setting where the gambler knows the arrival order beforehand, thus establishing a separation between the order selection and random order settings.
View PDF Chat

Prophet Secretary Through Blind Strategies

2018-01-01
José R. Correa , Raimundo Saona , Bruno Ziliotto
In the classic prophet inequality, samples from independent random variables arrive online. A gambler that knows the distributions must decide at each point in time whether to stop and pick … In the classic prophet inequality, samples from independent random variables arrive online. A gambler that knows the distributions must decide at each point in time whether to stop and pick the current sample or to continue and lose that sample forever. The goal of the gambler is to maximize the expected value of what she picks and the performance measure is the worst case ratio between the expected value the gambler gets and what a prophet, that sees all the realizations in advance, gets. In the late seventies, Krengel and Sucheston, and Gairing (1977) established that this worst case ratio is a universal constant equal to 1/2. In the last decade prophet inequalities has resurged as an important problem due to its connections to posted price mechanisms, frequently used in online sales. A very interesting variant is the Prophet Secretary problem, in which the only difference is that the samples arrive in a uniformly random order. For this variant several algorithms achieve a constant of 1-1/e and very recently this barrier was slightly improved. This paper analyzes strategies that set a nonincreasing sequence of thresholds to be applied at different times. The gambler stops the first time a sample surpasses the corresponding threshold. Specifically we consider a class of strategies called blind quantile strategies. They consist in fixing a function which is used to define a sequence of thresholds once the instance is revealed. Our main result shows that they can achieve a constant of 0.665, improving upon the best known result of Azar et al. (2018), and on Beyhaghi et al. (2018) (order selection). Our proof analyzes precisely the underlying stopping time distribution, relying on Schur-convexity theory. We further prove that blind strategies cannot achieve better than 0.675. Finally we prove that no algorithm for the gambler can achieve better than 0.732.
View PDF Chat

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.
View PDF Chat

Prophet Inequalities with Limited Information

2013-12-18
Pablo Azar , Robert Kleinberg , S. Matthew Weinberg
Previous chapter Next chapter Full AccessProceedings Proceedings of the 2014 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)Prophet Inequalities with Limited InformationPablo D. Azar, Robert Kleinberg, and S. Matthew WeinbergPablo D. … Previous chapter Next chapter Full AccessProceedings Proceedings of the 2014 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)Prophet Inequalities with Limited InformationPablo D. Azar, Robert Kleinberg, and S. Matthew WeinbergPablo D. Azar, Robert Kleinberg, and S. Matthew Weinbergpp.1358 - 1377Chapter DOI:https://doi.org/10.1137/1.9781611973402.100PDFBibTexSections ToolsAdd to favoritesExport CitationTrack CitationsEmail SectionsAboutAbstract In the classical prophet inequality, a gambler observes a sequence of stochastic rewards V1, …, Vn and must decide, for each reward Vi, whether to keep it and stop the game or to forfeit the reward forever and reveal the next value Vi. The gambler's goal is to obtain a constant fraction of the expected reward that the optimal offline algorithm would get. Recently, prophet inequalities have been generalized to settings where the gambler can choose k items, and, more generally, where he can choose any independent set in a matroid. However, all the existing algorithms require the gambler to know the distribution from which the rewards V1, …, Vn are drawn. The assumption that the gambler knows the distribution from which V1, …, Vn are drawn is very strong. Instead, we work with the much simpler assumption that the gambler only knows a few samples from this distribution. We construct the first single-sample prophet inequalities for many settings of interest, whose guarantees all match the best possible asymptotically, even with full knowledge of the distribution. Specifically, we provide a novel single-sample algorithm when the gambler can choose any k elements whose analysis is based on random walks with limited correlation. In addition, we provide a black-box method for converting specific types of solutions to the related secretary problem to single-sample prophet inequalities, and apply it to several existing algorithms. Finally, we provide a constant-sample prophet inequality for constant-degree bipartite matchings. In addition, we apply these results to design the first posted-price and multi-dimensional auction mechanisms with limited information in settings with asymmetric bidders. Connections between prophet inequalities and posted-price mechanisms are already known, but applying the existing framework requires knowledge of the underlying distributions, as well as the so-called "virtual values" even when the underlying prophet inequalities do not. We therefore provide an extension of this framework that bypasses virtual values altogether, allowing our mechanisms to take full advantage of the limited information required by our new prophet inequalities. Previous chapter Next chapter RelatedDetails Published:2014ISBN:978-1-61197-338-9eISBN:978-1-61197-340-2 https://doi.org/10.1137/1.9781611973402Book Series Name:ProceedingsBook Code:PRDA14Book Pages:viii + 1885
View PDF Chat

Prophet Inequality on I.I.D. Distributions: Beating 1-1/e with a Single Query

2022-01-01
Bo Li , Xiaowei Wu , Yutong Wu
In this work, we study the single-choice prophet inequality problem, where a gambler faces a sequence of~$n$ online i.i.d. random variables drawn from an unknown distribution. When a variable reveals … In this work, we study the single-choice prophet inequality problem, where a gambler faces a sequence of~$n$ online i.i.d. random variables drawn from an unknown distribution. When a variable reveals its value, the gambler needs to decide irrevocably whether or not to accept the value. The goal is to maximize the competitive ratio between the expected gain of the gambler and that of the maximum variable. It is shown by Correa et al. that when the distribution is unknown or only $o(n)$ uniform samples from the distribution are given, the best an algorithm can do is $1/e$-competitive. In contrast, when the distribution is known or $\Omega(n)$ uniform samples are given, the optimal competitive ratio of 0.7451 can be achieved. In this paper, we study a new model in which the algorithm has access to an oracle that answers quantile queries about the distribution and investigate to what extent we can use a small number of queries to achieve good competitive ratios. We first use the answers from the queries to implement the threshold-based algorithms and show that with two thresholds our algorithm achieves a competitive ratio of $0.6786$. Motivated by the two-threshold algorithm, we design the observe-and-accept algorithm that requires only a single query. This algorithm sets a threshold in the first phase by making a query and uses the maximum realization from the first phase as the threshold for the second phase. It can be viewed as a natural combination of the single-threshold algorithm and the algorithm for the secretary problem. By properly choosing the quantile to query and the break-point between the two phases, we achieve a competitive ratio of $0.6718$, beating the benchmark of $1-1/e$.

Sample-Driven Optimal Stopping: From the Secretary Problem to the i.i.d. Prophet Inequality

2023-04-17
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 are able to recover several classic results in the area, thus giving a unifying framework for single selection optimal stopping. For the latter, we pin down the optimal algorithm, obtaining the optimal competitive ratios for all values of p. Funding: This work was partially supported by The Center for Mathematical Modeling at the University of Chile (ANID FB210005), Grant Anillo Information and Computation in Market Design (ANID ACT210005), FONDECYT 1220054 and 1181180, and a Meta Research PhD Fellowship.
View PDF Chat

Competitive Analysis with a Sample and the Secretary Problem

2019-12-23
Haim Kaplan , David Naori , Danny Raz
Previous chapter Next chapter Full AccessProceedings Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms (SODA)Competitive Analysis with a Sample and the Secretary ProblemHaim Kaplan, David Naori, and Danny RazHaim … Previous chapter Next chapter Full AccessProceedings Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms (SODA)Competitive Analysis with a Sample and the Secretary ProblemHaim Kaplan, David Naori, and Danny RazHaim Kaplan, David Naori, and Danny Razpp.2082 - 2095Chapter DOI:https://doi.org/10.1137/1.9781611975994.128PDFBibTexSections ToolsAdd to favoritesExport CitationTrack CitationsEmail SectionsAboutAbstract We extend the standard online worst-case model to accommodate past experience which is available to the online player in many practical scenarios. We do this by revealing a random sample of the adversarial input to the online player ahead of time. The online player competes with the expected optimal value on the part of the input that arrives online. Our model bridges between existing online stochastic models (e.g., items are drawn i.i.d. from a distribution) and the online worst-case model. We also extend in a similar manner (by revealing a sample) the online random-order model. We study the classical secretary problem in our new models. In the worst-case model we present a simple online algorithm with optimal competitive-ratio for any sample size. In the random-order model, we also give a simple online algorithm with an almost tight competitive-ratio for small sample sizes. Interestingly, we prove that for a large enough sample, no algorithm can be simultaneously optimal both in the worst-cast and random-order models. Previous chapter Next chapter RelatedDetails Published:2020eISBN:978-1-61197-599-4 https://doi.org/10.1137/1.9781611975994Book Series Name:ProceedingsBook Code:PRDA20Book Pages:xxii + 3011
View PDF Chat

Prophet Secretary and Matching: the Significance of the Largest Item

2024-11-02
Ziyun Chen , Zhiyi Huang , Dongchen Li +1 more
The prophet secretary problem is a combination of the prophet inequality and the secretary problem, where elements are drawn from known independent distributions and arrive in uniformly random order. In … The prophet secretary problem is a combination of the prophet inequality and the secretary problem, where elements are drawn from known independent distributions and arrive in uniformly random order. In this work, we design 1) a $0.688$-competitive algorithm, that breaks the $0.675$ barrier of blind strategies (Correa, Saona, Ziliotto, 2021), and 2) a $0.641$-competitive algorithm for the prophet secretary matching problem, that breaks the $1-1/e\approx 0.632$ barrier for the first time. Our second result also applies to the query-commit model of weighted stochastic matching and improves the state-of-the-art ratio (Derakhshan and Farhadi, 2023).
View PDF Chat

Online Weighted Matching with a Sample

2022-01-01
Haim Kaplan , David Naori , Danny Raz
Previous chapter Next chapter Full AccessProceedings Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)Online Weighted Matching with a SampleHaim Kaplan, David Naori, and Danny RazHaim Kaplan, David … Previous chapter Next chapter Full AccessProceedings Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)Online Weighted Matching with a SampleHaim Kaplan, David Naori, and Danny RazHaim Kaplan, David Naori, and Danny Razpp.1247 - 1272Chapter DOI:https://doi.org/10.1137/1.9781611977073.52PDFBibTexSections ToolsAdd to favoritesExport CitationTrack CitationsEmail SectionsAboutAbstract We study the greedy-based online algorithm for edge-weighted matching with (one-sided) vertex arrivals in bipartite graphs, and edge arrivals in general graphs. This algorithm was first studied more than a decade ago by Korula and Pál for the bipartite case in the random-order model. While the weighted bipartite matching problem is solved in the random-order model, this is not the case in recent and exciting online models in which the online player is provided with a sample, and the arrival order is adversarial. The greedy-based algorithm is arguably the most natural and practical algorithm to be applied in these models. Despite its simplicity and appeal, and despite being studied in multiple works, the greedy-based algorithm was not fully understood in any of the studied online models, and its actual performance remained an open question for more than a decade. We provide a thorough analysis of the greedy-based algorithm in several online models. For vertex arrivals in bipartite graphs, we characterize the exact competitive-ratio of this algorithm in the random-order model, for any arrival order of the vertices subsequent to the sampling phase (adversarial and random orders in particular). We use it to derive tight analysis in the recent adversarial-order model with a sample (AOS model) for any sample size, providing the first result in this model beyond the simple secretary problem. Then, we generalize and strengthen the black box method of converting results in the random-order model to single-sample prophet inequalities, and use it to derive the state-of-the-art single-sample prophet inequality for the problem. Finally, we use our new techniques to analyze the greedy-based algorithm for edge arrivals in general graphs and derive results in all the mentioned online models. In this case as well, we improve upon the state-of-the-art single-sample prophet inequality. Previous chapter Next chapter RelatedDetails Published:2022eISBN:978-1-61197-707-3 https://doi.org/10.1137/1.9781611977073Book Series Name:ProceedingsBook Code:PRDA22Book Pages:xvii + 3771
View PDF Chat

Constrained-Order Prophet Inequalities

2021-01-01
Makis Arsenis , Odysseas Drosis , Robert Kleinberg
Free order prophet inequalities bound the ratio between the expected value obtained by two parties each selecting one value from a set of independent random variables: a "prophet" who knows … Free order prophet inequalities bound the ratio between the expected value obtained by two parties each selecting one value from a set of independent random variables: a "prophet" who knows the value of each variable and may select the maximum one, and a "gambler" who is free to choose the order in which to observe the values but must select one of them immediately after observing it, without knowing what values will be sampled for the unobserved variables. It is known that the gambler can always ensure an expected payoff at least 0.669 … times as great as that of the prophet. In fact, even if the gambler uses a threshold stopping rule, meaning there is a fixed threshold value such that the gambler rejects every sample below the threshold and accepts every sample above it, the threshold can always be chosen so that the gambler-to-prophet ratio is at least . … In contrast, if the gambler must observe the values in a predetermined order, the tight bound for the gambler-to-prophet ratio is 1/2.In this work we investigate a model that interpolates between these two extremes. We assume there is a predefined set of permutations of the set indexing the random variables, and the gambler is free to choose the order of observation to be any one of these predefined permutations. Surprisingly, we show that even when only two orderings are allowed — namely, the forward and reverse orderings — the gambler-to-prophet ratio improves to …, the inverse of the golden ratio. As the number of allowed permutations grows beyond 2, a striking "double plateau" phenomenon emerges: after increasing from 0.5 to φ–1 when two permutations are allowed, the gambler-to-prophet ratio achievable by threshold stopping rules does not exceed φ–1 + o(1) until the number of allowed permutations grows to O(log n). The ratio reaches for a suitably chosen set of O(poly(∊–1) · log n) permutations and does not exceed even when the full set of n! permutations is allowed.
View PDF Chat

Prophet Inequalities Require Only a Constant Number of Samples

2024-06-10
Andrés Cristi , Bruno Ziliotto
In a prophet inequality problem, n independent random variables are presented to a gambler one by one. The gambler decides when to stop the sequence and obtains the most recent … In a prophet inequality problem, n independent random variables are presented to a gambler one by one. The gambler decides when to stop the sequence and obtains the most recent value as reward. We evaluate a stopping rule by the worst-case ratio between its expected reward and the expectation of the maximum variable. In the classic setting, the order is fixed, and the optimal ratio is known to be 1/2. Three variants of this problem have been extensively studied: the prophet-secretary model, where variables arrive in uniformly random order; the free-order model, where the gambler chooses the arrival order; and the i.i.d. model, where the distributions are all the same, rendering the arrival order irrelevant. Most of the literature assumes that distributions are known to the gambler. Recent work has considered the question of what is achievable when the gambler has access only to a few samples per distribution. Surprisingly, in the fixed-order case, a single sample from each distribution is enough to approximate the optimal ratio, but this is not the case in any of the three variants. We provide a unified proof that for all three variants of the problem, a constant number of samples (independent of n) for each distribution is good enough to approximate the optimal ratios. Prior to our work, this was known to be the case only in the i.i.d. variant. Previous works relied on explicitly constructing sample-based algorithms that match the best possible ratio. Remarkably, the optimal ratios for the prophet-secretary and the free-order variants with full information are still unknown. Consequently, our result requires a significantly different approach than for the classic problem and the i.i.d. variant, where the optimal ratios and the algorithms that achieve them are known. We complement our result showing that our algorithms can be implemented in polynomial time. A key ingredient in our proof is an existential result based on a minimax argument, which states that there must exist an algorithm that attains the optimal ratio and does not rely on the knowledge of the upper tail of the distributions. A second key ingredient is a refined sample-based version of a decomposition of the instance into "small" and "large" variables, first introduced by Liu et al. [EC'21]. The universality of our approach opens avenues for generalization to other sample-based models. Furthermore, we uncover structural properties that might help pinpoint the optimal ratios in the full-information cases.
View PDF Chat

Constrained-Order Prophet Inequalities

2020-01-01
Makis Arsenis , Odysseas Drosis , Robert Kleinberg
Free order prophet inequalities bound the ratio between the expected value obtained by two parties each selecting a value from a set of independent random variables: a "prophet" who knows … Free order prophet inequalities bound the ratio between the expected value obtained by two parties each selecting a value from a set of independent random variables: a "prophet" who knows the value of each variable and may select the maximum one, and a "gambler" who is free to choose the order in which to observe the values but must select one of them immediately after observing it, without knowing what values will be sampled for the unobserved variables. It is known that the gambler can always ensure an expected payoff at least $0.669\dots$ times as great as that of the prophet. In fact, there exists a threshold stopping rule which guarantees a gambler-to-prophet ratio of at least $1-\frac1e=0.632\dots$. In contrast, if the gambler must observe the values in a predetermined order, the tight bound for the gambler-to-prophet ratio is $1/2$. In this work we investigate a model that interpolates between these two extremes. We assume there is a predefined set of permutations, and the gambler is free to choose the order of observation to be any one of these predefined permutations. Surprisingly, we show that even when only two orderings are allowed---namely, the forward and reverse orderings---the gambler-to-prophet ratio improves to $\varphi^{-1}=0.618\dots$, the inverse of the golden ratio. As the number of allowed permutations grows beyond 2, a striking "double plateau" phenomenon emerges: after increasing from $0.5$ to $\varphi^{-1}$, the gambler-to-prophet ratio achievable by threshold stopping rules does not exceed $\varphi^{-1}+o(1)$ until the number of allowed permutations grows to $O(\log n)$. The ratio reaches $1-\frac1e-\varepsilon$ for a suitably chosen set of $O(\text{poly}(\varepsilon^{-1})\cdot\log n)$ permutations and does not exceed $1-\frac1e$ even when the full set of $n!$ permutations is allowed.
View PDF Chat

Prophet Inequalities Require Only a Constant Number of Samples

2023-01-01
Andrés Cristi , Bruno Ziliotto
In a prophet inequality problem, $n$ independent random variables are presented to a gambler one by one. The gambler decides when to stop the sequence and obtains the most recent … In a prophet inequality problem, $n$ independent random variables are presented to a gambler one by one. The gambler decides when to stop the sequence and obtains the most recent value as reward. We evaluate a stopping rule by the worst-case ratio between its expected reward and the expectation of the maximum variable. In the classic setting, the order is fixed, and the optimal ratio is known to be 1/2. Three variants of this problem have been extensively studied: the prophet-secretary model, where variables arrive in uniformly random order; the free-order model, where the gambler chooses the arrival order; and the i.i.d. model, where the distributions are all the same, rendering the arrival order irrelevant. Most of the literature assumes that distributions are known to the gambler. Recent work has considered the question of what is achievable when the gambler has access only to a few samples per distribution. Surprisingly, in the fixed-order case, a single sample from each distribution is enough to approximate the optimal ratio, but this is not the case in any of the three variants. We provide a unified proof that for all three variants of the problem, a constant number of samples (independent of n) for each distribution is good enough to approximate the optimal ratios. Prior to our work, this was known to be the case only in the i.i.d. variant. We complement our result showing that our algorithms can be implemented in polynomial time. A key ingredient in our proof is an existential result based on a minimax argument, which states that there must exist an algorithm that attains the optimal ratio and does not rely on the knowledge of the upper tail of the distributions. A second key ingredient is a refined sample-based version of a decomposition of the instance into "small" and "large" variables, first introduced by Liu et al. [EC'21].
View PDF Chat

Single-Sample Prophet Inequalities via Greedy-Ordered Selection

2021-01-01
Constantine Caramanis , Paul Dütting , Matthew Faw +6 more
We study single-sample prophet inequalities (SSPIs), i.e., prophet inequalities where only a single sample from each prior distribution is available. Besides a direct, and optimal, SSPI for the basic single … We study single-sample prophet inequalities (SSPIs), i.e., prophet inequalities where only a single sample from each prior distribution is available. Besides a direct, and optimal, SSPI for the basic single choice problem [Rubinstein et al., 2020], most existing SSPI results were obtained via an elegant, but inherently lossy, reduction to order-oblivious secretary (OOS) policies [Azar et al., 2014]. Motivated by this discrepancy, we develop an intuitive and versatile greedy-based technique that yields SSPIs directly rather than through the reduction to OOSs. Our results can be seen as generalizing and unifying a number of existing results in the area of prophet and secretary problems. Our algorithms significantly improve on the competitive guarantees for a number of interesting scenarios (including general matching with edge arrivals, bipartite matching with vertex arrivals, and certain matroids), and capture new settings (such as budget additive combinatorial auctions). Complementing our algorithmic results, we also consider mechanism design variants. Finally, we analyze the power and limitations of different SSPI approaches by providing a partial converse to the reduction from SSPI to OOS given by Azar et al.

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.

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.
View PDF Chat

Revelation gap for pricing from samples

2021-06-15
Yiding Feng , Jason D. Hartline , Yingkai Li
This paper considers prior-independent mechanism design, in which a single mechanism is designed to achieve approximately optimal performance on every prior distribution from a given class. Most results in this … This paper considers prior-independent mechanism design, in which a single mechanism is designed to achieve approximately optimal performance on every prior distribution from a given class. Most results in this literature focus on mechanisms with truthtelling equilibria, a.k.a., truthful mechanisms. Feng and Hartline [FOCS 2018] introduce the revelation gap to quantify the loss of the restriction to truthful mechanisms. We solve a main open question left in Feng and Hartline [FOCS 2018]; namely, we identify a non-trivial revelation gap for revenue maximization.
View PDF Chat

Secretary and online matching problems with machine learned advice

2023-05-01
Antonios Antoniadis , Themis Gouleakis , Pieter Kleer +1 more
The classic analysis of online algorithms, due to its worst-case nature, can be quite pessimistic when the input instance at hand is far from worst-case. In contrast, machine learning approaches … The classic analysis of online algorithms, due to its worst-case nature, can be quite pessimistic when the input instance at hand is far from worst-case. In contrast, machine learning approaches shine in exploiting patterns in past inputs in order to predict the future. However, such predictions, although usually accurate, can be arbitrarily poor. Inspired by a recent line of work, we augment three well-known online settings with machine learned predictions about the future, and develop algorithms that take these predictions into account. In particular, we study the following online selection problems: (i) the classic secretary problem, (ii) online bipartite matching and (iii) the graphic matroid secretary problem. Our algorithms still come with a worst-case performance guarantee in the case that predictions are subpar while obtaining an improved competitive ratio (over the best-known classic online algorithm for each problem) when the predictions are sufficiently accurate. For each algorithm, we establish a trade-off between the competitive ratios obtained in the two respective cases.
View PDF Chat

Single-Sample Prophet Inequalities via Greedy-Ordered Selection

2022-01-01
Constantine Caramanis , Paul Dütting , Matthew Faw +6 more
Previous chapter Next chapter Full AccessProceedings Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)Single-Sample Prophet Inequalities via Greedy-Ordered SelectionConstantine Caramanis, Paul Dütting, Matthew Faw, Federico Fusco, Philip … Previous chapter Next chapter Full AccessProceedings Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)Single-Sample Prophet Inequalities via Greedy-Ordered SelectionConstantine Caramanis, Paul Dütting, Matthew Faw, Federico Fusco, Philip Lazos, Stefano Leonardi, Orestis Papadigenopoulos, Emmanouil Pountourakis, and Rebecca ReiffenhäuserConstantine Caramanis, Paul Dütting, Matthew Faw, Federico Fusco, Philip Lazos, Stefano Leonardi, Orestis Papadigenopoulos, Emmanouil Pountourakis, and Rebecca Reiffenhäuserpp.1298 - 1325Chapter DOI:https://doi.org/10.1137/1.9781611977073.54PDFBibTexSections ToolsAdd to favoritesExport CitationTrack CitationsEmail SectionsAboutAbstract We study single-sample prophet inequalities (SSPIs), i.e., prophet inequalities where only a single sample from each prior distribution is available. Besides a direct, and optimal, SSPI for the basic single choice problem [Rubinstein et al., 2020], most existing SSPI results were obtained via an elegant, but inherently lossy reduction to order-oblivious secretary (OOS) policies [Azar et al., 2014]. Motivated by this discrepancy, we develop an intuitive and versatile greedy-based technique that yields SSPIs directly rather than through the reduction to OOSs. Our results can be seen as generalizing and unifying a number of existing results in the area of prophet and secretary problems. Our algorithms significantly improve on the competitive guarantees for a number of interesting scenarios (including general matching with edge arrivals, bipartite matching with vertex arrivals, and certain matroids), and capture new settings (such as budget additive combinatorial auctions). Complementing our algorithmic results, we also consider mechanism design variants. Finally, we analyze the power and limitations of different SSPI approaches by providing a partial converse to the reduction from SSPI to OOS given by Azar et al. Previous chapter Next chapter RelatedDetails Published:2022eISBN:978-1-61197-707-3 https://doi.org/10.1137/1.9781611977073Book Series Name:ProceedingsBook Code:PRDA22Book Pages:xvii + 3771
View PDF Chat

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.
View PDF Chat

The Secretary Problem with Distributions

2022-01-01
Pranav Nuti
View PDF Chat

Efficient two-sided markets with limited information

2021-06-15
Paul Dütting , Federico Fusco , Philip Lazos +2 more
A celebrated impossibility result by Myerson and Satterthwaite (1983) shows that any truthful mechanism for two-sided markets that maximizes social welfare must run a deficit, resulting in a necessity to … A celebrated impossibility result by Myerson and Satterthwaite (1983) shows that any truthful mechanism for two-sided markets that maximizes social welfare must run a deficit, resulting in a necessity to relax welfare efficiency and the use of approximation mechanisms. Such mechanisms in general make extensive use of the Bayesian priors. In this work, we investigate a question of increasing theoretical and practical importance: how much prior information is required to design mechanisms with near-optimal approximations?
View PDF Chat

Secretary Problems: The Power of a Single Sample

2023-01-01
Pranav Nuti , Jan Vondrák
In this paper, we investigate two variants of the secretary problem. In these variants, we are presented with a sequence of numbers Xi that come from distributions Di, and that … In this paper, we investigate two variants of the secretary problem. In these variants, we are presented with a sequence of numbers Xi that come from distributions Di, and that arrive in either random or adversarial order. We do not know what the distributions are, but we have access to a single sample Yi from each distribution Di. After observing each number, we have to make an irrevocable decision about whether we would like to accept it or not with the goal of maximizing the probability of selecting the largest number.The random order version of this problem was first studied by Correa et al. [SODA 2020] who managed to construct an algorithm that achieves a probability of 0.4529. In this paper, we improve this probability to 0.5009, almost matching an upper bound of ≃ 0.5024 which we show follows from earlier work. We also show that there is an algorithm which achieves the probability of ≃ 0.5024 asymptotically if no particular distribution is especially likely to yield the largest number. For the adversarial order version of the problem, we show that we can select the maximum number with a probability of 1/4, and that this is best possible. Our work demonstrates that unlike in the case of the expected value objective studied by Rubinstein et al. [ITCS 2020], knowledge of a single sample is not enough to recover the factor of success guaranteed by full knowledge of the distribution.
View PDF Chat

Comparisons of Stop Rule and Supremum Expectations of I.I.D. Random Variables

1982-05-01
Theodore P. Hill , Robert P. Kertz
Implicitly defined (and easily approximated) universal constants $1.1 < a_n < 1.6, n = 2,3, \cdots$, are found so that if $X_1, X_2, \cdots$ are i.i.d. non-negative random variables and … Implicitly defined (and easily approximated) universal constants $1.1 < a_n < 1.6, n = 2,3, \cdots$, are found so that if $X_1, X_2, \cdots$ are i.i.d. non-negative random variables and if $T_n$ is the set of stop rules for $X_1, \cdots, X_n$, then $E(\max\{X_1, \cdots, X_n\}) \leq a_n \sup\{EX_t: t \in T_n\}$, and the bound $a_n$ is best possible. Similar universal constants $0 < b_n < \frac{1}{4}$ are found so that if the $\{X_i\}$ are i.i.d. random variables taking values only in $\lbrack a, b\rbrack$, then $E(\max\{X_1, \cdots, X_n\}) \leq \sup\{EX_t: t \in T_n\} + b_n(b - a)$, where again the bound $b_n$ is best possible. In both situations, extremal distributions for which equality is attained (or nearly attained) are given in implicit form.
View PDF Chat

Matroid prophet inequalities

2012-05-19
Robert Kleinberg , S. Matthew Weinberg
Consider a gambler who observes a sequence of independent, non-negative random numbers and is allowed to stop the sequence at any time, claiming a reward equal to the most recent … Consider a gambler who observes a sequence of independent, non-negative random numbers and is allowed to stop the sequence at any time, claiming a reward equal to the most recent observation. The famous prophet inequality of Krengel, Sucheston, and Garling asserts that a gambler who knows the distribution of each random variable can achieve at least half as much reward, in expectation, as a "prophet" who knows the sampled values of each random variable and can choose the largest one. We generalize this result to the setting in which the gambler and the prophet are allowed to make more than one selection, subject to a matroid constraint. We show that the gambler can still achieve at least half as much reward as the prophet; this result is the best possible, since it is known that the ratio cannot be improved even in the original prophet inequality, which corresponds to the special case of rank-one matroids. Generalizing the result still further, we show that under an intersection of $p$ matroid constraints, the prophet's reward exceeds the gambler's by a factor of at most $O(p)$, and this factor is also tight.
View PDF Chat

Stop rule and supremum expectations of i.i.d. random variables: A complete comparison by conjugate duality

1986-06-01
Robert P. Kertz

Beating 1-1/e for ordered prophets

2017-06-15
Melika Abolhassani , Soheil Ehsani , Hossein Esfandiari +3 more
Hill and Kertz studied the prophet inequality on iid distributions [The Annals of Probability 1982]. They proved a theoretical bound of 1 - 1/e on the approximation factor of their … Hill and Kertz studied the prophet inequality on iid distributions [The Annals of Probability 1982]. They proved a theoretical bound of 1 - 1/e on the approximation factor of their algorithm. They conjectured that the best approximation factor for arbitrarily large n is 1/1+1/e ≃ 0.731. This conjecture remained open prior to this paper for over 30 years. In this paper we present a threshold-based algorithm for the prophet inequality with n iid distributions. Using a nontrivial and novel approach we show that our algorithm is a 0.738-approximation algorithm. By beating the bound of 1/1+1/e, this refutes the conjecture of Hill and Kertz. Moreover, we generalize our results to non-uniform distributions and discuss its applications in mechanism design.
View PDF Chat

The Prophet Inequality Can Be Solved Optimally with a Single Set of Samples

2018-01-01
Jack Wang
The setting of the classic prophet inequality is as follows: a gambler is shown the probability distributions of $n$ independent, non-negative random variables with finite expectations. In their indexed order, … The setting of the classic prophet inequality is as follows: a gambler is shown the probability distributions of $n$ independent, non-negative random variables with finite expectations. In their indexed order, a value is drawn from each distribution, and after every draw the gambler may choose to accept the value and end the game, or discard the value permanently and continue the game. What is the best performance that the gambler can achieve in comparison to a prophet who can always choose the highest value? Krengel, Sucheston, and Garling solved this problem in 1978, showing that there exists a strategy for which the gambler can achieve half as much reward as the prophet in expectation. Furthermore, this result is tight. In this work, we consider a setting in which the gambler is allowed much less information. Suppose that the gambler can only take one sample from each of the distributions before playing the game, instead of knowing the full distributions. We provide a simple and intuitive algorithm that recovers the original approximation of $\frac{1}{2}$. Our algorithm works against even an almighty adversary who always chooses a worst-case ordering, rather than the standard offline adversary. The result also has implications for mechanism design -- there is much interest in designing competitive auctions with a finite number of samples from value distributions rather than full distributional knowledge.

Prophet Inequalities for I.I.D. Random Variables from an Unknown Distribution

2019-06-17
José R. Correa , Paul Dütting , Felix Fischer +1 more
A central object in optimal stopping theory is the single-choice prophet inequality for independent, identically distributed random variables: given a sequence of random variables X1, ..., Xn drawn independently from … A central object in optimal stopping theory is the single-choice prophet inequality for independent, identically distributed random variables: given a sequence of random variables X1, ..., Xn drawn independently from a distribution F, the goal is to choose a stopping time τ so as to maximize α such that for all distributions F we have E[Xτ]≥α•E[maxt Xt]. What makes this problem challenging is that the decision whether τ=t may only depend on the values of the random variables X1, ..., Xt and on the distribution F. For a long time the best known bound for the problem had been α≥1-1/e≅0.632, but quite recently a tight bound of α≅0.745 was obtained. The case where F is unknown, such that the decision whether τ=t may depend only on the values of the random variables X1, ..., Xt, is equally well motivated but has received much less attention. A straightforward guarantee for this case of α≥1-1/e≅0.368 can be derived from the solution to the secretary problem, where an arbitrary set of values arrive in random order and the goal is to maximize the probability of selecting the largest value. We show that this bound is in fact tight. We then investigate the case where the stopping time may additionally depend on a limited number of samples from~F, and show that even with o(n) samples α≥1/e. On the other hand, n samples allow for a significant improvement, while O(n2) samples are equivalent to knowledge of the distribution: specifically, with n samples α≥1-1/e≅0.632 and α≥ln(2)≅0.693, and with O(n2) samples α≥0.745-ε for any ε>0.
View PDF Chat

Prophet Inequalities Made Easy: Stochastic Optimization by Pricing Non-Stochastic Inputs

2017-10-01
Paul Dütting , Michal Feldman , Thomas Keßelheim +1 more
We present a general framework for stochastic online maximization problems with combinatorial feasibility constraints. The framework establishes prophet inequalities by constructing price-based online approximation algorithms, a natural extension of threshold … We present a general framework for stochastic online maximization problems with combinatorial feasibility constraints. The framework establishes prophet inequalities by constructing price-based online approximation algorithms, a natural extension of threshold algorithms for settings beyond binary selection. Our analysis takes the form of an extension theorem: we derive sufficient conditions on prices when all weights are known in advance, then prove that the resulting approximation guarantees extend directly to stochastic settings. Our framework unifies and simplifies much of the existing literature on prophet inequalities and posted price mechanisms, and is used to derive new and improved results for combinatorial markets (with and without complements), multi-dimensional matroids, and sparse packing problems. Finally, we highlight a surprising connection between the smoothness framework for bounding the price of anarchy of mechanisms and our framework, and show that many smooth mechanisms can be recast as posted price mechanisms with comparable performance guarantees.
View PDF Chat

Prophet Secretary for Combinatorial Auctions and Matroids

2018-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 [33] and Feldman et al. [17] 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 [45] and Esfandiari et al. [15] 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.
View PDF Chat

Prophet secretary through blind strategies

2020-08-03
José R. Correa , Raimundo Saona , Bruno Ziliotto
View PDF Chat

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.