Answer: Polynomial-time solvable in \(\tau\) and \(L\). Aggregate finite-negotiation attainment holds exactly when \(b_t\leq 1/8\) for every type \(t\).
Theorem 2 — class: other
Given rational masses \(\mu_t\) over a finite support of dispute-pair types, where type \(t\) specifies bias \(b_t\in(0,1/2)\) and the paper’s quadratic payoffs and uniform state \(\theta\in[0,1]\), compute typewise optimal arbitration and mediation rules and determine whether finite type-specific cheap-talk protocols attain the aggregate mediation value \(\sum_t\mu_t V_t^M\).
A society is given by its support: \(\tau\geq1\) publicly known dispute-pair types, each with positive binary rational mass \(\mu_t\), with \(\sum_t\mu_t=1\), and binary rational bias \(b_t\in(0,1/2)\). Types describe independent disputes; no communication, transfers, or constraints connect different pairs. Let \(L\) be the total input bit length; there is no candidate parameter \(m\).
For each type, the informed party observes \(\theta\sim\mathrm{Unif}[0,1]\); the decision-maker chooses \(y\in\mathbb R\). Their payoffs are respectively \(-(y-\theta-b_t)^2\) and \(-(y-\theta)^2\), with no transfers.
An arbitration rule is a measurable probability kernel \(K_t(dy\mid r)\), with finite second moments, for reports \(r\in[0,1]\). Truthful reporting must weakly maximize the informed party's expected payoff for every state; recommendations are binding. Mediation additionally requires \(\mathbb E[\theta\mid y]=y\) almost surely under truthful reporting. Each optimal rule maximizes \(V_t=-\int_0^1\int_{\mathbb R}(y-\theta)^2K_t(dy\mid\theta)\,d\theta\); denote the mediation optimum by \(V_t^M\).
A finite negotiation protocol permits arbitrary measurable message spaces and finitely many rounds of simultaneous messages, publicly revealed after each round, followed by the decision-maker's action. Attainment means existence of type-specific Bayesian–Nash equilibria whose mass-weighted value equals \(\sum_t\mu_tV_t^M\); finite refers to rounds, not message-space cardinality.
Computing rules means returning exact symbolic descriptions: finite programs with binary rational constants, arithmetic, comparisons, and integer indexing that specify the conditional action lotteries; indexed families need not be expanded.
Can typewise optimal arbitration and mediation rules be computed, and aggregate finite-negotiation attainment decided, in time polynomial in \(\tau\) and \(L\), or is this combined computational task NP-hard?
For a single dispute with a continuous state, optimal arbitration is known to be deterministic, and an explicit optimal mediation rule randomizes between two actions conditional on each state; its value is \(-b(1-b)/3\). Finite negotiation attains that value exactly when \(b\leq1/8\). These are structural results, rather than a discrete complexity classification or an analysis of binary-input running time. [Source](https://warwick.ac.uk/fac/soc/economics/staff/fsquintani/research/goltsman_horner_pavlov_squintani_jet.pdf)
Result. The combined task is polynomial-time solvable in \(\tau\) and \(L\), with the requested symbolic output convention. Aggregate finite-negotiation attainment holds exactly when \(b_t\leq 1/8\) for every type \(t\).
The main computational issue is that an optimal mediation rule can have exponentially many intervals. The construction below specifies them by integer indices, using only polynomially many bits.
1. Optimal arbitration.
Fix one type and write its bias as \(b\in(0,1/2)\). Return the deterministic kernel
\(K^A(dy\mid r)=\delta_{A(r)}(dy)\), where
\(A(r)=\min\{r+b,1-b\}\).
Theorem 1 of the cited paper establishes that this rule is optimal among all stochastic incentive-compatible arbitration rules. Its hypotheses match this problem: uniform state on \([0,1]\), quadratic preferences with constant positive bias, binding recommendations, and no transfers. [Goltsman, Hörner, Pavlov and Squintani, Theorem 1](https://warwick.ac.uk/fac/soc/economics/staff/fsquintani/research/goltsman_horner_pavlov_squintani_jet.pdf).
Incentive compatibility can also be checked directly. The available actions form the interval \([b,1-b]\). For state \(\theta\), truthful reporting selects the projection of the informed party’s preferred action \(\theta+b\) onto this interval. It therefore weakly minimizes the informed party’s squared loss over every report.
The kernel is measurable and bounded. Its value is
\(V^A=-b^2(1-2b)-\int_{1-2b}^{1}(1-b-\theta)^2\,d\theta=-b^2+4b^3/3\).
Its symbolic description requires only the rational constant \(b\), arithmetic, and a comparison.
2. An indexed optimal mediation rule.
We give a construction and prove its feasibility and optimality.
Let \(N\) be the least positive integer satisfying \(2bN^2\geq 1\). Because \(b<1/2\), we have \(N\geq 2\), and minimality gives
\(2b(N-1)^2<1\leq 2bN^2\).
Define
\(h=\bigl(1-2b(N-1)^2\bigr)/(2N-1)\)
and
\(\rho=h(2b-h)/\bigl((1-h)(1+h-2b)\bigr)\).
Define the thresholds by
\(x_0=0\) and
\(x_i=(2i-1)h+2b(i-1)^2\) for \(1\leq i\leq N\).
Define the actions by
\(a_i=2ih+b(2i^2-2i+1)\) for \(0\leq i<N\).
For a report \(r\), choose the unique index \(i\) with \(x_i\leq r<x_{i+1}\), assigning \(r=1\) to \(i=N-1\). Return
\(K^M(dy\mid r)=\rho\,\delta_b(dy)+(1-\rho)\,\delta_{a_i}(dy)\).
Here \(\delta_z\) denotes the probability measure concentrated at \(z\).
Validity of the parameters. The defining inequalities for \(N\) imply \(0<h\leq 2b<1\). Indeed, positivity follows from \(2b(N-1)^2<1\), while \(h\leq 2b\) is equivalent to \(1\leq 2bN^2\).
Consequently, the denominator \(D=(1-h)(1+h-2b)\) is positive and the numerator of \(\rho\) is nonnegative. Moreover,
\(D-h(2b-h)=1-2b>0\).
Thus \(0\leq\rho<1\).
The thresholds satisfy \(x_1=h>0\), \(x_N=1\), and, for \(1\leq i<N\),
\(x_{i+1}-x_i=2h+2b(2i-1)>0\).
They therefore partition the state interval into \(N\) intervals of positive length.
Incentive compatibility. We have \(a_0=b\) and
\(a_i-a_{i-1}=2h+4b(i-1)>0\) for \(1\leq i<N\).
Direct substitution also gives
\((a_{i-1}+a_i)/2=x_i+b\).
For state \(\theta\), the expected squared loss from choosing interval \(i\) is
\(\rho(b-\theta-b)^2+(1-\rho)(a_i-\theta-b)^2\).
The first term is independent of the report. Since \(1-\rho>0\), the informed party chooses the action \(a_i\) closest to \(\theta+b\). The equality
\((a_{i-1}+a_i)/2=x_i+b\)
places every indifference boundary exactly at \(\theta=x_i\). Because the actions are strictly increasing, these adjacent boundaries characterize a globally nearest action. Truthful reporting is therefore optimal at every state, including the boundaries, where the informed party is indifferent.
Obedience. For \(1\leq i<N\), substitution gives
\(a_i=(x_i+x_{i+1})/2>b\).
The recommendation \(a_i\) arises only from states in its corresponding interval, with constant probability \(1-\rho\). Conditional on this recommendation, the state is uniform on that interval, so
\(\mathbb E[\theta\mid y=a_i]=(x_i+x_{i+1})/2=a_i\).
Recommendation \(b\) occurs with probability one on \([0,h)\), because \(a_0=b\), and with probability \(\rho\) on \([h,1]\). Its total probability is \(h+\rho(1-h)>0\). Its state first moment is
\(h^2/2+\rho(1-h^2)/2\).
The definition of \(\rho\) is precisely the identity
\(h^2+\rho(1-h^2)=2b\bigl(h+\rho(1-h)\bigr)\).
Dividing by twice the recommendation’s probability yields
\(\mathbb E[\theta\mid y=b]=b\).
Thus obedience holds for every recommendation having positive probability. The kernel is measurable and has bounded support, hence finite second moments.
3. A self-contained proof of mediation optimality.
Consider any feasible mediation kernel for this bias. Define
\(a(\theta)=\mathbb E[y\mid\theta]\),
\(q(\theta)=\mathbb E[y^2\mid\theta]\), and
\(U(\theta)=-q(\theta)+2(\theta+b)a(\theta)-(\theta+b)^2\).
Here \(U(\theta)\) is the informed party’s truthful expected utility. Put
\(W(\theta)=U(\theta)+(\theta+b)^2\).
For \(s<\theta\), incentive compatibility in both directions gives
\(2(\theta-s)a(s)\leq W(\theta)-W(s)\leq 2(\theta-s)a(\theta)\).
These inequalities imply \(a(s)\leq a(\theta)\). Since the endpoint means are finite, \(a\) is bounded and monotone. Summing the inequalities over partitions and taking the limit of the upper and lower Riemann sums gives
\(W(\theta)-W(0)=2\int_0^\theta a(s)\,ds\).
Therefore,
\(U(\theta)=U(0)+2\int_0^\theta(a(s)-s-b)\,ds\).
These quantities are integrable: boundedness of \(a\) and \(W\), together with
\(q(\theta)=2(\theta+b)a(\theta)-W(\theta)\),
also bounds \(q\).
Let \(Q=\mathbb E[y^2]\) and let \(V\) denote the decision-maker’s value. Obedience implies
\(\mathbb E[y]=\mathbb E[\theta]=1/2\)
and
\(\mathbb E[\theta y]=\mathbb E[y^2]=Q\).
Hence \(V=Q-1/3\).
Expanding the informed party’s squared loss and using \(\mathbb E[y-\theta]=0\) gives
\(\int_0^1U(\theta)\,d\theta=V-b^2\).
On the other hand, integrating the envelope formula gives
\(\int_0^1U(\theta)\,d\theta
=U(0)+2\int_0^1(1-s)a(s)\,ds-1/3-b
=U(0)+2/3-b-2Q\).
Combining these identities yields
\(3V=U(0)-b(1-b)\).
Since utility is the negative of an expected square, \(U(0)\leq 0\). Thus every feasible mediation rule satisfies
\(V\leq-b(1-b)/3\).
In the constructed rule, state zero receives action \(b\) with probability one. Its preferred action is also \(b\), so \(U(0)=0\). The rule attains the bound and is therefore optimal:
\(V^M=-b(1-b)/3\).
4. Binary-input running time.
Write \(b=p/q\), with positive integers \(p,q\), and let \(\ell\) be their total binary encoding length.
Compute \(N\) by binary search for the least integer satisfying \(2pN^2\geq q\). The interval \([1,q]\) contains such an integer, since \(2pq^2\geq q\). Binary search uses \(O(\log q)\) comparisons, each involving integers of \(O(\ell)\) bits. Thus \(N\) is computable in polynomial bit time and itself has \(O(\ell)\) bits.
The formulas for \(h\) and \(\rho\) use a fixed number of rational arithmetic operations on quantities of \(O(\ell)\) bits. Both rational constants consequently have polynomial encoding length.
The output program stores \(b,N,h,\rho\), evaluates the indexed formulas for \(x_i\) and \(a_i\), and finds the report’s interval by binary search. It uses only the permitted arithmetic, comparisons, and integer indexing. It does not enumerate the intervals.
This distinction is essential. For example, when \(b=2^{-2k-1}\), the construction has \(N=2^k\) intervals, although the input and indexed description have size \(O(k)\). The requested output convention accommodates this exponential interval count.
Applying the construction separately to all \(\tau\) types therefore takes polynomial time in \(\tau\) and \(L\), and produces polynomial total output length.
5. Aggregate finite-negotiation attainment.
We use the stipulated single-dispute characterization: on \(0<b<1/2\), finite negotiation attains the mediation value exactly when \(b\leq1/8\). The cited paper’s negotiation model uses finitely many simultaneous public-message rounds and Bayesian–Nash equilibrium, matching the task. Its revelation-principle comparison also bounds every negotiation equilibrium’s value by the mediation optimum. [Goltsman, Hörner, Pavlov and Squintani, Section 2 and Theorem 3](https://warwick.ac.uk/fac/soc/economics/staff/fsquintani/research/goltsman_horner_pavlov_squintani_jet.pdf).
Let \(W_t\) be the value achieved by a chosen finite-negotiation equilibrium for type \(t\). Then \(W_t\leq V_t^M\). Because every mass is positive,
\(\sum_t\mu_tW_t=\sum_t\mu_tV_t^M\)
holds if and only if \(W_t=V_t^M\) for every \(t\): all terms
\(\mu_t(V_t^M-W_t)\) are nonnegative, and their sum can vanish only when each vanishes.
Necessity therefore requires \(b_t\leq1/8\) for every type. Conversely, if all these inequalities hold, choose a finite attaining equilibrium for each independent type. Their weighted value is the target value. If a common round bound is needed, take the maximum of their finitely many round counts and pad shorter protocols with dummy messages.
The decision algorithm is consequently just the conjunction of the exact rational comparisons \(b_t\leq1/8\). These comparisons take polynomial bit time. The aggregate optimum, if desired, is the exactly computable rational number
\(-\frac13\sum_t\mu_tb_t(1-b_t)\).
Thus both rule construction and attainment decision admit polynomial-time algorithms. A classification of this task as NP-hard under standard polynomial-time reductions would consequently imply \(\mathrm P=\mathrm{NP}\).
⟨structured verdict parsed — rendered above⟩
Verdict: proved. The output resolves all parts of the assigned task. The rule constructions, optimality argument, binary-input complexity analysis, and aggregate attainment criterion are correct. I found no major or minor issues requiring repair.
The cited Theorem 1, restricted to \(0<b<1/2\), gives precisely the deterministic action \(A(r)=\min\{r+b,1-b\}\). Its model and incentive constraints match the task, and its optimality comparison includes stochastic rules. [Source, Theorem 1](https://warwick.ac.uk/fac/soc/economics/staff/fsquintani/research/goltsman_horner_pavlov_squintani_jet.pdf).
The direct incentive-compatibility check is valid: the report-induced action set is \([b,1-b]\), and truthful reporting selects the closest available action to \(\theta+b\). This holds at both endpoints and at the cap threshold.
The value calculation is correct. The tail integral equals \(2b^3/3\), yielding \(V^A=-b^2+4b^3/3\). Measurability, finite second moments, and the permitted symbolic representation are established.
The least-integer definition of \(N\) is well posed. Since \(2b<1\), it gives \(N\geq2\), with exactly the stated inequalities.
The deductions \(0<h\leq2b<1\) are correct. Both denominator factors defining \(\rho\) are positive, and the identity
\(D-h(2b-h)=1-2b>0\)
correctly establishes \(0\leq\rho<1\).
Substitution verifies \(x_N=1\), and the stated threshold differences are positive. Thus every report receives a well-defined index, including the separately assigned report \(r=1\).
The boundary case \(2bN^2=1\) causes no failure: the formulas give \(h=2b\) and \(\rho=0\). All intervals still have positive length.
Both action identities are correct:
\(a_i-a_{i-1}=2h+4b(i-1)>0\) and
\((a_{i-1}+a_i)/2=x_i+b\).
The expected-loss expression correctly separates a report-independent term from the squared distance to \(a_i\), multiplied by the positive constant \(1-\rho\).
For strictly ordered actions, their adjacent midpoints determine the globally closest action. The displayed midpoint identity therefore verifies truthful optimality at every state. At threshold states, either adjacent report interval is optimal; the specified boundary convention is valid.
For every \(i\geq1\), the identity
\(a_i=(x_i+x_{i+1})/2>b\)
is correct. These actions are distinct and can arise only from their corresponding intervals. Constant selection probability on each interval gives the claimed uniform conditional state distribution.
For recommendation \(b\), the probability and unnormalized first moment are correctly computed, including the fact that both lottery components coincide on the first interval.
The identity used to establish its posterior mean is algebraically equivalent to the definition of \(\rho\). Its conditioning probability is strictly positive because \(h>0\). The obedience argument remains valid when \(\rho=0\).
The resulting kernel is measurable and has finite, bounded support for each input bias.
The two incentive inequalities have the correct directions. Together they imply that \(a\) is nondecreasing. Finite second moments at every report imply finite endpoint means, so monotonicity bounds \(a\) throughout the interval.
The partition argument legitimately sandwiches the increments of \(W\) between lower and upper Riemann sums. A bounded monotone function is Riemann integrable, so the claimed envelope identity follows, including at endpoints.
The subsequent boundedness and integrability claims are justified: the envelope identity bounds \(W\), and the displayed relation for \(q\) then bounds \(q\). Thus the later integrations and exchanges of integration are legitimate.
Obedience correctly gives
\(\mathbb E[y]=1/2\) and
\(\mathbb E[\theta y]=\mathbb E[y^2]=Q\).
Consequently, \(V=Q-1/3\).
Both expressions for integrated informed-party utility check out:
\(\int_0^1U(\theta)\,d\theta=V-b^2\) and
\(\int_0^1U(\theta)\,d\theta=U(0)+2/3-b-2Q\).
Combining them indeed yields \(3V=U(0)-b(1-b)\). Since \(U(0)\leq0\), the upper bound follows. The constructed rule assigns action \(b\) surely at state zero, attaining \(U(0)=0\), so its optimality is established.
The search interval \([1,q]\) contains \(N\), and the predicate \(2pN^2\geq q\) is monotone. Binary search requires \(O(\log q)\) comparisons on integers with \(O(\ell)\) bits.
The fixed number of rational operations defining \(h\) and \(\rho\) preserves polynomial encoding length. No irrational constants or root extraction are required.
The indexed program describes every interval and conditional lottery without enumeration. Binary search for a report’s interval is compatible with the permitted arithmetic, comparisons, and integer indexing. The construction-time claim does not require a finite binary encoding for every possible real report.
The example \(b=2^{-2k-1}\), giving \(N=2^k\), is correct and explains why the output convention matters. Summing construction costs and description lengths over the input types remains polynomial in \(\tau\) and \(L\).
The cited negotiation model uses simultaneous messages revealed after each round, a final decision-maker action, and Bayesian–Nash equilibrium. Finite means finitely many rounds. The threshold characterization includes equality at \(b=1/8\), and the source also states the mediation upper bound for negotiation outcomes. These match the invoked structural results. [Source, Sections 2 and 5](https://warwick.ac.uk/fac/soc/economics/staff/fsquintani/research/goltsman_horner_pavlov_squintani_jet.pdf).
Given \(W_t\leq V_t^M\), positivity of every mass makes the aggregate equality equivalent to equality for every type. The argument correctly excludes compensation across types.
Independence permits selection of an attaining protocol for each eligible type. Because there are finitely many types, taking the maximum round count and padding shorter protocols is valid.
Exact rational threshold comparisons decide attainment in polynomial time. The optional aggregate-value formula is also correct. The closing statement about NP-hardness appropriately retains the qualification that such hardness would imply \(\mathrm P=\mathrm{NP}\).
Required clarification or repair: none.
⟨structured verdict parsed — rendered above⟩
Tier: machine-proved, adversarially reviewed by an independent model. No human has checked this proof. Generated from pipeline artifacts by tools/atlas_build.py.