| paper | Properties of Position Matrices and Their Elections |
| authors | — |
| venue | AAAI 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 6
statement extracted from the paper’s text layer
Given candidates \(C\), an explicitly listed set \(D\) of ranking types, a rational bistochastic frequency matrix \(Y\), and candidate \(c\), decide whether there exists a probability distribution \(\mu\) over \(D\) such that \(\mu\) realizes \(Y\) and \(c\) is preferred to every other candidate by mass greater than one half; equivalently, maximize \(\delta\) subject to the realization constraints and all Condorcet margins being at least \(\frac{1}{2}+\delta\), and test whether \(\delta > 0\).
A high-multiplicity electorate whose explicit ranking types v∈D carry nonnegative masses μ_v; Y fixes candidate-position marginals, and the LP objective maximizes the minimum Condorcet margin δ.
Theorem 6's continuous counterpart is an immediate LP augmentation of the paper's existing frequency-realization machinery, so its technical novelty and complexity interest may be limited.
fatal: False
The mirror covers structured frequency realization and Condorcet-winner feasibility, with Theorem 6 as the surviving anchor; it leaves counting, uniform sampling, Theorem 5's discrete restricted-domain hardness, distance experiments, and the necessary-condition results aside.
The strongest positive case is a Class A mirror built around the paper’s frequency-matrix realization problems. The lead anchor is Theorem 3, proved in this paper.
The population is a large electorate whose voter types are complete rankings of the same candidate set. Two voters are the same type exactly when they have the same ranking. The intended regime is millions of voters but a moderate catalogue of recurring preference types—for example, voters clustered into repeated ideological or demographic cells along a known political axis. The ambient structured domain may contain exponentially many admissible rankings, but only a finite subset carries positive mass.
For a candidate set \(C\), let \(D\) be either an explicitly listed set of rankings, all rankings single-peaked on a supplied axis, or all rankings compatible with a supplied balanced or caterpillar group-separability tree. Given a rational bistochastic matrix \(Y\), define:
*Structured-Frequency-Realization\(_\infty\).* Find nonnegative masses \(\mu_v\) for \(v\in D\) such that
\[ \sum_{v\in D}\mu_v=1 \]
and, for every candidate \(c\) and position \(i\),
\[ \sum_{v\in D:\,v\text{ ranks }c\text{ at }i}\mu_v=Y_{i,c}. \]
The question is whether such a population distribution exists; a solution is the distribution \(\mu\), represented by its finite rational support. Equivalently, this is feasibility of a linear program, with objective \(0\).
This is not merely calling a finite election “continuous.” If a discrete election has \(z_v\) voters of type \(v\) and \(n\) total voters, then \(\mu_v=z_v/n\). The continuous problem replaces the integer multiplicities \(z_v\) by arbitrary nonnegative masses. Conversely, every rational solution can be scaled to a finite election. Discrete elections are therefore lattice points in the continuous realization fibre.
Theorem 3 says exactly that this problem is polynomial-time solvable for the explicit, single-peaked, and group-separable domains specified above. It is an unusually good mirror because the paper itself already works with normalized frequency matrices and explicitly notes that its LPs may discover exponentially many votes without constructing them individually. The authors would recognize the model: candidates, rankings, structural domain, and positionwise aggregate information are unchanged; only voter multiplicity has been continuized. This is my strongest anchor, and its expected classification is Class A.
It generates several natural follow-up questions: can one optimize a linear statistic over the realization fibre rather than merely test feasibility? Can one maximize a pairwise margin or the score of a designated candidate? Can one characterize the extreme or maximum-entropy realizations? And how large is the rounding gap when a rational mass distribution must be implemented with a prescribed population size?
A second, genuinely distinct anchor is Theorem 4, also proved in this paper. Here the hierarchy itself is latent.
*Latent-Balanced-Group-Realization\(_\infty\).* Given a candidate set \(C\) and rational bistochastic matrix \(Y\), decide whether there exist both a balanced binary tree \(H\) over \(C\) and a population distribution \(\mu\) over rankings compatible with \(H\) such that \(\mu\) realizes \(Y\).
This models a large population whose preferences reflect a common but initially unknown hierarchy of candidate attributes—for example, voters evaluating candidates through a shared organizational or policy taxonomy. The tree is not an individual attribute; it is a common structural feature of the society. Theorem 4 proves that the problem is polynomial-time solvable, even when the tree is not supplied, and even for position matrices as well as frequency matrices. Thus this is also Class A. The interesting extensions are to output all compatible trees, optimize over the latent tree, or drop the balanced/caterpillar restriction.
The strongest mirror of one of the paper’s negative results is based on Theorem 6, proved here. The theorem gives NP-hardness when votes must come from an explicitly listed set \(D\), a position matrix is prescribed, and a designated candidate must be a Condorcet winner.
The continuous counterpart is:
*Condorcet-in-the-Frequency-Fibre\(_\infty\).* Given \(C\), an explicitly listed ranking-type set \(D\), a rational frequency matrix \(Y\), and candidate \(c\), decide whether there is a distribution \(\mu\) over \(D\) realizing \(Y\) in which \(c\) is a Condorcet winner. Equivalently, solve
\[ \max \delta \]
subject to the realization constraints above and
\[ \sum_{v\in D:\,c\succ_v d}\mu_v\ge \frac12+\delta \qquad\text{for every }d\ne c. \]
The answer is yes exactly when the optimum satisfies \(\delta>0\). This preserves the paper’s central phenomenon: the position matrix does not determine pairwise comparisons, so different realizations of the same aggregate data may have different Condorcet winners. It changes only integer vote multiplicities into population mass.
Because \(D\) is explicit, this is a polynomial-size linear program. Hence the expected classification is Class A: the NP-hardness of Theorem 6 does not transfer to its high-multiplicity relaxation. The natural regime is a large electorate with a moderate explicit catalogue of recurring ballot types, where the position frequencies are known but the underlying pairing of candidates across rankings is not. Further questions include the set of all possible Condorcet winners, maximum achievable Condorcet margin, and whether tractability survives when \(D\) is given implicitly by a structured domain rather than listed.
This case deliberately does not claim a clean mirror for Theorem 1’s \(\#\)P-completeness result. Counting atomic elections has no canonical direct analogue once the population becomes a mass distribution; volume, entropy, or approximate sampling of the realization fibre would be new choices rather than faithful translations. Nor am I claiming to mirror the map-of-elections experiments or the isomorphic swap-distance computation.
The weakest point is that Theorem 3 is already very close to a high-multiplicity result: the paper’s frequency matrices and LP formulations partially contain the continuous model. An opponent could therefore call the mirror a relabelling rather than a new problem. That criticism has force. But it does not undermine the positive case. The programme is testing whether the population-continuous regime is mathematically sensible and computationally productive, not claiming that every such formulation must be novel to the source paper. Here the authors’ own normalized formulation supplies strong evidence of plausibility, while Theorem 6 demonstrates a real complexity change: an NP-hard finite-multiplicity problem becomes a precise LP over population masses without losing the position-matrix or Condorcet semantics.
The strongest negative case is that the first two anchors are not mirrors at all: they are already continuous computational results in the paper.
For Theorem 3, let \(Y\) be the rational frequency matrix and let \(\mu_v\) be the mass assigned to each admissible ranking. The constraints in the proposed Structured-Frequency-Realization∞ problem are exactly the constraints defining an election that realizes \(Y\). Clearing denominators in a rational \(\mu\) produces a finite election, and normalizing any finite election produces such a \(\mu\). This is not merely an analogy between two models; it is a bijective correspondence between rational points of the distribution polytope and finite elections.
More importantly, the paper already solves this distributional feasibility problem with LP machinery. Its explicit warning that an LP solution may contain exponentially many votes which need not be constructed is precisely the column-generation viewpoint of the proposed continuous model. Calling this merely “high-multiplicity prior art” would be too weak: the input is already a normalized point in the population simplex, and the algorithm already reasons over fractional vote masses. The proposed mirror therefore adds notation, not a new computational question.
The suggested extensions do not rescue it. Optimizing a linear score, pairwise margin, or candidate statistic over the realization fibre is the same LP with a different objective. Extreme-point questions are standard LP questions. Rounding asks about the bridge back to finite elections, not about a new continuous society. Entropy, volume, and approximate sampling could be interesting, but they are new probabilistic geometry problems; there is no canonical reason to identify any of them with the paper’s #REALIZATIONS problem.
Theorem 4 has the same defect, with an additional modelling weakness. The latent balanced tree is a common structure on the candidates, not a population attribute. Theorem 4 already searches for that structure from a frequency or position matrix. Replacing the vote multiplicities by \(\mu\) therefore changes nothing: the tree search and the realization constraints are already formulated at the normalized aggregate level. “Output all compatible trees” or “optimize over latent trees” may be worthwhile new problems, but they are not continuous mirrors of the theorem; they are extensions of an already solved frequency-matrix problem.
Theorem 6 is the proponent’s best anchor, but it too can be resisted. With \(D\) explicitly listed, the proposed Condorcet-in-the-frequency-fibre problem is simply a polynomial-size LP: the position constraints and every Condorcet-margin constraint are linear. That is a valid formulation, but it is an immediate augmentation of the frequency-realization LP already present in the paper, not a new continuous technique or a new population-level phenomenon.
The finite NP-hardness in Theorem 6 comes from integral selection of listed votes. In the X3C-style construction, the position matrix forces a discrete exact cover. Allowing arbitrary masses permits fractional use of those set-votes, so the reduction’s combinatorial content disappears. The resulting LP still asks which Condorcet winners are compatible with aggregate rank marginals, but its computational difficulty is no longer the paper’s problem; it is the generic fractional relaxation of an exact-cover system. The fact that the relaxation is well posed is not enough to make it a worthwhile mirror when its formulation and solution are already immediate.
A stronger version does not help much. If \(D\) remains explicit, the problem stays a routine LP. If \(D\) is made implicit through single-peakedness or group-separability, the question becomes a structured-domain extension of Theorems 3 and 4. If one restores integral multiplicities, prescribed support sizes, or uniform counting, one has reintroduced precisely the discrete feature that continuization was meant to remove. If one replaces the question by entropy, volume, or sampling, one has changed the target rather than found a better mirror.
Thus the paper offers no unclaimed computational mirror: Theorems 3 and 4 already solve their continuous formulations, while Theorem 6 yields only an elementary fractional relaxation of the paper’s integral problem. The negative case is not completely airtight, because the Condorcet fibre is a sensible high-multiplicity object and the programme explicitly values cases where integrality hardness disappears. But the strongest honest conclusion is that this paper is a poor ChoCo target—not because population continuization is incoherent, but because its most natural population-continuous questions have effectively already been formulated and answered here.
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.