Distributed Algorithmic Mechanism Design

Motivation: mechanisms with no trusted center

Most of algorithmic mechanism design (AMD) decentralizes the incentives but keeps the computation central. In an auction, bidders are selfish, but the auctioneer computes winners and payments. Complexity is judged by ordinary centralized measures. This quietly needs two assumptions:

1. a trusted center exists that every agent will hand its information to;
2. shipping all information there, and computing there, is manageable.

Interdomain routing breaks both. The Internet is a collection of Autonomous Systems (ASes), competing firms stitched together by the interdomain-routing system:

Pressure	Why it rules out a center
Trust	ASes are competitors; they won’t reveal private policy or cede control to anyone
Scalability	a center would need the whole AS graph, re-sent on every change; the graph is huge and volatile
Reliability	a center is a single point of failure or subversion

Scalability and reliability alone already push toward distribution. Even intradomain routing, where all routers trust each other, is almost always distributed. So the computation must be done by the ASes themselves. That gives Distributed Algorithmic Mechanism Design (DAMD).

---

Two ways DAMD differs from AMD

DAMD keeps AMD’s dual concern of incentive compatibility plus complexity, but changes both halves.

Network complexity

When the algorithm runs over an interconnection network $T$, a single running time is the wrong measure. Any distributed algorithm must be charged for at least five resources, and excess in any one makes it unacceptable:

Resource	What it guards against
total messages over $T$	overall network load
max messages over any one link	hot-spot links
max message size	a “distributed” algorithm that secretly ships everything
local computation per node	overloading individual routers
storage per node	routing-state blowup

Computational manipulation

If $T$ is trusted and can act as the center, network complexity is the only difference. But if the agents run the distributed algorithm, a second difference appears. In AMD an agent can only choose among the actions the mechanism defines, for example which bid to report. The outcome is then computed faithfully from those actions. In DAMD an agent can also:

• misreport the result of a local computation to a neighbour;
• refuse to communicate with a neighbour, perhaps to exclude them from the game.

Example in this note	Computational manipulation?	Network complexity?
Distributed VCG: ex-post Nash from replication	yes, the focus	ignored
Multicast cost sharing: network complexity	no (trusted infrastructure)	yes, the focus
Interdomain routing	yes	yes

---

Distributed VCG: ex-post Nash from replication

Setup. There are outcomes $O$ and agents $N$, and agent $i$ has valuation $v_i$ over $O$. There is no trusted center: the agents compute. There is a central enforcer that implements the agreed outcome, collects payments, and imposes a severe penalty if the agents fail to agree.

Why naive distribution fails

graph LR
  A["Agent 1"] --> B["Agent 2"]
  B --> C["Agent 3: writes own bid, fakes 2nd bid low"]
  C --> D["Agent 4"]
  D --> A

Generally: run any distributed algorithm $A$ that computes $\tilde o$, $W$ and each $W_{-i}$ over a subset of the agents, and a participant can tamper with it. The problem is that the agent who computes also has a stake.

The fix: split roles by replication

ProofArgument from the chapter

Step 1: The other group’s answer is truthful VCG. By strategyproofness, truth-telling to the other group is optimal. With the other agents faithful, that group outputs the true $\tilde o$ and $p$.

Step 2: Any deviation in $i$‘s own computation causes disagreement. A manipulated result differs from the benchmark, so the enforcer penalizes everyone, including $i$.

Step 3: So faithful computation is a best response to others’ faithfulness, whatever the types. That is exactly ex-post Nash.

∎

---

Multicast cost sharing: network complexity

The problem. Multicast delivers one packet to many receivers over a shared delivery tree. Packets are replicated at branch points, so each link carries at most one copy. This suits popular real-time content such as movies. Every link transmission costs something, and every receiver gets some benefit. Who should receive the content, and how much should each pay?

Setup.

Symbol	Meaning
$P$	user population
$N$, $L$	network nodes; bidirectional links
$\alpha_0 \in N$	source node of the multicast
$T(S) \subseteq L$	multicast tree rooted at $\alpha_0$ spanning the users in $S \subseteq P$
$c(l) \ge 0$	cost of link $l$, known to its two endpoints
$u_i$	user $i$‘s (private) utility for receiving
$\sigma_i \in \{0,1\}$	whether $i$ receives
$p_i \ge 0$	what $i$ is charged

Monotone routing: $S_1 \subseteq S_2 \Rightarrow T(S_1) \subseteq T(S_2)$. Adding receivers only grows the tree.

A mechanism is a pair $M(u) = (\sigma(u), p(u))$. Crucially, both inputs and outputs are distributed: each $u_i$ enters at user $i$‘s location, and $\sigma_i(u), p_i(u)$ must be delivered back there.

Desiderata. Three properties are desirable:

• strategyproofness, because users are selfish;
• budget balance, so that $\sum p_i$ covers the cost;
• efficiency, so that total welfare is maximized.

MC: the efficient mechanism

This is VCG specialized to multicast. $\widehat{NW} - \widehat{NW}_{-i}$ is $i$‘s marginal contribution to welfare, and $i$ keeps exactly that as surplus.

SH: the budget-balanced mechanism

Why the pruning is well defined. If different removal orders gave different final sets, the mechanism would be ambiguous. Cross-monotonicity rules this out: an agent is never charged less when someone else leaves.

ProofLegal orderings concatenate

Step 1: Legality is inherited by subsets. If $i$ is overcharged when $S$ remains, then by cross-monotonicity $i$ is charged at least as much when any subset of $S$ remains. So $i$ is still overcharged.

Step 2: Concatenation of legal orderings is legal (skipping duplicates). Each pruning in the second ordering happens on a smaller set than it originally did, so it stays legal by Step 1. Example: if $(1,5,7,3)$ and $(7,2,5,8)$ are legal, so are $(7,2,5,8,1,3)$ and $(1,5,7,3,2,8)$.

The key step: so if $S$ and $S'$ are both reachable, then $S \cap S'$ is reachable. The reachable sets are closed under intersection, so there is a unique smallest one, independent of order.

∎

The complexity separation

Both MC and SH are polynomial-time centrally. The real question is distributed cost. The trivial distributed algorithm ships every valuation to one node, computes, and ships results back. That costs on the order of $|P|$ bits across some links.

MC, by contrast, needs two short messages per link. The algorithm runs on the tree $T(P)$ and uses the following notation:

Symbol	Meaning
$V(P)$	node set of $T(P)$
$Ch(\alpha)$	children of node $\alpha$
$res(\alpha)$	users resident at $\alpha$
$u^\alpha$	$\sum_{i \in res(\alpha)} u_i$
$c^\alpha$	cost of the link from $\alpha$ to its parent
$T^\alpha(P)$	subtree at $\alpha$ plus the link to its parent

Why two passes suffice. Computing $p_i$ does not require recomputing $\widehat{NW}_{-i}$ from scratch. Let $i \in res(\beta)$, and let $y_i(u)$ be the smallest $W^\alpha$ on the path from $\beta$ to the root. That is exactly the $A$ that phase 2 carries down to $\beta$. Then:

• if $u_i \le y_i(u)$, removing $i$ does not change which nodes receive the content, so $p_i = 0$;
• if $u_i > y_i(u)$, removing $i$ does change the delivery tree, and $\widehat{NW} - \widehat{NW}_{-i} = y_i(u)$, so $p_i = u_i - y_i(u)$.

See cost-sharing (AGT chapter 15) for more on cost-sharing mechanisms.

---

Interdomain routing: the problem

The ASes must be interconnected to give host-to-host reachability. There is no center they all answer to, so they compute routes themselves. Three features make this hard:

1. there are many ASes;
2. ASes have different, possibly conflicting criteria for preferring routes;
3. the ASes and links change frequently.

Setup. The AS graph is $G = (N, L)$ with $N = \{1,\dots,n\}$. Links are direct connections between neighbouring ASes. Protocols compute each destination independently, so fix a destination $d$. Let $P^i$ be the set of loop-free paths from $i$ to $d$ that are not removed from consideration. A path can be removed by filtering at $i$ or a neighbour, or by link or node failure. A protocol assigns each source $i$ a route $R_i \in P^i$.

Networking perspective

Requirement	Why
Distributed	trust, scale, robustness
Destination-based forwarding	reduces routing state; each AS has one next hop for $d$, so $T_d = \{R_1,\dots,R_n\}$ is a confluent tree into $d$
Adaptive	adjusts to the current topology, with no a priori topology knowledge
Efficient	in time, inter-AS communication, and per-AS storage
Loop-free under autonomy	routes must stay loop-free even while each AS chooses by its own criteria

Distance-vector, link-state and path-vector all satisfy the first four; they differ in space. Only the last requirement separates them.

BGP

Adjacent ASes exchange update messages announcing newly chosen routes, each containing the full list of ASes to $d$. The computation starts when $d$ announces itself to its neighbours. Knowledge of how to reach $d$ then spreads recursively. The network is asynchronous: updates on some links may be delayed.

graph TD
  I["Destination AS announces itself"] --> W["Wait for updates"]
  W --> IM["Import routes from neighbours"]
  IM --> ST["Store routes in routing table"]
  ST --> CH["Choose best route by policy"]
  CH -->|"best route changed"| EX["Export route to neighbours"]
  CH -->|"best route unchanged"| W
  EX --> W

Convergence can fail

We want a stable state: every node prefers its current route to all others in its table, and every table reflects neighbours’ current choices. We also want robustness: convergence on every instance obtained by deleting any nodes and links. Path-vector prevents loops but does not guarantee convergence.

graph LR
  N1["AS 1: prefers 12d over 1d"] --- N2["AS 2: prefers 21d over 2d"]
  N1 --- D["d"]
  N2 --- D

There is an inherent trade-off between local autonomy and global robustness. The standard sufficient condition is the absence of a dispute wheel.

---

The mechanism-design view of routing

Reinterpret BGP’s “arbitrary” policy autonomy as selfish preference. Each source node $i$ has a private valuation $$v_i : S^i \to \mathbb{R}_{\ge 0},$$ where $S^i$ is the set of simple routes from $i$ to $d$ in the complete graph obtained by adding links to $G$. Also $v_i(\emptyset) = 0$.

Component	Detail
Signature	$v_i : S^i \to \mathbb{R}_{\ge 0}$
Domain	every simple $i \to d$ route over the complete graph, including routes that don’t exist in $G$
Codomain	the “monetary value” to AS $i$ of having that route

The social goal is welfare maximization: $$T_d = \arg\max_{T = \{R_1,\dots,R_n\}} \sum_{i=1}^n v_i(R_i).$$

A routing protocol should satisfy two requirements:

• executed honestly, it should maximize social welfare;
• it should be incentive-compatible: no AS gains by deviating from its prescribed actions.

Solution concept: ex-post Nash in a distributed mechanism

Consider $n$ nodes and outcomes $O$. Node $i$ has private type $\theta_i \in \Theta_i$ and utility $u_i : O \times \Theta_i \to \mathbb{R}$.

Concept	Best response holds against	What an AS must know
dominant strategy	every strategy of others	nothing
ex-post Nash	others playing $s^*$, for every type profile	nothing about others’ types
Nash	others playing $s^*$, at the actual types	others’ private routing policies

---

BGP without payments

Networking points to path-vector plus policies that guarantee convergence. Mechanism design demands incentives for faithful execution, usually via payments. The chapter’s result is that, under realistic policy assumptions, plain BGP needs no payments at all.

The Gao–Rexford model

Most AS relationships are of two kinds:

• customer–provider: the customer pays the provider for connectivity;
• peering: two peers exchange traffic free because it helps both (they avoid paying their providers for that traffic).

An AS can be in many relationships at once. These are long-term contracts driven by external factors such as traffic patterns and network size.

Gao–Rexford is not enough for optimality

graph BT
  D["d"] --> N1["AS 1"]
  D --> N2["AS 2"]
  N1 --> N3["AS 3: prefers 31d"]
  N2 --> N3
  N3 --> N4["AS 4: prefers 432d, value 1 + alpha"]

(Arrows point customer → provider.)

Policy consistency

Policy consistency holds in the two best-studied special cases:

Case	Valuation depends on	Why it is consistent
next-hop policies	only the route’s next hop	$(i,j)Q$ and $(i,j)R$ share next hop $j$, so $i$ is indifferent
metric-based policies	total link length (shorter preferred)	a shared prefix $(i,j)$ adds the same length to both

The main theorem

The proof actually establishes something stronger in two ways:

1. it needs only no dispute wheel + policy consistency (Gao–Rexford is one way to get no dispute wheel);
2. every AS gets its individually best route.

ProofInduction along an arbitrary competing route

Step 0: Set up the comparison. Fix a node $m$ and any loop-free route $R = u_k u_{k-1}\cdots u_0 \in P^{u_k}$ with $u_k = m$, $u_0 = d$. Let $R_i = u_i \cdots u_0$ be its suffix, and write $S_i$ for $u_i$‘s route in $T_d$. We show by induction on $i$ that $v_{u_i}(S_i) \ge v_{u_i}(R_i)$. At $i = k$ this says $m$‘s BGP route beats $R$. Since $m$ and $R$ were arbitrary, $T_d$ is locally optimal.

Step 1: Base case $i=0$. The only route is the empty one. Trivial.

Step 2: Induction hypothesis. $$v_{u_{i-1}}(S_{i-1}) \ge v_{u_{i-1}}(R_{i-1}). \tag{14.1}$$ Also, $u_i \notin R_{i-1}$ because $R$ is loop-free.

Step 3, Case I ($u_i \notin S_{i-1}$): extend and apply consistency. Both $S_{i-1}$ and $R_{i-1}$ extend along $(u_i, u_{i-1})$ without loops, and $(u_i,u_{i-1})S_{i-1} \in P^{u_i}$. Then

$$v_{u_i}(S_i) \overset{(a)}{\ge} v_{u_i}\big((u_i,u_{i-1})S_{i-1}\big) \overset{(b)}{\ge} v_{u_i}(R_i).$$

• (a) $T_d$ is stable, so $S_i$ is at least as good as any other route at $u_i$ (eq. 14.3).
• (b) By (14.1) and policy consistency with $j = u_{i-1}$, $Q = S_{i-1}$, $R = R_{i-1}$ (eq. 14.2).

Step 4, Case II ($u_i \in S_{i-1}$): consistency is unusable, so use the wheel. Extending $S_{i-1}$ to $u_i$ would create a loop. Since $u_{i-1}$‘s route passes through $u_i$, we get $u_{i-1} \notin S_i$ (otherwise the confluent tree $T_d$ would contain a cycle). Suppose for contradiction that $v_{u_i}(R_i) > v_{u_i}(S_i)$. Assemble the chain:

• $R_i \preceq_2 S_i$, since $u_i$ prefers $R_i$ (the assumption);
• $S_i \preceq_1 S_{i-1}$, since $S_{i-1}$ passes through $u_i$ and, by destination-based forwarding, continues from there along $S_i$;
• $S_{i-1} \preceq_2 R_{i-1}$, by the induction hypothesis (14.1);
• $R_{i-1} \preceq_1 R_i$, since $R_i = (u_i,u_{i-1})R_{i-1}$.

The key step: this gives $R_i \preceq R_{i-1}$ and $R_{i-1} \preceq R_i$, but they start at different nodes ($u_i \ne u_{i-1}$). That is a dispute wheel, contradicting the hypothesis. So $v_{u_i}(R_i) \le v_{u_i}(S_i)$. (The chapter adds: recall there are no ties in valuations.)

∎

ProofTheorem 14.7 from Lemma 14.8

Step 1: Convergence. Gao–Rexford ⇒ no dispute wheel ⇒ BGP converges to a unique stable $T_d$, by the Griffin et al. result.

Step 2: Local optimality. Lemma 14.8 applies, since policy consistency holds.

Step 3: Local ⇒ global optimality. For any allocation $\{R_1,\dots,R_n\}$, each $R_i \in P^i$, so $v_i(S_i) \ge v_i(R_i)$ termwise. Summing gives $\sum_i v_i(S_i) \ge \sum_i v_i(R_i)$.

Step 4: Local optimality ⇒ deviation-proof. Every AS already holds its single best available route, so no deviation by any group can strictly improve the outcome of even one agent.

Step 5: Deviation-proof ⇒ collusion-proof ex-post Nash. Collusion-proof ex-post Nash only forbids improving one member without harming another. Deviation-proofness forbids improving anyone at all, so it is far stronger. The argument uses no knowledge of other ASes’ types, so it holds ex post. No payments appear anywhere.

∎

---

Open problems

• Beyond routing. Candidates include web caching, P2P file sharing, overlay construction and distributed task allocation. Each has literature on distributed algorithms and on incentives, but no coherent DAMD theory unifies them.
• BGP convergence. There is no complete characterization of robust convergence; no dispute wheel is sufficient, not known necessary.
• BGP incentives. Gao–Rexford + policy consistency are sufficient, not known necessary, for collusion-proof ex-post Nash. There are no necessary and sufficient conditions even for plain ex-post Nash, even allowing payments. Little is known without policy consistency and local optimality.
• Network complexity of BGP is open even when convergence is guaranteed.

---

Quick reference

Object	Statement	Note
AMD vs DAMD	DAMD distributes computation as well as incentives	needed when there’s no trusted center or centralizing is too costly
Network complexity	total msgs, max msgs per link, max msg size, local compute, local storage	excess in any one is unacceptable
Computational manipulation	agents misreport local results or withhold messages	absent in AMD
Distributed VCG	replicate across two groups; penalize disagreement	faithful computation is ex-post Nash, not dominant
VCG payment	$p_i = W_{-i} - W + v_i(\tilde o)$	harm imposed on others
Laffont–Green	strategyproof + efficient + budget-balanced is impossible	hence MC vs SH
MC mechanism	serve largest NW-maximizer $\tilde S$; $p_i = \sigma_i u_i - \widehat{NW} + \widehat{NW}_{-i}$	efficient, strategyproof
SH mechanism	split link cost equally downstream; prune $p_i > u_i$	budget-balanced, strategyproof
SH order independence	legal orderings concatenate; reachable sets closed under $\cap$	via cross-monotonicity
Thm 14.1	SH needs $\Omega(\lvert P\rvert)$ bits over linearly many links	proof not in chapter
Thm 14.2	MC: two messages per link, one up pass, one down pass	message-optimal
MC share	$p_i = \max(0,\, u_i - y_i(u))$, with $y_i$ = min $W^\alpha$ on the path to the root	proof is an exercise
Path-vector	full AS path in each update	only design that is loop-free under autonomy
BGP stages	import → select → export, iterated	each with its own policy
Fig. 14.4	mutual “prefer the other” ⇒ possible oscillation	timing-dependent
Def 14.3	no dispute wheel: $\preceq$ antisymmetric up to same start node	$\preceq = (\preceq_1 \cup \preceq_2)^*$
No dispute wheel	⇒ unique stable allocation, robust convergence	sufficient, not known necessary
Def 14.4	$dM = (\Sigma, g, s^M)$	$s_i^M$ = algorithm $i$ should run
Def 14.5	ex-post Nash: $s^*$ best response for all type profiles	no knowledge of others’ types
Collusion-proof ex-post Nash	no group deviation helps a member without hurting another
Gao–Rexford	no CP cycles; customer > peer > provider; transit only for customers	⇒ no dispute wheel
Fig. 14.5	Gao–Rexford-stable allocation can be arbitrarily suboptimal	loses $\alpha$
Def 14.6 policy consistency	$v_j(Q) \ge v_j(R) \Rightarrow v_i((i,j)Q) \ge v_i((i,j)R)$	holds for next-hop and metric policies
Lemma 14.8	no dispute wheel + consistency ⇒ BGP locally optimal	induction; Case II via dispute wheel
Thm 14.7	Gao–Rexford + consistency ⇒ BGP optimal, collusion-proof ex-post Nash, no payments	actually deviation-proof
Remarks 14.9–10	holds on subinstances; unique equilibrium	no selection problem

Facts to keep to hand

• Distributing computation costs a solution concept. Every result here drops from dominant strategies to ex-post Nash. The drop comes from letting agents compute, not from anything about types.
• Each §14.2 example isolates one axis. VCG has manipulation but no complexity issue; multicast has complexity but obedient infrastructure. Routing has both.
• Two ways to make faithful computation rational. Replication uses a strategyproof core plus a disagreement penalty, so honest play is a benchmark you can’t beat. BGP under Gao–Rexford + consistency uses local optimality: nobody has anything left to gain, so no penalty or payment is needed.
• No dispute wheel does three jobs: convergence, uniqueness (so no equilibrium selection), and the contradiction in Lemma 14.8 Case II.
• Gao–Rexford buys stability; policy consistency buys optimality. Fig. 14.5 is the gap between them: a stable outcome in which an upstream AS disagrees with its next hop.
• In Lemma 14.8 the two cases use different hypotheses. Case I extends a route and uses policy consistency. Case II can’t extend (a loop would form) and uses no dispute wheel.
• Central complexity doesn’t predict network complexity. MC and SH are both polynomial centrally, yet constant vs linear bits per link. Locality of the payment rule, one path-minimum flowing down, is what matters.
• Every sufficient condition in the chapter is not known to be necessary. This applies to dispute wheels, Gao–Rexford, and policy consistency.

References

• Nisan, Roughgarden, Tardos, Vazirani, Algorithmic Game Theory — chapter 14 (Feigenbaum, Schapira, Shenker)