A typical goal for a gambler facing an online selection problem is to choose the best element, particularly in comparison to the best hindsight-optimal selection. This objective is nontrivial when there is high competition for top elements. For example, highly skilled job candidates are often recruited by top companies, leaving less competitive companies with the remaining candidates. This phenomenon introduces nontrivial correlations among the remaining candidates; hence, a gambler facing this problem with misaligned beliefs might act sub optimally if she expects a top element to still be available for selection. Motivated by these considerations, we introduce the residual prophet inequality (k-RPI) problem. In the k-RPI problem, we consider a finite sequence of n nonnegative independent random values with known distributions and a known integer 0 ≤ k ≤ n - 1. Before the gambler observes the sequence, the top k values are removed from the sequence whereas the remaining n - k values are streamed sequentially to the gambler. Upon observing a value, the gambler must decide irrevocably if to accept/reject a value without the possibility of revisiting past values. We study two variants of k-RPI, according to whether the gambler learns online of the identity of the variable that he sees (FI-model) or not (NI-model). Our main result is a randomized algorithm in the FI-model with competitive ratio of at least 1/(k + 2), which we show is tight. Our algorithm is data-driven and requires access only to the k + 1 largest values of a single sample from the n input distributions. In the NI-model, we provide a similar algorithm that guarantees a competitive ratio of 1/(2k + 2). We further analyze independent and identically distributed instances when k = 1. We build a single-threshold algorithm with a competitive ratio of at least 0.4901, and show that no single-threshold strategy can get a competitive ratio greater than 0.5464.

Research on dynamic pricing has been growing during the last four decades due to its use in practice by a variety of companies as well as the several model variants that can be considered. In this work, we consider the particular pricing problem where a firm wants to sell one item to a single buyer in order to maximize expected revenues. The firm commits to a price function over an infinite horizon. The buyer has a private value for the item and purchases at the time when his utility is maximized. In our model, the buyer is more impatient than the seller and we study how important is to observe the buyer time arrival in terms of the seller's expected revenue. When the seller can observe the arrival of the buyer, she can make the price function contingent on the buyer's arrival time. On the contrary, when the seller cannot observe the arrival, her price function is fixed at time zero for the whole horizon. The value of observabilityis defined as the worst case ratio between the expected revenue of the seller when she observes the buyer's arrival and that when she does not. Our main result is to prove that in a very general setting, the value of observability is at most~4.911. To obtain this result we fully characterize the observable setting and use this solution to construct a random and periodic price function for the unobservable case.