| paper | d4-conf-aaai-2024-1429 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
Theorem 2
statement extracted from the paper’s text layer
Given \(m\) alternatives and a rational distribution \(\mu\) over complete rankings, reveal alternatives in adversarial order and, at each arrival, reveal only the majority comparisons between the new alternative and those already arrived. The algorithm must maintain an ordering without changing the relative order of previously arrived alternatives. Is there a distribution over such societies and arrival orders for which every randomized strategy has expected backward-edge cost at least \(\Omega(m)\) times the offline optimum?
Types are complete rankings of the \(m\) alternatives, with rational masses \(\mu_t\) summing to \(1\). The majority relation induced by \(\mu\) defines the tournament. The algorithm sees only the comparisons revealed as alternatives arrive, and its loss is the number of backward majority edges relative to the offline minimum.
The society's masses affect only the majority signs: once those are fixed, the algorithm, objective, and offline benchmark are exactly those of online tournament FAS.
fatal: False
The mirror covers Theorems 1 and 2 for online ranking from majority comparisons. Theorems 3–6 sample alternatives rather than voter mass, so they are not covered by this population mirror.
The strongest mirror I see is the paper’s pure-online Kemeny–Young interpretation. The paper ranks alternatives from pairwise comparisons; a continuous electorate can generate those comparisons. Let \(C\) be \(m\) alternatives, and let each voter type \(t\in T\) be a complete ranking of \(C\). The society is a distribution \(\mu\) over rankings, with rational type masses summing to \(1\). For each pair of alternatives, the majority under \(\mu\) determines the corresponding tournament edge. Restrict to strict majorities, which is enough for the results below.
The online source instance is \(\mu\) together with an adversarial arrival order of the alternatives. To retain the paper’s online information model, the algorithm learns only the majority comparisons between a newly arriving alternative and those already arrived; it does not see \(\mu\) or unrevealed edges in advance. It must maintain an ordering and cannot change the relative order of alternatives already placed. Its loss is the number of backward edges in the completed ordering, compared with the minimum backward-edge count of an offline ordering of the same majority tournament. A solution is an online ranking strategy, or, for a lower bound, a distribution over society-and-arrival instances that defeats every randomized strategy.
This has a credible high-multiplicity regime: an electorate can have an arbitrarily large number \(N\) of voters but only \(\tau\) distinct ranking types. In fact, every strict tournament can be realized as the majority relation of a rational distribution over \(O(m^2)\) ranking types, using the standard majority-profile construction; replicating the voters makes \(N\) arbitrarily large without changing the tournament. So the mirror preserves the paper’s hard online instances while making the electorate a continuous society with \(N\) much larger than \(\tau\). The combinatorics that drive the lower bound remain in the number of alternatives \(m\).
My lead anchor is Theorem 2, a result of this paper rather than a result cited from elsewhere; its proof is omitted in the provided conference version. It states that there is a distribution over online feedback arc set instances with adversarial vertex arrivals for which every randomized algorithm has competitive ratio \(\Omega(n)\), where \(n\) is the number of vertices. Its continuous question is: for the online majority-tournament problem just defined, does there exist a distribution over rational societies \(\mu\) and adversarial alternative-arrival orders such that every randomized online ranking strategy has ratio \(\Omega(m)\)? The tournament-realization argument lifts the paper’s hard instances to such societies without changing the edge stream or offline optimum. I expect this lower bound to transfer: it is driven by the alternative count, not by the number of voters.
The paired upper-bound anchor is Theorem 1, also this paper’s result, with its detailed proof deferred in the provided version. It states that Algorithm 1 is \(O(n)\)-competitive for fully arbitrary vertex orders. The corresponding continuous question is whether an online strategy can rank alternatives from the revealed majority edges with loss at most \(O(m)\) times the offline optimum, for every society and arrival order. The paper’s pivot algorithm answers this directly, since it uses only the tournament edges. Together, these two mirrors predict a tight \(\Theta(m)\) competitive ratio. The upper-bound question is tractable in the online competitive sense; the lower-bound question is B-like, since its difficulty persists under high multiplicity and is driven by \(m\).
This mirror covers Theorems 1 and 2 only. Theorems 3–6 concern a sample of vertices—that is, alternatives in this interpretation—whereas the continuous population here is the electorate. I would not present those sample results as results about sampling voter mass. A separate model would be needed to ask whether a sample of voters changes the online guarantees.
The weakest point is the information model. The paper takes a tournament as input and never supplies a voter distribution; in this mirror, the society is the source of the tournament, but the online algorithm sees it only through the paper’s edge-revelation stream. If the full \(\mu\) were given to the algorithm at the outset, it could compute every majority edge, and the online lower-bound question would no longer match Theorem 2. This is a real limitation. The case for the mirror rests on the paper’s explicit connection to Kemeny–Young aggregation and on keeping its incremental information access.
The strongest objection is that Theorems 1 and 2 lift only by treating the electorate as a hidden way to generate the tournament. That makes them poor evidence for a computational question *about* a continuous society.
For a society \(\mu\), let
\[
\Delta_\mu(i,j)=\sum_t \mu_t\bigl(\mathbf{1}[i\succ_t j]-\mathbf{1}[j\succ_t i]\bigr).
\]
The proposed mirror uses only \(\operatorname{sgn}(\Delta_\mu(i,j))\). Its loss counts each backward majority edge once, regardless of the margin. Societies with very different supports and masses therefore become indistinguishable whenever they induce the same tournament. The voter distribution does no work in the online algorithm, the objective, or the offline benchmark.
That leaves Theorem 1 with a dilemma. If the online algorithm receives the full support and masses over a known candidate set, it can compute the tournament and an optimal offline order in advance, then insert each arriving candidate in that order; the online constraint preserves the old candidates’ relative order, so the ratio is \(1\). If it receives only the newly revealed majority comparisons, the pivot algorithm and its \(O(m)\) guarantee are exactly the paper’s result on an edge stream. The population is hidden provenance for that stream. A mass-sensitive Kemeny objective could retain more information, but its pair costs would depend on the margins or vote counts, and Theorem 1 would no longer be the result being mirrored.
Theorem 2 has the same problem in reverse. A rational society can realize each hard tournament, so pushing the lower-bound distribution through that representation gives the claimed \(\Omega(m)\) bound. That transfer is valid; hardness transferring from the alternative set is not itself an objection under the programme’s rules. The concern is that the proof and the bound still concern only online tournaments. The electorate contributes no additional computational structure. The sample results in Theorems 3–6 do not repair this: their samples are of alternatives, not voter mass.
This case against is limited. Online ranking from majority preferences is a coherent social-choice problem, and the paper explicitly invokes Kemeny–Young, so the authors might well recognize the proposed model. The objection is that it is a thin continuous mirror: with the paper’s unweighted objective, mass collapses to majority signs; with a mass-sensitive objective, these two theorems no longer anchor it. I cannot honestly rule out the online-majority model as worthwhile. If a mirror may count when society only supplies the tournament stream, the proponent’s case survives this objection.
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.