Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userThe Stationary Prophet Inequality Problem
86
0
0.0
(
0
)
Added by
David Wajc
Publication date
2021
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
We study a continuous and infinite time horizon counterpart to the classic prophet inequality, which we term the stationary prophet inequality problem. Here, copies of a good arrive and perish according to Poisson point processes. Buyers arrive similarly and make take-it-or-leave-it offers for unsold items. The objective is to maximize the (infinite) time average revenue of the seller. Our main results are pricing-based policies which (i) achieve a $1/2$-approximation of the optimal offline policy, which is best possible, and (ii) achieve a better than $(1-1/e)$-approximation of the optimal online policy. Result (i) improves upon bounds implied by recent work of Collina et al. (WINE20), and is the first optimal prophet inequality for a stationary problem. Result (ii) improves upon a $1-1/e$ bound implied by recent work of Aouad and Saritac{c} (EC20), and shows that this prevalent bound in online algorithms is not optimal for this problem.
rate research
Read More
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.
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.
We introduce a model of competing agents in a prophet setting, where rewards arrive online, and decisions are made immediately and irrevocably. The rewards are unknown from the outset, but they are drawn from a known probability distribution. In the standard prophet setting, a single agent makes selection decisions in an attempt to maximize her expected reward. The novelty of our model is the introduction of a competition setting, where multiple agents compete over the arriving rewards, and make online selection decisions simultaneously, as rewards arrive. If a given reward is selected by more than a single agent, ties are broken either randomly or by a fixed ranking of the agents. The consideration of competition turns the prophet setting from an online decision making scenario to a multi-agent game. For both random and ranked tie-breaking rules, we present simple threshold strategies for the agents that give them high guarantees, independent of the strategies taken by others. In particular, for random tie-breaking, every agent can guarantee herself at least $frac{1}{k+1}$ of the highest reward, and at least $frac{1}{2k}$ of the optimal social welfare. For ranked tie-breaking, the $i$th ranked agent can guarantee herself at least a half of the $i$th highest reward. We complement these results by matching upper bounds, even with respect to equilibrium profiles. For ranked tie-breaking rule, we also show a correspondence between the equilibrium of the $k$-agent game and the optimal strategy of a single decision maker who can select up to $k$ rewards.
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 prophets reward exceeds the gamblers by a factor of at most O(p), and this factor is also tight. Beyond their interest as theorems about pure online algorithms or optimal stopping rules, these results also have applications to mechanism design. Our results imply improved bounds on the ability of sequential posted-price mechanisms to approximate Bayesian optimal mechanisms in both single-parameter and multi-parameter settings. In particular, our results imply the first efficiently computable constant-factor approximations to the Bayesian optimal revenue in certain multi-parameter settings.
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.669dots$ 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.632dots$. 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.618dots$, 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})cdotlog n)$ permutations and does not exceed $1-frac1e$ even when the full set of $n!$ permutations is allowed.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
