Incentives In Peer-To-Peer Systems

Motivation: voluntary contribution among strangers

Napster (1999) and Gnutella (2000) showed that millions of strangers could self-organize to share content. Yet within six months, two thirds of Gnutella users were free-riding: downloading without uploading. This was long before copyright lawsuits gave users any reason to hide.

Why cooperation is hard in p2p:

Feature	Consequence
large scale, high turnover, anonymity	most transactions are one-shot interactions between strangers
hidden actions	defections may be undetectable
cheap pseudonyms	identities can be multiplied (Sybil) or discarded (whitewashing) at no cost

The strategy space is rich. Beyond share/don’t share, peers choose:

• what private information to reveal (resources, workload, costs, willingness to pay);
• how much hidden effort to exert;
• whom to connect to (network-formation-games);
• when to arrive and leave (strategic churn);
• how to manage their own identities and treat others’.

Mechanism	Reciprocity	Long-term state	Example
barter	direct	none needed	BitTorrent
reputation	indirect	reputation scores	KaZaA, EigenTrust
currency	indirect, stored	account balances	MojoNation, Karma
contracts	— (moral hazard)	outcome-contingent payments	packet forwarding

---

The p2p file-sharing game

Each peer is sometimes a client, who benefits from a download, and sometimes a server, who pays bandwidth and CPU costs to upload.

Why direct reciprocity doesn’t scale

With random matching in a large, dynamic population, two peers rarely meet again, and even more rarely with their client/server roles reversed. The shadow of the future is too faint.

Two remedies follow, and they organize the rest of the chapter:

1. Force repeat interaction with a small set of peers. This is BitTorrent’s barter, and it works for large, popular files.
2. Share information so that behaviour toward others counts. This is reputation, and it covers many files and long timescales.

Dealing with strangers

In high-turnover systems, peers constantly meet strangers with no history. The policy toward strangers is a critical design choice:

Policy toward strangers	Problem
always cooperate	exploited by whitewashers, who leave and rejoin as “newcomers”
always defect	robust to whitewashers, but discourages real newcomers and can trigger defection cycles
cooperate with fixed probability $0<p<1$	not robust against whitewashers
cooperate with probability adapted to strangers’ recent cooperation	effective against whitewashers, at least for low turnover

---

Reputation

Reputation sustains cooperation from evolutionary biology to eBay. In p2p it is paired with service differentiation: contributors earn good reputations and receive good service; free riders get poor service.

Attacks on reputation systems:

Attack	Mechanism
collusion	peers boost each other with false praise, or target a victim with false accusations
Sybil	one peer creates many colluding identities
whitewashing	defect every time, and rejoin under a fresh identity before bad reputation bites

A minimalist model: generosity types

Fixpoint dynamics. From some $x$, peers decide, their decisions define a new $x$, and so on. Write $F(x) = \Pr(\theta_i \ge 1/x)$.

• If $F(x) < x$ (cost exceeds willingness), contribution falls.
• If $F(x) > x$, contribution rises.

With two nonzero fixpoints $x_2 < x_1$:

Region	Direction	Fate
$x < x_2$	down	collapse to $0$
$x_2 < x < x_1$	up	converge to $x_1$
$x > x_1$	down	converge to $x_1$

DerivationUniform generosity $\theta_i \sim U(0,\theta_m)$

Step 1: The willingness curve. For $x \ge 1/\theta_m$, $\Pr(\theta_i \ge 1/x) = 1 - \frac{1}{x\theta_m}$.

Step 2: The fixpoint equation. $x = 1 - \frac{1}{x\theta_m}$, i.e. $\theta_m x^2 - \theta_m x + 1 = 0$.

Step 3: Solve.

$$x_{1,2} = \frac{\theta_m \pm \sqrt{\theta_m^2 - 4\theta_m}}{2\theta_m} = \frac12\left(1 \pm \sqrt{1 - \frac{4}{\theta_m}}\right).$$

The larger root $x_1$ is stable and $x_2$ is not.

Step 4: Read off Claim 23.1. Real roots need $\theta_m \ge 4$. At $\theta_m = 4$, $x_1 = 1/2$. As $\theta_m\to\infty$, $x_1 \to 1$.

System performance. Each peer, contributor or not, gets benefit $\alpha x$ with $\alpha \ge 1$ large, so collapse is socially bad. Only contributors pay, $1/x$ each. With the network size normalized to 1:

$$W_S = \alpha x - \frac1x\cdot x = \alpha x - 1 \quad (x > 0).$$

Reputation-based service differentiation

The penalty has two effects, both raising contribution:

Effect	Formula
reduced cost $R$: free riders consume less, so the load falls to $x + (1-x)(1-p)$	$R = \dfrac{x + (1-x)(1-p)}{x}$
threat $T$: free-riding forfeits a fraction $p$ of the benefit	$T = p\alpha x$

With individual benefit $Q = \alpha x$:

• a contributor gets $Q - R$;
• a free rider gets $Q - T$.

A peer contributes iff $\theta_i \ge R - T$.

DerivationSimplifying $W_S(p)$

Let $L = x + (1-x)(1-p)$. Then

$$x\Big(\alpha x - \frac{L}{x}\Big) + (1-x)(1-p)\alpha x = \alpha x\big[x + (1-x)(1-p)\big] - L = (\alpha x - 1)L.$$

ProofAt full contribution, the threat outweighs the cost

At $x = 1$: $R = 1$ and $T = p\alpha \ge 1$, so $R - T \le 0 \le \theta_i$ for every peer, and everyone contributes. There are no free riders, so no penalty is ever actually imposed, and performance reaches the optimum $\alpha - 1$.

∎

---

Barter: BitTorrent

Rational manipulations (Shneidman et al. 2004, via “specification faithfulness”):

1. understate upload bandwidth while preserving your rank among uploaders, so you upload less without downloading less;
2. Sybil: split into several identities to be picked more often by opportunistic unchoking;
3. whitewash identities when beneficial;
4. upload garbage to inflate your apparent upload rate.

---

Currency

Peers earn currency by contributing and spend it to consume (MojoNation, Karma).

---

Hidden actions: contracts for unobservable effort

Free-riding is observable in principle. Many p2p actions are hidden.

The principal–agent model

graph LR
  subgraph AND["AND: packet forwarding along one path"]
    S1["s"] -->|"agent 1"| M1["relay"]
    M1 -->|"agent 2"| M2["relay"]
    M2 -->|"agent n"| T1["t"]
  end
  subgraph OR["OR: multipath routing"]
    S2["s"] -->|"agent 1"| T2["t"]
    S2 -->|"agent 2"| T2
    S2 -->|"agent n"| T2
  end

Running example	Technology	What the sender observes
packet forwarding in a MANET: each hop is an agent	AND	only whether the packet arrived
multipath routing: duplicate over disjoint paths, one agent per path	OR	whether any copy arrived
query forwarding in p2p file sharing	OR-of-AND	—

Contracts. Under limited liability (no fines), a contract pays agent $i$ an amount $p_i \ge 0$ on success only.

$$u_i(a) = p_i\,t(a) - c(a_i), \qquad u(a,v) = t(a)\Big(v - \sum_i p_i\Big).$$

The principal picks contracts to maximize its utility at a Nash equilibrium of the agents. With multiple equilibria it may “suggest” one. This is justified here because the best Nash equilibrium is also a strong equilibrium, and often the unique one.

The price of unaccountability

If actions were observable, the principal would pay exactly $c$ per worker, so its utility would equal social welfare, $t(a)v - \sum_{a_i=1}c$. Let $S^*(v)$ and $S^*_{oa}(v)$ be the optimal worker sets under hidden and observable actions.

Computational hardness

For general read-once networks, the optimal contract depends on which agents work, not just how many.

ProofSketch: recover network reliability from the contract threshold

Step 1: Start from network reliability. Take an instance $\langle G, \{\zeta_e\}\rangle$: compute $t(E)$, the probability that some path works when edge $e$ works with probability $\zeta_e$. This is #P-hard (Provan–Ball).

Step 2: Build $G'$. AND $G$ in series with a new agent $x$ having $\gamma_x$ just below $\tfrac12$ and $\delta_x = 1 - \gamma_x$. For the original edges, set $\delta_e = \zeta_e$ and $\gamma_e = \zeta_e/2$.

Step 3: Agent $x$ enters last. With $\gamma_x \approx \tfrac12$, $x$‘s effort barely matters, so it joins the optimal contract only at very large $v$, after all of $E$.

The key step: use the supposed optimal-contract algorithm to find the critical $v$ at which $x$ enters. There the principal is indifferent between $E$ and $E\cup\{x\}$, and that indifference equation can be solved for $t(E)$.

∎

---

Open problems

---

Quick reference

Object	Statement	Note
Gnutella free-riding	two thirds within six months	pre-lawsuits
One-shot file sharing	free-ride is dominant	Prisoner’s Dilemma
Direct reciprocity	TFT on your own history with the peer	fails under random matching at scale (Fig. 23.1)
Indirect reciprocity	condition on behaviour toward others	needs reputation
Strangers policy	adapt cooperation to strangers’ recent behaviour	fixed $p$ fails vs whitewashers
Reputation attacks	collusion, Sybil, whitewashing	cheap pseudonyms
Minimalist model	contribute iff $\theta_i > 1/x$	cost $1/x$
Fixpoint	$x = \Pr(\theta_i \ge 1/x)$	attractors $0$, $x_1$; tipping point $x_2$
Uniform types	$x_{1,2} = \tfrac12(1\pm\sqrt{1 - 4/\theta_m})$
Claim 23.1	$x_1\uparrow$ in $\theta_m$, $\to1$; collapse if $\theta_m < 4$
Performance	$W_S = \alpha x - 1$
Penalty: cost	$R = [x + (1-x)(1-p)]/x$	reduced load
Penalty: threat	$T = p\alpha x$	lost benefit
Penalty fixpoint	$x = \Pr(\theta_i \ge R - T)$
Penalty performance	$W_S(p) = (\alpha x - 1)(x + (1-x)(1-p))$
Claim 23.2	$p\ge1/\alpha$ ⇒ equilibrium $x = 1$	threat never executed; welfare $\alpha - 1$
BitTorrent	about 40 peers, 4–5 neighbours, opportunistic unchoke	barter; no seeding incentive
BitTorrent manipulations	understate bandwidth, Sybil, whitewash, garbage uploads	Shneidman et al.
FOX	$k$-ary tree schedule plus grim-trigger meltdown	not subgame perfect
Golle et al.	charge $\propto$ downloads − uploads ⇒ unique strict NE
Friedman et al.	threshold equilibria; optimal money supply	inflation as a lever
Principal–agent	$a_i\in\{0,1\}$, cost $c$, pay $p_i\ge0$ on success	limited liability
AND / OR	$\gamma^{n-m}(1-\gamma)^m$ / $1 - \gamma^m(1-\gamma)^{n-m}$	forwarding / multipath
Marginal contribution	$\Delta_i = t(1,a_{-i}) - t(0,a_{-i})$	Def 23.3
Claims 23.4–23.5	work iff $p_i \ge c/\Delta_i$; optimal $p_i = c/\Delta_i$	information rent $c\,t(0,a_{-i})/\Delta_i$
POU (Def 23.6)	observable-action optimum / hidden-action optimum, worst over $v$	price-of-anarchy analogue
Lemma 23.7	utility, success probability, payment nondecreasing in $v$
Thm 23.8 (AND)	one transition $0\to n$; $\mathrm{POU} = (1/\gamma - 1)^{n-1} + 1 - \gamma/(1-\gamma)$	unbounded
Thm 23.9 (OR)	all transitions $k\to k+1$; $\mathrm{POU}\le 5/2$
Thm 23.10	optimal contracts on read-once networks are #P-hard	via network reliability

Facts to keep to hand

• Every mechanism rebuilds the shadow of the future differently. Barter forces repeat play, reputation broadcasts history, currency stores it as a balance. All three fail when identities are free: Sybil multiplies them and whitewashing resets them.
• Generosity toward newcomers is a subsidy to whitewashers. They are indistinguishable, so any fixed welcome can be exploited. Only welcome levels adapted to observed newcomer behaviour resist it.
• Contribution has increasing returns, which creates tipping points. The cost per contributor is $1/x$, so participation feeds on itself upward and unravels downward. $x = 0$ is always an equilibrium, and a stingy population ($\theta_m < 4$) always falls to it.
• Good threats are never executed. With $p\ge1/\alpha$, everyone contributes and no penalty is imposed. The cost of the mechanism is paid only off the equilibrium path. The flip side: FOX’s threat is so extreme that it isn’t credible (not subgame perfect).
• Hidden action is moral hazard. Pay-on-success contracts must reward the marginal contribution $\Delta_i$, so they overpay by an information rent. The size of the loss depends on complementarity: AND (complements) gives all-or-nothing contracting and unbounded POU; OR (substitutes) gives gradual contracting and POU $\le 5/2$.
• Monitoring has value exactly where effort is complementary. AND’s unbounded POU argues for investing in per-hop monitoring. OR’s bounded POU says end-to-end observation is nearly enough.
• Designing optimal contracts can be as hard as computing reliability. They are #P-hard on general read-once networks.

References

• Nisan, Roughgarden, Tardos, Vazirani, Algorithmic Game Theory — chapter 23 (Babaioff, Chuang, Feldman)