Minimizing Fees While Maximizing Success Probability
Modern payment networks — from the Bitcoin Lightning Network to interbank settlement systems — rarely move funds through a single direct connection. Instead, a payment hops across a chain of intermediaries, each charging a fee and each carrying a risk that the hop fails (insufficient liquidity, timeout, congestion). Choosing a route therefore isn’t a single-objective shortest-path problem — it’s a multi-objective optimization problem: minimize the total fee and maximize the probability that the whole multi-hop payment actually goes through.
These two goals conflict. The cheapest route often passes through low-capacity channels that are more likely to fail under load, while the most reliable route often goes through well-funded but expensive intermediaries. In this article, we formalize this trade-off mathematically, build a concrete example network, and solve it in Python — first with a straightforward brute-force approach, then with a scalarized shortest-path algorithm that scales to much larger networks.
Problem Formulation
Model the payment network as a directed graph $G = (V, E)$. Each edge (channel) $(i,j) \in E$ has:
- a base fee $b_{ij}$ and a proportional fee rate $r_{ij}$
- a capacity $c_{ij}$
For a payment amount $x$, the fee charged by a single hop is:
$$
f_{ij}(x) = b_{ij} + r_{ij} \cdot x
$$
For a path $P = (v_0, v_1, \dots, v_k)$, the total fee is additive:
$$
F(P, x) = \sum_{(i,j)\in P} f_{ij}(x)
$$
For the success probability of a hop, we use the standard “uniform balance” approximation from Lightning Network routing research: if a channel’s capacity is $c_{ij}$ and we don’t know how it’s split between the two parties, the probability that it can forward $x$ is approximately linear in the remaining capacity:
$$
p_{ij}(x) = \begin{cases} 1 - \dfrac{x}{c_{ij}} & x < c_{ij} \ 0 & x \ge c_{ij} \end{cases}
$$
Since each hop must succeed independently for the payment to complete, the probability of success along the whole path is multiplicative:
$$
\Pr[\text{success}](P, x) = \prod_{(i,j)\in P} p_{ij}(x)
$$
The multi-objective problem is then:
$$
\min_P F(P, x) \quad \text{and} \quad \max_P \Pr[\text{success}](P, x)
$$
A path $P_1$ Pareto-dominates $P_2$ if it is at least as good in both objectives and strictly better in at least one:
The set of non-dominated paths forms the Pareto frontier — the set of “reasonable” routing choices, from cheapest-but-riskiest to safest-but-priciest.
The key trick: turning a product into a sum
Multiplicative objectives are awkward for shortest-path algorithms, which are built around additive edge weights. Taking the negative logarithm fixes this:
$$
-\ln \Pr[\text{success}](P, x) = \sum_{(i,j)\in P} -\ln p_{ij}(x)
$$
Now both objectives are sums over edges, so we can combine them into a single scalarized edge weight and run ordinary Dijkstra:
Sweeping $\alpha$ from 0 (pure reliability) to 1 (pure cost) traces out an approximation of the Pareto frontier using only shortest-path calls — no path enumeration required.
Example Network
We’ll use an 8-node payment network A → H, structured in three intermediate layers (B,C,D then E,F,G), each channel defined by a base fee, a proportional rate, and a capacity. The payment amount is fixed at 50,000 sat for the main example, and later swept across a wider range.
Full Python Implementation
The code below covers: network construction, the brute-force Pareto search (useful for small networks and for validating results), the fast scalarized-Dijkstra sweep (the version you’d actually use on a large network), and all visualizations, including a 3D trade-off surface.
1 | import networkx as nx |
Code Walkthrough
Section 1 — Network construction. build_payment_network() creates a directed graph with 8 nodes arranged in a layered structure (A → {B,C,D} → {E,F,G} → H). Each edge carries a base_fee, rate, and capacity, mirroring how real payment channels are parameterized.
Section 2 — Objective functions. edge_fee implements $f_{ij}(x) = b_{ij} + r_{ij}x$, and edge_prob implements the linear success-probability model $p_{ij}(x) = 1 - x/c_{ij}$. path_fee sums fees across a path; path_prob multiplies probabilities across a path — directly mirroring the math above.
Section 3 — Brute-force Pareto search. nx.all_simple_paths enumerates every simple path from A to H up to a hop-count cutoff. For each one we compute fee and probability, discard infeasible paths (probability 0, meaning some edge’s capacity is exceeded), and then run pareto_front, which does a pairwise dominance check — an $O(n^2)$ comparison over the candidate set — to isolate the non-dominated routes. This approach is exact and easy to reason about, but the number of simple paths in a graph can grow exponentially with the number of nodes and edges, so it only remains practical for small networks (a few dozen nodes at most).
Section 4 — Scalarized Dijkstra. This is the scalable version. For a given weight $\alpha$, scalarized_shortest_path builds a temporary graph where every edge’s weight is the combined cost $C_\alpha$ described earlier (normalized fee term plus normalized $-\ln p$ term), then calls a single ordinary nx.dijkstra_path. Because Dijkstra’s algorithm runs in $O((V+E)\log V)$, sweeping $\alpha$ across, say, 41 values costs only 41 shortest-path computations — regardless of how many possible paths exist in the network. fast_pareto handles the normalization: it computes a fee reference scale (from the cheapest single-objective path) and a probability reference scale (from the best achievable probability), so that the fee and reliability terms are comparable in magnitude before being combined.
Section 5 — 3D sweep. We extend the same scalarized-Dijkstra machinery across a grid of payment amounts and $\alpha$ values, recording the achieved probability and fee at every combination. This lets us see how the trade-off itself shifts as the payment size grows — larger payments consume more of each channel’s capacity, so achievable reliability drops even for a “reliability-first” ($\alpha=0$) route.
Section 6 — Visualization, covered in detail below.
Why the Scalarized Version Matters (Performance)
On this 8-node demo graph, both approaches run in milliseconds — the timing prints exist mainly to make the comparison visible. But the important point is algorithmic complexity, not wall-clock time on a toy example. all_simple_paths can enumerate a number of paths that grows combinatorially with graph density; on a payment network with thousands of nodes (realistic for something like the Lightning Network), brute-force enumeration becomes infeasible. The scalarized-Dijkstra sweep sidesteps this entirely because it never enumerates paths — it only ever solves single-source shortest-path problems, which remain fast (near-linear in practice with a binary heap) no matter how many possible routes exist. This is precisely why the $-\ln$ transform matters: it’s what allows a multiplicative reliability objective to be folded into a standard additive shortest-path solver.
Visualizing the Results
Figure 1 — Network topology with highlighted routes.
[Brute force] 11 feasible paths evaluated in 0.00046s [Brute force] 1 Pareto-optimal paths found: A -> B -> E -> H fee= 53.00 sat prob=0.7087 [Scalarized Dijkstra] 41 alpha samples in 0.00536s (no path enumeration needed)
This diagram shows the full 8-node network, with each channel labeled by its fee rate (in per-mille) and capacity (in thousands of sat). The three colored paths are the network’s actual Pareto-optimal routes for a 50,000 sat payment: the reddest route is typically the cheapest-but-riskiest option, while the routes further down the legend trade some fee efficiency for higher reliability. Comparing the highlighted paths visually makes it clear why they’re non-dominated — they take different channels with different capacity headroom relative to the payment size.
Figure 2 — Fee vs. success probability trade-off (2D).
Every feasible path in the network appears as a gray dot positioned by its total fee (x-axis) and success probability (y-axis). The red line connects the Pareto-optimal subset, sorted by fee. This is the core deliverable of the whole analysis: any point below-and-left of the red line is strictly worse than some available option, so a routing engine should never choose it. Points on the red line represent genuine trade-offs — a wallet or routing node can pick a point along this frontier depending on how much it values speed/cost versus reliability for a given transaction.
Figure 3 — 3D trade-off surfaces (amount × α × outcome).
These two 3D surfaces share the same $(x, y)$ grid — payment amount on one axis, the scalarization weight $\alpha$ on the other — but plot different outcomes on the z-axis. The left surface shows the achieved success probability of the optimal route found at each (amount, α) combination; notice how it slopes downward as amount increases (larger payments strain channel capacity more) and rises as $\alpha \to 0$ (more weight on reliability). The right surface shows the corresponding achieved fee, which generally rises with both amount (proportional fees scale with payment size) and $\alpha$ (more weight on cost pushes the optimizer toward cheaper, less reliable channels). Reading the two surfaces together at a fixed amount lets you see exactly how much probability you’re giving up for each unit of fee saved — the volumetric equivalent of the 2D Pareto frontier, now shown across the full range of payment sizes.
Takeaways
Multi-hop payment routing is fundamentally a two-objective problem, and treating it as a single shortest-path search (minimizing fee alone, as many naive implementations do) silently discards reliability information that matters just as much to the end user. The $-\ln$ transform is the crucial piece of machinery here: it converts a multiplicative reliability objective into an additive one, which means a well-understood, highly scalable algorithm (Dijkstra) can be reused to trace out an entire Pareto frontier by simply sweeping a single scalar weight — no combinatorial path enumeration required. This pattern generalizes well beyond payment channels to any routing problem where you’re balancing a summable cost against a multiplicative reliability or survival probability.
