| paper | d4-conf-ijcai-2015-0329 |
| 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: Computing \(\operatorname{TEQ}(T_\mu)\) on the promised inputs is polynomial-time solvable in \(m,\tau,L\). · discrete side: polynomial · adjudication: proved
full proof & adversarial review →
Theorem 1
statement extracted from the paper’s text layer
Given (m ) alternatives and a finite support \{(\pi_i,\mu_i)\}_{i=1}^{\tau} of complete rankings with positive binary-rational masses summing to 1 , suppose every pair has a strict weighted majority comparison and the resulting tournament T_\mu has equal triangle packing and covering numbers. Compute \operatorname{TEQ}(T_\mu) .
Types are complete rankings of the m alternatives, and \mu_i is the population mass of type \pi_i . Pairwise majority comparisons induce T_\mu ; the input promises equal triangle packing and covering numbers, and the task is to return its tournament equilibrium set \operatorname{TEQ}(T_\mu) .
Covers Theorem 1’s uniqueness guarantee and polynomial-time computation for profiles whose majority tournament has equal triangle packing and covering numbers; it leaves Theorems 2–4 and the paper’s other structural results aside.
The strongest mirror is continuous TEQ evaluation on packing-covering-equal societies. Its anchor is Theorem 1, proved in this paper using structural results of Cai et al. (2001): Schwartz’s Conjecture holds for every tournament whose triangle packing number equals its triangle covering number, and the tournament equilibrium set \(\tau\) can be calculated in polynomial time on that class. Thus the theorem gives both uniqueness of the minimal \(\tau\)-retentive set and an algorithm for finding the winners.
For the mirror, fix \(m\) alternatives. An instance is a list of \(\tau\) complete rankings \(\pi_1,\ldots,\pi_\tau\), each with a positive binary rational mass \(\mu_i\), where \(\sum_i\mu_i=1\). Here \(\tau\) is the support size. The mass of a ranking is its share of the population. For each pair of alternatives, compare the total mass ranking one above the other; require that these pairwise comparisons have no ties, so they induce a tournament \(T_\mu\). Promise that \(T_\mu\)’s triangle packing and covering numbers are equal.
The question is: return \(\operatorname{TEQ}(T_\mu)\) exactly, where \(\operatorname{TEQ}\) denotes the paper’s tournament equilibrium set. A solution is the set of winning alternatives; there is no optimization objective, because the paper’s underlying task is to compute a tournament solution. By Theorem 1, the answer is also the unique minimal \(\tau\)-retentive set. Pairwise aggregation takes polynomial time in \(m,\tau,L\), where \(L\) is the encoding length of the masses, and the paper’s algorithm then computes the winners in polynomial time in \(m\). So this promised continuous problem is tractable.
A plausible regime is a large electorate repeatedly ranking a fixed set of proposals, with many people but relatively few recurring ballot types. The paper itself points to a particularly concrete subclass: alternatives form small groups of at most three similar options, voters share a consensus order over the groups, and any cycles occur within the groups. The resulting triangles are disjoint and ordered across groups, giving equal triangle packing and covering numbers. For rational masses, the profile is exactly realizable as a finite electorate by multiplying through by a common denominator; that electorate can be enormous, which is the high-multiplicity setting the continuous input captures. This is plausible for a large membership organization or recurring public consultation whose ballots come from a small set of preference patterns.
This mirror covers Theorem 1’s tractability result and its uniqueness guarantee on the promised class. It does not extend those claims to all tournaments or mirror the paper’s other structural results. Natural next questions are whether the promise class can itself be recognized efficiently from the mass profile, how the winners behave when small mass changes alter pairwise majorities, and whether the paper’s cited NP-hardness of determining membership in \(\tau\) for general tournaments transfers to a compact mass-profile input.
The soft spot is that the population distribution disappears once its pairwise-majority tournament has been computed: the mirror preserves the paper’s rule and winners exactly, but does not create a new computational question beyond evaluating that tournament solution. I still think it is a credible mirror because the paper introduces tournaments as the majority preferences of a group of agents, so a mass distribution over ballots is a direct population-level way to specify the object it studies.
The best objection is that Theorem 1 starts after the population has already been compressed away. Its input is a tournament, and its condition—equality of triangle packing and covering numbers—is a property of that tournament. For a society \(\mu\), the proposed task factors as
\[
\mu \longmapsto M(\mu) \longmapsto \operatorname{TEQ}(M(\mu)),
\]
where \(M(\mu)\) is the pairwise-majority tournament. Once \(M(\mu)\) is formed, neither the masses nor the ballot types affect the answer. Aggregation takes time polynomial in \(m\), the support size \(\tau\), and the mass bit length \(L\); the paper’s algorithm then runs on the graph. Every tournament also has a finite majority-profile realization with polynomially many voters, so this formulation does not expose a population structure that the theorem needs in order to work.
The stronger proposed scenario—many voters with recurring ballots and cycles confined to small groups of similar alternatives—is plausible. But it makes the profile a way to *encode* the tournament, not an active part of the computational question. A mass-perturbation or campaigning problem could make mass the quantity being optimized, but this paper gives no result about changing the tournament or the population. That would be a new problem, not a stronger mirror of Theorem 1.
This is a reason to treat the mirror as a thin profile-to-tournament wrapper, not a reason I can honestly claim that it is invalid. The paper itself motivates tournaments as majority preferences of agents, and returning TEQ from a rational distribution over rankings is a coherent high-multiplicity question. I cannot defeat that mirror’s strongest version: the negative case is weak at the author-recognition gate. My best case is that it adds little population-specific computation, not that no worthwhile continuous mirror exists.
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.