| paper | d4-conf-wine-2012-0011 |
| 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: Polynomial-time solvable: a certified additive-\(\eta\) approximation is computable, and \(s_\epsilon\) is always finite under the stated strict median hypothesis. · discrete side: other · adjudication: proved_with_minor_gaps
full proof & adversarial review →
Corollary 1
Given an ordered finite support of \(\tau\) single-peaked types with rational masses \(\mu_i\) and a unique median type \(r\), determine the least interaction time \(s\) at which the triadic mass process places at least \(1-\epsilon\) of its mass on \(r\), and provide a certified bound on that time. The process starts at \(\nu(0)=\mu\); at each infinitesimal interaction, three types are drawn independently from \(\nu\), and their mass is relabeled to the median type. Establish how this accuracy guarantee relates to the finite-population process as population size grows.
Use the mass state \(\nu(s)\) over ordered voter-proposal types, with \(\dot{\nu}_j=3(q_j(\nu)-\nu_j)\), where \(q_j(\nu)\) is the probability that the median of three independent draws has type \(j\). The input is \(\mu\); the output is a certified interaction horizon for reaching the requested mass on the median type. There is no separate intervention objective.
The full mass vector already identifies the median, so the proposed accuracy calculation studies the flow's convergence rather than the finite protocol's sampling accuracy or profile-blind communication burden.
fatal: False
The mirror covers the single-peaked outcome accuracy result and can also describe the exact winner-law limit and thresholded comparison exposure. It leaves the quasi-truthful Nash theorem, higher-dimensional simulations, and the Hot-or-Not comparison outside its scope.
The strongest positive case is a high-multiplicity limit of the paper’s single-peaked Triadic Consensus process. There is a natural regime for it: a large public consultation over a fixed slate of budget packages or policy proposals. Many residents submit the same package and share the same distance-based ranking of the slate. The number of residents \(N\) can be very large while the number of distinct complete types \(\tau\)—package and preference pairs—is modest. Mass \(\mu_i\) means the fraction of residents of type \(i\), and each type includes everything the model uses about those residents. This is a plausible version of the paper’s crowdsourcing motivation, though it is less faithful to its image of unique, individually authored proposals.
The paper has no named result classifying a problem as NP-hard, in P, or FPT. Its relevant anchors are randomized outcome and communication guarantees. The numbered arXiv version gives the anchors below; the pasted text omits those numbers. ([Goel and Lee, *Triadic Consensus*](https://arxiv.org/html/1210.0664v1))
My lead is Theorem 3.3, proved in this paper. It states that for \(n\) single-peaked participants ordered from one end of the axis to the other, using quasi-truthful votes and \(k=1\), the probability that Triadic Consensus returns participant \(i\) is
\[
\Pr[w=i]=\left(\frac12\right)^{n-1}\binom{n-1}{i-1}.
\]
The proof uses the paper’s urn reduction and an absorption-probability theorem derived from Lee and Bruck. This exact law is the cleanest bridge from individually named participants to an aggregate population.
The corresponding question is High-Multiplicity Triadic Consensus: winner limit. Its instance is a finite ordered slate \(C=\{c_1,\ldots,c_\tau\}\) and rational masses \(\mu_i>0\) summing to \(1\). Type \(i\) consists of residents who submit \(c_i\) and share the same distance-based ranking of the slate. Assume a unique median type \(r\), so the mass strictly to either side of \(c_r\) is less than \(1/2\). Start with mass distribution \(\nu(0)=\mu\). At each interaction, sample three labels independently from the current mass distribution; under the paper’s single-peaked, quasi-truthful rule, their median label wins, and the three sampled infinitesimal portions are relabeled with it. With interaction time normalized per unit population mass, write
\[
\dot{\nu}_j(s)=3\bigl(q_j(\nu(s))-\nu_j(s)\bigr),
\]
where \(q_j(\nu)\) is the probability that the median of three independent draws from \(\nu\) has label \(j\). The question is to compute the terminal recommendation distribution \(\lim_{s\to\infty}\nu(s)\), and establish when it agrees with the limit of the finite-population winner law. The solution sought is the limiting distribution and a proof of convergence.
For a cut \(i\), let \(F_i(s)=\sum_{j\le i}\nu_j(s)\). A median of three draws is on the left of that cut exactly when at least two draws are, giving
\[
\dot F_i=3F_i(1-F_i)(2F_i-1).
\]
With a unique median, each cut below it moves toward \(0\), and each cut at or above it moves toward \(1\). Thus the mass converges to \(\delta_r\). This is a tractable limit question: the output is the median type, and the cut dynamics certify the result. It is a result about the fate of the triadic process, not just a recommendation to compute a median directly.
Two other anchors sharpen the case. Corollary 1, proved here using standard probabilistic arguments, states that for \(n\) single-peaked participants, if \(k=O(\epsilon^{-2}\log(1/\delta))\), then quasi-truthful Triadic Consensus returns a \((1-\epsilon/\sqrt n)\)-approximation of the Condorcet winner with probability at least \(1-\delta\). Theorem 3.4, also proved here, states that for single-peaked preferences and quasi-truthful voting, the total communication complexity is \(O(kn\log^2(kn))\). The latter proof draws on an urn running-time bound derived from Lee and Bruck. Neither is a hardness result.
For Corollary 1, the continuous question is Mass Accuracy for Triadic Consensus: given the rational finite-support society above and a rational tolerance \(\epsilon>0\), determine whether the mass-flow process reaches a state with at least \(1-\epsilon\) of its mass on the unique Condorcet type, and return a certified interaction horizon that achieves this. In the unique-median regime the flow converges to that type, so every positive tolerance is eventually reached. This is the continuum analogue of the paper’s accuracy guarantee, but it replaces finite-population success probability with deterministic mass concentration; it does not claim to preserve the corollary’s exact approximation convention or its \(\delta\) dependence.
For Theorem 3.4, the companion question is Mass Communication Cost: on the same instance, find the least normalized comparison exposure needed to put at least \(1-\epsilon\) of the mass on the median type. A triad uses three comparisons, so a horizon \(s\) corresponds to \(3s\) comparisons per unit population mass under this normalization. The scalar cut equations make this a plausible tractable problem, with the cost depending on the tolerance and the society’s distance from a tied median. It asks about the communication burden of the same rule, rather than simply relabeling its output.
Together, these mirrors cover the paper’s single-peaked, quasi-truthful outcome and communication results. They do not stretch to the two-dimensional simulations, the Hot-or-Not comparison, or the quasi-truthful Nash-equilibrium theorem. The paper’s Theorem 3.6 already analyzes a one-step continuous distribution of voters, deriving \(g_{\text{Triadic}}(x)=6x(1-x)\) for a uniform population on \([0,1]\). That is useful evidence that the authors would recognize continuous population mass as meaningful, but it is not the proposed mirror: the mirror asks about the full multi-round process and its high-multiplicity outcome and communication cost.
The soft spot is that the limit changes what counts as an outcome. The finite algorithm eventually selects one named participant; the mass process converges to a type, and generally reaches exact concentration only asymptotically. The limit also removes the finite-population randomness that gives \(k\), \(\delta\), and the binomial winner law much of their force. So this is a credible mirror of the protocol’s aggregate behavior, but it does not yet recover its finite-\(n\) guarantees. The natural next questions are whether one can quantify finite-population corrections to the mass flow, handle societies with no unique median, and extend the analysis beyond single-peaked profiles.
The high-multiplicity setting is plausible: a large consultation over a fixed slate could have many residents with the same proposal and preferences. I would not reject it on the ground that the paper’s participants are individuals. Nor does the paper’s one-step continuous-density calculation already answer a multi-round question. The problem with the three proposed mirrors is narrower: they turn results about a finite randomized protocol into mean-field analyses, rather than into the kind of computational problem ChoCo is trying to chart.
For Theorem 3.3, the proposed flow is a credible limit model. But its terminal question is analytic: follow the mass dynamics and show they concentrate on the median type. With the stated cut equation, that is an ODE calculation. The finite theorem’s output is instead a distribution over named participants. If a type occupies a block of participant ranks, its finite-\(N\) probability is the sum of the binomial probabilities across that block; with a positive-mass unique median type, that sum concentrates on the type as \(N\) grows. This is useful evidence for a discrete-to-continuous dictionary, but the mirror as posed does not ask for an algorithmic or complexity result about the society. A more demanding version could seek finite-\(N\) corrections to the flow, but that keeps the finite population and its sampling fluctuations as the object of analysis.
Corollary 1 has the same scale problem. Its guarantee concerns finite-sample accuracy and confidence. In a fixed finite type space, normalized rank error vanishes and the positive-mass median type captures the limit; the confidence parameter \(\delta\) and the theorem’s finite-\(n\) approximation scale disappear. On a continuous, atomless proposal space, exact concentration on a single median proposal is itself the wrong target: one would need to ask about a neighborhood instead. Either repair changes the accuracy question. The natural finite-population repair is a probabilistic limit analysis, not a continuous computational problem over type masses.
Theorem 3.4 is the strongest anchor because communication complexity is a computational resource, and it would be a mistake to say the paper has no computational result. But the proposed \(3s\) comparisons per unit mass measure exposure in the fluid process. Exact absorption takes infinite time there; stopping at \(1-\epsilon\) mass concentration substitutes a new stopping criterion for the finite protocol’s selection of one participant. Also, the protocol’s point is to find a winner through comparisons without knowing the population profile. If the continuous input supplies the full masses, the profile already reveals the median; if it does not, the mirror needs an additional sampling or oracle model. That could be studied, but it is not supplied by the proposed mass-flow question.
There is a more substantive possible extension: ask how much mass must change its reports or preferences to alter the protocol’s eventual winner or its probability of selecting a target. That could become a continuous robustness or campaign problem. But it requires a new intervention model and costs; it does not mirror the communication theorem or the paper’s unilateral quasi-truthful Nash result. In the ordinary nonatomic limit, one individual’s deviation has zero mass effect, while a positive-mass coalition changes the problem from individual incentives to collective intervention.
So the negative case is strongest against the *specific three mirrors*: they capture valid population limits, but their central deliverables are analytic behavior of a protocol, not ChoCo’s computational landscape. It is not airtight as a universal exclusion. The communication-complexity result and the paper’s interest in manipulation leave room for a carefully specified mass-level robustness problem that the authors might recognize.
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.