Lookback Prophet Inequalities

Summary

This paper extends the standard online selection problem by enabling the decision-maker to choose previous items with some discount that is captured by decay functions. The authors analyze the competitive ratio for different observation orders by giving a reduction from general decay functions to simple decay function.

Strengths

1. This paper extends the standard prophet inequality to a more general and realistic form. 2. This paper gives a general reduction that characterizes the property of decay functions. 3. The competitive ratio for adversarial order is tight.

Weaknesses

1. The analyses for random order and IID cases are not ideal. It seems neither upper nor lower bounds are tight for general $\gamma$. 2. I am not sure about the technical contribution of this paper. What is the biggest technical challenge in the analysis?

Questions

1. What is the biggest technical challenge in the analysis? 2. I feel it is better to emphasize the choice of distribution with support ${0,a,b}$ when proving the upper bound of $\gamma$-prophet inequality (maybe change the statement of theorems). This is because $CR^D(ALG) \le \sup_A \frac{\mathbb{E}[A^{\gamma_D}(I)]}{\mathbb{E}[OPT(I)]}$ for $I$ taking values in $0,a,b$ and $\sup_A CR^{\gamma_D}(A) = \sup_A \inf_I \frac{\mathbb{E}[A^{\gamma_D}(I)]}{\mathbb{E}[OPT(I)]} \le f(\gamma_D)$ (current statement in Theorem 4.4/4.5) does not directly imply $CR^D(ALG) \le f(\gamma_D)$.

Rating

5

Confidence

3

Soundness

3

Presentation

3

Contribution

2

Limitations

Yes.

Summary

**Problem Studied** This paper introduces the problem of "lookback prophet inequalities", which is a variant of prophet inequalities. In this problem, at the stopping time, instead of always selecting the current item, the algorithm is allowed to select any item that has arrived up to now. However, items in the past have their value discounted by known decay functions. The goal is to design algorithms with a good competitive ratio, which is the ratio of the algorithm's expected value to the expectation of the highest-value item in hindsight. **Main Results / Contributions** The first main contribution of this paper is to define the problem of lookback prophet inequalities. The paper considers the problem in the adversarial order, random order, and IID models. It turns out that for all three models, when analyzing the worst-case competitive ratio, one can assume that the decay functions are all of the form $x \to \gamma x$, for some $\gamma$. For the adversarial model, matching upper and lower bounds are derived. For the random order and IID models, upper and lower bounds are derived, but they do not match.

Strengths

The paper is generally well-written. The definitions and theorem statements are clear, and the proof sketches in the first 9 pages of the paper gives the reader a good intuition about why the statements are true. The paper introduces a new problem (lookback prophet inequalities), which to my knowledge has not be studied before. The problem definition is clean and I think it is a reasonably natural formulation.

Weaknesses

There are already numerous papers on variants of the prophet inequality, and this paper introduces yet another one. At this point, one must question how interesting or significant this contribution is. However, the problem definition appears reasonable, and the proofs seem to be fairly clean, which is why I am recommending a weak acceptance.

Questions

1. I think the real estate example doesn't make too much sense. If the seller returns to a previous buyer, and it turns out the buyer is no longer interested, the seller can continue to sell the house. 2. The restaurant example also seems a bit strange to me. If the cost of revisiting a restaurant depends on the distance you need to walk back to it, this doesn't seem to be capturable with the current definitions of the decay functions, no? (Currently, the decay functions only model how many steps back into the past you look. E.g. If you are going from restaurant 3 to restaurant 1, this uses the same decay function as going from restaurant 5 to restaurant 3.) 3. It seems like the reduction to $\mathcal{D}_\infty$ relies on the fact that $n$ goes to infinity. Are there better competitive ratios that are possible for a fixed $n$? 4. There are several typos in the paper, notably in the title ("Inequalitites" -> "Inequalities").

Rating

6

Confidence

3

Soundness

4

Presentation

3

Contribution

2

Limitations

Yes.

Summary

This paper studies a variant of prophet inequalities where the agent can reuse a previous item at a decaying price. Analyzing three models, adversarial model, random order model, and iid model, this paper gives various lower and upper bounds about the competitve ratio that an algorithm may achieve in these setups. The paper mainly follows a reduction idea. It first show that for any decaying function family $\mathcal D$, the optimal competitive ratio is close to that for the limiting decaying function $D_{\infty}$, which reduces the $\mathcal D$-prophet problem to a $D_{\infty}$ one. This idea is further generalized so that it suffices to consider linear functions (i.e., $x\mapsto \gamma x$ for some $\gamma$) as the CR for $D_{\infty}$ is again close to that of $x\mapsto (\lim_{x\to \infty} \frac{D_{\infty}(x)}{x})x$. Equipped with these reductions, the authors 1. establish an upper bound on the CR in the adversarial model, where a matching online algorithm is also proposed; 2. develop an upper bound that is more general than previous works (considering classical prophet inequalities) in the random order model, but the lower bound algorithm is neither computationally feasible nor optimal; and 3. design an algorithm in the iid case whose asymptotic CR is the same as that in the random order model.

Strengths

1. The setup is new, and it looks to of importance. 1. The paper is well-written so it is easy to get the intuitions behind the reductions. 2. The result for adversarial case is optimal.

Weaknesses

1. For the first reduction ($\mathcal D$ to $D_{\infty}$), it seems that only some order models mentioned in the main text allows such a reduction. Why you only consider these models, and are there any other models excluded from this reduction (or do you have any intuition on what kinds of order models can ensure the reduction)? 2. For random order models and iid models, the algorithms designed are sub-optimal and cannot be implemented easily.

Questions

1. See Weakness 1 2. 'However, considering larger classes of algorithms, the competitive ratios achieved in the IID model are better than those of the random order model.' Can you give some examples? I see in the limitations you mentioned that such algorithms are not designed in your $\mathcal D$-prophet model. Why they do not generalize?

Rating

6

Confidence

3

Soundness

3

Presentation

4

Contribution

3

Limitations

Clearly stated