SU\G(๐”ธ)/KยทU
Sign Up for free Log In

Matroid prophet inequalities

Authors

Robert Kleinberg, S. Matthew Weinberg
Type: Article
Publication Date: 2012-05-19
Citations: 227
DOI: https://doi.org/10.1145/2213977.2213991

Abstract

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.

Locations

  • arXiv (Cornell University)
    View PDF

Ask a Question About This Paper

Summary

Login to see paper summary

Matroid Prophet Inequalities

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

Matroid Prophet Inequalities

2012-01-23
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 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 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 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. 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.

Polymatroid Prophet Inequalities

2013-01-01
Paul Duetting , Robert Kleinberg
Consider a gambler and a prophet who observe a sequence of independent, non-negative numbers. The gambler sees the numbers one-by-one whereas the prophet sees the entire sequence at once. The โ€ฆ Consider a gambler and a prophet who observe a sequence of independent, non-negative numbers. The gambler sees the numbers one-by-one whereas the prophet sees the entire sequence at once. The goal of both is to decide on fractions of each number they want to keep so as to maximize the weighted fractional sum of the numbers chosen. The classic result of Krengel and Sucheston (1977-78) asserts that if both the gambler and the prophet can pick one number, then the gambler can do at least half as well as the prophet. Recently, Kleinberg and Weinberg (2012) have generalized this result to settings where the numbers that can be chosen are subject to a matroid constraint. In this note we go one step further and show that the bound carries over to settings where the fractions that can be chosen are subject to a polymatroid constraint. This bound is tight as it is already tight for the simple setting where the gambler and the prophet can pick only one number. An interesting application of our result is in mechanism design, where it leads to improved results for various problems.
View PDF Chat

Polymatroid Prophet Inequalities

2013-07-19
Paul Duetting , Robert Kleinberg
Consider a gambler and a prophet who observe a sequence of independent, non-negative numbers. The gambler sees the numbers one-by-one whereas the prophet sees the entire sequence at once. The โ€ฆ Consider a gambler and a prophet who observe a sequence of independent, non-negative numbers. The gambler sees the numbers one-by-one whereas the prophet sees the entire sequence at once. The goal of both is to decide on fractions of each number they want to keep so as to maximize the weighted fractional sum of the numbers chosen. The classic result of Krengel and Sucheston (1977-78) asserts that if both the gambler and the prophet can pick one number, then the gambler can do at least half as well as the prophet. Recently, Kleinberg and Weinberg (2012) have generalized this result to settings where the numbers that can be chosen are subject to a matroid constraint. In this note we go one step further and show that the bound carries over to settings where the fractions that can be chosen are subject to a polymatroid constraint. This bound is tight as it is already tight for the simple setting where the gambler and the prophet can pick only one number. An interesting application of our result is in mechanism design, where it leads to improved results for various problems.

Single Sample Prophet Inequality for Uniform Matroids of Rank 2

2023-01-01
Kanstantsin Pashkovich , Alice Sayutina
We study the prophet inequality when the gambler has an access only to a single sample from each distribution. Rubinstein, Wang and Weinberg showed that an optimal guarantee of 1/2 โ€ฆ We study the prophet inequality when the gambler has an access only to a single sample from each distribution. Rubinstein, Wang and Weinberg showed that an optimal guarantee of 1/2 can be achieved when the underlying matroid has rank 1, i.e. in the case of a single choice. We show that this guarantee can be achieved also in the case of a uniform matroid of rank 2 by a deterministic mechanism, and we show that this is best possible among deterministic mechanisms. We also conjecture that a straightforward generalization of our policy achieves the guarantee of 1/2 for all uniform matroids.
View PDF Chat

Prophet Inequalities with Limited Information

2013-01-01
Pablo Azar , Robert Kleinberg , S. Matthew Weinberg
In the classical prophet inequality, a gambler observes a sequence of stochastic rewards $V_1,...,V_n$ and must decide, for each reward $V_i$, whether to keep it and stop the game or โ€ฆ In the classical prophet inequality, a gambler observes a sequence of stochastic rewards $V_1,...,V_n$ and must decide, for each reward $V_i$, whether to keep it and stop the game or to forfeit the reward forever and reveal the next value $V_i$. 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 $V_1,...,V_n$ are drawn. The assumption that the gambler knows the distribution from which $V_1,...,V_n$ 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, \emph{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 \emph{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. We apply these results to design the first posted-price and multi-dimensional auction mechanisms with limited information in settings with asymmetric bidders.
View PDF Chat

Oracle-Augmented Prophet Inequalities

2024-04-17
Sariel Har-Peled , Elfarouk Harb , Vasilis Livanos
In the classical prophet inequality settings, a gambler is given a sequence of $n$ random variables $X_1, \dots, X_n$, taken from known distributions, observes their values in this (potentially adversarial) โ€ฆ In the classical prophet inequality settings, a gambler is given a sequence of $n$ random variables $X_1, \dots, X_n$, taken from known distributions, observes their values in this (potentially adversarial) order, and select one of them, immediately after it is being observed, so that its value is as high as possible. The classical \emph{prophet inequality} shows a strategy that guarantees a value at least half of that an omniscience prophet that picks the maximum, and this ratio is optimal. Here, we generalize the prophet inequality, allowing the gambler some additional information about the future that is otherwise privy only to the prophet. Specifically, at any point in the process, the gambler is allowed to query an oracle $\mathcal{O}$. The oracle responds with a single bit answer: YES if the current realization is greater than the remaining realizations, and NO otherwise. We show that the oracle model with $m$ oracle calls is equivalent to the \textsc{Top-$1$-of-$(m+1)$} model when the objective is maximizing the probability of selecting the maximum. This equivalence fails to hold when the objective is maximizing the competitive ratio, but we still show that any algorithm for the oracle model implies an equivalent competitive ratio for the \textsc{Top-$1$-of-$(m+1)$} model. We resolve the oracle model for any $m$, giving tight lower and upper bound on the best possible competitive ratio compared to an almighty adversary. As a consequence, we provide new results as well as improvements on known results for the \textsc{Top-$1$-of-$m$} model.
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

An Improved Lower Bound for Matroid Intersection Prophet Inequalities

2022-01-01
Raghuvansh R. Saxena , Santhoshini Velusamy , S. Matthew Weinberg
We consider prophet inequalities subject to feasibility constraints that are the intersection of $q$ matroids. The best-known algorithms achieve a $\Theta(q)$-approximation, even when restricted to instances that are the intersection โ€ฆ We consider prophet inequalities subject to feasibility constraints that are the intersection of $q$ matroids. The best-known algorithms achieve a $\Theta(q)$-approximation, even when restricted to instances that are the intersection of $q$ partition matroids, and with i.i.d.~Bernoulli random variables. The previous best-known lower bound is $\Theta(\sqrt{q})$ due to a simple construction of [Kleinberg-Weinberg STOC 2012] (which uses i.i.d.~Bernoulli random variables, and writes the construction as the intersection of partition matroids). We establish an improved lower bound of $q^{1/2+\Omega(1/\log \log q)}$ by writing the construction of [Kleinberg-Weinberg STOC 2012] as the intersection of asymptotically fewer partition matroids. We accomplish this via an improved upper bound on the product dimension of a graph with $p^p$ disjoint cliques of size $p$, using recent techniques developed in [Alon-Alweiss European Journal of Combinatorics 2020].
View PDF Chat

Matroid inequalities

1995-12-01
Manoj K. Chari

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

Single sample prophet inequality for uniform matroids of rank 2

2025-02-27
Kanstantsin Pashkovich , Alice Sayutina
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

Sample-Based Matroid Prophet Inequalities

2024-07-08
Hu Fu , Pinyan Lu , Zhihao Gavin Tang +3 more
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

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: Separating Random Order from Order Selection

2023-01-01
Giordano Giambartolomei , Frederik Mallmann-Trenn , Raimundo Saona
Prophet inequalities are a central object of study in optimal stopping theory. A gambler is sent values online, sampled from an instance of independent distributions, in an adversarial, random or โ€ฆ Prophet inequalities are a central object of study in optimal stopping theory. A gambler is sent values online, sampled from an instance of independent distributions, in an adversarial, random or selected order, depending on the model. When observing each value, the gambler either accepts it as a reward or irrevocably rejects it and proceeds to observe the next value. The goal of the gambler, who cannot see the future, is maximising the expected value of the reward while competing against the expectation of a prophet (the offline maximum). In other words, one seeks to maximise the gambler-to-prophet ratio of the expectations. The model, in which the gambler selects the arrival order first, and then observes the values, is known as Order Selection. In this model a ratio of $0.7251$ has been proved to be attainable for any instance. In very recent work, this has been improved up to $0.7258$. If the gambler chooses the arrival order (uniformly) at random, we obtain the Random Order model. The worst case ratio over all possible instances has been extensively studied for at least $40$ years. In the recent work aforementioned, through simulations, this ratio has been shown to be at most $0.7254$ for the Random Order model, thus establishing for the first time that carefully choosing the order, instead of simply taking it at random, benefits the gambler. We give an alternative, more rigorous proof of this fact, by showing mathematically that in the Random Order model, no algorithm can achieve a ratio larger than $0.7235$. This sets a new state-of-the-art hardness for this model, and establishes more formally that there is a real benefit in choosing the order.

Constrained-Order Prophet Inequalities

2020-10-19
Makis Arsenis , Odysseas Drosis , Robert Kleinberg
Free order 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 โ€ฆ Free order 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 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.

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

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

Online revenue maximization for server pricing

2022-01-22
Shant Boodaghians , Federico Fusco , Stefano Leonardi +2 more
Efficient and truthful mechanisms to price resources on servers/machines have been the subject of much work in recent years due to the importance of the cloud market. This paper considers โ€ฆ Efficient and truthful mechanisms to price resources on servers/machines have been the subject of much work in recent years due to the importance of the cloud market. This paper considers revenue maximization in the online stochastic setting with non-preemptive jobs and a unit capacity server. One agent/job arrives at every time step, with parameters drawn from the underlying distribution. We design a posted-price mechanism which can be efficiently computed and is revenue-optimal in expectation and in retrospect, up to additive error. The prices are posted prior to learning the agent's type, and the computed pricing scheme is deterministic, depending only on the length of the allotted time interval and on the earliest time the server is available. We also prove that the proposed pricing strategy is robust to imprecise knowledge of the job distribution and that a distribution learned from polynomially many samples is sufficient to obtain a near-optimal truthful pricing strategy.
View PDF Chat

Beyond matroids: secretary problem and prophet inequality with general constraints

2016-06-10
Aviad Rubinstein
We study generalizations of the ``Prophet Inequality'' and ``Secretary Problem'', where the algorithm is restricted to an arbitrary downward-closed set system. For 0,1 values, we give O(n)-competitive algorithms for both โ€ฆ We study generalizations of the ``Prophet Inequality'' and ``Secretary Problem'', where the algorithm is restricted to an arbitrary downward-closed set system. For 0,1 values, we give O(n)-competitive algorithms for both problems. This is close to the Omega(n/log n) lower bound due to Babaioff, Immorlica, and Kleinberg. For general values, our results translate to O(log(n) log(r))-competitive algorithms, where r is the cardinality of the largest feasible set. This resolves (up to the O(loglog(n) log(r)) factor) an open question posed to us by Bobby Kleinberg.
View PDF Chat

Polymatroid Prophet Inequalities

2015-01-01
Paul Dรผtting , Robert Kleinberg
View PDF Chat

Dynamic Pricing (and Assortment) Under a Static Calendar

2020-09-22
Will Ma , David Simchiโ€Levi , Jinglong Zhao
This work is motivated by our collaboration with a large consumer packaged goods (CPG) company. We have found that whereas the company appreciates the advantages of dynamic pricing, they deem โ€ฆ This work is motivated by our collaboration with a large consumer packaged goods (CPG) company. We have found that whereas the company appreciates the advantages of dynamic pricing, they deem it operationally much easier to plan out a static price calendar in advance. We investigate the efficacy of static control policies for revenue management problems whose optimal solution is inherently dynamic. In these problems, a firm has limited inventory to sell over a finite time horizon, over which heterogeneous customers stochastically arrive. We consider both pricing and assortment controls, and derive simple static policies in the form of a price calendar or a planned sequence of assortments, respectively. In the assortment planning problem, we also differentiate between the static vs. dynamic substitution models of customer demand. We show that our policies are within 1-1/e (approximately 0.63) of the optimum under stationary demand, and 1/2 of the optimum under nonstationary demand, with both guarantees approaching 1 if the starting inventories are large. We adapt the technique of prophet inequalities from optimal stopping theory to pricing and assortment problems, and our results are relative to the linear programming relaxation. Under the special case of stationary demand single-item pricing, our results improve the understanding of irregular and discrete demand curves, by showing that a static calendar can be (1-1/e)-approximate if the prices are sorted high-to-low. Finally, we demonstrate on both data from the CPG company and synthetic data from the literature that our simple price and assortment calendars are effective. This paper was accepted by Hamid Nazerzadeh, big data analytics.
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 secretary through blind strategies

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

Optimal Pricing for MHR Distributions

2018-01-01
Yiannis Giannakopoulos , Kรจyรน Zhรผ
View PDF Chat

Dynamic Pricing under a Static Calendar.

2018-11-02
Will Ma , David Simchiโ€Levi , Jinglong Zhao
This work is motivated by our collaboration with a large Consumer Packaged Goods (CPG) company. We have found that while they appreciate the advantages of dynamic pricing, they deem it โ€ฆ This work is motivated by our collaboration with a large Consumer Packaged Goods (CPG) company. We have found that while they appreciate the advantages of dynamic pricing, they deem it operationally much easier to plan out a static price calendar in advance. In this paper, we investigate the efficacy of static control policies for dynamic revenue management problems. In these problems, a firm has limited inventory to sell over a finite time horizon where demand is known but stochastic. We consider both pricing and assortment controls, and derive simple static policies in the form of a price calendar or a planned sequence of assortments, respectively. We show that our policies are within 1-1/e (approximately 0.63) of the optimum under stationary (IID) demand, and 1/2 of optimum under non-stationary demand, with both guarantees approaching 1 if the starting inventory is large. A main contribution of this work is developing a system of tools for establishing best-possible performance guarantees relative to linear programming relaxations: in the stationary setting, structural properties about static policies which provide a complete characterization of tight bounds; and in the non-stationary setting, an adaptation of the prophet inequalities from optimal stopping theory to pricing and assortment problems. Finally, we demonstrate on data from the CPG company that our simple price calendars are effective.

Computing simple mechanisms: Lift-and-round over marginal reduced forms

2022-06-09
Yang Cai , Argyris Oikonomou , Mingfei Zhao
We study revenue maximization in multi-item multi-bidder auctions under the natural item-independence assumption โ€“ a classical problem in Multi-Dimensional Bayesian Mechanism Design. One of the biggest challenges in this area โ€ฆ We study revenue maximization in multi-item multi-bidder auctions under the natural item-independence assumption โ€“ a classical problem in Multi-Dimensional Bayesian Mechanism Design. One of the biggest challenges in this area is developing algorithms to compute (approximately) optimal mechanisms that are not brute-force in the size of the bidder type space, which is usually exponential in the number of items in multi-item auctions. Unfortunately, such algorithms were only known for basic settings of our problem when bidders have unit-demand or additive valuations.
View PDF Chat

On the product dimension of clique factors

2020-03-17
Noga Alon , Ryan Alweiss
View PDF Chat

On Simple Mechanisms for Dependent Items

2021-01-01
Yang Cai , Argyris Oikonomou
We study the problem of selling $n$ heterogeneous items to a single buyer, whose values for different items are dependent. Under arbitrary dependence, Hart and Nisan show that no simple โ€ฆ We study the problem of selling $n$ heterogeneous items to a single buyer, whose values for different items are dependent. Under arbitrary dependence, Hart and Nisan show that no simple mechanism can achieve a non-negligible fraction of the optimal revenue even with only two items. We consider the setting where the buyer's type is drawn from a correlated distribution that can be captured by a Markov Random Field, one of the most prominent frameworks for modeling high-dimensional distributions with structure. If the buyer's valuation is additive or unit-demand, we extend the result to all MRFs and show that max(SRev,BRev) can achieve an $\Omega\left(\frac{1}{e^{O(\Delta)}}\right)$-fraction of the optimal revenue, where $\Delta$ is a parameter of the MRF that is determined by how much the value of an item can be influenced by the values of the other items. We further show that the exponential dependence on $\Delta$ is unavoidable for our approach and a polynomial dependence on $\Delta$ is unavoidable for any approach. When the buyer has a XOS valuation, we show that max(Srev,Brev) achieves at least an $\Omega\left(\frac{1}{e^{O(\Delta)}+\frac{1}{\sqrt{n\gamma}}}\right)$-fraction of the optimal revenue, where $\gamma$ is the spectral gap of the Glauber dynamics of the MRF. Note that in the special case of independently distributed items, $\Delta=0$ and $\frac{1}{n\gamma}\leq 1$, and our results recover the known constant factor approximations for a XOS buyer. We further extend our parametric approximation to several other well-studied dependency measures such as the Dobrushin coefficient and the inverse temperature. Our results are based on the Duality-Framework by Cai et al. and a new concentration inequality for XOS functions over dependent random variables.
View PDF Chat

Prophet Inequality: Order selection beats random order

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

Mechanism Design for Subadditive Agents via an Ex Ante Relaxation

2016-07-21
Shuchi Chawla , J. Benjamin Miller
We consider the problem of maximizing revenue for a monopolist offering multiple items to multiple heterogeneous buyers. We develop a simple mechanism that obtains a constant factor approximation under the โ€ฆ We consider the problem of maximizing revenue for a monopolist offering multiple items to multiple heterogeneous buyers. We develop a simple mechanism that obtains a constant factor approximation under the assumption that the buyers' values are additive subject to a matroid feasibility constraint and independent across items. Importantly, different buyers in our setting can have different constraints on the sets of items they desire. Our mechanism is a sequential variant of two-part tariffs. Prior to our work, simple approximation mechanisms for such multi-buyer problems were known only for the special cases of all unit-demand or all additive value buyers.
View PDF Chat

A Stochastic Probing Problem with Applications

2013-01-01
Anupam Gupta , Viswanath Nagarajan
View PDF Chat

Sequential Posted Price Mechanisms with Correlated Valuations

2015-03-07
Marek Adamczyk , Allan Borodin , Diodato Ferraioli +2 more
We study the revenue performance of sequential posted price mechanisms and some natural extensions, for a general setting where the valuations of the buyers are drawn from a correlated distribution. โ€ฆ We study the revenue performance of sequential posted price mechanisms and some natural extensions, for a general setting where the valuations of the buyers are drawn from a correlated distribution. Sequential posted price mechanisms are conceptually simple mechanisms that work by proposing a take-it-or-leave-it offer to each buyer. We apply sequential posted price mechanisms to single-parameter multi-unit settings in which each buyer demands only one item and the mechanism can assign the service to at most k of the buyers. For standard sequential posted price mechanisms, we prove that with the valuation distribution having finite support, no sequential posted price mechanism can extract a constant fraction of the optimal expected revenue, even with unlimited supply. We extend this result to the the case of a continuous valuation distribution when various standard assumptions hold simultaneously. In fact, it turns out that the best fraction of the optimal revenue that is extractable by a sequential posted price mechanism is proportional to ratio of the highest and lowest possible valuation. We prove that for two simple generalizations of these mechanisms, a better revenue performance can be achieved: if the sequential posted price mechanism has for each buyer the option of either proposing an offer or asking the buyer for its valuation, then a Omega(1/max{1,d}) fraction of the optimal revenue can be extracted, where d denotes the degree of dependence of the valuations, ranging from complete independence (d=0) to arbitrary dependence (d=n-1). Moreover, when we generalize the sequential posted price mechanisms further, such that the mechanism has the ability to make a take-it-or-leave-it offer to the i-th buyer that depends on the valuations of all buyers except i's, we prove that a constant fraction (2-sqrt{e})/4~0.088 of the optimal revenue can be always be extracted.

Random Order Contention Resolution Schemes

2018-04-07
Marek Adamczyk , Michaล‚ Wล‚odarczyk
Contention resolution schemes have proven to be an incredibly powerful concept which allows to tackle a broad class of problems. The framework has been initially designed to handle submodular optimization โ€ฆ Contention resolution schemes have proven to be an incredibly powerful concept which allows to tackle a broad class of problems. The framework has been initially designed to handle submodular optimization under various types of constraints, that is, intersections of exchange systems (including matroids), knapsacks, and unsplittable flows on trees. Later on, it turned out that this framework perfectly extends to optimization under uncertainty, like stochastic probing and online selection problems, which further can be applied to mechanism design. We add to this line of work by showing how to create contention resolution schemes for intersection of matroids and knapsacks when we work in the random order setting. More precisely, we do know the whole universe of elements in advance, but they appear in an order given by a random permutation. Upon arrival we need to irrevocably decide whether to take an element or not. We bring a novel technique for analyzing procedures in the random order setting that is based on the martingale theory. This unified approach makes it easier to combine constraints, and we do not need to rely on the monotonicity of contention resolution schemes. Our paper fills the gaps, extends, and creates connections between many previous results and techniques. The main application of our framework is a $k+4+\varepsilon$ approximation ratio for the Bayesian multi-parameter unit-demand mechanism design under the constraint of $k$ matroids intersection, which improves upon the previous bounds of $4k-2$ and $e(k+1)$. Other results include improved approximation ratios for stochastic $k$-set packing and submodular stochastic probing over arbitrary non-negative submodular objective function, whereas previous results required the objective to be monotone.

Submodular Stochastic Probing on Matroids

2016-04-05
Marek Adamczyk , Maxim Sviridenko , Justin Ward
In a stochastic probing problem we are given a universe E, and a probability that each element e in E is active. We determine if an element is active by โ€ฆ In a stochastic probing problem we are given a universe E, and a probability that each element e in E is active. We determine if an element is active by probing it, and whenever a probed element is active, we must permanently include it in our solution. Moreover, throughout the process we need to obey inner constraints on the set of elements taken into the solution, and outer constraints on the set of all probed elements. All previous algorithmic results in this framework have considered only the problem of maximizing a linear function of the active elements. Here, we consider submodular objectives. We provide new, constant-factor approximations for maximizing a monotone submodular function subject to multiple matroid constraints on both the elements that may be taken and the elements that may be probed. We also obtain an improved approximation for linear objective functions, and show how our approach may be generalized to handle k-matchoid constraints.
View PDF Chat

Revenue Gaps for Static and Dynamic Posted Pricing of Homogeneous Goods

2016-01-01
Paul Dรผtting , Felix Fischer , Max Klimm
We consider the problem of maximizing the expected revenue from selling $k$ homogeneous goods to $n$ unit-demand buyers who arrive sequentially with independent and identically distributed valuations. In this setting โ€ฆ We consider the problem of maximizing the expected revenue from selling $k$ homogeneous goods to $n$ unit-demand buyers who arrive sequentially with independent and identically distributed valuations. In this setting the optimal posted prices are dynamic in the sense that they depend on the remaining numbers of goods and buyers. We investigate how much revenue is lost when a single static price is used instead for all buyers and goods, and prove upper bounds on the ratio between the maximum revenue from dynamic prices and that from static prices. These bounds are tight for all values of $k$ and $n$ and vary depending on a regularity property of the underlying distribution. For general distributions we obtain a ratio of $2-k/n$, for regular distributions a ratio that increases in $n$ and is bounded from above by $1/(1-k^k/(e^{k}k!))$, which is roughly $1/(1-1/(\sqrt{2ฯ€k}))$. The lower bounds hold for the revenue gap between dynamic and static prices. The upper bounds are obtained via an ex-ante relaxation of the revenue maximization problem, as a consequence the tight bounds of $2-k/n$ in the general case and of $1/(1-1/(\sqrt{2ฯ€k}))$ in the regular case apply also to the potentially larger revenue gap between the optimal incentive-compatible mechanism and the optimal static price. Our results imply that for regular distributions the benefit of dynamic prices vanishes while for non-regular distributions dynamic prices may achieve up to twice the revenue of static prices.

An O(log log m) Prophet Inequality for Subadditive Combinatorial Auctions

2020-11-01
Paul Dรผtting , Thomas KeรŸelheim , Brendan Lucier
Prophet inequalities compare the expected performance of an online algorithm for a stochastic optimization problem to the expected optimal solution in hindsight. They are a major alternative to classic worst-case โ€ฆ Prophet inequalities compare the expected performance of an online algorithm for a stochastic optimization problem to the expected optimal solution in hindsight. They are a major alternative to classic worst-case competitive analysis, of particular importance in the design and analysis of simple (posted-price) incentive compatible mechanisms with provable approximation guarantees. A central open problem in this area concerns subadditive combinatorial auctions. Here n agents with subadditive valuation functions compete for the assignment of m items. The goal is to find an allocation of the items that maximizes the total value of the assignment. The question is whether there exists a prophet inequality for this problem that significantly beats the best known approximation factor of O(log m). We make major progress on this question by providing an O(log log m) prophet inequality. Our proof goes through a novel primal-dual approach. It is also constructive, resulting in an online policy that takes the form of static and anonymous item prices that can be computed in polynomial time given appropriate query access to the valuations. As an application of our approach, we construct a simple and incentive compatible mechanism based on posted prices that achieves an O(log log m) approximation to the optimal revenue for subadditive valuations under an item-independence assumption.
View PDF Chat

Online Allocation and Pricing: Constant Regret via Bellman Inequalities

2019-01-01
Alberto Vera , Siddhartha Banerjee , Itai Gurvich
We develop a framework for designing simple and efficient policies for a family of online allocation and pricing problems, that includes online packing, budget-constrained probing, dynamic pricing, and online contextual โ€ฆ We develop a framework for designing simple and efficient policies for a family of online allocation and pricing problems, that includes online packing, budget-constrained probing, dynamic pricing, and online contextual bandits with knapsacks. In each case, we evaluate the performance of our policies in terms of their regret (i.e., additive gap) relative to an offline controller that is endowed with more information than the online controller. Our framework is based on Bellman Inequalities, which decompose the loss of an algorithm into two distinct sources of error: (1) arising from computational tractability issues, and (2) arising from estimation/prediction of random trajectories. Balancing these errors guides the choice of benchmarks, and leads to policies that are both tractable and have strong performance guarantees. In particular, in all our examples, we demonstrate constant-regret policies that only require re-solving an LP in each period, followed by a simple greedy action-selection rule; thus, our policies are practical as well as provably near optimal.

Simple Mechanisms for Subadditive Buyers via Duality

2016-01-01
Yang Cai , Mingfei Zhao
We provide simple and approximately revenue-optimal mechanisms in the multi-item multi-bidder settings. We unify and improve all previous results, as well as generalize the results to broader cases. In particular, โ€ฆ We provide simple and approximately revenue-optimal mechanisms in the multi-item multi-bidder settings. We unify and improve all previous results, as well as generalize the results to broader cases. In particular, we prove that the better of the following two simple, deterministic and Dominant Strategy Incentive Compatible mechanisms, a sequential posted price mechanism or an anonymous sequential posted price mechanism with entry fee, achieves a constant fraction of the optimal revenue among all randomized, Bayesian Incentive Compatible mechanisms, when buyers' valuations are XOS over independent items. If the buyers' valuations are subadditive over independent items, the approximation factor degrades to $O(\log m)$, where $m$ is the number of items. We obtain our results by first extending the Cai-Devanur-Weinberg duality framework to derive an effective benchmark of the optimal revenue for subadditive bidders, and then analyzing this upper bound with new techniques.
View PDF Chat

Pricing for Online Resource Allocation: Intervals and Paths

2019-01-01
Shuchi Chawla , J. Benjamin Miller , Yifeng Teng
We present pricing mechanisms for several online resource allocation problems which obtain tight or nearly tight approximations to social welfare. In our settings, buyers arrive online and purchase bundles of โ€ฆ We present pricing mechanisms for several online resource allocation problems which obtain tight or nearly tight approximations to social welfare. In our settings, buyers arrive online and purchase bundles of items; buyersโ€™ values for the bundles are drawn from known distributions. This problem is closely related to the so-called prophet-inequality of Krengel and Sucheston [23] and its extensions in recent literature. Motivated by applications to cloud economics, we consider two kinds of buyer preferences. In the first, items correspond to different units of time at which a resource is available; the items are arranged in a total order and buyers desire intervals of items. The second corresponds to bandwidth allocation over a tree network; the items are edges in the network and buyers desire paths.Because buyersโ€™ preferences have complementarities in the settings we consider, recent constant-factor approximations via item prices do not apply, and indeed strong negative results are known. We develop static, anonymous bundle pricing mechanisms.For the interval preferences setting, we show that static, anonymous bundle pricings achieve a sublogarithmic competitive ratio, which is optimal (within constant factors) over the class of all online allocation algorithms, truthful or not. For the path preferences setting, we obtain a nearly-tight logarithmic competitive ratio. Both of these results exhibit an exponential improvement over item pricings for these settings. Our results extend to settings where the seller has multiple copies of each item, with the competitive ratio decreasing linearly with supply. Such a gradual tradeoff between supply and the competitive ratio for welfare was previously known only for the single item prophet inequality.
View PDF Chat

Online Independent Set Beyond the Worst-Case: Secretaries, Prophets, and Periods

2013-07-11
Oliver Gรถbel , Martin Hoefer , Thomas KeรŸelheim +2 more
We investigate online algorithms for maximum (weight) independent set on graph classes with bounded inductive independence number like, e.g., interval and disk graphs with applications to, e.g., task scheduling and โ€ฆ We investigate online algorithms for maximum (weight) independent set on graph classes with bounded inductive independence number like, e.g., interval and disk graphs with applications to, e.g., task scheduling and spectrum allocation. In the online setting, it is assumed that nodes of an unknown graph arrive one by one over time. An online algorithm has to decide whether an arriving node should be included into the independent set. Unfortunately, this natural and practically relevant online problem cannot be studied in a meaningful way within a classical competitive analysis as the competitive ratio on worst-case input sequences is lower bounded by $\Omega(n)$. As a worst-case analysis is pointless, we study online independent set in a stochastic analysis. Instead of focussing on a particular stochastic input model, we present a generic sampling approach that enables us to devise online algorithms achieving performance guarantees for a variety of input models. In particular, our analysis covers stochastic input models like the secretary model, in which an adversarial graph is presented in random order, and the prophet-inequality model, in which a randomly generated graph is presented in adversarial order. Our sampling approach bridges thus between stochastic input models of quite different nature. In addition, we show that our approach can be applied to a practically motivated admission control setting. Our sampling approach yields an online algorithm for maximum independent set with competitive ratio $O(\rho^2)$ with respect to all of the mentioned stochastic input models. for graph classes with inductive independence number $\rho$. The approach can be extended towards maximum-weight independent set by losing only a factor of $O(\log n)$ in the competitive ratio with $n$ denoting the (expected) number of nodes.

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.

Polymatroid Prophet Inequalities

2013-07-19
Paul Duetting , Robert Kleinberg
Consider a gambler and a prophet who observe a sequence of independent, non-negative numbers. The gambler sees the numbers one-by-one whereas the prophet sees the entire sequence at once. The โ€ฆ Consider a gambler and a prophet who observe a sequence of independent, non-negative numbers. The gambler sees the numbers one-by-one whereas the prophet sees the entire sequence at once. The goal of both is to decide on fractions of each number they want to keep so as to maximize the weighted fractional sum of the numbers chosen. The classic result of Krengel and Sucheston (1977-78) asserts that if both the gambler and the prophet can pick one number, then the gambler can do at least half as well as the prophet. Recently, Kleinberg and Weinberg (2012) have generalized this result to settings where the numbers that can be chosen are subject to a matroid constraint. In this note we go one step further and show that the bound carries over to settings where the fractions that can be chosen are subject to a polymatroid constraint. This bound is tight as it is already tight for the simple setting where the gambler and the prophet can pick only one number. An interesting application of our result is in mechanism design, where it leads to improved results for various problems.

On Revenue Monotonicity in Combinatorial Auctions

2018-01-01
Andrew Chi-Chih Yao
View PDF Chat

A Simple and Tight Greedy OCRS

2021-11-25
Vasilis Livanos
In recent years, Contention Resolution Schemes (CRSs), introduced by Chekuri, Vondr\'{a}k, and Zenklusen, have emerged as a general framework for obtaining feasible solutions to combinatorial optimization problems with constraints. The โ€ฆ In recent years, Contention Resolution Schemes (CRSs), introduced by Chekuri, Vondr\'{a}k, and Zenklusen, have emerged as a general framework for obtaining feasible solutions to combinatorial optimization problems with constraints. The idea is to first solve a continuous relaxation and then round the fractional solution. When one does not have any control on the order of rounding, Online Contention Resolution Schemes (OCRSs) can be used instead, and have been successfully applied in settings such as prophet inequalities and stochastic probing. Intuitively, a greedy OCRS has to decide which elements to include in the integral solution before the online process starts. In this work, we give a simple $1/e$ - selectable greedy single item OCRS, and then proceed to show that it is optimal.

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

Online Contention Resolution Schemes

2015-12-21
Moran Feldman , Ola Svensson , Rico Zenklusen
We introduce a new rounding technique designed for online optimization problems, which is related to contention resolution schemes, a technique initially introduced in the context of submodular function maximization. Our โ€ฆ We introduce a new rounding technique designed for online optimization problems, which is related to contention resolution schemes, a technique initially introduced in the context of submodular function maximization. Our rounding technique, which we call online contention resolution schemes (OCRSs), is applicable to many online selection problems, including Bayesian online selection, oblivious posted pricing mechanisms, and stochastic probing models. It allows for handling a wide set of constraints, and shares many strong properties of offline contention resolution schemes. In particular, OCRSs for different constraint families can be combined to obtain an OCRS for their intersection. Moreover, we can approximately maximize submodular functions in the online settings we consider.We, thus, get a broadly applicable framework for several online selection problems, which improves on previous approaches in terms of the types of constraints that can be handled, the objective functions that can be dealt with, and the assumptions on the strength of the adversary. Furthermore, we resolve two open problems from the literature; namely, we present the first constant-factor constrained oblivious posted price mechanism for matroid constraints, and the first constant-factor algorithm for weighted stochastic probing with deadlines.
View PDF Chat

Online Pandoraโ€™s Boxes and Bandits

2019-07-17
Hossein Esfandiari , MohammadTaghi Hajiaghayi , Brendan Lucier +1 more
We consider online variations of the Pandoraโ€™s box problem (Weitzman 1979), a standard model for understanding issues related to the cost of acquiring information for decision-making. Our problem generalizes both โ€ฆ We consider online variations of the Pandoraโ€™s box problem (Weitzman 1979), a standard model for understanding issues related to the cost of acquiring information for decision-making. Our problem generalizes both the classic Pandoraโ€™s box problem and the prophet inequality framework. Boxes are presented online, each with a random value and cost drawn jointly from some known distribution. Pandora chooses online whether to open each box given its cost, and then chooses irrevocably whether to keep the revealed prize or pass on it. We aim for approximation algorithms against adversaries that can choose the largest prize over any opened box, and use optimal offline policies to decide which boxes to open (without knowledge of the value inside)1. We consider variations where Pandora can collect multiple prizes subject to feasibility constraints, such as cardinality, matroid, or knapsack constraints. We also consider variations related to classic multi-armed bandit problems from reinforcement learning. Our results use a reduction-based framework where we separate the issues of the cost of acquiring information from the online decision process of which prizes to keep. Our work shows that in many scenarios, Pandora can achieve a good approximation to the best possible performance.
View PDF Chat

Improved Mechanisms and Prophet Inequalities for Graphical Dependencies

2024-07-08
Vasilis Livanos , Kalen Patton , Sahil Singla
View PDF Chat

On Submodular Prophet Inequalities and Correlation Gap

2021-01-01
Chandra Chekuri , Vasilis Livanos
Prophet inequalities and secretary problems have been extensively studied in recent years due to their elegance, connections to online algorithms, stochastic optimization, and mechanism design problems in game theoretic settings. โ€ฆ Prophet inequalities and secretary problems have been extensively studied in recent years due to their elegance, connections to online algorithms, stochastic optimization, and mechanism design problems in game theoretic settings. Rubinstein and Singla developed a notion of combinatorial prophet inequalities in order to generalize the standard prophet inequality setting to combinatorial valuation functions such as submodular and subadditive functions. For non-negative submodular functions they demonstrated a constant factor prophet inequality for matroid constraints. Along the way they showed a variant of the correlation gap for non-negative submodular functions. In this paper we revisit their notion of correlation gap as well as the standard notion of correlation gap and prove much tighter and cleaner bounds. Via these bounds and other insights we obtain substantially improved constant factor combinatorial prophet inequalities for both monotone and non-monotone submodular functions over any constraint that admits an Online Contention Resolution Scheme. In addition to improved bounds we describe efficient polynomial-time algorithms that achieve these bounds.

Approximately Maximizing the Broker's Profit in a Two-sided Market

2019-01-01
Jing Chen , Bo Li , Yingkai Li
We study how to maximize the broker's (expected) profit in a two-sided market, where she buys items from a set of sellers and resells them to a set of buyers. โ€ฆ We study how to maximize the broker's (expected) profit in a two-sided market, where she buys items from a set of sellers and resells them to a set of buyers. Each seller has a single item to sell and holds a private value on her item, and each buyer has a valuation function over the bundles of the sellers' items. We consider the Bayesian setting where the agents' values are independently drawn from prior distributions, and aim at designing dominant-strategy incentive-compatible (DSIC) mechanisms that are approximately optimal. Production-cost markets, where each item has a publicly-known cost to be produced, provide a platform for us to study two-sided markets. Briefly, we show how to covert a mechanism for production-cost markets into a mechanism for the broker, whenever the former satisfies cost-monotonicity. This reduction holds even when buyers have general combinatorial valuation functions. When the buyers' valuations are additive, we generalize an existing mechanism to production-cost markets in an approximation-preserving way. We then show that the resulting mechanism is cost-monotone and thus can be converted into an 8-approximation mechanism for two-sided markets.

Online purchasing under uncertainty

2018-01-29
Alan Frieze , Wesley Pegden
Abstract Suppose there is a collection of independent uniform random variables, and a hypergraph of target structures on the vertex set . We would like to purchase a target structure โ€ฆ Abstract Suppose there is a collection of independent uniform random variables, and a hypergraph of target structures on the vertex set . We would like to purchase a target structure at small cost, but we do not know all the costs x i ahead of time. Instead, we inspect the random variables x i one at a time, and after each inspection, choose to either keep the vertex i at cost x i , or reject vertex i forever. In the present paper, we consider the case where is the edgeโ€set of a complete graph (or digraph), and the target structures are the spanning trees of a graph, spanning arborescences of a digraph, the paths between a fixed pair of vertices, perfect matchings, Hamilton cycles or the cliques of some fixed size.
View PDF Chat

Linear Programming Based Near-Optimal Pricing for Laminar Bayesian Online Selection

2019-01-01
Nima Anari , Rad Niazadeh , Amin Saberi +1 more
In the Bayesian online selection problem, the goal is to design a pricing scheme for a sequence of arriving buyers that maximizes the expected social-welfare (or revenue) subject to different โ€ฆ In the Bayesian online selection problem, the goal is to design a pricing scheme for a sequence of arriving buyers that maximizes the expected social-welfare (or revenue) subject to different types of structural constraints. Inspired by applications in operations management, the focus of this paper is on the cases where the set of served customers is characterized by a laminar matroid.We give the first Polynomial-Time Approximation Scheme (PTAS) for the problem when the laminar matroid has constant depth. Our approach is based on rounding the solution of a hierarchy of linear programming relaxations that approximate the optimum online solution with any degree of accuracy plus a concentration argument that shows the rounding incurs a small loss. We also study another variation, which we call the production constrained problem, for which the allowable set of served customers is characterized by a collection of production and shipping constraints forming a certain form of laminar matroid. Using a similar LP-based approach, we design a PTAS for this problem even when the depth of the laminar matroid is not constant. The analysis exploits the negative dependency of the optimum selection rule in the lower-levels of the laminar family. Finally, we conclude with a discussion of the linear programming based approach employed in the paper and re-derive some of the classic prophet inequalities known in the literature.
View PDF Chat

Optimal Revenue Guarantees for Pricing in Large Markets

2021-01-01
Josรฉ R. Correa , Dana Pizarro , Vรญctor Verdugo
View PDF Chat

Random Order Contention Resolution Schemes

2018-10-01
Marek Adamczyk , Michaล‚ Wล‚odarczyk
Contention resolution schemes have proven to be an incredibly powerful concept which allows tackling a broad class of problems. The framework has been initially designed to handle submodular optimization under โ€ฆ Contention resolution schemes have proven to be an incredibly powerful concept which allows tackling a broad class of problems. The framework has been initially designed to handle submodular optimization under various types of constraints, that is, intersections of exchange systems (including matroids), knapsacks, and unsplittable flows on trees. Later on, it turned out that this framework perfectly extends to optimization under uncertainty, like stochastic probing and online selection problems, which further can be applied to mechanism design. We add to this line of work by showing how to create contention resolution schemes for intersection of matroids and knapsacks when we work in the random order setting. More precisely, we do know the whole universe of elements in advance, but they appear in an order given by a random permutation. Upon arrival we need to irrevocably decide whether to take an element or not. We bring a novel technique for analyzing procedures in the random order setting that is based on the martingale theory. This unified approach makes it easier to combine constraints, and we do not need to rely on the monotonicity of contention resolution schemes, as it was the case before. Our paper fills the gaps, extends, and creates connections between many previous results and techniques. The main application of our framework is a k + 4 + ฮต approximation ratio for the Bayesian multi-parameter unit-demand mechanism design under the constraint of k matroids intersection, which improves upon the previous bounds of 4k - 2 and e(k + 1). Other results include improved approximation ratios for stochastic k-set packing and submodular stochastic probing over arbitrary nonnegative submodular objective function, whereas previous results required the objective to be monotone.
View PDF Chat

Online Independent Set Beyond the Worst-Case: Secretaries, Prophets, and Periods

2014-01-01
Oliver Gรถbel , Martin Hoefer , Thomas KeรŸelheim +2 more
View PDF Chat

Information Elicitation for Bayesian Auctions

2018-01-01
Jing Chen , Bo Li , Yingkai Li
View PDF Chat

Single-Sample Prophet Inequalities Revisited.

2021-03-24
Constantine Caramanis , Matthew Faw , Orestis Papadigenopoulos +1 more
The study of the prophet inequality problem in the limited information regime was initiated by Azar et al. [SODA'14] in the pursuit of prior-independent posted-price mechanisms. As they show, $O(1)$-competitive โ€ฆ The study of the prophet inequality problem in the limited information regime was initiated by Azar et al. [SODA'14] in the pursuit of prior-independent posted-price mechanisms. As they show, $O(1)$-competitive policies are achievable using only a single sample from the distribution of each agent. A notable portion of their results relies on reducing the design of single-sample prophet inequalities (SSPIs) to that of order-oblivious secretary (OOS) policies. The above reduction comes at the cost of not fully utilizing the available samples. However, to date, this is essentially the only method for proving SSPIs for many combinatorial sets. Very recently, Rubinstein et al. [ITCS'20] give a surprisingly simple algorithm which achieves the optimal competitive ratio for the single-choice SSPI problem $-$ a result which is unobtainable going through the reduction to secretary problems. Motivated by this discrepancy, we study the competitiveness of simple SSPI policies directly, without appealing to results from OOS literature. In this direction, we first develop a framework for analyzing policies against a greedy-like prophet solution. Using this framework, we obtain the first SSPI for general (non-bipartite) matching environments, as well as improved competitive ratios for transversal and truncated partition matroids. Second, motivated by the observation that many OOS policies for matroids decompose the problem into independent rank-$1$ instances, we provide a meta-theorem which applies to any matroid satisfying this partition property. Leveraging the recent results by Rubinstein et al., we obtain improved competitive guarantees (most by a factor of $2$) for a number of matroids captured by the reduction of Azar et al. Finally, we discuss applications of our SSPIs to the design of mechanisms for multi-dimensional limited information settings with improved revenue and welfare guarantees.

Matroid secretary problem in the random assignment model

2011-01-23
Josรฉ A. Soto
In the Matroid Secretary Problem, introduced by Babaioff et al. [5], the elements of a given matroid are presented to an online algorithm in random order. When an element is โ€ฆ In the Matroid Secretary Problem, introduced by Babaioff et al. [5], the elements of a given matroid are presented to an online algorithm in random order. When an element is revealed, the algorithm learns its weight and decides whether or not to select it. The objective is to return a maximum weight independent set of the matroid. There are different variants for this problem depending on the information known about the weights beforehand.In the random assignment model, a hidden list of weights is randomly assigned to the matroid ground set, independently from the random order they are revealed to the algorithm. Our main result is the first constant competitive algorithm for this version of the problem, solving an open question of Babaioff et al. Our algorithm achieves a competitive ratio of 2e2/(e โˆ’ 1). It exploits the notion of principal partition of a matroid, its decomposition into uniformly dense minors, and a 2e-competitive algorithm for uniformly dense matroids we also develop.We also present constant competitive algorithms in the standard model where the weights are assigned adversarially, for various classes of matroids including cographic, low density, k-column sparse linear matroids and the case when every element is in a small cocircuit. In the same model, we give a new O(log r)-competitive algorithm for matroids of rank r which only uses the relative order of the weights seen and not their actual values, as previously needed.

On Variants of the Matroid Secretary Problem

2011-01-01
Shayan Oveis Gharan , Jan Vondrรกk
View PDF Chat

Comparison of Threshold Stop Rules and Maximum for Independent Nonnegative Random Variables

1984-11-01
Ester Samuelโ€Cahn
Let $X_i \geq 0$ be independent, $i = 1, \cdots, n$, and $X^\ast_n = \max(X_1, \cdots, X_n)$. Let $t(c) (s(c))$ be the threshold stopping rule for $X_1, \cdots, X_n$, defined โ€ฆ Let $X_i \geq 0$ be independent, $i = 1, \cdots, n$, and $X^\ast_n = \max(X_1, \cdots, X_n)$. Let $t(c) (s(c))$ be the threshold stopping rule for $X_1, \cdots, X_n$, defined by $t(c) = \text{smallest} i$ for which $X_i \geq c(s(c) = \text{smallest} i$ for which $X_i > c), = n$ otherwise. Let $m$ be a median of the distribution of $X^\ast_n$. It is shown that for every $n$ and $\underline{X}$ either $EX^\ast_n \leq 2EX_{t(m)}$ or $EX^\ast_n \leq 2EX_{s(m)}$. This improves previously known results, [1], [4]. Some results for i.i.d. $X_i$ are also included.
View PDF Chat

Prophet-type inequalities for multi-choice optimal stopping

1987-02-01
Douglas P. Kennedy

Algorithms for Secretary Problems on Graphs and Hypergraphs

2009-01-01
Nitish Korula , Martin Pรกl
View PDF Chat

Bayesian Combinatorial Auctions: Expanding Single Buyer Mechanisms to Many Buyers

2011-10-01
Saeed Alaei
For Bayesian combinatorial auctions, we present a general framework for approximately reducing the mechanism design problem for multiple buyers to the mechanism design problem for each individual buyer. Our frame- โ€ฆ For Bayesian combinatorial auctions, we present a general framework for approximately reducing the mechanism design problem for multiple buyers to the mechanism design problem for each individual buyer. Our frame- work can be applied to any setting which roughly satisfies the following assumptions: (i) the buyer's types must be distributed independently (not necessarily identically), (ii) the objective function must be linearly separable over the set of buyers, and (iii) the supply constraints must be the only constraints involving more than one buyer. Our framework is general in the sense that it makes no explicit assumption about any of the following: (i) the buyer's valuations (e.g., submodular, additive, etc), (ii) The distribution of types for each buyer, and (iii) the other constraints involving individual buyers (e.g., budget constraints, etc). We present two generic ra-buyer mechanisms that use 1- buyer mechanisms as black boxes. Assuming that we have an ฮฑ-approximate 1-buyer mechanism for each buyer and assuming that no buyer ever needs more than 1/k of all copies of each item for some integer k โ‰ฅ 1, then our generic n- buyer mechanisms are ฮณ <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">k</sub> ยท ฮฑ-approximation of the optimal n-buyer mechanism, in which ฮณ <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">k</sub> is a constant which is at least 1 - 1/โˆš(k+3). Observe that ฮณ <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">k</sub> is at least1/2 (for k = 1) and approaches 1 as k increases. As a byproduct of our construction, we improve a generalization of prophet inequalities. Furthermore, as applications of our main theorem, we improve several results from the literature.
View PDF Chat

Comparison of optimal value and constrained maxima expectations for independent random variables

1986-06-01
Robert P. Kertz
For all uniformly bounded sequences of independent random variables X 1 , X 2, ยทยทยท, a complete comparison is made between the optimal value V ( X 1 , X โ€ฆ For all uniformly bounded sequences of independent random variables X 1 , X 2, ยทยทยท, a complete comparison is made between the optimal value V ( X 1 , X 2 , ยทยทยท) = sup { EX t :t is an (a.e.) finite stop rule for X 1, X 2 , ยทยทยท} and , where M i ( X 1, X 2 , ยทยทยท) is the i th largest order statistic for X 1 , X 2 , ยทยทยท In particular, for k&amp;gt; 1, the set of ordered pairs {( x , y ): x = V ( X 1 , X 2, ยทยทยท) and for some independent random variables X 1 , X 2 , ยทยทยท taking values in [0, 1]} is precisely the set , where B k (0) = 0, B k (1) = 1, and for The result yields sharp, universal inequalities for independent random variables comparing two choice mechanisms, the mortal&amp;amp;s value of the game V ( X 1 , X 2, ยทยทยท) and the prophet&amp;amp;s constrained maxima expectation of the game . Techniques of proof include probability- and convexity-based reductions; calculus-based, multivariate, extremal problem analysis; and limit theorems of Poisson-approximation type. Precise results are also given for finite sequences of independent random variables.

Bayesian Combinatorial Auctions: Expanding Single Buyer Mechanisms to Many Buyers

2011-06-06
Saeed Alaei
For Bayesian combinatorial auctions, we present a general framework for approximately reducing the mechanism design problem for multiple buyers to single buyer sub-problems. Our framework can be applied to any โ€ฆ For Bayesian combinatorial auctions, we present a general framework for approximately reducing the mechanism design problem for multiple buyers to single buyer sub-problems. Our framework can be applied to any setting which roughly satisfies the following assumptions: (i) buyers' types must be distributed independently (not necessarily identically), (ii) objective function must be linearly separable over the buyers, and (iii) except for the supply constraints, there should be no other inter-buyer constraints. Our framework is general in the sense that it makes no explicit assumption about buyers' valuations, type distributions, and single buyer constraints (e.g., budget, incentive compatibility, etc). We present two generic multi buyer mechanisms which use single buyer mechanisms as black boxes; if an $\alpha$-approximate single buyer mechanism can be constructed for each buyer, and if no buyer requires more than $\frac{1}{k}$ of all units of each item, then our generic multi buyer mechanisms are $\gamma_k\alpha$-approximation of the optimal multi buyer mechanism, where $\gamma_k$ is a constant which is at least $1-\frac{1}{\sqrt{k+3}}$. Observe that $\gamma_k$ is at least 1/2 (for $k=1$) and approaches 1 as $k \to \infty$. As a byproduct of our construction, we present a generalization of prophet inequalities. Furthermore, as applications of our framework, we present multi buyer mechanisms with improved approximation factor for several settings from the literature.

Comparison of optimal value and constrained maxima expectations for independent random variables

1986-06-01
Robert P. Kertz
For all uniformly bounded sequences of independent random variables X 1 , X 2, ยทยทยท, a complete comparison is made between the optimal value V ( X 1 , X โ€ฆ For all uniformly bounded sequences of independent random variables X 1 , X 2, ยทยทยท, a complete comparison is made between the optimal value V ( X 1 , X 2 , ยทยทยท) = sup { EX t :t is an (a.e.) finite stop rule for X 1, X 2 , ยทยทยท} and , where M i ( X 1, X 2 , ยทยทยท) is the i th largest order statistic for X 1 , X 2 , ยทยทยท In particular, for k&gt; 1, the set of ordered pairs {( x , y ): x = V ( X 1 , X 2, ยทยทยท) and for some independent random variables X 1 , X 2 , ยทยทยท taking values in [0, 1]} is precisely the set , where B k (0) = 0, B k (1) = 1, and for The result yields sharp, universal inequalities for independent random variables comparing two choice mechanisms, the mortal&amp;s value of the game V ( X 1 , X 2, ยทยทยท) and the prophet&amp;s constrained maxima expectation of the game . Techniques of proof include probability- and convexity-based reductions; calculus-based, multivariate, extremal problem analysis; and limit theorems of Poisson-approximation type. Precise results are also given for finite sequences of independent random variables.