| paper | Preferences Single-Peaked on a Tree: Multiwinner Elections and Structural Results |
| authors | Dominik Peters, Lan Yu, Hau Chan, Edith Elkind |
| venue | JAIR 2022 |
| filed under | multiwinner · multiwinner |
| judged by | gpt-5.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: NP-complete, even when the supplied tree has diameter \(4\) and pathwidth \(2\). · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 4.1
statement extracted from the paper’s text layer
Given candidates \(C\), a tree \(T\) on \(C\), a finite-support rational distribution \(\mu=(\mu_t)\) over complete ranking types \(\pi_t\) that are all single-peaked on \(T\), a committee size \(k\), and a rational threshold \(b\), decide whether there exists an integral committee \(W\subseteq C\) with \(|W|=k\) such that \(\sum_t \mu_t\bigl[-(\operatorname{pos}_{\pi_t}(\operatorname{top}_{\pi_t}(W))-1)\bigr]\ge b\).
A high-multiplicity electorate is represented by ranking types \(\pi_t\) carrying masses \(\mu_t\); the decision variable is an integral committee \(W\) of size \(k\), and the objective is its mass-weighted utilitarian Borda score.
The mirror covers utilitarian Chamberlin–Courant hardness on bounded-diameter and bounded-pathwidth trees, together with the few-leaf algorithmic regime. It leaves the egalitarian result, attachment-digraph structure, and tree-recognition results outside the main population mirror.
The strongest positive case is a genuine, narrow mirror for the paper’s utilitarian Chamberlin–Courant results. My lead anchor is Theorem 4.1; Theorem 5.1 gives a useful algorithmic companion.
Theorem 4.1, proved in this paper, states that given a profile \(P\) that is single-peaked on a tree, a committee size \(k\), and a threshold \(B\), deciding whether some size-\(k\) committee has Borda utilitarian Chamberlin–Courant score at least \(B\) is NP-complete. The hardness remains even when the supporting tree has diameter \(4\) and pathwidth \(2\). The proof reduces from Vertex Cover.
I would mirror it with the following problem.
Continuous Utilitarian Borda-CC on a Tree. An instance consists of candidates \(C\), a finite-support rational distribution \(\mu=(\mu_1,\ldots,\mu_\tau)\) over strict ranking types \(\pi_1,\ldots,\pi_\tau\), an integer \(k\), and a rational threshold \(b\). The positive-mass rankings are promised to be single-peaked on a common candidate tree \(T\); \(T\) may either be supplied or treated as part of the promise. A feasible solution is an integral committee \(W\subseteq C\) with \(|W|=k\). A type \(\pi_t\) is represented by its highest-ranked member of \(W\), and with the paper’s Borda vector \(s_r=-(r-1)\) its utility is
\[ u_t(W)=s_{\operatorname{pos}_{\pi_t}(\operatorname{top}_{\pi_t}(W))}. \]
The question is whether there exists \(W\) such that
\[ U_\mu(W)=\sum_{t=1}^{\tau}\mu_tu_t(W)\ge b. \]
The output, when solving the optimization version, is a maximizing committee \(W\).
This is population continuization, not outcome-space continuization: the committee remains an ordinary integral \(k\)-subset, and every individual receives an integral representative. Only the electorate becomes a distribution. A natural setting is the selection of \(k\) facilities or representatives for a very large population living on an acyclic transport or ideological network. Residents in the same district or demographic cohort may have the same complete ranking of facility sites. Their type mass is the fraction of the population in that cohort, and single-peakedness expresses preferences declining away from an ideal site along the common tree.
The high-multiplicity interpretation is especially credible here because it is already visible in the paper’s own reduction. In Theorem 4.1, the \(N_1\) voters contain \(5q\) identical copies of each vertex type, the \(N_3\) voters contain \(M=5pq\) identical copies of each vertex type, and the \(N_2\) voters contribute one type per edge. Thus the construction has at most \(2p+q\) distinct ranking types but a population of
\[ 5pq+Mp+q \]
voters. Replacing those multiplicities by normalized masses is not an artificial weakening; it exposes the repeated-type regime already carrying the paper’s hardness proof.
The discrete-to-continuous dictionary is exact. Given a finite profile with \(n_t\) voters of type \(t\), set \(\mu_t=n_t/N\), where \(N=\sum_tn_t\). Then
\[ U_\mu(W)=\frac{1}{N}\operatorname{score}^{+}(P,W). \]
Conversely, a rational distribution can be expanded into a finite profile by clearing denominators. Therefore the reduction in Theorem 4.1 immediately yields NP-hardness for the continuous problem, including the restrictions that the supporting tree has diameter \(4\) and pathwidth \(2\). Membership in NP holds for explicitly listed rational supports, since a committee is a polynomial-size certificate and its weighted score can be computed exactly. I therefore expect this mirror to be NP-complete: a clear Class B result, where the combinatorics live in candidate selection and Vertex Cover, not in the number of named voters.
The paper’s Theorem 5.1 supplies a second, algorithmic mirror. Proved here, it states that given a profile with \(m\) candidates and \(n\) voters, a tree \(T\) with \(\lambda\) leaves on which the profile is single-peaked, and a target committee size \(k\), a winning utilitarian Chamberlin–Courant committee can be found in time
\[ \operatorname{poly}(n,m^\lambda,k^\lambda). \]
The corresponding continuous problem is:
Continuous Tree-Structured CC with Few Leaves. The input is a rational type distribution \(\mu\), a common supporting tree \(T\) with \(\lambda\) leaves, a committee size \(k\), and the positional scoring data used by the paper. The task is to return an integral size-\(k\) committee maximizing the mass-weighted utilitarian score.
The paper’s dynamic programme survives directly. Every sum over voters is replaced by a rational weighted sum over types. The anti-chain decomposition of the tree is unchanged, and the algorithm still enumerates at most \(m^\lambda\) anti-chains and \(k^\lambda\) committee-size divisions. Its expected running time is therefore
\[ \operatorname{poly}(\tau,m^\lambda,k^\lambda,L), \]
where \(L\) is the encoding length of the masses and scoring data. For fixed \(\lambda\), this is polynomial in the compressed population description. This is a Class A result for the few-leaf regime, while Theorem 4.1 shows that arbitrary trees remain hard even under bounded diameter and pathwidth.
The two mirrors generate a useful boundary: high multiplicity does not dissolve the utilitarian CC hardness, but tree structure can still make the compressed distribution tractable. Further questions include whether the continuous problem is fixed-parameter tractable in \(\lambda\), whether hardness persists with very small \(\tau\), and whether one can efficiently choose a minimum-leaf supporting tree directly from the type distribution.
I would not claim to mirror the paper’s entire contribution. The egalitarian result, attachment-digraph structure, and NP-hardness of recognizing a particular tree shape are mainly structural or support-level statements; population mass either disappears from the objective or matters only through which types have positive support. The strongest case is specifically about the utilitarian Chamberlin–Courant problems.
The weakest point is that the proposed continuous problem is also a weighted-election reformulation: every rational distribution can be expanded into a finite profile. It therefore does not claim a continuum-specific algorithmic miracle. But that is not fatal under the ChoCo programme. The question is whether the high-multiplicity regime is sensible and whether the paper’s computational phenomenon survives there. Here the answer is strong: the authors’ own hardness reduction already uses many repeated voter types, the facility-on-a-tree interpretation is natural, the action remains genuinely discrete, and the continuous mirror yields both an exact hardness transfer and a compressed-population algorithmic regime.
The strongest negative case is that both proposed mirrors leave the population entirely passive. A distribution \(\mu\) is only a vector of coefficients in the committee objective; no mass is transferred, constrained, matched, or otherwise acted upon. Since a type is completely determined by its ranking, \(\mu\) is exactly a weighted histogram of the paper’s finite profile. Replacing repeated voters by rational masses therefore changes the encoding, but not the mathematical object being optimized.
This is especially clear for Theorem 4.1. For every committee \(W\),
\[ U_\mu(W)=\sum_t\mu_tu_t(W) =\frac{1}{N}\operatorname{score}^{+}(P,W). \]
The reduction’s repeated voters merely implement polynomially sized integer weights: it has \(2p+q\) ranking types and only polynomially many explicitly listed voters. Normalization gives a rational weighted-election instance, but no limiting or continuum-specific phenomenon. The hardness remains entirely in selecting candidates and encoding Vertex Cover. The facility-location story makes the weighted problem plausible, but does not make it a new population-computational problem.
Theorem 5.1 is an even weaker mirror in this respect. Its dynamic programme already aggregates voters only through sums of their utilities. Replacing those sums by rational weighted sums over types is immediate, giving the advertised \(\operatorname{poly}(\tau,m^\lambda,k^\lambda,L)\) bound. This is a useful compressed-input observation, but not a new continuous optimization result: the anti-chain decomposition, feasible committees, and recurrence are unchanged. The same is true if one uses the attachment-digraph algorithms to choose a supporting tree; duplicate voter copies never affect the digraph.
The natural ways to make the population genuinely active do not rescue these anchors. Allowing fractional committee membership would continuize the outcome space, which is outside the programme. Allowing population mass to move between preference types would create a bribery or control problem absent from the paper. Introducing locations, demographics, or identities that affect utilities would produce a different model rather than a continuization of Chamberlin–Courant.
That said, this negative case does not honestly defeat the proponent under ChoCo’s stated rules. The proposed weighted CC problem is well-posed, the high-multiplicity interpretation is credible, and neither identity dependence nor degeneracy applies. Theorem 4.1 is a legitimate Class B mirror even though its answer is inherited from the discrete problem, and Theorem 5.1 is a legitimate compressed-population algorithm. Thus the claim that no worthwhile mirror exists in any scenario is too strong; the defensible criticism is only that the mirror is modest and representational rather than a genuinely new continuous phenomenon.
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.