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.
Theorem 5 — class: other
PDF text-layer excerpt — equations and symbol order may be approximateSuppose there are n agents and m alternatives (where n is odd and m is even), and the agents’ preferences are known to be cardinally single-peaked, but the alternatives’ positions are not known. Then, to determine the aggregate ranking, in the worst case, at least (n + 1)m/4 comparison queries are necessary. Remarks: This remains true even if the alternatives’ ordinal positions are known at the beginning—more specifically, even if each alternative’s cardinal position is known at the beginning to lie in a certain interval, and these intervals do not overlap.
statement extracted from the paper’s text layer; consult the paper for the exact wording
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.
Definitions. Let \(A\) be \(m\) labelled alternatives and let \(\tau\) labelled cohorts have positive rational masses \(\mu_1,\ldots,\mu_\tau\) summing to \(1\). Hidden distinct positions \(r(a)\in\mathbb{R}\) and hidden ideals \(\theta_j\in\mathbb{R}\) satisfy \(|\theta_j-r(a)|\ne|\theta_j-r(b)|\) for \(a\ne b\).
A query \(Q(j,a,b)\) returns whether cohort \(j\) prefers \(a\) to \(b\), equivalently whether \(|\theta_j-r(a)|<|\theta_j-r(b)|\). Rank \(a\) above \(b\) when the total mass preferring \(a\) to \(b\) exceeds \(1/2\), tying them when it equals \(1/2\); output the resulting weighted aggregate ranking or its tie partition.
Target. Is the optimal worst-case comparison-query complexity for this problem \(\Theta(\tau m)\), or can an adaptive strategy determine the exact weighted aggregate ranking using \(o(\tau m)\) queries?
Nearest known results. For \(n\) individual agents, odd \(n\), and even \(m\), unknown alternative cardinal positions require at least \((n+1)m/4\) comparison queries in the worst case to determine the pairwise-majority aggregate ranking; this holds even when ordinal alternative positions are known.
No result for the mass-cohort formulation above is asserted here.
The worst case over positive rational mass vectors requires \(\Theta(m\log m+\tau m)\) queries to determine every pairwise aggregate outcome. Thus no adaptive strategy achieves \(o(\tau m)\) uniformly over the stated inputs. The bound becomes \(\Theta(\tau m)\) when \(\tau=\Omega(\log m)\).
Two qualifications are essential: some fixed mass vectors admit substantially fewer queries, and the pairwise rule in the question does not always define a ranking with tie classes.
1. The requested tie partition need not exist. Consider three alternatives with positions \(r(a)=-2\), \(r(b)=1\), and \(r(c)=4\). Take two cohorts of masses \(\mu_1=\mu_2=1/2\), with ideals \(\theta_1=0\) and \(\theta_2=10\).
Their respective distance vectors, in the order \(a,b,c\), are \((2,1,4)\) and \((12,9,6)\). Thus their strict rankings are \(b\succ a\succ c\) and \(c\succ b\succ a\). Every required individual comparison is strict.
Both cohorts prefer \(b\) to \(a\), while they disagree on each comparison involving \(c\). Consequently, the aggregate relation satisfies \(b\succ a\), \(a\sim c\), and \(b\sim c\). Aggregate indifference is therefore not transitive.
In particular, no ordered tie partition represents these outcomes: the two ties would put all three alternatives in one class, contradicting \(b\succ a\). Literally, the requested output does not exist on every admissible input.
The remainder establishes the tight query bound for the natural, always-defined output: all pairwise aggregate outcomes. The lower bound also holds on instances whose aggregate is a strict ranking.
2. Precise complexity statement. Assume \(m\geq 2\) and \(\tau\geq 1\). For a fixed, known mass vector \(\boldsymbol{\mu}\), let \(C(\boldsymbol{\mu},m)\) denote the optimal deterministic adaptive worst-case number of queries required to determine all pairwise outcomes, with the worst case taken over admissible positions and ideals. Define \(C_{\max}(\tau,m)=\sup_{\boldsymbol{\mu}}C(\boldsymbol{\mu},m)\), where the supremum ranges over positive rational mass vectors of length \(\tau\) summing to one.
We prove \(C_{\max}(\tau,m)=\Theta(m\log m+\tau m)\). For \(m=1\), no queries are necessary.
3. Upper bound. We use the following established elicitation theorem: if strict preferences are single-peaked with respect to a common, possibly unknown alternative order, knowing one complete preference ranking allows another ranking to be elicited using at most \(4m-6\) comparison queries. This is Theorem 2 in [Conitzer, *Eliciting Single-Peaked Preferences Using Comparison Queries*](https://www.cs.cmu.edu/~conitzer/singlepeakedJAIR.pdf).
Its hypotheses hold here. Order the alternatives by their distinct positions. For any cohort, distances decrease toward its ideal and increase afterward. Equivalently, for positions \(x<y<z\), the inequality \(|\theta_j-y|\leq\max\{|\theta_j-x|,|\theta_j-z|\}\) prevents a preference valley. The assumed absence of equal distances makes each ranking strict. All cohorts share the same alternative order.
First sort one cohort’s alternatives using at most \(m\lceil\log_2m\rceil\) queries. Apply the theorem to each remaining cohort, always using the first ranking as reference. The total is at most \(m\lceil\log_2m\rceil+(\tau-1)(4m-6)\).
Once every ranking is known, compute, for every pair, the rational sum \(\sum_{j:\,a\succ_j b}\mu_j\) and compare it with \(1/2\). This requires no further queries. Hence \(C(\boldsymbol{\mu},m)=O(m\log m+\tau m)\) for every admissible mass vector.
4. A sorting lower bound for every mass vector. Fix any admissible \(\boldsymbol{\mu}\). For each permutation \(\pi\) of the labelled alternatives, set every ideal to zero and set \(r(\pi(k))=k\) for \(1\leq k\leq m\).
All cohorts then have the same strict ranking \(\pi(1)\succ\cdots\succ\pi(m)\), which is also the aggregate ranking. Thus these admissible instances produce \(m!\) distinct required outputs.
A binary comparison-query decision tree of worst-case depth \(q\) has at most \(2^q\) leaves. Distinct outputs require distinct leaves, so \(q\geq\lceil\log_2(m!)\rceil\).
For \(m\geq4\), at least \(m/2\) factors in \(m!\) are at least \(m/2\), giving \(\log_2(m!)\geq(m/2)\log_2(m/2)\). Consequently, \(C(\boldsymbol{\mu},m)=\Omega(m\log m)\) for every mass vector.
This already rules out an unconditional \(\Theta(\tau m)\) formula when, for example, \(\tau=1\).
5. Transferring the supplied lower bound to cohorts. Let \(n\) be the largest odd integer at most \(\tau\), and let \(M\) be the largest even integer at most \(m\). The lower bound supplied in the question states that some instances with \(n\) individuals and \(M\) alternatives require at least \((n+1)M/4\) queries.
We reduce that individual-agent problem to a cohort problem with exactly the desired parameter values.
If \(\tau\) is odd, then \(n=\tau\). Give each cohort mass \(1/n\) and let it represent the corresponding individual. Every query answer and aggregate pairwise outcome is unchanged.
If \(\tau\) is even, then \(n=\tau-1\). Represent the first \(n-1\) individuals by cohorts of mass \(1/n\). Represent the last individual by two labelled cohorts, each of mass \(1/(2n)\), sharing that individual’s ideal. There are exactly \(\tau\) cohorts, and all masses are positive rational numbers summing to one.
For every alternative pair, the two split cohorts together contribute exactly the original individual’s mass. Thus the aggregate outcomes are unchanged. A query to either split cohort can be simulated by one query to the original individual. Coincident cohort ideals are permitted by the definitions.
If \(m\) is odd, add one alternative \(d\) that every cohort ranks last. This extension is always realizable: for any realization of the original instance, let \(D=\max_{j,a}|\theta_j-r(a)|\), and choose \(r(d)\) larger than every original alternative position and every \(\theta_j+D\). Then \(|\theta_j-r(d)|>D\) for every cohort. Queries involving \(d\) have known answers and require no original-agent query.
Therefore, an algorithm for these cohort instances would solve the original individual-agent problem using no more queries. Its worst-case cost is at least \((n+1)M/4\). Since \(n+1\geq\tau\) and \(M\geq m/2\), we obtain \(C_{\max}(\tau,m)\geq\tau m/8\).
This reduction preserves the original odd-electorate majority outcomes, so its hard instances have no aggregate ties.
Combining this lower bound with the sorting lower bound gives \(\Omega(m\log m+\tau m)\): the maximum of two nonnegative quantities is at least half their sum. Together with the upper bound, this proves the claimed tight formula.
6. Fixed masses can permit fewer queries. Suppose a known cohort \(h\) has mass \(\mu_h>1/2\). Whenever it prefers \(a\) to \(b\), the mass supporting that preference is at least \(\mu_h>1/2\). Hence every aggregate comparison agrees with cohort \(h\).
Sorting only its ranking solves the problem in \(O(m\log m)\) queries. The sorting lower bound above also applies, so \(C(\boldsymbol{\mu},m)=\Theta(m\log m)\) for every such mass vector.
For example, take \(\mu_1=3/4\) and \(\mu_j=1/[4(\tau-1)]\) for \(2\leq j\leq\tau\). Along any sequence with \(\tau/\log m\to\infty\), this complexity is \(o(\tau m)\).
Thus the quantifiers matter: a uniform subproduct bound is impossible, but a product lower bound for every prescribed mass vector is false. The literal ranking-output formulation additionally requires a restriction or revised output convention because aggregate ties need not form a partition.
⟨structured verdict parsed — rendered above⟩
The argument is correct in substance. It establishes that the literal requested output need not exist and proves the stated tight bound for its explicitly revised output, all pairwise aggregate outcomes. I found no major issue and one minor domain omission.
The deterministic query model and the worst case over mass vectors are stated explicitly. The result should be read with those qualifications.
The two distance vectors are correctly computed as \((2,1,4)\) and \((12,9,6)\). Each has distinct entries, so the strictness hypothesis is satisfied.
Both cohorts prefer \(b\) to \(a\), giving that preference total mass \(1\). Exactly one cohort supports each direction of the other two comparisons, giving \(a\sim c\) and \(b\sim c\).
These outcomes cannot be represented by an ordered tie partition: the two ties would require \(a,b,c\) to belong to the same class, contradicting \(b\succ a\). This is a decisive objection to the literal formulation, rather than a failure of the prover’s argument.
The definition of \(C(\boldsymbol{\mu},m)\) fixes the known masses and takes the worst case over admissible hidden realizations. The definition of \(C_{\max}(\tau,m)\) additionally takes the supremum over allowed mass vectors.
Consequently, the claimed lower bound concerns the worst mass vectors; it does not assert a product lower bound for every mass vector. The subsequent example of a dominant cohort is consistent with this distinction.
The restriction to deterministic adaptive algorithms is explicit. No claim about bounded-error randomized query complexity is established.
Conitzer’s Theorem 2 gives the stated bound of \(4m-6\) comparisons for eliciting another strict ranking from one known ranking when both are single-peaked on a common unknown alternative order. The theorem and surrounding assumptions match the prover’s statement. [Conitzer, Theorem 2](https://www.cs.cmu.edu/~conitzer/singlepeakedJAIR.pdf)
The prover verifies the necessary hypotheses: distinct alternative positions supply a common order, the displayed distance inequality excludes preference valleys, and the no-equal-distances assumption makes each ranking strict. Neither distinct cohort ideals nor knowledge of the common alternative order is required.
Sorting the first ranking and then applying the theorem gives the stated total
\(m\lceil\log_2m\rceil+(\tau-1)(4m-6)\).
This expression is valid for the specified range \(m\geq2\), including \(\tau=1\).
Once all rankings are elicited, exact rational mass sums determine every pairwise outcome without further oracle queries. The upper bound is therefore established in the stated query model.
For each permutation, assigning positions \(1,\ldots,m\) in that order and giving every cohort ideal zero yields an admissible instance. All cohorts have the same strict ranking, so every positive mass vector produces that same aggregate ranking.
There are \(m!\) distinct outputs. Each query has only two possible answers, so the binary decision-tree argument correctly gives a lower bound of \(\lceil\log_2(m!)\rceil\).
The factorial estimate for \(m\geq4\) is correct, including odd \(m\). The exact decision-tree bound also covers \(m=2,3\), so the asymptotic conclusion has no missing substantive edge case.
The chosen parameters satisfy the supplied theorem’s hypotheses: \(n\) is positive and odd, and \(M\) is positive and even.
For odd \(\tau\), equal cohort masses reproduce individual majority outcomes exactly. For even \(\tau\), splitting one individual into two identical cohorts preserves its combined mass and every aggregate comparison. The resulting cohort count and mass sum are correct, including \(\tau=2\), when \(n=1\).
Each cohort query can be simulated with at most one individual query. Repeated queries to the split individual do not invalidate that inequality.
The padding alternative is also legitimate. The specified strict inequality for its position makes it distinct from all original alternatives and farther from every ideal than every original alternative. Its comparison answers are therefore known without querying the original instance. The simulator needs only those answers, not numerical knowledge of the hidden realization.
Finally, \(n+1\geq\tau\) and \(M\geq m/2\) hold throughout the stated range, yielding \(\tau m/8\).
The claim that hard instances can have strict aggregate rankings is consistent with the supplied lower-bound problem. The cited construction also explicitly places the aggregate into ordered two-alternative blocks, with odd-electorate comparisons resolving each block. [Conitzer, Theorem 5](https://www.cs.cmu.edu/~conitzer/singlepeakedJAIR.pdf)
The sorting lower bound holds for every admissible mass vector, and the transferred lower bound supplies an admissible mass vector for each parameter pair. Thus both lower bounds apply to \(C_{\max}\).
Taking their maximum gives the claimed lower bound for their sum up to a constant factor. Together with the upper bound, this establishes
\(C_{\max}(\tau,m)=\Theta(m\log m+\tau m)\).
The stated simplification when \(\tau=\Omega(\log m)\), and the rejection of an unconditional \(\Theta(\tau m)\) formula when \(\tau=1\), both follow.
If \(\mu_h>1/2\), every aggregate comparison follows cohort \(h\). Sorting that cohort gives the upper bound, and the earlier sorting lower bound gives the matching lower bound.
Minor issue: the illustrative mass vector containing \(1/[4(\tau-1)]\) should explicitly be restricted to \(\tau\geq2\). As written, its first mass is \(3/4\), so at \(\tau=1\) it does not define an admissible mass vector.
Minimum clarification: prepend “For \(\tau\geq2\)” to that example. This does not affect the asserted asymptotic separation.
The genuine result is a tight deterministic comparison-query bound for the revised pairwise-output problem, together with a valid obstruction to the original tie-partition requirement. The complexity classification below records this query-complexity result, without interpreting its oracle lower bound as computational hardness.
⟨structured verdict parsed — rendered above⟩
Tier: machine-proved, adversarially reviewed by an independent model. No human has checked this proof. Generated from pipeline artifacts by tools/atlas_build.py.