Answer: polynomial-time solvable
Theorem 15 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateThe computation of Mt can be performed in time O(g|I|2). Moreover, the total time spent on this task throughout the auction is O(g|I|(|I| + T)). We obtain a bound on T, the number of rounds of Phase A, by comparing the sum of prices of all sub-configurations in rounds 1 and T.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a finite support of requirement types \(t\), binary-rational masses \(\mu_t\), type-specific GAI valuations \(u_t(\theta)=\sum_r f_{t,r}(\theta_r)\), common cluster domains and current cluster prices \(p_r(\alpha)\), and a rational tolerance \(\epsilon\), compute for each type the set \(M_{t,r}=\{\alpha:\exists\theta,\ \theta_r=\alpha,\ u_t(\theta)-\sum_r p_r(\theta_r)\ge\max_{\theta'}(u_t(\theta')-\sum_r p_r(\theta'))-\epsilon\}\), and aggregate possible demand as \(\nu_{r,\alpha}=\sum_{t:\alpha\in M_{t,r}}\mu_t\).
Let \(A\) consist of \(m\ge 1\) attributes with explicitly listed, finite nonempty domains \(D(a)\), and let \(\Theta=\prod_{a\in A}D(a)\).
The input includes nonempty clusters \(I_1,\ldots,I_g\) covering \(A\), arranged in a supplied junction tree satisfying running intersection; write \(D_r=\prod_{a\in I_r}D(a)\), \(\theta_r=\theta|_{I_r}\), and \(S=\sum_{r=1}^g|D_r|\). Overlapping cluster assignments must agree on shared attributes.
A society is given by its support: the list of the \(\tau\ge 1\) types with positive binary-rational masses \(\mu_t\), normalized by \(\sum_t\mu_t=1\). Here \(\tau\) is the support size, not the number of possible types.
Each type has explicitly tabulated binary-rational GAI factors \(f_{t,r}:D_r\to\mathbb Q\), with \(u_t(\theta)=\sum_r f_{t,r}(\theta_r)\ge 0\) for every configuration. Common current cluster prices \(p_r:D_r\to\mathbb Q\) are also explicitly tabulated; local factors and prices may have either sign. The tolerance \(\epsilon\) is a positive binary rational.
Define \(q_t(\theta)=u_t(\theta)-\sum_r p_r(\theta_r)\) and \(M_{t,r}=\{\alpha\in D_r:\exists\theta\in\Theta,\ \theta_r=\alpha,\ q_t(\theta)\ge\max_{\theta'\in\Theta}q_t(\theta')-\epsilon\}\). Include all qualifying assignments, including ties.
Compute every \(M_{t,r}\) and every possible-demand mass \(\nu_{r,\alpha}=\sum_{t:\alpha\in M_{t,r}}\mu_t\); this counts eligibility separately for each assignment, without allocating mass among alternatives. Let \(L\) be the total binary input length.
Is this exact computation solvable in polynomial time in \(m,\tau,g,S,L\), or is it NP-hard?
For a single discrete buyer with this junction-tree GAI structure, the preferred-subconfiguration set is computable in \(O(gS^2)\) arithmetic operations ([Engel and Wellman, 2010](https://arxiv.org/pdf/1401.3844)).
No result addressing exactly this support-given mass formulation was identified in the literature search.
Result. The exact computation is polynomial-time solvable in \(m,\tau,g,S,L\). The explicitly listed support permits computing eligibility separately for each type and then summing its mass. Below is a self-contained proof, including exact arithmetic and ties.
The single-type computation is consistent with Theorem 15 of [Engel and Wellman (2010)](https://arxiv.org/pdf/1401.3844); the proof below establishes the requested support-given formulation directly.
1. Compatibility on the junction tree.
Let \(T\) be the supplied tree on cluster indices. Running intersection means that, for every attribute \(a\), the nodes whose clusters contain \(a\) form a connected subtree.
Suppose assignments \(\alpha_r\in D_r\) agree on every tree-edge intersection. If an attribute \(a\) occurs in clusters \(I_r\) and \(I_s\), running intersection implies that every cluster on the path between them contains \(a\). Agreement along this path therefore gives the same value of \(a\) at both endpoints. Because the clusters cover \(A\), these assignments define a unique configuration in \(\Theta\).
For an edge \(\{r,s\}\), write \(J_{rs}=I_r\cap I_s\). Removing the edge gives two components, with node sets \(C_{r\to s}\) and \(C_{s\to r}\). Define their attribute sets by \(V_{r\to s}=\bigcup_{k\in C_{r\to s}}I_k\). Then
\( \displaystyle V_{r\to s}\cap V_{s\to r}=J_{rs}. \)
Indeed, an attribute occurring on both sides must occur throughout a path crossing the removed edge, hence in both endpoint clusters. The reverse inclusion is immediate. Thus the two sides share precisely their separator attributes.
2. Exact message recurrence.
Fix a type \(t\), and define the net local factor
\( \displaystyle h_{t,r}(\alpha)=f_{t,r}(\alpha)-p_r(\alpha). \)
Then \(q_t(\theta)=\sum_r h_{t,r}(\theta_r)\).
For each directed tree edge \(r\to s\) and separator assignment \(\sigma\in\prod_{a\in J_{rs}}D(a)\), define
\( \displaystyle B_{t,r\to s}(\sigma)= \max_{\substack{x\in\prod_{a\in V_{r\to s}}D(a)\\x|_{J_{rs}}=\sigma}} \sum_{k\in C_{r\to s}}h_{t,k}(x|_{I_k}). \)
For an empty separator, its assignment domain is the singleton containing the empty assignment. All these maxima exist: the domains are finite and nonempty, and every separator assignment extends to its component’s attribute set.
Let \(N(r)\) denote the neighbors of \(r\). The recurrence is
\( \displaystyle B_{t,r\to s}(\sigma)= \max_{\substack{\alpha\in D_r\\\alpha|_{J_{rs}}=\sigma}} \left[ h_{t,r}(\alpha)+ \sum_{k\in N(r)\setminus\{s\}} B_{t,k\to r}(\alpha|_{J_{kr}}) \right]. \)
To justify it, fix \(\alpha\in D_r\). Removing \(r\) splits the remaining clusters of \(C_{r\to s}\) into branches indexed by \(k\in N(r)\setminus\{s\}\). Each branch intersects \(I_r\) precisely in \(J_{kr}\). Any attribute shared by two branches belongs to \(I_r\), since the path between its occurrences passes through \(r\).
Consequently, once \(\alpha\) is fixed, branch assignments constrained by its separator restrictions are mutually compatible. Choosing a maximizing assignment in each branch and combining them with \(\alpha\) attains the bracketed expression. Conversely, every feasible component assignment restricts to feasible branch assignments, whose contributions are bounded above by the corresponding messages. Maximizing over \(\alpha\) proves the recurrence.
Choose any root. Compute messages toward the root in an upward pass, then messages away from it in a downward pass. In the downward pass, the message from a node’s parent is available before its outgoing messages to children are computed, while all messages from children were computed in the upward pass. Thus every recurrence uses only previously computed messages.
3. Recovering every qualifying assignment.
For each cluster assignment, calculate
\( \displaystyle H_{t,r}(\alpha)= h_{t,r}(\alpha)+ \sum_{k\in N(r)} B_{t,k\to r}(\alpha|_{J_{kr}}). \)
The same branch argument, now including all neighbors, proves
\( \displaystyle H_{t,r}(\alpha)= \max_{\substack{\theta\in\Theta\\\theta_r=\alpha}}q_t(\theta). \)
In particular, using any fixed cluster \(r_0\),
\( \displaystyle Q_t=\max_{\alpha\in D_{r_0}}H_{t,r_0}(\alpha) =\max_{\theta\in\Theta}q_t(\theta). \)
The equality holds because the configurations are partitioned according to their assignment on \(I_{r_0}\).
Therefore,
\( \displaystyle M_{t,r}= \{\alpha\in D_r:H_{t,r}(\alpha)\ge Q_t-\epsilon\}. \)
Both implications follow directly. A qualifying configuration gives a constrained maximum at least \(Q_t-\epsilon\). Conversely, if the constrained maximum meets that threshold, a configuration attaining it witnesses membership. Using the weak inequality retains every tie, including equality at the tolerance boundary.
4. Computing the masses.
Initialize every \(\nu_{r,\alpha}\) to zero. For each listed type \(t\), compute its sets as above and add \(\mu_t\) to \(\nu_{r,\alpha}\) exactly when \(\alpha\in M_{t,r}\). The resulting value is precisely
\( \displaystyle \nu_{r,\alpha}= \sum_{t=1}^{\tau}\mu_t\,\mathbf 1_{\{\alpha\in M_{t,r}\}}. \)
This adds a type’s mass separately to every eligible assignment, as required. A membership table contains \(\tau S\) Boolean entries, and there are \(S\) masses to output.
5. Polynomial operation count and bit complexity.
Put \(n_r=|D_r|\), so \(S=\sum_r n_r\) and \(g\le S\). Every separator domain has size at most either endpoint’s assignment domain. Separator projections can therefore be indexed explicitly in polynomial time without enumerating \(\Theta\).
A direct implementation of a message from \(r\) scans the \(n_r\) assignments and sums at most \(\deg(r)\) incoming values for each assignment. Across all directed messages, this takes at most a constant times
\( \displaystyle S+\sum_r n_r\deg(r)^2 \le S+g^2S \le 2gS^2 \)
arithmetic operations and comparisons. Computing all \(H_{t,r}\), testing membership, and updating masses also fits this bound. Hence all types require \(O(\tau gS^2)\) arithmetic operations and comparisons, plus polynomial preprocessing and output work. This includes \(g=1\), where there are no messages and the single table is scanned directly.
To establish polynomial bit complexity, represent each input rational as an integer numerator divided by a positive integer denominator. Let \(K\) be the product of all input rational denominators, including those of the masses and tolerance. The sum of their binary encoding lengths is bounded by \(L\), so \(K\) has \(O(L)\) bits. Computing it takes polynomial time.
Scale every rational by \(K\). All factors, prices, masses, and the tolerance become integers. Each scaled input value has \(O(L)\) bits, as does each scaled net local factor. Because \(K>0\), scaling preserves all maximization and eligibility comparisons.
Every message value is a sum of scaled local factors from a feasible assignment on at most \(g\) clusters. Every constrained or global maximum is likewise such a sum. Their magnitudes are therefore bounded by \(g\) times the largest scaled local-factor magnitude, giving \(O(L+\log g)\) bits. Intermediate partial sums satisfy the same bound.
Mass accumulation is also exact: add the scaled integer masses and output the resulting numerator over \(K\). Positive masses summing to one imply that each accumulated numerator lies between zero and \(K\). Thus each mass has a polynomial-length rational representation.
All arithmetic, comparisons, indexing, and output operations consequently have polynomial bit cost. Negative local factors and prices cause no difficulty; the proof uses finite maximization and exact addition, without a sign assumption.
The requested computation is therefore polynomial-time solvable under all the stated hypotheses.
⟨structured verdict parsed — rendered above⟩
The prover resolves the task correctly. The output establishes an exact polynomial-time algorithm for every \(M_{t,r}\) and every \(\nu_{r,\alpha}\), with polynomial bit complexity. I found no major or minor mathematical issues.
The running-intersection argument is correct. If two clusters contain an attribute, every cluster on their connecting path contains it. Agreement across tree-edge intersections therefore implies agreement across all overlapping clusters.
Coverage of \(A\) ensures that the compatible cluster assignments determine every attribute; their agreement ensures uniqueness. The resulting configuration belongs to \(\Theta\), since the specified domain is the full Cartesian product.
The separator identity
\[
V_{r\to s}\cap V_{s\to r}=J_{rs}
\]
also follows correctly: an attribute occurring on both sides of the removed edge must occur in both endpoint clusters. This justifies treating the separator as the complete interface between the components.
Each message is well-defined. Its feasible set is finite and nonempty because every separator assignment extends to the component’s attribute set. Empty separators are explicitly handled by the singleton empty assignment.
The recurrence accounts for every factor in the component exactly once. Its two required directions are justified:
The compatibility claim follows from running intersection: any attribute shared between branches also occurs in the central cluster, where its value is already fixed. There is no omitted dependence between branches.
The upward and downward passes provide all incoming messages before each outgoing recurrence is evaluated. For \(g=1\), the message stage is empty, as explicitly acknowledged.
The same branch decomposition correctly establishes
\[
H_{t,r}(\alpha)=
\max_{\theta\in\Theta:\,\theta_r=\alpha}q_t(\theta).
\]
Every cluster assignment extends to a full configuration. Consequently, taking the maximum over the assignments of any fixed cluster gives the unrestricted maximum \(Q_t\).
The membership criterion
\[
\alpha\in M_{t,r}
\quad\Longleftrightarrow\quad
H_{t,r}(\alpha)\ge Q_t-\epsilon
\]
matches the task’s existential definition exactly. The reverse implication uses attainment of a finite maximum, which the proof has established.
The weak inequality includes all ties and assignments exactly at the tolerance boundary. No assumption that \(q_t\) is nonnegative is used or needed.
The accumulation rule is exactly the requested sum over eligible support types. It adds each type’s mass independently to every eligible assignment, without dividing the mass among alternatives.
The output size is correctly bounded by \(\tau S\) membership entries and \(S\) rational masses. The algorithm depends on the explicitly listed support, rather than on an unlisted universe of possible types.
For a node \(r\), there are \(\deg(r)\) outgoing messages. Scanning its \(n_r\) assignments and summing at most \(\deg(r)\) incoming terms for each message gives the stated bound proportional to
\[
S+\sum_r n_r\deg(r)^2.
\]
The subsequent inequalities are valid:
\[
S+\sum_r n_r\deg(r)^2
\le S+g^2S
\le 2gS^2.
\]
They use \(\deg(r)\le g\), \(g\le S\), and \(g,S\ge1\).
Computing constrained maxima, threshold comparisons, and mass updates fits the same asymptotic bound. Separator domains cannot exceed either endpoint domain, so explicit separator indexing requires only polynomial preprocessing. Attribute projection and indexing costs are appropriately covered by the broader polynomial bit-cost claim.
Thus the stated \(O(\tau gS^2)\) arithmetic-operation bound is supported.
The common-denominator construction is valid for binary-rational input. The product \(K\) has \(O(L)\) bits because the sum of the input denominator lengths is bounded by the total input length.
Multiplying each rational by \(K\) produces an integer of \(O(L)\) bits. Scaling by a positive common factor preserves all relevant inequalities and maxima.
Each message represents a sum of local factors over at most \(g\) clusters. The stated magnitude bound therefore gives \(O(L+\log g)\) bits. Intermediate branch sums have the same bound because their factors come from disjoint sets of cluster nodes. Threshold subtraction also has polynomial bit length.
For each assignment, accumulated scaled masses lie between zero and \(K\), using positivity and normalization. Outputting the numerator over \(K\) is an exact polynomial-length rational representation; reduction to lowest terms is unnecessary.
The proof therefore establishes polynomial bit complexity, rather than merely polynomial arithmetic complexity.
The consistency claim agrees with Theorem 15’s single-buyer bound in [Engel and Wellman (2010)](https://arxiv.org/pdf/1401.3844). The prover supplies an independent argument, so the support-given result does not depend on an unstated application of that theorem.
The proof addresses precisely the supplied junction-tree representation and explicit local tables. It makes no unsupported claim of polynomial dependence on a compact representation that omits those tables.
No additional clarification or mathematical repair is required. Both the eligibility computation and the exact support-mass aggregation are established under the stated hypotheses.
⟨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.