| paper | Diversity, Agreement, and Polarization in Elections |
| authors | Piotr Faliszewski, Andrzej Kaczmarczyk, Krzysztof Sornat, Stanisław Szufa, Tomasz Wąs |
| venue | IJCAI 2023 |
| filed under | voting · theory |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c2r1) |
| judge confidence | high |
| authors would recognise it | yes |
Theorem 3
statement extracted from the paper’s text layer
Given candidates \(C\), a finite set of ranking types \(T\subseteq S_C\), rational masses \(\mu_t>0\) summing to \(1\), an integer \(k\), and rational threshold \(B\), decide whether there exists \(\Lambda\subseteq T\) with \(|\Lambda|\le k\) such that \(\sum_{t\in T}\mu_t\min_{\lambda\in\Lambda}\operatorname{swap}(t,\lambda)\le B\); the optimization version minimizes this quantity.
A high-multiplicity electorate represented by ranking types \(T\), rational population masses \(\mu\), and \(k\) representative rankings chosen from \(T\), minimizing weighted nearest-representative Kendall-\(\tau\) distance.
The mirror covers the computational \(k\)-KEMENY core, including Theorem 3 and Corollary 1; it leaves the diversity and polarization interpretations, MDS visualizations, statistical-culture experiments, and empirical validation largely untouched.
The strongest positive case is a direct high-multiplicity mirror of the paper’s \(k\)-Kemeny problems. My lead anchor is Theorem 3.
Let \(C\) be the candidate set and let \(T\subseteq S_C\) be a finite set of distinct rankings. A type \(t\in T\) is a complete ranking, exactly as in the paper; two voters are the same type because the paper uses no information about them beyond their rankings. A continuous society is a rational distribution \(\mu=(\mu_t)_{t\in T}\), where \(\mu_t\) is the fraction of voters of type \(t\). For a set \(\Lambda\) of \(k\) representative rankings, define
\[ \Phi_\mu(\Lambda)=\sum_{t\in T}\mu_t\min_{\lambda\in\Lambda}\operatorname{swap}(t,\lambda). \]
Thus the decision variable is the set of representative rankings, and the objective is average Kendall-\(\tau\) distance to the closest representative. If \(\mu_t=n_t/n\), then \(n\Phi_\mu(\Lambda)\) is exactly the paper’s discrete \(k\)-Kemeny objective.
This is a plausible high-multiplicity regime: a large electorate ranks a fixed slate of policy proposals, perhaps through repeated ballots within constituencies, demographic segments, parties, or organizational blocs. There may be millions of voters but only \(\tau\) distinct rankings, with \(\tau\ll n\). The representatives can be interpreted exactly as the paper interprets them: a small collection of coherent societal positions or “factions” minimizing total disagreement.
The lead problem is Weighted \(k\)-KEMENY-AMONG-TYPES\(_\infty\). An instance consists of \(C\), distinct rankings \(T=\{t_1,\ldots,t_\tau\}\), positive rational masses \(\mu_i\) summing to \(1\), an integer \(k\), and a rational threshold \(B\). The question is whether there exists \(\Lambda\subseteq T\), \(|\Lambda|\le k\), such that
\[ \sum_{i=1}^{\tau}\mu_i\min_{\lambda\in\Lambda} \operatorname{swap}(t_i,\lambda)\le B. \]
The optimization version asks for such a \(\Lambda\) of minimum cost.
This is a direct continuous counterpart of the paper’s \(k\)-KEMENY AMONG VOTES, not a weakened substitute: “among votes” becomes “among positive-mass types.” The paper’s Theorem 3, proved in this paper, states that \(k\)-KEMENY AMONG VOTES is NP-complete and \(W[2]\)-hard parameterized by \(k\). The reduction itself strongly supports the mirror. For every set-voter \(v_j\), the construction creates \(L=N(M+4)\) identical copies, and the authors explicitly say that these copies need not be distinguished. Replace those copies by one type of mass \(L/n\), and give each element-voter type mass \(1/n\), where \(n=ML+N\). Set the continuous threshold to \(D/n\). Every solution then has exactly the same normalized cost as in the discrete reduction.
Indeed, the reduction has only \(M+N\) relevant voter types but \(n=N(M^2+4M+1)\) voters. The population multiplicity is therefore compressed away without removing the reduction. The combinatorics live in selecting \(K\) set-types and in the ranking geometry, not in the identities of individual voters. I expect this problem to remain NP-complete and \(W[2]\)-hard parameterized by \(k\): a clear Class B result. This is my strongest anchor because the paper’s own hardness proof already exhibits the repeated-type regime.
My second anchor is Corollary 1, which is proved in the paper from Theorem 1 and cited \(k\)-median approximation algorithms. It states that there is a polynomial-time \(5.4\)-approximation algorithm for \(k\)-KEMENY.
The corresponding problem is Weighted \(k\)-KEMENY\(_\infty\)-Approx. The input is \(C\), a rational distribution \(\mu\) over \(\tau\) rankings, \(k\), and the approximation parameter \(\epsilon\) if a variable guarantee is requested. The output is a set \(\Lambda\) of \(k\) arbitrary rankings from \(S_C\) satisfying
\[ \Phi_\mu(\Lambda)\le 5.4\, \min_{\Lambda'\subseteq S_C,\ |\Lambda'|\le k} \Phi_\mu(\Lambda'). \]
The paper’s algorithm survives aggregation: use the distinct support rankings as weighted clients and as the restricted facility set, run the polynomial-time \(2.7\)-approximation for weighted \(k\)-median, and apply the paper’s Theorem 1. Its triangle-inequality argument is unchanged when each client term is multiplied by \(\mu_t\), yielding the factor \(2\cdot 2.7=5.4\). The running time should be polynomial in \(m\), \(\tau\), and the bit-length of the rational masses. This is a Class A approximation result, even though exact optimization remains hard.
The mirror also gives continuous versions of the paper’s indices. Writing
\[ \kappa_k^\infty(\mu)= \min_{|\Lambda|\le k}\Phi_\mu(\Lambda), \]
one can define
\[ D_\infty(\mu)= \frac{\sum_{k=1}^{\tau}\kappa_k^\infty(\mu)/k} {\binom{m}{2}} \quad\text{and}\quad P_\infty(\mu)= \frac{2(\kappa_1^\infty(\mu)-\kappa_2^\infty(\mu))} {\binom{m}{2}}. \]
For a finite election with \(\mu_t=n_t/n\), these agree with the paper’s normalized quantities, since \(\kappa_k(E)=n\kappa_k^\infty(\mu)\). The mirror covers the computational core behind diversity and polarization, but not the paper’s MDS visualizations, statistical-culture experiments, or empirical correlation claims.
The main further question is whether Theorem 2 admits a weighted-support version: for every \(\epsilon>0\), can one obtain a \((1+\epsilon)\)-approximation in time \(f(\tau,\epsilon)\operatorname{poly}(m,L)\), parameterized by the number of distinct types rather than the number of voters? The paper’s FPT-in-\(n\) result suggests this, but the weighted extension is not proved there, so I would treat it as a follow-up rather than a third anchor. Other natural questions concern exact complexity as a function of \(\tau\), improved approximation factors, and whether single-peaked or other structured supports make the continuous problem exactly tractable.
The weakest point is that the lead hardness result is a compressed weighted restatement of a discrete problem, not a continuum-specific phenomenon, and the approximation result is only approximate. The population distribution affects the objective rather than creating new feasible actions. But that is still a legitimate continuous mirror under this programme: the paper’s problem is explicitly a client-to-representative optimization problem, and its own reduction relies on indistinguishable voter copies. The honest claim is therefore not that continuization makes \(k\)-Kemeny easy. It is that the paper supplies both a faithful Class B hardness mirror and a meaningful Class A approximation mirror for the same continuous society model.
The strongest negative case is that every proposed mirror is merely a weighted version of finite \(k\)-median: replace the list of voters by rational client masses, and nothing else changes. But that objection is not available under this programme’s standards. The whole point of high multiplicity is precisely that such compression can be computationally meaningful.
Theorem 3 is especially difficult to defeat. Its reduction already creates \(L=N(M+4)\) indistinguishable copies of every set-voter, and the authors explicitly say those copies need not be distinguished. Replacing them by one type of mass \(L/n\), while assigning each element-voter its corresponding mass \(1/n\), preserves every objective value after normalization by \(n\). The resulting society has only \(M+N\) relevant types, rational weights of polynomial encoding length, and the same threshold \(D/n\). This is not a modelling contrivance: large electorates with repeated ballots, party blocs, constituencies, or demographic segments are exactly plausible high-multiplicity societies. The objective depends only on aggregate mass, not individual identity. Thus the theorem supplies a legitimate continuous Class B mirror.
Corollary 1 survives as well. The support rankings are weighted clients and facilities, and the paper’s reduction from unrestricted rankings to rankings appearing in the input uses only the triangle inequality, so it extends to rational client weights. A weighted \(k\)-median approximation therefore gives the corresponding \(5.4\)-approximation in time polynomial in \(m\), the number of types, and the weight encoding length. Calling this “generic” does not defeat it: exploiting standard continuous-optimization machinery on a high-multiplicity society is one of the programme’s stated aims.
The proposed indices do not degenerate either. For a distribution \(\mu\), \(\kappa_k^\infty(\mu)\) is zero once \(k\) reaches the number of positive-mass types, so the diversity sum is finite. If \(\mu_t=n_t/n\), then \(\kappa_k(E)=n\kappa_k^\infty(\mu)\), and the normalized diversity and polarization indices agree with the discrete ones. A fuller type space, including all rankings, remains a natural though potentially exponentially represented model; an explicit-support version is already sufficient.
One might object that the continuous version produces no continuum-specific phenomenon, but that is only the statement that the answer may be Class B or a routine weighted approximation. The programme explicitly treats transferred hardness and high-multiplicity algorithms as worthwhile outcomes, so it cannot serve as a negative argument. Nor can one claim that the paper lacks a sensible multiplicity regime, that its objective tracks identities, or that the limit becomes trivial.
Consequently, I cannot honestly defeat these anchors. The paper may be a weaker candidate than the bribery manuscript for discovering a genuinely continuum-specific Class A result, but Theorem 3 alone establishes a worthwhile population-continuized problem. The universal negative claim is therefore not supportable.
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.