| paper | Proportional Rankings |
| authors | P. Skowron, M. Lackner, Markus Brill, Dominik Peters, Edith Elkind |
| venue | IJCAI 2017 |
| 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}\text{-complete}\), even with dyadic masses and threshold · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Proposition 1
statement extracted from the paper’s text layer
Given alternatives \(A\), approval types \(T\subseteq 2^A\), rational masses \(\mu_t\ge 0\) summing to \(1\), \(\alpha\in(0,1]\cap\mathbb{Q}\), and \(\lambda\in\mathbb{N}\), decide whether there exist masses \(z_t\in[0,\mu_t]\) with \(\sum_t z_t=\alpha\) and \(\left|\bigcap_{t:z_t>0}A_t\right|\ge\lambda\). Equivalently, decide whether some \(B\subseteq A\) with \(|B|=\lambda\) satisfies \(\sum_{t:B\subseteq A_t}\mu_t\ge\alpha\).
A society consists of approval types \(A_t\subseteq A\) with masses \(\mu_t\). The decision variables \(z_t\) select a subpopulation of total mass \(\alpha\); the objective is feasibility, or equivalently maximizing the mass supporting a common approval set \(B\) of size \(\lambda\).
The continuous significant-group problem eliminates most of the population decision once a common approval set \(B\) is fixed, reducing it to a weighted common-intersection problem over discrete alternatives; this may yield limited new continuous optimization structure.
fatal: False
The mirror directly covers Proposition 1 and gives a plausible extension of Theorem 1. It does not establish continuous versions of Theorems 2–6 or the experimental findings.
The strongest positive case is a genuine high-multiplicity version of the paper’s central problem: keep the alternatives and the output ranking discrete, but replace the finite voter list by a distribution over approval types. My lead anchor is Theorem 1.
Consider a search, recommendation, or liquid-democracy platform with millions of users but only \(\tau\) recurring approval profiles. A type is an approval set \(A_t\subseteq A\), and \(\mu_t\) is the fraction of users of that type. This is a credible regime when users are clustered by query intent, topic interest, or recurring proposal preferences: the number of users is enormous, while the number of distinct approval profiles is much smaller. The type is complete for the paper’s model, since approval sets are the only information used.
For a continuous society, let \(z_t\in[0,\mu_t]\) describe a measurable subpopulation selected from type \(t\). Its mass is \(a(z)=\sum_t z_t\), its common approval set is \(I(z)=\bigcap_{t:z_t>0}A_t\), and its cohesiveness is \(\lambda(z)=|I(z)|\). For a prefix \(S\subseteq A\) of a ranking, its average representation is \(\operatorname{avg}_\mu(z,S)=\frac{1}{a(z)}\sum_t z_t|A_t\cap S|\). The continuous analogue of justifiable demand is \(\operatorname{jd}_\mu(z,k)=\min(\lfloor a(z)k\rfloor,\lambda(z))\).
This gives the following precise problem.
Continuous Optimal Proportional Ranking\(_\infty\) — Given alternatives \(A\), a finite set of approval types \(T\subseteq 2^A\), and rational masses \(\mu_t\) summing to \(1\), find a ranking \(r\) maximizing
\[ q_\mu(r)=\inf_{\substack{k\in[m],\,z\\ \operatorname{jd}_\mu(z,k)>0}} \frac{\operatorname{avg}_\mu(z,r_{\le k})} {\operatorname{jd}_\mu(z,k)}. \]
The decision version asks whether there exists a ranking \(r\) with \(q_\mu(r)\ge 1\). The output remains an ordinary permutation of the alternatives; only the society has been continuized. This is therefore not an outcome-space relaxation and not merely a rewriting of \(|N'|/|N|\) as a percentage.
Theorem 1 is the lead anchor. It states: given a finite approval profile \(P\), it is NP-hard to decide whether there exists a ranking \(r\) with \(q_P(r)\ge 1\), where \(q_P\) is the paper’s worst-case ratio of average representation to justifiable demand over every voter group and every prefix. The theorem is proved in this paper, using a reduction from 3-regular VERTEX COVER; the source problem’s NP-hardness is cited to Garey and Johnson.
The reduction constructs, from a graph \(G=(V,E)\) and an integer \(\ell\), alternatives \(A=V\cup\{d\}\). For every edge \(\{a,b\}\in E\), it creates a voter approving exactly \(\{a,b\}\). It adds \(3\ell+3-|E|\) dummy voters approving only \(d\), so that \(n=3\ell+3\). Since the graph is 3-regular, \(m=2|E|/3+1\le 3\ell\). The paper proves that \(G\) has a vertex cover of size \(\ell\) if and only if the resulting profile admits a ranking with \(q_P(r)\ge1\).
The continuous question above is a faithful mirror of that result. The ranking is still required to satisfy every cohesive group at every prefix; the only change is that a type class is divisible. The natural expectation is that hardness transfers, placing this problem in Class B. The combinatorics in the reduction live primarily in the incidence structure between alternatives and approval sets, not in the existence of millions of individually named voters. A finite construction can be represented by its type masses, and every type can be replicated arbitrarily many times without changing \(\mu\), producing a genuinely high-multiplicity population.
That transfer is not automatic: fractional subpopulations may weaken the exact Vertex Cover gadget, so a new mass-aware reduction would be needed. But that is a technical question about the continuous complexity landscape, not a reason to reject the mirror. The problem remains recognisably the authors’ own optimization problem, with the same objective, same rankings, same groups, and same proportionality requirement.
The paper’s Proposition 1 gives a second, particularly clean anchor. It states that deciding whether there exists an \((\alpha,\lambda)\)-significant group is NP-complete. Such a group must contain exactly \(\lceil\alpha n\rceil\) voters and have cohesiveness at least \(\lambda\), meaning that at least \(\lambda\) alternatives are approved by every voter in the group. This proposition is proved in the paper by a reduction from Maximum \(k\)-Subset Intersection; Xavier’s work is cited for the source problem.
Its continuous counterpart is:
Continuous Significant-Group Detection\(_\infty\) — Given \(A\), approval types \(T\), rational masses \(\mu\), \(\alpha\in(0,1]\cap\mathbb{Q}\), and \(\lambda\in\mathbb{N}\), decide whether there is a measurable subpopulation \(z\) with total mass \(\alpha\) and \(|I(z)|\ge\lambda\). Equivalently, decide whether there exists \(B\subseteq A\) with \(|B|\ge\lambda\) such that
\[ \sum_{t:B\subseteq A_t}\mu_t\ge\alpha. \]
A solution is the common approved set \(B\), together with the selected mass \(z\); the optimization version maximizes the mass supporting some \(\lambda\)-element common set.
Here the high-multiplicity dictionary is especially strong. Given a finite profile, set \(\mu_t\) equal to the fraction of voters having approval type \(t\). For a threshold \(\alpha=k/n\), the continuous condition says exactly that at least \(k\) voters approve every alternative in \(B\), which is exactly the finite significant-group condition. Repeating every voter, or every type class, makes the number of agents arbitrarily larger than the number of types without changing the continuous instance. Thus Proposition 1 supplies a direct hardness-transfer candidate rather than a merely metaphorical analogy. I would expect this problem also to be Class B.
This mirror would be plausible to the original authors because proportionality is already expressed in terms of population fractions and cohesive groups. The continuous formulation preserves the substantive question: which alternatives should appear early enough in one collective ranking to serve every sufficiently large, internally consistent constituency? It does not replace rankings by fractional rankings, make alternatives divisible, or change the proportionality criterion into an unrelated average-case objective.
The mirror covers Theorem 1 and Proposition 1 emphatically. I would not claim that it automatically covers Theorems 2–6 or the experiments. Those results concern guarantees of particular finite-profile rules, and their continuous versions would require separate work. For example, weighted-type versions of AV or SeqPAV are natural, but proving that their \(\kappa\)-group guarantees survive arbitrary measurable subpopulations is a distinct theorem.
The main further questions are whether Continuous Optimal Proportional Ranking\(_\infty\) remains NP-hard, whether its continuous feasibility constraints admit a separation oracle, and whether one can obtain approximation or parameterized algorithms in \(m\), \(\tau\), or \(\lambda\). Continuous Significant-Group Detection\(_\infty\) also isolates a weighted maximum-common-approval problem that may itself be a useful Class B or Class C boundary problem.
My weakest point is that Theorem 1’s particular Vertex Cover reduction has not been shown in the paper to survive fractional type masses. The finite optimum might relax after agents of one type can be divided continuously. That objection is real. It weakens the claim that the theorem’s exact NP-hardness transfers, but not the case for the mirror: Proposition 1 has a much cleaner mass-preserving correspondence, and the ranking problem remains precisely the paper’s central problem in a credible high-multiplicity regime.
The strongest negative case is that the proponent overstates Theorem 1. Its reduction does not exhibit a high-multiplicity population regime. There is essentially one voter type for each graph edge, plus the dummy type: in a generic instance, \(\tau=\Theta(|E|)=\Theta(n)\). The combinatorial information is encoded by distinct approval types, not by many interchangeable voters. Cloning every edge voter \(K\) times makes the electorate large, but leaves the type description unchanged and contributes no new continuous structure. Worse, the paper’s vertex-cover equivalence has not been shown to survive fractional selection of subpopulations within types. Thus Theorem 1 supplies a plausible weighted variant, but not yet a convincing continuization result.
A stronger version could seek a mass-aware reduction with few recurring approval types, but that would be a new theorem rather than a mirror delivered by this paper. The natural search-engine story also does not rescue the specific reduction: users repeatedly expressing one of a small number of approval sets are plausible, but the hardness construction itself requires a graph-sized collection of distinct approval patterns. This makes Theorem 1 a weak anchor for the programme’s population-continuum agenda.
Proposition 1 is much harder to defeat. For a continuous society, define
\[ w(B)=\sum_{t:B\subseteq A_t}\mu_t . \]
A measurable subpopulation of mass \(\alpha\) with at least \(\lambda\) commonly approved alternatives exists exactly when
\[ \exists B\subseteq A,\quad |B|=\lambda,\quad w(B)\ge \alpha . \]
The forward direction takes \(B\) inside the group’s common approval set. For the reverse direction, select mass \(\alpha\) from the types containing \(B\); divisibility makes this possible. With \(\mu_t=n_t/n\) and \(\alpha=k/n\), this is exactly the finite condition that at least \(k\) voters jointly approve \(B\).
The best objection is that this “continuous” problem eliminates the population variable entirely. Once \(B\) is fixed, one simply takes all available mass supporting \(B\), with at most one type partially used. The remaining problem is a weighted common-intersection problem over discrete alternatives. It creates no configuration LP, no genuinely fractional ranking, and no continuous optimization phenomenon. But that is not a decisive objection under the programme’s rules: it is still a legitimate high-multiplicity version of a named NP-complete problem, and the fact that the population can be compressed to type weights is precisely what high multiplicity means. Calling it a mere restatement would incorrectly treat high-multiplicity structure as a collision.
The remaining theorems are bounds for particular ranking rules and experimental observations, not additional computational anchors. Their inequalities would in fact admit fairly natural mass-weighted reformulations, although those would be analytic guarantees rather than the programme’s main complexity contribution.
So the honest negative case is limited: Theorem 1 does not itself establish a meaningful high-multiplicity hardness family, and the proposed ranking mirror still lacks a mass-aware theorem. But I cannot defeat Proposition 1 without relying on arguments the brief expressly rules out. Its continuous significant-group problem is well-posed, faithful, and plausibly worth studying. The universal claim that no worthwhile continuous mirror exists therefore cannot be sustained.
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.