Manipulation-Resistant Reputation Systems

Motivation: trusting strangers online

The Internet enables interactions between parties with no common context. Their value depends on the partner’s ability and reliability. An online shopper may find better deals, or be defrauded with little redress.

Making each entity’s history visible does three jobs:

Benefit	Economic problem solved
reveals ability, so others choose partners and terms	information
future visibility deters cheating or shirking now	moral hazard
high-ability entities are distinguishable and rewarded, so they join	adverse selection

IntuitionThe central question

A reputation system is only as good as the histories it records and the identities it attaches them to. When participants can abandon bad names, shade or skip their feedback, and invent fake raters, which guarantees can a reputation system still provide — and which are impossible?

What a reputation system is

DefinitionReputation system

A system that collects, maintains and disseminates reputations: aggregated records of each participant’s past interactions. Records combine objective data (e.g., sale price) with subjective feedback (e.g., buyer and seller rating each other; peers reporting availability). Reputations are usually numeric summaries, for easy comparison.

graph LR
  I["Interactions between entities"] --> C["Collect objective data and feedback"]
  C --> U["Aggregate and update reputations"]
  U --> D["Disseminate reputations"]
  D --> I

Aggregation happens along three dimensions:

across users: a statistic of everyone’s reports about $A$ ;
across time: a statistic of past reports;
transitive trust: reports from highly reputed users weigh more.

NoteScope

Economic models in which actions link to outcomes only probabilistically, or with observation error, are “interesting and complex” but out of scope. The chapter studies threats to the system itself: how histories are collected and attached to identities.

DefinitionThree threats

Whitewashing: take a new pseudonym and start over with a clean record.
Incorrect feedback: don’t report it, or don’t report it honestly.
Phantom feedback: feedback on interactions that never happened, often from sock puppets or sybils, identities created for the purpose.

Threats 1 and 3 both come from cheap pseudonyms.

Threat	Model	Remedy	Section
whitewashing	repeated PD with random matching	pay-your-dues	Whitewashing
dishonest or missing feedback	common-prior signal model	peer prediction	Eliciting effort and honest feedback
dishonest and phantom feedback	trust graph	seeded, path-based ranking	Transitive trust and sybils

Why reputations work: the repeated Prisoner’s Dilemma

DefinitionThe stage game

	Bob: $C$	Bob: $D$
Alice: $C$	$1,\ 1$	$-1,\ 2$
Alice: $D$	$2,\ -1$	$0,\ 0$

One-shot, $D$ is dominant, so the outcome is $(D,D)$ .

FormulaDiscounted average payoff

$\pi_i = (1 - \delta)\sum_{t=0}^\infty \delta^t\pi_i^t,\qquad 0\le\delta<1.$ The factor $(1-\delta)$ normalizes: getting $1$ every round gives $\pi_i = 1$ . $\delta$ measures how much future rounds matter (think of interest rates).

DefinitionGrim trigger

Play $C$ until anyone has played $D$ , then play $D$ forever. $(\text{Grim}, \text{Grim})$ is a subgame perfect Nash equilibrium (SPNE) when no player wants to deviate at any stage game.

ProofGrim is an SPNE iff

\delta\ge1/2

Step 1: One-shot deviations suffice (the single-deviation property from dynamic programming).

Step 2: Compare. Deviate at round 0: $(1-\delta)(2 + 0 + 0 + \cdots) = 2(1-\delta)$ . Comply: $(1-\delta)(1 + \delta + \cdots) = 1$ .

Step 3: Solve. Complying is optimal iff $1\ge2(1-\delta)$ , i.e. $\delta\ge\tfrac12$ . The same holds at every round $t$ , since both sides scale by $\delta^t$ .

∎

ImportantReputations need patience

If players don’t value the future enough (small $\delta$ ), no reputation system can constrain behaviour. Less harsh strategies, which punish for only a few rounds, can also sustain cooperation, for higher $\delta$ .

DefinitionReputational Grim (random matching)

$N+1$ players ( $N$ odd) are paired at random each round. Everyone starts good, and stays good by playing $C$ against good partners and $D$ against bad ones. This is an SPNE for $\delta\ge\tfrac12$ : a deviator faces the same punishment as under full Grim.

WarningPrivate histories don’t scale

Without shared reputations, a player can punish only on her own encounters (personalized Grim, $N$ separate games). She meets a given partner about once every $N$ rounds, so the SPNE condition becomes $\delta \ge 1 - \frac{1}{2N},$ which is unreasonably close to 1 for large $N$ . Shared histories are what make reputations work at scale. (Compare direct vs indirect reciprocity in p2p-incentives.)

NoteDerivation left as an exercise

The chapter gives $1 - 1/(2N)$ without derivation.

RemarkHeterogeneous abilities

Varying ability is modelled by different action sets. A commitment type has one action only (low types only $D$ , honest high types only $C$ ), or $C$ may cost low types more. Strategic types choose actions to mimic high types. With noisy outcomes, strategic types can defect occasionally and hide among honest types who have bad luck.

Whitewashing

WarningCheap identities destroy Grim

A player can play $D$ , then re-register under a new name next round. Punishment never reaches the deviator.

Entry fees

DerivationThe fee needed to deter whitewashing:

f\ge1/\delta

Charge $f$ to register. Whitewash once (defect, pay again, cooperate after):

\pi' = (1-\delta)\big(2 - f + \delta(1 - f) + \delta^2 + \delta^3 + \cdots\big).

Comply: $\pi = (1-\delta)\big(1 - f + \delta + \delta^2 + \cdots\big).$ Then $\pi - \pi' = (1-\delta)(\delta f - 1)$ . So $\pi \ge \pi'$ iff $\delta f \ge 1 \iff f \ge \frac1\delta.$ $\delta\ge1/2$ is still needed to stop deviation without whitewashing.

Pay your dues

Fees may be infeasible or politically unacceptable. Instead, charge a reputational fee.

DefinitionPay-your-dues (PYD)

vs a veteran who has never deviated from PYD: play $C$ ;
vs a veteran who has deviated: play $D$ ;
vs a newcomer: play $D$ , unless you are a newcomer too, in which case play $C$ .

Veterans get to exploit newcomers once; newcomers “pay dues” by cooperating while exploited.

IntuitionWhy this deters whitewashing

A whitewasher returns as a newcomer and gets exploited, which costs as much as the punishment it tried to escape. Newcomers must be penalized at least as much as deviators, because they are indistinguishable.

WarningAn unavoidable social cost

A veteran–newcomer pair plays $(D,C)$ , with total payoff $2 - 1 = 1$ instead of $2$ for $(C,C)$ . Making newcomers defect against each other too would give $0$ , which is even worse. So whitewashing imposes a cost on society that even the best equilibrium can’t avoid. Under PYD, every player still averages a discounted payoff of 1 (exercise).

A more realistic dynamic model

WarningThe naive model is too easy

If the population is fixed, every newcomer is a whitewasher. Always defecting on post-period-1 arrivals (and personalized Grim otherwise) is then fully efficient.

Add real turnover. $\alpha N$ genuine newcomers arrive each period and as many random veterans leave. There is still a fragile equilibrium: play PYD while exactly $\alpha N$ newcomers appear, and defect forever if more appear. One deviation collapses everything. Such knife-edge equilibria are artifacts of noiselessness and perfect rationality.

TheoremPYD is the most efficient equilibrium under noise (Friedman–Resnick)

Add noise: in any stage game, a player plays $D$ by accident with probability $\epsilon > 0$ and returns next period as a whitewasher. Then PYD yields the highest fraction of cooperative outcomes of any equilibrium.

NoteProof omitted

Showing PYD is an equilibrium uses dynamic programming. Optimality needs a careful stochastic analysis (Friedman–Resnick 2001), not reproduced.

ImportantDistrust of newcomers is the price of cheap pseudonyms

In practice PYD means mistrusting newcomers until they prove themselves. The only way to treat newcomers better is to make whitewashing harder for existing members than for genuine newcomers. For example: require a true name, give one free pseudonym, and restrict or charge for additional ones.

Eliciting effort and honest feedback

Subjective feedback has two problems:

Problem	Cause
underprovision	forming and reporting an opinion takes effort; the benefit goes to others
dishonesty	niceness or fear of retaliation suppresses negatives; conflicts of interest, or wanting to look like a good rater, distort reports

If objective outcomes are later revealed (weather, sports), reports can be scored against them; see prediction-markets. The hard case is no objective outcome: either none exists (product “quality”), or it exists but is private (breakdown frequency, known only to owners).

WarningRewarding agreement causes herding

Scoring raters by agreement with peers backfires. A rater with a bad experience of a seller with a stellar record still expects the next rater to report good, so she reports good too. This resembles herding and information cascades.

NoteMeta-moderation

Slashdot has users rate the raters. That is inefficient (effort diverted from rating content) and only pushes the incentive problem up one level.

RemarkCurrency of rewards

Scores can become money or discounts, but prestige often suffices: Slashdot “karma,” ePinions status, chess and bridge ratings.

The model

DefinitionSignal model

A product has a fixed type $t\in\{1,\dots,T\}$ with a common prior $\Pr_0(t) > 0$ .
Raters $i\in I$ , with $|I|\ge3$ , possibly countably infinite. Each privately observes a signal $S^i\in\{s_1,\dots,s_M\}$ .
Given the type, signals are i.i.d. with commonly known $f(s_m\mid t) > 0$ , which differs across types (so signals are informative).
Raters report $x^i$ to a center, which has no independent information and pays transfers $\tau_i(x)$ based only on reports.
Raters are risk-neutral with utility linear in points.

DefinitionBest response and truthful equilibrium

$\bar x^i$ is a best response if for every signal $s_m$ and every alternative report $\hat x^i$ :

\mathbb{E}_{S^{-i}}\big[\tau_i(\bar x^i_m, \bar x^{-i})\mid S^i = s_m\big] \ge \mathbb{E}_{S^{-i}}\big[\tau_i(\hat x^i, \bar x^{-i})\mid S^i = s_m\big]. \tag{27.1}

Truthful revelation ( $x^i_m = s_m$ ) is a (strict) Nash equilibrium if truth is a (strict) best response when everyone else is truthful.

ExampleRunning example: two types, two signals

$\Pr_0(H) = \Pr_0(L) = 0.5$ , with $f(h\mid H) = 0.85$ and $f(h\mid L) = 0.45$ . So $\Pr(h) = 0.65$ and $\Pr(l) = 0.35$ .

Predicting another rater $j$ :

\Pr(S^j = h\mid S^i = l) = 0.85\cdot\frac{0.15\cdot0.5}{0.35} + 0.45\cdot\frac{0.55\cdot0.5}{0.35} \approx 0.54,

\Pr(S^j = h\mid S^i = h) = 0.85\cdot\frac{0.85\cdot0.5}{0.65} + 0.45\cdot\frac{0.45\cdot0.5}{0.65} \approx 0.71.

The herding trap: even after seeing $l$ , rater $i$ thinks $j$ will probably see $h$ ( $0.54$ ). A pure agreement reward would make her report $h$ .

Peer-prediction scoring

DefinitionDefinition 27.1 — strictly proper scoring rule

A rule $T(s\mid\text{report})$ is strictly proper if a rater uniquely maximizes her expected score by reporting her true beliefs.

ExampleLogarithmic scoring rule

For a binary event with reported probability $\hat p$ of $h$ : $T(h\mid\hat p) = \ln\hat p$ and $T(l\mid\hat p) = \ln(1 - \hat p)$ . With true belief $p$ , the expected score $p\ln\hat p + (1-p)\ln(1-\hat p)$ has first-order condition $\hat p = p$ .

DefinitionPeer-prediction method (Miller–Resnick–Zeckhauser)

Assign each rater a reference rater $r(i) \ne i$ . The rater reports only her signal. The center infers her implied forecast of the reference rater’s report and scores it with the log rule:

\tau_i^*\big(x^i, x^{r(i)}\big) = T\big(x^{r(i)}\mid x^i\big) = \ln\Pr_0\big(S^{r(i)} = x^{r(i)}\mid S^i = x^i\big). \tag{27.2}

Component	Detail
Input	$i$ ’s report and the reference rater’s report
Inferred belief	posterior over $S^{r(i)}$ given $S^i = x^i$ , computed by the center from the common prior
Output	log-probability the inferred belief assigned to what $r(i)$ actually reported (a penalty $\le 0$ )
Not required of the rater	any Bayesian computation

TheoremProposition 1 — truthful reporting is a strict Nash equilibrium

For any assignment $r(i)\ne i$ , truthful reporting is a strict Nash equilibrium of the simultaneous reporting game with transfers $\tau_i^*$ .

ProofStrict propriety applied to the inferred forecast

Step 1: The reference rater is truthful. Then $S^i$ is stochastically informative about $r(i)$ ‘s report.

Step 2: Rater $i$ ‘s problem. With true signal $s^*$ , she chooses $x^i$ to maximize

\sum_{n=1}^M T\big(s_n\mid x^i\big)\,\Pr\big(S^{r(i)} = s_n\mid S^i = s^*\big). \tag{27.3}

The key step: reporting $x^i$ amounts to announcing the forecast $\Pr(S^{r(i)}\mid S^i = x^i)$ . The true forecast is the one conditioned on $s^*$ . The log rule is strictly proper, and different signals induce different forecasts (signals are informative), so (27.3) is uniquely maximized at $x^i = s^*$ .

∎

ExampleThe numbers: honesty wins

Rater $i$ saw $l$ .

Report	Expected score
honest $l$	$0.54\ln0.54 + 0.46\ln0.46 \approx -0.69$
lie $h$	$0.54\ln0.71 + 0.46\ln0.29 \approx -0.75$

The expectations use $i$ ‘s true beliefs ( $0.54$ , $0.46$ ). The log terms use the forecast implied by her report.

ImportantWhy peer prediction beats agreement

The score depends on the updated belief about the peer’s signal given your report, not on whether you match. The update already folds in the prior, so there’s no reason to shade your report toward the prior’s likely outcome. The rater just reports what she saw, trusting the center to do the Bayes.

NoteScores are penalties

Since $0 < \Pr < 1$ , $\tau_i^* < 0$ . Adding a constant that depends only on $f$ makes scores positive without changing incentives.

WarningNon-truthful equilibria exist

“Always report $h$ ” is also an equilibrium. Against an always- $h$ reference rater, reporting $l$ scores $\ln0.54\approx-0.62$ and reporting $h$ scores $\ln0.71\approx-0.34$ . Similarly for always- $l$ . Mitigations:

the truthful equilibrium is focal (limited communication; some raters prefer honesty);
the center can punish everyone on detecting an uninformative pattern.

Extensions.

Modification	Effect
add a constant	raises payoffs; incentives unchanged
multiply by a constant	incentives unchanged, but tunes how much costly effort raters spend acquiring signals
settle via transfers between raters	budget-balanced, no subsidy from the center
alternative proper rules	smaller expected payments (Jurca–Faltings)
sequential reporting	score each rater on the belief implied by the prior, previous reports and her own; reporting her own signal stays optimal

CautionThe weak point: common priors

The center needs common beliefs about types and about signal distributions given types, to infer each forecast. Eliciting the forecast directly fails, because $i$ ‘s signal report is also needed to score someone else.

Partial fix 1: ask each rater for her personal prior over types before she observes, then her signal.
Partial fix 2: define types empirically by their signal distributions (type 1 gives 10% $h$ , type 2 gives 20%, …), which makes the conditional signal beliefs common by construction.

NoteOpen questions

Raters of differing ability, where scores both assess credibility and give incentives; self-selected rather than random interaction partners; robustness to collusion and sybil confirmers.

Transitive trust and sybils

DefinitionTransitive trust

Postulate: a rater’s credibility equals her reputation as an actor. Weight ratings of an entity by the raters’ credibilities, which come from their reputations. This is recursive: bootstrap from a credible set and grow it along positive feedback. Positive feedback from a well-rated eBay member counts more.

DefinitionTrust graph and reputation function

Ignore time order. The trust graph is $G = (V, E, t)$ , where $t(ij) > 0$ summarizes $i$ ‘s trust in $j$ . Graphs are sparse, so $E$ is listed explicitly. A reputation function $F : G \to \mathbb{R}^{|V|}$ induces a ranking of the nodes. $F$ is trivial if the ranking is the same for every $G$ .

Reputation function	Definition	Seeded?
PageRank (simple)	$F_v = \epsilon + (1-\epsilon)\sum_{(v',v)\in E}F_{v'}\,t(v',v)$ ; web: $t(v,w) = 1/\mathrm{Out}(v)$	no (symmetric)
max-flow (Advogato)	$F_v$ = max flow from seed $v_0$ to $v$ , with capacities $t$	yes
Pathrank	ranked by shortest path from $v_0$ to $v$ , edge length $1/t$ (shorter = better)	yes

In P2P settings each node can use itself as the seed (personalized reputation). For web ranking, pick trusted seeds.

DefinitionMonotonic and symmetric

Monotonic: adding an incoming edge $uv$ never lowers $v$ ‘s rank relative to any $w$ (both strict and weak order preserved). All three functions above are monotonic (PageRank: Chien et al.).
Symmetric: $F$ commutes with relabelling nodes; reputations depend only on graph structure. PageRank is symmetric. Max-flow and Pathrank are not: the seed is privileged.

Honest reporting: rank-strategyproofness

WarningTransitive trust has the worst incentives

Raters are rewarded only for ratings they receive, never for ratings they give. So there is no incentive to rate informatively, and possibly an incentive to rate strategically, to undermine rivals’ credibility.

DefinitionRank-strategyproof

No agent $v$ , in any graph, can improve her position in the ranking by changing how she rates others. (Changing scores is allowed; improving rank is not.)

TheoremImpossibility for symmetric systems

No nontrivial, monotonic, symmetric reputation system is rank-strategyproof.

ExamplePageRank manipulation

Node $v$ can drop an outgoing edge to a higher-ranked node $u$ . That lowers $u$ ‘s score, which can move $v$ above $u$ .

NoteCited, not proved

See Altman–Tennenholtz and related axiomatic work (compare the axiomatic method in cost-sharing). Pathrank escapes: it is monotonic and rank-strategyproof.

Sybil attacks

DefinitionDefinition 27.2 — sybil strategy

Given $G$ and user $v$ , a sybil strategy is a graph $G'$ and a set $U'\ni v$ of sybils such that collapsing $U'$ into one node labelled $v$ gives back $G$ . The attacker may create any number of sybils with any trust among them, split incoming trust among them in any way that preserves the total $\sum_{v'}t(v',v)$ , and set outgoing edges arbitrarily.

DefinitionDefinitions 27.3–27.4 — sybilproofness

Value-sybilproof: no sybil strategy gives any $u\in U'$ a score $F_u(G') > F_v(G)$ . You can’t raise your number.
Rank-sybilproof: no sybil strategy gives some $u\in U'$ a score $F_u(G')\ge F_w(G')$ for some $w\in V\setminus\{v\}$ with $F_v(G) < F_w(G)$ . You can’t overtake anyone.

TheoremTheorem 27.5 — no symmetric rank-sybilproof function

No nontrivial symmetric reputation function is rank-sybilproof. Monotonicity is not assumed.

ProofClone the whole network

Step 1: Pick a target. Nontriviality gives a graph $G$ with $F_w(G) > F_v(G)$ .

Step 2: Sybil strategy. Let $G'$ be two disjoint copies of $G$ , and let the sybils $U'$ be $v$ together with the whole second copy. Collapsing $U'$ into $v$ returns $G$ (up to internal edges).

The key step: by symmetry, swapping the two copies is an automorphism, so the copy $u$ of $w$ has $F_u(G') = F_w(G')$ . A sybil now ties $w$ , whom $v$ previously trailed. Rank-sybilproofness fails.

∎

graph LR
  subgraph Original["Original graph G"]
    V1["v: lower rank"] --- W1["w: higher rank"]
  end
  subgraph Clone["Sybil copy of G, all controlled by v"]
    V2["copy of v"] --- W2["copy of w: ties w by symmetry"]
  end

DefinitionDefinition 27.6 — $K$ -rank-sybilproof

Rank-sybilproof against all sybil strategies with $|U'|\le K+1$ .

TheoremTheorem 27.7 — even one sybil breaks symmetry

No nontrivial symmetric reputation function is $K$ -rank-sybilproof for any $K > 0$ .

ProofAdd the clone one node at a time

Step 1: Interpolate. With $V = \{v = v_1, \dots, v_r = w\}$ and clone $\{u_1,\dots,u_r\}$ , let $G^t$ contain $V\cup\{u_1,\dots,u_t\}$ . So $G^0 = G$ and $G^r = G'$ .

Step 2: A first crossing. At $t = 0$ , the best of $v$ ‘s identities trails $w$ . At $t = r$ , $u_r$ ties $w$ (Theorem 27.5). So some $t$ has $\max_{i\in\{v,u_1..u_t\}}F_i(G^t) < F_w(G^t)$ but $\max_{i\in\{v,u_1..u_{t+1}\}}F_i(G^{t+1}) \ge F_w(G^{t+1})$ .

The key step: let $m$ be the top identity in $G^{t+1}$ . Either $m$ or $u_{t+1}$ now reaches $w$ . So adding the single node $u_{t+1}$ is a successful 1-sybil strategy for $m$ in $G^t$ .

∎

WarningPageRank

PageRank is symmetric, so it is not rank-sybilproof. About half of all web pages could double their PageRank with a single sybil.

Escape: break symmetry with a trusted seed. Seeding alone isn’t enough; the aggregation rule matters too.

TheoremTheorem 27.8 — max-flow is value-sybilproof

The max-flow ranking from a seed $s$ is value-sybilproof.

ProofMin cut bounds every sybil

By max-flow = min-cut, $F_v(G)$ is the capacity of a minimum $s$ – $v$ cut. All of $v$ ‘s sybils lie on $v$ ‘s side of that cut, away from $s$ . The trust entering them is at most the trust entering $v$ , so no sybil’s max flow exceeds $F_v(G)$ .

∎

ExampleFigure 27.2 — max-flow is not rank-sybilproof

Node $a$ lies on a max-flow path to a node $b$ ranked above it. $a$ reroutes its outgoing trust from $b$ into a sybil $a'$ . $a$ ’s own value is unchanged, but $b$ loses the flow through $a$ and falls below $a$ . The attacker can’t raise itself, but it can lower others that depend on it.

TheoremTheorem 27.9 — Pathrank is value- and rank-sybilproof

Shortest-path ranking from a seed is both value-sybilproof and rank-sybilproof.

ProofSybils can’t shorten paths, and blockers are already ahead

Value: sybils sit behind $v$ , so no path to a sybil is shorter than the shortest path to $v$ .

Rank: $v$ can affect $w$ ‘s value only if $v$ lies on the shortest $s$ – $w$ path. But then $v$ is strictly closer to $s$ than $w$ , so $v$ already outranks $w$ . There is no one it could overtake by manipulating.

∎

ImportantFlows vs paths

The pattern generalizes. Generalized flow mechanisms (e.g., “leaky pipes”) are value- but not rank-sybilproof. Generalized path mechanisms are both, and in a large class, only path-based mechanisms are rank-sybilproof.

NoteOpen question

PageRank and max-flow are not worst-case sybilproof but are very useful in practice. Are they less manipulable on average? This needs a precise formulation.

Open problems and extensions

NoteDistributed reputation systems

In P2P and ad hoc networks there is no trusted party computing reputations, and users may intercept or alter messages. Techniques: replication (compute at many nodes and detect inconsistencies), and redundant paths so no single user can block or modify messages. Both are vulnerable to collusion. The defense is to require many colluders, which sybils undermine.

NoteDynamic attacks

Users may claim credit for others’ interactions, or copy others’ actions (puzzle solutions, ratings) to build reputation cheaply. Conversely, dynamics can limit attacks: in P2P, sybils need real interactions to gain incoming links, and low-ranked sybils struggle to find partners.

NoteMetrics and benchmarks

Robustness isn’t everything. Giving everyone zero reputation is perfectly secure and perfectly useless. We need metrics (economic welfare, or more direct measures) of how well an aggregation method serves users’ information needs.

NoteOther disciplines, and synthesis

Sociology and social psychology study the broader notion of trust. The grand challenge is a single design combining honest elicitation, whitewashing and sybil robustness, and distributed computation.

Quick reference

Object	Statement	Note
Benefits of visible history	ability revelation; deters moral hazard; averts adverse selection
Three threats	whitewashing; incorrect feedback; phantom (sybil) feedback	cheap pseudonyms
PD payoffs	$CC = 1$ , $DD = 0$ , $DC = 2$ , $CD = -1$
Discounted average	$\pi_i = (1-\delta)\sum\delta^t\pi_i^t$
Grim SPNE	iff $\delta\ge1/2$	$2(1-\delta)\le1$
Reputational Grim	SPNE for $\delta\ge1/2$ under random matching	shared history
Personalized Grim	needs $\delta\ge1 - 1/(2N)$	private histories don’t scale
Entry fee	deters whitewashing iff $f\ge1/\delta$
PYD	veterans exploit newcomers once; newcomers cooperate	$(D,C)$ total 1 vs 2
Noisy dynamic model	PYD maximizes cooperation	Friedman–Resnick
Fix for newcomer distrust	make new pseudonyms costly for existing members	one free pseudonym
Signal model	common prior $\Pr_0(t)$ ; i.i.d. signals $f(s\mid t)$ ; $\lvert I\rvert\ge3$	center has no outside info
Herding	agreement rewards suppress minority signals	Ex.: $\Pr(h\mid l)\approx0.54$
Strictly proper rule	truth uniquely maximizes expected score	log rule
Peer prediction (27.2)	$\tau_i^* = \ln\Pr(S^{r(i)} = x^{r(i)}\mid S^i = x^i)$	the rater reports only her signal
Prop 1	truthful is a strict NE for any $r(i)\ne i$
Example	honest $l$ : $-0.69$ ; lie $h$ : $-0.75$
Non-truthful equilibria	always- $h$ , always- $l$	focal truth; punish uninformative patterns
Weak point	common priors on types and signal distributions	empirical types
Trust graph	$G = (V,E,t)$ , $F: G\to\mathbb R^{\lvert V\rvert}$
PageRank	$F_v = \epsilon + (1-\epsilon)\sum F_{v'}t(v',v)$	symmetric
Max-flow / Pathrank	flow / shortest path from seed $v_0$	asymmetric
Rank-strategyproof	can’t improve rank by how you rate	impossible if symmetric, monotonic, nontrivial
Sybil strategy (Def 27.2)	$(G',U')$ collapsing to $G$	split incoming trust arbitrarily
Value- / rank-sybilproof	can’t raise own score / can’t overtake anyone
Thm 27.5	no symmetric rank-sybilproof $F$	clone the network
Thm 27.7	not even 1-rank-sybilproof	add the clone node by node
Thm 27.8	max-flow value-sybilproof	min cut; not rank (Fig. 27.2)
Thm 27.9	Pathrank value- and rank-sybilproof	only path-based is rank-sybilproof

Facts to keep to hand

Every remedy trades something away. Pay-your-dues buys whitewashing resistance at the cost of newcomer welfare. Peer prediction buys honesty at the cost of a common-prior assumption and spurious equilibria. Seeded path rankings buy sybilproofness at the cost of symmetry and dependence on a trusted seed.
Anyone indistinguishable from a deviator must be punished like one. Newcomers look like whitewashers, so they pay dues. This echoes the whitewasher problem in p2p-incentives: generosity toward newcomers subsidizes cheaters.
Shared history is what makes reputation scale. Private punishment needs $\delta\to1$ as $N$ grows. Public reputations keep the threshold at $1/2$ .
Score beliefs, not agreement. Peer prediction scores the implied forecast of a peer’s signal with a strictly proper rule, which already corrects for the prior, so honest minority reports aren’t penalized. This is the same proper-scoring-rule logic as market scoring rules in prediction-markets.
Symmetry is fatal for sybil resistance. If $F$ ignores labels, cloning the network (or even adding one well-chosen node) lets an attacker tie anyone. Robust systems must privilege a seed.
Flows can be drained; paths can’t be shortened. Sybils can’t raise their own flow (min cut) but can starve downstream rivals. On shortest paths, anyone able to influence you is already ahead of you, so rank manipulation is impossible.
Security is not the objective. A system that rates everyone zero is unmanipulable and useless. Robustness results must be paired with measures of informativeness.

References

Nisan, Roughgarden, Tardos, Vazirani, Algorithmic Game Theory — chapter 27 (Friedman, Resnick, Sami)