| paper | d4-conf-ecai-2024-0018 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
P→P discrete result → its continuous mirror
Answer: Polynomial-time solvable · discrete side: polynomial · adjudication: proved
full proof & adversarial review →
Proposition 3
statement extracted from the paper’s text layer
Given candidates \(C\), a rational distribution \(\mu\) over \(\tau\) complete rankings, and a Borda winner \(w\), choose rational masses \(x_{t,p}\ge 0\) for partial rankings \(p\subseteq t\), with \(\sum_{p\subseteq t}x_{t,p}=\mu_t\). Require that for every opponent \(c\), \(\sum_{t,p}x_{t,p}\underline{s}_p(w)\ge\sum_{t,p}x_{t,p}\overline{s}_p(c)\), where the score bounds range over completions of \(p\); ties count as wins. Restrict each partial ballot to have either no hidden entries or at least two, and minimize \(\sum_{t,p}x_{t,p}|p|\), the average number of disclosed ranking entries per person.
A distribution over ranking types, with each type’s mass split among partial ballots; choose the splits so the named candidate remains a Borda winner under every completion, while minimizing expected disclosed entries.
Proposition 3 finds an inclusion-minimal explanation for a fixed profile, whereas the proposed LP globally minimizes average disclosure across fractional splits of each type’s mass.
fatal: False
It covers the Borda iAXp and smallest-explanation strand, including its connection to the \(n-\lfloor n/m\rfloor\) size bound. It leaves contrastive explanations, enumeration, other scoring rules, and the simulations untouched.
My lead is the iAXp clause of Proposition 3, proved in this paper. The full proposition says that, for a profile with \(n\) voters and \(m\) candidates under a scoring rule, Algorithm 1 finds one contrastive explanation in \(\Theta(nm^2)\) time and Algorithm 2 finds one irredundant abductive explanation in \(\Theta(nm^3)\) time. I mirror the iAXp computation; the paper gives no named hardness result to anchor a hardness-transfer claim.
Continuous problem: Mass-Minimum Borda AXp. Consider a large referendum or participatory vote in which, say, millions of people rank a small list of proposals, but only \(\tau\) distinct rankings occur. A type is a complete ranking \(t\); its mass \(\mu_t\) is the fraction of the population with that ranking. The input is the candidates, the rational masses \(\mu_t\) summing to \(1\), and a candidate \(w\) who wins under Borda.
For each type \(t\), choose how much mass \(x_{t,p}\) receives each partial ranking \(p\) obtained by hiding some entries of \(t\), with \(\sum_{p\subseteq t}x_{t,p}=\mu_t\). This says what fraction of each ballot type’s information is disclosed in each form. Require that \(w\) remain a Borda winner under every completion of the hidden entries. Equivalently, for each opponent \(c\), require
\[
\sum_{t,p}x_{t,p}\,\underline{s}_p(w)
\;\ge\;
\sum_{t,p}x_{t,p}\,\overline{s}_p(c),
\]
where \(\underline{s}_p(w)\) is \(w\)’s minimum Borda score over completions of \(p\), and \(\overline{s}_p(c)\) is \(c\)’s maximum. Ties count as wins, as they do in the paper.
Among such explanations, minimize
\[
\sum_{t,p}x_{t,p}|p|,
\]
the average number of ranking entries disclosed per person. This is the high-multiplicity version of finding a smallest iAXp: with masses in units of \(1/n\), the objective is \(|X|/n\), and an optimum is inclusion-minimal because any valid coarsening would disclose fewer entries. To match the paper’s irredundancy convention, a partial ballot either has no hidden entries or at least two; a ballot with just one hidden entry conveys a complete ranking already. A solution is the rational mass assignment \(x\).
I expect Class A, though it is not established by Proposition 3. The sufficient-winner conditions give an LP with \(\tau\) mass equations and \(m-1\) winner inequalities, but up to \(2^m\) partial ballots per type. For Borda, a partial ballot’s score bounds depend on whether \(w\) or an opponent is fixed and on the first and last hidden positions. That suggests a polynomial pricing routine: enumerate those endpoint positions, then optimize the remaining lock-or-hide choices position by position. If this yields polynomial separation, the GLS ellipsoid machinery gives an exact algorithm polynomial in \(m,\tau,L\). Proving that pricing claim is the key obligation; without it, the exponential column set prevents an efficiency claim. Rational normalization also gives the right bridge: a rational solution can be scaled into a finite cloned electorate with the same completions, winner comparisons, and tie semantics.
This is a recognizable question for the authors: their explanations already select rank-matrix entries, their necessary-winner test uses minimum and maximum achievable scores, and they study smallest explanations. The continuous version replaces repeated rows by ballot-type masses and total locked cells by average disclosed entries. Because Borda is anonymous, the identities of voters with the same ranking do not affect the winner guarantee. The mass split does change the granularity of the explanation: it can disclose a position for part of a type’s mass. That is appropriate for a population-level explanation, but it is the weakest point in claiming this is their exact explanatory object.
A useful check comes from Theorem 4, proved here, though it is not a complexity anchor: for any rank matrix with \(n\) voters and \(m\) candidates where \(w\) is a Borda winner, every AXp \(X\) satisfies \(|X|\ge n-\lfloor n/m\rfloor\). Under rational cloning, this implies an average-information lower bound of \(1-1/m\) disclosed entries per person in the mass model. It connects the proposed optimization to the paper’s own finding that Borda explanations can remain long even when minimized.
The mirror covers the computation of a smallest Borda iAXp and its size behavior; it does not claim to mirror the paper’s contrastive-explanation algorithm, enumeration procedures, simulations, or all scoring rules. The further questions are whether the Borda pricing routine is polynomial, how the optimum depends on \(\mu\) and \(w\), and whether a continuous contrastive version has a minimum at all when making a candidate beat \(w\) requires a strict score inequality.
The case is positive but modest: Proposition 3 already gives a polynomial-time discrete algorithm, so this mirror does not dissolve known hardness. Its potential contribution is a support- and bit-length-sensitive formulation for populations with \(\tau\ll n\), together with a new pricing question.
The proposed mirror does not match the result it names. Proposition 3 finds *one inclusion-minimal explanation for a fixed, explicit rank matrix*. The mass LP instead minimizes total disclosure over assignments of partial ballots to voter mass. That is a different objective and output. Its solution can be expanded into a concrete explanation after cloning the electorate to fit the rational masses, but that gives a minimum-size explanation for the cloned profile; it does not reproduce Algorithm 2’s result for the paper’s input. The algorithm’s \(\Theta(nm^3)\) bound is tied to scanning voter-indexed cells, and replacing \(n\) by support size only makes sense after changing the task to an aggregate one.
The strongest repair is to anchor the mirror in the paper’s study of smallest explanations, rather than Proposition 3. That yields a coherent question: for each ballot type, how should mass be split among partial ballots to minimize average disclosure while certifying the winner? The skeptical concern is that this reports a cohort-level disclosure policy, not the paper’s subset of cells in a particular profile. But it is not decisive: scoring is anonymous, and a rational solution expands to an ordinary explanation on a sufficiently large cloned electorate. In a large referendum with repeated rankings, that seems like a plausible object the authors could recognize.
There is also a problem with using Theorem 5 to claim the lower bound is universally tight as printed. With three candidates and ballots \(A\!>\!B\!>\!C\), \(B\!>\!C\!>\!A\), and \(C\!>\!A\!>\!B\), \(A\) is a Borda winner but is ranked first on only one ballot. The theorem’s construction requires \(n-\lfloor n/m\rfloor=2\) ballots with \(A\) first, so that construction is not a subset of this profile. This weakens the proponent’s supporting claim, though it does not by itself rule out the mass optimization.
I would not claim that the universal negative is established. The paper’s voter-indexed explanation semantics give a real reason to doubt that an anonymous mass policy is the same explanatory product, but the minimum-size variant has a credible large-electorate interpretation. There is no sound no-multiplicity or continuum-degeneration objection here: repeated rankings are plausible, and the per-person disclosure cost need not vanish. The case against is strongest against Proposition 3 as the anchor; it is much weaker against the repaired smallest-explanation mirror.
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.