| paper | d4-conf-ijcai-2015-0153 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
Answer: \(V(\alpha)=1-h_2(\min\{\alpha,1/2\})\). For \(0<\alpha\leq1/2\), asymptotic optimality is equivalent to \(\mathbb E T_N=o(N)\). For \(1/2<\alpha\leq1\), it is equivalent to \(N-H(E^N)=o(N)\) and \(I(E^N;R^N)=o(N)\). At \(\alpha=0\), the unique admissible family is optimal. · discrete side: other · adjudication: proved
full proof & adversarial review →
Theorem 5
statement extracted from the paper’s text layer
For α∈[0,1], let \(k_N=\lfloor α N\rfloor\). Draw \(N\) binary opinions independently and uniformly, choose a hidden coalition of \(k_N\) advisors uniformly, and let non-colluders report truthfully. Over all joint stochastic reporting kernels \(Q_N(r_{K_N}\mid o_{K_N})\) for the coalition, determine whether \(V(α)=\lim_{N→\infty}N^{-1}\min_{Q_N} I(O^N;R^N)\) exists, its value, and an asymptotically optimal family of kernels.
A large advisor population with type masses for honesty status and binary opinion, a hidden coalition of mass \(α\), and arbitrary joint reporting kernels that retain correlations among individual reports. Minimize mutual information between the full opinion and rating vectors, normalized per advisor, as the population grows.
A fixed type-mass vector does not encode the correlations among individual opinions and reports on which the paper’s leakage measure depends.
fatal: False
The mirror covers Theorem 5’s strongest arbitrary-collusion result and asks about the limiting coordination gap suggested by Theorem 6; it leaves the leakage calculations for literature attacks and the trust-system design proposal aside.
There is a credible continuous mirror here, but it is a mirror of the paper’s attack-optimization problem, not of a complexity classification. The paper states no named result saying a problem is in \(P\), NP-hard, or in another complexity class. Its closest anchors are Theorem 5 and Theorem 6, both proved in this paper. They are information-theoretic optimization results, not complexity results; that limits how much of the ChoCo programme this paper can support.
Theorem 5 is the strongest anchor. For \(m\) advisors and a uniformly unknown coalition of \(k\) attackers, with fair binary opinions and honest advisors reporting truthfully, it bounds the information leakage of any type-IV attack—the class allowing arbitrary coordinated strategies. The proof gives the lower bound
\[
m-\log_2\!\left(\sum_{i=0}^{k}\binom{m}{i}\right)
\]
bits, with leakage at most \(m\) bits. The lower bound is attainable: the proof constructs a strategy making the posterior over opinion vectors uniform within the Hamming ball of radius \(k\) around the ratings. This result is proved here, not cited.
A natural scenario is a large online marketplace where many advisors rate the same target. Suppose each advisor has a binary underlying opinion, and a stable fraction \(\alpha\) belong to a colluding group. Advisors sharing the same honesty status and opinion are the same type, so \(T=\{(\mathrm{honest},0),(\mathrm{honest},1),(\mathrm{colluder},0),(\mathrm{colluder},1)\}\), with masses \((1-\alpha)/2,(1-\alpha)/2,\alpha/2,\alpha/2\). The number of advisors \(N\) is large while the number of types is four. A shared coalition strategy is plausible for a coordinated group of Sybil accounts or organized sellers.
My lead mirror is the Asymptotic Strongest-CUR Rate problem. Its instance is \(\alpha\in[0,1]\). For each \(N\), take \(k_N/N\to\alpha\), draw the \(N\) opinions independently and fairly, and choose the \(k_N\)-advisor coalition uniformly at random, hidden from the user. Honest advisors report truth. The action is an arbitrary joint stochastic kernel \(Q_N(r_{K_N}\mid o_{K_N})\) for the coalition’s ratings, preserving the paper’s allowance for coordination; the user sees the full rating vector. The objective is to minimize the limiting information leakage per advisor:
\[
V(\alpha)=\lim_{N\to\infty}\frac{1}{N}
\min_{Q_N} I(O^N;R^N).
\]
A solution supplies the value and an asymptotically optimal family of kernels. The question should also establish that the limit exists.
The expected answer is tractable by the same Hamming-ball argument. With \(h_2\) denoting binary entropy,
\[
V(\alpha)=
\begin{cases}
1-h_2(\alpha),&0\le\alpha\le \tfrac12,\\
0,&\tfrac12\le\alpha\le1.
\end{cases}
\]
The ball’s logarithmic size grows as \(N h_2(\alpha)\) below half the population and as \(N\) at or above half. This is a Class A style outcome in the broad sense of an analytically tractable optimization problem, though it is not an algorithmic complexity result from the paper. The authors should recognize it as their strongest-attack question with population size scaled to infinity and leakage reported per capita.
Theorem 6 gives a second, distinct anchor. For \(1<k<m\), it proves that there are type-IV attacks with strictly less information leakage than *every* attack in types I, II, and III: respectively, independent truth-or-lie behavior, uniform ballot-stuffing or bad-mouthing, and a coalition that jointly chooses truth or lies. This theorem is also proved here.
Its continuous mirror is the Asymptotic Coordination Gap problem. For each \(\alpha\), compute the minimum leakage rates \(V_I,V_{II},V_{III},V_{IV}\) under those same four strategy classes, and determine
\[
\Delta(\alpha)=\min\{V_I(\alpha),V_{II}(\alpha),V_{III}(\alpha)\}-V_{IV}(\alpha).
\]
The finite theorem’s strict separation need not survive normalization by population size. In fact, the likely answer is \(\Delta(\alpha)=0\): type I alone can match the type-IV rate. Below \(\alpha=\tfrac12\), let colluders always lie, so the error set is the uniformly chosen coalition. At or above \(\tfrac12\), randomize their lies so the error set has asymptotic density \(\tfrac12\). In both cases the error-pattern entropy reaches the optimal rate. Thus the finite coordination advantage may be real but sublinear. This is an informative “where does the gap go?” question, not a claim that Theorem 6 is overturned. A natural follow-up is to determine the finite-size gap’s order.
These mirrors cover the strongest arbitrary-collusion result and its comparison with three restricted attack families. They do not cover the paper’s measurements of particular literature attacks or its design proposal for robust trust evaluation.
The main weakness is that a type-mass vector alone does not retain the paper’s central feature: correlations among the coalition’s individual reports. The mirror must preserve those through the joint kernels \(Q_N\), and its entropy objective must retain the random microstate around the limiting masses. If one replaces the kernel with independent type-level mass transfers, one changes the problem. This makes the mirror less like a finite-dimensional LP and more like a high-multiplicity entropy-rate problem. It is still a sensible population continuization, but the paper supplies no discrete hardness result whose dissolution or transfer would make it a direct complexity-landscape contribution.
The strongest objection is not that advisors cannot occur in large homogeneous populations. Millions of advisors using the same rating protocol is a plausible regime. The problem is that Theorems 5 and 6 measure information about the whole vector of advisors’ opinions. A continuous society described by masses of finitely many types does not retain that object.
In the proposed four-type mirror, the mass vector records proportions of honest and colluding advisors with each opinion. But in the paper, opinions are random across named advisors, and the coalition is a hidden random subset. The user learns from which ratings appear at which advisor positions. As \(N\) grows, the empirical type frequencies converge to their expected masses; those frequencies contain only \(O(\log N)\) bits of information. Theorem 5’s leakage can be proportional to \(N\). Thus a fixed type-mass vector cannot preserve the quantity being optimized. Making identity part of the type retains the vector, but requires a growing number of types and gives up the finite-support high-multiplicity model.
A richer mirror could use a random coalition subset and a joint stochastic process indexed by a continuum of advisor labels. That might be a legitimate information-theoretic project. But it is no longer an optimization over a society \(\mu\) of the programme’s kind: it needs a law over microscopic opinion and rating configurations, plus an entropy-rate objective. The paper itself poses no runtime, algorithm, or complexity classification for that optimization. Its named results are extremal information-theoretic bounds, not computational-complexity results. Asking for an asymptotic leakage rate would therefore introduce a new entropy-rate question rather than continuize a computational problem from the paper.
Theorem 6 has the same obstruction. Its claim is a strict finite-instance separation between strategy classes. A normalized asymptotic gap asks about leading rates; a finite-size gap asks about the integer coalition and its individual report patterns. The first is an entropy-rate problem, the second keeps the discrete microstate. Neither becomes a finite-type mass-transfer problem. This does not depend on whether the leading gap is positive or zero. Replacing the target with information about aggregate opinion frequencies would fit a population distribution, but it would ask a different question from the paper’s: the paper measures what ratings reveal about advisors’ individual opinions.
So I would argue against spending ChoCo effort on these anchors. The case is not airtight in the broadest possible sense: an authors-recognized continuum-indexed stochastic-process model could be worth studying. But its value would be as information theory on random fields, not as a continuous mirror of the paper’s computational problem.
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.