| paper | d4-conf-ijcai-2016-0307 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | no |
Theorem 10 studies the cost of discovering preferences through comparisons to named voters. The proposed mass-list model makes the full distribution available and reduces the task to computing a winner from known data. That is a sensible weighted winner problem, but no continuous version of the anchored elicitation question survives.
fails bit b-changes — the continuum limit changes the question
The proposal reformulates weak Condorcet winner determination for star-single-peaked rankings with known masses; it does not mirror Theorem 10's query lower bound or the paper's preference elicitation and tree-parameter query results.
The strongest honest positive mirror is finding a weak Condorcet winner from a high-multiplicity society. The paper has no named NP-hardness, polynomial-time, or parameterized-complexity result. Its named results concern query complexity; my anchor is Theorem 10, proved in this paper: for profiles single-peaked on a star with \(m\) candidates and \(n\) voters, every algorithm that finds a weak Condorcet winner needs \(\Omega(mn)\) pairwise comparison queries in the worst case. The theorem’s queries compare two candidates for one specified voter.
A plausible high-multiplicity regime is a large membership or resident population choosing among a central status-quo option and several alternatives. Preferences follow a known star-shaped tree: each person has a complete ranking that is single-peaked on that tree. There may be, say, \(100{,}000\) people but only a few dozen distinct complete rankings. A type is the complete ranking; its mass is the fraction of the population with that ranking. That grouping preserves the preference information relevant to this problem.
Call the mirror Star-Mass-WCDub. An instance consists of a candidate set \(C\), a known star \(T\) on \(C\), and a list of distinct rankings \(t\) single-peaked on \(T\), each with a positive binary-rational mass \(\mu_t\), where \(\sum_t\mu_t=1\). If the list has size \(\tau\), the task is to return a candidate \(c\) such that, for every other candidate \(y\),
\[
\sum_{t:\,y\succ_t c}\mu_t\le \frac12.
\]
There is no cost objective: a candidate satisfying these inequalities is a solution. The paper’s stated existence result for weak Condorcet winners on tree-single-peaked profiles guarantees one exists here too.
This mirror should be tractable. Accumulate, for each pair \(y,c\), the mass of types ranking \(y\) above \(c\), then return a candidate meeting the inequalities. Direct evaluation takes \(O(\tau m^2)\) rational operations, with bit complexity polynomial in \(m,\tau,L\), where \(L\) is the mass encoding length. I expect Class A. Theorem 10’s \(\Omega(mn)\) query lower bound does not carry over: the continuous input groups identical rankings and supplies their masses, so the algorithm processes types rather than interrogating named individuals.
The scope is deliberately limited to the paper’s weak-Condorcet-winner task. It does not mirror preference elicitation: pairwise aggregate masses need not determine the full distribution over rankings. It also does not establish that the paper’s query lower bound itself disappears under every access model. A useful next question is how many exact aggregate pairwise-mass queries suffice when the support is hidden, and how that depends on \(m,\tau,L\).
The weak point is the change in access model. Theorem 10 studies an unknown profile exposed through individual comparison queries; Star-Mass-WCDub takes the mass distribution as input. The authors would recognize the winner-finding objective, but might view the explicit mass list as changing the information problem that drives their lower bound. That makes this a credible mirror of their underlying social-choice problem, but a modest case for mirroring the theorem’s query model itself.
The paper does have named computational results: its query complexity bounds are computational claims, even though they are not running-time results. Theorem 10 is therefore a legitimate anchor to consider. The difficulty is that its lower bound is specifically about eliciting a winner: the profile is unknown, and each query compares two candidates for one named voter.
Star-Mass-WCDub changes that information model. Its input gives the complete rankings and masses, so it has already supplied the information that Theorem 10’s algorithm must acquire through queries. It preserves the winner-finding objective, but it does not mirror the theorem’s \(\Omega(mn)\) query lower bound. In the paper’s setting, \(n\) counts separately queryable people; in the proposed mirror, those people have become known mass entries.
The closest version that preserves the original access model would query individuals in a large population. But for a continuous society, an individual has zero mass. Randomly sampling individuals instead gives a statistical problem: without a margin promise, finitely many samples cannot in general certify an exact weak Condorcet winner when pairwise support is arbitrarily close to \(1/2\). Adding a margin or asking for an approximate winner may be sensible, but it introduces a sampling model and parameters absent from Theorem 10. Asking an oracle for exact aggregate masses avoids that problem by supplying the pairwise statistics directly; it is a different oracle model, not a continuous version of the paper’s per-voter query bound.
That is the strongest objection to this anchor: the explicit mass-list mirror may be a valid weighted winner-finding problem, but it does not continue the paper’s central information-acquisition question. This objection is narrow. Repeated ballot types in a large membership or resident population are plausible, and nothing about the weak Condorcet condition degenerates under fractional masses. So I cannot honestly rule out every worthwhile continuous question here. I can only say that the proposed mirror supports a new full-information problem, while the paper’s main result is about the cost of discovering preferences from individuals.
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.