| paper | d4-conf-ijcai-2016-0065 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
other→P discrete result → its continuous mirror
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})\). · discrete side: other · adjudication: proved
full proof & adversarial review →
Theorem 1
statement extracted from the paper’s text layer
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?
The hidden society is a piecewise-constant map \(R\) from cumulative mass \(u\in[0,1]\) to ranking types, with rational interval boundaries of at most \(L\) bits and the single-crossing order known. A query chooses \(u\) and two candidates and returns their ordering at \(u\); the goal is exact recovery almost everywhere, equivalently the ordered ranking types and their masses.
The society is hidden behind queries at exact mass coordinates rather than given as an explicit list of ranking types and masses, so the mirror studies oracle learning instead of computation on the programme’s usual supplied-mass input.
fatal: False
The mirror covers Theorem 1’s known-order, random-access exact-elicitation lower-bound setting; it leaves the other access and ordering settings, nearly single-crossing results, and the remaining query bounds aside.
The strongest mirror is the paper’s known-order, random-access setting. Theorem 1 proves here that if a profile is single crossing with respect to a known voter order, then any algorithm that exactly elicits it using random access needs \(\Omega(m\log m+m\log n)\) comparison queries. The \(\Omega(m\log m)\) term comes from recovering even one ranking; the \(\Omega(m\log n)\) term comes from locating where candidate pairs cross along the voter order. This is a query-complexity lower bound, rather than a conventional NP-hardness result.
A natural regime is a large population whose rankings over a small set of options change monotonically along a known social or market coordinate. Many people may share each ranking, while the number of distinct ranking types stays small: in a single-crossing profile it is at most \(\binom{m}{2}\), as Lemma 3 proves. This fits settings such as a large survey ordered by a known ideological index. Each type is a complete ranking; its mass is the fraction of the population with that ranking.
I would ask a prover to study Continuous Known-Order Preference Elicitation. The input is a candidate set \(C\), \(|C|=m\), and an unknown ranking function \(R:[0,1]\to L(C)\). The coordinate \(u\) is cumulative population mass, and \(R\) is single crossing along that coordinate: for every pair \(x,y\), the set of \(u\) where \(x\succ_{R(u)}y\) is an interval. The change points are rational, with numerator and denominator encoded using at most \(L\) bits. The order of the mass coordinate is known. A query chooses \(u\) and a pair \(x,y\), and returns how the voter at \(u\) ranks them. The task is to recover \(R\) almost everywhere—equivalently, the ordered ranking segments and their masses \(\mu_r=\lambda(\{u:R(u)=r\})\)—using as few queries as possible.
I expect this problem to be tractable in \(m\) and \(L\). Each pair’s transition can be located to its exact rational coordinate with \(O(L)\) comparison queries, so checking all pairs gives an \(O(m^2L)\) upper bound. The discrete \(\log n\) term in Theorem 1 has a direct interpretation here: when the population masses lie on a grid with denominator \(n\), locating a transition takes \(O(\log n)\) queries, just as locating its rational coordinate takes a number of queries tied to its bit length. The continuous question is to characterize the optimal dependence on \(m\) and \(L\), including lower bounds.
This should still look like preference elicitation to the authors: the goal is exact recovery of the preference profile, and the query still asks a voter to compare two candidates. The change is that the voter’s index is cumulative mass \(u\), rather than an integer label. The mirror covers Theorem 1’s known-order random-access case only; it does not claim to continuize the paper’s sequential-access or unknown-order results.
The weakest point is the oracle: asking for a comparison at an exact mass coordinate is an idealized continuous counterpart to querying a named voter. Exact recovery also needs a bound on the bit length of transition masses; with arbitrary real transitions, no finite number of point queries can guarantee exact reconstruction. Those are real modeling choices, but they make the mirror precise rather than changing its elicitation objective.
Theorem 1 is a genuine computational anchor: it gives a query-complexity lower bound for exact preference elicitation, with separate costs for learning a ranking and locating pairwise crossings. The continuous model in the proponent’s case is also a serious attempt to preserve that task, not a straw man. [The paper](https://arxiv.org/abs/1604.05194) studies precisely this oracle setting.
The difficulty is that the programme’s society is given as masses of complete voter types, and a type here is a ranking. With that input, the profile to be elicited is already known. To keep elicitation nontrivial, the proposed mirror hides the society and gives the learner a point-query oracle at any \(u\in[0,1]\). That oracle retains an address for every point on an ordered population axis. It is mathematically coherent, and the interval of each ranking type can have positive mass, but it asks a different access question from computing over a supplied mass distribution.
A sample-access repair illustrates the gap. Exact recovery of a hidden distribution can require exponentially many samples in the mass bit length: a type of mass \(2^{-L}\) may go unseen for exponentially many draws. Approximate distribution learning is a plausible research problem, but it changes the paper’s exact recovery objective. Direct queries at arbitrary \(u\) avoid that obstacle by exposing the ordered coordinate and its change points; queries for exact interval masses would introduce yet another oracle.
So the strongest case against the mirror is about fit, not validity. Its tractability comes from learning a finite collection of ordered thresholds to \(L\)-bit precision. That is a clean continuous query-learning problem, but it does not study computation over an explicitly represented high-multiplicity society, the setting ChoCo is built to analyze. I would treat it as a separate elicitation project rather than a strong ChoCo anchor.
That case is weak against the universal claim in the prompt. A continuum of ordered agents with a known single-crossing axis is a plausible scenario, and the point-query model preserves the paper’s task unusually well. I cannot honestly rule out every worthwhile mirror here; I can only argue that the best one sits at the edge of the programme’s intended scope.
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.