Bias Detection via Signaling

Authors: yiling  chen
tao  lin
ariel d procaccia
aaditya  ramdas
itai  shapira
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-13 20:57:54

Abstract: We introduce and study the problem of detecting whether an agent is updating their prior beliefs given new evidence in an optimal way that is Bayesian, or whether they are biased towards their own prior. In our model, biased agents form posterior beliefs that are a convex combination of their prior and the Bayesian posterior, where the more biased an agent is, the closer their posterior is to the prior. Since we often cannot observe the agent's beliefs directly, we take an approach inspired by *information design*. Specifically, we measure an agent's bias by designing a *signaling scheme* and observing the actions they take in response to different signals, assuming that they are maximizing their own expected utility; our goal is to detect bias with a minimum number of signals. Our main results include a characterization of scenarios where a single signal suffices and a computationally efficient algorithm to compute optimal signaling schemes.

Main paper: 
 introduction: 
 A bag contains two coins that look and feel identical, but one is a fair coin that, on a flip, comes up heads with probability 0.5, and the other is an unfair coin with probability 0.9 of heads. You reach into the bag, grab one of the coins and flip it once; it lands on heads. Since you are (hopefully) familiar with Bayes' rule, you conclude that the probability you are holding the fair coin is ≈ 0.36. Now suppose you are offered the following deal: if you pay $1, you get to flip the same coin again, and if it comes up heads, you will receive $1.4. Since you now believe that the probability of heads is 0.76, you take the deal (assuming you are risk neutral) and earn 6 cents in expectation.If, by contrast, another risk-neutral person in the same situation decides to decline the same deal, they must believe that the probability they are holding the fair coin is greater than 0.47. That is, their belief is still very close to the prior of 0.5. We think of such a person as being biased, in the sense that they are unwilling to significantly update their beliefs, despite evidence to the contrary.Of course, failing to update one's beliefs about coin flips is not the end of the world. But this example serves to illustrate a broader phenomenon that, in our view, is both important and ubiquitous. In particular, the "stickiness" of prior beliefs in the face of evidence plays a role in politics -think of the controversy over Russian collusion in the 2016 US presidential election or the existence of weapons of mass destruction in Iraq in 2003. It is also prevalent in science, as exemplified by the polarized debate over the origins of the Covid pandemic [3] .Our goal in this paper is to develop algorithms that are able to detect bias in the form of non-Bayesian updating of beliefs. To our knowledge, we are the first to formalize and analytically address this problem, and we aim to build an initial framework that future work would build on. In the long term, we believe such algorithms could have many applications, including understanding to what degree the foregoing type of bias contributes to disagreement and polarization, and discounting the opinions of biased agents to improve collective decision making.Our approach. The first question we need to answer is how to quantify bias. In this first investigation, we adopt a linear model of bias that was proposed and used as a general belief updating model in economics [8, 10, 5, 18] . If the prior is µ 0 and the correct Bayesian posterior upon receiving a signal (or evidence) s is denoted µ s , we posit that an agent with bias w ∈ [0, 1] adopts the belief wµ 0 + (1 -w)µ s . At the extremes, an agent with bias w = 0 performs perfect Bayesian updating and an agent with bias w = 1 cannot be convinced to budge from the prior.The bigger conceptual question is how we can infer an agent's bias. To address it, we take an approach that is inspired by the literature on information design [13] . In our context, suppose that we (the principal) and the agent have asymmetric information: while both share a common (say public) prior about the state of the world, the principal knows the true (realized) state of the world, but the agent does not. The principal publicly commits to a (randomized) signaling scheme that specifies the probability of sending each possible signal given each possible realized state of the world. Given their knowledge of the latter, the principal draws a signal from the specified distribution and sends it to the agent. Upon receiving such a signal, the agent updates their beliefs about the state of the world (from the common prior) and then takes an action that maximizes their expected utility according to a given utility function. Similarly to the example we started with, it is the action taken by the agent that can (indirectly) reveal their degree of bias.Note that the problem of estimating the exact level of bias reduces to the problem of detecting whether the agent's bias is above or below some threshold. Indeed, to estimate the level of bias to an accuracy of ϵ, log(1/ϵ) such threshold queries suffice by using binary search. The challenge, then, is to design signaling schemes that test whether bias is above or below a given threshold in the most efficient way, that is, using a minimum number of signals in expectation.Our results. We design a polynomial-time algorithm that computes optimal signaling schemes, in Section 4. We first show that constant algorithms, which repeatedly use the same signaling scheme, are as powerful as adaptive algorithms, which can vary the scheme over time based on historical data (Lemma 4.1); we can therefore restrict our attention to constant algorithms. In Lemma 4.5, we establish a version of the revelation principle for the bias detection problem, which asserts that optimal signaling schemes need only use signals that can be interpreted as action recommendations. Finally, building on these insights, we show that the optimal solution to our problem is obtained by solving a "small" linear program (Algorithm 1 and Theorem 4.6).In Section 5, we present a geometric characterization of optimal signaling schemes (Theorem 5.2), which sheds additional light on the performance of the algorithm. In particular, the characterization provides sufficient and necessary conditions for the testability of bias, and also identifies cases where only a single sample is needed for this task.Related work. There is a significant body of experimental work in the social sciences aiming to explain the failure of partisans to reach similar beliefs on factual questions where there is a large amount of publicly available evidence. The fact that biased belief updating occurs is undisputed (to our knowledge), and the focus is on understanding the factors that play a role. In particular, a prominent line of work supports the (perhaps counterintuitive) hypothesis that the more cognitively sophisticated a partisan is, the more politically biased is their belief update process [16, 17, 12, 11] . These results are challenged by more recent work by Tappin et al. [19] , who found that greater analytical thinking is associated with belief updates that are less biased, using an experimental design that explicitly measures the proximity of belief updates to a correct Bayesian posterior. While these studies provide empirical underpinnings for our theoretical model, their research questions are orthogonal to ours: we aim to measure the magnitude of bias regardless of its source. [4, 13] studies how a principal can strategically provide information to induce an agent to take actions that are beneficial for the principal, assuming a perfectly Bayesian agent. Various relaxations of the perfectly Bayesian assumption have been investigated [1, 10, 7, 5, 9, 21, 14] . The work by de Clippel and Zhang [5] is close to us, which studies biased belief update models including the linear model. However, their goal is to maximize the principal's utility with the agent's bias fully known. In our problem the agent's bias level is unknown, and the principal's goal is to infer the agent's bias level instead of maximizing their own utility. Tang and Ho [18] present real-world experiments showing that human belief updates are close to a linear bias model, which supports our theoretical assumption.Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?Answer: [Yes] Justification:Guidelines:• The answer NA means that the abstract and introduction do not include the claims made in the paper. • The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers. • The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings. • It is fine to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper. 
model: 
 Biased agent. Consider a standard Bayesian setting: the relevant state of the world is θ ∈ Θ, distributed according to some known prior distribution µ 0 . If an agent were perfectly Bayesian, when receiving some new information ("signal") s and with the knowledge of the conditional distributions P (s|θ) for all θ, they would update their belief about the state of the world according to Bayes' Rule: µ s (θ) = P (θ|s) = µ0(θ)P (s|θ) P (s). We refer to µ s as the true posterior belief induced by s. Being biased, the agent's belief after seeing s, denoted ν s , is a convex combination of µ s and µ 0 :ν s = wµ 0 + (1 -w)µ s ,where w ∈ [0, 1] is the unknown bias level, capturing the agent's inclination to retain their prior belief in the presence of new information. This linear model was proposed and adopted in economics for non-Bayesian belief updating [8, 10] , in order to capture people's conservatism in processing new information and their tendency to protect their beliefs [20] .The agent can choose an action from a finite set A and has a state-dependent utility function U : A × Θ → R. They receive utility U (a, θ) when taking action a in state θ. The agent will act according to their (biased) belief ν s and choose an action a that maximizes their expected utility:a ∈ arg max a∈A E θ∼νs [U (a, θ)] = arg max a∈A θ∈Θ ν s (θ)U (a, θ).In the absence of any additional information, the agent operates based on the prior belief µ 0 and will select an action deemed optimal with respect to µ 0 . We introduce the following mild assumption to ensure the uniqueness of this action: Assumption 2.1. There is a unique action that maximizes the expected utility based on the prior belief µ 0 : | arg max a∈A { θ∈Θ µ 0 (θ)U (a, θ)}| = 1.This assumption will be made throughout the paper. We denote the unique optimal action on the prior belief as a 0 = arg max a∈A { θ∈Θ µ 0 (θ)U (a, θ)}, and call it the default action.Bias detection. The principal, who knows the prior µ 0 and the agent's utility function U , seeks to infer the agent's bias level from their action as efficiently as possible. The principal has an informational advantage -they observe the independent realizations of the state of the world at each time step. In other words, the principal knows θ t , an independent sample drawn according to µ 0 at time t. The principal wants to design signaling schemes to strategically reveal information about θ t to the agent, hoping to influence the agent's biased belief in a way that the agent's chosen actions reveal information about their bias level. Specifically, with a finite signal space S, the principal can commit to a signaling scheme π t : Θ → ∆(S) at time t, where π t (s|θ) specifies the probability of sending signal s in state θ at time t. After seeing a signal s t , drawn according to π t (s|θ t ) at time t, the agent takes action a t that is optimal for their biased belief ν st . The principal infers information about bias w from the history of signaling schemes, realized states, realized signals, and agent actions H t = {(π 1 , θ 1 , s 1 , a 1 ), . . . , (π t , θ t , s t , a t )}. We denote by Π an adaptive algorithm that the principal uses to decide on the signaling scheme at time t + 1 based on history H t .Given a threshold τ ∈ (0, 1), the principal wants to design Π to answer the following question:Is the agent's bias level w greater than or equal to τ or less than or equal to τ ?1 As noted earlier, by answering the above threshold question, one can also estimate the bias level w within accuracy ϵ by performing log(1/ϵ) iterations of binary search. This effectively reduces the broader task of estimating w to a sequence of targeted threshold checks. By employing an adaptive signaling scheme, this approach lets us approximate w to any desired precision, providing an efficient solution to the bias estimation problem.An algorithm Π for the above question terminates as soon as it can output a deterministic answer. The number of time steps for Π to terminate, denoted by T τ (Π, w), is a random variable. The sample complexity of Π is defined to be the expected termination time in the worst case over w ∈ [0, 1]: Definition 2.1 (sample complexity). The (worst-case) sample complexity of Π is defined as2 T τ (Π) = max w∈[0,1] E[T τ (Π, w)].Our objective is to develop an algorithm Π that can determine whether w ≥ τ or w ≤ τ with minimal sample complexity. Specifically, we want to solve the following minimax problem:min Π max w∈[0,1] E[T τ (Π, w)].We say that an algorithm Π is constant if it keeps using the same signaling scheme repeatedly until termination. Constant algorithms are a special case of non-adaptive algorithms, which may vary the signaling schemes over time but remain independent of historical data.Preliminaries. We now introduce the well-known splitting lemma from the information design literature [2, 13, 15] . It relates a signaling scheme with a set of induced true posteriors for a Bayesian agent and a distribution over the set of true posteriors. Lemma 2.1 (Splitting Lemma, e.g., [13] ). Let π be a signaling scheme where each signal s ∈ S is sent with unconditional probability π(s) = θ∈Θ µ 0 (θ)π(s|θ) and induces true posterior µ s . Then, the prior µ 0 equals the convex combination of {µ s } s∈S with weights {π(s)} s∈S : µ 0 = s∈S π(s)µ s . Conversely, if the prior can be expressed as a convex combination of distributions µ ′ s ∈ ∆(Θ): µ 0 = s∈S p s µ ′ s , where p s ≥ 0, s∈S p s = 1, then there exists a signaling scheme π where each signal s is sent with unconditional probability π(s) = p s and induces posterior µ ′ s .The splitting lemma is also referred as the Bayesian consistency condition. It allows one to think about choosing a signaling scheme as choosing a set of true posteriors, {µ s } s∈S , and a distribution over the set, {π(s)} s∈S , in a Bayesian consistent way.3 Warm-Up: A Two-State, Two-Action ExampleHow can the principal design a signaling scheme to learn the agent's bias level? We use a simple two-state, two-action example to demonstrate how inducing a specific true posterior belief will allow the principal to determine whether w ≥ τ or w ≤ τ .The two states of the world are represented as {Good, Bad}. The agent has two possible actions: Active and Passive. Taking the Passive action always yields a utility of 0, independently of the state. For the Active action, the utility is a if the state is Good and -b otherwise; a, b > 0. We use the probability of the Good state to represent a belief, so the prior is a number µ 0 ∈ [0, 1], which is only a slight abuse of notation. With belief µ ∈ [0, 1] for the Good state (and 1 -µ for the Bad state), the agent's expected utility for choosing the Active action is aµ-b(1 -µ) = (a + b)µ -b.Thus, the Active action is better than the Passive action (so the agent will take Active) ifEQUATIONConversely, the Passive action is better if µ < µ * . Here, µ * = b a+b is an indifference belief where the agent is indifferent between the two actions. We assume that the prior µ 0 satisfies 0 < µ 0 < µ * , so the agent chooses the Passive action by default.Consider the following constant signaling scheme π τ with two signals {G, B}:• If the state is Good, send signal G with probability one.• If the state is Bad, send signal B with probability µ * -µ0 (µ * -τ µ0)(1-µ0) and signal G with the complement probability.We will show that, by repeatedly using π τ , we can test whether the agent's bias w is ≤ τ or ≥ τ . By Bayes' Rule, the true posterior beliefs (for the Good state) associated with the two signals are µ B = 0 (i.e., on receiving B, the agent knows the state is Bad for sure) andµ G = P (Good|G) = µ0•πτ (G|Good) µ0•πτ (G|Good)+(1-µ0)•πτ (G|Bad) = µ * -τ µ01-τ . Notably, the posterior µ G satisfies the following property: if the agent's bias level w is exactly equal to τ , then the agent's biased belief is equal to the indifference belief:when w = τ , ν G = τ µ 0 + (1 -τ )µ G = µ * .We also note the inequality µ 0 < µ * < µ G . As a result, if the agent's bias level w is greater than τ , then the biased belief will be smaller than µ * , and otherwise the opposite is true:for w > τ , wµ 0 + (1 -w)µ G < µ * ; for w < τ , wµ 0 + (1 -w)µ G > µ * .By Equation (1) , this means that the agent will take the Passive action if w > τ , and the Active action if w < τ (on receiving G). Therefore, by observing which action is taken by the agent when signal G is sent, we can immediately tell whether w ≤ τ or w ≥ τ . This leads to the following:Theorem 3.1. In the two-state, two-action example, for any threshold τ ∈ [0, 1-µ * 1-µ0 ], the above constant signaling scheme π τ can test whether the agent's bias w satisfies w ≤ τ or w ≥ τ : specifically, whenever the signal G is sent,• if the agent takes action Active, then w ≤ τ , • if the agent takes action Passive, then w ≥ τ .The sample complexity of this scheme is µ * -µ0 µ0(1-τ ) + 1, which increases with τ .Proof.The range τ ∈ [0, 1-µ * 1-µ0 ] ensures that the probability π τ (B|Bad) = µ * -µ0 (µ * -τ µ0)(1-µ0) is in [0, 1].The two items in the theorem follow from the argument before the theorem statement. The sample complexity is equal to the expected number of time steps until a G signal is sent, which is a geometric random variable with success probabilityP (G) = µ 0 π τ (G|Good) + (1 - µ 0 )π τ (G|Bad) = µ0(1-τ )µ * -τ µ0 . So the sample complexity is equal to the mean 1P (G) = µ * -µ0 µ0(1-τ ) +1.The main intuition behind this result is that in order to test whether w ≥ τ or w ≤ τ , we design a signaling scheme where certain signals induce posteriors that make the agent indifferent between two actions if the agent's bias level is exactly τ . Then, the action actually taken by the agent will directly reveal whether w ≥ τ or w ≤ τ . Such signals are useful signals, but not all signals are necessarily useful. The sample complexity is then determined by the total probability of useful signals. This intuition will carry over to computing the optimal signaling scheme for the general case in Section 4.Finally, we remark that using the constant signaling scheme π τ constructed above to test w ≥ τ or w ≤ τ is in fact the optimal adaptive algorithm, according to the results we will present in Section 4. So, the minimal sample complexity to test whether w ≥ τ or w ≤ τ in this two-state, two-action example is exactly µ * -µ0 µ0(1-τ ) + 1 as shown in Theorem 3.1.Question: Does the paper discuss the limitations of the work performed by the authors?Answer: [Yes]Justification: Limitations are discussed in Section 6.Guidelines:• The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper. • The authors are encouraged to create a separate "Limitations" section in their paper.• The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be. • The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with a few runs. In general, empirical results often depend on implicit assumptions, which should be articulated. • The authors should reflect on the factors that influence the performance of the approach. For example, a facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon. • The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size. • If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness. • While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations. 
theory assumptions and proofs: 
 Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?Answer: [Yes] Justification: 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 crossreferenced. • All assumptions should be clearly stated or referenced in the statement of any theorems. • The proofs 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 complemented by formal proofs provided in appendix or supplemental material. • Theorems and Lemmas that the proof relies upon should be properly referenced. 
computing the optimal signaling scheme in the general case: 
 In this section, we generalize the initial observations from the previous section to the case with any number of actions and states and general utility function U . We will show how to compute the optimal algorithm (signaling scheme) to test the agent's bias level. There are three key ingredients. First, we prove that we can use a constant signaling scheme. Second, we develop a "revelation principle" to further simplify the space of signaling schemes. Building on these two steps, we show that the optimal signaling scheme can be computed by a linear program.In this subsection, we show that adaptive algorithms are no better than constant algorithms for the problem of testing whether w ≥ τ or w ≤ τ . Therefore, to find the algorithm with minimal sample complexity, we only need to consider constant algorithms/signaling schemes.Lemma 4.1. Fix τ ∈ (0, 1). For the problem of testing whether w ≥ τ or w ≤ τ , the sample complexity of any adaptive algorithm is at least that of the optimal constant algorithm (i.e., using a fixed signaling scheme repeatedly).To prove this lemma, we introduce some notations. For any action a ∈ A \ {a 0 }, define vectorEQUATIONwhose components are the utility differences between the default action a 0 and any other action a at different states θ ∈ Θ. Let R a0 ⊆ ∆(Θ) be the region of beliefs under which the agent strictly prefers a 0 over any other action:R a0 = µ ∈ ∆(Θ) | ∀a ∈ A \ {a 0 }, c ⊤ a µ > 0 .As the agent strictly prefers a 0 at the prior µ 0 , we have µ 0 ∈ R a0 . The boundary of this region, ∂R a0 , is the set of beliefs where the agent is indifferent between a 0 and at least one other action a ∈ A \ {a 0 } and a 0 and a are both (weakly) better than any other action:EQUATIONLastly, the exterior of R a0 , denoted as extR a0 , comprises the set of beliefs where the agent strictly prefers not to choose a 0 :extR a0 = ∆(Θ) \ (R a0 ∪ ∂R a0 ) = µ ∈ ∆(Θ) | ∃a ∈ A \ {a 0 }, c ⊤ a µ < 0 .Given a signaling scheme π, we classify its signals into three types based on the location of the biased belief associated with the signal with respect to the region R a0 . Definition 4.1. Let τ ∈ (0, 1) be a parameter. Let s ∈ S be a signal from a signaling scheme π, with associated true posterior µ s and τ -biased posteriorµ τ s = τ µ 0 + (1 -τ )µ s . We say s is • an internal signal if µ τ s ∈ R a0 ; • a boundary signal if µ τ s ∈ ∂R a0 ; • an external signal if µ τ s ∈ extR a0 .The above classification helps to formalize the idea of whether a signal is "useful" for bias detection. A boundary signal is useful because the action taken by the agent after receiving a boundary signal immediately tells whether w ≥ τ or w ≤ τ : Lemma 4.2. When a boundary signal is realized, the agent's action immediately reveals whether w ≥ τ or w ≤ τ . Specifically, if the agent chooses action a 0 , then w ≥ τ ; otherwise, w ≤ τ .Proof. If the agent's bias level satisfies w < τ , then the biased belief ν s = wµ 0 + (1 -w)µ s must be inside R a0 (because µ τ s = τ µ 0 + (1 -τ )µ s is on the boundary of R a0 and µ 0 ∈ R a0 ), so the agent strictly prefers the default action a 0 . If w > τ , then the biased belief ν s is outside of R a0 , so the agent will not take action a 0 .An external signal might also be useful in revealing whether w ≥ τ or w ≤ τ if the agent is indifferent between some actions a 1 , a 2 other than a 0 at the τ -biased belief µ τ s . However, the following lemma shows that, in such cases, we can always modify the signaling scheme to turn the external signal into a boundary signal. This modification will increase the total probability of useful signals and hence reduce the sample complexity. The proof of this lemma is in Appendix A.1. Lemma 4.3. Suppose Π is an adaptive algorithm that uses signaling schemes with internal, boundary, and external signals. Then, there exists another adaptive algorithm Π ′ with equal or lower sample complexity that employs only signaling schemes with internal and boundary signals.An internal signal, on the other hand, is not useful for testing w ≥ τ or w ≤ τ , for the following reason. For an internal signal, the biased belief with bias level τ , µ τ s , lies inside R a0 . Since R a0 is an open region, there must exist a small number ε > 0 such that when the agent has bias level w = τ + ε or τ -ε, the biased belief with bias level w, wµ 0 + (1 -w)µ s , is also inside the region R a0 , so the agent will take action a 0 . As the agent takes a 0 under both w = τ + ε and τ -ε, we cannot distinguish these two cases, so this signal is not helpful in determining w ≥ τ or w ≤ τ . The following lemma formalizes the idea that internal signals are not useful: Lemma 4.4. To test whether w ≥ τ or w ≤ τ , any adaptive algorithm that uses signaling schemes with boundary and internal signals cannot terminate until a boundary signal is sent.Proof of Lemma 4.1. By Lemma 4.3, the optimal adaptive algorithm only uses signaling schemes with boundary and internal signals. By Lemma 4.4, the algorithm cannot terminate until a boundary signal is sent. By Lemma 4.2, the algorithm terminates when a boundary signal is sent. We conclude that the termination time of any adaptive algorithm cannot be better than the constant algorithm that keeps using the signaling scheme that maximizes the total probability of boundary signals.To compute the optimal constant signaling scheme, we need another technique that is similar to the revelation principle in the information design literature [13, 6] . The revelation principle says that, in some information design problems, it is without loss of generality to consider only "direct" signaling schemes where signals are recommendations of actions for the agent, that is, the signal space is S = A, and when the principal sends signal a, it should be optimal for the agent to take action a given the posterior belief induced by signal a.Unlike classical information design problems where the agent is unbiased, our problem involves a biased agent, so we need a different revelation principle: the signals are still action recommendations, but when the principal sends signal a, action a is optimal for an agent with bias level exactly τ ; moreover, if a ̸ = a 0 , then an agent with bias level τ will be indifferent between a and a 0 . This insight is formalized in the following lemma: Lemma 4.5 (revelation principle for bias detection). Let π be an arbitrary signaling scheme that can test w ≥ τ or w ≤ τ . Then, there exists another signaling scheme π ′ that can do so with signal space S = A such that:(1) Given signal a ∈ A, action a is an optimal action for any agent with bias level w = τ .(2) Given signal a ∈ A \ {a 0 }, actions a and a 0 are both optimal for any agent with bias level w = τ . As a corollary, if the agent's bias level w < τ , then the agent strictly prefers a over a 0 ; and if w > τ , then the agent strictly prefers a 0 over any other actions. (3) The sample complexity satisfies T τ (π ′ ) ≤ T τ (π).In the above signaling scheme π ′ , every a ∈ A \ {a 0 } is a boundary signal (Definition 4.1), which is useful for testing bias: given signal a ∈ A \ {a 0 }, if the agent takes action a 0 , then it must be w ≥ τ ; otherwise w ≤ τ . The signal a 0 is internal and not useful for determining w ≥ τ or w ≤ τ . So, the sample complexity of π ′ is equal to the expected time steps until a signal in A \ {a 0 } is sent.The idea behind Lemma 4.5 is combination of signals. Suppose there is a signaling scheme that can determine whether w ≥ τ or w ≤ τ with a signal space larger than A. There must exist two signals s and s ′ under which the agent is indifferent between a 0 and some action a ̸ = a 0 if the agent's bias level is exactly τ . We can then combine the two signals into a single signal s ′′ under which the agent remains indifferent between a 0 and a, yielding a new signaling scheme with a smaller signal space. Repeating this can reduce the signal space to size |A|. See Appendix A.3 for the full proof.Finally, we present an algorithm to compute the optimal (minimal sample complexity) signaling scheme to test whether w ≥ τ or w ≤ τ . The revelation principle in the previous subsection ensures that we only need a direct signaling scheme where signals are action recommendations. The optimal direct signaling scheme turns out to be solvable by a linear program, detailed in Algorithm 1. In the linear program, the constraint in Equation ( 5) ensures that whenever the principal recommends action a ∈ A, it is optimal for an agent with bias level τ to take action a; this satisfies condition (1) in the revelation principle (Lemma 4.5). The indifference constraint (Equation ( 5)) ensures that when the recommended action a is not a 0 , an agent with bias level τ is indifferent between a and a 0 ; this satisfies condition (2) in the revelation principle. The objective (Equation ( 4)) is to maximize the probability of useful signals (those in A \ {a 0 }), hence minimize the sample complexity. Theorem 4.6. Algorithm 1 finds a constant signaling scheme for testing w ≥ τ or ≤ τ that is optimal among all adaptive signaling schemes. The sample complexity of the optimal signaling scheme is 1/p * , where p * is the optimal objective value in Equation (4).Algorithm 1: Linear program to compute the optimal signaling scheme Input : prior µ 0 , utility function U , and the parameter τ ∈ (0, 1) Variable: signaling scheme π, consisting of conditional probabilities π(a|θ) for a ∈ A, θ ∈ Θ Denote ∆U (a, a ′ , θ) = U (a, θ) -U (a ′ , θ). Solve the following linear program:EQUATIONsubject to:                              Optimality of a over other actions:EQUATIONIndifference between a and a 0 :EQUATIONProbability distribution constraints: ∀θ ∈ Θ, a∈A π(a|θ) = 1 and ∀a ∈ A, π(a|θ) ≥ 0.Using the above optimal signaling scheme, whenever the principal recommends an action a other than a 0 , the agent's action immediately reveals whether w ≥ τ or w ≤ τ : if the agent indeed follows the recommendation or takes any other action than a 0 , then the bias must be small (w ≤ τ ); if the agent takes a 0 instead, the bias must be large (w ≥ τ ). Thus, the expected sample complexity is equal to the expected number of iterations until a signal in A \ {a 0 } is sent, which is 1/p * 3 .The linear program in Algorithm 1 has a polynomial size in |A| (the number of actions) and |Θ| (the number of states), so it is a polynomial-time algorithm. The solution p * depends on the geometry of the problem instance and does not seem to have a closed-form expression.The remainder of this section proves Theorem 4.6. The proof requires an additional lemma: Lemma 4.7. Given a signaling scheme π = (π(a|θ)) a∈A,θ∈Θ and an agent's bias level w, after signal a is sent, the agent strictly prefers action a 1 over a 2 under the biased belief if and only if:θ∈Θ π(a|θ) • µ 0 (θ) (1 -w)∆U (a 1 , a 2 , θ) + w θ ′ ∈Θ µ 0 (θ ′ )∆U (a 1 , a 2 , θ ′ ) > 0.Proof. The agent's biased belief under signal a and bias level w is given by (1w)µ0(θ)π(a|θ) θ ′ ∈Θ µ0(θ ′ )π(a|θ ′ ) + wµ 0 (θ), ∀θ ∈ Θ.The condition for the agent to strictly prefer a 1 over a 2 is that the expected utility under the biased belief when choosing a 1 is greater than that of a 2 :θ∈Θ (1 -w) µ 0 (θ)π(a|θ) θ ′ ∈Θ µ 0 (θ ′ )π(a|θ ′ ) + wµ 0 (θ) ∆U (a 1 , a 2 , θ) > 0,where ∆U (a 1 , a 2 , θ) = U (a 1 , θ) -U (a 2 , θ). Multiplying by θ ′ ∈Θ µ 0 (θ ′ )π(a|θ ′ ), we obtain:(1 -w) θ∈Θ µ 0 (θ)π(a|θ)∆U (a 1 , a 2 , θ) + w θ∈Θ µ 0 (θ) θ ′ ∈Θ µ 0 (θ ′ )π(a|θ ′ )∆U (a 1 , a 2 , θ) > 0.Factoring out the terms, this can be rewritten as:θ∈Θ π(a|θ)µ 0 (θ) (1 -w)∆U (a 1 , a 2 , θ) + w θ ′ ∈Θ µ 0 (θ ′ )∆U (a 1 , a 2 , θ ′ ) > 0.3 While our focus is the expected sample complexity, we can also derive a high-probability guarantee: with t ≥ 1 p * log 1 δ iterations, we can determine whether w ≥ τ or w ≤ τ with probability at least 1 -δ. This is because the probability that no useful signal is sent after t iterations is at most (1-p * ) t ≤ δ when t ≥ 1 p * log 1 δ .(0, 0, 1)(1, 0, 0) (0, 1, 0) The three qualitatively different cases for detecting the level of bias, each illustrated within a simplex over three states where µ 0 is the prior belief. Each point in the simplex corresponds to an optimal action for the agent. Green curves indicate indifference between the default action a 0 and another action under an unbiased belief. Orange curves are translated versions of these indifference curves; a posterior on these curves means the agent's biased belief (at bias level τ ) aligns with the green curves. From (a) to (c), τ increases, translating the orange curves further. In Figure 1a , µ 0 can be represented as a convex combination of points on the translated curves, allowing bias level detection with a single sample. In Figure 1b , only some signals are useful, requiring more than one sample in the worst case. In Figure 1c , the bias level cannot be tested against τ .This final expression is positive if and only if the agent to strictly prefer a 1 over a 2 .Proof of Theorem 4.6. According to Lemma 4.1 (constant algorithms are optimal) and Lemma 4.5 (revelation principle), to find an optimal adaptive algorithm we only need to find the optimal constant signaling scheme that satisfies the conditions in Lemma 4.5. We verify that the signaling scheme computed from the linear program in Algorithm 1 satisfies the conditions in Lemma 4.5:• The optimality constraint (Equation ( 5)) in the linear program, together with Lemma 4.7, ensures that: whenever signal a ∈ A is sent, action a is weakly better than any other action for an agent with bias level w = τ . This satisfies the first condition in Lemma 4.5. • The indifference constraint (Equation ( 5)), together with Lemma 4.7, ensures that: whenever a ∈ A \ {a 0 } is sent, the agent is indifferent between action a and a 0 if the bias level w = τ . Then, by the optimality constraint (Equation ( 5)), we have both a and a 0 being optimal actions. This satisfies the second condition in Lemma 4.5.We then argue that the solution of the linear program is the optimal signaling scheme that satisfies the conditions of Lemma 4.5. According to our argument after Lemma 4.5, only the signals in A \ {a 0 } are useful signals, so the sample complexity is equal to the expected number of time steps until a signal in A \ {a 0 } is sent. The probability that a signal in A \ {a 0 } is sent at each time step isa∈A\{a0} π(a) = a∈A\{a0} θ∈Θ µ 0 (θ)π(a|θ).The expected number of time steps is the inverse1 a∈A\{a 0 }θ∈Θ µ0(θ)π(a|θ) (because the number of time steps is a geometric random variable). The linear program maximizes the probability a∈A\{a0} θ∈Θ µ 0 (θ)π(a|θ), so it minimizes the sample complexity.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 conclusions of the paper (regardless of whether the code and data are provided or not)? Answer: [NA] Justification: 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 a 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 a novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is 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 submissions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example (a) If the contribution is primarily a new algorithm, the paper should make it clear how to reproduce that algorithm. (b) If the contribution is primarily a 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 a way to access this model for reproducing the results or a way to reproduce 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 authors 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., to registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results. 
geometric characterization of the testability of bias: 
 To complement the algorithmic solution presented in the previous section, this section provides a geometric characterization of the bias detection problem. We identify the conditions under which testing whether w ≥ τ or w ≤ τ can be done in only one sample, in finite number of samples, or cannot be done at all (which is the scenario where the linear program in Algorithm 1 is infeasible). By Assumption 2.1 (a 0 is strictly better than other actions at prior µ 0 ), we have:c ⊤ a µ 0 = θ∈Θ µ 0 (θ) U (a 0 , θ) -U (a, θ) > 0, ∀a ∈ A \ {a 0 },where c a is as defined in Equation ( 2). Define I a as the set of indifference beliefs between action a and a 0 , which is the intersection of the hyperplane {x|c ⊤ a x = 0} and the probability simplex ∆(Θ):I a := {µ ∈ ∆(Θ) | c ⊤ a µ = 0}.Given a parameter τ ∈ (0, 1), for which we want to test whether w ≥ τ or w ≤ τ , letI a,τ = {µ ∈ ∆(Θ) | (1 -τ )µ + τ µ 0 ∈ I a }be the set of posterior beliefs for which, if the agent's bias level is exactly τ , then the agent's biased belief will fall within the indifference set I a . Lemma 5.1. I a,τ is equal to the intersection of the probability simplex ∆(Θ) and a translation of the hyperplane {x | c ⊤ a x = 0}:I a,τ = µ ∈ ∆(Θ) | c ⊤ a µ = -τ 1-τ c ⊤ a µ 0 .The proof of this lemma is in Appendix B.1. With this representation of I a,τ in hand, we can now present a geometric characterization of the testability of bias. Theorem 5.2 (geometric characterization). Fix τ ∈ (0, 1). The problem of testing w ≥ τ or w ≤ τ• Can be solved with a single sample (the sample complexity is 1) if and only if the prior µ 0 is in the convex hull formed by the translated sets I a,τ for all non-default actions a ∈ A \ {a 0 }: i.e., µ 0 ∈ ConvexHull a∈A\{a0} I a,τ . • Can be solved (with finite sample complexity) if and only if I a,τ ̸ = ∅ for at least one a ∈ A\{a 0 }.• Cannot be solved if I a,τ = ∅ for all a ∈ A \ {a 0 }. Figure 1 illustrates the three cases of Theorem 5.2. In the first case, the solution of the linear program in Algorithm 1 satisfies a∈A\{a0} θ∈Θ π(a|θ)µ 0 (θ) = 1, meaning that useful signals are sent with probability 1, which allows us to tell whether w ≥ τ or w ≤ τ immediately. In the second case, the total probability of useful signals satisfies a∈A\{a0} θ∈Θ π(a|θ)µ 0 (θ) < 1, so the sample complexity is more than 1. In the third case, the linear program in Algorithm 1 is not feasible, so w ≥ τ or w ≤ τ cannot be determined; importantly, this is not a limitation of our particular algorithm, but a general impossibility in our model. The proof of Theorem 5.2 is in Appendix B.2.Question: Does the paper provide open access to the data and code, with sufficient instructions to faithfully reproduce the main experimental results, as described in supplemental material?Answer: [NA] Justification: Guidelines:• The answer NA means that paper does not include experiments requiring code.• Please see the NeurIPS code and data submission guidelines (https://nips.cc/ public/guides/CodeSubmissionPolicy) for more details. • While we encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a 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.cc/public/guides/CodeSubmissionPolicy) for more details. • The authors should provide instructions on data access and preparation, including how to 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 a 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 as possible in supplemental material (appended to the paper) is recommended, but including URLs to data and code is permitted. 
discussion: 
 Our approach has some limitations; here we discuss the two that we view as most significant.First, we have assumed a linear model of bias. While the linear model is common in the literature [8, 10, 5, 18] , we also consider a more general model of bias (in Appendix C): as the bias level w increases from 0 to 1, the agent's belief changes from the true posterior µ s to the prior µ 0 according to some general continuous function ϕ(µ 0 , µ s , w). We show that, as long as the function ϕ satisfies a certain single-crossing property (as w increases, once the agent starts to prefer the default action a 0 , they will not change the preferred action anymore), our results regarding the optimality of constant signaling schemes and the geometric characterization still hold, while the revelation principle and the linear program algorithm no longer work because ϕ is not linear. We consider it an interesting challenge to come up with more general models of bias that are still tractable, in the sense that one can efficiently design good signaling schemes with reasonable sample complexity bounds.Second, we have assumed that the agent's prior is the same as the real prior from which states of the world are drawn. But what if the agent's prior is different? Our results directly extend to the case where the agent has a wrong, known prior. If the agent's prior is unknown, then our problem becomes significantly more challenging. More generally, the agent may have a private type that determines both their prior and utility and is unknown to the principal. We conjecture that testing the agent's bias in this case becomes impossible, because if different types consistently take "opposite" actions, then the actions provide no information about the agent's bias.Despite these limitations, we view our paper as making significant progress on a novel problem that seems fundamental. Our results suggest that practical algorithms for detecting bias in belief update are within reach and, in the long term, may lead to new insights on issues of societal importance. In particular, we anticipate future research in more complex situations such as combining decisions of many experts (human or AI) after measuring and accounting for their individual biases.Question: Does the paper specify all the training and test details (e.g., data splits, hyperparameters, how they were chosen, type of optimizer, etc.) necessary to understand the results? Answer: [NA] Justification: Guidelines:• The answer NA means that the paper does not include experiments.• The experimental setting should be presented in the core of the paper to a 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. 
experiment statistical significance: 
 Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments? Answer: [NA] Justification: 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, confidence intervals, or statistical significance tests, at least for the experiments that support the 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, or overall run with given experimental conditions). • The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.) • The assumptions made should be given (e.g., Normally distributed errors). • It should be clear whether the error bar is the standard deviation or the standard error of the mean.• It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have a 96% CI, if the hypothesis of Normality of errors is not verified. • For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates). Guidelines:• The answer NA means that there is no societal impact of the work performed.• If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact. • Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations. • The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster. • The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology. • If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?Answer: [NA] Justification: Guidelines:• The answer NA means that the paper poses no such risks.• Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters. • Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images. • We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make a best faith effort. 12. Licenses for existing assets Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected? Answer: [NA] Justification: Guidelines:• The answer NA means that the paper does not use existing assets.• The authors should cite the original paper that produced the code package or dataset.• The authors should state which version of the asset is used and, if possible, include a URL. • The name of the license (e.g., CC-BY 4.0) should be included for each asset.• For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided. • If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a dataset. • For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided. • If this information is not available online, the authors are encouraged to reach out to the asset's creators. ν s k ∈ B ε (µ τ s k ) ⊆ R a0 .So, the agent should take action a 0 given signal s k . Note that this holds for every k = 1, . . . , t and any w ∈ [τ -ε 2 , τ + ε 2 ]. So we cannot determine whether w ≥ τ or w ≤ τ so far. We have to run the algorithm until a boundary signal is sent.A.3 Proof of Lemma 4.5Proof. Let π be a signaling scheme that can test whether w ≥ τ or w ≤ τ . According to Lemma 4.3, π can be assumed to only use boundary and internal signals. Recall that a signal s is boundary if the τ -biased belief µ τ s = τ µ 0 + (1 -τ )µ s lies on the boundary set ∂R a0 . For a ∈ A \ {a 0 }, let B a be the set of beliefs under which the agent is indifferent between a and a 0 and a and a 0 are both better than other actions:B a = {µ ∈ ∆(Θ) | c ⊤ a µ = 0 and ∀a ′ ∈ A, c ⊤ a ′ µ ≥ 0}.The boundary set ∂R a0 can be written as the union of B a for a ∈ A \ {a 0 }:∂R a0 = a∈A\{a0} B a .Then, we classify the boundary signals into |A| -1 sets {S a } a∈A\{a0} according to which B a sets their τ -biased beliefs belong to: namely, the set S a contains boundary signals s under which τ µ 0 + (1 -τ )µ s ∈ B a . We then combine the signals in S a . Specifically, consider the normalized weighted average of the true posterior beliefs associated with the signals in S a , denoted by µ a :µ a = s∈Sa π(s) s ′ ∈Sa π(s ′ ) µ s .Note that the τ -biased version of µ a is also in the set B a because B a is a convex set:τ µ 0 + (1 -τ )µ a = s∈Sa π(s) s ′ ∈Sa π(s ′ ) τ µ 0 + (1 -τ )µ s ∈ B a .This means that if a signal a induces true posterior µ a , then this signal is a boundary signal.After defining µ a as above for every a ∈ A \ {a 0 }, let's consider the set of internal signals of the signaling scheme π, which we denote by S I . For each internal signal s ∈ S I , the τ -biased belief satisfies τ µ 0 + (1 -τ )µ s ∈ R a0 . Similar to above, we combine all the signals in S I : define µ a0 to be the normalized weighted average of the posteriors associated with all internal signals:µ a0 = s∈S I π(s) s ′ ∈S I π(s ′ ) µ s .Then, the τ -biased version of µ a0 must be in R a0 because R a0 is a convex set:τ µ 0 + (1 -τ )µ a0 = s∈S I π(s) s ′ ∈S I π(s ′ ) τ µ 0 + (1 -τ )µ s ∈ R a0 .This means that, if a signal induces posterior µ a0 , then this signal is internal.From the splitting lemma (Lemma 2.1), we know that the convex combination of the original posteriors s∈S π(s)µ s is equal to the prior µ 0 . This means that the following convex combination of the new posteriors {µ a } a∈A\a0 and µ a0 is also equal to the prior:a∈A\a0 s ′ ∈Sa π(s ′ )µ a + s ′ ∈S I π(s ′ )µ a0 = a∈A\a0 s∈Sa π(s)µ s + s∈S I π(s)µ s = s∈S π(s)µ s = µ 0where the convex combination weight of µ a is s ′ ∈Sa π(s ′ ) for every a ∈ A \ {a} and the convex combination weight of µ a0 is s ′ ∈S I π(s ′ ). One can easily verify that the weights sum to 1. Then, by the splitting lemma (Lemma 2.1), there exists a signaling scheme π ′ with signal space of size |A| (so we simply denote the signal space by A) where each signal a ∈ A induces posterior µ a . We show that this new signaling scheme π ′ satisfies the properties in Lemma 4.5:• If τ µ 0 + (1 -τ )µ s / ∈ ∂R a0 , then there must exist some action a ′ that is strictly better than a and a 0 for the agent at the τ -biased belief, hence τ µ 0 + (1 -τ )µ s ∈ extR a0 (so s is an external signal). Then, according to the argument in Lemma 4.3, we can find another belief µ ′ s on the line segment between µ s and µ 0 such that the τ -biased version of µ ′ s lies exactly on the boundary set ∂R a0 : τ µ 0 + (1 -τ )µ ′ s ∈ ∂R a0 , µ ′ s = tµ s + (1 -t)µ 0 for some t ∈ [0, 1].After the above discussion, we have found a µ ′ s that is either equal to µ s or on the line segment between µ s and µ 0 , for every s ∈ S. So, µ 0 can be written as a convex combination of {µ ′ s } s∈S :µ 0 = s∈S p ′ s µ ′ s .Moreover, the µ ′ s defined above satisfies τ µ 0 + (1 -τ )µ ′ s ∈ ∂R a0 . So, a signal inducing true posterior µ ′ s will be a boundary signal and useful for testing w ≥ τ or w ≤ τ (Lemma 4.2). Finally, by the splitting lemma (Lemma 2.1), we know that there must exist a signaling scheme π ′ with signal space S where each signal s ∈ S indeed induces posterior µ ′ s . Such a signaling scheme sends useful (boundary) signals with probability 1. Hence, the sample complexity of it is 1.The "only if" part. Suppose whether w ≥ τ or w ≤ τ can be tested with a single sample. This means that the optimal signaling scheme obtained from the linear program in Algorithm 1 must satisfy a∈A\{a0} π(a) = We first prove that, if whether w ≥ τ or w ≤ τ can be tested with finite sample complexity, then I a,τ ̸ = ∅ for at least one a ∈ A \ {a 0 }.According to Lemma 4.1, if we can test whether w ≥ τ or w ≤ τ with finite sample complexity using adaptive algorithms, then we can do this using a constant signaling scheme. Lemma 4.3 further ensures that we can do this using a constant signaling scheme π with only boundary and internal signals. But according to Lemma 4.4, internal signals are not useful for testing w ≥ τ or w ≤ τ . So, the signaling scheme π must send some boundary signal s with positive probability. Let µ s be the true posterior induced by s. By the definition of boundary signal, τ µ 0 + (1 -τ )µ s ∈ ∂R a0 , implying that the agent is indifferent between a 0 and some action a ∈ A \ {a 0 } if their belief is τ µ 0 + (1 -τ )µ s (and a 0 and a are better than any other actions). This means τ µ 0 + (1 -τ )µ s ∈ I a , so µ s ∈ I a,τ by definition. Hence, I a,τ ̸ = ∅.We then prove the opposite direction: if I a,τ ̸ = ∅ for at least one a ∈ A \ {a 0 }, then whether w ≥ τ or w ≤ τ can be tested with finite sample complexity.Let a 1 ∈ A \ {a 0 } be an action for which I a1,τ ̸ = ∅. We claim that: Claim B.1. There exists a state θ 1 ∈ Θ for which the agent weakly prefers action a 1 over action a 0 if the true posterior is state θ 1 with probability 1 and the agent has bias level τ . In notation, let e θ1 ∈ ∆(Θ) be the vector whose θ 1 th component is 1 and other components are 0. The agent weakly prefers action a 1 over action a 0 under belief τ µ 0 + (1 -τ )e θ1 .Proof. Suppose on the contrary that no such state θ 1 exists. Then the agent strictly prefers a 0 over a 1 under belief τ µ 0 + (1 -τ )e θ for every state θ ∈ Θ. This implies that, for any belief µ ∈ ∆(Θ),• Any µ / ∈ R a0 satisfies single-crossing.• For any µ ∈ R a0 , any w ∈ [0, 1], ϕ(µ 0 , µ, w) ∈ R a0 .Under the above general bias model with the stated assumptions, our results regarding the optimality of constant signaling schemes (Lemma 4.1) still holds. The geometric characterization of testability of bias (Theorem 5.2) holds after redefining some notations. Let I a = {µ ∈ ∆(Θ) | c ⊤ a µ = 0} still be the set of beliefs where the agent is indifferent between actions a and a 0 . Let I a,τ still be the set of posterior beliefs for which an agent with bias level τ will be indifferent between a and a 0 , but with a more general expression than the linear model: With the above definition of I a,τ , Theorem 5.2 still holds. We omit the proofs because they are almost identical to the proofs for the linear model.The revelation principle (Lemma 4.5) and the linear program algorithm for computing the optimal signaling scheme (Algorithm 1 and Theorem 4.6) do not apply to the general bias model because ϕ is not linear. Designing an efficient algorithm to compute a good signaling scheme to test bias in a more general model is an interesting future direction.38th Conference on Neural Information Processing Systems (NeurIPS 2024).One may want to test w ≥ τ or w < τ instead. But this requires assumptions on tie-breaking when the agent has multiple optimal actions. Indifference at w = τ allows us to avoid such assumptions.Taking the worst case over w ∈ [0, 1] is not overly pessimistic. As we will show in the proofs, the worst case in fact happens at w ∈ [τ -ε, τ + ε] for some ε > 0, which makes intuitive sense. Therefore, the sample complexity can be equivalently defined as Tτ (Π) = max w∈[τ -ε,τ +ε] E[Tτ (Π, w)]. 
 
 Appendix:  


Decision: The paper studies the problem of detecting a bias in the way an agent updates their prior belief given new evidence. Specifically, it does so by using techniques borrowed from the information design (aka Bayesian persuasion) literature, namely, through the provision of (partially) informative signals to the agent.

All the Reviewers agree on the fact that the paper is well-written and studies an interesting problem. The results presented in the paper also allow to reach interesting conclusions. The Reviewers only raised some (minor) concerns that have been adequately addressed by the Authors in the rebuttal.

Thus, I recommend the paper to be accepted at NeurIPS, **subject to the Authors addressing all the issues raised by the Reviewers in the final version of the paper**.

Reviews: review: paper_summary: paper_summary: The paper studies a Bayesian persuasion problem involving a biased receiver. In this model, the bias is defined by how the receiver deviates from the Bayesian posterior, which is a convex combination of the prior and the induced posterior. The authors propose algorithms to test whether this bias exceeds a fixed constant and discuss scenarios where it is possible or not to fully detect the bias level. In cases where it is possible to detect this bias level, they propose algorithms to solve the problem polynomially using direct signaling schemes.
strength_weakness: strength_weakness: - Under the assumption that the sender knows everything about the environment (prior, utilities, etc.) and only needs to determine if the bias level is larger than a constant, I think that the results are not difficult to derive. The paper presents some characterizations, such as the use of constant algorithms and the study of instances in which it is possible to determine with one sample whether the bias level is greater than a constant, or whether it is not possible even with infinitely many samples. However, these characterizations alone are not sufficient to justify accepting the paper.

- The sample complexity problem studied in this paper is quite different from the classical notion, where you are given two parameters, $\epsilon$ and $\delta$, and you want to output an $\epsilon$-optimal solution with probability $1 - \delta$. I would have found it much more interesting (and standard) to compute a confidence bound for the bias level with high probability, rather than determining if the bias is larger than a constant.

- Finally, the main theorems are not clearly stated.  For example, in the statement of Theorem 3.1, you refer to "the above signaling scheme," which requires the reader to look for this scheme on the preceding page. Additionally, in the main theorem, the final sample complexity of the optimal constant signaling scheme is not specified. This makes it challenging to have a high-level understanding of the contribution of your main theorems.
questions: questions: - In sample complexity problems, you are usually given two parameters $\epsilon$ and $\delta$, and you want to output an $\epsilon$-optimal solution with probability $1-\delta$. In your model, this can be formulated as learning the bias up to an $\epsilon$ error with probability $1-\delta$. My question is, why not study this version of the problem? Can your approach be employed to tackle this version of the problem as well?

- Can your algorithm be extended to scenarios with a multi-type receiver?

- In the case of finite sample complexity, is it possible to achieve a better dependence with respect to $\tau$, or are your results tight?
limitations: limitations: NA
paper_summary: paper_summary: The paper studies the problem of detecting whether an agent is updating their prior beliefs given new evidence in a Bayesian way, or  whether they are biased towards their own prior. The paper considers a setting where biased agents form posterior beliefs that are a convex combination of their prior and the Bayesian posterior (parameterized by an unknown parameter $\omega$). Given a fixed $\tau$, the paper takes an information design to detect where $\omega\ge \tau$ or $\omega\le \tau$. In particular, one can design a signaling scheme and observe that actions taken by the agents to infer the bias level $\omega$. The paper aims to minimize the number of rounds (each round deploying a signaling scheme) needed to detect whether $\omega\ge \tau$ or $\omega\le \tau$. 

The main results of the paper show that (1) a fixed signaling scheme suffices to achieve minimum number of rounds used detect whether $\omega\ge \tau$ or $\omega\le \tau$; (2) a computationally efficient algorithm to compute such optimal signaling scheme for detecting whether $\omega\ge \tau$ or $\omega\le \tau$.
strength_weakness: strength_weakness: There may be an immediate future direction is like given any $\varepsilon\ge 0$, what is the sample complexity of narrowing down the unknown bias level $\omega$ to be in an $\varepsilon$-interval? I feel $O(\log \frac{1}{\varepsilon})$ number of rounds using binary search should suffice (though you may need to carefully handle the randomness of realized signals).

There is a previous work "HOCMP 2021 — On the Bayesian Rational Assumption in Information Design", where that work presents some real-world behavior experiments showing that humans are updating beliefs really not in a Bayesian way, and show that a convex combination of the prior and the Bayesian posterior can better explain human belief updating. The authors may want to include HOCMP 2021 and discuss its connections.
questions: questions: See above
limitations: limitations: N/A
paper_summary: paper_summary: This paper studies the problem of determining the bias level of an agent in updating their beliefs using signaling schemes. Specifically, they detect to what degree, the agent is updating their beliefs biased towards their own prior, or 'correctly' according to the Bayesian rule. They propose a signaling scheme to detect whether the bias level is below or above a given threshold $\tau$. The core of their algorithm design is the revelation principle, which converts to a linear program subjecting to optimality, indifference, and probability distribution constraints.
strength_weakness: strength_weakness: Although the studied problem is novel, it lacks motivation and application in the real world. The authors motivate it by connecting bias to disagreement and polarization, but they don't provide any detailed discussion. Also, currently the authors assume the principal knows the agent's prior. Then it makes no sense to "discount the opinions of biased agents to improve collective decision making" because the principal knows enough information and can solve the optimal decision solely.
questions: questions: The problem studied in this paper is determining whether the bias is below or above a given threshold $\tau$. A closely related, and probably more common problem is directly estimating the bias level using signaling. Can the authors share their thoughts on this? For example, what's the main difficulty of this new problem? Do the authors believe (variants of) constant schemes are still optimal?
limitations: limitations: I don't see any limitations or potential negative societal impact of this work.
paper_summary: paper_summary: The paper studies bias detection in the Bayesian persuasion model. In particular the paper wants to test for a threshold that represents the resistance of the receiver to change its mind and update their prior. The test is performed trough signalling schemes and observe the action performed by the receiver. The paper is concerned with finding the signalling scheme that minimizes the worst case expectation of the needed number of queries. The problem is solved by geometrical techniques.
strength_weakness: strength_weakness: The main weakness in my opinion is the definition of the baseline and its poor understanding in the larger context of PAC learning. 
Why the baseline is defined as such rather then considering the minimum of expected samples needed to understand if \omega\ge\tau-\epsilon or \omega \le \tau+\epsilon with probability at least 1-\delta? This is a key technical point and, while negative results such as lemma 4.4 are expected with \epsilon=0, they are not expected to hold with \epsilon>0. For example for (\epsilon,\delta)-PAC learning for best arm identification in multi armed bandit has infinite samples complexity with \epsilon=0 even in trivial cases such as all the arms have the same mean.
questions: questions: see weaknesses
limitations: limitations: yes

Comments: comment: Thank you very much. We are happy to follow these suggestions.
I thank the authors for their responses. Regarding the PAC learning formulation of the problem, I suggest to the authors to better explain this aspect in the final version of the paper and also discuss the possibility of extending their model to a multi-typed receiver. I believe this would strengthen the current submission. Furthermore, since some of my concerns have been addressed in this rebuttal, I am increasing my score by one point to a borderline accept.
Thank the authors for your response. I do not have further concerns.
We would greatly appreciate your response to the rebuttal, which, in our view, effectively addresses your main concerns. If there are lingering questions, we would gladly engage in a discussion.
We would greatly appreciate your response to the rebuttal, which, in our view, effectively addresses your main concerns. If there are lingering questions, we would gladly engage in a discussion.
Thank you for your response. We will gladly expand this discussion and include it in the paper.
I thank the authors for their reply. I understand now better the relationship with PAC learning. I believe that this discussion should be expanded and included into the paper, as also other reviewers seemed to have similar questions. I confirm my evaluation