d4-conf-ijcai-2019-1030

The paper has no named complexity classification such as a theorem that a problem is in P or NP-hard. It does, however, give explicit rules and an algorithm with named guarantees, and it reports no competing hardness result. My strongest mirror is its parameter-update rule, Theorem 4; Theorem 3 gives a separate, plausible ordinal-election mirror.

For Theorem 4, proved in this paper, the anchor is: *“The Suppress Outer-\(\sigma\) Parameter Update Rule is resilient up to \(\sigma < \nicefrac{1}{3}\) sybil penetration.”* In full, the rule trims the top \(\sigma\)-fraction of ideal points and takes the reality-aware median \(v^{-\sigma}\) of what remains; it also trims the bottom \(\sigma\)-fraction and takes the median \(v_{-\sigma}\). Given the reality-aware median \(v^*\) of the full electorate and current value \(r\), it moves to \(v^{-\sigma}\) if \(r < v^{-\sigma} \le v^*\), moves to \(v_{-\sigma}\) if \(v^* \le v_{-\sigma} < r\), and otherwise stays at \(r\). The theorem says this rule is sybil-safe relative to the reality-aware median base rule and satisfies sybil-liveness below the one-third penetration threshold.

My lead question is Continuous Outer-\(\sigma\) Parameter Update. An instance consists of a current parameter value \(r\), a rational \(\sigma < 1/3\), and a finite support of ideal points \(x_i\) with positive rational masses \(\mu_i\) summing to one. The society is the probability distribution \(\mu=\sum_i\mu_i\delta_{x_i}\); it may represent a very large population, with many people sharing each ideal point. The input also has a hidden decomposition into genuine and sybil mass, with sybil mass \(\sigma\). The task is to output the exact updated value under the rule above. For a mass distribution, define its median set as the values with at least half the mass weakly on either side, and choose the point in that set closest to \(r\). To trim a tail, remove exactly \(\sigma\) mass from that end, splitting the mass at a boundary point if needed. These conventions extend the paper’s reality-aware median and fractional trimming directly.

The expected classification is tractable: sort the \(\tau\) supported ideal points, accumulate rational masses, and locate the full and trimmed median sets. This takes polynomial time in \(\tau\) and the input bit length \(L\). The associated guarantee to prove is that, for every hidden decomposition with sybil mass \(\sigma\), the output lies between \(r\) and the reality-aware median of the genuine population, and that unanimous genuine support for any value \(q\ne r\) can move the parameter to \(q\) when \(\sigma<1/3\). The paper’s proof already points toward the mass argument: after trimming, genuine mass still forms a majority when the sybil fraction is below one third.

A credible regime is a large online community setting a public parameter in fixed increments—say, a fee or rate in basis points. Millions of participants may share ideal values on a finite grid, so the number of agents can greatly exceed the number of types. An ideal point completely determines a voter’s preference in this single-peaked model. This is a plausible high-multiplicity scenario, though less compelling if participants can report arbitrary, mostly unique real values. A useful follow-up is to ask what input representation permits the same problem when the ideal-point distribution is given by a density or quantile oracle rather than a finite support list.

For Theorem 3, also proved here, the anchor is: *“Algorithm 1 satisfies the Conservative Reality-Aware \(\delta\)-Supermajority Condorcet criterion.”* The algorithm first keeps alternatives that beat reality \(r\) by the specified supermajority; if there are none, it elects \(r\). Otherwise it runs an amendment agenda from \(r\) on those alternatives, then checks whether the agenda winner beats every remaining viable alternative by a \(\delta\)-supermajority. It elects that winner if so, and elects \(r\) otherwise. The theorem says this realizes the conservative criterion: elect a \(\delta\)-supermajority Condorcet winner among the reality-viable alternatives if one exists, and elect \(r\) if none exists.

The corresponding Continuous Conservative Amendment Agenda takes a finite set \(A\) of alternatives with status quo \(r\), a rational \(\delta\), and a distribution over \(\tau\) complete rankings with rational masses. It asks for the alternative returned by Algorithm 1, treating a challenger as winning a pairwise vote only when its mass exceeds \(1/2+\delta\). With \(\delta=\sigma/2\), this is the paper’s sybil-resilient setting. The expected classification is again tractable: compute the weighted viability and pairwise tallies over the supported rankings, then execute the agenda and its final checks. This takes polynomial time in the number \(m\) of alternatives, \(\tau\), and \(L\). Its natural regime is a large membership voting on a fixed agenda, where repeated complete rankings are common. A further question is how the guarantees change with different tie conventions, which matter more when exact fractional masses make ties common.

The ordinal result is a good second anchor because it is an actual algorithmic realization over a population of ranking types. The parameter-update result is stronger: the population interpretation turns the rule directly into a weighted quantile problem, and the one-third threshold has a natural mass-based proof. Neither mirror should be sold as dissolving known discrete hardness. The paper’s contribution is rule design and sybil-resilience, not a complexity separation between discrete and continuous versions.

My weakest point is therefore also clear: both proposed computation problems look easy because they are weighted tallying and quantile-finding. They illustrate that the authors’ questions admit a sensible continuous-population formulation, but they do not deliver the programme’s more ambitious prize of showing whether discrete hardness disappears under continuization. The case survives as a concrete, author-recognizable mirror of two named results, especially Theorem 4, while remaining modest about its computational significance.