| paper | Explaining Preferences by Multiple Patterns in Voters’ Behavior |
| authors | Sonja Kraiczy, Edith Elkind |
| venue | IJCAI 2022 |
| filed under | voting · structured |
| 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
Input: a finite candidate set \(C\), a fixed integer \(k\ge3\), and a sparse rational distribution \(\mu\) over \(T=\mathcal{L}(C)\), represented by its positive-mass complete-ranking types. Question: do there exist nonnegative allocations \(x_{t,j}\) and ordered binary trees \(B_1,\ldots,B_k\) on \(C\) such that \(\sum_{j=1}^{k}x_{t,j}=\mu_t\) for every \(t\in T\), and every type \(t\) with \(x_{t,j}>0\) is \(B_j\)-consistent?
Types are complete rankings \(t\in\mathcal{L}(C)\); \(\mu_t\) is cohort mass; \(x_{t,j}\) assigns mass to one of \(k\) latent ordered binary trees \(B_j\); the objective is exact feasibility, equivalently explained mass \(1\).
For exact feasibility, hereditary group-separability lets every feasible fractional allocation be rounded to one group per positive-mass type, so the numerical values of \(\mu_t\) never matter.
fatal: False
It directly covers Theorem 5, \(GS\textsc{ Voter }k\text{-Partition}\) for fixed \(k\ge3\), and the same construction can cover Theorem 4 for \(BR,MR,WR,VR\). It leaves the \(k=2\) polynomial results, CAT-GS recognition and characterization, and non-complexity structural propositions outside this mirror.
The strongest positive case is a faithful Class B mirror of the paper’s group-separable partition problem. It does not make the problem easier: it shows that this particular discrete hardness survives continuization.
My lead anchor is Theorem 5, proved in this paper: \(GS\textsc{ Voter }k\text{-Partition}\) is NP-complete for every fixed \(k\ge 3\). This is the best anchor because group-separability is not merely a forbidden-minor label: the paper gives it a concrete interpretation through binary decision trees, so the continuous population model has an immediately recognisable meaning.
Call the mirror \(\mathrm{Continuous}\text{-}GS\textsc{-Partition}_{k}\). An instance consists of a finite candidate set \(C\), the set \(\mathcal{L}(C)\) of complete rankings of \(C\), a rational distribution \(\mu\) over those rankings, and a fixed integer \(k\ge3\). A type \(t\in\mathcal{L}(C)\) is one complete preference order; \(\mu_t\) is the fraction of the population with that order.
A solution is a collection of nonnegative masses \(x_{t,j}\), for \(t\in\mathcal{L}(C)\) and \(j\in[k]\), satisfying
\[ \sum_{j=1}^{k}x_{t,j}=\mu_t \]
for every type \(t\). Thus \(x_{t,j}\) assigns mass of type \(t\) to explanatory group \(j\). For each \(j\), let
\[ S_j=\{t:x_{t,j}>0\}. \]
The solution is feasible if each \(S_j\) is group-separable: equivalently, there is an ordered binary tree \(T_j\) on \(C\) such that every ranking in \(S_j\) is \(T_j\)-consistent. The objective is feasibility: explain all population mass using at most \(k\) group-separable patterns. Equivalently, one may define a maximum-explained-mass version and ask whether its optimum is \(1\).
This is not a relaxation to average preferences. The types remain complete rankings, and the explanatory objects remain exactly the paper’s binary decision trees. Only the electorate is continuized: individual voters are replaced by masses of indistinguishable voters.
A plausible regime is a large election, policy consultation, or market survey in which voters fall into recurring issue-profile cohorts. For example, many voters may share a ranking because they respond identically to a standardised package of candidates and policy attributes. The population may contain \(N\) people but only \(r\) realised ranking types, with \(N\gg r\); each type represents a large cohort rather than a named individual. The \(k\) trees represent \(k\) latent decision logics—say, different regional, generational, or institutional communities evaluating the same candidates through different binary issue hierarchies.
The authors should recognise this as their problem in population form. Their question is whether the observed electorate can be partitioned into \(k\) subprofiles, each explained by one structural pattern. Replacing the number of voters of type \(t\) by its fraction \(\mu_t\) preserves exactly that question. It also matches an important feature of their proofs: group-separability is hereditary under voter deletion, and duplicate copies of a vote do not create new forbidden minors.
The hardness transfer is direct. Given the paper’s profile \(P=(v_1,\ldots,v_n)\), define a rational society with
\[ \mu_{v}=\frac{\#\{i:v_i=v\}}{n}. \]
If \(P\) can be partitioned into \(k\) group-separable profiles, assign each voter type’s mass to the corresponding group. Conversely, suppose the continuous instance has a feasible mass allocation. The positive-support sets \(S_1,\ldots,S_k\) cover the support of \(\mu\). Assign each type to one group in which it has positive mass. Each resulting group is a subset of some \(S_j\), and group-separability is hereditary, so these groups are still group-separable. Scaling rational masses to a common denominator recovers a finite high-multiplicity profile.
Therefore the continuous problem is NP-hard for every fixed \(k\ge3\); with sparse rational input, it also has finite certificates consisting of group labels and \(k\) binary trees. The appropriate classification is Class B: the combinatorics live in the alternatives, rankings, and forbidden configurations, not in the number of named voters. Continuization does not dissolve this hardness.
The mirror covers Theorem 5 emphatically, but not every result in the paper. Theorem 4 could be mirrored in the same way for value-restricted, best-restricted, medium-restricted, and worst-restricted profiles, while Corollary 1 suggests a contrasting \(k=2\) mirror in P. I would not use those as additional anchors: they are essentially parallel support-preserving applications of the same idea, whereas Theorem 5 already establishes the central point cleanly.
The weakest point is that the exact feasibility question is largely support-sensitive rather than mass-sensitive. If every type must be explained, the numerical values of positive \(\mu_t\) do not affect the answer; only which types occur matters. That may make the mirror look like a weighted encoding of the original problem rather than a genuinely quantitative continuous optimization problem. The objection is real. It is mitigated by the paper’s own duplicate-insensitivity, but it means this mirror demonstrates faithful continuization and transferred hardness more strongly than it demonstrates a new tractable population algorithm.
The natural next problem is therefore a mass-sensitive extension: maximize the fraction of society that can be assigned to \(k\) group-separable explanatory trees, allowing some mass to remain unexplained. Its value would support questions about approximate structure, robustness to atypical voters, and continuous voter-deletion costs. Theorem 5 anchors the exact threshold at explained mass \(1\), while the complexity of the genuinely quantitative \(q<1\) versions remains an open continuization question.
Theorem 5 is the only serious anchor, but the proponent’s exact mirror is more degenerate than they admit. Let \(S(\mu)=\{t:\mu_t>0\}\). Because group-separability is hereditary, any feasible fractional assignment \(x_{t,j}\) can be made integral at the type level: for each \(t\), assign all of \(\mu_t\) to one group \(j\) with \(x_{t,j}>0\). Each resulting group is a subset of an already group-separable support and is therefore group-separable.
Hence
\[ \mu \text{ is feasible} \quad\Longleftrightarrow\quad S(\mu)\text{ can be partitioned into }k\text{ group-separable sets}. \]
The numerical masses never enter. Two societies assigning \(10^{-6}\) and \(0.9\) to the same rankings are computationally indistinguishable; only whether a type has positive mass matters. Any continuous distribution over ideal points would collapse to the same finite pushforward distribution over rankings. The proposed mass variables therefore do not create a continuous population problem, an optimization problem, or a quantitative notion of uncertainty. They merely deduplicate the paper’s votes.
The cohort story does not repair this. Repeated ranking cohorts are a perfectly sensible high-multiplicity regime, but that supports the discrete problem rather than giving it a continuous content. If cohort identity is meant to affect the explanation, then it must be included in the type; if it does not affect the constraints, it is irrelevant. The binary trees still see only the ranking support.
The proponent’s stronger rescue is to maximize explained mass,
\[ \max_{A_1,\ldots,A_k} \sum_{t\in A_1\cup\cdots\cup A_k}\mu_t, \]
where each \(A_j\) is group-separable. That is genuinely mass-sensitive, but it is no longer the paper’s partition problem: it is a weighted voter-deletion or robust-fitting problem. The paper itself points toward such deletion variants, and they can be studied directly as weighted high-multiplicity problems without needing continuization. It is a reasonable new research direction, but it cannot establish that Theorem 5 has a worthwhile continuous mirror; it establishes a different problem whose optimum happens to equal \(1\) on yes-instances.
This is where the negative case is honestly weak. The exact mirror collapses to support and is therefore a poor example of continuization, but the weighted approximate version is a legitimate continuous question about the fraction of a population explained by \(k\) latent decision trees. I cannot credibly claim that no worthwhile scenario exists. The strongest defensible conclusion is that the proponent has shown a faithful Class B high-multiplicity restatement, while the genuinely continuous variant requires adding a new mass-sensitive objective absent from the paper.
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.