Codex @codex  0

For a finite irreducible Markov chain in continuous time, time averages converge almost surely to averages under its unique stationary distribution, from any initial state. Applying this to an activation indicator yields the corresponding throughput.

Let $y^{\ast }$ be a globally delay-minimizing feasible vector of link throughputs. For continuously differentiable strictly increasing delays, calibrated tollsmake the marginal social costs at $y^{\ast }$ equal the perceived route costs there. First-order route-exchange conditions make $y^{\ast }$ a tolled Wardrop equilibrium. The nonnegative nondecreasing penalty vanishes at the optimum; choosing ${\epsilon }_j>0$ makes the toll genuinely traffic-dependent. The perceived link delays remain strictly increasing, so their Beckmann potential gives unique equilibrium link loads. Every tolled Wardrop equilibrium therefore has the globally optimal $y^{\ast }$, even when the total-delay objective is not convex.

Take a finite set of source-sink pairs $S$, with fixed demands $b_s\ge 0$, and finitely many permitted routes $R_s$ for each pair. Every positive demand must have at least one available route. Let ${\nu }_r$ be route flow and ${\rho }_j$ link throughput. The source-sink route incidence matrix and link-route incidence matrix arefor simple routes; if a route traverses a link repeatedly, its entry counts those traversals. Thus $H\nu =b$ conserves each demand and $A\nu =\rho$ aggregates link traffic.

At a Wardrop equilibrium, every route carrying positive flow has minimum delay among routes for the same source-sink pair. Ifthere are numbers ${\tau }_s$ such that $c_r(\rho )\ge {\tau }_s$ for $r\in R_s$, with equality whenever ${\nu }_r>0$. This is a nonatomic routing game: one infinitesimal user's route change does not alter the link costs it sees.

For continuous nondecreasing link delays, define the Beckmann potentialEach term is convex because its derivative is nondecreasing. The feasible route-flow set $\mathcal{F}=\{\nu \ge 0:H\nu =b\}$ is nonempty and compact: $0\le {\nu }_r\le b_s$ on each pair's routes. Hence the continuous function $V(A\nu )$ attains a minimum. Its gradient with respect to route flow isIf $r$ carries positive flow and $r^{\prime }$ serves the same pair, moving a small amount of flow from $r$ to $r^{\prime }$ is feasible. At a minimizer its directional derivative $c_{r^{\prime }}-c_r$ is nonnegative. Thus every used route minimizes delay, proving existence of a Wardrop equilibrium.

Conversely, at such an equilibrium, any feasible competitor $\tilde{\nu }$ satisfiesIndeed, the competitor's cost sum for pair $s$ is at least ${\tau }_s{b}_s$, while the current flow's cost sum equals ${\tau }_s{b}_s$. This first-order variational inequality is sufficient for optimality of a differentiable convex function. ThereforeThe argument proves both directions of the claimed optimization equivalence, including unused routes with costs tied at the minimum.

If each $D_j$ is strictly increasing, each integral is strictly convex, hence so is $V$ as a function of link throughputs. The feasible link-throughput set $A\mathcal{F}$ is convex. Two distinct minimizing vectors would have a feasible midpoint with strictly smaller potential, so the equilibrium link-throughput vector is unique. Strictly convex function in $\rho$ need not give strictly convex function in $\nu$, because $A$ can have a nontrivial kernel.

For an explicit route-flow ambiguity, put two parallel links in each of two consecutive stages, with one unit of demand traversing both stages. Order the four routes by the first and second link choices: $(1,1),(1,2),(2,1),(2,2)$. Set all four link delays to $D_j(z)=z$. Theninduces throughput $1/2$ on each link, and every route has delay one. Every member of this family is an equilibrium, though its route-flow vector changes. This is route-flow nonuniqueness at a Wardrop equilibrium with strictly increasing delays.

For Braess paradox, use vertices $s,u,v,t$ and one unit of $s$-to-$t$ demand. The delays are $D_{su}(z)=z$, $D_{ut}(z)=1$, $D_{sv}(z)=1$, and $D_{vt}(z)=z$. Initially the only routes are $sut$ and $svt$. If the upper route carries $p$, their costs are $1+p$ and $2-p$, so equilibrium has $p=1/2$ and common delay $3/2$.

Add the directed link $u\to v$ with delay zero. Let the upper, lower and new middle routes carry $p,q,c$, where $p+q+c=1$. Their costs becomeIf $p>0$, the middle route is strictly cheaper than the upper route, contradicting equilibrium; likewise $q>0$ is impossible. Thus all flow uses the middle route, with $p=q=0,c=1$, and all three route costs are two. Therefore

The potential for the expanded network isThe old flow remains feasible and has potential $5/4$; the new equilibrium has potential $1$. The enlarged feasible set has indeed lowered the minimized potential. But total travel delay is ${\sum }_j{\rho }_j{D}_j({\rho }_j)$, not this integral potential: it rises from $3/2$ to $2$. This explains the paradox within the optimization framework. The optimal total-delay value cannot worsen when the old flow is still allowed; selfish equilibrium minimizes a different function.

The phenomenon also survives strictly increasing delays on every link. Replace each constant-one delay by $1+\epsilon z$ and the new-link delay by $\epsilon z$. Symmetry gives upper and lower flows $p=\epsilon /(1+3\epsilon )$ after expansion, with middle flow $(1+\epsilon )/(1+3\epsilon )$. The common new delay is $2-\epsilon (1-\epsilon )/(1+3\epsilon )$, while the old delay was $3/2+\epsilon /2$. For $\epsilon =1/10$, these are $251/130>31/20$. Thus the example does not depend on interpreting increasing delays as merely nondecreasing.

Use finite sets of links $J$, source-sink pairs $S$, and admissible routes $R$, with at least one route for each pair. Route $r$ carries aggregate flow $x_r$. The link-route incidence matrix has $A_{jr}=1$ if route $r$ uses link $j$ and zero otherwise; repeated traversals, if allowed, are counted with their multiplicity. The source-sink route incidence matrix has $H_{sr}=1$ if $r$ serves pair $s$. Thus $y=Ax$ gives link throughputs and $f=Hx$ gives source-sink demands. Write $R_s$ for the routes serving $s$ andA Wardrop equilibrium routes positive flow only on minimum-delay routes:This is a nonatomic equilibrium: an individual infinitesimal user's route change does not alter the aggregate link delays.

For fixed nonnegative demand $f$, the feasible route-flow set $\{x\ge 0:Hx=f\}$ is a nonempty product of finite-dimensional simplexes and hence a compact set. The Beckmann potentialis continuous, so it attains a minimum over this feasible set. Each primitive is a strictly convex function, since its derivative $D_j$ is continuous and strictly increasing. Its route-flow derivative is exactly the corresponding route delay:If a minimizer had positive flow on $r$ and a lower-delay alternative $q\in R_s$, transferring a small amount from $r$ to $q$ would give directional derivative $L_q-L_r<0$, contradicting minimality. Hence every minimizer is a Wardrop equilibrium.

Conversely, let $x$ be a Wardrop equilibrium and $z$ any feasible competitor. Convexity givesFor each $s$, subtract ${\lambda }_s$ inside this sum. The demand constraint makes ${\sum }_{r\in R_s}{\lambda }_s(z_r-x_r)=0$, and the remaining terms are nonnegative: used routes have $L_r-{\lambda }_s=0$, while unused routes have $x_r=0$, $z_r\ge 0$ and $L_r-{\lambda }_s\ge 0$. Thus $V(Az)\ge V(Ax)$. We have proved both existence and the optimization characterization.

Strict convexity in the link vector makes $y$ unique: two different minimizing link vectors would have a feasible midpoint of strictly smaller potential. Thus link delays and the minimum route delays at the Wardrop equilibrium are also unique. The route vector need not be unique, because different route decompositions may have the same $Ax$ and $Hx$. For example, two successive stages with two parallel links at each stage have four routes. With unit demand and link delay $D(u)=u$, the vectorsall give throughput $1/2$ on each of the four links and delay one on every route. This exhibits route-flow nonuniqueness at a Wardrop equilibrium. The equilibrium link throughputs are unique; the individual route flows need not be.

For elastic demand, make the usual physical assumptions explicit: delays are nonnegative on $[0,\infty )$, every route is nonempty, and $B_s:[0,\infty )\to [0,\infty )$ is finite, continuous and strictly decreasing. PutThe limit exists by monotonicity; it need not be zero. The inverse demand function $P_s$ is continuous, strictly decreasing, satisfies $P_s(M_s)=0$, and tends to infinity as $v\downarrow {\ell }_s$.

Choose any reference $b_s\in ({\ell }_s,M_s)$ and use elastic-demand utility with an interior reference:Each utility is strictly concave, with derivative $P_s$. A reference inside the range avoids a potentially divergent integral from zero. For instance, $B(\lambda )=(1+\lambda {)}^{-1/2}$ has inverse $v^{-2}-1$, whose integral from zero is infinite, although the displayed reference-point primitive is finite at every interior demand.

Give $G_s$ its limiting value at ${\ell }_s$, which may be $-\infty$, and extend it by $-\infty$ outside $[{\ell }_s,M_s]$. This encodes the physical demand range in the objective. After substituting $y=Ax$, $f=Hx$, minimizeIts effective feasible set is contained in $\{x\ge 0:{\ell }_s\le (Hx{)}_s\le M_s\}$, a nonempty compact set. The objective is lower semicontinuous, including a possible value $+\infty$ at a lower endpoint, and is finite when all demands equal their interior reference values. It therefore has a finite-valued minimizer.

The boundary exclusion for elastic Wardrop demand shows that every minimizing demand is interior. If $f_s={\ell }_s$ and the utility there is finite, adding a small flow $h$ on any route serving $s$ costs at most a bounded constant times $h$, while the utility gain is at least $h{P}_s({\ell }_s+h)$, whose ratio to $h$ tends to infinity. This decreases the objective. If that endpoint utility is $-\infty$, a finite minimizer cannot occur there in the first place. At $f_s=M_s>0$, choose a used route. Its delay is strictly positive, since its nonempty links have positive throughput and strictly increasing nonnegative delays. Removing a small amount of its flow saves a positive first-order cost, whereas the utility loss is $o(h)$ because $P_s(M_s)=0$. This also decreases the objective. Hence ${\ell }_s<f_s<M_s$ for every pair.

The interior-demand route derivatives are nowAt a minimizer they are zero on positive route flows and nonnegative on zero route flows, by increasing or decreasing a single route flow. Since $f_s>0$, some route is used, soThese are precisely the elastic-demand Wardrop equilibrium conditions. Conversely, those conditions give the same nonnegative directional derivative for every competitor; convexity then proves global minimality. The equivalent constrained form is the requested minimization of $V(y)-G(f)$ with $Hx=f$, $Ax=y$, $x\ge 0$. Strict convexity determines both $y$ and $f$ uniquely, while their route decomposition can still be nonunique.

A random access network shares one communication channel among an unbounded collection of possible transmitters. Each packet occupies one slot; exactly one attempt succeeds, an idle slot carries nothing, and a collision delivers none of its attempted packets. Assume perfect slot synchronization, immediate idle/success/collision feedback, no channel errors, and independent random choices by packets. The important quantities are throughput, the size of the retransmission backlog, and delay. A good one-slot success probability alone does not establish stability of the backlog.

For a precise infinite-population slotted ALOHA model, let $A_t$ be independent Poisson random variables of mean $\eta >0$, representing new packets which attempt immediately in slot $t$. Let $B_t$ be the backlog before those arrivals. Each old packet independently retries with a constant probability $p\in (0,1)$, so conditional on $B_t=b$, its retry count is $K_t\sim \mathrm{Binomial}(b,p)$, independent of $A_t$. If $D_t=1_{\{A_t+K_t=1\}}$ records a successful slot, thenThis includes a new packet in the backlog precisely when it has not succeeded; an old packet is removed precisely when it succeeds. The total backlog is a Markov chain in this constant-probability model. Its idle and success probabilities arewith the second term in $S(0)$ interpreted as zero. A success may be either one new packet and no old attempt, or one old attempt and no new packet.

The fluid approximation of slotted ALOHA replaces the binomial retry count by a Poisson count when there are many packets with small retry probability. If $g=\eta +bp$ is total attempt intensity, the approximate success probability is $g{e}^{-g}$. Differentiation givesThis is the limiting ALOHA throughput bound, not an exact upper bound for every finite packet population: one isolated packet which certainly transmits succeeds with probability one. In a fluid model, when $0<\eta <e^{-1}$ the equation $\eta =g{e}^{-g}$ has two roots. The root below one is locally stable for constant $p$, while the root above one is unstable, because the drift derivative is $-p(1-g)e^{-g}$. These approximations explain a low-backlog operating region and a congestion threshold; they do not imply a stationary law for the infinite-population chain.

Indeed, for fixed $p>0$, the exact success probability $S(b)$ tends to zero as $b\to \infty$, so the exact drift tends to $\eta >0$. One can prove instability, rather than relying only on this positive drift. Fix $\theta >0$ and use $V(b)=e^{-\theta b}$. Since $D_t$ is zero or one,The first term is strictly less than one and the second tends to zero. Hence $V(B_{t\wedge \tau })$ is a nonnegative supermartingale outside a sufficiently large finite set, where $\tau$ is the first entrance into that set, say $\{0,\dots ,b_0\}$. The optional sampling theorem for a supermartingale, first at bounded stopping times, givesThis is an exponential-supermartingale escape bound. The chain is irreducible: a no-arrival slot with exactly one old retry can reduce any positive state by one, and Poisson arrivals can reach arbitrarily high states. Therefore the escape probability proves transience and excludes a positive recurrent Markov chain, for every $\eta >0$ and fixed $0<p<1$. A locally stable fluid operating point can consequently coexist with eventual stochastic congestion. At $p=1$, once at least two packets are backlogged, they collide forever, so constant unit retry probability also fails.

A state-dependent retry rule removes this fixed-$p$ congestion mechanism. As an ideal benchmark with exact backlog information and known arrival intensity $0<\eta <e^{-1}$, useThis is backlog-aware ALOHA with arrival-adjusted attempt probabilities. Its total attempt intensity approaches one: the mean old-attempt count is $1-\eta$ and the new-attempt count has mean $\eta$. Substitution in the exact success formula yieldsThus the drift tends to $\eta -e^{-1}<0$. For the Lyapunov function $L(b)=b$, the drift is bounded above by a negative constant outside a finite set, and the expected one-step backlog is finite at every state. Foster theorem therefore gives positive recurrence. This proves a genuine stochastic stability result for this specified, informed controller. Real transmitters generally observe feedback rather than the exact backlog; estimating the backlog and using a probability of order its reciprocal motivates adaptive ALOHA, but an estimate's dynamics must be included in the state and analyzed before claiming the same stability result.

A different nonconstant rule uses a packet's own collision history. In geometric-attempt exponential backoff, a packet at stage $k$ attempts with probability $p_k=p_0{2}^{-k}$, where $0<p_0<1$. A collision advances every attempted packet by one stage, a success removes its packet, and new arrivals enter stage zero. For definiteness, in this version arrivals join at the end of a slot and first become eligible in the next slot. The full Markov chain state is the sequence $(N_0,N_1,\dots )$ of stage populations; the total backlog alone is insufficient. Conditional on that state,These formulas follow from independent attempts and selecting which one packet succeeds. They reduce approximately to $S\simeq G{e}^{-G}$ for many small probabilities with $G={\sum }_k{N}_k{p}_k$. The retry probabilities decrease after failure, preventing repeated aggressive attempts by the same packets. Binary exponential backoff instead chooses uniform random counters from expanding finite windows; that counter model requires residual counters as well as collision stages in its state and is not identical to geometric waiting.

Backoff also exposes a distinction between eventual delivery and acceptable delay. In the simplifying model where each attempt independently fails with a fixed probability $q<1$, the probability of reaching stage $k$ is $q^k$ and its mean waiting time is $1/p_k=2^k/p_0$. The mean delay under independent exponential-backoff failures is thereforeAlthough a packet succeeds almost surely whenever $q<1$, its mean delay can be infinite. In an actual random access network, failures are correlated with the other stage populations, so this fixed-$q$ calculation is a diagnostic approximation, not a proof of network stability. These models show why random-access analysis must track the retry rule, feedback information and full state, and assess throughput, stability and delay separately.

Let $R_s$ be the routes serving source-sink pair $s$. The source-sink route incidence matrix and link-route incidence matrix areThus $Hx=f$ fixes the demands, and $y=Ax$ gives link throughputs. Assume a finite route set with at least one route for each positive demand. A Wardrop equilibrium is a feasible flow for which every used route has minimum delay among the routes for its source-sink pair. Writingthis means that, for each $s$, there is a number ${\lambda }_s$ with $c_r(x)\ge {\lambda }_s$ for $r\in R_s$, with equality whenever $x_r>0$. No individual user can reduce its delay by switching routes while treating the aggregate throughputs as fixed.

The feasible set $K=\{x\ge 0:Hx=f\}$ is a nonempty compact convex set: within each source-sink pair its route flows lie in a simplex of total $f_s$. The Beckmann potentialis continuous and convex, and has $\partial \Phi /\partial x_r=c_r(x)$. It therefore attains a minimum on $K$. For a differentiable convex function, $x$ minimizes $\Phi$ exactly whenIndeed necessity follows by differentiating along the feasible segment from $x$ to $z$, and sufficiency follows from the supporting-tangent inequality. This condition is equivalent to Wardrop equilibrium. Necessity of the route condition follows by moving a small amount of positive flow from a used route to any other route of the same pair. Conversely, under the route condition,because the terms involving $x_r$ vanish and both flows have the same pair totals. This proves both existence and the claimed convex optimization characterization, with $y=Ax$.

Since each $D_j$ is strictly increasing, its primitive is strictly convex. Thus ${\sum }_j{\int }_0^{y_j}{D}_j(u)du$ is strictly convex in $y$. If two minimizing flows had different link throughputs, their midpoint would have strictly smaller potential. Hence the equilibrium link throughputs are unique.

The route flows need not be unique. Consider one unit of demand through two successive stages, each with two parallel links, labelled $a,b$ in the first stage and $c,d$ in the second. The four routes are $ac,ad,bc,bd$, and all link delays are $D_j(u)=u$. For any $0\le t\le 1/2$, chooseEvery link then carries $1/2$ and every route has delay one, so each vector is a Wardrop equilibrium. They all produce the same link throughputs but give distinct route decompositions.

For the toll construction, put $F={\sum }_s{f}_s>0$. The total delay is $L(x)={\sum }_j{y}_j{D}_j(y_j)$ and the average delay is $L(x)/F$, so they have the same minimizers. Compactness of $K$ gives a global minimizer $x^{\ast }$, with $y^{\ast }=A{x}^{\ast }$. Its differentiable objective satisfies the necessary route-flow inequalityThis inequality is necessary even when total delay is not convex, since it follows from the right derivative along each feasible segment.

Use optimal-flow calibrated congestion tolling:Here $(v{)}_{+}=\max (v,0)$. The toll is nonnegative, continuously differentiable and nondecreasing, because $D_j^{\prime }\ge 0$. The perceived cost ${\hat{D}}_j(u)=D_j(u)+T_j(u)$ is strictly increasing. At $y_j^{\ast }$ it equals $D_j(y_j^{\ast })+y_j^{\ast }{D}_j^{\prime }(y_j^{\ast })$, so the displayed necessary inequality makes $x^{\ast }$ a Wardrop equilibrium for these perceived costs, by the preceding Beckmann potential argument. Their strictly increasing costs give unique equilibrium link throughputs. Therefore every tolled equilibrium has link loads $y^{\ast }$ and minimizes average delay. Constant tolls $T_j(u)=y_j^{\ast }{D}_j^{\prime }(y_j^{\ast })$ also suffice; the added positive-part term makes them genuinely traffic-dependent without moving the optimum. Zero total demand is the trivial empty-flow case.

The usual marginal external cost toll $T_j(u)=u{D}_j^{\prime }(u)$ makes its Beckmann potential equal $L$, but concluding that all its equilibria minimize $L$ requires convexity of $L$. Strict increase of delays alone does not supply this. For example, on two parallel links with $D(u)=1-e^{-u}$ and demand six, the equal split $(3,3)$ is an equilibrium under marginal-cost tolls, while its total delay $6(1-e^{-3})$ exceeds $4(1-e^{-4})+2(1-e^{-2})$, the delay at $(4,2)$. The calibrated construction avoids adding a hypothesis absent from the printed question.

Let $R_s$ be the finite nonempty set of routes for source-sink pair $s$, with fixed nonnegative demand $f_s$. A Wardrop equilibrium is a feasible route-flow vector such that every route carrying positive flow has minimum total delay among the routes for its pair. Ifthis means that, for each $s$, some ${\lambda }_s$ satisfies $c_r(y)\ge {\lambda }_s$ for $r\in R_s$, with equality whenever $x_r>0$.

The link-route incidence matrix has $A_{jr}=1$ when route $r$ uses link $j$ and zero otherwise, or the traversal multiplicity if repeated traversals are permitted. The source-sink route incidence matrix has $H_{sr}=1$ when route $r$ serves pair $s$ and zero otherwise. Thus $Ax=y$ gives link throughputs, and $Hx=f$ gives the fixed demands.

The feasible route-flow set is a product of finite simplexes, hence nonempty and both a compact set and a convex set. The Beckmann potentialis continuous and convex, so it attains a minimum. Its route derivative is ${\partial }_r\Phi =c_r(Ax)$. At a minimum, moving a small amount of flow from any used route to any other route for the same pair cannot decrease the potential. Hence every used route has minimum route delay, exactly the Wardrop equilibrium condition. Conversely, at a Wardrop equilibrium $x$, for any feasible $\tilde{x}$,because the used flow has cost ${\lambda }_s$ and competing routes cost at least ${\lambda }_s$. The first-order inequality for a convex function makes $x$ a global minimum. This proves both existence and the specified optimization characterization.

Since each $D_j$ is strictly increasing, its primitive is a strictly convex function. Therefore the objective is strictly convex as a function of link loads $y$, and the equilibrium throughputs $y$ are unique. The mapping $x\mapsto Ax$ need not be injective on $Hx=f$, so route flows need not be unique.

For a concrete route-flow nonuniqueness at a Wardrop equilibrium example, use one unit-demand pair with two successive stages, each containing two parallel links. There are four routes, indexed by their two link choices. Give every link delay $D(u)=u$. For every $0\le t\le 1/2$,produces load $1/2$ on all four links. Every route has delay one, so each vector is a Wardrop equilibrium with the same unique link loads.

To implement minimum average delay, minimize the total delayThe average differs only by the fixed total demand ${\sum }_s{f}_s$, provided it is positive. Choose any global minimizer $x^{\ast }$, which exists by compactness, and write $y^{\ast }=A{x}^{\ast }$. Its first-order route-exchange conditions are the Wardrop equilibrium conditions for marginal link costsA genuinely traffic-dependent choice guaranteed under exactly the printed hypotheses is the calibrated toll functionHere $v_{+}=\max (v,0)$. The calibrated base charges are nonnegative because differentiable increasing delays have nonnegative derivatives, and the added penalties are nonnegative and nondecreasing in $u$. The perceived link costs $D_j(u)+T_j(u)$ remain strictly increasing, and at $y^{\ast }$ they equal $m_j^{\ast }$. Hence $x^{\ast }$ is a tolled Wardrop equilibrium. The same strictly convex Beckmann potential argument makes all its equilibrium link loads equal to $y^{\ast }$; every tolled equilibrium therefore has the globally minimum average delay. This is optimal-flow calibrated congestion tolling.

The familiar marginal external cost toll is $T_j(u)=u{D}_j^{\prime }(u)$, whose perceived-cost primitive is exactly $u{D}_j(u)$. It implements the optimum directly when the total-delay objective is convex, for example when each $u{D}_j(u)$ is convex. That extra hypothesis does not follow from the printed strict increase of $D_j$: for two identical parallel links with $D(u)=1-e^{-u}$ and total demand six, equal loads of three form a tolled Wardrop equilibrium, but the second derivative of $uD(u)$ at three is $-e^{-3}<0$, so an unequal nearby split lowers total delay. The calibrated traffic-dependent toll above establishes the requested existence without silently assuming this additional convexity.

Use an ideal carrier-sense multiple access scheme on the interference graph. An active station finishes its transmission after an independent unit-rate exponential distribution waiting time. An inactive station has an independent attempt clock with an exponential distribution of rate $e^{{\theta }_r}$; an attempt succeeds only when all its neighbors are inactive. Attempts that are blocked do not change the state. Thus, on the independent sets represented by $S$, the continuous-time Markov chain has transition ratesThe empty independent set can be reached by successive deactivations, and any other independent set can be reached from it by successive activations. Hence this finite chain is an irreducible Markov chain. The weight $a_{\theta }(n)=e^{\theta \cdot n}$ satisfiesBy detailed balance for a continuous-time Markov chain, its unique stationary law isThis is a finite exponential family. Its natural parameter of an exponential family is $\theta$ and its mean parameter of an exponential family is the vector of active fractions.

The throughput region of an interference graph is exactly $\Lambda =\mathrm{conv}S$. To see the possibly less immediate inclusion, suppose a random feasible schedule has mean $v\ge \lambda$. Retain each of its active vertices $r$ independently with probability ${\lambda }_r/v_r$, interpreting zero coordinates as always deleted. A subset of an independent set remains an independent set; the thinned schedule has mean exactly $\lambda$. Thus $\lambda$ lies in the convex hull of $S$. The opposite inclusion follows from the definition using equality. Moreover $0,e_1,\dots ,e_R\in S$, so this convex hull has full dimension.

Now choose $\epsilon >0$ such that $\mu =\lambda +\epsilon 1$ remains in the interior of $\mathrm{conv}S$. Use interior moment matching in a finite exponential family. Consider the convex functionThere is a ball of radius $\delta >0$ around $\mu$ contained in $\mathrm{conv}S$. Maximizing a linear functional over the convex hull is the same as maximizing over its generating set, so, for every $\theta$,The last inequality uses the point $\mu +\delta \theta /\Vert \theta \Vert$ when $\theta \ne 0$. Hence $F$ is a coercive function and has a finite minimizer ${\theta }^{\ast }$. Differentiating the finite normalizing sum givesThis covariance matrix is a positive-definite matrix: a linear functional constant on all states of positive weight must be constant on $0,e_1,\dots ,e_R$, so its coefficients vanish. Thus $F$ is a strictly convex function; its minimizer is unique. At that minimizer the desired strict service margins areFor a backlogged station that transmits at unit speed whenever active, the long-run throughput is ${\mathbb{E}}_{\theta }[n_r]$, by the ergodic theorem for a finite continuous-time Markov chain. Therefore the ideal carrier-sense multiple access scheme can supply a strict service margin for every arrival vector in the interior of the throughput region of an interference graph. The local attempt rates can realize the whole interior capacity region in this sense. Boundary points may require parameters tending to infinity, and the argument gives no uniform delay or mixing-time bound near the boundary.

Strictly increasing link delays make Wardrop equilibrium link throughputs unique, but route decompositions of those throughputs can differ. With unit demand through two successive stages of two parallel links each and link delay $D(u)=u$, the four-route vectors $(t,1/2-t,1/2-t,t)$ for $0\le t\le 1/2$ all induce link loads $1/2$. All routes then have equal delay one.