Bias Detection via Signaling
Authors: Yiling Chen
Tao Lin
Ariel D. Procaccia
Aaditya Ramdas
Itai Shapira
Venue: NeurIPS 2024 poster (2024)
Keywords: Information design
algorithmic fairness
Bayesian inference
Primary area: algorithmic_game_theory

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.

Bias Detection via Signaling
Yiling Chen Harvard University yilingdseas. harvard. edu
Tao Lin Harvard University tlin8g. harvard. edu
Ariel D. Procaccia
Harvard University
arielpro8g. harvard.edu
Aaditya Ramdas Carnegie Mellon University aramdasdcmu.c edu
Itai Shapira
Harvard University
itaishapira@g. harvard.
Abstract
We introduce and study the problem of detecting whether an agent is updating their prior beliefs given new evidence in optimal way that is Bayesian, whether they are biased towards their own prior. In our model, biased agents form posterior beliefs that are 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 belief's directly, proach inspired by information design. Specifically, we measure an agent's 's bias by designing signaling scheme and observing the actions the agent takes in re- sponse to different signals, assuming that the agent maximizes their own expected utility. Our goal to detect bias with a minimum number of signals. Our main results include characterization of scenarios where single signal suffices and a computationally efficient algorithm to compute optimal signaling schemes.
take an ap-
Introduction
A bag contains two coins that look and feel identical, but one is fair coin that, 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 s 0.36. Now suppose you 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 1..4. Since you now believe that the probability of heads 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 unwilling significantly update their beliefs, despite evidence to the contrary.
Of course, failing update one's beliefs about coin flips serves to illustrate broader phenomenon that, in our view, is both important and ubiquitous. In particular, the "stickiness" prior beliefs in the face of evidence plays 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].
the end of the world. But this example
Our goal this paper develop algorithms that are able detect bias in the form of non -on-Baaesi 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
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

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 investiga- tion, we adopt linear model of bias that was proposed and used general belief updating model
in economics [8, 10, 5, 18]. If the prior is dA and the correct Bayesian posterior upon receiving a signal (or evidence) is denoted ps. we posit that an agent with bias w E [0, 1] adopts the belief' upo + (1 - w) lt. At the extremes, an agent with bias w = O performs perfect Bayesian updating and an agent with bias w cannot be convinced budge from the prior.
The bigger conceptual question is how we can infer an agent's 's bias. To address it, we take an approach that is inspired by the literature information design [13]. In our context, suppose that (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 belief's 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 c, log(1/e /c) 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 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 "small" linear program (Algorithm 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 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 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 de- sign 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.
Classical work in information design [4, 13] studies how a principal can strategically provide infor- mation 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, 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 s utility with the agent's bias fully known. our problem the agent's bias level is unknown, and the principal's 's goal is to infer the agent's bias level instead of maximizing their own utility. Tang and
2

---

Ho [18] present real-world experiments showing that human belief updates are close to linear bias model, which supports our theoretical assumption.
2 Model
Biased agent. Consider a standard Bayesian setting: the relevant state of the world is 0 O, distributed according to some known prior distribution Po- an agent were perfectly Bayesian, when receiving some
information ("signal") and with the knowledge of the conditional dis- tributions P() for all 0, they would update their belief about the state of the world according to Bayes' Rule: Mt (0) = P(0]s) P(al)) We refer to Mss as the true posterior belief induced by Being biased, the agent's belief after seeing 8, denoted Vs, is convex combination of μ4, and JAp:
P(s)
V/3 = WHo + (1 w)jf:
where w E [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 and has a state-dependent utility function U A x θ - R. They receive utility U(a, 8) when taking action in state A. The agent will act according to their (biased) belief V/3 and choose an action a that maximizes their expected utility:
arg max Eg-e, (a 0)] arg max a
Σ (O) 8EB
aEA
In the absence of any additional information, the agent operates based on the prior belief nn and will select an action deemed optimal with respect to (Ag- 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 No: arg max,g A (a)))((a, 1.
This assumption will be made throughout the paper. We denote the unique optimal action on the prior belief as dg arg max.eA (Eeso Mo(O)U(a 0)}, and call it the default action.
Bias detection. The principal, who knows the prior μo and the agent's utility function U, seeks 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. other words, the principal knows 6,, an independent sample drawn according to μ4 at time f. The principal wants to design signaling schemes to strategically reveal information about O to the agent, hoping to influence the agent's biased belief way that the agent's chosen actions reveal information about their bias level. Specifically, with finite signal space S, the principal can commit to a signaling scheme n, θ - (SS) at time L, where (s ()) specifies the probability of sending signal in state 0 at time After seeing signal s,, drawn according to T.(s (,)) at time t, the agent takes action a, that is optimal for their biased belief vs,, The principal infers information about bias from the history of signaling schemes, realized states, realized signals, and agent actions H, = { 01, $1, di)....: : principal uses decide on the signaling scheme time + 1 based on history H4.
(Te, it St, a.)}- We denote by II an adaptive algorithm that the
Given a threshold 7 E (0, 1), the principal wants to design to answer the following question:
Is the agent's 's bias level greater than or equal to or less than equal to r?!
As noted carlier, by answering the above threshold question, one can also estimate the bias level within accuracy by performing (og( iterations of binary search. This effectively reduces the broader task estimating w to a sequence of targeted threshold checks. By employing an adaptive signaling scheme, this approach lets us approximate to any desired precision, providing an efficient solution to the bias estimation problem.
'One may want to test w 2 T or < instead. But this requires assumptions tie- fiebbrakinn when the agent has multiple optimal actions. Indifference
allows avoid such assumptions.

---

An algorithm II for the above question terminates as soon as it can output a deterministic answer. The number of time steps for II to terminate, denoted by T- (II, w), is random variable. The sample complexity of IT is defined to be the expected termination time in the worst case over w E [0, 1]: Definition 2.1 (sample complexity). The (worst-case) sample complexity of II is defined as²
(11) max LTT, (II, wE(0.1]
Our objective is to develop an algorithm II that can determine whether w 2 T or w S with minimal sample complexity. Specifically, we want solve the following minimax problem:
min max [ETT (II, w)]. wE(o,1]
We say that an algorithm II is constant it keeps using the same signaling scheme repeatedly until termination. Constant algorithms are 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 of induced true posteriors for a Bayesian agent and distribution over the set of true posteriors.
Lemma 2.1 (Splitting Lemma, e.g., [13]). Let æ be a signaling scheme where each signal s E S is sent with unconditional probability T(s) = Ense (o()) and induces true posterior Mg. Then, the prior oo equals the convex combination of {HybsEs with weights {T(S)) ses: po E.es (.) Conversely, if the prior can be expressed as a convex combination of distributions p', E A(O): μo = E.ees Pelly, where ps Z 0, >.ES Ps = 1, then there exists a signaling scheme where each signal s sent with unconditional probability x(s) Ps and induces posterior pla-
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, { and a distribution over the set, {<s)) in Bayesian consistent way.
3 Warm-Up: A Two-State, Two-Action Example
How can the principal design 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 2 T or w S T.
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 utility of O, independently of the state. For the Active action, the utility is a if the state is Good and -b otherwise; a, > 0. We use the probability of the Good state to represent belief, so the prior is a number lo E [0, 1]. which is only slight abuse of notation. With belief μ E [0, 1] for the Good state (and 1 for the Bad state), the agent's expected utility for choosing the Active action au -(1 μi) = (a b)μ b. Thus, the Active action is better than the Passive action (so the agent will take Active) if
(a + b) b
(1)
a+b
Conversely, the Passive action is better if μ < n=" Here, 11" obb is an indifference belief where the agent is indifferent between the two actions. We assume that the prior μn satisfies < μo < p², so the agent chooses the Passive action by default.
Consider the following constant signaling scheme म, with two signals {G,
If the state is Good, send signal G' with probability one.
p' po If the state Bad, send signal with probability (n-- (n=- -oo and signal G with the com- plement probability.
*Taking the worst case over w E J0, is not overly pessimistic. As we will show in the proofs, the worst case in fact happens at w E [r e, + e] for some > 0, which makes intuitive sense. Therefore, the sample complexity can be equivalently defined T3 (1I) maxwe[r-e.ra E[2- w)].

---

We will show that, by repeatedly using we can test whether the agent's 's bias w is S or T. 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
NG = P(Good]G) po GG] (1-P)) [G]
(g (Gl Good)
Notably, the posterior JG satisfies the following property: if the agent's bias level we is exactly equal to 7, then the agent's biased belief is equal to the indifference belief:
when T. VG Tyu + (1 -T =
We also note the inequality pe < 1 < μca As a result, if the agent's 'sss bias level w is greater than T, then the biased belief will be smaller than μ², and otherwise the opposite is true:
for w > T, wHo + (1 (l--w)je ww)pG <;;;;
for w <T, wyo + (1 - w)NG > p²"
By Equation (1), this means that the agent will take the Passive action if w action if w < T (on receiving G). Therefore, by observing which action is taken by the agent when signal G' is sent, we can immediately tell whether w S w 2 This leads to the following:
and the Active
Theorem 3.1. In the two-state, two-action example, for any threshold T E [0, 1 the above constant signaling scheme яr can test whether the agent's bias w satisfies w S T or w 2 T: specifically, whenever the signal G is sent,
the agent takes action Active, then w S if the agent takes action Passive, then w 2 T.
The sample complexity of this scheme is _=- ="=uo -]
+ 1, which increases with T.
1ー ensures that the probability कं (=(BBBad) (n- 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 geometric random variable with success probability P(G) = μOT, (G)Godd) + (1
Proof. The range T E [0, 1-pp-
H² 140
(0) TT, (G Bad)
(1-17) So the sample complexity is equal to the mean P(G] po(1-1) +1. μ -Mo
The main intuition behind this result is that in order to test whether w 2 T or w S T, we design a signaling scheme where certain signals induce posteriors that make the agent indifferent between two actions if the agent's 's bias level exuctly r. Then, the action actually taken by the agent will directly reveal whether 2 7 useful. The sample complexity 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.
< Such signals are useful signals, but not all signals are necessarily
Finally, we remark that using the constant signaling scheme N., constructed above test w 2 T or w S T 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 2 T or w S T in this two-state, two-action example is exactly (1-1-
poo + as shown in Theorem 3.1.
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 these two steps, we show that the optimal signaling scheme can be computed by a linear program.
4.1 Optimality of Constant Signaling Schemes
In this subsection, we show that adaptive algorithms are no better than constant algorithms for the problem of testing whether w 2 r or w S r. Therefore, to find the algorithm with minimal sample complexity, we only need to consider constant algorithms/signaling schemes.
5

---

Lemma 4.1. Fix T E (0. For the problem of testing whether w 2 T or w S T, the sample complexity of any adaptive algorithm least that of the optimal constant algorithm (i.e., using fixed signaling scheme repeatedly).
To prove this lemma, introduce some notations. For any action E AA) {. define vector
Ca (Ca,))ooe (U 0) (a, see ER
whose components are the utility differences between the default action ao and any other action different states O. Let Ran A()) be the region of beliefs under which the agent strictly prefers over any other action:
Rao
{u E ((0) Va E (ao), cm 0}.
It is the intersection of |A| open halfspacces with the probability simplex A(O). As the agent strictly prefers ag at the prior μlo. we have 14g E Rag. The boundary of this region, aRag. is the set of beliefs where the agent is indifferent between dg and at least one other action a E A {uo) and ag and a are both (weakly) better than any other action:
Raa {u A()) 3a A {ao), co / 0 and Va' E A (ao), 62220) 0}.
(3)
Lastly, the exterior of Reo denoted as extBaag. comprises the set of beliefs where the agent strictly prefers not to choose Ou:
extRa. = A(0) \ (Rao UR..)) = (ME Ba E A {co); Co < <0)
Given a signaling scheme n, we classify its signals into three types based on the location of the biased belief associated with the signal with respect to the region Rag.
Definition 4.1. Let E (0,1) be a parameter. Let s E S be a signal from a signaling scheme n with associated true posterior μs and --iiased posterior P1 Tpo + (1 M) We say is
an internal signal p. Ravi
a boundary signal if p. E 0
an external signal if pº E ext
The above classification helps to formalize the idea of whether 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 2
S T:
Lemma 4.2. When a boundary signal is realized, the agent's 's action immediately reveals whether 2 T or S r. Specifically, if the agent chooses action ag, then т; otherwise, S T.
Proof. If the agent's 's bias level satisfies w < T, then the biased belief v. = wPo + (1 - w)fts must be inside Rao (because 'oī T/4 (1 T)ps is on the boundary of Ra, and so Rag)) ) so the agent strictly prefers the default action og. If w >> then the biased belief vs is outside of Rao so the agent will not take action ag-
An external signal might also be useful in revealing whether w 2 T w < T if the agent is indif- ferent between some actions a,, 02 other than ag the bibsee belief μº_ However, the following lemma shows that, in such cases, we can always modify the signaling scheme to turn the external signal into 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 II is an adaptive algorithm that uses signaling schemes with internal, bound- ary, and external signals. Then, there exists another adaptive algorithm II' with equal 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 2 T or w I T, for the following reason. For an internal signal, the biased belief with bias level т, nT lies inside Rag Since R. is an open region, there must exist small number > 0 such that when the agent has bias level w = r + e or e, the biased belief with bias level w. wnyo + (1 w)),, is also inside the region Rag. so the agent will take action dg. As the agent takes dg under both = + e and T
we
cannot distinguish these two cases, so this signal not helpful in determining w 2 T or w S T. The
following lemma formalizes the idea that internal signals not useful:

---

Lemma 4,4. To test whether w T or w S 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 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.
4.2 Revelation Principle
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 S A, and when the principal sends signal a, 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 biased agent, so we need a different revelation principle: the signals are still action recommenda- tions, but when the principal sends signal a, action is optimal for an agent with bias level exactly t; moreover, if a o do. then an agent with bias level T will be indifferent between a and ag. 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 2 T or w S T. Then, there exists another signaling scheme n' that can do so with signal space S = A such that:
(1) Given signal a A, action is an optimal action for any agent with bias level w (2) Given signal
AA\ {ao}, actions a and ag are both optimal for any agent with bias level w т. As a corollary, if the agent's ' bias level w < T, then the agent strictly prefers a over oo: and if w > T, then the agent strictly prefers ag over any other actions.
(3) The sample complexity satisfies Tr (x²) S (T).
In the above signaling scheme x', every a E A {aoo is boundary signal (Definition 4.1), which useful for testing bias: given signal a E A {ao). the agent takes action an, then it must be w 2 otherwise S T. The signal an is internal and not useful for determining 2 or S T. So, the sample complexity of nT' equal to the expected time steps until a signal in \ {ao} sent.
The idea behind Lemma 4.5 is combination of signals. Suppose there is a signaling scheme that can determine whether 2 7 or w S T with a signal space larger than A. There must exist two signals and s' under which the agent is indifferent between ag and some action a ag 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 dg 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.
4.3 Algorithm for Computing the Optimal Signaling Scheme
Finally, we present an algorithm to compute the optimal (minimal sample complexity) signaling scheme to test whether 2 F or r. 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 be solvable by 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 7 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 ag. an agent with bias level is indifferent between and ag; this satisfies condition (2) in the revelation principle. The objective (Equation (4)) is to maximize the probability of useful signals (those in A (ao)), hence minimize the sample complexity.
Theorem 4.6. Algorithm I finds a conslant signaling scheme for lesting 2 T S T 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).
7

---

Algorithm 1:
Linear program to compute the optimal signaling scheme
Input : pprior μo, utility function U, and the parameter T E (0.1) 1)
Variable: signaling scheme consisting of conditional probabilities r(al0) for a E A, e
Denote (U a',0) Ul, 0) ( 0). Solve the following linear program:
Maximize
Σ
Σ x(al0)po(0)
(4)
aEA/ap 6EE
subject to:
Optimality of a over other actions: Va E A, Va' E A {a}
(aa(0) ( mo(0) r) + r Σ Ho(0)) (o(t))U(o,dd 2 0: (5)
8EB
M'EB
Indifference between a and ag: Va E A\ {aot.
xaa(0) (o (0(0) (a, (1))))) ao. 0) +
Σ AU 81) =0; (6)
SEB
O'E0
Probability distribution constraints: V0 O
Σ Taal0) = and Va E A, Ta 0) 20
AEA
Using the above optimal signaling scheme, whenever the principal recommends action other than ag, the agent's action immediately reveals whether w 2 T or w S т: the agent indeed follows the recommendation agent takes ag instead, the bias must be large (w 2 7). Thus, the expected sample complexity is equal to the expected number of iterations until signal in A \ {ao} } is sent, which is 1/p"*.
takes any other action than do then the bias must be small (w r); if the
The linear program in Algorithm 1 has polynomial size in |A| (the number of actions) and |O| (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 closed-form expression.
The remainder of this section proves Theorem 4.6. The proof requires an additional lemma: Lemma 4.7. Given signaling scheme signal o is sent, the agent strictly prefers action 01 over 02 under the biased belief if and only if:
(aEE) A,000 and agent's bias level after
Σ x(al0) po(0) (1- ((ll-))A((a,aa0 a2, 0) + w Σ (U))) 0z, 0¹] > 0. 9E9
Proof. The agent's biased belief under signal a and bias level w is given by (1 (o(0)r(a]0)
w) Eo'ee Po (((()))(())) wpo((), VO e θ. The condition for the agent to strictly prefer aj over ag is that the expected utility under the biased belief when choosing a₁ is greater than that of az: (a())
{(1-
Σ (1 BEE
(1-w) w) Σ Eoree (()()))(((())))))) + wHo(()) AU (a1,, az 0) 0,
where AU (a1, 02, 0) = Ua1 0) - (12, 0). Multiplying by Ho we obtain:
(1 w.
(o(0) a2, 02, 0) + w
(0) Σ
(o(())(a|0))A0(m) 0z, 0) > 0.
BEE
BEO
Mee
Factoring out the terms, this can be rewritten
Σ =(ll0))o(0)
w:) AU) (2,, 0) w Σ (o(()) 0.
Whiie our focus is the expected sample complexity, we can also derive a high-probability guarantee: with
1. 2 f log } iterations, we can determine whether 2 S with probability least - 8. This is because the probability that useful signal is sent after iterations is most (1 (1-p")² < when t f log $

---

B0
6.0.1
la.
Ta,
1
1
Pu
Ae
Pe
11..00
0,3.0
1
0.0.00
(a) A single sample
(b) Finite sample complexity
(c) Cannot be solved
Figure 1: The three qualitatively different cases for detecting the level of bias, each illustrated within simplex over three states where /o 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 ag and another action under unbiased belief. Orange curves translated versions of these indifference curves; posterior on these curves means the agent's biased belief (at bias level r) aligns with the green curves. From (a) to (c), increases, translating the orange curves further. In Figure la, Mo can be represented as a convex combination of points on the translated curves, allowing bias level detection with 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 T.
This final expression is positive if and only if the agent to strictly prefer a1 over az.
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 only need to find the optimal constant signaling scheme that satisfies the conditions 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, en- sures that: whenever signal E A is sent, action 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 \ {ao} is sent, the agent is indifferent between action and ag if the bias level w т. Then, by the optimality constraint (Equation (5)), we have both a and op being optimal actions. This satisfies the second condition in Lemma 4.5.
We then argue that the solution of the linear program 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 } are useful signals, so the sample complexity equal to the expected number of time steps until signal in A {oo} is sent. The probability that a signal in A {ao} is sent each time step is
Σ aE ((oo)
T(a)= = Σ Σ
po(0))
(EA)(ao) dEe
The expected number of time steps is the inverse ber of time steps is geometric random variable). The linear program maximizes the probability EaeA)ao Eoce (a))) so minimizes the sample complexity.
E.EAy(oo Zese (((o) (because the num-
Geometric Characterization of the Testability of Bias
To complement the algorithmic solution presented in the previous section, this section provides geometric characterization of the bias detection problem. We identify the conditions under which testing whether 2 cannot be done at all (which is the scenario where the linear program in Algorithm is infeasible).
S т can be done in only one sample, in finite number of samples, or
By Assumption 2.1 (ao is strictly better than other actions at prior po), we have:
T c no
Σ
(o 0) Uaa 0)) O, Va {

---

where is as defined in Equation (2). Define Ia as the set of indifference beliefs between action and og. which is the intersection of the hyperplane {z|c, x = 0} and the probability simplex A()):
La = { E (()) c H = 0}.
Given parameter (0, 1), for which want to test whether
S let
la,- {u E A(+) (1 - T)и + TPo E 1
be the set of posterior beliefs for which, the agent's bias level is exactly т, then the agent's biased belief will fall within the indifference set la-
Lemma 5.1. larr is equal to the intersection of the probability simplex A(0) and a translation of the hyperplane {x Cg x = 0}: la, = {u A(0) I c - 1o).
The proof of this lemma is in Appendix B. With this representation of Jar in hand, we can now present geometric characterization of the testability of bias.
Theorem 5.2 (geometric characterization). Fix T E (0,1). 1). The problem of testing w 2 T or w S
Can be solved with a single sample (the sample complexity 1) if and only if the prior po is in the convex hull formed by the translated sets la,5 for all non-default actions a E AA {ao}: i.e.
Fo E Convex (ull Ua Ja,z)
Can be solved (with finite sample complexity) if and only if Ja,r + for at least one a E A {
Cannot be solved if la, for all E A {ao).
Figure illlstraaes the three cases of Theorem 5.2. In the first case, the solution of the linear program in Algorithm 1 satisfies EueA((ao) } Eess क (o()))) = 1, meaning that useful signals are sent with probability 1, which allows us to tell whether 2 or S T immediately. In the second case, the total probability of useful signals satisfies Eaedy(ao) Eoco x (al())u (0) < 1, so the sample complexity is more than 1. In the third case, the linear program in Algorithm I is not feasible, so T w < cannot be determined; importantly, this is not limitation of our particular algorithm, but a general impossibility in our model. The proof of Theorem 5.2 is in Appendix B.2,
Discussion
Our approach has some limitations; here discuss the two that we view as most significant.
First, we have assumed linear model of bias. While the linear model common in the literature [8, 10, 5, 18], we also consider more general model of bias (in Appendix C): as the bias level w increases from 0 to 1, the agent's 's belief changes from the true posterior (ds to the prior 140 according to some general continuous function ((po) Me, w). We show that, as long the function é satisfies certain single-crossing property (as w increases, once the agent starts to prefer the default action ag, 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 longer work because é is not linear. We consider it interesting
the linear program algorithm 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 's prior is unknown, then our problem becomes significantly more challenging. More generally, the agent may have private type that determines both their prior and utility and is unknown to the principal. We conjecture that testing the agent's '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 's bias.
Despite these limitations, we view our paper making significant progress on a novel problem that seems fundamental. Our results suggest that practical algorithms for detecting bias 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 more complex situations such as combining decisions of many experts (human AD) after measuring and accounting for their individual biases.
10

---

Acknowledgments
This research was partially supported by the National Science Foundation under grants IIS-2147187, IIS-2229881 and CCF-2007080; and by the Office of Naval Research under grants N00014-20-1- 2488 and N00014-24-1-2704.
References
[1] R. Alonso and O. Câmara. Bayesian persuasion with heterogeneous priors. Journal of Eco- nomic Theory, 165:672-706, 2016.
[2] R. J. Aumann, M. B. Maschler, and R. E. Stearns. Repeated Games with Incomplete Informa- tion. MIT Press, 1995.
[3] J. D. Bloom, Y. A. Chan, R. S. Baric, P. J. Bjorkman, S. Cobery, B. E. Deverman, D. N. Fisman, R. Gupta, A. Iwasaki, M. Lipsitch, R. Medzhitov, R. A. Neher, R. Nielsen, N. Patter- son, T. Stearns, E. van Nimwegen, M. Worobey, and D. A. Relman. Investigate the origins of COVID-119. Science, 372(6543):694,, 2021.
[4] V. P. Crawford and J. Sobel. Strategic information transmission. Econometrica, 50(6):1431- 1451, 1982.
[5] G. de Clippel and Zhang. Non-Bayesian persuasion. Journal of Political Economy, 130 (10):2594-264) 2022.
[6] Dughmi and Xu. Algorithmic Bayesian persuasion. In Proceedings of the 48th Annual ACM Symposium on Theory of Computing (STOC), pages 412-425, 2016.
[7] Dworezak and A. Pavan. Preparing for the worst but hoping for the best: Robust (Bayesian) persuasion. Econometrica, 90(5):2017-2051, 2022.
[8] L. G. Epstein, J. Noor, and A. Sandroni. Non-Bayesian learning. The B.E. Journal of Theoret- ical Economics, 10(1):732-7535 2010.
[9] Yiding Feng, Chien-Ju Ho, and Wei Tang. Rationality-robust information design: Bayesian persuasion under quantal response. In Proceedings of the 2024 A ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 501-546. SIAM, 2024.
[10] D. Hagmann and G. Loewenstein. Persuasion with motivated beliefs. Carnegie Mellon Uni- versity technical report, 2017.
[11] D. M. Kahan. Ideology, motivated reasoning, and cognitive reflection. Judgment and Decision Making, 8(4):18, 2013.
[12] D. M. Kahan, E. Peters, M. Wittlin, P. Slovic, L. L. Ouellette, D. Braman, and G. Mandel. The polarizing impact of science literacy and numeracy on perceived climate change risks. Nature Climate Change, 2(10):732-735, 2012.
2012.
[13] E. Kamenica and M. Gentzkow. Bayesian persuasion. American Economic Review, 101(6): 2590-2615,, 2011.
[14] T. Lin and Y. Chen. Persuading a learning agent. arXiv preprint arXt:22402.09721, 2024.
[15] J. Renault. Repeated games with incomplete information. In R. A. Meyers, editor, Encyclope- dia of Complexity and Systems Science. Springer, 2012.
[16] C. S. Taber and M. Lodge. Motivated skepticism in the evaluation of political beliefs. American Journal of Political Science, 50(3):755-765 2006.
[17] C. Taber, D. Cann, and S. Kuesova. The motivated processing of political arguments. Polit- ical Behavior, 31(2):137-155 2009.

---

[18] Wei Tang and Chien-Ju Ho. On the Bayesian Rational Assumption in Information Design. Proceedings of the AAAI Conference on Human Computation and Crowdsoureing. 9:120-130, October 2021. ISSN 7769-1144, 2769-1330. doi: 10. 10.1609//comp.v9i1 v91..p9...1.......... URI. https: //ojs.aaii.
[19] B. M. Tappin, G. Pennycook, and D. G. Rand. Bayesian or biased? Analytic thinking and political belief updating. Cognition, 204:104375, 2020.
[20] E. Ward. Conservatism in human information processing. In D. Kahneman, P. Slovic, and A. Tversky, editors, Judgment Under Uncertainty: Heuristics and Biases. Cambridge Univer- sity Press, 2007.
[21] K. Yang and Zhang. Computational aspects of Bayesian persuasion under approximate best response, arXiv preprint arXiv:2402.07426, 2024.
12

---

NeurIPS Paper Checklist
Claims
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 perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results
be expected to generalize 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 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 not 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-specification, 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, e.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 the factors that influence the performance of the ap- proach. For example, a 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 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 faimess.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to 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: [Ys]]
13

---

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 cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theo- rems.
The proof's 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:
Guidelines:
The answer NA means that the paper does not include experiments. If the paper includes experiments, a No answer 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?
14

---

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://nipp cc/
https//oooeSueassiieeeeeee awssononncclyoll for more details. Seaiic//gides/Coooe
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.c..
gewgde//ooeeeiiiieeeeeee sebbbmsssii 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:
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:
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.
15

---

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 error 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 on the com- puter resources (type of compute workers, memory, time of execution) needed reproducc the experiments?
Question:
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of 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 or failed experiments that didn't 't make it into the paper).
9. Code Of Ethies
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https: : /ttp///eerppp.eeeee cc ht/pppiccc/tthiiciiieeeelses
Answer: [Yes]
Justification:
Guidelines:
The answer NA means that the authors have not reviewed the NeurlPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is a special consid- eration due to laws or regulations their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification: They discussed in Section and Section 6.
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 spe- cific 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 direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that improvement in the quality of generative models could be used to
16

---

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 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 mitiga- tion strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML).
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:
Guidelines:
The answer NA means that the paper poses no 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 quiring 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 challenging, and many papers do require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators 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:
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 dataset.
The authors should state which version of the asset used and, if possible, include URL.
The name 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 the pack- age should be provided. For popular datasets, paperswitheeee whwoodeitthheee.eeo com/ datasets 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 has changed) should be provided.
this information is not available online, the authors are encouraged to reach out to the asset's is creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and the documenta- tion provided alongside the assets?
17

---

Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details the d as part their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset 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 pa- per include the full text of instructions given participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does not 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 the main paper.
According to the NeurlPS Code of Ethics, workers involved in data collection, cura- tion, or other labor should be paid at least the minimum wage in 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 equivalent approval/review based the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending on the country which research conducted, IRB approval (or equiva-
lent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors to adhere the NeurIPS 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.
18

---

A Missing Proofs from Section
A.1 Proof of Lemma 4.3
Proof. Suppose that, during its operation, IT selects a signaling scheme æ that includes an external signal 8 E S. By definition, for an external signal, the r-biased belief nr T44 (1 p) is in ext Rag- This implies that the true posterior μss derived from the signaling scheme и and the prior μ4. also lies in ext.R... Consequently, the line segment connecting μl, and μo- represented as {(1 t) + tuo t E [0, I[}. must intersect the boundary &Ro at some point. Denote this intersection by y =
Jus + t" 1o E RRa
We will adjust the original signaling scheme म. To do so, define jı as the belief whose r-biased version equals μ²:
p (1" T) + (1 (1- 1')
Tuo + (1-r) μ²
Under the original signaling scheme иτ, according the splitting lemma (Lemma 2.1), the prior μo can be represented as a convex combination of μt and the posteriors associated with other signals s' 8 {s}:
Pg = Pofts +
Σ
Pe
If we change μ4 to a... then we obtain a new convex combination (this is valid because j., is on the line segment from pa to po):
Pg = Pufts +
Σ
Ps
('ES((a)
where
and Vs' e S {s}, Po ====--- 1-1+ Par
1 8" + ttP
Then, by the splitting lemma (Lemma 2.1), there exists a signaling scheme n' with [S] signals where signal s induces posterior fa and other signals induces (Ayt. Note that the 7-biased version of jts satisfies 7400 + (1 r) μ² 2Rag. is boundary signal under signaling scheme n².
Since 8 a boundary signal, we can immediately tell whether w 2 T or w S T according to Lemma 4.2 when is sent and end the algorithm. If any signal s' other than is sent, the induced posterior Ha is the same as the posterior in the original signaling scheme π, so the agent will take the same action, and we can just follow the rest of the original algorithm II. But note that the probability of signal being sent under the new signaling scheme n' is larger than or equal to the probability under the original signaling scheme
D8
p.
Ps-
1
t"ps
So, in expectation, we can end the algorithm faster by using ă than using Hence, by repeating the above procedure to replace all the signaling schemes in the original algorithm that use external signals, we obtain new algorithm II' that only uses boundary and internal signals with smaller or equal sample complexity.
A.2 Proof of Lemma 4.4
Proof. Let IT be any adaptive algorithm using signaling schemes with boundary and internal signals.
Let H, [ 0,, $1, (1,)),,,,,. ai),... (Te, 0,, St, az)} be any history that can happen during the execution of II. If no boundary signal has been sent, then every realized signal 8& is an internal signal in the respective signaling scheme Tk, with the r-biased posterior satisfying PI = THo (1 T) Rag Because Rap {n E A(O) Va A {ao): cf > 0} is an open region, there must exist some EN > 0 such that the norm ball Be, (1E,) = {n E A(O) || MT, ll S Ex} is subset of Ra,, Let E = min Ey > 0. Then B. (HT,.) C Ra, for every = l..... tt. Suppose the agent's 's bias level w is in the range [r 2, + 5]. Then, for every signal sk. the agent's 's biased belief
= wpo + (1 W)H, satisfies:
|R.. Ma
[1(w - -Ho )ll S l/o- - T/. IlMo Ms S
19

---

This means
Vs B,(p Roo
So, the agent should take action ag given signal 8k- Note that this holds for every 1,...,f and any [T 1. i.. So we cannot determine whether w or S so fär. We have to run the algorithm until a boundary signal is sent.
A.3 Proof of Lemma 4.5
Proof. Let a be a signaling scheme that can test whether w 2 or w I т. According to Lemma 4.3, be assumed only use boundary and internal signals. Recall that signal is boundary if the r-biased belief !4,"" = 7/40 + (1 p) lies on the boundary set &..- For a E A \ {ao), let Ba be the set of beliefs under which the agent is indifferent between and ag and and dg are both better than other actions:
B₂ (u A()) c.. l
and Va' A, A, 2 0}.
The boundary set Raa can be written as the union of Ba for E A {ao}:
a R
U Ba-
oEA\(ao)
Then, we classify the boundary signals into |A| -1 sets Aa according to which Ba sets their r-biased beliefs belong to: namely, the set S. contains boundary signals under which
T/40 (1 -) E B..
We then combine the signals in Sa- Specifically, consider the normalized weighted average of the true posterior beliefs associated with the signals in Sa, denoted by Ma:
((s)
Na Σ Eves. (88) us.
SES.
Note that the r-biased version of pa is also in the set Bo because B, is convex set:
Σ EVES, (8") (THO + (1 (1-r)ua) E Ba.
x(8)
TPo + (1 T)Ha
Eves.
sES.
This means that if a signal a induces true posterior Paa then this signal is boundary signal.
After defining Na above for every a E A {aaJ, let's consider the set of internal signals of the signaling scheme r,, which we denote by Sj. For each internal signal Sj, the r-biased belief satisfies
THo + (1 T)H Rag
Similar to above, we combine all the signals in Sy: define Mao to be the normalized weighted average of the posteriors associated with all internal signals:
((s)
Moo Σ Σ
SES, EvES, ((s)) Mo.
Then, the b-biseed version of Map must be in Rap because Ray is convex set:
THo + (1 - P)
Eves, T(s') Σ (THO + (1 ( -))a)) E Rag
Σ
a(s)
sES;
This means that, a signal induces posterior Pag- then this signal is internal.
From the splitting lemma (Lemma 2.1), we know that the convex combination of the original pos- teriors E.es {())ua is equal to the prior po. This means that the following convex combination of the new posteriors {PolaeAras and Mag also equal the prior:
Σ Σ T(')) + Σ (ss))oo
Σ
Σ T(S) +
Σ *()) = Σ T(S)) Po SESI
eEA'ia S'E..
s'ESt
GEAl sES.
where the convex combination weight of pa is Eres, (88) for every a E (a) and the convex combination weight of Ma, is Eves, T(s'). One can easily verify that the weights sum to 1. Then, by the splitting lemma (Lemma 2) there exists signaling scheme T' with signal space of size |A] (so we simply denote the signal space by A) where each signal a E induces posterior Pa- We show that this new signaling scheme T' satisfies the properties in Lemma 4.5;
20

---

Signal induces posterior Map whose 7-biased version satisfies THO + (1- Pao E Rao- So, given signal og- action ag the optimal action for an agent with bias level т.
For each signal a E A \ {ao}, the induced posterior μa satisfies Tμ4 + (1 T) E Ba S agag. So, by the definition of Ba agent with bias level is indifferent between actions a and ag and these two actions are better than other actions. Also, this signal is a boundary signal by Definition 4.1, which satisfies the following according Lemma 4.2: if the agent's 's bias level w < т, then the agent strictly prefers a over ag; if w > т, then the agent strictly prefers og over a.
The sample complexity of r' is the same π because: (1) the sample complexity equal to the inverse of the total probability of boundary signals (as corollary of Lemma 4.4), and (2) the total probability of boundary signals of the two signaling schemes the same:
Σ
a'(a)=
E
T(5')
Σ
TT)).
aEA(fa))
aEAlfao) s'ES.
So, (,(x)==)))))))) = (TTT)
B Missing Proofs from Section 5
B.1 Proof of Lemma 5.1
Proof. For y A(O), by convexity of A(O), have (1 - T) + 7P4 A(@). Then,
la.r > (1 TT- TMo E la < Co ((1 - T + TpO) 0
(1 T ccp | TC 14
c 1 co_ mo.
B.2 Proof of Theorem 5.2
We first prove the first part of Theorem 5.2, then prove the the second and third parts.
B.2.1 Proof of Part of Theorem 5.2
We want to prove that w 2 T or w S 7 can be tested with a single sample if and only if the prior No is in the convex hull formed by the translated sets la.r for all non-default actions A { N4 E ConvexHull( UaEA((av) Ta,r)
The "if" part. Suppose po ConvexHull Uaed)(ao) la,z ). namely, there exist a set of positive weights {p.bes and a set of posterior belief's {1s Jess such that
Pg = Σ
PoHls
SES
where each μ4 E Ia.r for some a E A {ao}. ). By definition, the r-biased belief T/4o + (1 - 7 T)Hs in the indifference set Ia- Recall the definition of the boundary set 2Ra, (Equation (3)). which is the set of beliefs under which the agent is indifferent between ag and some other action and these two actions are better any other actions. The --iasedd belief TPo (1 1 7)p, Ta may may belong to Rag depending on whether and ag are better than any other actions:
If тyo + (1 - T)Hs E Rags then s is boundary signal (by Definition 4.1) and hence useful for testing whether w
S 7 (Lemma 4.2). Denote μl, Me in this casc.
21

---

If T4Oo + (1-T))s & R. then there must exist some action a' that is strictly better than a and ag for the agent the r-biased belief, hence 74o + (1 -)ps E extR (so s an external signal). Then, according to the argument in Lemma 4.3, we can find another belief 1' on the line segment between 14s and μo such that the r-biased version of ju lies exactly on the boundary set Rao
THo + (1 t)p' E dRag =1 + (1 t) for some E [0, 1].
After the above discussion, we have found u² that is either equal to μ사 or on the line segment between Na and No. for every s S. So, no can be written as a convex combination of {pg)aes:
P40 = EP'als RES
Moreover, the N² defined above satisfies 7/40 + (1- T)p', E &Ra. So, a signal inducing true posterior n4, will be boundary signal and useful for testing 2 w T (Lemma 4.2). Finally, by the splitting lemma (Lemma 2.1), we know that there must exist a signaling scheme n' with signal space S where each signal E S indeed induces posterior /' Such signaling scheme sends useful (boundary) signals with probability 1. Hence, the sample complexity of it
The "only if" part. Suppose whether T I means that the optimal signaling scheme obtained from the linear program in Algorithm must satisfy Eo (a) EneA)(ag) (ag)) Loce (a (0)) = 1, namely, the total probability of useful signals (signals in A \ {{o)) is Then, by the splitting lemma, the prior poo can expressed
be tested with single sample. This
as the convex combination
H4 = Σ x(a)aa
(EA)(a)
where T(a) = =a)==Eee Mo (a)))) is the unconditional probability of signal and Hr, is the true posterior induced by signal a. Moreover, the indifference constraint (6) in the linear program ensures that the agent is indifferent between a and ao upon receiving signal a if the agent has bias level T: mathematically, T/40 + Taa E Ta. This means Paa E la,r by definition. So, we obtain
μo E ConvexHull
U
Ia.
aEAl(ao}
B.2.2 Proof of Parts and 3 of Theorem 5.2
We first prove that, whether w 2 T or w S r can be tested with finite sample complexity, then larr * @ for at least one E A {pn)-
According to Lemma 4.1, we can test whether 2 T or w S T 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 > T So, the signaling scheme π must send some boundary signal s with positive probability. Let μs be the true posterior induced by By the definition of boundary signal, T/4 + (1 T)H E 0Ra implying that the agent is indifferent between ag and some action a E A \ {ao} if their belief is THo + (1--)de T)H,, (and ag and a are better than any other actions). This means THe + (1 T)p, Ia. so pa E La,r by definition. Hence, la,r + 0.
S т.
We then prove the opposite direction: if Ta.- * 0 for at least one A {oo), then whether w 2 or w S can be tested with finite sample complexity.
Let ai E AA } be an action for which lag.r + 0. We claim that:
Claim B.1. There exists a state Oj θ for which the agent weakly prefers action an over action
ao if the true posterior is state 01 with probability I and the agent has bias level т. In notation, let ca, E A()) be the vector whose th component and other components are O. The agent weakly prefers action an over action og under belief Tpo +1 (1-7)e8,
Proof. Suppose on the contrary that no such state 0, exists. Then the agent strietly prefers ag over aj under belief T4o + (1 T)ea for every state E e. This implies that, for any belief μ e A()),
22

---

the agent should also strictly prefer over under the belief TAO + (1 t)μ, due to linearity of the agent's s utility with respect to the belief. The agent strictly preferring an over dj implies 4/40 + (1 F & la so cannot be in lar by definition. This holds for any E A(O), so larr = 6, a contradiction.
Let 01 be the state in the above claim. The prior μo can be trivially written as the convex combination of ea, and eg for other states 0:
n40 = po(01)eo, +
Σ vo(0)eg-
0E
Since the agent does not prefer on under belief 7/40 + (1 -1- (1-T)e,,, the belief Tyo + (1 - -Tee, cannot be in the region Rag- The prior Ho is in the region Rag- Consider the line segment connecting co, and the prior An- There must exist point y² teg, + (1 f)1o on the line segment such that the r-biased belief THo + (1 T)y' lies exactly the boundary of Rao- Clearly, the prior can also be written as convex combination of p' and eg for E θ {(1}}:
Ho = p'u' +
Σ BE
Poea-
Then by the splitting lemma (Lemma 2.1), there exists a signaling scheme with [+] signals where signal induces posterior μí and the other signals induce posteriors {ealage) (+1)- (#))) In particular, the signal inducing μ' is boundary signal since 744 + (1 +)p E RR, by construction. By
Lemma 4.2, that signal useful for testing w 2 T or w I т. When that signal is sent (which happens with positive probability p' 0 at each time step). can tell finishes the proof.
This The two directions proved above together prove the parts 2 and 3 of Theorem 5.2.
C A More General Bias Model
We define a more general model of biased belief than the linear model. The agent's bias is captured by some function A()) x A(O) x [0, 1] A(O). Given prior Nu A(O), true posterior 1s, E (()), and bias level w E [0, 1]. the agent has biased belief 6(HO, Ma, w). The linear model is the special case where (6 Ma. w) wpo + w)Js. We make the following natural assumptions on d:
Assumption C.1.
d(Ho, Ma, 0) = ps (no bias), (po, Pa, 1) = po (full bias).
*(Ho: Ma, w) is continuous in (Ao May
We then make some joint assumptions on the bias model & and the agent's utility function U. Recall that the notation Ra {u A()) Va E A {ao), c, p > 0. the region of beliefs under which the agent strictly prefers action ag, ŌRa is the boundary of Ra,, and ext is the exterior of Ra, where the agent strictly not prefers ag.
Assumption C.2. When receiving no information, the agent will take the default action: Ypo A(O), Yuu E [0, 1]. (Pus Ho, Hu.w) E Ruc-
Definition C.1. We say that a posterior belief μ E A(O) satisfies single-crossing if the curve (á(Ho- u4 w) w [0, 1]} passes the boundary oRao only once: namely, there exists w [0, such that
Vi [0, w),
@uo, p., w) E ext Ragi
(po, n. w) E ÖRagi
Yu (w. 1], @po. p. w) E Rao
We assume that all posteriors outside Ru, satisfy cingle-roossing and all posteriors inside Rag do not cross the boundary when the bias level varies in [0, 1]: Assumption C.3.
23

---

Any P. & Rag satisfies single-crossing.
For any E Rag any w E [0, 11. 6fuo p. w) E Rao
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 Ia {ur E A c, ff 0} still be the set of beliefs where the agent is indifferent between actions and do- Let lar still be the set of posterior beliefs for which an agent with bias level T will be indifferent between a and ag, but with more general expression than the linear model:
Lar == {a E ((+) 6(HO, u4 T) E Loj.
With the above definition Ja 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 and Theorem 4.6) do not apply to the general bias model because linear. Designing an efficient algorithm to compute good signaling scheme to test bias in more general model is an interesting future direction.
24


Reviews:
[{"review_id": "pTpTmGriPs", "reviewer": "Reviewer_7Pvv", "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.", "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?\n\n- Can your algorithm be extended to scenarios with a multi-type receiver?\n\n- 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": "NA", "rating": 5, "confidence": 5, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "- The problem studied in this paper is of interest to the Bayesian Persuasion community.\n- The geometric characterization of the problem is interesting and clear, specifically the characterization of whether or not it is possible to learn the bias level presented in section 5.", "weaknesses": "- 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.\n\n- 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.\n\n- 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> 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. [...] 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?\n\nWe believe that we can effectively address this concern, and would be happy to add the discussion below to the paper. \n\nWe first note that our approach can be directly employed to estimate the bias up to an $\\epsilon$ error, by solving the threshold problem $\\log(1/\\epsilon)$ times, through binary search, as briefly mentioned in line 55. We will expand on this in the revised paper.\n\nLet us now explain why we did not include a confidence parameter, and why our results directly imply confidence bounds if one did want to include one. First, we note that unlike the standard PAC setting (where there is some underlying distribution), the only source of randomness in our problem is the signaling scheme. As we show, the optimal scheme maximizes the probability $p$ of obtaining useful signals. If that probability is $p$, the optimal scheme needs $1/p$ samples in expectation. You could ask instead about the number of samples $t$ needed for a success probability of $1-\\delta$, but given this discussion, the answer is straightforward: $(1-p)^t\\leq \\delta$, which is satisfied when $t \\ge \\frac{1}{p} \\log \\frac{1}{\\delta}$. \n\nIn other words, our current formulation implicitly provides confidence bounds, but we agree it would be valuable to make this more explicit. \n\n\n> 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.\n\nFor Theorem 3.1, we note that it's common to refer in a theorem statement to an algorithm that is defined previously, say \"Algorithm 1.\" In our case, we felt it would be awkward to put the signaling scheme on lines 158-161 in an environment (\"Signaling Scheme 3.1\") because it's so simple. However, we are open to doing so if it would improve readability.\n\nThe point about the Theorem 4.6 is more important as it may stem from a misunderstanding.  The final sample complexity of the optimal signaling is equal to $1/p^*$, where $p^*$ is the objective value of the linear program (Equation 6, Algorithm 1) and represents the probability of useful signals. This sample complexity depends on the geometry of the instance and lacks a simple closed-form solution. The main contribution of Theorem 4.6 — which builds on Lemmas 4.1-4.5 — is algorithmic. Section 4 as a whole demonstrates that the optimal signaling scheme can be computed efficiently. While Section 5 provides insights into the sample complexity (and Theorem 3.1 gives tight bounds for a special case), we emphasize that the general case where the sample complexity is finite but greater than 1 does not appear to have a more detailed, concise characterization.\n\n\n> Can your algorithm be extended to scenarios with a multi-type receiver?\n \nThe concept of a \"multi-type receiver\" could be interpreted in various ways.\n \nIf the sender knows the receiver's type in each round, we believe our results can be directly extended to this multi-type setting.\n\nHowever, if the sender does not know the receiver's type, we conjecture that testing the receiver's bias becomes impossible. The intuition is that if different types consistently take \"opposite\" actions, the receiver's observed action provides no information about their bias.\n\n> In the case of finite sample complexity, is it possible to achieve a better dependence with respect to $\\tau$, or are your results tight?\n\nOur results are tight for both the two-state-two-action case (Theorem 3.1) and the general case (Theorem 4.6), as they provide the optimal signaling schemes.", "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": "HVif5ETna0", "reviewer": "Reviewer_1o3u", "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$. \n\nThe 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$.", "questions": "See above", "limitations": "N/A", "rating": 7, "confidence": 5, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "In practice, it is widely observed that human belief updating with uncertainty is usually not following the Bayesian manner due to various biases and oftentimes such biases remain unknown to the system. Thus, it is natural to study how to detect such human bias and thus I think the motivation of this work is strong. The paper uses a novel approach via information design to detect human bias level. This, in addition, also opens up another application of information design/Bayesian persuasion. The paper also presents that using such approach is computationally efficient (for constant number of states and actions). \nThe paper is also well-written and results are stated in a clear way. Overall, I think this paper is a good addition to NeurIPS.", "weaknesses": "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).\n\nThere 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> There may be an immediate future direction is like given any $\\epsilon$, what is the sample complexity of narrowing down the unknown bias level $\\omega$ to be in an $\\epsilon$-interval? I feel $\\log \\frac{1}{\\epsilon}$ number of rounds using binary search should suffice (though you may need to carefully handle the randomness of realized signals).\n\nAbsolutely, we allude to this in line 55, but we will certainly elaborate on this point (which was brought up in some form by all reviewers) in the revision. \n\n> 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.\n\nThanks for the excellent pointer; this will strengthen our case for focusing on the linear model of bias (convex combination of prior and Bayesian posterior), which we currently support via references [8,10,5] in line 39.", "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": "GpoKgUDvnf", "reviewer": "Reviewer_rhkn", "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.", "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": "I don't see any limitations or potential negative societal impact of this work.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper is in general well-written and smooth to follow. The problem formulation and scheme design intuitions are nicely explained. The problem studied is novel. The proofs seem to be theoretically sound.", "weaknesses": "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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> 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.\n\nYour point is well taken that expanding our motivation would be beneficial, and we plan to do so in the revision.\n\nWe disagree with the specific criticism in your comment, however; in particular, we aren't sure what you have in mind when you refer to the \"optimal decision,\" as this is not part of our model. One way to motivate our setup is to view it as the initial interaction between a decision maker and an expert before any future solicitation of information from the expert for decisions of interest. The goal of this interaction — which can be structured as an artificial game, for example — is to estimate the expert's bias so that the expert's future opinions can be appropriately adjusted, improved or even discarded. This is conceptually analogous to the design of interactions to measure individual risk attitudes before giving subjects decision-making tasks, an approach common to economists and psychologists. Note that here the decision maker only has an informational advantage in the initial interaction.\n\nTo better connect our problem to polarization, we note that one can make a distinction between two sources of polarization [1]: two people can be exposed to different sources of information (e.g., news stories that reflect opposite positions), or they can be exposed to similar sources of information but reach different conclusions. Techniques for measuring bias in our sense may help disambiguate these two sources. For example, for two people who have very different world views, if we find that they have low levels of bias according to our definition, it would increase our confidence that they were exposed to different sources of information. \n\n[1] Nika Haghtalab, Matthew O. Jackson, Ariel D. Procaccia: Belief polarization in a complex world: A learning theory perspective. Proc. Natl. Acad. Sci. USA 118(19): e2010144118 (2021).\n\n> 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?\n\nOur approach can be directly employed to estimate the bias up to an $\\epsilon$ error, by solving the threshold problem $\\log(1/\\epsilon)$ times, through binary search. This requires adaptive signaling schemes and constant schemes are not sufficient. We mentioned this in line 55, but we will certainly elaborate on this point (which was brought up in some form by all reviewers) in the revision.", "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": "hLGavk2TMa", "reviewer": "Reviewer_NFob", "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.", "questions": "see weaknesses", "limitations": "yes", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper is well written and fairly easy to follow. Moreover it provides interesting answers to interesting questions. The answers goes trough geometrical characterisation and the paper helps build the intuition required for understanding the main results.", "weaknesses": "The main weakness in my opinion is the definition of the baseline and its poor understanding in the larger context of PAC learning. \nWhy 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> 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 than 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, $(\\epsilon, \\delta)$-PAC learning for best arm identification in multi-armed bandit has infinite sample complexity with $\\epsilon = 0$ even in trivial cases such as all the arms have the same mean.\n\nThis is an interesting point worth clarifying, but we disagree that it is a weakness and believe we can provide an effective rebuttal. \n\nWe first note that it isn't completely clear whether you're interested in the problem of testing whether $\\omega\\in [\\tau-\\epsilon,\\tau+\\epsilon]$ (in which case \"if\" and \"or\" should be replaced with \"and\") or the \"gap\" problem of testing if $\\omega \\le \\tau - \\epsilon$ or $\\omega \\ge \\tau + \\epsilon$ (in which case the inequalities are flipped). We assume you have the former problem in mind, as it is more consistent with the PAC setting. \n\nNext, the problem of testing whether $\\omega\\in [\\tau-\\epsilon,\\tau+\\epsilon]$ involves testing whether $\\omega\\leq \\tau+\\epsilon$ *and* $\\omega\\geq \\tau-\\epsilon$, that is, it is equivalent to two instances of the exact threshold problem. This may seem unintuitive, and you may wonder whether testing other thresholds in this interval might lead to better sample complexity; that is not the case, though, because the choice of bias level is adversarial (in the same way that testing a threshold $\\tau$ cannot be sped up by testing another threshold $\\tau'\\neq \\tau$).\n\nFinally, we argue that there is no reason to include a confidence parameter. Unlike standard PAC problems (where there is some underlying distribution), the only source of randomness in our problem is the signaling scheme. Recall, also, that we show that the optimal scheme simply maximizes the probability of useful signals. If that probability is $p$, the optimal scheme needs $1/p$ samples in expectation. You could ask instead about the number of samples $t$ needed for a success probability of $1-\\delta$, but given this discussion, the answer is clear: $(1-p)^t\\leq \\delta$, which is satisfied when $t \\ge \\frac{1}{p} \\log \\frac{1}{\\delta}$. \n\nYour PAC intuition may hold true if, analogously to a stochastic multi-armed bandit problem, the bias $\\omega$ is drawn from a distribution, but that's a fundamentally different model (in the same way that stochastic bandits are fundamentally different from adversarial bandits).", "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 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**.
Decision: Accept (poster)