| paper | d4-conf-aaai-2010-0378 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
NP-hard→P discrete result → its continuous mirror
Answer: Polynomial-time solvable in \(m,\tau,L,k\), with exact identification of \(+\infty\). · discrete side: hardness · adjudication: proved_with_minor_gaps
full proof & adversarial review →
Theorem 5
statement extracted from the paper’s text layer
Given candidates \(C\), a target \(p\), and partial-ballot types \(t\) with rational masses \(\mu_t\), each allowing one or two rankings, independently complete each ballot uniformly among its type's allowed rankings. For \(N\) divisible by the mass denominators, let \(P_N\) be the probability that \(p\) is the unique plurality winner among \(N\mu_t\) ballots of each type. Compute \(I_p(\mu)=\lim_{N\to\infty}-N^{-1}\ln P_N\), taking \(I_p(\mu)=+\infty\) if a unique \(p\)-winning completion is infeasible. When it is feasible, equivalently compute \(\inf_{z\in W_p^+}\sum_t\mu_tD(z_t\Vert u_t)\), where \(z_t\) is a distribution over type \(t\)'s rankings, \(u_t\) is uniform, and \(W_p^+\) imposes strict plurality victory for \(p\).
A population with rational mass \(\mu_t\) on each partial-ballot type \(t\); each unit of mass receives an independent uniform completion from that type's allowed rankings. Optimize the weighted relative entropy of the completion distributions subject to \(p\)'s strict plurality victory, to obtain the per-capita decay rate of the finite society's winning probability.
The mirror covers the plurality case of Theorem 5 for partial ballots with at most one unresolved pair; it leaves veto and the paper's other results aside.
My strongest positive case is a large-population rate version of the paper’s plurality counting problem. It mirrors one result, not the paper as a whole.
The anchor is Theorem 5, proved here. It states that Plurality-\(\#\)POSSIBLE-WINNER and veto-\(\#\)POSSIBLE-WINNER are \(\#\)P-hard even when each partial vote has at most one undetermined pair of candidates. The paper proves the plurality case and says veto follows by a simple adaptation. In the plurality reduction, extensions in which the designated candidate wins correspond one-to-one with perfect matchings. I would build the mirror around the plurality result.
Call it Plurality-Possible-Winner Rate\(_\infty\). An instance has a candidate set \(C\), target \(p\), and a finite support \(T\) of partial-ballot types with rational masses \(\mu_t\) summing to \(1\). Each type has either one permitted ranking or two, differing in the order of the top pair. A type includes the partial ballot and the paper’s uniform completion rule, so agents of that type are alike in every respect the model uses.
For each type \(t\), let \(\Pi_t\) be its permitted rankings. The decision variable \(z_{t\pi}\) is the fraction of type \(t\)’s mass completed as ranking \(\pi\), with \(z_t\) in the simplex over \(\Pi_t\). The completed society gives candidate \(c\) plurality score
\[
S_c(z)=\sum_{t\in T}\mu_t\sum_{\pi\in\Pi_t}z_{t\pi}\,\mathbf{1}[\pi\text{ ranks }c\text{ first}].
\]
Let \(W_p^+\) be the set of these mass allocations for which \(S_p(z)>S_c(z)\) for every \(c\ne p\).
The question is to compute the exponential rate at which \(p\)-winning completions become rare as the population grows. For any \(N\) divisible by the denominators of the \(\mu_t\), take \(N\mu_t\) agents of each type and independently complete each ballot uniformly from \(\Pi_t\). If \(P_N\) is the probability that \(p\) is the unique winner, the continuous problem is to compute
\[
I_p(\mu)=\lim_{N\to\infty}-\frac{1}{N}\ln P_N.
\]
Equivalently, when a strictly winning allocation exists, the method of types gives
\[
I_p(\mu)=\inf_{z\in W_p^+}\sum_{t\in T}\mu_t D(z_t\Vert u_t),
\]
where \(u_t\) is uniform on \(\Pi_t\) and \(D\) is relative entropy; if no strictly winning allocation exists, set \(I_p(\mu)=+\infty\). A solution can be the rate to additive error \(\epsilon\), optionally with a mass allocation attaining that rate to the same precision.
The regime is a large electorate with repeated, recognizable patterns of incomplete ballots—for example, a large consultation using a fixed questionnaire whose uncertainty leaves only the top pair unresolved. The number of agents \(N\) is much larger than the number of patterns \(\tau=|T|\). Each agent is still counted as an individual in the finite model; the continuous object is the distribution of the population among partial-ballot types and, within each type, among completions.
I expect this restricted mirror to be Class A. With at most two completions per type, there are only \(O(\tau)\) variables. Plurality’s winner conditions are linear inequalities, and the relative-entropy objective is convex. Strict-winner feasibility can be checked by linear programming; when it is feasible, the rate can be approximated through convex optimization in parameters such as \(m,\tau,L,\) and \(1/\epsilon\). The reduction’s perfect-matching choices are integral in the finite counting problem, but become fractional cohort shares here. This does not prove that the paper’s \(\#\)P-hardness disappears in every related continuous problem; it gives a specific, tractable rate question suggested by that result.
The authors have a plausible reason to recognize this as their problem: their paper counts extensions because it wants the probability that a designated candidate wins under uniform random completion. This mirror keeps that same ballot uncertainty and winner event, then asks for the per-capita exponential rate in a high-multiplicity regime. It covers the plurality part of Theorem 5 only; it makes no claim about veto or the paper’s other results.
The main weakness is that the mirror replaces the exact finite count with its asymptotic rate. The rate can be \(0\) when winning is not exponentially rare, and it loses subexponential information, so it cannot recover the exact number of winning extensions. The theorem also does not itself establish that the rate problem is tractable or hard. Those are real costs of the continuous limit, but the rate remains a well-defined computational question about the same winning probability under a continuous population model. Further questions include whether the rate remains tractable for partial orders with more extensions, and whether exact or approximation hardness survives for those broader types.
The only strong computational anchor is Theorem 5’s plurality result: counting winning completions is \(\#\)P-hard even when each partial ballot has just one unresolved pair. Its reduction assigns a partial-ballot type to each graph edge, so the original hard instances do not themselves have many repeated ballot types. That weakens the connection to a high-multiplicity regime, but it does not rule one out: repeat each edge type in a larger electorate and keep its population share fixed.
The strongest objection is a dilemma about what quantity survives the limit. If the continuous model records completed rankings as deterministic population masses, the winner is determined by their scores and the completion probability disappears. If it retains independent random completions, the law of large numbers makes the winning probability tend to \(1\) or \(0\) whenever the expected score has a strict margin. The proponent’s rate \(I_p(\mu)\) avoids that collapse, but changes the target from the paper’s count or winning proportion to the exponential decay of a rare event.
That is a real narrowing of the mirror, not a decisive objection under ChoCo’s standard. The paper explicitly motivates counting by the probability of winning under uniform random completion. A large-deviation rate is a natural population-scale refinement of that probability, and its entropy optimization retains the same ballot uncertainty and winner event. The lost finite-count information is a cost, but it is not enough to dismiss the question when the programme is specifically about what changes under continuization.
So the negative case is weak. I can argue against a literal continuous version of the exact count, and against treating the rate as the same output. I cannot honestly defeat the rate mirror itself: the paper gives a plausible reason its authors would recognize it as their problem, and the supplied criteria do not let me dismiss it merely because the limit may have a tractable answer.
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.