| paper | d4-conf-sagt-2024-0023 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
Theorem 13 is a computational hardness result, but the proposed mass formulation does not give it a distinct continuous-population mirror. There are finitely many poset types, and with rational \(M\) the feasibility constraints have rational coefficients, so any feasible distribution has a rational feasible point that can be converted into a finite electorate; the paper already permits electorates of any finite size. The proposed question therefore restates the paper’s model in mass notation.
fails bit b-already — the paper is already native to the continuum
The proposed formulation targets Theorem 13 on integral inputs and relies on Theorem 10; it leaves the half-integral and integral bounds on rationality number outside its scope.
My lead mirror is a mass-distribution version of the paper’s rationality-number problem. Think of a large electorate or consumer panel with many people but relatively few distinct patterns of strict preferences and unresolved comparisons: \(N\gg\tau\), where each type is a partial order on the \(n\) alternatives and \(\mu_P\) is the fraction of the population with type \(P\). In a plausible regime, millions of respondents share a modest repertoire of such patterns. The paper’s pairwise matrix \(M\) is the observed aggregate data; the task is to find a population of types that explains it.
Precisely, given a rational preference matrix \(M=(p_{ij})\) and an integer \(k\), let \(\mathcal P_{n,k}\) be the strict partial orders on \([n]\) of width at most \(k\). Ask whether there is a distribution \(\mu\) over \(\mathcal P_{n,k}\) such that, for every \(i\ne j\),
\[
\sum_{P:\,i\succ_P j}\mu_P
\ \le\ p_{ij}\ \le\
\sum_{P:\,i\succ_P j\ \text{or}\ i\parallel_P j}\mu_P.
\]
A solution is a finite list of poset types and their nonnegative masses summing to \(1\). Equivalently, minimize the greatest width among types with positive mass; the decision question asks whether that minimum is at most \(k\). The input is \(M\) and \(k\); the type universe is all partial orders on the alternatives. In the computational problem, \(M\) has binary rational entries.
The anchor is Theorem 13, proved in this paper: deciding whether the rationality number of \(M\) is at most \(k\) is NP-complete for \(k\ge2\), even when \(M\) is integral. The paper’s proof uses its Theorem 10, also proved here, which says that for integral \(M\), \(\alpha(M)\) equals the dichromatic number of its voting tournament. The hardness proof then draws on cited results of Chen, Hu and Zang for \(k=2\), and Fox et al. for extending hardness to larger \(k\). The continuous question above mirrors Theorem 13 directly: for integral inputs, its feasible mass distributions have the same minimum width as the paper’s problem, so the NP-completeness carries over.
I would expect this mirror to be hardness-transferring. The hard combinatorics live in the number of alternatives and the directed tournament, not in the number of people. Indeed, the paper’s Theorem 9 says one voter suffices for integral matrices, so allowing a continuum of population mass cannot remove that hardness. That is a useful boundary case for ChoCo: this is a population-level computational question, but continuizing the population does not make this particular hardness disappear.
The scope is deliberately narrow: it covers the integral rationality-number decision problem, not the paper’s half-integral bounds or its broader search for characterizations. It also raises natural follow-ups: whether fractional masses change rationalizability for non-integral \(M\); whether minimum width admits useful approximation or parameterized algorithms; and how the complexity depends on the number of supported types.
The weak point is that this is close to an explicit restatement of the paper’s existing model. The paper already works with pairwise population fractions and permits a voter set of unrestricted size; on rational inputs, replacing equal-weight finite voters by arbitrary masses over types may not change the decision problem. So this is a strong case that the problem has a natural continuous-population form, but a weak claim that the paper needs a new continuization. The positive case rests on its value as a clear mass-based formulation of the computational question, not on a new source of complexity.
Theorem 13 is a real computational result, and Theorem 10 gives it a strong structural anchor. But the proposed mass formulation is already the paper’s rationalizability problem in continuous notation. The paper takes pairwise population fractions \(p_{ij}\) as input, permits a voter set of any finite size, and asks whether its empirical type frequencies satisfy the same lower and upper bounds. For rational input \(M\), allowing arbitrary real masses does not enlarge the feasible set in a meaningful way: there are finitely many poset types on \(n\) candidates, and the proposed constraints form a rational polyhedron. If it is feasible, it has a rational feasible point; clearing denominators turns that point into a finite electorate. Conversely, any finite electorate gives a rational mass distribution. Thus the two decision problems are equivalent, instance for instance.
That equivalence carries Theorem 10 across unchanged. For integral \(M\), each poset type with positive mass can only have strict comparisons agreeing with the voting tournament; indifference can leave a comparison unspecified. The minimum width among compatible types is therefore the tournament’s dichromatic number, exactly as in the paper. Consequently the mass version of Theorem 13 has the same NP-completeness result, but that is not a new continuous complexity landscape. The paper’s own model and proofs already settle it.
The panel scenario makes sense as an interpretation of the data, but it does not create the ChoCo regime of a supplied society over voter types. The input is still the pairwise matrix; the distribution over posets is an unknown explanation the problem seeks. If instead the type masses are supplied, checking whether they satisfy the pairwise constraints is direct, and the task is no longer Theorem 13. Adding prices, identities, or other type attributes would likewise define a different problem, not a stronger mirror of this result.
The honest negative case is strongest for these anchors: the paper has a computational theorem, but the proposed continuous version is an exact restatement of its existing arbitrary-size, proportion-based model. A version over irrational matrix entries would need a finite input representation before it could pose the same kind of complexity question. For the paper’s rational computational problem, there is no distinct continuous mirror left to investigate.
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.