| paper | d4-conf-aaai-2017-0660 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
Both theorems are named computational results, but the proposed mirrors require a hidden-population majority oracle. With the programme’s stated input of types and masses, pairwise majority orientations can be computed directly; hiding those masses leaves the tournament oracle problem unchanged. The paper’s large-electorate motivation makes that application recognizable, but it does not make the population the computational object.
fails bit b-none — no population with multiplicity to relax
The proposal covers Theorem 2’s lower bounds and Theorem 11’s promised upper bound; it leaves the other tournament query results without a population mirror.
The strongest mirror is an electorate that induces the tournament the paper’s algorithms must learn. Fix a candidate set \(C\) of odd size \(n\), and let each voter type \(t\) be a complete ranking of \(C\). The society is a rational distribution \(\mu\) over those rankings; \(\mu_t\) is the fraction of the population with ranking \(t\). A pairwise query for \(a,b\) returns whether \(\sum_{t:a\succ_t b}\mu_t>1/2\) or \(<1/2\), with ties excluded. The target is an exact tournament solution, and the algorithm’s choices of pairs to query are its decision variables; its objective is to minimize the worst-case number of queries, or the worst-case expected number for randomized algorithms.
Call this Continuous-Population Majority-Oracle Set Computation. The target \(f\) is Copeland, Slater, or Markov, and a solution is the exact set \(f(T_\mu)\) for the majority tournament induced by \(\mu\). The lead anchor is Theorem 2, proved in this paper: for tournaments on an odd number of vertices, any randomized algorithm computing the Copeland set, the Slater set, or the Markov set has expected query complexity \({n\choose 2}\). In the population version, that says each of these exact-set problems still requires \({n\choose 2}\) expected pair queries in the worst case.
The transfer is direct. Every tournament can be induced as a strict-majority tournament of rational ranking masses: for each directed pair, use two rankings that support that direction and cancel each other on every other pair. This uses at most \(n(n-1)\) ranking types. Thus the tournament instances behind Theorem 2 have continuous-population counterparts with exactly the same oracle answers and outputs, so the query lower bound carries over. This is my strongest mirror, and I expect hardness to transfer (Class B), rather than a population continuum to remove the lower bound.
A second, complementary mirror is Small-Top-Cycle Population Query Computation. It has the same electorate and oracle, adds the promise that the induced majority tournament’s top cycle has size at most \(k\), and asks for the exact Copeland, Slater, Markov, bipartisan, uncovered, or Banks set. Theorem 11, also proved here, says that when this size bound is known, each of those six sets can be found using \(\mathcal{O}\!\left(nk+\frac{n\log(n/k)}{\log(k/(k-1))}\right)\) queries. That bound carries over unchanged to this population-oracle problem. I expect a tractable, parameter-restricted case (Class A): for fixed small \(k\), the query count is \(\mathcal{O}(n\log n)\). It also raises a further question: can an algorithm certify the small-top-cycle promise within a comparable query bound, rather than being given it?
The regime is plausible in the paper’s own terms. Think of millions of users ranking products, with many users sharing the same ranking type and a costly pairwise market audit revealing which product a strict majority prefers. The type is complete for this problem: users with the same ranking are indistinguishable to every query and solution rule used here. In the worst-case realization above, the support is at most \(n(n-1)\), while the population can be scaled arbitrarily far beyond that. The paper explicitly motivates its edge-query model by the cost of learning majority relations in large electorates, so I expect its authors to recognize this as their problem with the population represented as mass. The oracle reports exact majority orientation; it does not sample voters or add noise, and the continuity is in the population rather than in outcomes or time.
My weakest point is the representation. In the programme’s standard model, the support and masses are given to the algorithm. If that full list is visible here, all pairwise majorities can be computed from it, and these query lower bounds do not establish a lower bound on running time in \(n,\tau,L\). This mirror therefore depends on treating the population as an implicitly accessible distribution, with pairwise majority queries as the costly input interface. That is a real qualification, but it preserves the paper’s central computational question and matches its stated application. The next sharp question would be whether the lower bound survives if each query returns the numerical pairwise margin, rather than only its orientation.
The paper does have named computational results, so the objection is not that it lacks an anchor. The difficulty is that its query input is a tournament, not a society.
For Theorem 2, the natural continuous society would be a rational distribution \(\mu\) over rankings. But if \(\mu\) is given as a list of types and masses, the algorithm can compute each pairwise majority directly from \(\sum_{t:a\succ_t b}\mu_t\). There is no need to query an edge. That leaves a running-time question about computing the solution from the resulting tournament, but it is not the query-complexity question Theorem 2 answers.
The proponent’s stronger version hides \(\mu\) and gives the algorithm a majority-orientation oracle. That is coherent as a model of costly audits, and the paper’s motivation about large electorates makes it a plausible application. But it makes the population a hidden source for the oracle, not the input being continuized. Every tournament can be induced by a rational ranking profile with support bounded in terms of the number of alternatives, so the oracle can expose exactly the same instances as in the paper. Once an edge is queried, its answer depends only on the tournament; the population’s support and masses never affect the query problem. Theorem 2 then transfers because the oracle problem is unchanged, not because continuous mass has created a new computational object. Asking for numerical margins would not repair this anchor: the solution depends on edge orientations, and margin-sensitive costs or sampling would be a different query model.
Theorem 11 has the same problem. Its promise concerns the size of the top cycle among alternatives. With an explicit society, the algorithm can derive the whole tournament without edge queries; with a hidden majority oracle, the theorem applies unchanged to the same tournament promise. Asking an algorithm to certify the promise would add a question about the tournament oracle, not make the population distribution computationally relevant.
So the negative case rests on an input mismatch, not on the results being dull or on hardness surviving continuization. Under ChoCo’s stated model, the society is supplied by its types and masses; then these edge-query anchors have no query cost to study. Under the proponent’s hidden-population model, the anchors remain meaningful, but the population is only the provenance of an otherwise unchanged tournament oracle. That is the weak point in my case: the hidden-population reading is a credible application story, and the authors might recognize it. I still would not count it as a worthwhile continuous mirror under the programme’s input model.
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.