d4-conf-ecai-2024-0308 (d4-conf-ecai-2024-0308)

Fix \(k\ge2\) and a tournament solution \(\gamma\subseteq TC\). Given a finite item set \(E\), a support of \(\tau\) types with positive binary-rational masses \(\mu_t\) summing to one, and common-scale rational coefficients \(\omega^t_S\) for \(S\in[E]^k\), with \(\Psi^t=0\), define \(u_t(A)=\sum_{S\subseteq A}\omega^t_S\) and \(\Phi_\mu(A,B)=\sum_t\mu_t(u_t(A)-u_t(B))\). Return one alternative in \(\gamma(2^E,\Phi_\mu)\), with input size measured in \(|E|,\tau\)\) and the coefficient and mass bit length. For \(\gamma=TC\), this is to return a set maximizing \(\sum_t\mu_tu_t(A)\).

Fix a constant \(k\ge2\) and a tournament solution \(\gamma\) that always returns a nonempty subset of the Top Cycle \(TC\).
Let \(E\) be a finite item set with \(m=|E|\), and define \([E]^k=\{S\subseteq E:1\le|S|\le k\}\). Every subset of \(E\), including \(\varnothing\), is an admissible alternative.
A society is given by its support: a list of \(\tau\) types with positive binary-rational masses \(\mu_t\) satisfying \(\sum_t\mu_t=1\). Here \(\tau\) is the support size, not the number of possible types.
Each type supplies explicitly listed coefficients \(\omega^t_S\in\mathbb Q\) for every \(S\in[E]^k\), on a common interpersonal scale; negative and zero coefficients are allowed. There are no bilinear interaction terms. Define \(u_t(A)=\sum_{S\in[E]^k,\,S\subseteq A}\omega^t_S\) and \(\Phi_\mu(A,B)=\sum_t\mu_t(u_t(A)-u_t(B))\).
Strict preference means \(\Phi_\mu(A,B)>0\), and zero means indifference. On these induced weak tournaments, \(TC(2^E,\Phi_\mu)=\operatorname*{arg\,max}_{A\subseteq E}\sum_t\mu_tu_t(A)\); ties are retained. The required output is any one set in \(\gamma(2^E,\Phi_\mu)\).
Let \(L\) be the total binary encoding length of the masses and coefficients; state running times in \(m,\tau,L\), with \(k\) and \(\gamma\) fixed.

Is this mass-society search problem solvable in time polynomial in \(m,\tau,L\), or is it NP-hard?

Known results: For a single rational-coefficient SSB model, finding one winner of any \(\gamma\subseteq TC\) over all subsets is NP-hard for every fixed \(k\ge2\), already with no bilinear terms. [Gilbert, Ouaguenouni and Spanjaard](https://ebooks.iospress.nl/pdf/doi/10.3233/FAIA240887).
No separate result explicitly addressing the stated mass-society formulation was verified.

Conclusion

The problem is NP-hard for every fixed \(k\ge 2\) and every fixed nonempty refinement \(\gamma\subseteq TC\). Hardness holds already for \(\tau=1\), mass \(\mu_1=1\), and coefficients belonging to \(\{-2,0,1\}\). Consequently, a running time polynomial in \(m,\tau,L\) would imply \(\mathrm P=\mathrm{NP}\).

1. Aggregation preserves the utility representation

Define the aggregate coefficients and utility by
\(\bar\omega_S=\sum_{t=1}^{\tau}\mu_t\omega_S^t\) and
\(U(A)=\sum_{S\in[E]^k,\ S\subseteq A}\bar\omega_S\).

Interchanging finite sums gives
\[ \sum_{t=1}^{\tau}\mu_tu_t(A)=U(A), \qquad \Phi_\mu(A,B)=U(A)-U(B). \]
Thus, by the Top Cycle identity stipulated in the question,
\(TC(2^E,\Phi_\mu)=\operatorname*{arg\,max}_{A\subseteq E}U(A)\).
Every valid output from \(\gamma\) must therefore maximize \(U\).

There are \(N_k(m)=\sum_{j=1}^{\min(k,m)}\binom mj=O((m+1)^k)\) coefficients per type. Aggregation uses \(O(\tau N_k(m))\) rational arithmetic operations and takes polynomial bit time. For example, elementary integer arithmetic gives the conservative bound
\(O(\tau(m+1)^k(L+1)^2)\): for any fixed coefficient, the products of the input denominators have \(O(L)\) bits, and the corresponding numerator also has \(O(L)\) bits.

This establishes efficient preprocessing; it does not establish efficient maximization.

2. Explicit hardness reduction

We reduce from the classical NP-complete Independent Set decision problem: given a finite simple undirected graph \(G=(V,F)\) and an integer \(r\), determine whether there is an independent vertex set of cardinality at least \(r\).

Construct an instance with \(E=V\), \(m=|V|\), one type, and \(\mu_1=1\). Explicitly list all required coefficients, setting
\[ \omega^1_S= \begin{cases} 1 & \text{if }|S|=1,\\ -2 & \text{if }|S|=2\text{ and }S\in F,\\ 0 & \text{otherwise}. \end{cases} \]
Here an edge is identified with its two-element endpoint set. All coefficients of cardinality greater than two are zero, so the construction applies to every fixed \(k\ge2\). The mass is positive and binary-rational, and every coefficient is an allowed rational number.

For \(A\subseteq V\), let \(e_G(A)\) denote the number of graph edges with both endpoints in \(A\). The resulting utility is
\(U(A)=|A|-2e_G(A)\).

Claim. The utility maximizers are exactly the maximum independent sets of \(G\).

Proof. Suppose \(A\) is not independent. Choose a vertex \(v\in A\) incident to an edge within \(A\), and let \(d_A(v)\ge1\) be its degree in the induced graph on \(A\). Deleting \(v\) removes exactly \(d_A(v)\) induced edges. Hence
\[ U(A\setminus\{v\})-U(A) =(|A|-1)-2(e_G(A)-d_A(v))-(|A|-2e_G(A)) =2d_A(v)-1\ge1. \]
Therefore no non-independent set maximizes utility.

For every independent set \(I\), we have \(e_G(I)=0\), so \(U(I)=|I|\). Because a maximizer exists on the finite domain and every maximizer is independent, the maximum utility equals the maximum independent-set cardinality. Consequently, the maximizers are precisely the maximum independent sets. This also covers the admissible empty alternative. \(\square\)

3. Every permissible output solves the source instance

Let \(A^\star\) be any valid output of the mass-society search problem. Since
\(A^\star\in\gamma(2^E,\Phi_\mu)\subseteq TC(2^E,\Phi_\mu)\),
the preceding claim implies that \(A^\star\) is a maximum independent set. Therefore the source instance is a yes-instance exactly when \(|A^\star|\ge r\).

The construction explicitly lists \(O((m+1)^k)\) coefficients, each of constant binary length. Even charging for subset labels, its encoding length and construction time are \(O((m+1)^k\log(m+2))\). Since \(k\) is fixed and \(\tau=1\), both are polynomial in the graph input size. Checking the cardinality of the returned set also takes polynomial time.

Thus one call to any correct search algorithm, followed by polynomial-time processing, decides an NP-complete problem. The reduction works for every permissible output, irrespective of how \(\gamma\) chooses among tied maximizers.

4. Relation to the supplied result

The same transfer follows immediately from the supplied single-model theorem: use one type of mass one and copy its coefficients. The induced preference intensities, Top Cycle, and \(\gamma\)-choice set are unchanged. The cited paper’s Theorem 3 explicitly establishes hardness with zero bilinear coefficients and pads higher-degree coefficients with zeros. [Gilbert, Ouaguenouni and Spanjaard, Theorem 3](https://ebooks.iospress.nl/pdf/doi/10.3233/FAIA240887).

No separate mass-society hardness theorem is needed; the one-type subclass already proves the requested result.

⟨structured verdict parsed — rendered above⟩

The output resolves the task correctly. Its explicit reduction establishes NP-hardness for every fixed \(k\ge2\) and every fixed nonempty refinement \(\gamma\subseteq TC\). No mathematical gaps or false steps were found.

• Aggregation and the Top Cycle. The definitions of \(\bar\omega_S\) and \(U(A)\) are valid for all supplied rational coefficients, including negative and zero values. Interchanging the finite sums correctly gives

\[ \sum_t\mu_tu_t(A)=U(A),\qquad \Phi_\mu(A,B)=U(A)-U(B). \]
Applying the Top Cycle identity explicitly stipulated in USER_TASK therefore establishes that every permissible output maximizes \(U\). This implication does not assume that every maximizer belongs to \(\gamma\).

• Preprocessing complexity. The coefficient count

\[ N_k(m)=\sum_{j=1}^{\min(k,m)}\binom mj=O((m+1)^k) \]
is correct for fixed \(k\), including \(m<k\) and \(m=0\). Computing each aggregate coefficient requires a number of rational operations linear in \(\tau\). For a fixed coefficient, the total input bit length bounds the denominator-product length and the numerator length by \(O(L)\). Thus the stated conservative bound \(O(\tau(m+1)^k(L+1)^2)\) is valid using elementary exact arithmetic. The output correctly distinguishes this preprocessing bound from the complexity of maximization.

• Source problem and construction. Independent Set on explicitly represented finite simple undirected graphs is an appropriate NP-complete source problem. The construction satisfies every relevant input restriction:

• The support has \(\tau=1\), with positive binary-rational mass \(\mu_1=1\).
• Every required coefficient is explicitly supplied.
• Coefficients belong to \(\{-2,0,1\}\).
• There are no bilinear terms.
• Setting coefficients above degree two to zero accommodates every fixed \(k\ge2\).

The construction correctly yields \(U(A)=|A|-2e_G(A)\) for every admissible subset \(A\).

• Characterization of maximizers. If \(A\) contains an edge, a vertex incident to that edge has \(d_A(v)\ge1\). The stated deletion calculation is correct:

\[ U(A\setminus\{v\})-U(A)=2d_A(v)-1\ge1. \]
Consequently, no non-independent subset can maximize utility. On independent subsets, utility equals cardinality. The finite, nonempty alternative domain guarantees a maximizer, so the argument correctly establishes that the maximizers are exactly the maximum independent sets.

The empty alternative causes no exception. For an empty graph vertex set, it is the sole alternative and the maximum independent set. For a nonempty vertex set, a singleton has utility one, exceeding the empty set’s utility zero.

• Use of every permissible output. Since \(\gamma\) is nonempty and contained in \(TC\), any returned \(A^\star\) is a maximum independent set. Hence comparing \(|A^\star|\) with \(r\) correctly decides the source instance. This works for arbitrary integer thresholds and for every choice among tied winners. No ability to control \(\gamma\)’s selection is assumed.

• Reduction complexity and hardness conclusion. Explicitly listing the coefficients and their subset labels takes \(O((m+1)^k\log(m+2))\) space and construction time under the standard explicit graph encoding. Fixed \(k\) makes this polynomial in the source input size. Cardinality extraction is polynomial as well. The argument therefore establishes NP-hardness of the search problem through one search call followed by polynomial processing. It does not claim NP-completeness or require efficient verification of membership in an arbitrary fixed \(\gamma\).

• Cited theorem. The supplementary attribution is accurate: [Theorem 3 of the cited paper](https://ebooks.iospress.nl/pdf/doi/10.3233/FAIA240887) treats the complete alternative domain, fixed degree at least two, and refinements of the Top Cycle; its proof uses a null bilinear matrix and zero coefficients above degree two. The one-type transfer preserves the preference intensities and choice set. The explicit reduction already establishes the conclusion independently of this citation.

No corrective feedback or additional clarification is required.

⟨structured verdict parsed — rendered above⟩