| paper | Eliciting single-peaked preferences using comparison queries |
| authors | Vincent Conitzer |
| venue | ATAL 2007 |
| filed under | voting · incomplete-info |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
other→other discrete result → its continuous mirror
Answer: The stated tie-partition output need not exist. For determining all pairwise aggregate outcomes, the worst case over positive rational mass vectors is \(\Theta(m\log m+\tau m)\), so a uniform \(o(\tau m)\) strategy is impossible. Some fixed mass vectors admit \(\Theta(m\log m)\) queries. · discrete side: other · adjudication: proved_with_minor_gaps
full proof & adversarial review →
Theorem 5
statement extracted from the paper’s text layer
Given \(m\) alternatives, labelled cohorts with known masses \(\mu_1,\ldots,\mu_\tau\) satisfying \(\sum_j\mu_j=1\), unknown common cardinal positions \(r(a)\), and unknown cohort ideal points \(\theta_j\), adaptively query \(Q(j,a,b)\) and output the exact \(\mu\)-weighted aggregate ranking, or its tie partition, minimizing worst-case query count.
A finite-support society whose homogeneous cohorts have masses \(\mu_j\); decision variables are adaptive cohort-level comparisons \(Q(j,a,b)\), the objective is exact recovery of every cohort ranking or the mass-weighted aggregate ranking, and complexity is measured by worst-case queries as a function of \(m\), \(\tau\), and \(\mu\).
The mirror depends on publicly known cohort labels and exact masses, an access model absent from the original paper; without it, anonymous finite queries cannot exactly recover an arbitrary population distribution.
fatal: False
The mirror covers the paper's exact-profile and aggregate-ranking elicitation results, including Theorems 2, 3, and 5; it leaves winner-only elicitation, experiments, and the almost-single-peaked discussion outside.
I think there is a defensible positive case, but it depends on a specific high-multiplicity regime: a large consultation population divided into publicly identifiable, homogeneous cohorts. For example, suppose \(N\) citizens are choosing among \(m\) budget levels or locations, but there are only \(\tau\) policy-position cohorts, with \(N\gg\tau\). Cohort \(j\) has mass \(\mu_j\), where
\[ \mu=\sum_{j=1}^{\tau}\mu_j\delta_{t_j},\qquad \sum_j\mu_j=1. \]
All members of cohort \(j\) have the same complete preference type \(t_j\): the same ranking, and, in the cardinal model, the same ideal position and all other parameters relevant to answering queries. The masses \(\mu_j\) are known, but the cohort rankings are not.
A comparison query selects a cohort \(j\) and two alternatives \(a,b\), and asks one representative whether \(a\succ_j b\). Because the cohort is homogeneous, one answer applies to its entire mass. The aggregate relation is
\[ a\succ_\mu b \quad\Longleftrightarrow\quad \sum_{j=1}^{\tau}\mu_j \mathbf 1[\pi_j(a)\succ\pi_j(b)]>\frac12. \]
The action is therefore an adaptive choice of cohort-level comparison queries; the objective is to minimize the worst-case number of queries while recovering either every cohort ranking or the aggregate ranking. This is a population continuization, not a continuization of the alternatives or the outcome. The real-valued cardinal positions are inherited from the paper’s model.
My lead anchor is Theorem 5, proved in this paper. It states that, when there are \(n\) agents and \(m\) alternatives with \(n\) odd and \(m\) even, agents have cardinally single-peaked preferences, and the alternatives’ cardinal positions are unknown, at least \((n+1)m/4\) comparison queries are necessary in the worst case to determine the aggregate ranking. The lower bound remains even if the alternatives’ ordinal positions are known through nonoverlapping cardinal intervals, and even if queries may be interleaved arbitrarily among agents.
The continuous mirror is:
\[ \mathrm{Cohort\text{-}Aggregate\text{-}Elicitation}_{\infty}. \]
An instance has \(m\) alternatives, \(\tau\) known cohort masses \(\mu_1,\dots,\mu_\tau\), unknown common alternative positions \(r(a)\), and unknown cohort ideal positions \(\theta_j\), with every cohort ranking alternatives by distance to its ideal point. The elicitor may ask \(Q(j,a,b)\), receiving the common answer of cohort \(j\). It must output the strict aggregate ranking induced by \(\mu\), for every feasible hidden configuration; ties can either be excluded or reported explicitly.
On the separated-interval family used in Theorem 5, let
\[ I_i=[k_i-1,k_i+1], \qquad k_i=10(-1)^i\left\lfloor\frac{i+1}{2}\right\rfloor, \]
and suppose \(r(a_i)\in I_i\), while every \(\theta_j\in[-1,1]\). The alternatives occur in fixed blocks \(\{a_1,a_2\},\{a_3,a_4\},\ldots\), so the only uncertainty is which alternative wins each block. Querying every cohort on
\[ (a_1,a_2),(a_3,a_4),\ldots,(a_{m-1},a_m) \]
takes exactly \(\tau m/2\) queries, after which the weighted majority in each block is known. The result is independent of the total population size \(N\). If \(\tau=O(1)\) while \(N\) grows, the paper’s \(nm\)-type information lower bound disappears and becomes a question about the number of distinct types.
For the unrestricted unknown-position version, a simple exact algorithm first elicits one cohort’s ranking by ordinary sorting, then uses Theorem 2’s procedure for every other cohort. Thus the query count is
\[ O(m\log m)+(\tau-1)(4m-6), \]
after which weighted majority computation produces the aggregate ranking. I therefore expect this mirror to be Class A: tractable in the finite-support, labelled-cohort regime. Its natural open question is whether aggregate-only elicitation can improve on this by exploiting the masses, especially when a few large cohorts already determine most pairwise majorities.
My second anchor is Theorem 2, also proved in this paper. It says that, when preferences are ordinally single-peaked but the common ordinal positions are unknown, a complete ranking of a new agent can be elicited using at most \(4m-6\) comparison queries provided one other agent’s complete ranking is already known.
The corresponding continuous problem is \(\mathrm{Cohort\text{-}Profile\text{-}Elicitation}_{\infty}\). The instance is a finite-support society \(\mu\) over \(\tau\) labelled homogeneous cohorts, all obeying one unknown single-peaked order. The task is to recover every cohort’s complete ranking, and hence the full distribution \(\mu\) over preference types. One cohort is first elicited using \(O(m\log m)\) ordinary comparisons; each remaining cohort is elicited with at most \(4m-6\) representative queries. This is exactly the paper’s elicitation problem with interchangeable agents compressed into types. It is again Class A, with complexity depending on \(\tau\), not \(N\).
A third, cleaner variant mirrors Theorem 3, proved here as well. Theorem 3 states that if the alternatives’ cardinal positions are known and preferences are cardinally single-peaked, the algorithm \(\mathrm{FindRankingGivenCardinalPositions}\) recovers one agent’s complete ranking using at most \(2\lceil\log m\rceil\) comparison queries. The continuous problem asks for every cohort ranking under the same known-cardinal-position assumption. Running the algorithm once per type gives
\[ 2\tau\lceil\log m\rceil \]
queries, followed by mass-weighted aggregation. Full type recovery should also require \(\Omega(\tau\log m)\) queries in the worst case, since each cohort’s peak can encode one of \(m\) possibilities. This is another Class A mirror.
The high-multiplicity dictionary is direct. A discrete profile with \(n_j\) agents of type \(t_j\) becomes \(\mu_j=n_j/N\); conversely, rational \(\mu_j\) can be cleared to obtain a finite profile. Taking \(\tau=N\) and all masses equal recovers the paper’s original named-agent model. Taking \(N\gg\tau\) is the genuinely new regime, where one query reveals information about an entire mass of agents.
The weakest point is the labelled-cohort assumption. The paper asks named individuals, and it does not provide an oracle identifying which agents share a type. If the elicitor can only sample anonymous individuals from an arbitrary continuum, exact recovery of \(\mu\) is generally impossible with finitely many queries. My mirror is therefore conditional on a scenario with known cohort membership and known cohort masses, such as institutional constituencies, demographic panels, or repeated consultation groups. That is a real modelling restriction, but it is precisely the kind of instance regime in which high multiplicity is meaningful.
The paper contains no named NP-hardness or parameterized-hardness theorem, so I cannot honestly offer a hardness-transfer anchor. Its strongest usable results are query-complexity upper and lower bounds. The mirror covers the paper’s exact and aggregate elicitation results, not the experimental section, the almost-single-peaked propositions, or winner-only elicitation.
The strongest negative argument is not that the paper lacks computational theorems. It has several. The problem is that all three are query-complexity theorems about hidden preferences of named agents, whereas a continuous society requires a well-defined representation and access model for a distribution. Once that access model is supplied, the proposed mirrors either cease to be the paper’s problems or reduce to a finite weighted query problem in which the population mass does no conceptual work.
Theorem 5 is the strongest anchor, but its lower bound is fundamentally identity-based. For each pair \((a_i,a_{i+1})\), the proof keeps the answers of named agents fixed and changes the hidden position of one unqueried agent, thereby changing the majority. The \(\Omega(nm)\) information is therefore carried by \(n\) independently addressable agents, not by population mass.
If those agents are placed into known homogeneous cohorts, one query reveals the answer for the whole cohort. That is a legitimate weighted-majority problem, but it is a new oracle model: the elicitor is given cohort labels and masses, although it does not know the cohort rankings. The continuous society is never itself queried or optimized over; it merely supplies weights to a final majority calculation. The natural complexity parameter is the number \(\tau\) of labelled representatives. This is compression by known equivalence classes, not a continuous version of the theorem’s lower-bound object.
The stronger possible formulation does not repair this. If cohorts are anonymous and the elicitor receives only individual comparison answers, exact aggregate ranking is impossible in general: finitely many answers leave unqueried positive mass that can be assigned different preferences while preserving the entire transcript. If queries instead return the fraction of society preferring \(a\) to \(b\), the oracle has been changed into an aggregate-statistics oracle; the answer is already the population-level quantity the original paper computes from individual queries. If queries are random samples, the problem becomes statistical estimation and requires approximation or margin assumptions absent from the paper. Thus the proposed Theorem 5 mirror has no canonical continuous interface.
Theorem 2 is weaker still. Its task is to recover every new agent’s complete ranking after one ranking is known. In a cohort version, the natural algorithm simply runs once per cohort. The masses do not affect the task, the query count, or the correctness argument. Changing \(\mu_j\) while keeping the cohort rankings fixed leaves the problem unchanged. If cohort membership is not known, the task is no longer “elicit a type” but “discover which agents are interchangeable,” which the paper does not study and which cannot be done exactly from anonymous finite querying. The proposed mirror is therefore either a finite list of \(\tau\) representatives or an underspecified distribution-learning problem.
Theorem 3 has the same defect in a particularly transparent form. The real-valued cardinal positions are already part of the paper’s model; distributing agents over ideal positions does not continuize the population unless the distribution itself is the object to be learned. For an arbitrary measure over ideal positions, individual comparison queries reveal only threshold information about queried agents, and exact recovery of the distribution is impossible with finitely many queries. With known finite cohorts, one again obtains \(2\tau\lceil\log m\rceil\) queries by repeating the paper’s algorithm, but this is simply the paper’s single-agent result applied to \(\tau\) representatives. With aggregate fraction queries, one has introduced a different oracle and a different problem.
There is a genuine vulnerability in this negative case. A consultation system with publicly identified, genuinely homogeneous constituencies and known constituency sizes is a sensible high-multiplicity regime. In that regime, the weighted version of Theorem 5 is well posed, and its adaptive query complexity could be worth studying. I cannot honestly claim that no worthwhile mirror exists there. But the positive result comes from adding a new labelled-cohort access model, not from a continuous limit of the paper’s elicitation problem. Under a stricter ChoCo requirement that the society be supplied as a distributional computational object rather than as an oracle over preidentified representatives, Theorems 2 and 3 do not survive, and Theorem 5 does not yield a canonical continuous mirror.
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.