| paper | On the Complexity of Calculating Approval-Based Winners in Candidates-Embedded Metrics |
| authors | Yongjie Yang |
| venue | IJCAI 2022 |
| filed under | multiwinner · multiwinner |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c22r1) |
| judge confidence | high |
| authors would recognise it | yes |
Theorem 5
statement extracted from the paper’s text layer
Given candidates \(C\), a rational metric \(f\), committee size \(k\), a finite support \(S\) of nonempty approval-set types \(v\subseteq C\) with rational masses \(\mu_v>0\) summing to \(1\), and rational threshold \(\theta\), decide whether some \(W\subseteq C\) with \(|W|=k\) satisfies \(\sum_{v\in S}\mu_v\max_{c\in W}\min_{a\in v}f(a,c)\leq\theta\).
Finite approval-set types \(v\subseteq C\) with rational masses \(\mu_v\), a rational candidate metric \(f\), discrete committee variable \(W\) with \(|W|=k\), and a weighted utilitarian maximum-distance objective.
Theorem 5's immediate reduction only proves hardness for an explicitly supported weighted formulation and leaves open whether small type support τ changes the complexity; this limits the continuous novelty but does not invalidate the mirror.
fatal: False
The mirror covers Theorem 5, Corollary 2, and Theorem 4, while leaving the other UWD/EWD variants, approximation bounds, and FPT results untreated.
The strongest honest case is that this paper admits a faithful population mirror, with Theorem 5 as the lead anchor. The mirror is not a relaxation of the committee, the candidate metric, or the approval rule. It changes only the multiset of voters into a distribution over voter types.
Let \(C\) be the candidates, \(f\) the rational metric, and let a voter type be a nonempty approval set \(v\subseteq C\). Two voters have the same type exactly when they approve the same candidates; this is a complete description of everything the paper’s objective uses. A continuous society is a rational distribution \(\mu=(\mu_v)\) over these types, with \(\sum_v\mu_v=1\). Define
\[ d_f(v,c)=\min_{a\in v} f(a,c). \]
The action remains a discrete \(k\)-committee \(W\subseteq C\), \(|W|=k\). Population mass enters through the objective: if \(n_v\) voters have type \(v\), then \(\mu_v=n_v/N\), and the continuous objective is exactly the discrete objective divided by \(N\).
The plausible regime is a large service, travel, or library platform with millions of users but only a few hundred recurring approval profiles. For example, candidates may be possible facilities or destinations embedded in a travel-time metric; users may fall into types such as “approves all sites within budget and near public transport.” The number of people is then much larger than the number \(\tau\) of distinct approval types. This is recognisably the paper’s problem: candidates remain metrically related, votes remain arbitrary approval sets, and the decision is still which \(k\) candidates to select.
My lead anchor is the paper’s Theorem 5, proved in this paper:
“UWD-MAX is NP-complete, and is W[2]-hard w.r.t. \(k\). This holds even when restricted to path-metrics, star-metrics, and discrete metrics.”
The corresponding continuous problem, which I would call \(\mathrm{UWD\text{-}MAX}_\infty\), is:
Given \(C\), a rational metric \(f\), \(k\), a finite support \(S\) of approval types with rational masses \(\mu_v>0\), and a rational threshold \(\theta\), decide whether there is a \(k\)-committee \(W\) such that
\[ \sum_{v\in S}\mu_v \max_{c\in W} d_f(v,c) \leq \theta. \]
A solution is the committee \(W\); the optimization version asks for the minimizing committee.
This is a direct high-multiplicity form of the theorem’s problem. Given a discrete instance with \(n_v\) copies of each vote, set \(\mu_v=n_v/N\) and \(\theta=s/N\). Every committee has exactly the same objective comparison as in the discrete instance. The reduction therefore preserves NP-hardness and W[2]-hardness, including the path-, star-, and discrete-metric restrictions. I expect this mirror to be Class B: the combinatorics live in selecting candidates and committees, not in the mere number of duplicate voters.
The main follow-up question is whether the hardness survives in a genuinely compressed regime with \(\tau\ll N\), rather than merely under the unrestricted explicit-support formulation. The theorem’s transfer establishes the mirror and its boundary, but not hardness parameterized by \(\tau\). That is precisely a useful continuous question: does small type support yield algorithms, approximation schemes, or new parameterized classifications?
A second, very clean hardness anchor is Corollary 2, stated in this paper but inherited directly from Betzler et al. [2013, Theorem 2]:
“For all metrics, UWD-MIN is NP-complete and W[2]-hard w.r.t. \(k\). This holds even if \(s=0\).”
Its mirror, \(\mathrm{UWD\text{-}MIN}_\infty\), asks whether there is a \(k\)-committee \(W\) satisfying
\[ \sum_{v\in S}\mu_v \min_{c\in W} d_f(v,c) \leq \theta. \]
At \(\theta=0\), this becomes especially transparent. Since \(f\) is a metric, \(d_f(v,c)=0\) exactly when \(c\in v\). Thus the question is whether \(W\) intersects every positive-mass approval type. It is the continuous weighted-support version of the hitting-set interpretation underlying the paper’s reduction. The expected classification is again Class B, with hardness transferring exactly.
This anchor is slightly weaker as evidence for the value of mass: at threshold zero, the actual values of the positive masses do not matter, only their support. I would include it because it gives an exceptionally robust boundary result—hardness for every metric and already at zero threshold—not because it supplies a distinct mass-sensitive phenomenon. Further questions include whether nonzero thresholds and bounded type support produce a richer continuous landscape.
The algorithmic companion is Theorem 4, proved here:
“UWD-MIN restricted to path-metrics can be solved in \(O(m^6\cdot n)\) time when the candidates in every vote are consecutive in the path-witness.”
The corresponding problem, \(\mathrm{Path\text{-}Interval\text{-}UWD\text{-}MIN}_\infty\), has the same input as \(\mathrm{UWD\text{-}MIN}_\infty\), but \(f\) is a path metric and every positive-mass approval type is an interval in the path order. It asks for a \(k\)-committee minimizing
\[ \sum_{v\in S}\mu_v \min_{c\in W}\min_{a\in v} f(a,c), \]
or, in decision form, whether this value is at most \(\theta\).
The dynamic programme in Theorem 4 extends directly: every sum over repeated votes becomes a weighted sum over types. The resulting running time is polynomial in \(m\), \(\tau\), and the rational encoding length, essentially \(O(m^6\tau)\) arithmetic operations before bit-complexity factors. This is a genuine Class A mirror in the high-multiplicity regime: the algorithm depends on the number of distinct interval types, not on the number of people. It is also plainly recognisable to the authors, since nothing about the objective or feasible committees has been softened; only the representation of the multiset has changed.
I am not claiming to mirror all six winner-determination variants, every FPT table entry, or the approximation results. These three anchors already cover a meaningful slice: broad hardness for utilitarian maximum distance, zero-threshold hardness for utilitarian minimum distance, and a structured tractable regime for the latter.
The weakest point is that, outside the interval-path result, the proposed mirrors can look like weighted-vote notation rather than a deep new continuous theory. Moreover, Theorem 5’s transferred hardness does not by itself prove hardness when the population is massively larger than its type support. But that weakness does not defeat the case: the paper’s multiset-vote model has exactly the right sufficient statistic for high multiplicity, its applications naturally admit repeated approval profiles, and Theorem 4 shows that replacing \(n\) by \(\tau\) can materially change the computational formulation. The right conclusion is therefore a modest but solid one: this paper supports a credible population continuization, with both transferred hardness and a real type-compressed algorithmic regime.
The strongest negative case is that the paper’s population is already exactly aggregatable. If \(h(v,W)\) denotes any of its voter–committee distances, then a multiset of votes contributes
\[ \sum_{v\in V} h(v,W)=\sum_{t} n_t h(t,W), \]
while an egalitarian objective depends only on the support. Thus the proposed mirror is a weighted high-multiplicity reformulation, not a new population-level object. Theorem 5’s reduction transfers immediately by setting \(\mu_t=n_t/N\), but that shows only that the explicitly supported weighted problem is hard. It says nothing about the genuinely compressed regime \(\tau\ll N\), which is the only place where continuity could add algorithmic value.
That objection is real for Theorem 5, but it does not defeat the mirror. A large platform with many users sharing a small number of approval profiles is a credible high-multiplicity regime. The approval set is a complete type because the paper’s objective uses no other voter information. Even if users originate from a richer continuous feature space—budgets, locations, transport preferences—pushing that distribution forward to approval sets gives precisely the proposed \(\mu\). Theorem 5 therefore supplies a legitimate continuous question, even if its transferred hardness does not establish hardness parameterized by \(\tau\).
Corollary 2 is weaker. At threshold \(0\),
\[ \sum_t \mu_t\min_{c\in W}d_f(t,c)\le 0 \]
depends only on which types have positive mass; the numerical masses disappear. This is a support problem, not a mass-sensitive one. But the stronger version with a positive threshold is perfectly well-defined and genuinely weight-dependent. The zero-threshold theorem cannot rule it out.
Theorem 4 is the decisive obstacle to a negative verdict. Its dynamic programme really does extend from vote multiplicities to rational type masses: every count becomes a weighted sum, and its running time becomes polynomial in \(m\), \(\tau\), and the encoding length of the masses. Interval approval types can naturally represent large cohorts of users. This is exactly the kind of high-multiplicity compression the programme is intended to study, and it preserves the candidates, metric, committees, and objective.
Consequently, I cannot honestly defeat every anchor. There is no identity dependence, no absence of plausible multiplicity regime, and no degeneration of the continuous objective. Nor is there an existing continuous computational treatment supplied by the paper. The most defensible criticism is that Theorems 5 and 2 should not be oversold as continuous-specific results: their immediate transfers are weighted reformulations, and the interesting \(\tau\)-parameterized landscape remains open. But Theorem 4 survives as a worthwhile Class A mirror. The universal negative case is therefore weak; this paper should be greened, cautiously, on the strength of its path-interval result.
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.