| paper | Computing Pareto Optimal Committees |
| authors | H. Aziz, J. Lang, J. Monnot |
| venue | IJCAI 2016 |
| 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: \(\mathrm{NP}\)-complete, even for dichotomous instances with \(\operatorname{Topwidth}=3\) and equal positive masses; also \(\mathrm{NP}\)-complete for strict preferences. Polynomial-time solvable for dichotomous instances with \(\operatorname{Topwidth}\le2\). · discrete side: hardness · adjudication: proved_with_minor_gaps
full proof & adversarial review →
Theorem 2
statement extracted from the paper’s text layer
Given a finite alternative set \(A\), committee size \(k\), a rational distribution \(\mu\) over complete weak-order types, and \(D\in\binom{A}{k}\), decide whether there exists \(W\in\binom{A}{k}\) such that \(W\succeq_t^{\mathrm{RS}}D\) for every type with \(\mu_t>0\), while \(\mu(\{t:W\succ_t^{\mathrm{RS}}D\})>0\). The question applies in particular to dichotomous types with \(\operatorname{Topwidth}\ge 3\), and asks whether \(D\) is continuously RS-efficient.
A high-multiplicity committee election in which types are complete weak orders on \(A\), \(\mu\) assigns mass to types, committees remain integral, and the decision concerns support-wide ordinal Pareto comparisons under the responsive extension.
The mirror covers the \(B\)-efficiency hardness of Theorem 8 and responsive-efficiency verification in Theorem 2, with Theorem 4 suggesting a \(\operatorname{Topwidth}\le 2\) tractable boundary. It leaves the strategyproof mechanisms, leximax and worst extensions, and other results without a continuous formulation.
The strongest honest case is that this paper admits a clean high-multiplicity mirror, although it is likely a Class B mirror: the discrete hardness survives rather than dissolving.
Take a finite alternative set \(A\), committee size \(k\), and let \(T\) be the finite set of weak orders over \(A\). A continuous society is a rational distribution \(\mu\) over \(T\). Thus \(\mu_t\) is the fraction of constituents whose complete preference description is type \(t\). Zero-mass types are omitted.
The outcome remains an ordinary committee \(W\in\binom{A}{k}\). There is no fractional committee and no lottery. For either set extension \(E\in\{\mathrm{RS},\mathrm{B}\}\), write \(W\succeq_t^E V\) for the preference between committees induced by type \(t\) in the paper. Say that \(W\) is a continuous Pareto improvement over \(V\) if
\[ W\succeq_t^E V \quad\text{for every }t\text{ with }\mu_t>0, \]
and
\[ \mu\bigl(\{t:W\succ_t^E V\}\bigr)>0. \]
Because \(T\) is finite, the second condition simply says that at least one positive-mass type strictly improves. A committee is continuously \(E\)-efficient if no such improvement exists.
This is the natural continuum version of the paper’s Pareto notion. It does not replace ordinal preferences by expected utilities, and it does not continuize the outcome space. It only replaces a list of individual agents by the distribution of preference types.
The regime is plausible for a large association, electorate, university consortium, or organization choosing \(k\) projects from a common slate of \(m\) alternatives. Constituents may belong to many large blocs—regions, professions, departments, or interest groups—with identical weak rankings over the slate. If there are \(r\) such types and each occurs \(M\) times, then the underlying population has \(n=Mr\) agents with \(r\ll n\). The paper’s constructions can be placed in this regime by replicating every constructed type \(M\) times. Replication changes neither Pareto dominance nor Pareto efficiency.
My lead anchor is Theorem 8. The paper proves, by a reduction from HITTING SET:
Theorem 8. Computing a \(B\)-efficient committee is NP-hard, even for dichotomous preferences.
The corresponding continuous problem is:
Continuous \(B\)-Efficient Committee. Given \(A\), \(k\), and a rational type distribution \(\mu\) over dichotomous weak orders, output some \(W\in\binom{A}{k}\) for which there is no \(V\in\binom{A}{k}\) satisfying \(V\succeq_t^B W\) for every positive-mass type \(t\), with strict improvement for at least one positive-mass type.
This is exactly the underlying problem computed in Theorem 8, with the finite profile replaced by its type distribution. It is not a softened optimization problem: the committee is still integral, the best-extension relation is unchanged, and the question is still whether any committee Pareto-dominates the output.
I would expect this continuous problem to remain NP-hard, most naturally as a Class B result. Every discrete profile maps to \(\mu_t=n_t/n\), and every rational \(\mu\) can be expanded into a finite profile by taking a common denominator. More importantly, the HITTING SET reduction is driven by the alternative/set-system structure, not by having many distinct named agents. Giving every constructed type positive mass, then multiplying all cohort sizes by \(M\), produces arbitrarily large high-multiplicity populations with the same answer.
The second anchor is Theorem 2, also proved in the paper, via VERTEX COVER:
Theorem 2. Checking whether a committee is Pareto optimal under the responsive set extension is coNP-complete, even for dichotomous preferences and \(\operatorname{Topwidth}(\%)\ge 3\), or for strict preferences.
The corresponding continuous problem is:
Continuous RS-Efficiency Checking. Given \(A\), \(k\), a rational distribution \(\mu\) over weak orders, and a committee \(D\in\binom{A}{k}\), decide whether there exists \(W\in\binom{A}{k}\) such that \(W\succeq_t^{\mathrm{RS}}D\) for every type \(t\) with \(\mu_t>0\), with \(W\succ_t^{\mathrm{RS}}D\) for a positive-mass type.
Equivalently, decide whether \(D\) is continuously RS-efficient. The problem should remain coNP-complete for dichotomous distributions whose positive-mass types have top width at least \(3\), and also for distributions of strict preference types. In the paper’s reduction, every edge-agent preference can become a positive-mass type, while the special agent becomes another positive-mass type. The continuous improvement condition is then exactly the finite one.
This second mirror is independently valuable because it concerns verification rather than construction. It also exposes a genuine boundary: the paper’s Theorem 4 gives a polynomial-time algorithm for finding an RS Pareto improvement under dichotomous preferences with \(\operatorname{Topwidth}(\%)\le 2\). Thus the continuous version would inherit a sharp contrast between the top-width-\(2\) regime and the top-width-\(3\) regime.
The mirror covers only the paper’s Pareto-efficiency results for the \(B\) and responsive extensions. It does not claim to continuize the strategyproof mechanisms, the leximax or worst extensions, or the committee itself.
The weakest point is that Pareto efficiency is replication-invariant. The numerical values of \(\mu_t\) largely disappear; only the positive-mass support matters. An opponent can therefore fairly say that this is a continuous population quotient, not a new LP-like optimization problem in which mass enters the objective. I would concede that. But it is also exactly what a faithful continuum mirror should reveal here: the paper’s hardness is caused by the combinatorics of alternatives and preference types, not by population multiplicity. The result is therefore not a tractability claim, but a precise negative boundary for continuization: these discrete hardness results remain hard even for arbitrarily large populations composed of repeated preference cohorts.
The strongest negative case is that Pareto efficiency destroys exactly the population quantity that continuization would introduce.
Let \(S_\mu=\{t:\mu_t>0\}\). For any extension \(E\), a continuous Pareto improvement from \(W\) to \(V\) satisfies
\[ V\succeq_t^E W \quad\text{for every }t\in S_\mu, \]
and
\[ \sum_{t:V\succ_t^E W}\mu_t>0. \]
Because the set of weak orders is finite, the second condition is equivalent to saying that at least one \(t\in S_\mu\) strictly improves. Therefore continuous \(E\)-efficiency depends only on \(S_\mu\), not on any value of \(\mu_t\). Every two distributions with the same support induce exactly the same efficient committees.
This is more than a dull computational answer. The population measure has disappeared from the problem. The proposed mirror is a finite support quotient of the original profile, not a computational problem about a continuous society. Replicating every type \(M\) times, changing the proportions, or making one bloc arbitrarily small has no effect. A richer type space cannot repair this: all four extensions factor through the induced weak order, so its measure can simply be pushed forward onto the finite set of weak orders.
Theorem 8 does not escape this problem. Its HITTING SET reduction is driven by which dichotomous preference types occur, not by how much mass they carry. The continuous version is therefore exactly the same support problem after deleting the \(\mu_t\)'s. That is a legitimate high-multiplicity reformulation, but it does not make the population continuous in the sense relevant to ChoCo; it merely compresses repeated rows of the input.
Theorem 2 is even less promising. The \(k\) agents associated with each edge in the reduction can be collapsed immediately into one edge type. The special agent supplies one further type. The coNP-hardness is consequently already a hardness result over a finite set of preference types. The claimed top-width boundary also concerns the support types alone; no population fraction enters it.
A better proposed mirror would have to make mass matter—for example, requiring a Pareto improvement for at least \(\delta\) mass, maximizing the mass that strictly improves, or assigning cardinal utilities and aggregating them. But each of these changes the paper’s problem. The paper supplies only ordinal set extensions, so there is no canonical way to measure the intensity of an improvement; \(\delta\) would be a new parameter and a weighted objective would be a new welfare problem. Fractional committees or lotteries would instead continuize the outcome space, which is outside the programme’s scope.
The honest limitation is that this does not show the two proposed questions are ill-posed. If ChoCo is willing to count a support-only high-multiplicity quotient as a worthwhile mirror, then the proponent’s anchors survive, most naturally as Class B results. The negative case is therefore conditional but substantial: under the programme’s stronger requirement that the society itself be a computationally operative continuous object, this paper offers no such mirror.
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.