Answer: Polynomial-time solvable in \(O(\tau m d^2 L^2)\) bit operations.
Lemma 9 — class: algorithmic
Given a common set of attributes, domains, and rooted tree, a support \(T\) of utility types with explicit local utility tables \(u_t\), and rational masses \(\mu_t\) summing to \(1\), compute a shared outcome \(\theta^\star \in \arg\max_{\theta \in \Theta} \sum_{t \in T} \mu_t u_t(\theta)\).
Let \(\Gamma=\{a_1,\ldots,a_m\}\), with \(m\geq1\), have explicitly listed, finite, nonempty domains \(D_i\); outcomes are \(\Theta=\prod_i D_i\). A common rooted tree on these attributes is directed away from its root \(a_\rho\), with parent index \(p(i)\) for each nonroot attribute.
A society is given by its support: the list \(T\) of the \(\tau\) types with positive mass, each mass \(\mu_t\) a binary rational, with \(\sum_t\mu_t=1\). Here \(\tau\) is the support size, not the number of possible types.
Each type supplies a reference assignment \(r_t\in\Theta\), a root table \(f_{t,\rho}:D_\rho\to\mathbb Q\), and conditional utility tables \(f_{t,i}:D_i\times D_{p(i)}\to\mathbb Q\), satisfying \(f_{t,i}(r_{t,i},y)=0\) for every parent value \(y\). All entries are explicitly given finite signed binary rationals.
Its utility is \(u_t(\theta)=f_{t,\rho}(\theta_\rho)+\sum_{i\ne\rho}f_{t,i}(\theta_i,\theta_{p(i)})\). The supplied utility scales are used without rescaling. Compute any shared outcome \(\theta^\star\in\arg\max_{\theta\in\Theta}\sum_{t\in T}\mu_tu_t(\theta)\); there are no additional feasibility constraints.
Let \(d=\max_i|D_i|\) and let \(L\) be the total binary input length. State running times in \(m,\tau,d,L\).
Is exact shared-outcome maximization for this support-and-mass model solvable in polynomial time in \(m,\tau,d,L\), or is it NP-hard?
For a single utility represented on a rooted tree, an exact tree-message algorithm computes the maximum and recovers a maximizing assignment in polynomial time in the explicit table size. This established result concerns one utility, rather than the support-and-mass objective above.
Exact shared-outcome maximization is polynomial-time solvable. A maximizing outcome can be computed in \(O(\tau m d^2 L^2)\) bit operations using ordinary integer arithmetic.
The crucial fact is that all types use the same attribute tree. Their weighted sum therefore retains a decomposition into a root potential and potentials on the tree’s edges.
Let \(C(i)\) denote the children of attribute \(a_i\). Define
\(g_\rho(x)=\sum_{t\in T}\mu_t f_{t,\rho}(x)\)
and, for each nonroot attribute,
\(g_i(x,y)=\sum_{t\in T}\mu_t f_{t,i}(x,y).\)
Distributing the finite sums gives, for every outcome \(\theta\),
\(F(\theta):=\sum_{t\in T}\mu_tu_t(\theta) =g_\rho(\theta_\rho)+\sum_{i\ne\rho}g_i(\theta_i,\theta_{p(i)}).\)
Thus the aggregate objective has the same tree structure.
The aggregated tables need not satisfy the reference-assignment normalization for any common reference assignment. This causes no difficulty: the algorithm below works for arbitrary finite signed root and edge potentials. It does not use the normalization condition.
For a nonroot attribute \(a_i\), let \(S_i\) be the set of indices in its subtree, including \(i\). For each \(y\in D_{p(i)}\), define
\(M_i(y)= \max_{\theta_{S_i}\in\prod_{j\in S_i}D_j} \left[ g_i(\theta_i,y) +\sum_{j\in S_i\setminus\{i\}} g_j(\theta_j,\theta_{p(j)}) \right].\)
Every maximum exists because its domain is finite and nonempty.
Compute these messages from the leaves toward the root, using
\(M_i(y)=\max_{x\in D_i} \left[g_i(x,y)+\sum_{j\in C(i)}M_j(x)\right].\)
For each \(y\), store one maximizing value \(b_i(y)\in D_i\). Empty sums are zero.
At the root, compute
\(V=\max_{x\in D_\rho} \left[g_\rho(x)+\sum_{j\in C(\rho)}M_j(x)\right]\)
and store one maximizing value \(x_\rho^\star\). Recover the outcome by setting \(\theta_\rho^\star=x_\rho^\star\) and, proceeding away from the root, setting
\(\theta_i^\star=b_i(\theta_{p(i)}^\star).\)
We prove the message recurrence by induction on subtree size.
For a leaf \(i\), its subtree contains only \(i\), so the message definition is exactly \(M_i(y)=\max_{x\in D_i}g_i(x,y)\).
Now suppose the messages of every child of \(i\) satisfy their definitions. Fix the parent value \(y\) and the value \(x\) at \(i\). The subtree objective splits into \(g_i(x,y)\) and one contribution from each child subtree.
These child subtrees have disjoint variables. Because the common graph is a tree, no potential joins two different child subtrees. Because there are no additional feasibility constraints, any independently chosen child-subtree assignments can be combined with the fixed value \(x\). Consequently, the maximum for fixed \(x,y\) equals
\(g_i(x,y)+\sum_{j\in C(i)}M_j(x).\)
Maximizing over \(x\) proves the recurrence.
The same argument at the root proves \(V=\max_{\theta\in\Theta}F(\theta)\). Each stored choice attains its corresponding message maximum. Recursively combining these choices therefore produces an outcome satisfying \(F(\theta^\star)=V\).
This also covers \(m=1\): only the root maximization remains.
Let
\(E=|D_\rho|+\sum_{i\ne\rho}|D_i||D_{p(i)}|.\)
There are \(E\) utility-table entries per type, and \(E\le md^2\).
To implement all calculations exactly, write every input rational with an integer numerator and a positive integer denominator. Let \(Q\) be the product of all denominators occurring in the masses and utility tables.
For any mass \(\mu_t=n_t/b_t\) and table entry \(f=c/e\), the product \(b_te\) divides \(Q\): the two denominator occurrences are included separately in that product. Hence
\(Q\mu_tf=n_tc\,\frac{Q}{b_te}\)
is an integer. Form the integer potentials \(H_\rho=Qg_\rho\) and \(H_i=Qg_i\), and run the message algorithm on these potentials. Since \(Q>0\), scaling preserves every maximizing assignment.
We now bound the integer sizes.
Constructing \(Q\) takes \(O(L^2)\) bit operations with schoolbook multiplication. Computing each scaled weighted entry takes \(O(L^2)\) bit operations, including exact division. Aggregating the tables therefore takes \(O(\tau E L^2)\) bit operations.
For the message phase, first compute \(\sum_{j\in C(i)}M_j(x)\) once for each \(x\in D_i\), then examine each table entry. This requires \(O(md+E)=O(md^2)\) integer additions and comparisons, each costing \(O(L)\) bit operations. Reconstruction takes \(O(m)\) stored-choice lookups.
The total bound is therefore
\(O\!\left(L^2+\tau E L^2+md^2L\right) =O(\tau m d^2L^2).\)
Thus the support-and-mass objective is tractable: aggregating the explicitly listed types preserves the common tree decomposition.
⟨structured verdict parsed — rendered above⟩
The output fully resolves the task. The aggregation, dynamic program, reconstruction, and exact-arithmetic bound are correct. No major or minor issues were found.
The definitions of \(g_\rho\) and \(g_i\) use the supplied masses and utility scales directly. Distributing the finite sums correctly gives
\[
F(\theta)=g_\rho(\theta_\rho)+\sum_{i\ne\rho}g_i(\theta_i,\theta_{p(i)}).
\]
All types use the same rooted tree, so aggregation introduces no additional interactions. This addresses the support-and-mass objective itself, rather than merely invoking the established algorithm for one utility.
The observation about reference normalization is also correct: the aggregated potentials need not admit a common reference assignment, but the algorithm and its proof impose no such requirement.
For each nonroot vertex, the definition of \(M_i(y)\) includes exactly the potentials belonging to its subtree, with its parent value fixed to \(y\). Every other parent appearing inside that definition belongs to the subtree, so all terms are well-defined.
The maxima exist because all domains are finite and nonempty.
The induction correctly establishes the recurrence:
Consequently, the maximum for fixed \(x,y\) is exactly the stated sum of child messages and the local potential. Maximizing over \(x\) proves the recurrence. Signed entries cause no difficulty.
The same decomposition at the root establishes that \(V\) is the global optimum.
Each stored choice \(b_i(y)\) attains the corresponding message maximum. Traversing away from the root supplies each choice with its actual parent value, and recursively combines attaining subtree assignments. The reconstructed outcome therefore attains \(V\).
Arbitrary tie-breaking is valid. The explicitly addressed case \(m=1\) correctly reduces to root maximization. Singleton domains are also covered by the same definitions.
The construction of \(Q\) is valid. It includes denominator occurrences, so the mass denominator and the denominator of the selected utility entry are separate factors even when their numerical values coincide. Hence \(b_te\) divides \(Q\), and
\[
Q\mu_tf=n_tc\,\frac{Q}{b_te}
\]
is an integer.
All denominators are positive, so \(Q>0\). Scaling the objective by \(Q\) preserves its maximizing assignments. The method therefore performs exact optimization without rounding or unauthorized rescaling of relative utility scales.
The bit-length analysis is sound:
Thus all relevant integers have \(O(L)\) bits. Negative values and cancellation do not invalidate these absolute-value bounds.
The entry count
\[
E=|D_\rho|+\sum_{i\ne\rho}|D_i||D_{p(i)}|
\]
is correct, and \(E\le md^2\).
Constructing \(Q\) within \(O(L^2)\) bit operations is justified with schoolbook multiplication: the cumulative factor lengths are bounded by \(L\). Each scaled entry uses multiplication and exact division on \(O(L)\)-bit integers, costing \(O(L^2)\). Aggregation therefore costs \(O(\tau E L^2)\).
Precomputing each child-message sum once per vertex value avoids repeating it for every parent value. Across the tree, this requires \(O(md)\) additions; examining the potential tables requires \(O(E)\) additions and comparisons. The stated message-phase bound follows.
The reconstruction count is stated in stored-choice accesses. Any bit cost for indexing and emitting the explicit assignment is absorbed by the overall bound. Therefore
\[
O(\tau m d^2L^2)
\]
is a valid polynomial bit-operation bound.
No additional clarification or repair is needed. The proof establishes polynomial-time exact shared-outcome maximization for the specified input model.
⟨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.