1 May 2022 in Mathematics of Operations Research
A central object of study in optimal stopping theory is the single-choice prophet inequality for independent and identically distributed random variables: given a sequence of random variables [ ] drawn independently from the same distribution, the goal is to choose a stopping time τ such that for the maximum value of α and for all distributions, [ ]. What makes this problem challenging is that the decision whether [ ] may only depend on the values of the random variables [ ] and on the distribution F. For a long time, the best known bound for the problem had been [ ], but recently a tight bound of [ ] was obtained. The case where F is unknown, such that the decision whether [ ] may depend only on the values of the random variables [ ], is equally well motivated but has received much less attention. A straightforward guarantee for this case of [ ] can be derived from the well-known optimal solution to the secretary problem, where an arbitrary set of values arrive in random order and the goal is to maximize the probability of selecting the largest value. We show that this bound is in fact tight. We then investigate the case where the stopping time may additionally depend on a limited number of samples from F, and we show that, even with o(n) samples, [ ]. On the other hand, n samples allow for a significant improvement, whereas [ ] samples are equivalent to knowledge of the distribution: specifically, with n samples, [ ] and [ ], and with [ ] samples, [ ] for any [ ].
14 September 2018 in Mathematics of Operations Research
Ideally, the properties of an economic mechanism should hold in a robust way across multiple equilibria and under varying assumptions regarding the information available to participants. Focusing on the design of robust position auctions, we seek mechanisms that possess an efficient equilibrium and guarantee high revenue in every efficient equilibrium, under complete and incomplete information. A generalized first-price auction that is expressive in the sense of allowing multidimensional bids turns out to be the only standard design able to achieve this goal, even when valuations are one dimensional. The equilibria under complete information are obtained via Bernheim and Whinston’s profit target strategies, those under incomplete information via an appropriate generalization thereof. Particularly interesting from a technical perspective is the incomplete information case, where the standard technique for establishing equilibrium existence due to Myerson is generalized to a setting in which the bid space h...
1 February 2024 in Games and Economic Behavior
1 May 2019 in Operations Research Letters