| paper | d4-conf-ecai-2012-0054 |
| 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 in \(O(\tau^2L^3)\) bit operations under standard binary rational encoding. · discrete side: other · adjudication: proved
full proof & adversarial review →
Proposition 1
statement extracted from the paper’s text layer
Given a finite set of interchangeable witness types \(T\), rational masses \(\mu_t\) summing to one, and indicators \(a_t\) specifying which types are selected for a reputation query, compute the normalized directed pair-query mass \(\lambda_{tu}=a_ta_u\mu_t\mu_u\) for each type pair and its total \(\Lambda=\sum_{t,u}\lambda_{tu}\).
Represent the potential witnesses for one reputation query by types \(T\) with masses \(\mu_t\); \(a_t\) marks selected types. Output the pair-query masses \(\lambda_{tu}\) and total workload \(\Lambda\), normalized by the square of the witness population. The total is \(w^2\), where \(w=\sum_t a_t\mu_t\).
The mirror covers only Proposition 1’s communication overhead for probing pairs of selected witnesses. It leaves Propositions 2–3, protocol effectiveness, and the simulations aside.
The strongest honest case is narrow: the lead anchor is Proposition 1, proved in this paper. It says that if \(|W|\) is the number of selected witnesses in Algorithm 1, the protocol’s communication cost is \(O(|W|^2)\). The proof attributes that overhead to asking witnesses about their trust in one another, adding quadratically many messages to the original reputation calculation. This is a resource bound, not a hardness result or a classification of an underlying decision problem. The paper’s Propositions 2 and 3 give equilibrium and success-probability formulas, so I would not present them as computational-complexity anchors.
A plausible regime is a large peer-to-peer service with many participants but relatively few recurring roles: for example, cohorts with the same software, trust-reporting policy, and relationships to other cohorts. Let \(N\) be the number of potential witnesses and \(\tau\) the number of distinct roles, with \(N\) much larger than \(\tau\). For this question, a type must capture everything the protocol uses: whether its members are selected witnesses for the focal trustee, their trust report about that trustee, and their reports about members of every other type. Thus members of one type are interchangeable in the relevant calculation. The mass \(\mu_t\) of type \(t\) is its fraction of the witness population. This is a regime assumption about the network, not a claim that arbitrary trust networks have few types.
The continuous mirror of Proposition 1 is Continuous Sybil-Probing Load. Its input is a finite type set \(T\), rational masses \(\mu_t\) summing to one, and an indicator \(a_t\) for whether members of type \(t\) are in the selected witness set \(W'\) for a fixed reputation query. Type-level trust reports can be included to specify the protocol instance; they do not affect this proposition’s message count. The question is: what is the normalized communication workload of Algorithm 1’s mutual-trust probing stage? Count one unit for each directed trust query between distinct selected witnesses, and return the pair-query mass by type and its total.
Writing \(w=\sum_t a_t\mu_t\), the type-pair query mass is \(\lambda_{tu}=a_ta_u\mu_t\mu_u\), and the total is
\[ \Lambda=\sum_{t,u}\lambda_{tu}=w^2. \]
This is the limit of the finite workload divided by \(N^2\): if \(N_w\) witnesses are selected, querying each ordered pair of distinct witnesses takes \(N_w(N_w-1)\) units, and \(N_w/N\to w\). Proposition 1 suppresses constant-factor details in its \(O(|W|^2)\) bound, so the mirror preserves that asymptotic convention.
This problem is tractable: after reading the type masses and eligibility indicators, compute \(w\) and the pair masses in polynomial time in \(\tau\) and the input bit length. It asks for the communication cost of the authors’ witness-pair protocol, not for a new encoding of their problem. The authors should recognize it as the large-population workload question for exactly the probing step Proposition 1 analyzes. Its scope is only that overhead result; it does not mirror the paper’s equilibrium analysis, attack-prevention effectiveness, or simulations.
The weakest point is substantial: the paper’s main contribution is the strategic dilemma, while this anchor concerns the overhead of one local protocol step. The continuous answer is also a normalized version of a simple quadratic count, not a case where continuous optimization unlocks a difficult algorithm. And the proposed regime needs genuinely repeated trust roles; if trust relations vary arbitrarily from pair to pair, the number of types may grow with \(N\), defeating the high-multiplicity premise.
The mirror does suggest further questions, but they are beyond Proposition 1: how much pair-query mass is needed to achieve a target probability of exposing a collusion, and how that tradeoff changes when witness types have different attack rewards and detection costs. Those would connect the workload question to the paper’s game-theoretic results, but they would need their own precise models and anchors.
The proponent has identified the paper’s only clear computational anchor: Proposition 1’s \(O(|W|^2)\) communication bound. There is a clean scaling calculation behind their mirror. If \(K\) of \(N\) agents are selected witnesses, the probing stage makes \(K(K-1)\) directed queries, so if \(K/N\to w\), the query count divided by \(N^2\) tends to \(w^2\).
The problem is that this limit answers a different resource question from the proposition. The continuous society’s type masses do not determine an absolute number of messages; recovering that number requires retaining \(N\). Normalize by \(N^2\), and the result is a density of pair queries, not the communication cost of a finite execution. That density is well-defined, but Proposition 1 is a counting bound for a protocol that addresses individual agents. The continuous calculation neither analyzes an algorithm over societies nor opens a complexity or optimization question. Its simplicity is not itself the objection; the mismatch is that the proposed mirror replaces the proposition’s resource measure with a normalized statistic.
A more ambitious mirror might ask how much probing is needed to detect a collusion at a target rate. But that is not what Proposition 1 establishes: Algorithm 1 probes all selected witness pairs. Detection also depends on the trust graph’s paths, pair-specific reports, and the stochastic removal of paths. A small set of interchangeable types cannot generally preserve those details. One could impose a block-network or graphon model, but then the result would depend on new assumptions about how connections and reports are generated. If types instead record enough individual neighborhood information to preserve the original graph calculation, their number can grow with \(N\). Either route may motivate a new project, but neither supplies a continuous mirror of the named bound.
The paper’s central results do not offer a stronger computational anchor. Propositions 2 and 3 analyze a fixed two-action game and give equilibrium and success-probability formulas. The payoffs depend on \(g\), \(c\), and the protocol’s Sybil probability \(\delta\), not on how many malicious agents there are. Giving attackers a distribution of types would average or stratify those games; making their choices interact through the network would require a new strategic model. The simulations vary the malicious-agent proportion, which makes a population-scale study plausible, but they are not a theorem or computational problem to continuize.
So the negative case is a scope argument, not a claim that high multiplicity is implausible for reputation systems. The paper’s large-network setting and population proportions make such a regime credible. I would still argue against treating this paper as a strong ChoCo mirror: its one named resource bound yields a normalized pair-count, while the results carrying the paper’s contribution do not formulate a population-level computational problem. That verdict is not airtight if ChoCo wants to include asymptotic workload models; under that broader standard, the \(w^2\) mirror is legitimate, though narrow.
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.