d4-conf-aaai-2013-0163 (d4-conf-aaai-2013-0163)

Given \(m\) and an explicit rational distribution \(\mu\) over ballot types \(t\in\{0,1\}^m\), decide whether there is a partition \(P\) of \([m]\) into nonempty bundles such that every \(C\in P\) satisfies \(q_\mu(C)\ge \tfrac12\), where \(q_\mu(C)=\sum_{t:\,2\sum_{i\in C}t_i\ge |C|}\mu_t\).

Let \(m\ge 1\) be the number of independent, equally weighted binary issues, indexed by \([m]=\{1,\ldots,m\}\).
A society is given by its support: a list \(T\subseteq\{0,1\}^m\) of \(\tau\) distinct types with positive binary rational masses \(\mu_t\), where \(\sum_{t\in T}\mu_t=1\). Here \(\tau\) is the support size, not the number of possible types; let \(L\) be the total input bit length.
Type \(t\) supports issue \(i\) exactly when \(t_i=1\). It approves a nonempty bundle \(C\subseteq[m]\) exactly when \(2\sum_{i\in C}t_i\ge |C|\).
Define \(q_\mu(C)=\sum_{t\in T:\,2\sum_{i\in C}t_i\ge |C|}\mu_t\). A bundle approves all its issues exactly when \(q_\mu(C)\ge\tfrac12\); ties at both voting stages favor approval.
A perfect bundling is a partition \(P\) of \([m]\) into nonempty bundles with \(q_\mu(C)\ge\tfrac12\) for every \(C\in P\). The number and sizes of bundles are unrestricted, and the society is fixed.

Is deciding whether a perfect bundling exists in \(\mathrm{P}\), with running time polynomial in \(m,\tau,L\), or is it \(\mathrm{NP}\)-hard?

For an explicitly listed finite electorate with equal voter weights and these same tie conventions, deciding whether a perfect bundling exists is \(\mathrm{NP}\)-complete. [Source](https://www.cs.tau.ac.il/~nogaa/PDFS/bundlingaaai2.pdf)
No separate result for this exact rational-mass formulation was identified in the search.

Result

The decision problem is \(\mathrm{NP}\)-complete. Hardness holds even when every mass is a dyadic rational, meaning a rational with a finite binary expansion.

Membership in \(\mathrm{NP}\)

A certificate assigns each issue a bundle label in \([m]\). The nonempty label classes form a partition, and the certificate uses \(O(m\log(m+1))\) bits.

Write each input mass as \(\mu_t=a_t/b_t\), with positive integers encoded in binary. Define
\(D=\prod_{t\in T}b_t\) and \(w_t=a_t(D/b_t)\).
These are integers, and normalization gives \(\sum_{t\in T}w_t=D\). The bit length of \(D\) is at most the sum of the denominator bit lengths, hence \(O(L)\); also \(0<w_t\le D\).

For each bundle \(C\), compute \(\sum_{i\in C}t_i\) for every type and check the exact integer inequality
\[ 2\sum_{\substack{t\in T\\2\sum_{i\in C}t_i\ge |C|}}w_t\ge D. \]
This is equivalent to \(q_\mu(C)\ge\tfrac12\). There are at most \(m\) bundles, and all arithmetic involves integers of polynomial bit length. Thus verification takes time polynomial in \(m,\tau,L\), proving membership in \(\mathrm{NP}\).

Polynomial reduction establishing hardness

We use the given equal-weight electorate hardness theorem. Its hypotheses match this task: the source defines approval by nested majority votes, breaks ties toward approval, and allows arbitrary partitions. Its Proposition 2 states that deciding whether a perfect bundling exists is \(\mathrm{NP}\)-complete. [Alon, Falik, Meir, and Tennenholtz, *Bundling Attacks in Judgment Aggregation*](https://www.cs.tau.ac.il/~nogaa/PDFS/bundlingaaai2.pdf)

Let an instance of that problem consist of \(n\ge1\) explicitly listed voters, whose rows are \(v^{(1)},\ldots,v^{(n)}\in\{0,1\}^m\). Repeated rows are permitted.

We first pad the electorate to make its size a power of two while preserving the decision on every nonempty bundle.

Let \(N\) be the smallest power of two satisfying \(N\ge\max\{2,n\}\). Then \(N\le2n\). Add

\[ a=\frac N2-\left\lceil\frac n2\right\rceil \]

voters supporting every issue, and

\[ b=\frac N2-\left\lfloor\frac n2\right\rfloor \]

voters supporting no issue. Both counts are nonnegative integers, and \(a+b=N-n\).

For a nonempty bundle \(C\), let \(r(C)\) be the number of original voters approving it. Every added all-supporting voter approves \(C\), and every added zero-supporting voter rejects it. Consequently, the padded electorate approves \(C\) exactly when

\[ r(C)+a\ge\frac N2 \quad\Longleftrightarrow\quad r(C)\ge\left\lceil\frac n2\right\rceil. \]

The last condition is exactly the original electorate’s approval rule, including its approval-favoring tie convention.

Now merge identical rows in the padded electorate. Let \(T\) be the set of distinct rows, and let \(k_t\) be the multiplicity of \(t\in T\). Set \(\mu_t=k_t/N\). These masses are positive, sum to one, and are dyadic because \(N\) is a power of two.

For every nonempty bundle \(C\),

\[ q_\mu(C)=\frac{r(C)+a}{N}. \]

Thus \(C\) passes in the constructed society if and only if it passes in the original electorate. Since the issues are unchanged, every partition succeeds in one instance if and only if it succeeds in the other. In particular, existence of a perfect bundling is preserved in both directions.

Finally, the construction has polynomial size. There are at most \(n+2\) distinct types; each type requires \(m\) bits, and each mass requires \(O(\log(n+1))\) bits. Hence the output length is

\[ O\bigl((n+2)(m+\log(n+1))\bigr), \]

which is polynomial in the explicitly listed electorate’s input length. Padding, grouping rows, and computing their multiplicities also take polynomial time.

This is a polynomial many-one reduction, proving \(\mathrm{NP}\)-hardness. Together with membership in \(\mathrm{NP}\), it settles the question.

⟨structured verdict parsed — rendered above⟩

The prover’s claim is proved. The argument establishes \(\mathrm{NP}\)-completeness for the stated rational-mass problem, including the restriction to dyadic masses. No major or minor mathematical issues were found.

1. Applicability of the cited hardness theorem

The cited source defines an electorate by an explicitly listed binary matrix. It defines majority with ties favoring approval, applies that convention at both voting stages, and allows unrestricted partitions of the issues. Its definition of a perfect bundling requires approval of every issue, and Proposition 2 states that deciding its existence is \(\mathrm{NP}\)-complete. These hypotheses match the source problem used in the reduction. [Alon, Falik, Meir, and Tennenholtz, *Bundling Attacks in Judgment Aggregation*, Preliminaries and Proposition 2](https://www.cs.tau.ac.il/~nogaa/PDFS/bundlingaaai2.pdf)

The prover appropriately invokes this theorem rather than claiming to reprove it. The source result is also explicitly supplied in USER_TASK.

2. Certificate and membership in \(\mathrm{NP}\)

Assigning each issue a label in \([m]\) specifies a partition through the nonempty label classes. Every issue belongs to exactly one class, and empty classes are disregarded. The certificate length bound of \(O(m\log(m+1))\) is correct, including when \(m=1\).

For positive rational masses \(\mu_t=a_t/b_t\), the definitions
\[ D=\prod_{t\in T}b_t, \qquad w_t=a_t(D/b_t) \]
give positive integers because every denominator divides \(D\). Normalization implies
\[ \sum_{t\in T}w_t=D. \]
Consequently, each \(w_t\) is at most \(D\).

The bit length of the product \(D\) is bounded by the sum of the denominator bit lengths, hence by \(O(L)\). Computing this product, performing the exact divisions, and constructing the integer weights all take polynomial time.

For each bundle, the verifier computes the number of supported issues for each type and then checks
\[ 2\sum_{\substack{t\in T\\2\sum_{i\in C}t_i\ge |C|}}w_t\ge D. \]
The inner inequality implements the type’s approval rule, including ties. The outer inequality implements the society’s approval rule, also including ties. Dividing by \(D>0\) establishes the stated equivalence with \(q_\mu(C)\ge\tfrac12\).

There are at most \(m\) nonempty bundles. The number of operations and the bit lengths of the integers used are polynomially bounded in \(m,\tau,L\). Membership in \(\mathrm{NP}\) follows.

3. Padding parameters and edge cases

The choice of \(N\) is valid. For \(n=1\), it gives \(N=2=2n\). For \(n\ge2\), the smallest power of two at least \(n\) satisfies \(N<2n\), so the stated bound \(N\le2n\) holds throughout.

Because \(N\) is even and \(N\ge n\),
\[ \frac N2\ge\left\lceil\frac n2\right\rceil. \]
Thus both padding counts
\[ a=\frac N2-\left\lceil\frac n2\right\rceil, \qquad b=\frac N2-\left\lfloor\frac n2\right\rfloor \]
are nonnegative integers. Their sum is \(N-n\), as claimed.

For the boundary case \(n=1\), these formulas give \(a=0\) and \(b=1\), so the construction remains well-defined.

4. Preservation of every nonempty bundle

An all-supporting voter approves every nonempty bundle. A zero-supporting voter rejects every nonempty bundle because its approval inequality would require \(0\ge |C|\). The restriction to nonempty bundles is therefore essential and is explicitly maintained.

The padded electorate has exactly \(r(C)+a\) approving voters. Since its size is \(N\), it approves the bundle exactly when
\[ r(C)+a\ge\frac N2 \quad\Longleftrightarrow\quad r(C)\ge\left\lceil\frac n2\right\rceil. \]
For integral \(r(C)\), the last condition is precisely the original electorate’s approval threshold.

This calculation correctly handles odd and even electorate sizes, including ties for even sizes. The preservation claim holds for every nonempty bundle, not merely for bundles belonging to a particular proposed partition.

5. Merging rows and rational encoding

Grouping identical rows produces distinct types with positive integer multiplicities \(k_t\). Their sum is \(N\), so the masses \(k_t/N\) are positive and normalized.

Because \(N\) is a power of two, all these masses are dyadic. They have polynomial-length encodings whether represented as binary numerator–denominator pairs or as finite binary expansions.

Merging rows preserves the total weight of approving voters. Hence
\[ q_\mu(C)=\frac{r(C)+a}{N} \]
is correct for every nonempty bundle, including when either added row type already occurred in the original electorate.

6. Preservation of the decision problem

The issue set is unchanged. Since each possible nonempty bundle passes in the constructed instance exactly when it passes in the original instance, each partition is perfect in one instance exactly when it is perfect in the other.

This establishes both directions required for a many-one reduction.

7. Polynomial size and construction time

Padding introduces at most two new distinct row types, giving at most \(n+2\) types. Each type requires \(m\) bits, and each mass requires \(O(\log(n+1))\) bits. The claimed output-size bound
\[ O\bigl((n+2)(m+\log(n+1))\bigr) \]
is polynomial in the explicitly listed source input length.

The bound \(N\le2n\) also ensures that literal padding, grouping rows, and counting multiplicities take polynomial time. No exponentially expanded electorate is used.

The reduction therefore proves \(\mathrm{NP}\)-hardness even for dyadic masses. Together with the verified membership argument, it proves the claimed \(\mathrm{NP}\)-completeness.

No additional clarification or repair is required.

⟨structured verdict parsed — rendered above⟩