Dynamic Pricing

$$ \newcommand{\R}{\mathbb{R}} \newcommand{\N}{\mathbb{N}} \newcommand{\E}{\mathbb{E}} \newcommand{\Csmooth}{\bar{C}} \newcommand{\Craw}{C} \newcommand{\tasktype}{\tau} \newcommand{\bps}{\mathrm{BPS}} $$

Dynamic Pricing Mechanism

BPE’s backpressure allocation determines who receives payment; we now formalize the complementary question of how much each unit of service costs. We introduce a dynamic pricing curve that creates economic backpressure: as queue load builds at a sink, the per-unit price rises, naturally throttling demand before overflow buffers are needed.

Definition (Queue-Length Price)

For task type \(\tasktype\) and sink \(k\) at time \(t\), the per-unit price is: $$ \begin{equation} \label{eq:price} p(\tasktype, k, t) = \beta_\tasktype(t) \cdot \left(1 + \gamma \cdot \frac{Q(\tasktype, k, t)}{\Csmooth(k, t, \tasktype)}\right) \end{equation} $$ where \(\beta_\tasktype(t) > 0\) is the base fee for task type \(\tasktype\), \(\gamma > 0\) is the price sensitivity parameter, \(Q(\tasktype, k, t) \geq 0\) is the current queue load reported by sink \(k\), and \(\Csmooth(k, t, \tasktype)\) is the EWMA-smoothed capacity from sec:ewma.

When a sink has zero queue load, the price reduces to the base fee \(\beta_\tasktype\). As \(Q / \Csmooth \to 1\) (queue approaches capacity), the price doubles. When \(Q > \Csmooth\) (overloaded), the price rises further, discouraging additional demand.

Base fee adjustment.

The base fee \(\beta_\tasktype\) adjusts per epoch following an EIP-1559-style mechanism (Roughgarden, 2021). Let \(D(\tasktype, t)\) denote aggregate demand (total flow rate from sources) and \(C_{\text{total}}(\tasktype, t) = \sum_k \Csmooth(k, t, \tasktype)\) be aggregate capacity. At each epoch boundary:

$$ \begin{equation} \label{eq:basefee} \beta_\tasktype(t+1) = \begin{cases} \beta_\tasktype(t) \cdot (1 + \delta) & \text{if } D(\tasktype, t) > C_{\text{total}}(\tasktype, t), \ \beta_\tasktype(t) \cdot (1 - \delta) & \text{otherwise}, \end{cases} \end{equation} $$ where \(\delta = 0.125\) (12.5%), matching the maximum per-block adjustment rate of EIP-1559. A floor \(\beta_{\min}\) prevents the base fee from collapsing to zero during sustained under-utilization.

Proposition (Price Equilibrium)

Under the adjustment rule Eq. (Base Fee) with price-sensitive demand \(D(\tasktype, \beta) = D_0 / \beta\) (unit-elastic), there exists a unique equilibrium base fee: $$ \begin{equation} \beta^* = \frac{D_0}{C_{\text{total}}(\tasktype)} \end{equation} $$ at which \(D(\tasktype, \beta^*) = C_{\text{total}}(\tasktype)\).

Proof

Proof. At equilibrium, the adjustment rule Eq. (Base Fee) is stationary, requiring \(D(\tasktype, \beta^*) = C_{\text{total}}\). Substituting the demand function: \(D_0 / \beta^* = C_{\text{total}}\), yielding \(\beta^* = D_0 / C_{\text{total}}\). Uniqueness follows from strict monotonicity of \(D(\cdot)\) in \(\beta\). Stability follows because \(\beta < \beta^*\) implies excess demand, triggering \(\beta \uparrow\), and \(\beta > \beta^*\) implies excess capacity, triggering \(\beta \downarrow\). ◻

Connection to Kelly shadow prices.

Proposition (Price Equilibrium) recovers a classical result from network pricing theory. Kelly (Kelly et al., 1998) showed that the Lagrange multiplier on each link’s capacity constraint in the proportional fairness optimization emerges as a per-unit price. In BPE, the equilibrium base fee \(\beta^*\) is precisely this shadow price for the aggregate capacity constraint. The queue-length surcharge \(\gamma \cdot Q/\Csmooth\) in Eq. (Price) refines this by providing per-sink price differentiation: sinks with shorter queues offer lower prices, attracting more demand, which is exactly the routing signal that a price-taking source should follow.

Proposition (Routing Equivalence)

A cost-minimizing source facing prices Eq. (Price) across sinks routes flow to the sink with the lowest price. At equilibrium, source flow distributes such that prices equalize across sinks with available capacity: $$ \begin{equation} Q(\tasktype, k, t) / \Csmooth(k, t, \tasktype) = Q(\tasktype, j, t) / \Csmooth(j, t, \tasktype) \quad \forall\, k, j \in K_\tasktype \end{equation} $$ i.e., all active sinks operate at the same utilization ratio.

Proof

Proof. If sink \(k\) has a lower utilization ratio \(Q_k/\Csmooth_k < Q_j/\Csmooth_j\), then by Eq. (Price), \(p(\tasktype, k, t) < p(\tasktype, j, t)\). A cost-minimizing source strictly prefers \(k\), shifting demand until utilization ratios equalize. At this point, no unilateral deviation reduces cost, establishing a Nash equilibrium in routing. ◻

Economic backpressure.

Traditional backpressure routing uses queue differentials as a signal to route traffic away from congested links (Tassiulas & Ephremides, 1992). Our pricing mechanism achieves the same effect through economic incentives: congested sinks become expensive, and rational sources route elsewhere. The key advantage is that pricing operates without centralized coordination—each source independently queries per-sink prices and routes to minimize cost, yet the aggregate effect is optimal load balancing.