Intrinsic Robustness of Prophet Inequality to Strategic Reward Signaling

Authors: wei  tang
haifeng  xu
ruimin  zhang
derek  zhu
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-15 03:22:46

Abstract: Prophet inequality concerns a basic optimal stopping problem and states that simple threshold stopping policies --- i.e., accepting the first reward larger than a certain threshold --- can achieve tight $\frac{1}{2}$-approximation to the optimal prophet value. Motivated by its economic applications, this paper studies the robustness of this approximation to natural strategic manipulations in which each random reward is associated with a self-interested player who may selectively reveal his realized reward to the searcher in order to maximize his probability of being selected. 

We say a threshold policy is $\alpha$(-strategically)-robust if it (a) achieves the  $\alpha$-approximation to the prophet value for strategic players; and (b) meanwhile remains a  $\frac{1}{2}$-approximation in the standard non-strategic setting.
Starting with a characterization of each player's optimal information revealing strategy, we demonstrate the intrinsic robustness of prophet inequalities to strategic reward signaling through the following results:
(1) for arbitrary reward distributions, there is a threshold policy that is $\frac{1-\frac{1}{e}}{2}$-robust, and this ratio is tight;
(2) for i.i.d. reward distributions, there is a threshold policy that is $\frac{1}{2}$-robust, which is tight for the setting; 
and (3) for log-concave (but non-identical) reward distributions, the $\frac{1}{2}$-robustness can also be achieved under certain regularity assumptions.

Main paper: 
 introduction: 
 The prophet inequality of Krengel and Sucheston [37] is a foundational framework for the theory of optimal stopping problems and sequential decision-making. In the classic prophet inequality, a searcher faces a finite sequence of non-negative, real-valued and independent random variables X 1 , . . . , X N with known distributions H i from which a reward of value X i is drawn sequentially for i = 1, . . . , N . Once a random reward is realized, the searcher decides whether to accept the realized reward and stop searching, or reject the reward and proceed to the next reward. The searcher's objective is to maximize the value of the accepted reward. The performance of the searcher's stopping policy is evaluated against a prophet value which equals to the ex-post maximum realized reward. The classic and elegant result of Samuel-Cahn [42] showed that a simple static threshold policy achieves at least half of the prophet value, and surprisingly, this bound is the best possible even among dynamic policies. Samuel-Cahn's policy uses the threshold that is the median of the distribution of the highest prizes, and then accepts the first realized reward that exceeds this threshold. The existence of this 1 /2-approximation is now known as the prophet inequality.Recently, there is a regained interest of the prophet inequality due to its beautiful connection to online mechanism design (see, e.g., [31, 16] ), and many different settings of the prophet inequality have been studied (see the survey by [40, 19] ). For example, Kleinberg and Weinberg [36] extend the prophet inequality to all matroid constraints and similar to [42] , they also show that a threshold stopping policy with the threshold equal to half of the expected maximum reward can also lead to the optimal 1 /2-approximation. Indeed, it is now well-known that there exists a range of thresholds for the classic prophet inequality that can achieve the optimal 1 /2-approximation (see Definition 2.2).An important assumption in the classic prophet inequality is that the distribution of each random variable is an inanimate object and, once the searcher reaches it, it will fully disclose its realized reward to the searcher. Yet this may not be the case in many real-world applications where each distribution may often be associated with a strategic player 6 who may have incentives to selectively disclose information to maximize his own probability of being chosen by the searcher. This is usually the case when information is not controlled by nature but by humans or algorithms. Such examples are ample in economic activities. For instance, when a recruiter searches for the best candidate for a position by sequentially interviewing a set of job applicants, each job applicant is naturally a strategic player and would want to control how much information they disclose about their characteristics (including strengths, weaknesses, personality, and experience) to the recruiter (the searcher) so as to maximize the probability of being hired. Similarly, when a venture capitalist searches for the most promising startup to invest by sequentially visiting each startup, the startups are strategic players. They have more accurate information about their own potential and can control how much of this information they disclose to attract the investment from the venture capitalist (the searcher). Finally, in the real estate market, when a buyer searches for the most attractive property to purchase, the property sellers are strategic players who can control the amount of information they disclose about the property's condition and potential returns to the buyer (the searcher).Motivated by real-world applications like above, we introduce and study a natural variant of the prophet inequality where each reward distribution is associated with a strategic player who can decide what information about the realized reward will be disclosed to the searcher. To capture such partial information revelation, we adopt the standard framework of information design (also known as Bayesian persuasion [35, 10] ) and assume that each player can selectively disclose reward information by implementing an information strategy -often referred to as an experiment or signaling scheme [35, 10] -which stochastically maps the realized reward (unobservable to the searcher) to a random signal (observable to the searcher). For the motivating applications above, such revelation strategies encode answers to standard interview questions (e.g., experiences, behavioral questions) prepared in advance by job candidates, the presentations prepared by startups for the VC, or the property's brochures prepared by property sellers. Each player aims to maximize his probability of being chosen by the searcher, leading to a (constant-sum) competition among them.Our Results. In this work, we stand in the searcher's shoes and look to understand how robust the classic prophet inequalities are to the above strategic player behaviors. Like most previous work in this space, we restrict our attention to threshold stopping policies. We start by characterizing players' optimal information revealing strategies. Given any threshold stopping policy with threshold T , the optimal information strategy of player i with prior reward distribution H i has the following clean threshold structure (albeit using a threshold different from T ): there exists a reward cutoff t i such that player i simply reveals whetherX i ≥ t i or X i < t i . Moreover, t i satisfies E[X i |X i ≥ t i ] = T .In words, player i simply pools all the "good rewards" together to make their expectation barely pass the threshold T . 7 This characterization allows us to reduce players' strategic behaviors to a related prophet inequality problem with binary reward supports. Our later analysis hence only needs to further investigate how well the thresholds for classic prophet inequalities perform in this (related) additional problem. Armed with the above characterization, next we turn to analyze the intrinsic robustness of the classic prophet inequality. We say a threshold stopping policy with threshold T is α(-strategically)robust if it retains the 1 /2-approximation in the classic setting and meanwhile also can achieve αapproximation in the strategic scenario when all the players optimally reveal information. Our first main result is that, for arbitrary reward distributions, the threshold policy with T equaling the half expected max threshold of Kleinberg and Weinberg [36] is 1-1 /e 2 -robust (Theorem 4.1). Moreover, this competitive ratio of 1-1 /e 2 ≈ 0.316 is the best among all known threshold policies that can secure the 1 /2-approximation in the classic non-strategic setting (Proposition 4.2). This suggests that this well-studied threshold policy can also perform robustly well even when players are all strategic, illustrating the intrinsic robustness of the classic prophet inequality.When the reward distributions are identical -referred to as IID distributions which have been extensively studied in literature [41, 18, 6, 30, 1, 33] -we show that there exists a threshold in the range of known thresholds (Definition 2.2) that is 1 /2-robust (Theorem 5.1). Moreover, this 1 /2 approximation ratio is optimal among all possible threshold stopping policies for any IID distributions (Proposition 5.2). Finally, when the reward distributions are not identical but log-concave, under certain regularity conditions we show that any threshold between the expected max and the median of the highest reward [42] is 1 /2-robust (Theorem 5.4). Note that log-concave reward distributions have been considered in previous works on prophet inequality (see, e.g., [6, 18] ); moreover, it is satisfied by a wide range of distributions (e.g., normal, uniform, Gamma, Beta, Laplace, etc., [8] ) and is a widely adopted assumption in algorithmic game theory (see, e.g., [15] ).Additional Related Work. Prophet inequality is a fundamental problem in optimal stopping theory which was introduced in the 70s [38, 37] . Recently there has been a growing interest in prophet inequalities, generalizing the problem to different settings [2, 7, 18, 21, 22, 36, 17, 4, 6, 20] . Our discussion here cannot do justice to its rich literature; hence, we refer interested readers to the recent survey by Lucier [40] , Correa et al. [19] for comprehensive overviews of recent developments and its connections to economic problems. This work takes an informational perspective and associate each distribution in the prophet inequality with a strategic player that strategically signals reward information to the searcher. We follow the information design literature [35, 10] and allow players to design signaling schemes to influence the searcher's beliefs about the realized rewards. In our considered game, players are competing with each other for the selection of the searcher. The players' game thus also shares similarity with competitive information design [26, 28, 5, 23, 34] .Conceptually, our work also relates to the rapidly growing literature on strategic machine learning (see, e.g., [45, 32, 29, 24, 43, 46, 9] ), which studies learning from strategic data providers. We also study similar strategic reward providers, albeit in a different algorithmic problem, i.e., optimal stopping. More generally, our work subscribes to the literature on information design in sequential decision-making. In particular, our paper relates to the recently increased interests on using online learning approaches to study the regret minimization when an information-advantaged player repeatedly interacts with an information-disadvantaged player [11, 14, 25, 44, 47] without knowing their preferences. Instead of focusing on regret minimization, we use the competitive ratio (as conventionally used in prophet inequalities) to measure the searcher's policy. It is worth mentioning that [30] also studies strategic information revealing in prophet inequality problems. In their setting, a centralized player strategically discloses reward information to the searcher, while players in our setting form a decentralized game and each player acts on his own to maximize his payoff.Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? Answer: [Yes] Justification: The abstract and introduction accurately summarize our results. In the main text, we provide all rigorous statements and proofs for these results. Guidelines:• The answer NA means that the abstract and introduction do not include the claims made in the paper. • The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers. • The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings. • It is fine to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper. 
preliminary: 
 In this section, we first revisit the formulation of the classic prophet inequality problem, and then formally introduce our setting as its natural variant where each distribution is associated with a strategic player who will be strategically signaling their reward information.Classic prophet inequality. In standard settings, a searcher faces a finite sequence of known distributions H 1:N ≜ (H i ) i∈[N ] of N non-negative independent random variables. The outcomes (i.e., the rewards) X i ∼ H i 8 for i ∈ [N ] are revealed sequentially to the searcher for i = 1, . . . , N . Let λ i ≜ E Hi [X i ] denote the mean reward for distribution H i . Upon seeing a reward, the searcher decides whether to accept the observed reward and stop the process, or irrevocably move on to the next reward. The searcher's goal is to maximize the expected accepted reward. The searcher's expected payoff cannot be more than that of a prophet who knows in advance the realizations of the rewards, namely, X 1 , . . . , X N . We denote by OPT ≜ E H1,...,H N max i∈[N ] X i the prophet value. Given a stopping policy q, let X (q) be the accepted reward. The stopping policy q is said to be α-approximate (of the prophet value) if the following holds for the searcher's expected payoff for any input distributions H 1:N :E X (q) ≥ α • OPT .The above statement is often referred to as the prophet inequality. For any stopping policy q, the largest constant α ∈ (0, 1] that satisfies the above inequality is named the competitive ratio. Classic results of [38, 37] elegantly show that there exist simple threshold stopping policies that achieve the competitive ratio 1 /2, and moreover the ratio of 1 /2 is tight. 9Definition 2.1 (Threshold Stopping Policy). A threshold stopping policy is an online algorithm which pre-computes a threshold value T as a function of the distributions H 1:N , and then accepts the first reward X i whose value is no smaller than the threshold, i.e., X i ≥ T .It is well-known that multiple thresholds can achieve the optimal 1 /2-approximation ratio. [42] ). Then any threshold stopping policy with threshold T ∈ [T KW , max{T SC , T * }] guarantees 1 /2-approximation to the prophet value. 10Prophet inequality with strategic reward signaling. In the strategic setting, each distribution H i may be associated with a strategic player that governs how much information about the realized reward he would like to reveal to the searcher once the searcher reaches his distribution. Formally, upon arriving at the reward distribution H i , the searcher does not directly observe the realized reward X i ∼ H i . Instead, she observes an information signal, designed by the player i with distribution H i , that is correlated with the reward X i . We follow the literature in information design [35] to model this strategic reward signaling: Each player i chooses a signaling schemeDefinition 2.2 ( 1 /2-approximation Threshold Spectrum). Let T KW ≜ E[maxi Xi] /2 (Kleinberg and Weinberg [36]), let T * satisfy T * = i∈[N ] E[(X i -T * ) + ], and let T SC ≜ sup{t : Pr[max i X i ≥ t] ≥ 1 /2} (Samuel-Cahnϕ i (• | x) ∈ ∆(Σ i ),where Σ i is a measurable signal space and ϕ i (σ | x) ∈ [0, 1] specifies the conditional probability of a signal σ ∈ Σ i that will be sent to the searcher when the rewardX i = x ∼ H i is realized. Notice that, upon seeing a signal σ ∼ ϕ i (• | x), together with the prior information H i from which the reward is realized, the searcher can update her Bayesian belief about the underlying realized value X i , and then decides whether to stop and choose player i, or reject i to continue her search.Each player i is competing with each other for the final selection from the searcher. Namely, a player obtains payoff 1 if his reward is accepted and payoff 0 if his reward is not accepted. 11 Each player's goal is to design an information revealing strategy that maximizes his probability of being chosen by the searcher. We below give two simple examples of information revealing strategies.(1) No information strategy: the signal is completely uninformative (e.g., the distribution sϕ i (• | x) is a Dirac delta function on a single signal, i.e., |Σ i | = 1), hence the searcher infers an expected reward of λ i = E[X i ] as her perceived reward from player i; (2) Full information revealing strategy: the signal perfectly reveals player i's value to the searcher (i.e., ϕ i (σ ≡ x | x) = 1 for every realized X i = x, andΣ i = supp(H i ))In this work, standing in the searcher's shoes, we are interested in how threshold stopping policies perform under players' optimal strategic reward signaling.Game Timeline. The timeline of our prophet inequality with strategic players problem, where the searcher employs a threshold stopping policy, can be detailed as follows: (1) Knowing H 1:N , the searcher first announces a threshold stopping policy with threshold T that is a function of H 1:N ; (2) Knowing threshold T , each player then picks a signaling scheme (also known as an experiment in economics literature [35, 10] ) to reveal partial information about the underlying reward; and (3) The searcher learns all players' information strategies, and then conducts a search based on her threshold stopping policy with threshold T (i.e., accepting the first player whose posterior mean of his reward distribution, given his revealed information signal, exceeds the threshold T ). The assumption that the searcher knows information strategies as well as realized signals is commonly adopted in the information design literature [35, 10] , and is also well motivated for the domains of our interest. For instance, when startups persuade VCs or property sellers persuade buyers, the signaling scheme could correspond to startups' product exhibitions or sellers' promotion brochures which determine what information the searcher could see. Misreporting realized signals corresponds to revealing untrue information, which not only violates regulation policies and but also causes the players to lose credibility in the long term.Slightly abusing the notation, we also use X (q) to denote the accepted reward given the searcher's stopping policy q under the strategic reward signaling, and let u s (q) ≜ E X (q) be the searcher's expected payoff. Notice that here the expectation is not only over the randomness of the distributions H 1:N , but also the information strategies {ϕ i (• | x)}. Anticipating the players' strategic behavior, the searcher wants a stopping policy that can still guarantee a good performance competing against the prophet value OPT.As mentioned earlier, we are particularly interested in how previously studied threshold stopping policies described in Definition 2.2 perform under the players' strategic reward signaling. To formalize our goal, we introduce the following notion of strategic robustness. Definition 2.4 (α(-strategically)-robust Stopping Policies). A stopping policy q is α-robust if it achieves α-approximation to the OPT when players are strategically signaling their rewards, and it remains a 1 /2-approximation in the standard non-strategic setting.Question: Does the paper discuss the limitations of the work performed by the authors? Answer: [Yes] Justification: They are discussed in conclusion section. Guidelines:• The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper. • The authors are encouraged to create a separate "Limitations" section in their paper.• The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be. • The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with a few runs. In general, empirical results often depend on implicit assumptions, which should be articulated. • The authors should reflect on the factors that influence the performance of the approach. For example, a facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon. • The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size. • If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness. • While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations. 
warm-up: characterizing optimal information revealing strategy: 
 We start our analysis by showing that when the searcher adopts a threshold stopping policy (Definition 2.1), each player's optimal information revealing strategy admits clean characterizations. Proposition 3.1 (Optimal Information Revealing Strategy). Given a threshold stopping policy as in Definition 2.1 with threshold T , for each player i:• if T ≤ λ i ,then player i's optimal information revealing strategy is the no information strategy; • if T > λ i , then player i's optimal information revealing strategy is threshold signaling and determined by a cutoff t i that satisfiesT = E[X i |X i ≥ t i ] = ∞ ti x dH i (x)/(1 -H i (t i )).That is, player i's optimal signaling scheme sends one of two signals: X i ≥ t i or X i < t i . 12We highlight the intuition behind Proposition 3.1 below. Under a threshold stopping policy, every player maximizes his utility by maximizing the probability that the signal's posterior expected reward is at least T (hence is selected). When the stopping threshold T ≤ λ i , this probability is 1 and hence maximized when player i simply reveals no information. When T > λ i , this probability is maximized when player i blends the highest rewards together to form a posterior mean just equal to T , which is exactly the scheme described in Proposition 3.1.For ease of presentation, Proposition 3.1 assumes the distribution H i is continuous. When H i has point masses, Proposition 3.1 still holds, but with a more subtle description of the pooling cutoff t i . We provide more detailed discussions in the full version of the paper. Remark 3.2. In game-theoretic terminology, Proposition 3.1 characterizes the subgame Perfect Nash equilibrium (SPNE) for the multi-player sequential game induced by any threshold stopping policy that the searcher commits to. This SPNE happens to enjoy simple structures; indeed, each player's equilibrium strategy is only a function of the threshold T and not on other players' strategies or their order. This clean characterization is a consequence of the simple structure of (static) threshold policies. If the searcher's stopping policy is instead dynamic (i.e., allowing the decision of player i to depend on previously realized rewards), SPNE is also well-defined but will adopt significantly more complex structures. While analyzing the SPNE under these dynamic policies may also be interesting, it is beyond the scope of this work since our focus is to study the power of static threshold policies, which is also a central theme in the study of prophet inequalities. Finally, we note that the optimal strategies characterized in Proposition 3.1 are not unique but they all result in the same utility for every player. This is because player i is actually indifferent on how to disclose the reward when X i ≤ t i , leading to many different but utility-equivalent information strategies.Equivalent Representation of Optimal Information Revealing Strategy. When T > λ i , player i's optimal information revealing strategy described in Proposition 3.1 pools all the rewards X i ∼ H i above t i together to forge a conditional mean value of T , and pools the remaining smaller rewards into another signal. We hence also refer to t i as the pooling cutoff. This threshold signaling scheme can be equivalently represented as a binary-support distribution G i supported on two realizations corresponding to the two signals respectively:EQUATIONIn the literature of information design, this distribution G i is also known as a mean-preserving contraction of prior reward distribution H i [27, 12, 13] .Viewing the player i's optimal information strategy as the distribution G i , one can simplify the interaction between the searcher and player i as the following when the searcher visits player i: a random reward X i ∼ G i is realized, and the searcher stops if and only if X i ≥ T . With this observation, one can also reduce the original interaction to the following simplified protocol: (1) the searcher first decides a stopping threshold T ; (2) each player i chooses the distribution G i as in Equation ( 1) according to his prior H i and the threshold T ;13 and (3) the searcher visits each G i sequentially and stops when the first realized reward X i ≥ T where X i ∼ G i .We emphasize that in the above reduction, given a threshold stopping policy with threshold T , the searcher's expected payoff under the strategic reward signaling can be computed as u s (T ) = E X (q) where the expectation is over distributions G 1:N and X (q) is the first realized X i ∼ G i such that X (q) ≥ T .4 Achieving 1-1 /e 2 -robustness for Arbitrary DistributionsIn this section, we show that for any distributions H 1:N , there exists a 1-1 /e 2 (-strategically)-robust threshold stopping policy using a threshold within the spectrum in Definition 2.2. The main result in this section is stated below. Theorem 4.1. For any distributions H 1:N , a threshold stopping policy with threshold T = T KW is 1-1 /e 2 -robust.t From Definition 2.2, we know that using the threshold stopping policy with threshold T KW can achieve the optimal 1 /2-approximation in the classic prophet inequality for any distributions H 1:N . Theorem 4.1 above shows another desired property of the threshold T KW : it can achieve 1-1 /e 2approximation even when distributions H 1:N are strategically signaling their rewards, thus establishing its 1-1 /e 2 -robustness. Given the optimality of the threshold T KW in the non-strategic setting, it would be intriguing to ask whether this threshold T KW can also achieve 1 /2-approximation under the strategic setting, or if there exists a threshold within the spectrum in Definition 2.2 that can achieve 1 /2-approximation under the strategic setting. Below we show that the answer is No. In fact, any threshold stopping policy using a threshold from the spectrum in Definition 2.2 cannot achieve ( 1-1 /e 2 + ε)-approximation for any ε > 0 under strategic reward signaling. Proposition 4.2 (Tightness of Theorem 4.1). There exist distributions H 1:N such that no threshold from the spectrum in Definition 2.2 can achieve α-robustness where α >1-(1-1/(N -1)) N -1 2 . Notice that lim N →∞ 1-(1-1/(N -1)) N -1 2 = 1-1 /e2 . Thus, the above Proposition 4.2 establishes the tightness of the results in Theorem 4.1. Remark 4.1. We point out a subtlety in the above lower bound, which leads to an intriguing open problem. Proposition 4.2 shows that any threshold within the spectrum in Definition 2.2 cannot achieve ( 1-1 /e 2 + ε)-approximation under strategic reward signaling. However, this does not rule out the possibility of having a threshold outside that spectrum that achieves 1 /2-robustness. This is an interesting open question to resolve, though necessarily challenging since it is even already quite non-trivial to prove 1 /2-approximation in the non-strategic setting for thresholds outside the spectrum of Definition 2.2, let alone achieving 1 /2-approximation simultaneously in both worlds. Theorem 4.1 holds for all distributions, regardless of being discrete or continuous. In the remainder of this subsection, we present the proof of Theorem 4.1 only for the continuous distribution case. The proof of this case carries our core ideas but is cleaner to present.Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof? Answer: [Yes] Guidelines:• The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.• If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics. • The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or regulations in their jurisdiction). 
(partial) proof of theorem 4.1: the case of continuous distributions: 
 Our proof starts by upper bounding the prophet value OPT. 14 Lemma 4.3 (Upper Bounding OPT via Pooling Cutoffs). Given a threshold stopping policy with threshold T , let t i be the pooling cutoff for each player i defined as in Proposition 3.1. Let I ≜ arg max i∈[N ] t i , then we have OPT ≤ H I (tI )t I + i T (1 -H i (t i )).Proof of Lemma 4.3. Let us fix a threshold T , and let t i be the pooling cutoff for player i defined in Proposition 3.1. Define b i ≜ (X i -t i ) + . By definition, for each i, we have X i ≤ t i + b i . Thus,OPT = E H 1:N max i X i ≤ max i t i + i E Hi [b i ] (a) ≤ max i t i + i (T -t i ) • (1 -H i (t i )) (b) ≤ t I H I (t I ) + i T (1 -H i (t i )) ,where inequality (a) follows from the definition of pooling cutoff t i in Proposition 3.1 and inequality (b) follows from the definition of I, t i ≥ 0, and rearranging the terms.With the above upper bound of prophet value, we have the following results:Lemma 4.4. Let T † satisfy N i=1 H i (t † i ) = ( N -1 N ) N where t † i is defined in Proposition 3.1 with threshold T † , then searcher's expected payoff u s (T † ) ≥ T † 1 -i H i (t † i ) ≥ 1-( N -1 N ) N 2•OPT. 15Proof of Lemma 4.4. Given a stopping threshold T , by Proposition 3.1, we can lower bound the searcher's expected payoff as follows:u s (T ) ≥ T • 1 - N i=1 H i (t i ) .Thus, together with 14 All our analysis in the main text implicitly consider the case where maxi λi < OPT /2. If we have maxi λi ≥ OPT /2, then the searcher can simply choose the threshold T = OPT /2 which lies in the range of the thresholds defined in Definition 2.2 to obtain payoff u s (T ) ≥ OPT /2. To see this, by Proposition 3.1, if maxi λi ≥ OPT /2 = T , then there exists at least one player j whose λj ≥ OPT /2 will choose the no information revealing strategy, and the searcher surely obtains a payoff no smaller than OPT /2.u s (T ) OPT ≥ T • 1 - N i=1 H i (t i ) OPT (a) ≥ T • 1 - N i=1 H i (t i ) t I H I (t I ) + i T (1 -H i (t i )) (b) ≥ 1 - N i=1 H i (t i ) H I (t I ) + i (1 -H i (t i )) (c) ≥ 1 - N i=1 H i (t i ) N + 1 -i H i (t i ) (d) ≥ 1 - N i=1 H i (t i ) N + 1 -( N i=1 H i (t i )) 1 N, where inequality (a) is by Lemma 4.3; inequality (b) is by the fact that t i ≤ T for all i ∈ [N ]; inequality (c) is due to H I (t I ) ≤ 1; and inequality (d) is by the AM-GM inequality. Now consider the function f(x) ≜ 1-x N +1-N x 1 N over x ∈ [0, 1]. By choosing x † = ( N -1 N ) N , we have f (x † ) = 1-( N -1 N ) N 2. This implies that we haveT † 1 -i H i (t † i ) ≥ 1-( N -1 N ) N 2 • OPT.With the above Lemma 4.4, we are now ready to prove Theorem 4.1:Proof of Theorem 4.1. From Lemma 4.4, we showedT † 1 - i H i (t † i ) ≥ OPT • 1 -( N -1 N ) N 2 ,where t † i is the pooling cutoff defined in Proposition 3.1 with the threshold T † . By definition of T † , we have i H i (t † i ) = ( N -1 N ) N ≤ 1 /e. Thus we can deduce that T † ≥ OPT /2 = T KW . Now let t ‡ i be the pooling cutoff when the searcher uses the stopping threshold T KW . Then we haveu s (T KW ) ≥ T KW • 1 - i H i (t ‡ i ) (a) ≥ T KW • 1 - i H i (t † i ) ≥ OPT • 1 -1 /e 2where inequality (a) is due to T † ≥ T KW , and thus we havet † i ≥ t ‡ i .5 Achieving 1 2 -robustness for Special DistributionsThe preceding section showed the (1 -1 /e) /2-robustness of the T KW -threshold stopping policy for arbitrary reward distributions. In this section, we show that this ratio can be improved to 1 /2-robustness when the distributions H 1:N satisfy certain conditions: (1) IID distributions -all reward distributions are identical, namely, H ≡ H i for all i ∈ [N ] (see Section 5.1); and (2) Log-concave distributionsreward distribution H i has log-concave density (see Section 5.2). We also show that 1 /2-robustness is tight under IID distributions. 
iid distributions: 
 Our main findings for IID distributions are stated below: Theorem 5.1. For any distributions H 1:N where H ≡ H i , ∀i ∈ [N ], a threshold stopping policy with threshold T = T * is 1 2 -robust where T * is defined in Definition 2.2. For IID distributions, we show that the searcher is able to achieve a better robustness approximation ratio compared to arbitrary distributions. Below we argue that this 1 /2-robustness is tight in the sense that there exists no threshold policy that can achieve better robustness approximation ratios. Proposition 5.2 (Tightness of Theorem 5.1). There exist IID distributions such that there exists no threshold stopping policy that can achieve α-robustness where α > 1 2 + ε for any ε > 0.We note that Proposition 5.2 is a slightly stronger lower bound than Proposition 4.2 as it rules out the possibility for all possible threshold stopping polices, being within the spectrum in Definition 2.2 or beyond. We prove Proposition 5.2 by constructing a hard instance. In particular, we construct IID distributions with binary support. With this instance, we show that any threshold policy that achieves competitive ratio at least 1 /2 in non-strategic setting will have competitive ratio approaching to 0 in the strategic setting. Please see A crucial requirement in our robustness study so far is that we insist that the threshold policy should, first of all, remains an 1 /2-approximation in the non-strategic setting 16 , conditioned on which we look for additional guarantee for in the strategic setting. We conclude this section by pointing that if one was willing to give up the 1 /2-approximation in the non-strategic setting, then it is indeed possible to have a threshold policy that achieves better approximation (specifically, an (1 -1 /e)-approximation) in the strategic setting. While this does not satisfy our robustness requirement, it is useful to note. Corollary 5.3. For any IID distributions, there exists a threshold stopping policy that is (1 -1 /e)approximation under strategic reward signaling. Moreover, there exist IID distributions such that no threshold stopping policy can achieve (1 -1 /e + ε)-approximation for any ε > 0.In this subsection, we show that when the distributions H 1:N satisfy certain regularity assumptions, there exist threshold stopping policies with thresholds from Definition 2.2 that can also achieve 1 /2-robustness. The main result in this section is stated as follows: Theorem 5.4. For α, β > 0, let F α,β be the family of distributions with log-concave probability density functionsf on support [0, 1] such that f (1) ≥ α and f ′ (1) ≥ -β. If the distributions H 1 , . . . , H N are all from F α,β and N ≥ 1 + β α 2 , then we always have 2 • T KW ≤ T SC and any threshold T satisfying 2 • T KW ≤ T ≤ T SC is 1 /2-robust.A few remarks on the assumptions in Theorem 5.4 are worth mentioning. First, log-concavity of probability density functions 17 is a commonly used assumption; they include but are not limited to: normal, beta, gamma, and exponential distributions. The restriction to support on [0, 1] is for normalization reasons, hence without loss of generality. The main non-trivial restriction is that this result holds when the number of players N is large enough, formally N ≥ 1 + β α 2 . This condition becomes less restrictive when α (lower bounding f (1)) becomes larger and/or β (upper bounding -f ′ (1)) becomes smaller. These together, intuitively, imply that f decreases slowly within [0, 1].N i=1 H i (x). Theorem 5.4 follows directly from the following Lemma 5.5 and Lemma 5.6. Lemma 5.5. If H is convex, then 2•T KW ≤ T SC and any threshold stopping policy with the threshold T satisfying 2 • T KW ≤ T ≤ T SC , where T KW , T SC are defined as in Definition 2.1, is 1 /2-robust. Lemma 5.6. If the distributions H 1 , . . . , H N are all from F α,β and N ≥ 1 + β α 2 , then H is convex. 
conclusion and future directions: 
 In this paper, we study a variant of the prophet inequality problem where each random variable is associated with a strategic player who can strategically signal their reward to the searcher. We first fully characterize the optimal information strategy of each player, then we show the threshold stopping policies that can perform robustly well under both the strategic and non-strategic settings.Our novel consideration of natural strategic manipulations in prophet inequalities open the door for many interesting future directions. First, it is interesting to see if we can improve the 1-1 /e 2robustness guarantee for arbitrary reward distributions by using not commonly used thresholds outside the spectrum of Definition 2.2. This may be technically challenging since finding a threshold outside this spectrum with optimal 1 /2-approximation for the classic non-strategic prophet inequality is already non-trivial. Another interesting direction is to go beyond threshold policies. That leads to a different research theme, not about robustness of the classic prophet inequality, but rather in the search of potentially much more complex best-of-both-world policies. Our preliminary result reveals that a dynamic threshold stopping policy (using different thresholds for different players) has the potential to help the searcher to achieve more than 1-1 /e 2 -approximation under the strategic setting. However, it is still unclear whether 1 /2-robustness is achievable under threshold stopping policies, no matter whether it is static threshold or dynamic threshold. Finally, even if one only cares about the performance under the strategic reward signaling (and ignore the non-strategic world), it is still unclear which static threshold stopping policy achieves the highest competitive ratio. The authors in [20] study a model with a very similar mathematical structure and proved that this best upper bound is strictly less than 1 /2 in Section 4.1, but an interesting direction is improving this bound further. We note that all our constructed examples in the hardness results (e.g., Proposition 4.2 and Proposition 5.2) do not rule out the existence of such 1 /2-approximation threshold stopping policies. 
broader impacts: 
 Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?Answer: [NA] Justification: The paper studies a theoretical problem, to the best of our knowledge, there is no societal impact of the work that we need to address.Guidelines:• The answer NA means that there is no societal impact of the work performed.• If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact. • Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.• The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster. • The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology. • If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?Answer: [NA] Justification: Not applicable to our paper.Guidelines:• The answer NA means that the paper poses no such risks.• Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters. • Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images. • We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make a best faith effort.12. Licenses for existing assets Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?Answer: [NA] Justification: No assets used.Guidelines:• The answer NA means that the paper does not use existing assets.• The authors should cite the original paper that produced the code package or dataset.• The authors should state which version of the asset is used and, if possible, include a URL. • The name of the license (e.g., CC-BY 4.0) should be included for each asset.• For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided. • If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a dataset. • For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided. 
 
 Appendix: We refer to the one that controls the reward information as the "player", and refer to the one that decides when to stop as the "searcher".More formally, these response strategies form a subgame perfect Nash equilibrium among the sequentialmove game of players (which turns out to be unique as far as players' utilities are concerned) (see Remark 3.2).Here Hi denotes the cumulative distribution function (CDF) of the reward XiSee[40,19] for the hardness example for the 1 /2-approximation.There also exists other thresholds that could lead to 1 /2-approximation, e.g., any T ∈ [min{T SC , T KW }, T KW ) where T SC ≜ inf{t : Pr[maxi Xi ≥ t] ≥ 1 /2}. However, using these thresholds requires to modify the policy defined in Definition 2.1 to be a strict stopping policy to obtain 1 /2-approximation (i.e., searcher accepts a first reward that is strictly larger than threshold). Moreover, under strict stopping policy, there may exist no Nash equilibrium among players' game that we formulate shortly.All of our results hold if each player i has payoff vi if his reward is accepted and payoff ui if his reward is not accepted as long as vi > ui.In the corner case when T is larger than the upper bound of player i's distribution, player i will never get chosen and thus they have no strategyWhen T ≤ λi, distribution Gi is a point mass at mean value λi.Note that for non-continuous distributions T † always exists but is defined a bit differently, please see the full version of the paper for more details.Note that in non-strategic setting, unlike the case for arbitrary distributions where there exists no policy that can achieve better than 1 /2-approximation, for IID distributions, (1 -1 /e)-approximation can be achieved by fixed threshold together with some careful probabilistic tie-breaking rule[3] (or 0.7451-approximation with an adaptive threshold policy[39]). However, in our work, we focus on fixed threshold policy with deterministic tie-breaking rule where 1 /2-approximation is still optimal for IID distributions.A probability density function f : R → R + is log-concave if log(f ) is concave. 


Decision: The paper investigates the robustness of the so-called Prophet inequality to strategic reward signaling. This inequality concerns simple threshold policies (the decision maker accepts the reward if it exceeds a threshold). Now the authors consider a scenario where the successive rewards are revealed by selfish agents willing to maximize the probability that their reward is selected. They show that if the decision maker applies a threshold-based policy applied to the posterior mean rewards given the signals sent by the players, then the optimal strategy of the players are simple binary policies.  
Based on this result, the authors first establish that the KW threshold achieves a $(1-1/e)/2$ approximation of the OPT under strategic players (Theorem 4.1). The result is extended to the particular case of IID rewards and log-concave distributions (with a ½ approximation ratio).    

Based on the reviews, the discussions during the rebuttal phase, and my own evaluation, we encourage the authors to modify their manuscript to account for the following points.

1. Clarity of the model. The game-theoretical model is described at the end of Section 2, and as pointed out by two reviewers, it needs to be really clarified.
(i) The decision maker. She knows the distributions $H_i$ and selects a threshold accordingly. The threshold will be comapred against the posterior means of the rewards given the signals sent by the players. 
(ii) The players. They know the threshold and know how it will be used by the decision maker.  
The objective is for players to design optimal signaling strategies, and to characterize the competitive ratio of the corresponding Nash Equilibrium (in terms of the selected reward). Currently the way the problem is presented is confusing.

2. Technical precision and proofs. Some of the reviewers (e.g. mXL5) asks for more clarity in the proofs. Also please state results rigorously in the main text (Prop. 3.1 is confusing because you do not specify the optimal strategy in the case where the threshold is greater than the upper bound of the reward distribution support – this is done properly in Appendix).

3. Adding discussions. Please include the discussions that you had with the reviewers. I would specifically recommend discussing the limitations of the model. One limitation pertains to the fact that the searcher is assumed to apply a threshold policy based on the posterior means of the rewards given the signals sent by the players. This implies that the players send both the signal $\sigma_i$ sampled from $\phi_i(.|X_i)$ ‘and’ $\phi_i$. The theory works because we assume that the players are truthful in the sense that they report the sample $\sigma_i$ actually sampled from $\phi_i(.|X_i)$. Could the authors discuss what societal mechanisms would encourage or enforce truthfulness, so that this is a reasonable, albeit idealized, assumption?

Reviews: review: paper_summary: paper_summary: This paper considers a bayesian persuasion variant of the classical prophet inequality problem: an online decision-maker will face a sequence of independent positive random variables $(X_1,\dots,X_n)$, $X_i \sim F_i$ known, and must decide when to stop in order to maximize the expectation of the selected item. Contrarily to the original problem,  each individual $i$ is strategic and chooses a signaling schemes aiming to maximize its chance of being selected (such as $\mathbb{1}_{X_i \geq t}$): the decision maker will only observe the signal from individual $i$, and not necessarily the $X_i$ directly. The process is in $3$ steps, the decision maker selects a stopping threshold $T$, the individuals select their signaling schemes, and finally the sequence of signals is observed. They first show that the usual rule of $\mathbb{E}[\max_i X_i]/2$ which without strategic agents achieves a $1/2$ competitive ratio, achieves a $(1-1/e)/2$ competitive ratio with strategic agents. In addition this is tight over a range of thresholds. Additional settings when the distributions are i.i.d. or are log-concave are considered.
strength_weakness: strength_weakness: 1) It remains unknown whether $(1-1/e)/2$ is the best competitive ratio achievable in the strategic setting.
2) Some of the additional assumptions made when considering log-concave distributions are strong and too specific.
questions: questions: Questions and remarks :
1) In the i.i.d. setting, the negative results do not seem to preclude the existence of a threshold with a $1-1/e$ CR in the non-strategic setting and a $1/2$ CR in the strategic setting. Is it possible to achieve? For instance, what is the performance of the quantile rule $T=F^{-1}(1-1/n)$ which achieves $1-1/e$ in the non-strategic iid setting?
2) Related to Corollary 5.3, do the authors know if better results are achievable in the non-iid strategic setting if we give up the performance in the non-strategic setting ? 
3) Do the authors have any insights about the prophet secretary case? 
4) I think it would be useful to give more details with respect to [29] as it seems to directly pertain to the topic at hand, and this could provide some insights in terms of what is gained in a centralized vs decentralized setting.
5) Regarding the payoffs obtained by the individuals when their item is selected, have other types of payoff structures been considered? For instance, player $i$ receives reward $X_i$ if item $i$ is selected, and $0$ otherwise. How does it affect the strategizing? 
6) A brief comment on the existence of $T^{\dagger}$ and $T^*$ that satisfy their relevant equations should be added.
7) Are there examples of log-concave distributions which does not respect the additional slow decrease condition and which achieves a CR smaller than $1/2$ with the suggested range of thresholds? More broadly, are the additional assumptions (other than log-concave) truly necessary? 

line 145: the \nicefrac{} command for $\mathbb{E}[\max_i X_i]/2$ makes it too small.
limitations: limitations: Some limitations regarding strong assumptions and tightness of results have been accordingly addressed in the paper.
paper_summary: paper_summary: The paper studies a variant of the prophet inequality modeled as a game between the reward holders (Players $1, \ldots, n$) and the searcher. In this model, each reward $X_i$ is sampled from a distribution $H_i$ that is known to the searcher. However, each player $i$ can choose not to reveal $X_i$, and instead only reveal a signal $\Phi(X_i)$ that provides partial information about $X_i$. The objective of each player $i$ is to maximize the probability of being selected by the searcher. On the other hand, the searcher's goal is to maximize the expected value that it selects, while maintaining a competitive ratio of $1/2$ in the case where all players fully reveal their prices, i.e. in the standard prophet inequality. The authors first characterize the optimal information-revealing strategy for the players, then present an algorithm that achieves a competitive ratio of $(1-1/e)/2$ in this strategic setting and $1/2$ in the standard setting. They also prove that this competitive ratio is the best possible. Finally, they give improved competitive ratios in the strategic setting with IID and with Log-concave Heterogeneous Distributions, also maintaining a competitive ratio of $1/2$ in the standard prophet inequality.
strength_weakness: strength_weakness: * The optimal revealing strategy is only characterized when the searcher follows a threshold policy
* The proposed algorithm is only optimal among threshold policies with thresholds in the spectrum given in Definition 2.2, and not among all possible algorithms.
* The paper requires the algorithms to maintain a competitive ratio of $1/2$ if all the players reveal their reward values. While this is a perfectly reasonable assumption in the general setting, it makes much less sense in the case of IID rewards. The optimal competitive ratio in the prophet inequality with IID random variables is $0.745...$. Even if we restrict ourselves to threshold policies, the optimal competitive ratio is $1-1/e$. The reasonable constraint in the IID case would then be that the algorithm maintains a competitive ratio of $1-1/e$ if all the players reveal their rewards.
* The problem assumes that the searcher does not observe the values $(X_i)_i$ but only signals $(\Phi(X_i))_i$. The threshold policy should then be defined as selecting the first reward $X_i$ such that $(\Phi(X_i) \geq T)$ and not $(X_i \geq T)$.

Minor weaknesses:
* Line 138: be more precise in the definition of the competitive ratio: it is the largest constant $\alpha$ satisfying $E[X^{(q)}] \geq \alpha \text{OPT}$
* Maybe Definition 2.2 should be a Lemma or Proposition instead
* Remark 3.1 should mention that Proposition A.1 also addresses the case where $X_i < T$ almost surely, not only the case of distributions with point masses, otherwise $t_i$ does not look well-defined.
questions: questions: * See weaknesses
* The game timeline (line 170) is confusing to me: the searcher selects a threshold without knowing the types of signals they will observe, and then the players select revealing schemes. How does the searcher choose its stopping strategy without even knowing the type of information they will observe, which can be for example binary ($\Phi(X_i) = (X_i > a)$), negative $\Phi(X_i) = -X_i$, constant $\Phi(X_i) = 1)$, or others ?
limitations: limitations: The assumptions for all the are clearly stated for all the claims made in the paper.
paper_summary: paper_summary: The paper studies a variant of the classical prophet inequalities problem, where "boxes" are now strategic agents who can pool their realized value into bins and only reveal to the decision maker which bin it falls into.  The expected value in that bin then plays the role of the realized value.  The authors study best-of-both-worlds threshold policies, which (1) achieve the tight 1/2 approximation ratio in the non-strategic setting, and (2) achieves a ratio of alpha in the strategic model.  The main results are (conditional) optimal policies in the general setting, the IID setting, and the log-concave priors setting.
strength_weakness: strength_weakness: Parts of the model can be better justified (see detailed comments).  I'd also appreciate the results better if there were unconditional / tighter impossibility results.
questions: questions: (also including detailed comments)

Line 70, threshold policies: is this without loss of generality?

Timeline paragraph: I feel this is a bit ambiguous.  In particular, since the searcher has first-order commitment power, essentially the model assumes the searcher only commits to policies that put a threshold on the posterior expected value (otherwise the searcher would do something like "if you don't reveal the full information, you are out" and we are back in the classical model).  I feel this part of the model could be better motivated.

Characterization of players' response: this is reminiscent of the response of value maximizing players in [19], which has a very similar structure.  I wonder if a formal connection can be made between the two models.

Remark 4.1: there is an upper bound (i.e., impossibility result) strictly smaller than 0.5 in [19], which might imply the impossibility of 1/2-robustness in your model, given the intuitive connection between the two models.  This would make your results a bit more complete.

Around line 368, dynamic threshold: I think you can get 1/2-approximation in the strategic setting?  Take any 1/2-approximation policy in the non-strategic setting.  Construct a new policy such that each player's response cutoff under the new policy is the same as the threshold of the old policy.  Then you can couple the two policies in the two worlds and argue they have exactly the same performance?
limitations: limitations: No concerns.
paper_summary: paper_summary: This paper studies the robustness of threshold algorithms when involving strategic manipulations in the classic prophet inequality problem. Specifically, the paper considers the scenario when each random reward of $N$ variables is associated with a strategic player, who can commit to a signaling scheme before the search, and the searcher can only see the signal rather than the actual reward during the whole search. Each player wants to maximize the probability of being chosen by the searcher and, thus, would optimally choose the signaling scheme against the searcher's thresholding algorithm. The authors first characterize any player's optimal scheme, which has a quite simple form. Based on the result, the authors show that threshold $T_\mathsf{KW}$ is a $(1 - 1/e)/2$-approximation in this setting and is tight. For i.i.d. distributions, $T^*$ gives a $1/2$-approximation, and is tight. For log-concave distributions, a spectrum of thresholds also gives a $1/2$-approximation.
strength_weakness: strength_weakness: This paper leaves some major problems unanswered. For example, can the authors provide some preliminary thoughts if we only require a $\beta < 1/2$ approximation in the original world and search for the Pareto frontier of $(\alpha, \beta)$? That being said, I think the authors have already provided enough.
questions: questions: Please see the weaknesses above.
limitations: limitations: The authors have addressed the limitations of their work.

Comments: title: Response to Reviewer's Comments
Response to Reviewer's Comments (Continued)
Response to Reviewer's Comments
comment: We greatly thank the reviewer for the feedback and encouraging words. Indeed, the comments/suggestions made by the reviewer (and also other reviewers) would be helpful to improve our paper and deepen our results. We will make sure to include these suggestions/comments in our revision.
I thank the authors for replying to my comments and have no further questions. I think after taking into account the suggestions/comments made by the reviewers and authors this will be a nice paper.

Best,
Thank you for your helpful response.  I don't have further questions.
We greatly thank the reviewer for the feedback! We will make sure to make our results for the IID case more complete, and state the limitations of our work more explicitly in the revision.
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 valuable comments/suggestions and hope that our response has effectively addressed your main questions/comments. If there are any lingering questions, we would be more than happy to address them.
We sincerely thank the reviewer again for engaging in our discussions and hope that our response has effectively addressed your further questions. If there are any lingering questions, we would be more than happy to address them.
We sincerely thank the reviewer again for engaging in our discussions and hope that our response has effectively addressed your further questions. If there are any lingering questions, we would be more than happy to address them.
We sincerely thank the reviewer for engaging in our discussions, and thanks for the insightful comments. We believe the following responses should help to address most of the reviewer’s concerns raised in Item 2 and 3 of the follow-up.

**Benchmarking within the threshold stopping policies**:
We agree with the reviewer that understanding optimality of our threshold policy compared to best **dynamic policy** is a very interesting future direction. Our current paper did not study this question. However, when compared with optimal **static threshold** (not necessarily within the $1/2$-approximation threshold spectrum as in Definition 2.2), our $1/2$-robustness in Theorem 5.1 for IID case is indeed optimal. This is shown by our Proposition 5.2. (please also refer to its refined proof in our additional response to the Reviewer **mXL5**). It constructs examples to show that, even in IID case, **any** static threshold (not necessarily within Def 2.2’s spectrum) achieving at least $1/2$-competitive ratio for non-strategic setting cannot be $(1/2+\epsilon)$-robust for any $\epsilon > 0$.  


**1-1/e competitive ratio for i.i.d. case**: 

1. The referred paper requires distributions to have NO point mass (see page 5, the third line after the **Query** paragraph, for the assumption statement; essentially they need the threshold T such that $\text{CDF}(T) = 1-1/n$ to exist). In our setting, we strived to make least assumptions on the reward distributions to understand its robustness against the strategic reward signaling, thus we do not make any assumptions on the reward distributions and allow them to have point masses.  
2. Take a step back, even for the IID continuous distributions, it is not difficult to identify examples to show that the above threshold T with $\text{CDF}(T) = 1-1/n$ — which to the best of our knowledge is the only known threshold to achieve the $(1-1/e)$ competitive ratio for non-strategic setting  —  can become arbitrarily bad in strategic setting (i.e., cannot guarantee $\epsilon$-robustness for any $\epsilon > 0$). Reviewer **mXL5** happened to also ask this question, hence please refer to our last response to Reviewer **mXL5** for a construction of such an example.
3. It is an interesting question to study whether there are other thresholds, other than the  $T = F^{-1}(1-1/N)$ (here F denotes the CDF) as in the referred paper, that guarantees $(1-1/e)$-CR in both non-strategic and strategic settings. However, this question is beyond the scope of this paper since it is not even known whether there is another threshold other than $T = F^{-1}(1-1/N)$ that can have  $(1-1/e)$-CR even just for the non-strategic setting.
**(Refined) Complete Proof of Proposition 5.2**:

Consider an instance with $N$ iid distributions on binary support $\{N-\alpha_1, N + \alpha_2\}$ for $ \alpha_1 \in (0, 1), \alpha_2 > 0$ such that the probabilities are chosen to make the mean of each distribution precisely $N$ -- i.e., the probability of taking the smaller value is $\frac{\alpha_2}{\alpha_1 + \alpha_2}$. For the purpose of this proof, one should think of $N, \alpha_2$ as being very large. The prophet value $\text{OPT}$ can be calculated as following:  
$$\text{OPT} = (N +  \alpha_2) \cdot  [1 - (\frac{\alpha_2}{\alpha_2+\alpha_1})^N]  + (N - \alpha_1) \cdot (\frac{ \alpha_2}{\alpha_2 + \alpha_1})^N.$$ 

We first claim that, for *any* $\alpha_1 \in(0, 1)$, no threshold $T \in (N - \alpha_1,  N + \alpha_2]$ can guarantee at least $1/2$ competitive ratio for non-strategic settings. Intuitively, this is because any such threshold will give up any realization of $N- \alpha_1$ value, which leads to bad performance when the probability of having at least one realization of $ N + \alpha_2$ is small (i.e., when $\alpha_2$ is very large). Detailed calculation is as below: any threshold $T \in (N - \alpha_1 , N + \alpha_2] $ only accepts the realized $N + \alpha_2$ value, hence the expected payoff for non-strategic (ns) setting is (i.e., the first term of $\text{OPT}$) $$u^{ns}(T) = (N + \alpha_2)  \cdot [ 1 - (\frac{\alpha_2 }{\alpha_2 + \alpha_1 })^N].$$

Therefore,
\begin{eqnarray*}
    \frac{u^{ns}(T)}{\text{OPT}}  &=&  \frac{ (N + \alpha_2)  \cdot [ 1 - (\frac{\alpha_2 }{\alpha_2 + \alpha_1 })^N]  }{ (N + \alpha_2)  \cdot [ 1 - (\frac{\alpha_2 }{\alpha_2 + \alpha_1 })^N]  + (N - \alpha_1) \cdot (\frac{ \alpha_2}{\alpha_2 + \alpha_1})^N  }  \\ 
    &=&  \frac{  1  }{ 1   + \frac{N - \alpha_1}{N + \alpha_2} \cdot \frac{(\frac{ \alpha_2}{\alpha_2 + \alpha_1})^N}{   1 - (\frac{\alpha_2 }{\alpha_2 + \alpha_1 })^N   }  }  
    \end{eqnarray*} 
We now analyze the limit of the key term $    \frac{N - \alpha_1}{N + \alpha_2} \cdot \frac{(  \frac{ \alpha_2}{\alpha_2 + \alpha_1})^N}{   1 - (\frac{\alpha_2 }{\alpha_2 + \alpha_1 })^N   }   $. To ease the analysis, we re-parameterize the above term with $\alpha_2 = \frac{\alpha_1 N }{ \alpha}$ with free parameter $\alpha$ to obtain 
\begin{eqnarray*}
  \frac{N - \alpha_1}{N + \alpha_2} \cdot \frac{( \frac{ \alpha_2}{\alpha_2 + \alpha_1})^N}{   1 - (\frac{\alpha_2 }{\alpha_2 + \alpha_1 })^N   }     =     \frac{N - \alpha_1}{N} \frac{1}{1 + \alpha_1/\alpha}  \cdot \frac{(  \frac{ N }{N + \alpha})^N}{   1 - (\frac{ N }{N + \alpha })^N   }  = A(N, \alpha; \alpha_1) 
\end{eqnarray*} 
Since $\alpha_1 \in (0, 1)$ is fixed. Now fix $\alpha$ and let $N \to \infty$, we have $\lim_{N \to \infty} A(N, \alpha; \alpha_1) =    \frac{1}{1 + \alpha_1/\alpha} \cdot \frac{e^{-\alpha} }{   1 - e^{-\alpha} }$. Now, letting $\alpha \to 0$ and applying standard l'hopital's rule, we have  $\lim_{ \alpha \to 0 }   \frac{1}{1 + \alpha_1/\alpha} \cdot \frac{e^{-\alpha} }{   1 - e^{-\alpha}  }  =  \lim_{ \alpha \to 0 }   \frac{\alpha e^{-\alpha} }{(\alpha + \alpha_1)(1 - e^{-\alpha} ) }  = 1/\alpha_1$. As a consequence, we have $\lim_{N \to \infty, \alpha_2 \to \infty}   \frac{u^{ns}(T)}{\text{OPT}} = \frac{\alpha_1}{\alpha_1  + 1}$. Thus, for any $\alpha_1 \in (0, 1)$, there exists an IID instance with large enough $N$ and $ \alpha_2 $ such that no threshold $T \in (N-\alpha_1, N +  \alpha_2]$ can achieve CR at least $1/2$.  

The above analysis shows that the only threshold $T$ that can guarantee a CR at least $1/2$ in the above class of instances must satisfy $T \le N-\alpha_1$. 
Any such threshold will achieve searcher's utility $u^s(T) = N$ in the strategic setting since all players will reveal no reward information, leading to expected reward value $N$ for each player. 
A similar limit analysis using the same reparameterization $\alpha_2 = \frac{\alpha_1 N }{ \alpha}$ shows that  $ \lim_{\alpha \to 0 }\lim_{N  \to \infty}  \frac{u^{s}(T)}{\text{OPT}} = \frac{1}{1+\alpha_1}$.

The arguments above shows that for any $\alpha_1 < 1$, as $N, \alpha_2 \to \infty$ in the above instances,  any threshold that has CR at least $1/2$ in non-strategic setting will have CR tending to $ \frac{1}{1+\alpha_1}$ in the strategic setting. Since this conclusion holds for any $\alpha_1 \in (0, 1)$, it rules out the possibility of  having an $(1/2+\alpha)$-robust threshold (even outside the $1/2$-approximation threshold spectrum as in Definition 2.2) for any  $\alpha > 0$.
We appreciate the reviewer’s engagement and very interesting questions, which also help us to further deepen our results. Our response below is a bit long, but it should resolve the reviewer’s three major questions we believe. In a nutshell, 
1. We identify an example to show that, even for continuous distributions, the known threshold to achieve the (1-1/e) competitive ratio (CR) in IID case for non-strategic setting can become arbitrarily bad in strategic setting (i.e., cannot guarantee $\epsilon$-robustness for any $\epsilon > 0$). While this is a very interesting question, it is unclear whether one could obtain interesting $\alpha$-robustness results for IID setting, subject to $(1-1/e)$-CR in non-strategic situations. Answering this question will also require significant advances over the state-of-the-art results for standard (non-strategic)  prophet inequality for IID cases, as the currently known threshold would not work.
2. We thank the reviewer for pointing out the incompleteness of current proof of Proposition 5.2 to our attention. We acknowledge that the current proof of Proposition 5.2 indeed does not fully prove the statement, though it has the right intuition and ideas (and the statement of Prop 5.2 is also correct). A slight modification of the constructed example by changing $N-1$ in the construction to $N-\alpha_1$ and then letting $\alpha_1 \to 1$ suffices to prove the proposition. We also include a complete argument below in case the reviewer would like to take a look.
3. Lastly, we'd also like to note that tiebreaks do not affect our proofs. In particular, allowing tiebreaks does not help to get a better CR in a strategic setting. This is followed by a simple observation of the structure of the players’ optimal information strategies (see Proposition 3.1), where each player’s optimal information strategy is a two-point-mass distribution with larger mass being the same $T$. Thus, the searcher would never be better off by randomly rejecting any player if he is realizing a mass $T$ since that is the maximum possible value sent by all the players. 

Needless to say, we will incorporate all the above discussions in the next draft and also follow the reviewer’s suggestion and add our discussions about $Q_7$. 


**The threshold with $1-1/e$ competitive ratio in IID case is NOT $\epsilon$-robust for any constant $\epsilon>0$**: 
Under **continuous** iid distributions, one can always achieve $1-1/e$ competitive ratio (CR) in the non-strategic setting using the threshold $T$ such that $T = F^{-1}(1-1/N)$, where $F$ is the CDF. An interesting question is whether this $T$ is $(1-1/e)$-robust in the sense that it also achieves $1-1/e$ CR in the strategic setting. Unfortunately, the answer to this question is no --- in fact, this threshold $T$ cannot guarantee $\alpha$-robustness for any positive $\alpha$. 

We provide an intuitive counterexample below, but happy to convert it to a rigorous construction (which should require no new ideas but just tedious math constructions) if the reviewer is interested to see. Notably, it is an interesting question to study whether there are other thresholds, other than the threshold $T = F^{-1}(1-1/N)$, that guarantees $(1-1/e)$-CR in both non-strategic and strategic settings. However, this question is far beyond the scope of this paper  since, to our knowledge, it is even not known whether there is another threshold other than $T = F^{-1}(1-1/N)$ that can have  $(1-1/e)$-CR even just for the non-strategic setting.  

The counterexample considers $N$ players with continuous iid distributions that almost have a binary support in $\{0,1\}$, with probability $ \frac{1}{2N}$ to be $1$ hence mean $1/(2N)$ (rigorous construction only needs to ``smooth'' this discrete distribution to be a continuous one that mostly concentrates its mass on $0, 1$).  These continuous distributions can be made to satisfy $F^{-1}(1-1/N) < \frac{1}{2N}$ (i.e., the threshold is very close to $0$ but just a little bit larger).  

Note under these distributions, the first player can use the no-information strategy and reveal $\delta(\frac{1}{2N})$ and will always be picked by the searcher. Hence the searcher’s payoff is $u^s(T) = \frac{1}{2N}$. Since we can approximate continuous distributions close to the binary support one, for any $\epsilon > 0$ we can always find a continuous distribution such that its $\text{OPT} = (1 - (1-\frac{1}{2N})^N) - \epsilon$, as $(1 - (1-\frac{1}{2N})^N)$ is the $\text{OPT}$ of the binary support one. Then the searcher’s CR is $\frac{u^S(T)}{\text{OPT}} = \frac{1}{N \cdot (1 - (1-\frac{1}{2N})^N - \epsilon)}$, which goes to $0$ as $N \to \infty$. Hence the searcher’s CR in the strategic setting can get very close to $0$, showing that $T = F^{-1}(1-1/N)$ is not robust to strategic reward signaling.
We thank the authors for their responses and clarifications. I still have a few questions left, 

Q1. I agree that when the distributions are discrete a tie-break is required to achieve $1-1/e$. However much of the paper’s main section presentation assumes continuous distributions, in which case the $1-1/e$ competitive ratio is achieved. I would expect that under continuous distributions the natural definition for i.i.d. $\alpha$-robustness would be to guarantee the non-strategic competitive ratio of $1-1/e$. Even without the continuous assumption, does allowing for random tie-breaks make any of the proofs catastrophically fail? If this is the case this should be pointed out, as allowing for tie-break is quite standard in the literature, in which case looking at thresholds without tie breaks might not be the right policy set to consider. 

I am also now confused about the current proof of Proposition 5.2 in the paper. Is it correct that what the counter example proves, is that any fixed threshold (without tie breaking) in the non strategic setting will bet at most $½$? Maybe I misunderstood something, but this does not prove that for any $\alpha$-robust policy, $\alpha \leq ½ $, as we could still have $½$ in the non strategic setting and more than $½$ in the strategic one. 
However your new counter example does show that if $½$ is achieved in the non strategic setting, then the competitive ratio is at most $5 / 8.2$ in the strategic setting, but this is still not $½$. Please feel free to correct me. 

Regarding $Q7$, I think this limitation should therefore be included next to the result for transparency.
I appreciate your response!
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.