Intrinsic Robustness of Prophet Inequality to Strategic Reward Signaling
Authors: Wei Tang
Haifeng Xu
Ruimin Zhang
Derek Zhu
Venue: NeurIPS 2024 poster (2024)
Keywords: prophet inequality
optimal stopping
robustness
strategic information revealing
Primary area: algorithmic_game_theory

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.

Intrinsic Robustness of Prophet Inequality to Strategic Reward Signaling
Wei Tang"
Haifeng Xut
Ruimin Zhang
Derek Zhu
Abstract
Prophet inequality concerns basic optimal stopping problem and states that sim- ple threshold stopping policies - i.e., accepting the first reward larger than cer- threshold can achieve tight 1/--approximatio the optimal prophet value. Motivated by its economic applications, this paper studies the robustness of this approximation to natural strategic manipulations which each random reward is associated with self-interested player who may selectively reveal his realized reward to the searcher order to maximize his probability of being selected.
We say a threshold policy is atstttategicallly if it (a) achieves the a- approximation to the prophet value for strategic players; and (b) meanwhile re- mains a 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 sig- naling through the following results: (1) for arbitrary reward distributions, there is a threshold policy that is 1-t/- -robust, and this ratio tight; (2) for i.i.d. re- ward distributions, there is threshold policy that is 1/2-robust, which is tight for the setting; and (3) for log-concave (but non-identical) reward distributions, the 1/2-robustness can also be achieved under certain regularity assumptions."
Introduction
The prophet inequality of Krengel and Sucheston [37] is foundational framework for the theory of optimal stopping problems and sequential decision-making. the classic prophet inequality, a searcher faces a fimite sequence of non-negative, real-valued and independent random variables XI....,Xx with known distributions H; from which a reward of value X, drawn sequentially for = I....,N. Once a random reward is realized, the searcher decides whether to accept the real- ized 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 's stop- ping policy evaluated against prophet value which equals the ex-post maximum realized reward. The classic and elegant result of Samuel-Cahn [42] showed that simple static threshold policy achieves least half of the prophet value, and surprisingly, this bound the best possible even among dynamic policies. Samuel-Cahn 's policy uses the threshold that is the median of the dis- tribution of the highest prizes, and then accepts the first realized reward that exceeds this threshold. The existence of this 1/-aaproxiimation is now known the prophet inequality.
Recently, there regained interest of the prophet inequality due its beautiful connection to online mechanism design (see, e.g., [31, 16)), and many different settings of the prophet inequality
Chinese University of Hong Kong. Email: wei tangggunu.h.... edu hks
1 University of Chicago. Email: saifengzu@uchicago edu.
University of Chicago. Email: ruimin@uchicago. edu.
University Chicago. Email: tahu@@uchicago.cc edu. edu.
'The full version of this paper can be found at
18269
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

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/-aaproximmaion. Indeed, it is now well-known that there exists a range of thresholds for the classic prophet inequality that can achieve the optimal 1/>-aprroximation (see Definition 2.2).
An important assumption in the classic prophet incquality 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" 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 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 de- cide 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 infor- mation 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 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 's brochures prepared by property sellers. Each player aims maximize his probability of being chosen by the searcher, leading to (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, has the following clean threshold structure (albeit using a threshold different from T): there exists a reward cutoff t, such that player simply reveals whether X; 2 t. or X, < t4. Moreover, t, satisfies E[X,|X, 2 t = T. In words, player& simply pools all the "good rewards" together to make their expectation barely pass the threshold T.? This characterization allows 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 clas- sic prophet inequality. We say a threshold stopping policy with threshold T is a(-strategically) robust if it retains the 1/aaapproximation 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// robusst (Theorem 4.1). Moreover,
"We refer to the one that controls the reward information as the "player", and refer the one that decides when to stop as the "searcher".
"More formally, these response strategies form subgame perfect Nash equilibrium among the sequential- move game of players (which turs out to be unique as far as players' utilities are concerned) (see Remark 3.2).
2

---

this competitive ratio of علاة ~ 0.316 is the best among all known threshold policies that can se- cure the 1/2-approximation 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 ex- tensively 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 2/2-robust (Theorem 5.1). Moreover, this 1/2 ap- proximation 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, 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, c.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 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 is 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, 9I), which studies learning from strategic data providers. We also study similar strategic reward providers, albeit 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 the recently increased interests on using online learning approaches to study the regret minimization when an information-al aavaattttnoo-daattaaeedeed player re- peatedly interacts with an poormation-disadvanaaa their preferences. Instead of focusing on regret minimization, we use the competitive ratio (as con- ventionally used in prophet inequalities) to measure the searcher's '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 decentralized game and each player acts on his own to maximize his payoff.
player [11, 14, 25, 44, 47] without knowing
2 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 strategic player who will be strategically signaling their reward information.
Classic prophet inequality. In standard settings, searcher faces finite sequence of known dis- tributions H e (Hi))en of N non-negative independent random variables. The outcomes (i.e., the rewards) X; H; for [N] are revealed sequentially the searcher for i = 1,..., N. Let A A EH, [X.] denote the mean reward for distribution H;, 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 's goal is to maximize the expected accepted reward. The searcher's ex- pected payoff cannot be more than that of a prophet who knows in advance the realizations of the rewards, namely, XI,...,,,, We denote by OPT A EH.....HN [max.e[N] X.] the prophet value. Given a stopping policy q, let (() be the accepted reward. The stopping policy q is said to be a-approximate (of the prophet value) if the following holds for the searcher's expected payoff for
'Here H. denotes the cumulative distribution function (CDF) of the reward X;
3

---

any imput distributions HI:N:
E
[
2 a OPT
The above statement is often referred to the prophet incquality. For any stopping policy q. the largest constant a E (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 /2, and moreover the ratio of 1/2 is tight. ?
Definition 2.1 (Threshold Stopping Policy). A threshold stopping policy is an online algorithm which pre-computes a threshold value T as function of the distributions H1:N. and then accepts the first reward X, whose value is no smaller than the threshold, i.e., X; 2 T.
It is well-known that multiple thresholds can achieve the optimal 1/2-aprroximation ratio.
Definition 2.2 (/2-aaprrxximation Threshold Spectrum), Let Tkw A Elmax, X.1/2 (Kleinberg and Weinberg [36]), let T satisfy T EiE(N] [[[X; - }. and let Tsc 2 supft :
Pr|max, X; 2 t) 2 1/2} (Samuel-Cahn [42]). Then any threshold stopping policy with threshold T E [Tkw, max [Tsc, T*) }] guarantees //-aapprxiimation to the prophet value."
Prophet inequality with strategic reward signaling. In the strategic setting, each distribution H; 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,, the searcher does not directly observe the realized reward X; He. Instead, she observes an information signal, designed by the player with distribution H,, that is correlated with the reward X₃, We follow the literature in information design [35] to model this strategic reward signaling: Each player chooses signaling scheme Φ.(- x)) E A(E.), where Σ, is a measurable signal space and Φ:(a 2) E [o, 1] specifies the conditional probability of a signal a Σ; that will be sent the searcher when the reward X;
H, is realized. Notice that, upon seeing a signal a ~ Φ:(- x), together with the prior information H; from which the reward is realized, the searcher can update her Bayesian belief about the underlying realized value X,, and then decides whether to stop and choose player i, or reject to continue her search.
Each player i is competing with each other for the final selection from the searcher. Namely, a player obtains payoff if his reward is accepted and payoff 0 if his reward is not accepted." 11 Each player's goal is 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.
Example 2.3 (Examples of Information Strategies). (1) No information strategy: the signal is com- pletely uninformative (e.g., the distribution so;(- x) is a Dirac delta function on a single signal, i.e., | = 1), hence the searcher infers an expected reward of X; = [[X,] as her perceived reward from player (2) Full information revealing strategy: the signal perfectly reveals player i's value to the searcher (i.e., 0:(0 = x x) = for every realized X; = and Σg = su)p(H:))
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 HI-N, the searcher first announces a threshold stopping policy with threshold T that is function of H1:25 (2) Knowing threshold T, each player then picks a signaling scheme (also known as an experiment in economics literature [35, 10)) reveal partial information about the underlying reward; and (3) The searcher learns all players' information strategies, and then conducts search based on her threshold
"Se [40, 19] for the hardness example for the 1/2-approximation. Theere also exists other thresholds that could lead to 1/2-approximation, e.g. any T [min[[sc. Tkw), Tkw) where Tsc è inf(t Pr[maxx X, 2 t] 2 1/23. However, using these thresholds requires to modify the policy detined in Definition 2.1 to be a strict stopping policy to obtain a/p-appoonnnation (i.e., searcher accepts 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.
'll of our results hold if each player i has payoff v; if his reward is accepted and payoff u, if his reward is not accepted as long as Us Ui.

---

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 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 to denote the accepted reward given the searcher's stopping policy q under the strategic reward signaling, and let (²(g) - E[x(") be the searcher's expected payoff. Notice that here the expectation not only over the randomness of the distributions
HIN. but also the information strategies {Øx(- 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, policies described in Definition 2.2 perform under the players' strategic reward signaling. To for- malize our goal, we introduce the following notion of strategic robustness.
particularly interested in how previously studied threshold stopping
Definition 2.4 (a(=strategicallly-ooo roobutt Stopping Policies). A stopping policy is a-robust if it achieves a approximaatin to the OPT when players are strategically signaling their rewards, and it remains 1 /2-approximation in the standard non-strategic setting.
3 Warm-up: Characterizing Optimal Information Revealing Strategy
We start our analysis by showing that when the searcher adopts threshold stopping policy (Defini- tion 2.1), each player's '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 euch player i:
ifT S X then player i's optimal information revealing strategy is the no information strategy; ifT> >s, then player i's optimal information revealing strategy is threshold signaling and de- termined by cutoff i; that satisfies T = [[ X; 2 L,] 1;)= Jt, x (a)(()) - H,((:))- That is, player i's optimal signaling scheme sends one of two signals: X, 2 4 or X; < <.,1
We highlight the intuition behind Proposition 3.1 below. Under threshold stopping policy, every player maximizes his utility by maximizing the probability that the signal's 's posterior expected re- ward is at least T (hence is selected). When the stopping threshold T < A,, this probability is and hence maximized when player i simply reveals no information. When T >> A; this probability is maximized when player blends the highest rewards together form posterior mean just equal to T, which is exactly the scheme described in Proposition 3.1. Remark 3.1 (Addressing Point Masses). For ease of presentation, Proposition 3.1 assumes the distribution H; is continuous. When H; has point masses, Proposition 3.1 still holds, but with more subtle description of the pooling cutoff t, We provide more detailed discussions in the full version of the paper.
Remark 3.2. In game-theoreti 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 enjoy simple structures; indeed, each player's equilibrium strategy is only a function of the threshold T and not on other players' strate- gies or their order. This clean characterization is consequence of the simple structure of (static) threshold policies. If the searcher's 's stopping policy is instead dynamic (i.e. allowing the decision of player to depend on previously realized rewards), SPNE is also well-defined but will adopt sig- nificantly more complex structures. While analyzing the SPNE under these dynamic policies may also be interesting, it beyond the scope of this work since our focus to study the power of static
In the comnrr 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 strategy
5

---

threshold policies, which is also central theme in the study of prophet inequaliries. 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 is actually indifferent on how to disclose the reward when X; S 1ú leading to many different but uulliy--quivalent information strategies.
Equivalent Representation of Optimal Information Revealing Strategy. When T > A player i's optimal information revealing strategy described in Proposition 3.1 pools all the rewards X; H; above t2 together to forge conditional mean value of T, and pools the remaining smaller rewards into another signal. We hence also refer & as the pooling cutoff. This threshold signaling scheme can be equivalently represented as binary-support distribution G; supported on two realizations corresponding to the two signals respectively:
Pra-a, [r = T] = 1 101--H100 H,(4), Pro~G, [a a:] H;(44) where a; A - A 1--T(11H,060 H.(+.) (I)
H2(4.)
In the literature of information design, this distribution G2 is also known a mean-preserving contraction of prior reward distribution H, [27, 12, 13].
Viewing the player i's optimal information strategy as the distribution G3 one can simplify the interaction between the searcher and player as the following when the searcher visits player random reward X; ~ G; is realized, and the searcher stops if and only if X; 2 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 chooses the distribution G, as in Equation (I) according to his prior H; and the threshold 7:13 and (3) the searcher visits each G; sequentially and stops when the first realized reward X; 2 T where X; G,.
We emphasize that in the above reduction, given a threshold stopping policy with threshold T, the searcher's ss expected payoff under the strategic reward signaling can be computed as (²) = E [x()] where the expectation is over distributions G1 and X (4) is the first realized X; G such that (4) 2 T.
4 Achieving 1 1/4e rrobustness for Arbitrary Distributions
In this section, we show that for any distributions HIN, there exists (-srattggcay threshold stopping policy using a threshold within the spectrum Definition 2.2. The main result in this section is stated below.
Theorem 4.1. For any distributions HIN,, a threshold stopping policy with threshold = -Tww is 1-//2 rrouss.t
2
From Definition 2.2, we know that using the threshold stopping policy with threshold Tkw can achieve the optimal 1/2-approximation in the classic prophet inequality for any distributions H Theorem 4.1 above shows another desired property of the threshold Tkw: it can achieve 1-1/-_ approximation even when distributions H are strategically signaling their rewards, thus estab- lishing its 1-//- robustness.. Given the optimality of the threshold Tkw in the non-strategic setting, 2 would be intriguing to ask whether this threshold Tkw can also achieve //-aaprrxximation un- der 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 (-- + appproxxinti for any E >> O under strategic reward signaling.
Proposition 4.2 (Tightness of Theorem 4.1). There exist distributions HI.N such that no threshold from the spectrum in Definition 2.2 can achieve a-robustness where a 1-(1-1/(N- 1
2
Notice that lim 1-1-1/(N-11) tightness of the results in Theorem
1-1// Thus, the above Proposition 4.2 establishes the
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
When T Ai, distribution G; is a point mass mean value Xi.

---

achieve (2 + a)aaprooxiimaioo 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/2aaprrxiimation in the non-strategic setting for thresholds outside the spectrum of Definition 2.2, let alone achieving / /2-approximation simultaneousty in both worlds.
Theorem 4. holds for all distributions, regardless of being discrete or continuous. 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 cleaner to present.
4.1 (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 Pooling Cutoffs). Given a threshold stopping policy with threshold T, let & be the pooling cutoff for each player defined as Proposition 3.1. Let I & arg maX) Lú then we have OPT < (r((t)tt + Σ. T(1 (t,),))
Proof of Lemma 4.3. Let us fix a threshold T, and let I, be the pooling cutoff for player defined in Proposition 3.1. Define by & (X; - + By definition, for each i, we have X, S t, + b, Thus,
OPT = EHEN max X, S max 1, + Σ EH, [b,]
(a) max 44 (T -T- 1.) H:(()))
( (7ll1(t1) + Σ [(())((t)).
x
where inequality (a) follows from the definition of pooling cutoff t; in Proposition 3.1 and inequality (b) follows from the definition of I, t 2 0, and rearranging the terms.
With the above upper bound of prophet value, we have the following results:
Lemma 4.4. Let I satisfy II, Ht)t)) = (N where t! is defined in Proposition 3.1 with threshold Tt, then searcher's expected payoff uz (TT) 2 Tt (1 [I,
II. II, H.(!)) 1-( N=1 OPT. 15
Proof 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²(T) 2 T
11- (1-I1 - H,((.)) Thus, together with
14 All our analysis max, d; 2 OPT/2, then the searcher can simply choose the threshold the thresholds defined in Definition 2.2 to obtain payoff d²(T) > OPT/2. To see this, by Proposition 3.1. if max; A > OPT/2 T', then there exists least one player whose Ay 2 OPT will choose the information revealing strategy, and the searcher surely ohtains payoff smaller than OPT/2.
main text implicitly consider case where max, < OPT/2. we have OPT/2 which lies in the range of
15 Note that for non con-contiuuous distributions 7 always exists but is defined bit differently, please see the full version of the paper for more details.
7

---

Lemma 4.3, we have
T 1 ---I Hi(t.)
" (T)
OPT
OPT
T. (1 -1- H:(4))
IVE
t1Hr((t) + E1 Ht.).)
IV3 IVE IV3
1- ((()))
Hy(t)) (, H.(t)
1 1- N H2(t))
N+1- Σx H:(4)
1- -- (2)+))
N + 1- (II H.())))*
where inequality (a) is by Lemma 4.3; inequality (b) is by the fact that t, S T for all E [N];
inequality (c) is due to (t,) I 1; and inequality (d) is by the AM-GM inequality. Now consider the function (x) A 1-2
N+1-Na over E [0, 11. By choosing x! ) we have f(xl)
N OPT.
This implies that we have T II. N
2
With the above Lemma 4.4, we now ready to prove Theorem 4.1: Proof of Theorem 4.1. From Lemma 4.4, we showed
Tt 1 I- 2 OPT 1 (
)
where !! the pooling cutoff defined in Proposition 3.1 with the threshold 7 By definition of T we have II, (t.) \ < l/.. Thus we can deduce that T 2 OPT/2 = Tkw. Now let t be the pooling cutoff when the searcher uses the stopping threshold Tkw. Then we have
(I- H((t)
(a) 2 Tkw
(1-I H(())) 2 OPT 1- 1/6
u² (TKT)) 2 Tkw
2
where inequality (a) is due to T 2 Tkw, and thus we have i 2/
Achieving ! -robustness for Special Distributions
The preceding section showed the (1- (1-1/)/2-robustneee of the Tkw-threshold stopping policy for ar- bitrary reward distributions. In this section, we show that this ratio be improved to 1/2-robustness when the distributions HI.N satisfy certain conditions: (1) IID distributions - all reward distributions identical, namely, H H, for all E [N] (see Section 5.1); and (2) Log-concave distributions reward distribution H, has log-concave density (see Section 5.2). We also show that 1/2-robustness tight under IID distributions.
5.1 IID Distributions
Our main findings for IID distributions are stated below:
Theorem 5.1. For any distributions HANN where H = H4, Vi E [N]. threshold stopping policy with threshold T = T is -oobbttt 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 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 a-robustness where > 1/ + s for any e >> 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 III) 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 O 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 //aaapproximation in the non-strategic setting" 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 //-approximmtion in the non- strategic setting, then it indeed possible to have a threshold policy that achieves better approximation (specifically, an (1 (1-1/))-appret -appapppoxiimaiion 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 threshold stopping policy that is (1 -/e)- approximation under strategic reward signaling, Moreover, there exist IID distributions such that no threshold stopping policy can achieve (1 (1-1/e + E) approximaaiin for any > O.
5.2 Log-concave Heterogeneous Distributions
In this subsection, we show that when the distributions H1-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 B > 0, let Fa.3 be the family of distributions with log-concave probability density functions f on support [0, 1] such that f(1) Z a and (1(1) 2 -3. If the distributions
H,...., N are all from Fa.8 and N 2 1+ L. then we always have 2 Tkw S Tsc and any threshold T satisfying 2. Tkw S T S Tsc is 1/2-robust.
few remarks on the assumptions Theorem 5.4 are worth mentioning. First, log-concavity of probability density functions is 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 2 1 1 22. This condition becomes less restrictive when a (lower bounding f1)) becomes larger and/or 3 (upper bounding -1)))) becomes smaller. These together, intuitively, imply that f decreases slowly within [0. 1].
Define (xx) A II H.(x). Theorem 5.4 follows directly from the following Lemma 5.5 and Lemma 5.6.
Lemma 5.5. If is convex, then T-Tww < Tsc and any threshold stopping policy with the threshold T satisfying 2- -TKW T Tsc, where Tkw. Tsc are defined as in Definition 2.1, is //2-robust.
Lemma 5.6. If the distributions HI...., H are all from Fa.g and N 2 1+ 2 then H is convex.
6 Conclusion and Future Directions
In this paper, we study a variant of the prophet inequality problem where each random variable is associated with 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/-_ 2 robustness guarantee for arbitrary reward distributions by using not commonly used thresholds out- side the spectrum of Definition 2.2. This may be technically challenging since finding a threshold
Nott that in non-strategic setting, unlike the case for arbitrary distributions where there exists no policy that can achieve better than //>-approximation, for IID distributions, (1 - by tixed threshold together with some careful probabilistic tie- brebbra rule [3] (or 0.7451 1445--ppprooimaattot with an adaptive threshold policy [39]). However, our work, we focus on fixed threshold policy with deterministic tie-breaking rule where //-approximation is still optimal for IID distributions.
can be achieved
A probability density function f IR - igt is log- log-concave if log(f) f) is concave.

---

outside this spectrum with optimal 1/2- /p-apppoxinnttio for the classic -tn-strategic prophet inequality already non-trivial. Another interesting direction 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 cest-of-otthwoolde 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 - approximaatinnnn under the strategic setting. However, it is still unclear whether 1/2-robustness is achievable under threshold stopping policies, no matter whether it static threshold or dynamic threshold. Finally, even if one only cares about the performance under the strategic reward signaling (and ignore the non- non-strategic world), it still unclear which static threshold stopping policy achieves the highest competitive ratio. The au- thors in [20] study a model with 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 improving this bound fur- ther. We note that all our constructed examples in the hardness results (e.g.. Proposition 4.2 and Proposition 5.2) not rule out the existence of such //>-approximation threshold stopping policies.
Acknowledgment. Haifeng Xu is supported in part by the NSF Award CCF-2303372, Anmy Research Office Award 1NF-2-33---000 and ONR Award N00014-23-1-2800 We thank the anonymous reviewers for constructive and helpful comments.
10

---

References
[1] Melika Abolhassani, Soheil Ehsani, Hossein Esfandiari, Mohammad Taghi Hajiaghayi, Robert Kleinberg, and Brendan Lucier. Beating 1-1/e for ordered prophets. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, pages 61-71, 2017.
[2] Saced Alaci. Bayesian combinatorial auctions: Expanding single buyer mechanisms to many buyers. SIAM Journal on Computing, 43(2):30-972, 2014.
[3] Nick Amosti and Will Ma. Tight guarantees for static threshold policies in the prophet secre- tary problem. In Proceedings the 23rd ACM Conference Economics and Computation, EC '22, page 242, 2022.
[4] Makis Arsenis and Robert Kleinberg. Individual fairness in prophet inequalities. In Proceed- ings of the 23rd ACM Conference on Economics and Computation, pages 245-245, 2022.
[5] Pak Hung Au and Keiichi Kawai. Competitive information disclosure by multiple senders. Games and Economic Behavior, 119:56-78, 2020.
[6] Pablo D Azar, Robert Kleinberg, and S Matthew Weinberg, Prophet inequalities with limited information. In Proceedings of the twenty-fithh annual ACM-SIAM symposium on Discrete algorithms, pages 1358-1377. SIAM, 2014.
[7] Moshe Babaioff, Nicole Immorlica, and Robert Kleinberg. Matroids, secretary problems, and online mechanisms. In Symposium Discrete Algorithms (SODA 07), pages 434-443, 2007.
[8] Mark Bagnoli and Ted Bergstrom. Log-concave probability and its applications. In Rationality and Equilibrium: A Symposium in Honor of Marcel K. Richter, pages 217-241. 2prnerr 2006.
(9] Yahav Bechavod, Katrina Ligett, Steven Wu, and Juba Ziani. Gaming helps! learning from strategic interactions in natural dynamics. International Conference on Artificial Intelligence and Statistics, pages 1234-1242. PMLR, 2021.
[10] Dirk Bergemann and Stephen Morris. Bayes correlated equilibrium and the comparison of information structures in games. Theoretical Economics, 11(2):88-5522, 2016.
[11] Martino Bernasconi, Matteo Castiglioni, Andrea Celli, Alberto Marchesi, Francesco Trovò, and Nicola Gatti. Optimal rates and efficient algorithms for online bayesian persuasion. In International Conference on Machine Learning, pages 2164-2183. PMLR, 2023.
[12] David Blackwell. Comparison of experiments. In Proceedings of the second Berkeley sym- posuum on mathematical statistics and probability. volume 2, pages 93-103. University of California Press, 1951.
[13] David A Blackwell and Meyer Girshick. Theory of games and statistical decisions. Courier Corporation, 1979.
[14] Matteo Castiglioni, Andrea Celli, Alberto Marchesi, and Nicola Gatti. Online bayesian per- suasion. Advances Neural Information Processing Systems, 33, 2020.
[15] Shuchi Chawla, Jason D Hartline, and Robert Kleinberg. Algorithmic pricing via virtual valu- ations. In Proceedings of the 8th ACM Conference on Electronic Commerce, pages 243-251, 2007.
[16] Shuchi Chawla, Jason D Hartline, David L Malec, and Balasubramanian Sivan. Multi- parameter mechanism design and sequential posted pricing. In Proceedings of the forty-ecoond ACM symposium Theory of computing, pages 31 311-320, 2010.
[17] Shuchi Chawla, Nikhil Devanur, and Thodoris Lykouris. Static pricing for multi-unit prophet incqualities. Operations Research, 2023.
[18] José Correa, Patricio Foncea, Ruben Hoeksma, Tim Oosterwijk, and Tjark Vredeveld. Posted price mechanisms for a random stream of customers. Proceedings of the 2017 ACM Con- ference Economics and Computation, pages 169-186, 2017.

---

[19] Jose Correa, Patricio Foncea, Ruben Hoeksma. Tim Oosterwijk. and Tjark Vredeveld. Recent developments in prophet inequalities. ACM SIGecom Exchanges, 17(1):61-70, 2019.
[20] Yuan Deng, Vahab Mirrokni, and Hanrui Zhang. Posted pricing and dynamic prior-independent mechanisms with value maximizers. Advances in Neural Information Processing Systems, 35: 24158-20 22169, 2022.
[21] Nikhil R Devanur, Kamal Jain, Balasubramanian Sivan, and Christopher A Wilkens. Near optimal online algorithms and fast approximation algorithms for resource allocation problems. In Proceedings of the 12th ACM conference on Electronic commerce, pages 29-38, 2011.
[22] Nikhil Devanur, Balasubramanian Sivan, and Yossi Azar. Asymptotically optimal algorithm for stochastic adwords. In Proceedings of the 13th ACM Conference Electronic Commerce, pages 388-404, 2012.
[23] Bolin Ding, Yiding Feng, Chien-Ju Ho, Wei Tang, and Haifeng Xu. Competitive information design for pandora's s box. Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 353-381. SIAM, 2023.
[24] Jinshuo Dong, Aaron Roth, Zachary Schutzman, Bo Waggoner, and Zhiwei Steven Wu. Strate- gic classification from revealed preferences. In Proceedings of the 2018 ACM Conference on Economics and Computation, pages 55-70, 2018
[25] Yiding Feng, Wei Tang, and Haifeng Xu. Online bayesian recommendation with no regret. In Proceedings of the 23rd ACM Conference on Economics and Computation, pages 2022.
[26] Matthew Gentzkow and Emir Kamenica. Competition in persuasion. The Review of Economic Studies, 84(1):300-322, 2016.
[27] Matthew Gentzkow and Emir Kamenica. A rothhshhidd-siigiit approach to bayesian persuasion. American Economic Review, 106(5):597-601, 2016.
[28] Matthew Gentzkow and Emir Kamenica. Bayesian persuasion with multiple senders and rich signal spaces. Games and Economic Behavior, 104:411-429, 2017.
[29] Ganesh Ghalme, Vineet Nair, Itay Eilat, Inbal Talgam-Cohen, and Nir Rosenfeld. Strategic classification in the dark. International Conference on Machine Learning, pages 3672- 3681. PMLR, 2021.
[30] Niklas Hahn, Martin Hoefer, and Rann Smorodinsky. Prophet inequalities for bayesian per- suasion. In IJCAL, pages 175-181, 2020.
[31] Mohammad Taghi Hajiaghayi, Robert Kleinberg, and Tuomas Sandholm. Automated online mechanism design and prophet inequalities. In AAAI, volume 7, pages 58-65, 2007.
[32] Moritz Hardt, Nimrod Megiddo, Christos Papadimitriou, and Mary Wootters. Strategic classi- fication. In Proceedings of the 2016 ACM conference on innovations in theoretical computer science, pages 112, 2016.
[33] Theodore Hill and Robert P Kertz, Comparisons of stop rule and supremum expectations of iid random variables. The Annals of Probability, pages 336-345, 1982.
[34] Safwan Hossain, Tonghan Wang, Tao Lin, Yiling Chen, David Parkes, and Haifeng Xu. Multi-sender persuasion computational perspective. arXiv preprint 20X1:22402.04771, 2024.
[35] Emir Kamenica and Matthew Gentzkow. Bayesian persuasion. American Economic Review, 10166):250-26155 2011.
[36] Robert Kleinberg and Seth Matthew Weinberg. Matroid prophet inequalities. In Proceedings of the forty-fourth annual ACM symposium on Theory of computing, pages 123-136, 2012.
[37] Ulrich Krengel and Louis Sucheston. Semiamarts and finite values. 1977.
12

---

[38] Ulrich Krengel and Louis Sucheston. On semiamarts, amarts, and processes with finite value. Probability on Banach spaces, 4:197-266, 1978.
[39] Allen Liu, Renato Paes Leme, Martin Pal, Jon Schneider, and Sivan Balasubramanian. Variable decomposition for prophet inequalities and optimal ordering. EC '21: Proceedings of the 22nd ACM Conference on Economics and Computation, page 692, 2021.
[40] Brendan Lucier. An economic view of prophet inequalities. ACM SIGecom Exchanges, 16(1): 24 47, 2017.
[41] Sebastian Perez-Salazar, Mohit Singh, and Alejandro Toriello. The iid prophet inequality with limited flexibility. arXiv preprint arXiv:2210. 05634,, 2022.
[42] Ester Samuel-Cahn. Comparison of threshold stop rules and maximum for independent non- negative random variables. the Annals of Probability, pages 1213-1216, 1984.
[43] Ravi Sundaram, Anil Vullikanti, Haifeng Xu, and Fan Yao. Pac-learning for strategic classifi- cation. Journal of Machine Learning Research, 24(192):1-38, 2023.
[44] Jibang Wu, Zixuan Zhang, Zhe Feng, Zhaoran Wang, Zhuoran Yang. Michael Jordan, and Haifeng Xu. Sequential information design: Markov persuasion process and its efficient rein- forcement learning. In Proceedings of the 23th ACM Conference Economics and Computa- lion, 2022.
[45] Hanrui Zhang and Vincent Conitzer. Incentive-aware pac learning. In Proceedings of the AAAI Conference Artificial Intelligence, volume 35, pages 5797-5804, 2021.
[46] Tijana Zrnc,, Eric Mazumdar, Shankar Sastry, and Michael Jordan. Who leads and who follows in strategic classification? Advances in Neural Information Processing Systems, 34:15257- 15269, 2021.
[47] You Zu, Krishnamurthy Iyer, and Haifeng Xu. Learning to persuade on the fly: Robustness against ignorance. In Proceedings of the 22nd ACM Conference Economics and Computa- tion, pages 927-928, 2021.
13

---

NeurIPS Paper Checklist
1. Claims
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 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.
fine to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations 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 discussed in the paper.
The authors are encouraged to create 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-specificatton, asymptotic approximations only holding locally). The au- thors should reflect 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, c.g., if the approach was only tested on few datasets or with 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 ap- proach. For example, facial recognition algorithm may perform poorly when image resolution is low images taken in low lighting. Or a speech-to-text system might not be used reliably to provide closed captions for online lectures because 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 ad- dress problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't i acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [es]]
14

---

Justification:
All assumptions are clearly stated, and proofs are rigorously written.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theo- rems.
The proof' can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be comple- mented by formal proof's provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main experimental results of the paper to the extent that it affects the main claims and/or conclu- sions of the paper (regardless of whether the code and data are provided or not)?
Answer: [NA]
Justification: This is theory work, no experiment is provided.
Guidelines:
The answer NA means that the paper does not include experiments. If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary either make it possible for others replicate the model with the same dataset, or provide access to the model. In general. releasing code and data often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all sub- missions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or a way to re- produce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case au- thors are welcome to describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
15

---

Answer:
[NA]
Justification:
No data and code is used.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nipt) cc/
Policy) for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https: //nips cttccc/puuu httppppgpppiiiieeeee Seediddee//eeuubeeeeeee ssi onPolicy) for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [NA]
Justification:
No experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropri- ate information about the statistical significance of the experiments?
Answer: [NA]
Justification: No experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, at least for the experiments that support main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
should be clear whether the error bar is the standard deviation the standard error of the mean.
16

---

is OK to report I-sigma error bars, but one should state it. The authors should prefer- ably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative eтror rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [NA]
Justification:
No experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary failed experiments that didn't 't make it into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics https:
cc ctcpp/ubblcccthicciiieeeeeeeeeed
Answer: [Yes]
Justification:
No violation of NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurlPS Code of Ethies.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (c.g., there is a special consid- eration due to laws or regulations in their jurisdiction).
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 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 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 spe- cific groups), privacy considerations, and security considerations.
17

---

The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is 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 being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitiga- tion strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility MI).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
Not applicable to our paper.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by re- quiring that users adhere usage guidelines or restrictions 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 require this, but we encourage authors to take this into account and make best faith effort.
12. Lieenses for existing assets
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?
Question:
Answer: [NA]
Justification: No assets used.
Guidelines:
The answer NA means that the paper does not 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 URL.
The name the license (c.g., CC-BY 4.0) should be included for each asset. For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
assets are released, the license, copyright information, and terms of use the pack- age should be provided. For popular datasets, paperswi thcode com/ /ataaset has curated licenses for some datasets. Their licensing guide can help determine the li- cense of 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.
18

---

If this information is not available online, the authors are encouraged to reach out to the asset's 's creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documenta- tion provided alongside the assets?
Answer: [NA]
Justification:
No new assets as this is theory work.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moodl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the per include the full text instructions given to participants and sereenshots, applicable, well as details about compensation (if any)?
Answer: [NA]
Justification:
This project is not a crowd sourcing project and has no human subjects.
Guidelines:
The answer NA means that the paper does involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contri- bution of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Ethies, workers involved in data collection, cura- tion, or other labor should be paid at least the minimum wage the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: No IRB needed.
Guidelines:
The answer NA means that the paper does involve crowdsoureing research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equiva- lent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
19

---

The full version of this paper, including detailed proofs, can be found at https://arxiv.org pdf/2409. 18269
20


Reviews:
[{"review_id": "21BBQkUmzL", "reviewer": "Reviewer_mXL5", "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.", "questions": "Questions and remarks :\n1) 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?\n2) 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 ? \n3) Do the authors have any insights about the prophet secretary case? \n4) 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.\n5) 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? \n6) A brief comment on the existence of $T^{\\dagger}$ and $T^*$ that satisfy their relevant equations should be added.\n7) 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? \n\nline 145: the \\nicefrac{} command for $\\mathbb{E}[\\max_i X_i]/2$ makes it too small.", "limitations": "Some limitations regarding strong assumptions and tightness of results have been accordingly addressed in the paper.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1) This is a novel model which incorporates strategic behavior into prophet inequalities, adding to the growing literature of algorithms in strategic environments. \n2) The paper is clear and well written.\n3) The new results are significant, and non-trivial. Upper and lower bounds on the competitive ratio in the strategic setting are provided. This work also considers multiple sub-settings, giving more insight and leaving specific interesting open questions for this new problem.", "weaknesses": "1) It remains unknown whether $(1-1/e)/2$ is the best competitive ratio achievable in the strategic setting.\n2) Some of the additional assumptions made when considering log-concave distributions are strong and too specific.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely thank the reviewer for the positive feedback and valuable comments/suggestions! Please find our response to each of your questions below.\n\n**Q1: Results for i.i.d case** \nWe 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. \n\nHowever, 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.\nThis 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.\n\nHowever, 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.\n\n**Q2: Better results in strategic setting while ignoring performance in non-strategic setting**\nWhen 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.\n\n**Q3: Prophet secretary** \nThanks 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.\n\n**Q4: Comparisons to [29]** \nWe thank the reviewer for this suggestion. We agree with the reviewer and will add more discussions about the comparison to the work [29].\n\n**Q5: Different payoff structure**\nOur 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.\n\n**Q6: Existence of** $T^\\dagger$ **and** $T^*$\nWe 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.\n\n**Q7: Additional assumptions for log-concave distributions**\nWe 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.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "Z6SgDC1Vc0", "reviewer": "Reviewer_vri4", "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.", "questions": "* See weaknesses\n* 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": "The assumptions for all the are clearly stated for all the claims made in the paper.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "* The setting is motivated\n* The paper is well-written and presents a good balance between technical proofs and high level intuitions\n* The paper presents some interesting results.", "weaknesses": "* The optimal revealing strategy is only characterized when the searcher follows a threshold policy\n* 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.\n* 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.\n* 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)$.\n\nMinor weaknesses:\n* 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}$\n* Maybe Definition 2.2 should be a Lemma or Proposition instead\n* 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "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.\n\n**Clarification of the searcher’s stopping policy**\nWe 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.. \n\nIndeed, 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$.\n\nFor 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$.\n\n**Benchmarking within the threshold stopping policies**\nWe 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. \nOur 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.\n\n\n**Optimal revealing strategy when the searcher follows a threshold policy**\nWe 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.\nOn 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. \n\n**1-1/e competitive ratio for iid case**\nThe 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.  \nThe 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. \nLastly, 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$.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "2AomsdiZ6y", "reviewer": "Reviewer_1242", "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.", "questions": "(also including detailed comments)\n\nLine 70, threshold policies: is this without loss of generality?\n\nTimeline 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.\n\nCharacterization 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.\n\nRemark 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.\n\nAround 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": "No concerns.", "rating": 6, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "The model appears novel and sensible, and the results are relatively complete.  It is nice to see best-of-both-worlds guarantees are possible in this model, which wasn't clear to me before the fact.", "weaknesses": "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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely thank the reviewer for the positive feedback! Please find below our response to each of your comments. \n\n**The generality of threshold policies**\nThe 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.\n\n**Threatening policy**\nThis 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. \n\n**Connections to [19]**\nWe 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.\n\nAfter 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! \n\n**½-approximation policy in strategic settings**\nThe 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.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "XsXNqYgFNM", "reviewer": "Reviewer_BRGn", "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.", "questions": "Please see the weaknesses above.", "limitations": "The authors have addressed the limitations of their work.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "Personally, I like the idea of involving incentives in the classic online decision-making problems, and this work successfully gives such a trial. This work is well-motivated in the real-world scenarios for the prophet inequality problem, where the searched agents have incentives to manipulate their true rewards by giving signals. Consequently, this paper transfers the decision-making problem into a game. Also, thresholding algorithms are concise and known to be optimal for the original problem, and it is interesting to see that they can also work well with strategic players under the result that the SPE for these players is also concise. I like this paper's motivation and results, and they can be set as a basis for future work.", "weaknesses": "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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely thank the reviewer for the positive feedback! Please find below our response to your comment.\n\n$(\\alpha, \\beta)$ **Pareto frontier**\nWe 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.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: 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?
Decision: Accept (poster)