| paper | Margin of Victory for Weighted Tournament Solutions |
| authors | — |
| venue | AAMAS 2023 |
| filed under | voting · weighted-tournaments |
| judged by | gpt-5.6-terra / high (triple__gpt-5.6-terra__high__ctx2r8-rejudge1) |
| judge confidence | high |
| authors would recognise it | yes |
Theorem 3.3
statement extracted from the paper’s text layer
Given alternatives \(C\), a balanced society \(\mu\) over pairwise-comparison report types \((\{a,b\},a\succ b)\) and \((\{a,b\},b\succ a)\), and a Borda non-winner \(d\), find a minimum-total-mass feasible transfer between opposite reports within each pair stratum such that \(d\) has maximum induced Borda score.
A finite-type society of independently collected pairwise-comparison tasks, with masses \(\mu_{ab}^a,\mu_{ab}^b\), pairwise report-flip variables \(\delta_{ab}\), objective \(\sum_{\{a,b\}}|\delta_{ab}|\), and Borda scores induced by conditional support rates.
The mirror covers the constructive and destructive Borda MoV results in Theorems 3.3 and 3.1; it leaves the Split Cycle and weighted Uncovered Set results unaddressed.
I think there is a strong, if deliberately narrow, positive case here. The lead mirror is the paper’s Borda construction, anchored in Theorem 3.3 (proved in this paper): computing the MoV of a Borda non-winner in an \(n\)-weighted tournament is polynomial-time solvable.
Call the continuous problem Continuous Comparative-Borda MoV. Let \(C\) be the alternatives and let \(E=\{\{a,b\}:a\ne b\}\). Society consists of a large, balanced population of pairwise-comparison tasks: each task is assigned one pair \(\{a,b\}\) and reports either \(a\succ b\) or \(b\succ a\). Thus a type is simply
\[ (\{a,b\},\text{ reported winner}), \]
with a finite type set of size \(2\binom m2\). Let \(\mu_{ab}^a,\mu_{ab}^b\) be the masses of the two types for pair \(\{a,b\}\), with \(\mu_{ab}^a+\mu_{ab}^b=1/\binom m2\). The conditional support rate is
\[ p(a,b)=\binom m2\,\mu_{ab}^a,\qquad p(a,b)+p(b,a)=1. \]
The induced weighted tournament uses \(p(a,b)\) as its edge weight, and Borda score is \(\sum_{b\ne a}p(a,b)\).
An intervention is a signed mass transfer on each pair: moving mass \(\delta_{ab}\) from the “\(b\succ a\)” type to the “\(a\succ b\)” type, within the obvious availability bounds. Its cost is the total fraction of comparison tasks corrected, misreported, or manipulated:
\[ \sum_{\{a,b\}}|\delta_{ab}|. \]
Given a non-winner \(d\), ask for a minimum-cost transfer such that \(d\) has maximum Borda score in the resulting tournament; a solution is the transfer vector and its value.
This is not merely analogous to the paper’s problem. An \(n\)-weighted tournament embeds exactly: take \(\mu_{ab}^a=w(a,b)/(n\binom m2)\). Reversing \(r\) comparisons on a pair becomes a mass transfer \(r/(n\binom m2)\); the new winner set is unchanged, and the objective is the paper’s MoV divided by the constant \(n\binom m2\). Conversely, rational continuous instances are rational weighted tournaments after clearing denominators. The paper’s minimum-cost \(b\)-flow method in Theorem 3.3 works with rational capacities and costs, so I expect this continuous problem firmly in Class A, with an exact polynomial-time algorithm rather than merely an approximation.
The regime is plausible and genuinely high-multiplicity. Think of a large comparative survey, crowdsourced benchmark, peer-review calibration exercise, or repeated head-to-head forecasting system. With \(m=100\), there are 4,950 pair strata and 9,900 response types, while a balanced system may contain millions of comparison observations—thousands per type. “Change 0.2% of the evidence comparing \(a\) and \(b\)” is more natural than naming individual observations. It also directly matches the paper’s premise that tournament weights arise from repeated comparisons, and its own interpretation of reversal sets as rigged games or altered pairwise information.
A useful second anchor is Theorem 3.1 (also proved here), on polynomial-time destructive Borda MoV. Its continuous counterpart is Continuous Comparative-Borda Destructive MoV: given the same society and a Borda winner \(a\), find the least comparison-task mass to transfer so that some other alternative strictly exceeds \(a\)’s Borda score. This too is Class A. The paper’s greedy argument becomes even cleaner with divisible mass: first transfer on the direct \(a\)-versus-\(b\) stratum, which improves their score gap twice as fast, then use adjacent strata as needed. It yields both the value and an explicit continuous reversal plan.
The authors should recognise these as their questions. Their central object is already a repeated-comparison tournament; I have only replaced the integer count of repeated observations by population proportions. I am not claiming that this is the continuous analogue of changing coherent full rankings in an ordinary ballot election. It is the continuous analogue of this paper’s weighted-tournament and pairwise-reversal model—especially apt because the paper itself notes its proximity to independent pairwise microbribery.
The scope is intentionally only the Borda results. I would not lean on Theorems 3.5 or 3.8 (the NP-completeness results for constructive Split Cycle and wUC) without rechecking their reductions against fractional interventions: an integer reduction need not automatically survive divisibility. That is a good next research question, not evidence already in hand.
The weak point is also clear: the best natural society here is a population of comparison observations, not a population of voters each submitting one coherent ranking. In settings where each person supplies a full ranking and interventions must preserve or pay for coherent preference changes, this mirror is too permissive. But that limitation does not undermine the Borda comparative-data regime; it identifies precisely which substantial class of the paper’s own applications has an honest continuous mirror.
I do not think the negative universal claim is defensible here. The proponent’s two anchors are really one mirror, but it is a good one—and that is enough.
For Theorem 3.3, the proposed type space \((\{a,b\},\text{reported winner})\) is a complete description of a comparison observation for the stated task. In a fixed, balanced comparative-data design, observations of a given pair and answer are genuinely interchangeable for both the Borda aggregate and the intervention cost. There can be very many of them per type. Moving a fraction of reports from one answer to the other is exactly the high-multiplicity relaxation of changing repeated comparisons. The normalization gives a literal correspondence with the paper’s weighted reversal operation, not merely an analogy.
The usual objection—that individual respondents have coherent rankings, heterogeneous reliability, or correlated judgments—does not defeat this. It only defeats this mirror for full-ballot elections or poorly specified survey models. The paper itself is about weighted tournaments and permits pairwise-comparison applications; a crowdsourced calibration, benchmark-comparison, or repeated forecasting regime supplies the required alternative scenario. Heterogeneous prices or sources can also be included in the type whenever they matter. Thus neither identity dependence nor lack of multiplicity is present in the best version of the model.
Theorem 3.1 survives for the same reason. Destructive and constructive Comparative-Borda MoV differ only in the target condition. The former asks for the least report mass needed to make another alternative overtake the present Borda winner; the latter asks for the least mass needed to put a given alternative at the top. Both retain an honest mass interpretation and a finite, high-multiplicity type space.
There is a limited negative observation: this is not a continuization of coherent-ranking bribery. It treats pairwise reports as independently editable, so it should not be advertised as modelling the alteration of ordinary voters’ complete preferences. But that boundary does not eliminate the comparative-data regime; it merely identifies it. Nor may one object that the resulting continuous problem is a rescaling of the weighted-tournament formulation or that it remains tractable: under the programme’s criteria, that is still a well-posed continuous-population computational question.
So the strongest honest negative conclusion is that the paper offers a narrow mirror rather than a universal one across all electoral interpretations. It does not defeat either Borda anchor, and I would green the paper on that basis.
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.