Answer: \(Q(m,L)=\Theta(m\log m+mn_L\log(1+m/n_L)+m^2\log(1+n_L/m))\), where \(n_L\) is one plus the number of admissible interior boundaries. For binary-encoded rationals, \(n_L=\Theta(L2^L)\); for dyadic rationals, \(n_L=\Theta(2^{L/2})\).
Theorem 1 — class: other
PDF text-layer excerpt — equations and symbol order may be approximateSuppose a profile P is single crossing with respect to the identity permutation of votes. Given random access to voters, any Preference Elicitation algorithm has query complexity Ω(mlog m + mlog n).
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given \(m\) candidates and oracle access to an unknown single-crossing ranking map \(R:[0,1]\to L(C)\), whose rational change points have at most \(L\) bits and whose mass order is known, what is the optimal worst-case number of queries \((u,x,y)\) needed to recover \(R\) almost everywhere?
Let \(C\) contain \(m\ge 2\) candidates, and let \(\mathcal L(C)\) denote strict rankings. Voters occupy \([0,1]\) with Lebesgue mass, and increasing coordinates give the known single-crossing order.
A society is represented by its support: the list of its \(\tau\) ranking types with positive mass, each mass a binary rational; \(\tau\) is the support size, not \(m!\). In this elicitation model, this list is unknown and available only through the oracle.
The unknown map \(R:[0,1]\to\mathcal L(C)\) is piecewise constant and right-continuous on \([0,1)\), with \(R(1)\) equal to its left limit. For each distinct \(x,y\), the indicator that \(R(u)\) ranks \(x\) above \(y\) is monotone in \(u\), in either direction.
Every interior change point is a reduced rational \(p/q\) with \(\operatorname{bits}(p)+\operatorname{bits}(q)\le L\), where \(L\ge2\) is given. The change points and rankings are unknown.
A deterministic adaptive algorithm may query any rational \(u\in[0,1]\) and distinct \(x,y\in C\); the answer states whether \(R(u)\) ranks \(x\) above \(y\). Count distinct coordinate–unordered-candidate-pair queries, with repeats cached.
Recover the exact ordered interval rankings and rational boundaries, identifying maps that agree almost everywhere. State running times in \(m,\tau,L\) and the bit lengths of query coordinates.
What is the optimal worst-case number \(Q(m,L)\) of comparison queries needed to recover \(R\) almost everywhere, up to constant factors?
For \(n\) discrete voters with known single-crossing order and random access, the established lower bound is \(\Omega(m\log m+m\log n)\), with upper bound \(O(m^2\log n)\). [Dey–Misra](https://www.ijcai.org/Proceedings/16/Papers/039.pdf)
Later work claims the stronger discrete lower bound \(\Omega(m^2\log n)\). [Dey](https://arxiv.org/pdf/1611.04175) No result for precisely the bounded-rational continuous oracle model was located.
All logarithms below are base two. I interpret “binary rational” as a rational whose numerator and denominator are encoded in binary. I also give the answer when it means a dyadic rational.
Let \(\mathcal B_L\) be the set of admissible interior boundaries, and put \(n_L=|\mathcal B_L|+1\). For binary-encoded rationals,
\(\mathcal B_L=\{p/q:0<p<q,\ \gcd(p,q)=1,\ \operatorname{bits}(p)+\operatorname{bits}(q)\le L\}\).
The optimal worst-case query complexity is
\[ Q(m,L)=\Theta\!\left( m\log m+ mn_L\log(1+m/n_L)+ m^2\log(1+n_L/m) \right). \]
Equivalently, defining \(F(m,n)\) by
\[ F(m,n)= \begin{cases} m\log m+mn\log(1+m/n),&n\le m,\\ m\log m+m^2\log(1+n/m),&n\ge m, \end{cases} \]
we have \(Q(m,L)=\Theta(F(m,n_L))\).
For binary-encoded rationals, \(n_L=\Theta(L2^L)\). For dyadic rationals, \(n_L=\Theta(2^{L/2})\). Substituting either estimate in the formula preserves its constant-factor accuracy.
Consequently, \(Q(m,L)=\Theta(m^2L)\) when \(L\) is sufficiently large relative to \(\log m\), but this is not a uniform answer: for every fixed \(L\), the complexity is \(\Theta(m\log m)\).
The algorithms below use query coordinates of \(O(L)\) bits and can be implemented in time polynomial in \(m,\tau,L\).
Write the admissible boundaries as \(b_1<\cdots<b_N\), where \(N=|\mathcal B_L|\), and set \(b_0=0\), \(b_{N+1}=1\). There are \(n=N+1\) elementary cells.
Every permitted map is constant on each cell \([b_i,b_{i+1})\), with the final cell including \(1\). Right-continuity makes a query at \(b_i\) return that cell’s ranking. Thus the problem is exactly recovery of a single-crossing sequence of \(n\) rankings, allowing repetitions.
Conversely, every single-crossing sequence on these cells defines a permitted map. Its masses are differences of rational boundaries; in the dyadic interpretation, these differences are dyadic.
This reduction applies to lower bounds even when the algorithm queries arbitrary rational coordinates: every such coordinate belongs to a known elementary cell.
Let \(K=\binom m2\). Each pair changes orientation at most once. Every change of ranking changes at least one pair, so there are at most \(K\) changes. Moreover, a ranking cannot disappear and later reappear: if the rankings at two coordinates agree, monotonicity forces every pair to keep that orientation between them. Hence
\(\tau\le\min\{n,K+1\}\),
and the distinct positive-mass rankings occur in a uniquely ordered interval representation.
It remains to prove that the finite-domain complexity is \(\Theta(F(m,n))\).
Suppose a known ranking lists candidates as \(c_1,\ldots,c_m\), and the new ranking differs from it on \(d\) unordered pairs.
Insert \(c_1,\ldots,c_m\), in that order, into a list sorted according to the new ranking. Let \(d_i\) be the number of previously inserted candidates that \(c_i\) must pass. Then \(\sum_i d_i=d\).
Exponential search from the right end, followed by binary search, locates the insertion position using \(O(1+\log(1+d_i))\) comparisons. Concavity of the logarithm gives the total bound
\(O\!\left(m+m\log(1+d/m)\right)\).
Ordinary linear insertion instead uses \(O(m+d)\) comparisons.
These are comparison algorithms for an unknown strict order, so each comparison is an allowed oracle query.
Suppose \(n\le m\). Sort the first cell using \(O(m\log m)\) comparisons, then elicit successive cells using exponential insertion.
Let \(d_j\) count the pairs changing between cells \(j\) and \(j+1\). Single crossing gives \(\sum_jd_j\le K\). For \(n\ge2\), concavity therefore bounds the total cost by
\(O\!\left(m\log m+mn+m(n-1)\log\!\left(1+\frac{K}{m(n-1)}\right)\right)\).
Because \(K\le m^2/2\) and \(n\le m\), this is
\(O\!\left(m\log m+mn\log(1+m/n)\right)\).
For \(n=1\), only the initial sorting is needed.
Suppose \(n\ge m\). Choose at most \(m+1\) cell indices, including the first and last, so that successive selected indices differ by \(O(1+n/m)\).
Elicit their rankings in increasing order, using ordinary linear insertion after the first. Across these selected rankings, the total number of changed pairs is at most \(K\). Their total elicitation cost is therefore \(O(m\log m+m^2)\).
For each pair:
Thus the total cost is
\(O\!\left(m\log m+m^2\log(1+n/m)\right)\).
After finding all pairwise thresholds, their sorted distinct values are exactly the society’s boundaries. The ranking on every resulting interval follows from the known pair orientations.
This proves the upper bound \(O(F(m,n))\).
A deterministic algorithm making at most \(q\) distinct queries has at most \(2^q\) possible answer transcripts. Cached repetitions introduce no additional branching. Therefore a family of \(M\) pairwise different permitted maps requires at least \(\log M\) queries in the worst case.
Constant maps provide \(m!\) possible rankings. Hence every algorithm needs \(\Omega(\log(m!))=\Omega(m\log m)\) queries.
We first construct the lower bound for many cells, and also a bound of order \(mn\) when \(n\le m\).
For \(s\) candidates, start with their identity order. Perform \(s\) layers of adjacent swaps, alternating between position pairs
\((1,2),(3,4),\ldots\)
and
\((2,3),(4,5),\ldots\).
Swaps within a layer are disjoint.
After these \(s\) layers, the order is reversed. Indeed, a candidate initially at an odd position moves right, and one initially at an even position moves left. At an endpoint it pauses for one layer and then reverses direction. Counting its moves shows that a candidate initially at position \(j\) finishes at position \(s+1-j\).
The total number of swaps is \(\binom s2\): for \(s=2r\) it is \(r^2+r(r-1)\), and for \(s=2r+1\) it is \(r(r+1)+r^2\).
Reversal has \(\binom s2\) inversions. Every adjacent swap changes the inversion count by one, so every swap increases it. Consequently, every candidate pair crosses exactly once.
Assume \(N=n-1\ge4\), and set
\(s=\min\{m,\lfloor N/2\rfloor\}\), \(g=\lfloor m/s\rfloor\), and \(r=\lfloor N/s\rfloor\).
Partition \(gs\) candidates into \(g\) consecutive blocks of size \(s\), keeping the relative order of different blocks fixed. Run the reversal network independently inside each block.
Allocate \(r\) consecutive admissible boundaries to each layer. Each swap independently chooses one of its layer’s \(r\) boundaries as its crossing threshold. This produces a valid ranking sequence: swaps in one layer are disjoint and commute, and every earlier layer finishes before the next begins.
Different threshold choices produce maps differing on a positive-length interval. The family therefore has size
\(r^{\,g\binom s2}\).
Since \(g\ge m/(2s)\) and \(\binom s2\ge s^2/4\), its logarithm is at least \((ms/8)\log r\).
It follows that:
This proves the required lower bound throughout \(n\ge m\), and supplies \(\Omega(mn)\) when \(n\le m\).
For \(n\le m\), the preceding construction lacks the factor \(\log(1+m/n)\) when \(m/n\) is large. The following construction supplies it.
Assume \(n\ge12\) and \(m\ge4096n\). Put
\(T=\lfloor n/3\rfloor\), \(k=\lfloor\sqrt{m/(8T)}\rfloor\), and \(B=\lfloor m/k\rfloor\).
Use \(kB\) candidates labelled \((a,b)\), with \(0\le a<k\) and \(1\le b\le B\). Associate to each candidate the affine function
\(f_{a,b}(z)=b+az\).
Any unused candidates occupy fixed positions below these candidates.
For each integer \(t\in\{1,\ldots,T\}\), create three consecutive rankings:
Here \(\varepsilon=1/(2k)\). The first and third rankings have no ties: the difference of two scores is an integer plus or minus a nonzero fraction of absolute value less than one.
There are \(3T\le n\) rankings. Assign them to consecutive elementary cells and repeat the last ranking on any remaining cells.
For two candidates, the score difference is affine in \(z\).
If their slopes agree, their order is constant. Otherwise, their scores cross at most once. At a sampled integer crossing, the arbitrary order in the middle ranking chooses one of the two surrounding orientations. It therefore cannot create a second change.
Thus every constructed profile is single crossing.
At time \(t\), every integer score \(y\) satisfying
\(1+(k-1)t\le y\le B\)
has exactly \(k\) candidates in its tie class: one for each slope \(a\), with intercept \(b=y-at\).
From \(k^2\le m/(8T)\), we obtain \(B\ge2kT\). Consequently there are at least \(B/2\) such classes at every time \(t\).
Their orders can be chosen independently, giving at least
\((k!)^{TB/2}\)
different maps. Distinct choices differ on the cell assigned to the corresponding middle ranking, which has positive length.
For \(k\ge4\), \(\log(k!)\ge(k/4)\log k\). Also,
\(T\ge n/4\), \(kB\ge m/2\), and
\(\log k\ge\frac12\log(m/n)-3\ge\frac14\log(m/n)\).
Hence the logarithm of the family size is
\(\Omega(mn\log(m/n))=\Omega(mn\log(1+m/n))\).
This proves the missing lower bound.
When \(n\ge m\), Section 3.2 gives the required term \(m^2\log(1+n/m)\).
When \(12\le n\le m\):
When \(n<12\), the entire expression \(F(m,n)\) is \(O(m\log m)\), so the sorting lower bound suffices.
Taking the maximum of this bound and the sorting bound is, within a constant factor, their sum. Thus the lower bound is \(\Omega(F(m,n))\), completing the query-complexity proof.
The upper bound \(N=O(L2^L)\) follows by grouping numerator-denominator pairs by bit lengths \(a,b\). For fixed \(a+b\), there are at most \(L\) groups, each containing at most \(2^{a+b}\) pairs.
For completeness, the matching lower bound includes the coprimality restriction.
Take \(a+b=L\), with \(L/4\le a<L/2\), and write \(P=2^{a-1}\), \(H=2^{b-1}\). Consider
\(P\le p<2P\), \(H\le q<2H\).
Then \(p<q\), and there are \(PH\) pairs. The number with a common divisor is at most
\[ PH\sum_{d=2}^{\infty}d^{-2} +(P+H)\sum_{d=2}^{2P}d^{-1} +2P. \]
The first sum is at most \(3/4\). The remaining terms divided by \(PH\) tend uniformly to zero as \(P\) grows, because \(H\ge P\). Thus a fixed positive fraction of these pairs are coprime for sufficiently large \(L\).
There are \(\Theta(L)\) disjoint choices of \(a,b\), each contributing \(\Omega(2^L)\) reduced fractions. Therefore
\(N=\Theta(L2^L)\).
For \(L=2\), there are no interior boundaries; this finite exception does not affect the stated constant-factor estimate for \(n_L=N+1\).
If every mass is dyadic, every boundary, being a sum of masses, is dyadic. Conversely, any selection of dyadic boundaries gives dyadic masses.
A reduced interior dyadic boundary is \(p/2^k\), with \(p\) odd. Its denominator has \(k+1\) bits. Consequently,
\[ N=\sum_{k=1}^{L-2} 2^{\,\min\{k,L-k-1\}-1}. \]
The summands grow geometrically toward the middle and decrease geometrically afterward. Hence
\(n_L=N+1=\Theta(2^{L/2})\).
Enumerating the boundary universe can take exponential time in \(L\). We can nevertheless attain the optimal query bound in polynomial time by using two implementations.
Let \(B_0=L+\lceil\log(m+1)\rceil\).
When \(L<16\log(m+1)\), enumerate and sort \(\mathcal B_L\), then apply Section 2.
There are \(O(L2^L)\) numerator-denominator pairs to inspect. All queried coordinates are admissible boundaries or \(0\), so their numerator-plus-denominator lengths are at most \(L\), apart from an irrelevant constant for \(0\).
A conservative bit-operation bound is
\(O((L2^L+m^2+\tau m\log m)B_0^5)\).
Because this branch has \(2^L<(m+1)^{16}\), the bound is polynomial in \(m,\tau,L\).
When \(L\ge16\log(m+1)\), use pairwise dyadic bisection directly.
Sort the rankings at \(0\) and \(1\). A pair agreeing at both endpoints is constant. For a disagreeing pair, maintain a bracket \(a<t\le b\) for its crossing threshold and make \(2L+2\) midpoint queries.
Every admissible denominator is less than \(2^{L-1}\). Distinct admissible fractions therefore differ by more than \(2^{-2L+2}\). The final bracket has length \(2^{-2L-2}\), so it contains exactly one admissible threshold.
That threshold can be recovered in polynomial time by continued fractions. Explicitly, for the bracket midpoint \(v\),
\(|v-t|\le2^{-2L-3}<1/(2q^2)\),
where \(q\) is the threshold’s denominator. The classical continued-fraction criterion says that a reduced fraction satisfying this inequality is a convergent of \(v\). Compute its convergents and select the unique admissible one in \((a,b]\).
This implementation uses \(O(m\log m+m^2L)\) queries. Its query coordinates have numerator-plus-denominator length at most \(4L+5\).
Even the dyadic boundary universe satisfies
\(n_L\ge2^{\lfloor(L-1)/2\rfloor}\). In this branch, therefore,
\(\log(n_L/m)=\Omega(L)\), while \(\log n_L=O(L)\). The proved optimum is consequently \(\Theta(m^2L)\), so bisection attains it within a constant factor.
A conservative bit-operation bound is
\(O((m^2+\tau m\log m)B_0^5)\).
In either implementation, reconstructing the output requires no further oracle queries. Sorting candidates by the recovered pair orientations on each interval takes \(O(\tau m\log m)\) known comparisons. Boundary differences have \(O(L)\)-bit rational representations.
The pairwise-search upper bound and sorting-based lower bound agree with the established results of [Dey–Misra](https://www.ijcai.org/Proceedings/16/Papers/039.pdf).
The proof of Theorem 5 in [Dey’s later paper](https://arxiv.org/pdf/1611.04175) does not establish its stated bound as written. With a fixed single-crossing voter order, copies of \(\ell\) fixed ranking types must occupy consecutive blocks. If each type appears, the number of profiles is \(\binom{n-1}{\ell-1}\), rather than \(\ell^n\).
The formula proved here also shows why the parameter range matters. At \(n=m\), the optimal discrete complexity is \(\Theta(m^2)\), so a uniform lower bound \(\Omega(m^2\log n)\) cannot hold. When \(n\ge m^2\), our bound becomes \(\Theta(m^2\log n)\), validating that order of growth in the large-voter regime.
⟨structured verdict parsed — rendered above⟩
The prover’s claimed result is proved. The finite-domain bounds, boundary counts, and polynomial-time implementation withstand verification. I found no substantive gap or false statement requiring correction.
The interpretation of “binary rational” as a rational encoded by binary numerator and denominator is explicit. The prover also handles the alternative dyadic interpretation, so this ambiguity does not undermine the answer.
The reduction in Section 1 is valid:
The support bound \(\tau\le\min\{n,\binom m2+1\}\) is correct. Every genuine ranking change reverses at least one pair, and no pair can reverse twice. The argument excluding a ranking’s disappearance and subsequent reappearance also follows directly from pairwise monotonicity.
Thus the reduction preserves both exact recovery almost everywhere and the relevant query lower bounds.
The displayed three-term formula and the piecewise definition of \(F(m,n)\) agree within absolute constant factors.
For \(n\le m\), the omitted term \(m^2\log(1+n/m)\) is of order \(mn\), which is absorbed by \(mn\log(1+m/n)\). For \(n\ge m\), the omitted term \(mn\log(1+m/n)\) is of order \(m^2\), which is absorbed by \(m^2\log(1+n/m)\).
There is no inconsistency between the two formulations.
Section 2.1 correctly identifies \(d_i\) as the number of inversions involving the newly inserted candidate and previously inserted candidates. Therefore \(\sum_i d_i=d\).
The stated insertion costs are valid:
Summation and logarithmic concavity give the claimed bounds. Every comparison is an allowed query about the new coordinate’s strict ranking.
For \(n\le m\), the successive inversion distances satisfy \(\sum_jd_j\le\binom m2\). The concavity calculation and absorption of the \(mn\) term are valid. The separate \(n=1\) case is correctly handled by sorting alone.
For \(n\ge m\), the selected cells can have gaps of \(O(1+n/m)\). Across their rankings, ordinary insertion incurs at most \(\binom m2\) inversion changes in total, plus \(O(m^2)\) insertion overhead.
For every pair:
Every actual ranking boundary reverses a pair, so the distinct recovered pair thresholds are exactly the output boundaries. Reconstruction from the recovered orientations requires no additional oracle queries.
The upper bound \(O(F(m,n))\) is established.
The binary decision-tree argument remains valid when only distinct queries are counted. A repeated query has a predetermined cached answer and supplies no additional branching.
Constant maps supply \(m!\) distinct valid outputs, giving the stated \(\Omega(m\log m)\) lower bound.
Both arguments apply to the requested almost-everywhere recovery criterion.
The reversal network in Section 3.2 is valid. Alternating the two disjoint adjacent-swap layers for \(s\) layers reverses the order. The stated swap counts equal \(\binom s2\) for both even and odd \(s\).
Since reversal has exactly that many inversions and each adjacent swap changes the inversion count by one, every swap must increase it. Consequently, each candidate pair crosses exactly once.
The independent-threshold construction also works:
The family size \(r^{g\binom s2}\), the estimates on \(g\) and \(\binom s2\), and the resulting lower bounds are correct in the stated range \(N\ge4\).
The remaining bounded-size cases are covered by the sorting bound and Section 3.4’s treatment of \(n<12\).
Section 3.3 supplies the additional logarithmic factor correctly.
Under its assumptions, \(k\ge4\), so the sampled coordinates \(t-\varepsilon,t,t+\varepsilon\) occur in increasing order across consecutive integers. At the outer samples, equal slopes give distinct intercepts, while unequal slopes give a nonzero fractional perturbation of absolute value less than one. Hence those rankings have no ties.
Each pair’s affine score difference has at most one zero. Arbitrary ordering within an integer-time tie class selects one of the two surrounding pair orientations, so it cannot introduce a second reversal. Arbitrary tie-class permutations still define strict rankings.
The counting steps are valid:
The inequalities involving \(T\), \(kB\), \(\log(k!)\), and \(\log k\) hold under \(n\ge12\) and \(m\ge4096n\). They establish the claimed \(\Omega(mn\log(1+m/n))\) lower bound.
Section 3.4 correctly combines the parameter ranges. Taking the maximum of the sorting and construction lower bounds yields their sum within a constant factor.
For binary-encoded rationals, the upper bound obtained by grouping numerator and denominator bit lengths is correct.
The coprimality argument also checks out. Its common-divisor count is a valid union bound. The reciprocal-square sum is at most \(3/4\), and the remaining error terms are uniformly negligible in the chosen bit-length range. The rectangles have \(p<q\), are disjoint across bit-length choices, and each contains a constant fraction of reduced pairs for sufficiently large \(L\).
This establishes \(N=\Theta(L2^L)\) asymptotically. Using \(n_L=N+1\) correctly handles the absence of interior boundaries at \(L=2\) and the other finitely many small values.
For dyadic rationals, the summation counts precisely the admissible odd numerators for each denominator \(2^k\). Its geometric growth and decay establish \(n_L=\Theta(2^{L/2})\).
The two implementation branches establish the requested running-time claim.
In the smaller-\(L\) branch, exhaustive enumeration is polynomial in \(m\) because \(2^L<(m+1)^{16}\). Enumeration, sorting, elicitation, threshold processing, and output reconstruction fit within the stated conservative bit-operation bound.
In the larger-\(L\) branch:
The continued-fraction theorem is stated sufficiently precisely for this application: the threshold is reduced, its denominator is positive, and the required strict approximation inequality holds. Selecting the unique admissible convergent inside the bracket therefore recovers the threshold.
The query-coordinate bound \(4L+5\) is correct. Boundary differences have \(O(L)\)-bit representations. The large-\(L\) branch also justifies \(\log(n_L/m)=\Omega(L)\) for both interpretations, so its \(O(m\log m+m^2L)\) query cost matches the proved optimum.
The stated polynomial bit-operation bounds are conservative but valid.
The description of the established random-access bounds agrees with [Dey–Misra](https://www.ijcai.org/Proceedings/16/Papers/039.pdf).
The criticism of the later counting argument is accurate. The proof of Theorem 5 in [Dey’s paper](https://arxiv.org/pdf/1611.04175) counts unrestricted assignments of fixed ranking types rather than profiles respecting the fixed single-crossing voter order. When all fixed types occur, their consecutive positive block sizes give the binomial count stated by the prover, provided \(n\ge\ell\); for \(n<\ell\), that family is empty.
The consequences at \(n=m\) and \(n\ge m^2\) follow from the proved finite-domain formula. This literature discussion is consistent with, and unnecessary to the validity of, the independent proof.
No repair or additional clarification is needed to establish the requested result.
⟨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.