| paper | d4-conf-atal-2013-0343 |
| 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→P discrete result → its continuous mirror
Answer: Polynomial-time solvable in \((m+\tau+L)^{O(1)}\) bit operations. · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 5.3
statement extracted from the paper’s text layer
Given two agendas \(A_1,A_2\), a finite support \(T\) of joint ranking types with rational masses \(\mu_t\) summing to \(1\), rational committee masses \(\alpha_1,\alpha_2>0\) with \(\alpha_1+\alpha_2\le1\), and target winners \(a_1^\star,a_2^\star\), decide whether there are allocations \(x_{t,j}\ge0\) satisfying \(\sum_j x_{t,j}\le\mu_t\) and \(\sum_t x_{t,j}=\alpha_j\), such that each target wins under weighted 2-Approval and the paper’s fixed tie-breaking rule.
Use support \(T\) of joint types \(t=(R_t^1,R_t^2)\), masses \(\mu_t\), and allocation variables \(x_{t,j}\) for \(j\in\{1,2\}\). Each alternative’s score on issue \(j\) is \(\mathrm{sc}_j(a)=\sum_t x_{t,j}\mathbf{1}[a\text{ is in the top two of }R_t^j]\); impose the target-winner comparisons according to the fixed tie-breaking order. This gives a finite-support linear feasibility problem, with strict comparisons handled by maximizing a common positive margin.
The mirror covers the hardness questions in Theorems 5.3 and 6.1; it leaves the paper’s algorithmic results, other voting rules, and richer center-preference models aside.
The strongest mirror is the paper’s two-issue, two-committee problem. A credible regime is a very large membership organization forming substantial online assemblies for several policy decisions. Members have recurring, standardized preference profiles, so the population may have millions of people but far fewer distinct profiles. A type is a member’s joint preference profile across the issues. Keeping the joint profile matters: replacing it with separate per-issue distributions would lose the correlations that constrain who can serve on which committee.
The lead anchor is Theorem 5.3, proved in this paper: “2-Approval-DELEGATION is NP-complete even if \(k=2\).” In the finite problem, the input gives two issues, a voter set with a ranking for each voter on each issue, fixed committee sizes, and a desired outcome. The question is whether the center can assign voters to disjoint committees of those sizes so that 2-Approval elects the desired alternative on both issues. The theorem proves this joint assignment problem NP-complete, via a reduction from P-MATCHING. It is a particularly good anchor because the hardness concerns coordination between committees, not just choosing one winning committee.
Here is the corresponding Continuous 2-Approval Delegation problem. The input gives two issue agendas \(A_1,A_2\), a finite support \(T\) of joint types \(t=(R_t^1,R_t^2)\), rational masses \(\mu_t\ge 0\) summing to \(1\), committee mass requirements \(\alpha_1,\alpha_2>0\) with \(\alpha_1+\alpha_2\le 1\), and target winners \(a_1^\star,a_2^\star\). A solution is an allocation \(x_{t,j}\ge 0\), where \(x_{t,j}\) is the mass of type \(t\) assigned to committee \(j\), satisfying
\[
\sum_{j=1}^2 x_{t,j}\le\mu_t
\quad\text{and}\quad
\sum_{t\in T}x_{t,j}=\alpha_j.
\]
For each issue \(j\), the weighted 2-Approval score of alternative \(a\) is
\[
\mathrm{sc}_j(a)=\sum_{t\in T}x_{t,j}\,\mathbf{1}[a\text{ is in the top two of }R_t^j].
\]
The allocation is feasible exactly when \(a_j^\star\) is the winner under the paper’s fixed tie-breaking rule on each issue. The objective remains the paper’s decision objective: find any feasible assignment of mass, or report that none exists.
This is an LP feasibility problem, with \(O(|T|)\) allocation variables for the two committees and linear score constraints. Ties are handled exactly: require a weak score inequality against alternatives the target beats in a tie, and a strict one against alternatives that beat it in a tie. Strict inequalities can be checked by maximizing a shared positive margin \(\epsilon\) for the latter comparisons and asking whether the optimum is positive. Thus this mirror is expected to be tractable, in time polynomial in the agendas’ size, support size, and input bit length.
The mirror preserves the paper’s central choice: the designer allocates a population to committees, must respect committee sizes and the one-committee-per-person constraint, and wants specified voting outcomes. It also preserves the cross-issue correlation through joint types. Its substantive change is that a type’s mass may be split between committees. That is the intended high-multiplicity interpretation: if a discrete instance has \(n_t\) members of type \(t\) among \(n\) members, and committee sizes \(s_j\), then \(\mu_t=n_t/n\) and \(\alpha_j=s_j/n\); every discrete assignment gives a continuous allocation, while the reverse need not hold.
A second, narrower anchor is Theorem 6.1, also proved here: for every \(r\ge3\), \(r\)-Approval-DELEGATION is NP-complete even when \(k=1\). The finite problem asks whether a committee of the specified size can be selected so that a designated alternative wins under \(r\)-Approval. The paper proves the \(r=3\) case by reduction from Exact Cover by 3-Sets, then pads the construction for larger \(r\).
Its mirror, Continuous \(r\)-Approval Delegation, has one issue, a support of rational-mass ranking types, a committee mass \(\alpha\), and a target winner \(a^\star\). Find \(x_t\in[0,\mu_t]\) with \(\sum_t x_t=\alpha\) such that \(a^\star\) wins with scores \(\mathrm{sc}(a)=\sum_t x_t\mathbf{1}[a\text{ is ranked in the top }r\text{ by }t]\), using the same tie rule. This too is an LP, so I expect it to be tractable. The theorem’s exact-cover hardness is in the integral choice of voters; the continuous problem allows fractions of a type to be selected. The two-committee mirror is the stronger case, but this one independently tests whether the single-committee selection hardness survives that relaxation.
These questions cover the hardness results in Theorems 5.3 and 6.1, not the paper’s full complexity landscape, its richer center-preference models, or its results for other voting rules. They also generate useful follow-up questions: when can a feasible fractional allocation be rounded to an actual delegation while preserving the winners, especially with small winner margins? And which changes to the model—richer voting rules or compact descriptions of acceptable outcome combinations, for example—reintroduce hardness in the continuous problem?
My weakest point is the meaning of “committee.” The paper motivates committees that may be small and made of individually appointed people; in those settings, a fractional committee is not a literal committee. The proposed regime needs large assemblies whose sizes scale with the membership, and where assignments can be interpreted as selecting cohorts from repeated types. If the authors reject that regime, the mirror fails their plausibility test. But for large membership bodies making decisions through large online assemblies, it seems a faithful high-multiplicity version of their allocation problem—not a change to the voting rule or the designer’s goal.
The strongest objection I can make is about what counts as a committee. In the paper’s motivating settings, committees are usually small bodies of individually appointed people. Giving each committee a fixed fraction of a large membership can instead describe an online voting assembly, and splitting a cohort by type can feel unlike appointing members. If the authors care essentially about small, deliberative committees, these mirrors miss their intended object.
That objection does not defeat Theorem 5.3, though. The formal problem uses voter identities only to enforce that a person serves on at most one committee; outcomes depend on rankings and committee sizes. A distribution over joint rankings across the two issues preserves the cross-issue correlations, and allocating disjoint masses to the two committees preserves the exclusivity constraint. Large membership organizations that form issue-specific online assemblies are a plausible regime. Since the paper does not model deliberation or identity-based selection, its formal question appears to survive that change of setting.
Theorem 6.1 has an even cleaner candidate mirror: select mass \(\alpha\) from a distribution of ranking types for one committee, and ask whether the designated alternative wins under \(r\)-Approval. The target’s score comparisons remain meaningful, including with the paper’s tie-breaking rule. The Exact Cover reduction relies on indivisible voter selection, so its hardness need not carry over; but that is a possible answer to the continuous question, not a reason the question is unworthy. Large membership bodies selecting substantial cohorts for an issue assembly provide a plausible interpretation here too.
I cannot make a strong universal case against these anchors. The paper has named computational results; the modeled objective does not track individual identities; and the continuous committee questions do not become meaningless simply because some members have measure zero. I know of no continuous treatment in the supplied material that already answers these computational questions. The small-committee objection is real for the paper’s motivating examples, but it does not rule out the alternative regime the proponent proposes. My negative case is therefore weak: both anchors appear to survive.
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.