Intrinsic Robustness of Prophet Inequality to Strategic Reward Signaling

We sincerely thank the reviewer for the positive feedback! Please find below our response to your comment.

$(\alpha, \beta)$ Pareto frontier We thank the reviewer for this very interesting comment. Characterizing the Pareto frontier of the approximation ratios requires substantial additional effort. So far we do not have a clear picture on how this Pareto frontier would look like, and we agree with the reviewer this is an interesting open question to explore as the future work.

We sincerely thank the reviewer for the positive feedback! Please find below our response to each of your comments.

The generality of threshold policies The reason that we restrict our attention to the threshold policies is that they are the policies that achieve the classic prophet inequality in the non-strategic setting. Given that our main focus in this work is to understand the robustness of the classic prophet inequality, it is indeed without loss to focus on the threshold policies. We will make this point more clear in the revision.

Threatening policy This is a great point and we also thought about it previously. However, we felt that the threatening policy is not natural because it is not a subgame perfect Nash, which is the standard solution concept in such sequential interactions. Our model can be viewed as an approximate version of subgame perfect Nash, where the first player (i.e. the searcher) plays an approximately optimal strategy from a simple policy space (the exact optimal stopping policy is likely very complex). The motivation for adopting such approximately optimal yet simple policy naturally echoes the entire literature on prophet inequality.

Connections to [19] We thank the reviewer for pointing out the connection to the [19]. It is indeed interesting to see that the player’s optimal information revealing strategy has the similar structure to the response of the value maximizing buyers studied in [19], especially given that the player in our setting and the buyer in [19] have two very different optimization problems. We will add a discussion on this connection in the revision.

After going through the hard example provided in [19], we can conclude that the same example can also be used in our setting to show the best approximation ratio that one can achieve for a static threshold policy is strictly smaller than 0.5 under a strategic setting, implying that a $1/2$-robustness is impossible for static threshold policy. We appreciate the reviewer for bringing out this impossibility result in [19] to our attention, and we will for sure add this result!

½-approximation policy in strategic settings The reviewer is correct that there always exists an ½ approximation policy for the strategic settings. Indeed, the reviewer’s proposed method for constructing such a policy is essentially the dynamic threshold stopping policy (using different thresholds for different players) that we mentioned in Line 368 about our preliminary result.

We sincerely thank the reviewer for the feedback and valuable comments! We notice that there may exist some conceptual misunderstandings in the reviewer's comments about the searcher’s stopping policy and the reason for us to study threshold stopping policies. So we would like to first clarify these potential misunderstandings and then provide our response to the other comments.

Clarification of the searcher’s stopping policy We kindly recall that $\phi_i(\cdot \mid X_i)$ denotes the probability distribution over the signal space when the player $i$’s realized reward is $X_i$. Here, the signal space could be an arbitrary measurable space. Thus, directly comparing the realized signal with the stopping threshold is not feasible..

Indeed, the stopping threshold $T$ is used for the searcher to decide whether she should accept the realized reward or move to the next player. Yet in our setting, even though the searcher is not able to directly observe the realized reward, she can observe the realized signal. With the observed signal, the searcher is able to derive a Bayesian posterior belief over the underlying realized reward $X_i$. Then the stopping threshold $T$ is used for the searcher to decide whether she should accept the current player by looking at whether the mean of this posterior belief is larger or smaller than the stopping threshold $T$.

For example, if the reward distribution is uniform over $[0, 1]$, and the signaling scheme is $\phi(X_i) = \Bbb{1}_{X_i > a}$ (i.e., the searcher can observe whether the realized reward is smaller or larger than $a$), and if the searcher observes a signal that tells \indicator{X_i > a} = 1, then the searcher is able to update her Bayesian posterior and know that the expected realized reward should equal to (1+a)/2. Consequently, the searcher’s decision should be based on comparing $(1+a)/2$ and the stopping threshold $T$.

Benchmarking within the threshold stopping policies We would like to clarify that the primary goal of this work, as also apparent from the paper's title, is to understand whether the well-studied prophet inequality (which is achieved by the static threshold stopping policies with the thresholds defined in Definition 2.2) is robust to the players’ strategical reward signaling. Our motivation is to study how these threshold stopping policies would perform if the players are strategically disclosing reward information (also known as the “best-of-both-worlds” style of results). Characterizing the approximation ratio for general stopping policies is also an interesting question (with a different motivation), but is beyond the scope of this paper.

Optimal revealing strategy when the searcher follows a threshold policy We would like to clarify that our characterized optimal information revealing strategy actually holds as long as the researcher uses a stopping policy that only depends on the reward distributions $(H_i)_{i\in[N]}$. So it is beyond just "following a threshold policy" as the reviewer suggested. On the other hand, as we mentioned in Remark 3.2, when the searcher’s stopping policy is more generally allowed to even depend on the realized signal or the information strategies, the subgame Perfect Nash equilibrium among players’ game would adopt significantly more complex structures and it requires complex backward induction analysis. While analyzing this challenging situation could also be a technically interesting question, it deviates from our current paper’s motivation of analyzing classic prophet inequality’s robustness to strategic rewards, and could be suitable for a future work focusing on developing new prophet inequalities under strategically revealed reward signals.

1-1/e competitive ratio for iid case The 0.745 competitive ratio for the iid case in the non-strategic setting is achieved by an adaptive threshold policy where the threshold for each player can depend on the previous reward realizations. This policy, however, is beyond the scope of this work as we focus on understanding how the classic static threshold policy performs (in both non-strategic and strategic settings). This is not to suggest that a dynamic threshold is uninteresting, but we aimed to maintain coherence in our results and avoid overwhelming readers with too many different settings. This is especially important as this study is the first of its kind, and the static threshold setting, while basic, is already quite intriguing.
The 1-1/e competitive ratio, to our best knowledge, can be indeed achieved by a static threshold policy but requires some careful probabilistic tie-breaking rule when the searcher faces a tie between the realized reward and the stopping threshold (e.g., https://arxiv.org/pdf/2108.12893). While in our paper, we focus on a deterministic tie-breaking rule where the searcher always accepts the player if the expected realized reward is no smaller than the stopping threshold. The rationale behind this focus is that: (1) this class of static threshold policy with this simple tie-breaking rule are indeed effective policies for the classic prophet inequality, and we are studying their robustness in this paper; (2) they are more straightforward to implement in real-life cases. Lastly, we also kindly remark that in Corollary 5.3, we show there exists a static threshold policy that is 1-1/e approximation under the strategic setting (and this ratio is tight), however such policy has a bad performance in the non-strategic setting. Notice that our Proposition 5.2 rules out the possibility for all possible static threshold stopping policies (being within the spectrum in Definition 2.2 or beyond) to achieve $\alpha$-robustness with $\alpha>1/2$.

I thank the authors for their response.

• Clarification of the searcher’s stopping policy. I thank them for the clarification.
• Benchmarking within the threshold stopping policies I agree that studying algorithms with adaptive thresholds is highly challenging. However, in many variants of prophet inequalities, when the observation order is fixed, as in the current paper, static threshold policies are enough to achieve an optimal competitive ratio. I am curious to know if this is the case also in the current problem or if adaptive thresholds can yield better competitive ratios. My question is not about studying general threshold policies, but instead on proving the optimality, or not, of the proposed static threshold policy among all algorithms, or at least among all algorithms with static thresholds (beyond the limited spectrum of Definition 2.2).
• 1-1/e competitive ratio for iid case The competitive ratio of $1-1/e$ in the iid case is achieved by a simple static threshold algorithm, which does not seem to require a random tie-breaking rule, see the proof of Theorem 3.1 in https://arxiv.org/pdf/2205.05519. I still believe that in the iid case, it makes much more sense to require a competitive ratio of 1-1/e in the non-strategic setting instead of 1/2.

The authors' response addressed some of my concerns, though not all. However, in light of the other reviews and all the authors' responses, I have slightly raised my score to lean towards acceptance.

I thank the authors for all the clarifications. I strongly encourage them to include the additional discussion of the IID case, and state more explicitly the limitations of their work indicated during the rebuttal in the revised version of the paper.

The authors have addressed most of my concerns. I raised my score to reflect my satisfaction with their responses.

We sincerely thank the reviewer for the positive feedback and valuable comments/suggestions! Please find our response to each of your questions below.

Q1: Results for i.i.d case We would like to first clarify that, to the best of our knowledge, the existence of a static threshold policy that achieves $1-1/e$ CR in non-strategic IID setting requires that the searcher carefully breaks the ties when she faces a tie between the realized reward and the stopping threshold (i.e. it involves some probabilistic tie-breaking, especially when facing distributions with masses). While in our setting, we consider a static threshold policy where the searcher always accepts the player when the expected realized reward is no smaller than the stopping threshold (see Definition 2.1). Thus, our negative result in Proposition 5.2 indeed excludes the case mentioned by the reviewer.

However, we note that the reviewer might be asking that if there exists a static threshold that achieves an ½ CR in non-strategic setting and an 1-1/e CR in strategic setting. The answer to this question is also no: consider the example of $5$ iid distributions with binary support $\{4.2,s\}$ where $s$ is sufficiently large and the mean is $5$. One can compute in this case that $\lim_{s \to \infty} \text{OPT} = \lim_{s \to \infty} (\frac{s-5}{s-4.2})^5 \cdot 4.2 + (1 - (\frac{s-5}{s-4.2})^5) \cdot s = 8.2$. We first assume such a threshold $T$ exists. For the non-strategic setting, if $T > 4.2$, then the searcher only accepts realized reward $s$, so the searcher’s payoff is $\lim_{s \to \infty} (1 - (\frac{s-5}{s-4.2})^5) \cdot s = 4$. Clearly $4/8.2 < ½$ so we must have $T \le 4.2$. Then in the strategic setting, if $T \le 4.2$, then the searcher would always accept the first player, so her payoff is $5$ with clearly $\frac{5}{8.2} < 1-1/e$, showing that such a $T$ ceases to exist. This example also shows that $T=F^{-1}(1-1/n)$ does not achieve $½$ CR in a non-strategic setting. In fact, if we consider the same example of $5$ iid distributions on binary support $\{t,s\}$ but letting $t \to 5$ instead of $t = 4.2$, we can see that since $T > t$, the searcher only accepts reward $s$ in the non-strategic setting. If $t$ becomes close enough to $5$ and $s$ is large enough we see that the non-strategic CR for such $T$ can actually approach zero.

However, we note that extending our results to more general stopping policies would be definitely an interesting future direction. We will add corresponding discussions in the revision.

Q2: Better results in strategic setting while ignoring performance in non-strategic setting When ignoring the performance in non-strategic setting, in the paper we show that the best approximation ratio that a static threshold stopping policy can achieve is $(1-1/e)/2$. So far it is unclear to us if this ratio could be improved for the static threshold stopping policy. Indeed, Reviewer 1242 pointed out a hard example provided in [19], under the same example we can conclude that the best approximation ratio of a static threshold policy one can achieve is no more than 0.4823 when players are strategic. However, whether $(1-1/e)/2$ is the optimal or if it can be improved for static threshold stopping policies still remains an open question, and we consider it as an intriguing future work.

Q3: Prophet secretary Thanks for bringing out this interesting extension. We think the results we establish in Section 3 (i.e. characterizing the player’s optimal information revealing strategy when the searcher adopts a threshold stopping policy) still hold. Characterizing strategic-robust stopping policy may require significant effort for this problem and we leave it as another interesting future direction.

Q4: Comparisons to [29] We thank the reviewer for this suggestion. We agree with the reviewer and will add more discussions about the comparison to the work [29].

Q5: Different payoff structure Our results can be easily extended to the setting where each player $i$ has a payoff $v_i \ge 0$ if his reward is accepted and 0 otherwise (please see our footnote 6 for this discussion). Using the terminology in information design, here the player’s payoff is essentially state-independent (i.e., it only depends on the searcher’s action and not on the realized reward $X_i$). It would be interesting to explore how the results would change if the player’s payoff is state-dependent.

Q6: Existence of $T^\dagger$ and $T^*$ We thank the reviewer for this suggestion. We will add a comment about the existence of $T^\dagger$ and $T^*$. The proofs in the main text are for the continuous distributions, thus $T^\dagger$ and $T^*$ always exists. The definitions of $T^\dagger$ and $T^*$ are slightly different for the distributions with atoms, and they also always exist.

Q7: Additional assumptions for log-concave distributions We acknowledge that, after extensive simulations, we did not find an instance with log-concave distributions that has strictly smaller than ½-robustness when this instance does not satisfy the given conditions. These assumptions are meant to serve as smoothing parameters to imitate nice behavior of endpoints on [0,1]. We believe relaxing these assumptions may require significant effort and we leave it as an intriguing future work.