Incentives And Pricing In Communication Networks

Motivation: prices in a network nobody controls

Modern networks are huge and span many administrative domains, with end users whose needs differ. Centralized resource-allocation protocols are hard to formulate and harder to deploy. The standard response is to model users, and sometimes providers, as self-interested agents. Two consequences follow:

modeling such networks needs game theory;
without central control, selfish interaction can misallocate resources.

Prices play two conceptually different roles:

Role	Who sets prices	Users	Section
control signal	the network, to implement the social optimum	price takers	§22.1
revenue instrument	competing profit-maximizing providers	route by Wardrop’s principle	§22.2

IntuitionThe central question

Can decentralized prices — computed by routers from local congestion, or set by competing firms for profit — steer selfish traffic to the socially optimal allocation, and when they can’t, how much is lost?

Prices as control: network utility maximization

Setup. A network of links $l$ with capacities $c_l$ is shared by users (sources) $r$ . Each user sends at rate $x_r$ (packets per unit time) along a fixed route. “User,” “source,” “connection” and “route” share the index $r$ , and $l \in r$ means link $l$ is on route $r$ .

DefinitionRouting matrix and utilities

$R_{lr} = 1$ if $l \in r$ , else $0$ . Each user has a utility $U_r(x_r)$ that is strictly increasing and strictly concave. An allocation is socially optimal if it maximizes total utility. (In networking, “social optimality” and “fairness” are often used interchangeably.)

FormulaNUM — Kelly’s resource allocation problem

\max_{x \ge 0}\ \sum_r U_r(x_r) \quad\text{s.t.}\quad Rx \le c. \tag{22.1}

The constraint says $\sum_{r:\, l\in r} x_r \le c_l$ at every link. Strict concavity gives a unique optimum $\hat x$ .

The obstacle. Solving (22.1) needs every utility and every route. VCG (mechanism-design) would elicit utilities, but it needs a central authority solving a global optimization, which is computationally heavy. Kelly’s alternative is simpler.

Link prices are Lagrange multipliers

TheoremKKT conditions for NUM

$\hat x$ is optimal iff there exist multipliers $\hat p \ge 0$ with

U_r'(\hat x_r) = \sum_{l\in r}\hat p_l\ \ \forall r, \qquad \hat p_l\Big(\sum_{r:\,l\in r}\hat x_r - c_l\Big) = 0\ \ \forall l, \qquad \sum_{r:\,l\in r}\hat x_r \le c_l,\qquad \hat p,\hat x \ge 0. \tag{22.2–22.5}

DefinitionRoute price

Charge user $r$ a per-bit price equal to the sum of link prices along its route: $\hat q_r = \sum_{l \in r}\hat p_l, \qquad \hat q = R^T\hat p. \tag{22.6}$

IntuitionReading the KKT conditions

$\hat p_l$ is the shadow price of link $l$ ‘s capacity. It is positive only if the link is full (complementary slackness). At the optimum, each user’s marginal utility equals the total congestion price of its path.

Price takers. If each flow is negligible, users treat prices as fixed and solve

$\max_{x_r \ge 0}\ U_r(x_r) - \hat q_r x_r. \tag{22.7}$

The solution is exactly $\hat x_r$ from (22.2).

ImportantSelfish = optimal, under two assumptions

Users are price takers: reasonable in a huge network like the Internet.
Prices equal the Lagrange multipliers: reasonable when a network controller cares about overall performance, and not when profit-seeking providers set prices (Prices set by competing providers).

RemarkRelation to Chapter 21

This is the network version of Theorem 21.1: price taking plus market clearing gives efficiency. scalable-resource-allocation shows that when users instead anticipate their effect on price, one link loses up to 1/4.

Two practical problems, and the bid mechanism

Computing $\hat p$ runs into two problems:

P1. The network doesn’t know the utility functions.
P2. Even with the utilities, no central authority knows all capacities and the whole topology.

AlgorithmTwo-step bid mechanism

Each user announces a bid $w_r$ : what it is willing to pay per unit time.
The network allocates rates by solving $\max_{x\ge0}\ \sum_r w_r\log x_r \quad\text{s.t.}\quad Rx \le c. \tag{22.8}$

DefinitionWeighted proportional fairness

The solution $x^*$ of (22.8) is the weighted proportionally fair allocation. Its KKT conditions are those of NUM with $U_r'$ replaced by $w_r/x_r$ :

\frac{w_r}{x_r^*} = \sum_{l\in r}p_l^*,\quad p_l^*\Big(\sum_{r:\,l\in r}x^*_r - c_l\Big) = 0,\quad \sum_{r:\,l\in r}x^*_r \le c_l,\quad p^*,x^* \ge 0. \tag{22.9–22.12}

ImportantMatching the bids

If users bid $w_r = x_r^*\,U_r'(x_r^*)$ , then (22.9) coincides with (22.2), so $x^* = \hat x$ . The network solves a utility-free problem, and the bids carry exactly the information needed.

A distributed algorithm: congestion control

Solve (22.8) dynamically, with each link updating its own price.

AlgorithmPrimal–dual congestion control

Links (routers):

\dot p_l = (y_l - c_l)^+_{p_l}, \qquad y_l = \sum_{r:\,l\in r} x_r, \tag{22.13}

where $(a)^+_b = \max(a,0)$ if $b = 0$ , and $a$ if $b > 0$ . The price rises while the link is overloaded, falls while it is underloaded, and never goes negative.

Users (end hosts): $x_r = \frac{w_r}{q_r}, \qquad q_r = \sum_{l\in r} p_l. \tag{22.14}$ Reacting to the route price $q_r$ is what networking calls congestion control.

Equilibria of (22.13) have either $y_l = c_l$ or $p_l = 0$ , which is complementary slackness (22.10). So any steady state of (22.13)–(22.14) satisfies (22.9)–(22.12).

TheoremConvergence for fixed bids

Suppose $R$ has full row rank, so link prices are determined by route prices and $p^*$ is unique. Then for fixed bids, (22.13)–(22.14) converge to $(x^*, p^*)$ .

ProofLyapunov function

V(p) = \tfrac12\lVert p - p^*\rVert^2

Identity used throughout: $q^Tx = p^TRx = p^Ty$ .

\frac{dV}{dt} = \sum_l(p_l - p_l^*)(y_l - c_l)^+_{p_l} \overset{(a)}{\le} (p - p^*)^T(y - c)

= (p - p^*)^T(y - y^*) + (p - p^*)^T(y^* - c) \overset{(b)}{\le} (p - p^*)^T(y - y^*)

= (p - p^*)^TR(x - x^*) = (q - q^*)^T(x - x^*) = \sum_r\Big( \frac{w_r}{x_r} - \frac{w_r}{x_r^*}\Big)(x_r - x_r^*) \overset{(c)}{\le} 0.

(a) If the projection is inactive, this is equality. If active ( $p_l = 0$ and $y_l < c_l$ ), the left term is 0 while the right term $-p_l^*(y_l - c_l) \ge 0$ .
(b) For each link, either $y_l^* = c_l$ , or $y_l^* < c_l$ with $p_l^* = 0$ . Either way $(p_l - p_l^*)(y_l^* - c_l) = p_l(y_l^* - c_l) \le 0$ .
(c) $1/x$ is decreasing, so each summand is $\le 0$ .

The key step: the route-price/rate relation $q_r = w_r/x_r$ is monotone decreasing. That makes the cross term nonpositive, which is exactly the concavity of $w_r\log x_r$ .

∎

NoteStated at this level of detail

The chapter concludes convergence directly from $\dot V \le 0$ . A LaSalle- type argument, using uniqueness of $(x^*,p^*)$ , is implicit.

Bid updates by myopic users

Bids affect what users pay, so users will adjust them. Suppose users are price-taking and myopic, maximizing instantaneous net utility:

\max_{w_r}\ U_r\!\left(\frac{w_r}{q_r}\right) - w_r \;\Rightarrow\; U_r'\!\left(\frac{w_r}{q_r}\right) = q_r \;\Leftrightarrow\; w_r = x_rU_r'(x_r).

FormulaResulting congestion control law

U_r'(x_r) = q_r, \qquad\text{i.e.}\quad x_r = (U_r')^{-1}(q_r). \tag{22.15}

The equilibrium of (22.13) with (22.15) is (22.9)–(22.12) with $w_r = x_r^*U_r'(x_r^*)$ , so $x^* = \hat x$ .

ImportantSelfish objectives align with welfare

Price-taking, myopic users plus multiplier-tracking links reach the social optimum. Convergence follows from the same Lyapunov function.

Architecture from prices

The pricing model decomposes resource allocation across the network:

Congestion control at end users: adapt rates to route-price feedback.
Congestion indication at routers: compute each outgoing link’s price.
Congestion feedback: e.g., a packet header field set to 0 at the source, with each router adding its price. The destination echoes the total $q_r$ back to the source.

graph LR
  S["Source: sets rate from route price"] -->|"packet, price field = 0"| R1["Router 1: adds its link price"]
  R1 --> R2["Router 2: adds its link price"]
  R2 --> D["Destination: reads route price"]
  D -->|"echo route price"| S

Wireless extension: scheduling

In wireless networks, interference means nearby links can’t transmit together.

DefinitionSchedules

A schedule $M_i$ is a set of links that can transmit simultaneously. Let $M_1,\dots,M_n$ be the possible schedules, and $f_i$ the fraction of time schedule $M_i$ is used. The constraints become

\sum_{r:\,l\in r}x_r \le \sum_{i:\,l\in M_i} f_i\,c_l,\qquad \sum_{i=1}^n f_i \le 1,\qquad f,x\ge0, \tag{22.16–22.18}

where $c_l$ is link $l$ ‘s service rate when scheduled.

DerivationThe dual splits into rate control and scheduling

D(p,\lambda) = \underbrace{\max_{x\ge0}\Big[\sum_r U_r(x_r) - \sum_l p_l \sum_{r:\,l\in r}x_r\Big]}_{(22.19)\ \text{same as wireline}} + \underbrace{\max_{f\ge0}\Big[\sum_l p_l\sum_{i:\,l\in M_i}f_ic_l - \lambda\Big(\sum_i f_i - 1\Big)\Big]}_{(22.20)\ \text{new: scheduling}}.

Dropping $\lambda$ and keeping $\sum_i f_i \le 1$ explicit, interchange sums:

\max_{\sum f_i\le1,\,f\ge0}\ \sum_i f_i\sum_{l\in M_i}p_lc_l = \max_i \sum_{l\in M_i} p_l c_l.

This is a linear program, so the optimum is at a vertex: put all weight on one schedule.

AlgorithmMax-weight scheduling

At each instant, activate the schedule maximizing $\sum_{l\in M_i}p_lc_l$ , the capacity-weighted sum of link prices. Sources still use (22.15). Links update

\dot p_l = \Big(y_l - \sum_{i:\,l\in M_i}f_ic_l\Big)^+_{p_l}, \tag{22.21}

which needs no explicit implementation: $p_l$ is just the queue length at link $l$ .

IntuitionQueues are prices

A backlog grows exactly when arrivals exceed service, which is the price dynamics (22.21). So “serve the schedule with the most weighted backlog” is dual ascent in disguise. The long-run fractions of time spent in each schedule solve the utility-maximization problem (see Lin et al. 2006).

WarningThe hard part (open)

Computing the max-weight schedule is computationally hard and must be distributed in practice. Low-complexity distributed approximations are an open problem. Given one, stability follows by a similar Lyapunov argument.

Prices set by competing providers

§22.1 was not game-theoretic: users took prices, and prices were set to implement the optimum. Two gaps remain:

users may face no explicit prices at all (unpriced congestion);
prices are often set by profit-maximizing providers controlling their own domains.

This section studies the second. Competition creates negative congestion externalities between providers: one provider’s price moves traffic onto another’s links.

A two-link warm-up

ExampleExample 22.1 — efficient, selfish, monopoly, duopoly

One unit of traffic, two parallel routes with latencies $l_1(x) = x^2/3$ and $l_2(x) = \tfrac23 x$ .

Regime	$x_1$	$x_2$	Prices
social optimum (min total delay)	$2/3$	$1/3$	—
Wardrop, no prices	$\sqrt3 - 1 \approx 0.73$	$\approx 0.27$	—
monopoly	$2/3$	$1/3$	$p_1 = (2/3)^3 + k$ , $p_2 = 2/3^2 + k$
duopoly	$\approx 0.58$	$\approx 0.42$	$p_1 \approx 0.61$ , $p_2 \approx 0.44$

Optimum: marginal costs $x_1^2$ and $\tfrac43x_2$ are equal at $(2/3, 1/3)$ (both $4/9$ ).

Wardrop: $x_1^2/3 = \tfrac23(1 - x_1)$ gives $x_1^2 + 2x_1 - 2 = 0$ , so $x_1 = \sqrt3 - 1$ . Route 1 is overused, because its users ignore the steeper congestion they cause.

Monopoly: the markup $x_il_i'(x_i)$ is exactly the Pigouvian tax: $x_1 \cdot \tfrac23x_1 = 8/27$ and $x_2\cdot\tfrac23 = 2/9$ . The common constant $k$ extracts all consumer surplus.

Duopoly: $p_i = x_i\,(l_1' + l_2')$ (see (22.27)). At $x_1 = 0.58$ , $l_1' \approx 0.39$ , so $p_1 \approx 0.61$ and $p_2 \approx 0.44$ . Both effective costs are $\approx 0.72$ .

graph LR
  O["Origin: 1 unit of traffic"] -->|"route 1: latency x squared / 3"| D["Destination"]
  O -->|"route 2: latency 2x / 3"| D

WarningMore competition, less efficiency

The duopoly is less efficient than the monopoly. This inverts the usual economic intuition. The monopolist is efficient but takes all surplus; duopoly users may keep positive consumer surplus. (Consumer surplus is willingness to pay minus $p_i + l_i$ . Social surplus is willingness to pay minus $l_i$ only, so it also counts profits.)

IntuitionThe extra duopoly markup: locking in your own users

If provider 1 raises its price, some traffic shifts to route 2, which congests route 2. That makes route 2 a worse outside option, so route 1’s remaining users are more locked in. Each duopolist therefore charges an extra markup on top of the Pigouvian one. The two extra markups differ, so the traffic split is distorted.

Model: parallel links, reservation utility

DefinitionPrice competition setting

$I$ parallel links, $\mathcal I = \{1,\dots,I\}$ . Link $i$ has flow $x_i$ and a convex, nondecreasing, $C^1$ latency $l_i$ with $l_i(0) = 0$ (queueing delay dominates propagation delay).
Link price $p_i$ per unit flow.
$d$ units of traffic from many small users, all with reservation utility $R$ : they don’t send if the effective cost exceeds $R$ .

DefinitionWardrop equilibrium with prices

$x^{WE} \in W(p)$ if

l_i(x_i^{WE}) + p_i = \min_j\big[l_j(x_j^{WE}) + p_j\big] \le R\ \ \text{for all } i \text{ with } x_i^{WE} > 0,\qquad \sum_i x_i^{WE} \le d, \tag{22.22}

with $\sum_ix_i^{WE} = d$ whenever the minimum effective cost is $< R$ . Traffic uses only cheapest routes, and all of it is sent unless even the cheapest route costs $R$ . (Wardrop equilibria in routing-games are the case with no prices.)

FormulaSocial optimum and social surplus

S(x) = \sum_i (R - l_i(x_i))\,x_i, \qquad x^S \in \arg\max_{x\ge0,\ \sum x_i\le d} S(x). \tag{22.23, 22.25}

With two links both used,

l_1(x_1^S) + x_1^Sl_1'(x_1^S) = l_2(x_2^S) + x_2^Sl_2'(x_2^S), \tag{22.24}

so the marginal congestion prices $p_i = x_i^Sl_i'(x_i^S)$ implement the optimum as a Wardrop equilibrium. This is the Pigouvian tax of routing-games.

Monopoly

A monopolist owns all links and maximizes $\Pi(p,x) = \sum_i p_ix_i$ with $x\in W(p)$ . This is a two-stage game: prices first, then Wardrop routing.

DefinitionMonopoly equilibrium (ME)

$(p^{ME}, x^{ME})$ with $x^{ME}\in W(p^{ME})$ and $\Pi(p^{ME},x^{ME}) \ge \Pi(p,x)$ for all $p \ge 0$ and $x\in W(p)$ . This is stronger than subgame perfection, but the two coincide here (Acemoglu–Ozdaglar).

TheoremMonopoly is efficient (Acemoglu–Ozdaglar)

$x$ is an ME flow iff it is a social optimum. The result extends to general topologies (Huang et al. 2006).

NoteStated without proof

This contrasts sharply with selfish routing, where the PoA with general latencies is unbounded (nonlinear Pigou). A monopolist pricing its own network internalizes the congestion externality.

Oligopoly

$S$ providers; provider $s$ owns the links $\mathcal I_s$ and sets their prices $p_s$ . Given rivals’ prices $p_{-s}$ , its profit is $\Pi_s(p_s,p_{-s},x) = \sum_{i\in\mathcal I_s}p_ix_i$ with $x\in W(p_s,p_{-s})$ .

DefinitionOligopoly equilibrium (OE)

$(p^{OE},x^{OE})$ with $x^{OE}\in W(p^{OE})$ such that for every $s$ ,

\Pi_s(p_s^{OE},p_{-s}^{OE},x^{OE}) \ge \Pi_s(p_s,p_{-s}^{OE},x)\quad \forall p_s\ge0,\ \forall x\in W(p_s,p_{-s}^{OE}). \tag{22.26}

This is a pure-strategy subgame perfect equilibrium of the price competition game.

TheoremOE prices

If $p_i^{OE}x_i^{OE} > 0$ for some $i$ , then for every $s$ and $i\in\mathcal I_s$ :

p_i^{OE} = \begin{cases} x_i^{OE}l_i'(x_i^{OE}), & \text{if } l_j'(x_j^{OE}) = 0 \text{ for some } j\notin\mathcal I_s,\\[4pt] \min\left\{R - l_i(x_i^{OE}),\ \ x_i^{OE}l_i'(x_i^{OE}) + \dfrac{\sum_{j\in\mathcal I_s}x_j^{OE}}{\sum_{j\notin\mathcal I_s} 1/l_j'(x_j^{OE})}\right\}, & \text{otherwise.}\end{cases}

With two links and minimum effective cost below $R$ :

p_i^{OE} = x_i^{OE}\big(l_1'(x_1^{OE}) + l_2'(x_2^{OE})\big). \tag{22.27}

Term	Meaning
$x_i\,l_i'(x_i)$	Pigouvian markup: the provider internalizes congestion on its own links
$x_i\,l_j'(x_j)$ (two links)	competitive markup: users leaving congest the rival, which locks in the provider’s remaining users
$R - l_i(x_i)$	ceiling: users drop out beyond the reservation utility
competitor has a zero-slope link	no lock-in is possible, so only the Pigouvian markup remains

NoteDerivation omitted

The characterization comes from the optimality conditions of (22.26), in Acemoglu–Ozdaglar (2006b).

Efficiency of oligopoly

DefinitionEfficiency metric

$r_I(\{l_i\}, x^{OE}) = \frac{S(x^{OE})}{S(x^S)}. \tag{22.28}$ This is a surplus ratio ( $\le 1$ ). We seek its worst case over all price competition games with pure-strategy OE. That class is much larger than linear latencies.

ExampleExample 22.2 — the 5/6 instance

$d = 1$ , $R = 1$ , each link owned by a different provider: $l_1(x) = 0,\qquad l_i(x) = \tfrac32(I-1)x\ \ (i = 2,\dots,I).$

Optimum: everything on the free link 1, $S = 1$ .
Unique OE: $x_1 = \tfrac23$ and $x_i = \frac{1}{3(I-1)}$ otherwise. Each costly link then has latency $\tfrac12$ , so $S(x^{OE}) = \tfrac23 + (I-1)\cdot\tfrac12\cdot\tfrac{1}{3(I-1)} = \tfrac23 + \tfrac16 = \tfrac56.$

Check for $I = 2$ : provider 2’s rival has a zero-slope link, so $p_2 = x_2l_2' = \tfrac12$ . Provider 1 is capped at $p_1 = R - 0 = 1$ . Both routes have effective cost $1 = R$ .

TheoremTheorem 22.3 — oligopoly efficiency ≥ 5/6, tight

For any parallel-link network with $I\ge2$ links and any ownership structure $\{\mathcal I_s\}$ , every pure-strategy OE flow has $r_I \ge \tfrac56$ . Example 22.2 is tight.

NoteProof not given in the chapter

See Acemoglu–Ozdaglar (2006b).

ImportantIndependent of size and market structure

The worst case doesn’t depend on $I$ or on how links are split among providers. Arbitrarily large networks can be as inefficient as small ones. This superficially contradicts the economic result that large oligopolies become competitive. Those theorems concern replicas of a fixed market, not arbitrary large markets.

Extension: elastic traffic

Delay-tolerant applications (e.g., e-mail) can use any amount of bandwidth. Model them with an aggregate utility $u(\sum_ix_i)$ that is increasing, concave and $C^2$ .

DefinitionWardrop equilibrium with elastic demand

l_i(x_i^*) + p_i = u'\Big(\sum_j x_j^*\Big)\ \text{ if } x_i^* > 0, \qquad l_i(x_i^*) + p_i \ge u'\Big(\sum_jx_j^*\Big)\ \ \forall i.

Social surplus and $r_I$ are redefined with $R\sum_ix_i$ replaced by $u(\sum_ix_i)$ .

WarningGeneral concave utility: no bound

With an arbitrary concave $u$ , efficiency can be arbitrarily close to 0 (Ozdaglar 2006).

TheoremTheorem 22.4 — elastic traffic, $u'$ concave: ≥ 2/3, tight

With each link owned by a different provider and $u'$ concave, every pure-strategy OE has $r_I \ge \tfrac23$ , and this is tight.

NoteHistory

Hayrapetyan–Tardos–Wexler (2005) first studied this game and gave nontight bounds ( $1/5.064$ in general, $1/3.125$ with zero free-flow latency). The tight $2/3$ is from Ozdaglar (2006). The proof is not given here.

Extension: parallel–serial topologies

Real traffic crosses several interconnected domains in series. The simplest such topology is parallel paths, each a chain of links owned by different providers.

graph LR
  S["Source: d units, reservation utility R"] --> A1["path 1, link 1"]
  A1 --> A2["path 1, link 2"]
  A2 --> T["Destination"]
  S --> B1["path 2, link 1"]
  B1 --> B2["path 2, link 2"]
  B2 --> T

DefinitionDouble marginalization

A provider raising its price reduces the traffic, and hence the revenue, of every other provider on the same path. It ignores this negative externality, so serial providers stack markups. This is the classic multiple-monopolies problem.

WarningCoordination failure

In its extreme form, every provider expects the others to price high, prices high itself, and kills all traffic on a path. So the analysis restricts to strict equilibria (Harsanyi), where each provider plays a strict best response, and to equilibria in which all traffic is sent. Otherwise efficiency can be arbitrarily low.

TheoremTheorem 22.5 — parallel–serial: ≥ 1/2, tight

In any $I\ge2$ path network with serial links, each link owned by a different provider, every strict OE flow has $r_I \ge \tfrac12$ , and this is tight.

CautionWithout $l_i(0) = 0$ , the bound collapses

If links have positive free-flow latency, the efficiency loss of strict OE can be arbitrarily large. This suggests unregulated competition across general networks can be very costly, and some regulation may be needed.

Setting	Worst-case surplus ratio
selfish routing, no prices, general latencies	unbounded loss
monopoly	1 (efficient)
oligopoly, parallel links, inelastic	$5/6$
oligopoly, elastic, $u'$ concave	$2/3$
oligopoly, elastic, general $u$	$\to 0$
parallel–serial, strict OE, all traffic sent	$1/2$
parallel–serial, $l_i(0) > 0$	$\to 0$

Alternative pricing and incentive approaches

Earlier work on pricing

RemarkFlat vs usage-based pricing

Internet access is mostly flat-fee, but differentiated service classes will need differentiated prices. Usage-based prices can act partly as congestion control. Critics point to billing overhead and users’ uncertainty about their expenses.

Proposal	Idea
smart market (Mackie-Mason–Varian)	bid per packet; serve packets above a cutoff set by marginal willingness to pay and marginal congestion cost; winners pay the market-clearing price, below all admitted bids. Vickrey-like, so truthful
Paris Metro Pricing (Odlyzko)	split the network into logical subnetworks with different prices. Pricier ones are less used, so they give better service
edge pricing	local charges from expected congestion and routes
expected capacity pricing	charge for the capacity the network provisions for you
effective bandwidth pricing	price real-time QoS traffic by its effective bandwidth

DefinitionFirst-best pricing

Tolls that induce system-optimal flows. Marginal cost pricing is the classic example. The toll set is the set of all tolls inducing optimal flows. It can be searched for secondary goals such as minimal total toll or fewest tolled routes (Hearn–Ramana). There is also work with heterogeneous price sensitivities (Cole et al.; Fleischer et al.).

Current directions

RemarkFlat fees and the marginal user

With only the distribution of utilities known, the profit-maximizing flat fee in a wireless network equals the utility of the marginal user, the one indifferent to joining (Acemoglu et al. 2004). The price and the resource-allocation rule determine the marginal user together, so they must be chosen jointly.

RemarkP2P incentives

Every peer is both a client and a server, so capacity grows with demand. Simple models suggest no performance loss as a BitTorrent-type network grows (Qiu–Srikant). But this needs cooperation: if everyone downloads and nobody uploads, scaling fails. Built-in incentives (as in BitTorrent) address this.

RemarkCooperation in multihop wireless

Nodes must forward others’ packets. A node can overhear whether a neighbour forwarded a packet, but a simultaneous transmission by another neighbour can mask it, making an honest node look selfish. This is a prisoner’s dilemma with noisy monitoring. Current models ignore topology and MAC details, and realistic models are open.

Future research

NoteOpen directions

Incentive-compatible differentiated pricing: combine provider competition with mechanism design. By the revelation principle, use direct mechanisms with incentive-compatibility constraints. The difficulty is combining the IC constraints with competition.
Capacity investment: multi-stage models in which providers choose investment and capacity as well as prices. Arguably more important than allocating existing capacity.
Simple pricing rules: quantify how well simple, real-time-computable prices approximate optimal or profit-maximizing ones.

Quick reference

Object	Statement	Note
NUM (22.1)	$\max\sum U_r(x_r)$ , $Rx\le c$	$U_r$ strictly concave, so a unique $\hat x$
KKT (22.2–22.5)	$U_r'(\hat x_r) = \sum_{l\in r}\hat p_l$ ; complementary slackness	link price = shadow price
Route price (22.6)	$\hat q = R^T\hat p$	sum of link prices on the path
Price-taker problem (22.7)	$\max U_r(x_r) - \hat q_rx_r$	solved by $\hat x_r$
Bid mechanism (22.8)	$\max\sum w_r\log x_r$ , $Rx\le c$	weighted proportional fairness
Bid matching	$w_r = x_r^U_r'(x_r^)$ ⇒ $x^* = \hat x$
Link update (22.13)	$\dot p_l = (y_l - c_l)^+_{p_l}$	projected dual ascent
Source update (22.14)	$x_r = w_r/q_r$	congestion control
Lyapunov	$V = \tfrac12\lVert p-p^*\rVert^2$ , $\dot V\le0$	needs full row rank $R$
Myopic users (22.15)	$U_r'(x_r) = q_r$	converge to the social optimum
Architecture	end-host control, router pricing, feedback field
Wireless constraints (22.16–22.18)	capacity $\le \sum_{i\ni l}f_ic_l$ , $\sum f_i \le 1$	schedules $M_i$
Max-weight scheduling	$\arg\max_i\sum_{l\in M_i}p_lc_l$	LP vertex; queues = prices (22.21)
Ex. 22.1	optimum $(2/3, 1/3)$ ; Wardrop $(0.73, 0.27)$ ; monopoly optimal; duopoly $(0.58, 0.42)$	duopoly worse than monopoly
Wardrop with prices (22.22)	used routes minimize $l_i + p_i \le R$	reservation utility
Social surplus (22.25)	$S = \sum(R - l_i)x_i$
Pigouvian price (22.24)	$x_il_i'(x_i)$	implements the optimum
ME	monopoly flow ⟺ social optimum	markup = Pigouvian tax
OE price (22.27)	$p_i = x_i(l_1' + l_2')$ (two links)	Pigouvian + lock-in markup
Ex. 22.2	$l_1 = 0$ , $l_i = \tfrac32(I-1)x$ ⇒ $5/6$
Thm 22.3	oligopoly, parallel: $r \ge 5/6$ , tight	independent of $I$ and ownership
Thm 22.4	elastic, $u'$ concave: $r\ge 2/3$ , tight	general $u$ : $\to 0$
Thm 22.5	parallel–serial, strict OE: $r\ge1/2$ , tight	double marginalization; fails if $l_i(0)>0$
Smart market	per-packet Vickrey-like bids	truthful
Paris Metro Pricing	price-differentiated logical subnets
Flat fee	= marginal user’s utility

Facts to keep to hand

Prices as multipliers and prices as markups are opposite regimes. Multipliers computed by the network implement the optimum exactly (price takers, myopic bids). Markups set for profit are efficient only under monopoly, and competition adds distortion.
The monopoly markup is the Pigouvian tax. Owning all the links makes the congestion externality internal, so profit maximization and welfare maximization pick the same flow. Only the surplus split differs. This inverts selfish routing, where no one owns the externality and the loss is unbounded.
Competition creates a second externality: lock-in. Pushing traffic onto a rival congests it, which makes your own users less willing to leave. That extra markup, $x_il_j'$ , and its asymmetry across providers is the entire source of oligopoly inefficiency.
Serial providers stack markups. Double marginalization turns inefficiency from “bounded” (5/6) into “halved” (1/2), or into complete shutdown without the strict-equilibrium refinement.
Worst cases are topology-free, like the price of anarchy. The 5/6 bound ignores $I$ and ownership, just as nonatomic routing’s 4/3 ignores topology. Large markets are not automatically competitive.
The dual decomposition is the architecture. The Lagrangian separates per-user rate problems (end-host congestion control) from per-link price updates (routers). In wireless it adds a scheduling problem whose prices are literally queue lengths.
Price taking is what makes §22.1 work, and Chapter 21 prices the alternative. Anticipating one’s effect on price costs up to 1/4 on a single link. In a large network with negligible flows, price taking is the natural assumption.

References

Nisan, Roughgarden, Tardos, Vazirani, Algorithmic Game Theory — chapter 22 (Ozdaglar, Srikant)

Related

Incentives And Pricing In Communication Networks

Motivation: prices in a network nobody controls

Prices as control: network utility maximization

Link prices are Lagrange multipliers

Two practical problems, and the bid mechanism

A distributed algorithm: congestion control

Bid updates by myopic users

Architecture from prices

Wireless extension: scheduling

Prices set by competing providers

A two-link warm-up

Model: parallel links, reservation utility

Monopoly

Oligopoly

Efficiency of oligopoly

Extension: elastic traffic

Extension: parallel–serial topologies

Alternative pricing and incentive approaches

Earlier work on pricing

Current directions

Future research

Quick reference

References

Mentioned in