Answer: Exact maximization is solvable in time polynomial in \(m,\tau,d,k,L\), with unrestricted \(d\). An optimal obedient assignment uses at most \(k\) active messages and at most \(k\tau\) nonzero entries.
Theorem 3 — class: algorithmic
Given a rational distribution \(\mu_A\) over episode types \(a\), where each type specifies its conditional law of \((B,E)\), and a \(k\)-piecewise-linear convex score function \(G\), choose message-assignment masses \(x_{a,s}\geq 0\) satisfying \(\sum_s x_{a,s}=\mu_A(a)\). Use recommendation messages \(s=(i_0,(i_b)_{b\in\mathcal B})\), with each recommendation obedient for the posterior induced by positive mass on \(s\), both before and after each Bob signal \(b\). Compute a feasible assignment maximizing the per-episode sender objective \(J(x)=\sum_s[q_sG(p_s)-\sum_b q_{s,b}G(p_{s,b})]\), where \(q_s=\sum_a x_{a,s}\), \(q_{s,b}=\sum_a x_{a,s}\Pr(b\mid a)\), and \(p_s,p_{s,b}\) are the corresponding event posteriors. Theorem 3 gives a polynomial-time algorithm in \(k^{|\mathcal B|},|\mathcal A|,|\mathcal E|\).
A society is given by its support: the list of \(\tau=|\mathcal A|\) episode types with positive binary-rational masses \(\mu_A(a)\), summing to \(1\); \(\tau\) is the support size, not the number of possible types.
Let \(\mathcal E,\mathcal B\) be nonempty finite sets, with \(m=|\mathcal E|\) and \(d=|\mathcal B|\). Each type supplies an explicit rational probability table \(h_a(b,e)=\Pr(B=b,E=e\mid A=a)\).
The score is specified by a rational matrix \(U\in\mathbb Q^{k\times m}\), with \(k\geq1\), defining \(G(p)=\max_{i\in[k]}\sum_e U(i,e)p(e)\) on \(\Delta(\mathcal E)\); coefficients may have either sign. Let \(L\) be the total input bit length.
Messages are \(s=(i_0,(i_b)_{b\in\mathcal B})\in\mathcal S=[k]^{d+1}\). Choose divisible masses \(x_{a,s}\geq0\) with \(\sum_s x_{a,s}=\mu_A(a)\); message selection depends only on \(a\).
Define \(z_{s,b,e}=\sum_a x_{a,s}h_a(b,e)\), \(q_{s,b}=\sum_e z_{s,b,e}\), and \(q_s=\sum_b q_{s,b}\). At positive denominators, set \(p_{s,b}(e)=z_{s,b,e}/q_{s,b}\) and \(p_s(e)=\sum_b z_{s,b,e}/q_s\).
Obedience requires \(i_0\in\arg\max_i\sum_e U(i,e)p_s(e)\) whenever \(q_s>0\), and \(i_b\in\arg\max_i\sum_e U(i,e)p_{s,b}(e)\) whenever \(q_{s,b}>0\). Any maximizing recommendation is permitted in a tie; zero-mass histories impose no condition.
Maximize \(J(x)=\sum_s[q_sG(p_s)-\sum_b q_{s,b}G(p_{s,b})]\), interpreting zero-mass terms as zero. An assignment is represented by its nonzero entries.
Is exact maximization of \(J\) solvable in time polynomial in \(m,\tau,d,k,L\), or is it NP-hard, with \(d\) unrestricted?
Known results: finite-signal commitment admits an exact \(\operatorname{poly}(k^d,\tau,m)\)-time algorithm, hence polynomial time for fixed \(d\). [Source](https://arxiv.org/html/2009.03607).
That model already permits arbitrary divisible joint message/type probabilities, so the same bound covers this mass formulation; it does not establish polynomial time when \(d\) varies. No source located settles the unrestricted target.
Exact maximization is solvable in time polynomial in \(m,\tau,d,k,L\), even when \(d\) is unrestricted. An optimal obedient assignment can be returned with at most \(k\) active messages and at most \(k\tau\) nonzero entries.
The key is that messages with the same initial recommendation can be merged without decreasing the objective. Their recommendations after observing \(B\) can then be chosen anew.
For \(a\in\mathcal A\), \(b\in\mathcal B\), and \(j\in[k]\), define rational coefficients
\(r_{b,j,a}:=\sum_{e\in\mathcal E}U(j,e)h_a(b,e)\), and \(c_{j,a}:=\sum_{b\in\mathcal B}r_{b,j,a}\).
For a nonnegative mass vector \(v=(v_a)_{a\in\mathcal A}\), define
\(R_{b,j}(v):=\sum_a r_{b,j,a}v_a\), and \(R_j(v):=\sum_a c_{j,a}v_a=\sum_bR_{b,j}(v)\).
Also define
\(H_b(v):=\max_{j\in[k]}R_{b,j}(v)\), and \(H(v):=\max_{j\in[k]}R_j(v)\).
For a message \(s\), put \(v^s_a=x_{a,s}\). Since each \(h_a\) is a probability table, \(q_s=\sum_a v^s_a\). At positive denominators, direct substitution gives
\(q_sG(p_s)=H(v^s)\), and \(q_{s,b}G(p_{s,b})=H_b(v^s)\).
These identities also hold under the stipulated zero-mass convention. Indeed, if \(q_{s,b}=0\), nonnegativity implies \(z_{s,b,e}=0\) for every \(e\), so every \(R_{b,j}(v^s)\) is zero. If \(q_s=0\), then \(v^s=0\).
Consequently,
\(J(x)=\sum_s F(v^s)\), where \(F(v):=H(v)-\sum_bH_b(v)\).
Initial obedience for recommendation \(i\) is exactly
\(R_i(v)\geq R_j(v)\quad\text{for every }j\in[k]\).
When the message has zero mass, these inequalities hold automatically. The analogous statement applies to subsequent obedience using \(R_{b,j}\).
Lemma. Let \(v^1,\ldots,v^t\) be nonnegative mass vectors for which the same initial recommendation \(i\) is obedient. Then their sum \(w:=\sum_{\ell=1}^t v^\ell\) also admits initial recommendation \(i\), and
\(F(w)\geq\sum_{\ell=1}^tF(v^\ell)\).
Proof. For every \(j\), linearity gives
\(R_i(w)-R_j(w)=\sum_{\ell=1}^t\bigl(R_i(v^\ell)-R_j(v^\ell)\bigr)\geq0\).
Thus \(H(w)=R_i(w)\), while \(H(v^\ell)=R_i(v^\ell)\) for each \(\ell\).
For every \(b\),
\(H_b(w)=\max_j\sum_{\ell=1}^tR_{b,j}(v^\ell)\leq\sum_{\ell=1}^t\max_jR_{b,j}(v^\ell)=\sum_{\ell=1}^tH_b(v^\ell)\).
Subtracting these inequalities from the additive initial score yields
\(F(w)=R_i(w)-\sum_bH_b(w)\geq\sum_{\ell=1}^t\left(R_i(v^\ell)-\sum_bH_b(v^\ell)\right)=\sum_{\ell=1}^tF(v^\ell)\).
No sign restriction on \(U\) is used. \(\square\)
Apply the lemma to all messages having a given initial recommendation \(i\). Define their merged masses by
\(y_{a,i}:=\sum_{s:\,i_0(s)=i}x_{a,s}\), and write \(y^i=(y_{a,i})_a\).
For every retained merged vector, choose
\(j_{i,b}\in\arg\max_{j\in[k]}R_{b,j}(y^i)\).
The merged vector can be assigned to the permitted message
\(s_i=(i,(j_{i,b})_{b\in\mathcal B})\in[k]^{d+1}\).
Initial obedience follows from the lemma; subsequent obedience follows from the choice of \(j_{i,b}\). Ties are permitted, and zero-mass histories impose no obstacle. Messages belonging to different \(i\) are distinct because their initial recommendations differ.
Mass conservation is preserved, and the objective does not decrease. Therefore it suffices to optimize over one mass vector for each of the \(k\) possible initial recommendations.
Introduce nonnegative variables \(y_{a,i}\) and real variables \(t_{i,b}\). The latter will represent \(H_b(y^i)\).
Let \(M:=\max_{j,e}|U(j,e)|\). Consider the following linear program.
Maximize
\(\displaystyle \sum_{i\in[k]}\sum_{a\in\mathcal A}c_{i,a}y_{a,i}-\sum_{i\in[k]}\sum_{b\in\mathcal B}t_{i,b}\),
subject to:
\(\sum_{i\in[k]}y_{a,i}=\mu_A(a)\) for every \(a\in\mathcal A\).
\(y_{a,i}\geq0\) for every \(a,i\).
\(\sum_a(c_{i,a}-c_{j,a})y_{a,i}\geq0\) for every \(i,j\in[k]\).
\(t_{i,b}\geq\sum_a r_{b,j,a}y_{a,i}\) for every \(i,b,j\).
\(-M\leq t_{i,b}\leq M\) for every \(i,b\).
The variables \(t_{i,b}\) must be allowed to be negative because \(U\) may have negative coefficients.
The finite bounds exclude no intended solution. For any mass-conserving \(y\), define \(z^i_{b,e}:=\sum_a y_{a,i}h_a(b,e)\). Then
\(\left|R_{b,j}(y^i)\right|=\left|\sum_eU(j,e)z^i_{b,e}\right|\leq M\sum_ez^i_{b,e}\leq M\),
because the total mass of \(y^i\) is at most \(1\). Thus \(H_b(y^i)\in[-M,M]\).
The program is nonempty: choose an initial action maximizing \(R_j(\mu_A)\), assign all masses to that action, and set the corresponding \(t\)-variables to their maxima. Set all other mass vectors and their \(t\)-variables to zero. Its feasible set is closed and bounded, so an optimum exists.
At every optimum,
\(t_{i,b}=H_b(y^i)\).
Otherwise, lowering an excessive \(t_{i,b}\) to \(H_b(y^i)\) preserves every constraint and strictly increases the objective. Initial obedience also ensures \(R_i(y^i)=H(y^i)\). Hence the optimal objective is exactly \(\sum_iF(y^i)\).
Let \(V\) denote the original optimal value and \(V_{\mathrm{LP}}\) the linear-program optimal value.
For every original obedient assignment, merging as above gives feasible LP masses \(y\) with
\(\sum_iF(y^i)\geq J(x)\).
Setting \(t_{i,b}=H_b(y^i)\) therefore proves \(V_{\mathrm{LP}}\geq V\).
Conversely, take an optimal LP solution. For every \(i\) with \(\sum_a y_{a,i}>0\), choose the maximizing recommendations \(j_{i,b}\) and construct \(s_i\) as above. Set
\(x_{a,s_i}:=y_{a,i}\),
and set every other entry to zero. This assignment conserves every type’s mass and satisfies all obedience conditions. Its objective equals the LP objective, proving \(V\geq V_{\mathrm{LP}}\).
Therefore \(V=V_{\mathrm{LP}}\), and the construction returns an optimal original assignment.
The LP has \(k\tau+kd\) variables and
\(O(\tau+k\tau+k^2+k^2d+kd)\)
constraints. Computing all \(r_{b,j,a}\) and \(c_{j,a}\) requires polynomially many exact rational operations, and their bit lengths are polynomial in the input bit length. Thus the LP’s complete encoding has polynomial size in \(m,\tau,d,k,L\).
The standard exact rational linear-programming theorem gives a polynomial-time algorithm for an explicitly encoded rational LP, including an optimal rational solution of polynomial bit length when a finite optimum exists. Here the hypotheses hold: the LP is rational, nonempty, and bounded.
Recovering each \(j_{i,b}\) requires comparing only \(k\) rational scores. The resulting assignment contains at most \(k\) messages and \(k\tau\) nonzero entries, with polynomial encoding length.
The cited [Theorem 4.2](https://arxiv.org/html/2009.03607) gives an algorithm exponential in \(d\). The merging lemma above establishes a polynomial bound for the precise objective and obedience rules in this question.
⟨structured verdict parsed — rendered above⟩
The proof is correct and resolves the unrestricted problem. It establishes an exact polynomial-time algorithm in \(m,\tau,d,k,L\), returning an optimal obedient assignment with at most \(k\) active messages and at most \(k\tau\) nonzero entries.
I found no major or minor mathematical issues. The argument uses the stated freedom to merge messages and choose their subsequent recommendations anew.
The coefficients \(r_{b,j,a}\) and \(c_{j,a}\) correctly express the unnormalized subsequent and initial scores.
Because every \(h_a\) is a probability table, the identity \(q_s=\sum_a v^s_a\) is valid. At positive denominators, multiplying each posterior score by its denominator gives exactly \(R_j(v^s)\) or \(R_{b,j}(v^s)\). Taking maxima therefore gives the asserted identities involving \(H\) and \(H_b\).
The zero-denominator arguments are also correct:
Thus the expression \(J(x)=\sum_s F(v^s)\) holds everywhere, including zero-mass histories.
Multiplying obedience inequalities by a positive denominator preserves their direction. At zero mass, the corresponding unnormalized scores are all zero, so the inequalities impose no additional restriction. The claimed linear characterization of obedience is exact.
Both parts of the lemma are justified.
First, summing the initial obedience inequalities preserves them, so the common initial recommendation \(i\) remains maximizing for the merged vector.
Second, for every \(b\), the displayed inequality
\(\max_j\sum_\ell R_{b,j}(v^\ell)\leq\sum_\ell\max_jR_{b,j}(v^\ell)\)
is valid: every individual summand is bounded above by its corresponding maximum. This remains true when scores are negative.
Since the initial score is additive on vectors sharing the maximizing recommendation \(i\), subtracting the subsequent-score inequality gives the claimed direction \(F(w)\geq\sum_\ell F(v^\ell)\).
The subsequent recommendations need not survive merging. The proof explicitly chooses new maximizing recommendations, which the task permits. This is essential and correctly handled.
Grouping by initial recommendation preserves every type’s mass. The recovered messages for distinct initial recommendations are distinct. Consequently, the reduction to at most \(k\) active messages is valid.
The LP correctly models the reduced optimization:
The finite bounds are valid. Nonnegativity and mass conservation imply that each \(y^i\) has total mass at most \(1\). The supplied calculation therefore establishes \(\lvert R_{b,j}(y^i)\rvert\leq M\), and hence \(H_b(y^i)\in[-M,M]\).
Allowing negative \(t_{i,b}\) correctly accommodates signed coefficients in \(U\). The bounds also work when \(M=0\).
The proposed feasible point satisfies every constraint: the selected initial recommendation maximizes the aggregate initial score, and unused initial recommendations receive zero vectors and zero subsequent scores.
The feasible set is closed and bounded. Lowering an excessive \(t_{i,b}\) to \(H_b(y^i)\) preserves all constraints, including the finite bounds, and strictly improves the objective. Thus the claimed equality at every optimum follows.
Both value comparisons are correct.
An original obedient assignment can be merged into feasible LP masses with an objective at least as large. Setting the auxiliary variables to the actual subsequent maxima gives \(V_{\mathrm{LP}}\geq V\).
Conversely, the optimal LP masses determine messages whose initial and subsequent recommendations satisfy obedience. Assigning \(x_{a,s_i}=y_{a,i}\) preserves mass conservation, and the denominator-free identities establish equality of the recovered assignment’s objective with the LP objective. Therefore \(V\geq V_{\mathrm{LP}}\).
There is no message collision between different retained indices \(i\), and omitting zero-total-mass vectors loses no allocated mass. This establishes exact equivalence and attainment of the original optimum.
The variable count \(k\tau+kd\) and the stated constraint count are correct. In particular, the subsequent-score inequalities contribute \(k^2d\) constraints; no enumeration of \(k^{d+1}\) messages occurs.
The coefficient computations involve polynomially many rational sums and products. Their bit lengths remain polynomial in the explicit input length, so the complete LP encoding has polynomial size.
The stated exact rational LP theorem applies: the program is explicitly encoded, rational, nonempty, and bounded. Its use to obtain an exact optimal rational solution of polynomial encoding length is justified.
Recovery requires only polynomially many rational score computations and comparisons. Each active message contains \(d+1\) recommendation indices, and the assignment has at most \(k\tau\) nonzero masses. The claimed polynomial output encoding follows.
The argument covers unrestricted \(d\), signed scores, ties, zero-probability subsequent histories, and the boundary cases \(k=1\) and \(M=0\). It uses \(\tau\) as the explicitly listed support size.
The description of the previously known bound agrees with [Theorem 4.2 of the cited paper](https://arxiv.org/html/2009.03607#S4.Thmtheorem4.2), which states a runtime polynomial in \(k^{|\mathcal B|},|\mathcal A|,|\mathcal E|\). The new proof does not rely on that theorem to establish its polynomial bound.
No repair or additional clarification is required. The merging lemma, LP formulation, recovery procedure, and exact bit complexity argument establish the claimed result.
⟨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.