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.

In this work we consider the problem of online submodular maximization under a cardinality constraint with differential privacy (DP). A stream of T submodular functions over a common finite ground set U arrives online, and at each time-step the decision maker must choose at most k elements of U before observing the function. The decision maker obtains a profit equal to the function evaluated on the chosen set and aims to learn a sequence of sets that achieves low expected regret. In the full-information setting, we develop an $(\varepsilon,\delta)$-DP algorithm with expected (1-1/e)-regret bound of $O( \frac{k^2\log |U|\sqrt{T \log k/\delta}}{\varepsilon} )$. This algorithm contains k ordered experts that learn the best marginal increments for each item over the whole time horizon while maintaining privacy of the functions. In the bandit setting, we provide an $(\varepsilon,\delta+ O(e^{-T^{1/3}}))$-DP algorithm with expected (1-1/e)-regret bound of $O( \frac{\sqrt{\log k/\delta}}{\varepsilon} (k (|U| \log |U|)^{1/3})^2 T^{2/3} )$. One challenge for privacy in this setting is that the payoff and feedback of expert i depends on the actions taken by her i-1 predecessors. This particular type of information leakage is not covered by post-processing, and new analysis is required. Our techniques for maintaining privacy with feedforward may be of independent interest.