| paper | d4-conf-aaai-2013-0163 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
NP-hard→NP-hard discrete result → its continuous mirror
Answer: \(\mathrm{NP}\text{-complete}\), even for dyadic rational masses. · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Proposition 2
statement extracted from the paper’s text layer
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\).
The society is an explicit distribution \(\mu\) over complete yes/no ballot types \(t\in\{0,1\}^m\). The chair chooses a partition of the issues; each type votes yes on a bundle when at least half its issues have yes answers, and the bundle passes when yes-voting mass is at least \(\tfrac12\).
The mirror covers the worst-case results PERFECTBUNDLING in Proposition 2 and \(k\)-BUNDLING in Proposition 1. It does not cover the average-case analysis, including Theorem 5.
My strongest case is for a continuous mirror of the paper’s worst-case bundling problems. A type is a complete yes/no opinion vector \(t\in\{0,1\}^m\) over the issues. The society is an explicit distribution \(\mu\) over the types that occur, with rational masses summing to \(1\). A bundle \(C\) passes the paper’s two-stage voting rule when a majority of the population has a majority of yes answers within \(C\), with ties going to yes. In notation, its yes-mass is
\[
q_\mu(C)=\sum_{t:\,2\sum_{i\in C}t_i\ge |C|}\mu_t,
\]
and \(C\) passes when \(q_\mu(C)\ge \tfrac12\).
This is a plausible high-multiplicity setting for a public consultation or referendum on a growing slate of issues: residents submit complete binary ballots, and the chair chooses how to package the issues for voting. The population could number in the millions while many residents share ballot types; for instance, standardized positions or recurring coalitions could yield a support much smaller than the electorate. More generally, any finite instance in the paper can be replicated \(q\) times, giving \(q n\) people across at most \(n\) types without changing the distribution. This does not establish hardness for constant or very small support, but it shows how the mass model represents a large population sharing complete types. The issues stay finite and the chair’s action remains an ordinary partition; the population is what is represented continuously.
Lead anchor: Proposition 2. The paper states that PERFECTBUNDLING is NP-complete: given an IJA matrix, decide whether there is a partition of its issues such that every bundle is approved, so the resulting outcome approves all issues. The paper proves this in a proof sketch by reduction from ISTRIPARTITE, whose NP-hardness it attributes to a reduction from graph 3-coloring.
The corresponding continuous question is Continuous PERFECTBUNDLING. Given \(m\) and an explicit rational distribution \(\mu\) over a support \(S\subseteq\{0,1\}^m\), decide whether there is a partition \(P\) of \([m]\) into nonempty bundles such that \(q_\mu(C)\ge\tfrac12\) for every \(C\in P\). A solution is such a partition. The paper’s discrete instances embed exactly: for a matrix \(A\) with \(n\) judges, set \(\mu_t\) to the fraction of its rows equal to \(t\). Then \(q_\mu(C)\) equals the fraction of judges who approve \(C\), so a partition succeeds in one model exactly when it succeeds in the other. The continuous problem is in NP because a proposed partition can be checked using exact rational arithmetic. Thus, with explicit-support binary input, this mirror is NP-complete and belongs to Class B: the agenda and partitioning combinatorics carry the hardness across.
Second anchor: Proposition 1. The paper states that \(k\)-BUNDLING is NP-complete: given an IJA matrix and \(k\le m\), decide whether some bundle of exactly \(k\) issues is approved. The paper proves this by a transpose reduction from its OPTIMALLOBBYING′ variant; its discussion argues that variant is NP-hard by adapting the optimal-lobbying hardness cited there from Nehama (2013).
Its mirror is Continuous \(k\)-BUNDLING. Given \(m\), \(k\le m\), and an explicit rational distribution \(\mu\) over \(\{0,1\}^m\), decide whether there exists \(C\subseteq[m]\) with \(|C|=k\) and \(q_\mu(C)\ge\tfrac12\). A solution is the bundle \(C\). The same empirical-distribution embedding preserves yes and no instances, and verification is polynomial, so this problem is also NP-complete in the explicit-support encoding. It is a distinct anchor: it shows hardness for a single chosen bundle, as well as for partitioning the entire agenda. I expect hardness to transfer for both mirrors, rather than disappear or arise specifically from arbitrary fractional masses.
These questions cover the paper’s deterministic worst-case bundling hardness results, not its average-case Theorem 5. That theorem studies random finite profiles under an i.i.d. agreement model; it can be noted separately as a probability-over-profiles angle, but it is not needed for this population mirror.
My weakest point is that the hardness argument is deliberately conservative: it follows because every finite profile is already an empirical distribution. The paper’s reductions do not show NP-hardness when the number of types \(\tau\) is fixed or especially small relative to \(m\), nor do they establish a new continuum-specific obstruction. That limits what this case says about the benefit of high multiplicity. It does not, though, make the mass-based questions implausible: each preserves the paper’s types, voting rule, chair’s decision, and objective while asking the same computational question for a population given by type shares. Further questions include whether bounded \(\tau\), restrictions on bundle size or count, or approximation variants admit algorithms.
I cannot make the requested universal negative case honestly. Both anchors are named computational results, and their strongest continuous mirrors survive the programme’s criteria.
For Proposition 2, use complete yes/no ballots as types and let \(\mu_t\) be each type’s population share. A bundle passes when the mass of judges who approve a majority of its issues is at least \(1/2\); a partition succeeds when every bundle passes. This keeps the agenda, chair’s action, and objective intact. Replacing individual judges with masses loses no information the problem uses, and the majority threshold remains meaningful in the continuum.
The same construction defeats Proposition 1: ask whether some size-\(k\) bundle passes. In both cases, every finite profile maps to its empirical distribution with exactly the same answer. Conversely, clearing the denominators of any rational distribution gives a finite weighted electorate. That equivalence limits claims of novelty, but it is not a valid objection here: the programme explicitly treats high-multiplicity formulations as supporting evidence, and transferred hardness is an acceptable outcome.
The strongest reservation is about the regime’s reach. A type is a complete ballot over all \(m\) issues, so the possible type space has size \(2^m\). The paper’s reductions do not show hardness when the support size \(\tau\) is small, and in a growing agenda exact ballot repetition may be less common. That makes the proponent’s case for a *low-support* advantage incomplete. It does not rule out a sensible regime, though: for a fixed or stable agenda, a large electorate with recurring ballot types is plausible, and neither anchor tracks named individuals or degenerates when agents become negligible.
So the negative case is weak. The mirrors may yield hardness that transfers directly, but the task’s rules explicitly exclude that as a reason to reject them. I see no permitted ground that defeats either anchor in every plausible scenario.
The adversarial triple: the proponent anchors on up to three named results; the opponent sees that case and must defeat every anchor; the judge decides which case convinced it. These are the pipeline’s own outputs, generated by tools/triple_run.py — no human edited them. The paper’s own text is not reproduced here beyond the quoted statement above.