# Duality in branched transport and urban planning

Julius Lohmann Bernhard Schmitzer Benedikt Wirth11footnotemark: 1 Institute
for Numerical and Applied Mathematics, University of Münster, Einsteinstraße
62, 48149 Münster<EMAIL_ADDRESS>for Computer
Science, University of Göttingen, Goldschmidtstraße 7, 37077 Göttingen,
Germany. schmitzer<EMAIL_ADDRESS>
###### Abstract

In recent work [LSW22, Theorem 1.3.4] we have shown the equivalence of the
widely used nonconvex (generalized) branched transport problem with a shape
optimization problem of a street or railroad network, known as (generalized)
urban planning problem. The argument was solely based on an explicit
construction and characterization of competitors. In the current article we
instead analyse the dual perspective associated with both problems. In more
detail, the shape optimization problem involves the Wasserstein distance
between two measures with respect to a metric depending on the street network.
We show a Kantorovich–Rubinstein formula for Wasserstein distances on such
street networks under mild assumptions. Further, we provide a Beckmann
formulation for such Wasserstein distances under assumptions which generalize
our previous result in [LSW22]. As an application we then give an alternative,
duality-based proof of the equivalence of both problems under a growth
condition on the transportation cost, which reveals that urban planning and
branched transport can both be viewed as two bilinearly coupled convex
optimization problems.

Keywords: branched transport, Fenchel duality, geometric measure theory,
optimal transport, rectifiable networks, urban planning, Wasserstein distance

###### Contents

  1. 1 Introduction
    1. 1.1 Generalized urban planning
    2. 1.2 Generalized branched transport
    3. 1.3 Summary of results
    4. 1.4 Notation and definitions
  2. 2 Beckmann formulation of $\boldsymbol{W_{d_{S,a,b}}}$ using duality
    1. 2.1 Kantorovich–Rubinstein duality in urban planning
  3. 3 Urban planning formulation of branched transport using duality
    1. 3.1 Duality for the total network transportation cost
    2. 3.2 Branched transport as street network optimization
  4. 4 Acknowledgements

##  1 Introduction

Classical optimal transport takes two probability measures
$\mu_{+},\mu_{-}\in\mathcal{P}(\mathcal{C})$ on some compact domain
$\mathcal{C}\subset\mathbb{R}^{n}$ and computes the optimal assignment $\pi$
between them, where $\pi$ is a probability measure on
$\mathcal{C}\times\mathcal{C}$ with the interpretation that $\pi$ at $(x,y)$
represents the mass transported from $x$ to $y$. Optimality is here assessed
with respect to the cost
$\int_{\mathcal{C}\times\mathcal{C}}c(x,y)\,\mathrm{d}\pi(x,y)$ for some given
transportation cost $c$. The special case $c(x,y)=|x-y|$ yields the so-called
Wasserstein transport, inducing the Wasserstein-1 distance
$W_{1}(\mu_{+},\mu_{-})$ between both measures. An important reformulation of
the Wasserstein transport is the so-called Beckmann formulation, obtained by
dualizing the problem twice as we quickly recapitulate (rather formally)
below: Introducing Lagrange multipliers $\phi,\psi$ for the constraint of
$\pi$ being an assignment between $\mu_{+}$ and $\mu_{-}$, one obtains

$\displaystyle W_{1}(\mu_{+},\mu_{-})$
$\displaystyle=\inf_{\pi\in\mathcal{P}(\mathcal{C})}\left\\{\int_{\mathcal{C}\times\mathcal{C}}|x-y|\,\mathrm{d}\pi(x,y)\,\middle|\,\pi(\cdot,\mathcal{C})=\mu_{+},\pi(\mathcal{C},\cdot)=\mu_{-}\right\\}$
$\displaystyle=\inf_{\pi\in\mathcal{P}(\mathcal{C})}\sup_{\phi,\psi\in
C(\mathcal{C})}\int_{\mathcal{C}\times\mathcal{C}}|x-y|\,\mathrm{d}\pi(x,y)+\int_{\mathcal{C}}\phi(x)\,\mathrm{d}(\mu_{+}(x)-\pi(x,\mathcal{C}))+\int_{\mathcal{C}}\psi(y)\,\mathrm{d}(\mu_{-}(y)-\pi(\mathcal{C},y)).$
By classical Lagrange or Fenchel–Rockafellar duality one can swap $\inf$ and
$\sup$ and then minimize for $\pi$ to arrive at
$\displaystyle=\sup\left\\{\int_{\mathcal{C}}\phi\,\mathrm{d}\mu_{+}+\int_{\mathcal{C}}\psi\,\mathrm{d}\mu_{-}\,\middle|\,\phi,\psi\in
C(\mathcal{C}),\,\phi(x)+\psi(y)\leq|x-y|\,\forall
x,y\in\mathcal{C}\right\\}.$ Now it is not difficult to show that in the
optimum $\psi$ has to equal $-\phi$ so that the above turns into the so-called
Kantorovich–Rubinstein formula
$\displaystyle=\sup\left\\{\int_{\mathcal{C}}\phi\,\mathrm{d}(\mu_{+}-\mu_{-})\,\middle|\,\phi\in
C^{0,1}(\mathcal{C})\text{ with }|\nabla\phi|\leq 1\text{ a.e. in
}\mathcal{C}\right\\},$ where we exploited that the constraint turns into
$1$-Lipschitz continuity of $\phi$, which can equivalently be expressed by
constraining $\nabla\phi$. Introducing a vector-valued Radon measure
$\mathcal{F}\in\mathcal{M}^{n}(\mathcal{C})$ on $\mathcal{C}$ as Lagrange
multiplier for the new constraint we get $\displaystyle=\sup_{\phi\in
C(\mathcal{C})}\inf_{\mathcal{F}\in\mathcal{M}^{n}(\mathcal{C})}\int_{\mathcal{C}}\phi\,\mathrm{d}(\mu_{+}-\mu_{-})+\int_{\mathcal{C}}\nabla\phi\cdot\mathrm{d}\mathcal{F}+|\mathcal{F}|(\mathcal{C}),$
where $|\mathcal{F}|(\mathcal{C})$ denotes the total variation of
$\mathcal{F}$. An integration by parts now moves the derivative from $\phi$
onto $\mathcal{F}$. Furthermore, again by Lagrange or Fenchel–Rockafellar
duality we can swap $\inf$ and $\sup$ and then minimize explicitly over
$\phi$, which finally yields the Beckmann formulation of the Wasserstein-1
distance,
$\displaystyle=\inf\left\\{|\mathcal{F}|(\mathcal{C})\,\middle|\,\mathrm{div}(\mathcal{F})=\mu_{+}-\mu_{-}\right\\}.$

In this article we aim to derive the Kantorovich–Rubinstein and the Beckmann
formula for the setting where $c(x,y)$ is replaced by a (pseudo-)metric which
stems from a street network or more generally a countably $1$-rectifiable set
$S\subset\mathcal{C}$ on which the transport is cheaper than on its
complement. These formulations are needed to understand the relation between
the so-called _urban planning_ and _branched transport problem_.

The _urban planning problem_ was proposed by Brancolini and Buttazzo [BB05] as
well as Buttazzo, Pratelli, Solimini and Stepanov [But+09]. It is a shape
optimization problem in which one seeks an optimal street geometry for public
transportation. The cost for a commuter to travel from one position to another
(e. g. from home to work) is descibed using the _urban metric_ , the minimum
travel distance based on the street network. The corresponding objective
functional can be decomposed into the total cost for commuting (a
Wasserstein-1 distance with respect to the urban metric) and for maintenance
(proportional to the total length of the street network). The urban planning
problem and urban metric were generalized in [LSW22]: As an additional
parameter, a _friction coefficient_ was introduced which assigns a different
street quality to different parts of the network. Both the urban metric and
the maintenance cost in the generalized model depend on this friction
coefficient.

The _branched transport problem_ on the other hand is a non-convex and non-
smooth variational problem on Radon measures in which one optimizes over mass
fluxes from a given initial to a final mass distribution. A good introduction
to classical branched transport is given in [BCM09].

In [LSW22] it was shown that the generalized urban planning problem is
equivalent to the branched transport problem with concave _transportation
cost_ , extending a result from [BW16] (equivalence between the classical
urban planning problem and the branched transport problem with a specific
transportation cost). The main step was to prove a Beckmann-type flux
formulation of the Wasserstein-1 distance with respect to the generalized
urban metric. To this end it was assumed that the generalized urban planning
problem has finite cost, which allowed to derive a particular property of the
network (namely, for any $C>0$ smaller than the friction outside the network,
streets with friction smaller than $C$ have finite total length). This
property was used to construct a minimizer for the Beckmann problem from a
minimizer of the Wasserstein distance and vice versa. Without this assumption
an explicit construction of minimizers is not possible since the Beckmann
problem may not admit a minimizer. The main aim of the current work is to
prove the Beckmann formulation using duality arguments (as recapitulated above
for the Euclidean setting) without making use of the assumption. We prove it
for the case of finite friction outside the network, but also show that this
reformulation will stay true under mild assumptions (related to the network
property from above) if the friction outside the network is infinite. We will
first prove a Kantorovich–Rubinstein formula for the Wasserstein distance
(under these mild assumptions) in which the gradients of the Kantorovich
potentials are bounded in terms of the friction coefficient and then apply
Fenchel duality to obtain the Beckmann formulation.

Apart from this result, we will provide a dual representation of the total
network transportation cost induced by a mass flux from the branched transport
problem (it is known that such a flux can be decomposed into a part
concentrated on a network-like set and a diffuse part) under the assumption
that the right derivative of the transportation cost is finite in zero. We
will use this expression and the previously mentioned duality results to give
a short alternative proof of the urban planning formulation of branched
transport under the same assumption on the transportation cost.

In the remainder of this section, we introduce the terminology used in urban
planning and branched transport. Further, we summarize our main results and
list the used notation and definitions. In section 2 we will derive the
Kantorovich–Rubinstein formula for the Wasserstein distance with respect to
the generalized urban metric under mild assumptions on the street network. We
will afterwards use this result to prove the Beckmann formulation under these
mild assumptions or for the case of finite friction outside the network.
Finally, in section 3 we will introduce the friction coefficients as dual
variables in a formula for the total network transportation cost of a mass
flux from branched transport and give an alternative proof of the urban
planning formulation of branched transport under the above-mentioned growth
condition on the transportation cost.

###  1.1 Generalized urban planning

The original urban planning problem was introduced in [BB05, But+09]. We will
directly introduce the generalized setting and refer the reader to [LSW22,
Section 1.2] for a brief description of the relation between classical and
generalized urban planning. We first introduce the set of admissible street
networks.

######  Definition 1.1.1 (Street network, friction coefficient, city).

A street network is a pair $(S,b)$ with

  * •

$S\subset\mathbb{R}^{n}$ countably $1$-rectifiable and Borel measurable,

  * •

$b:S\to[0,\infty)$ lower semicontinuous.

The function $b$ is called friction coefficient. A city is a triple $(S,a,b)$,
where $(S,b)$ is a street network and $a\in[0,\infty]$ satisfies $b\leq a$ on
$S$.

The (friction) coefficients $b$ and $a$ describe the cost for travelling on
and outside the network $S$ ($b$ may vary on $S$ since the street quality may
vary). Note that, in general, offroad movement may be limited through
buildings or the like. However, the results in this article will still hold
true if we exclude finitely many sufficiently regular connected sets in
$\mathbb{R}^{n}\backslash S$. The cost for travelling from $x$ to $y$ is
desribed by the following (pseudo-)metric (in which $\mathcal{H}^{1}$ denotes
the one-dimensional Hausdorff measure).

######  Definition 1.1.2 (Generalized urban metric).

Let $(S,a,b)$ be a city. The associated generalized urban metric is defined as

$d_{S,a,b}(x,y)=\inf_{\gamma}\int_{\gamma([0,1])\cap
S}b\,\mathrm{d}\mathcal{H}^{1}+a\mathcal{H}^{1}(\gamma([0,1])\setminus S),$

where the infimum is taken over Lipschitz paths
$\gamma:[0,1]\to\mathbb{R}^{n}$ with $\gamma(0)=x$ and $\gamma(1)=y$.

Let $\mu_{+}$ and $\mu_{-}$ be probability measures on $\mathbb{R}^{n}$, which
may for example describe the distribution of homes and workplaces. The total
cost for the commuting population is then given by the Wasserstein distance
with respect to $d_{S,a,b}$.

######  Definition 1.1.3 (Wasserstein distance, transport plans).

Let $(S,a,b)$ be a city. The Wasserstein distance between $\mu_{+}$ and
$\mu_{-}$ with respect to $d_{S,a,b}$ is defined as

$W_{d_{S,a,b}}(\mu_{+},\mu_{-})=\inf_{\pi}\int_{\mathbb{R}^{n}\times\mathbb{R}^{n}}d_{S,a,b}\,\mathrm{d}\pi,$

where the infimum is taken over all probability measures $\pi$ on
$\mathbb{R}^{n}\times\mathbb{R}^{n}$ with
$\pi(B\times\mathbb{R}^{n})=\mu_{+}(B)$ and $\pi(\mathbb{R}^{n}\times
B)=\mu_{-}(B)$ for all Borel sets $B\in\mathcal{B}(\mathbb{R}^{n})$. Any such
measure is called a transport plan. The set of transport plans is denoted by
$\Pi(\mu_{+},\mu_{-})$.

The Wasserstein distance is the first term which appears in the cost
functional of the generalized urban planning problem. The second term
corresponds to the total maintenance cost of the street network.

######  Definition 1.1.4 (Maintenance cost).

A maintenance cost is a non-increasing function $c:[0,\infty)\to[0,\infty]$.

The maintenance cost $c\circ b$ has the interpretation of a cost per length
for maintaining a street with friction coefficient $b$.

######  Definition 1.1.5 (Generalized urban planning cost).

Given a maintenance cost $c$, set

$a=\inf c^{-1}(0).$

The generalized urban planning cost of a city $(S,a,b)$ is given by

$\mathcal{U}^{c,\mu_{+},\mu_{-}}[S,b]=W_{d_{S,a,b}}(\mu_{+},\mu_{-})+\int_{S}c(b)\,\mathrm{d}\mathcal{H}^{1},$

and the generalized urban planning problem is the optimization problem

$\inf\left\\{\mathcal{U}^{c,\mu_{+},\mu_{-}}[S,b]\,\middle|\,(S,b)\text{
street network with }b\leq a\text{ on }S\right\\}.$

Note that $c\circ b$ is upper semi-continuous due to the assumptions on $b$
and $c$.

###  1.2 Generalized branched transport

To describe branched transport we use the Eulerian formulation due to Xia
[Xia03], which uses vector-valued Radon measures. Let $\mu_{+}$ and $\mu_{-}$
be probability measures on $\mathbb{R}^{n}$ that describe the initial an final
distribution of mass (or of commuters in the context of urban planning). The
cost to move an amount of mass per unit distance is given by the following
function.

######  Definition 1.2.1 (Transportation cost).

A transportation cost is a non-decreasing concave function
$\tau:[0,\infty)\to[0,\infty)$ with $\tau(0)=0$.

A classical example for a transportation cost is $\tau(m)=m^{\alpha}$ for some
$\alpha\in(0,1)$. The concavity of $\tau$ encodes that the transport gets
cheaper per mass particle if more mass is transported together. To describe
transport along a finite graph we define polyhedral mass fluxes (or
equivalently, finite oriented weighted graphs) between distributions $\mu_{+}$
and $\mu_{-}$ which are concentrated in finitely many points.

######  Definition 1.2.2 (Polyhedral mass flux and branched transport cost).

Assume that $\mu_{+}$ and $\mu_{-}$ are finite sums of weighted Dirac
measures, i. e.,

$\mu_{+}=\sum_{i=1}^{M}f_{i}\delta_{x_{i}}\text{\qquad
and\qquad}\mu_{-}=\sum_{j=1}^{N}g_{j}\delta_{y_{j}},$

where $f_{i},g_{j}\in[0,1]$ satisfy $\sum_{i}f_{i}=\sum_{j}g_{j}=1$ and
$x_{i},y_{j}\in\mathbb{R}^{n}$. A polyhedral mass flux between $\mu_{+}$ and
$\mu_{-}$ is a vector-valued Radon measure
$\mathcal{F}\in\mathcal{M}^{n}(\mathbb{R}^{n})$ which satisfies
$\textup{div}(\mathcal{F})=\mu_{+}-\mu_{-}$ in the distributional sense and
can be written as

$\mathcal{F}=\sum_{e}m_{e}\vec{e}\mathcal{H}^{1}\mathbin{\vrule
height=6.88889pt,depth=0.0pt,width=0.55974pt\vrule
height=0.55974pt,depth=0.0pt,width=5.59721pt}e,$

where the sum is over finitely many edges
$e=x_{e}+[0,1](y_{e}-x_{e})\subset\mathbb{R}^{n}$ with orientation
$\vec{e}=(y_{e}-x_{e})/|y_{e}-x_{e}|$, the coefficients $m_{e}$ are positive
real weights, and $\mathcal{H}^{1}\mathbin{\vrule
height=6.88889pt,depth=0.0pt,width=0.55974pt\vrule
height=0.55974pt,depth=0.0pt,width=5.59721pt}e$ is the restriction of the one-
dimensional Hausdorff measure to $e$. The branched transport cost of
$\mathcal{F}$ with respect to a transportation cost $\tau$ is defined as

$\mathcal{J}^{\tau,\mu_{+},\mu_{-}}[\mathcal{F}]=\sum_{e}\tau(m_{e})\mathcal{H}^{1}(e).$

We use the lower semi-continuous envelope of
$\mathcal{J}^{\tau,\mu_{+},\mu_{-}}$ to get the branched transport cost of a
general vector-valued Radon measure with distributional divergence equal to
$\mu_{+}-\mu_{-}$.

######  Definition 1.2.3 (Mass flux and branched transport cost).

A vector-valued Radon measure $\mathcal{F}\in\mathcal{M}^{n}(\mathbb{R}^{n})$
is called mass flux between the probability measures $\mu_{+}$ and $\mu_{-}$
if there exist two sequences of probability measures $\mu_{+}^{k},\mu_{-}^{k}$
and a sequence of polyhedral mass fluxes $\mathcal{F}_{k}$ with
$\textup{div}(\mathcal{F}_{k})=\mu_{+}^{k}-\mu_{-}^{k}$ such that
$\mathcal{F}_{k}\xrightharpoonup{*}\mathcal{F}$ and
$\mu_{\pm}^{k}\xrightharpoonup{*}\mu_{\pm}$, where $\xrightharpoonup{*}$
indicates the weak-$*$ convergence in duality with continuous functions. We
write
$(\mathcal{F}_{k},\mu_{+}^{k},\mu_{-}^{k})\xrightharpoonup{*}(\mathcal{F},\mu_{+},\mu_{-})$.
If $\mathcal{F}$ is a mass flux, then the branched transport cost of
$\mathcal{F}$ is defined as

$\mathcal{J}^{\tau,\mu_{+},\mu_{-}}[\mathcal{F}]=\inf\left\\{\liminf_{k}\mathcal{J}^{\tau,\mu_{+}^{k},\mu_{-}^{k}}[\mathcal{F}_{k}]\,\bigg{|}\,(\mathcal{F}_{k},\mu_{+}^{k},\mu_{-}^{k})\xrightharpoonup{*}(\mathcal{F},\mu_{+},\mu_{-})\right\\}.$

The corresponding branched transport problem is the optimization problem

$\inf\\{\mathcal{J}^{\tau,\mu_{+},\mu_{-}}[\mathcal{F}]\,|\,\mathcal{F}\in\mathcal{M}^{n}(\mathbb{R}^{n}),\textup{div}(\mathcal{F})=\mu_{+}-\mu_{-}\\}.$

###  1.3 Summary of results

Our main results are

  * •

a Kantorovich–Rubinstein formula for the Wasserstein distance $W_{d_{S,a,b}}$
under mild assumptions on the city $(S,a,b)$ (theorem 1.3.2),

  * •

a Beckmann formula for $W_{d_{S,a,b}}$ under the same assumptions on the city
or $a<\infty$ (theorem 1.3.4),

  * •

a dual formula for a total network transportation cost under the growth
condition $\tau^{\prime}(0)<\infty$ (theorem 1.3.7), and

  * •

a new proof of the equivalence between urban planning and branched transport
for the case $\tau^{\prime}(0)<\infty$ using our duality results (theorem
1.3.8).

Let $\mu_{+},\mu_{-}$ be probability measures on $\mathbb{R}^{n}$ with bounded
supports, contained in $\mathcal{C}=[-1,1]^{n}$ without loss of generality. We
will prove our first main result under the following assumption.

######  Assumption 1.3.1 (Regularity of the city $(S,a,b)$).

The friction coefficient $b$ is bounded away from $0$, and the function which
maps $x\in\mathbb{R}^{n}$ to the friction coefficient at $x$, i.e. $b(x)$ if
$x\in S$, $a$ else, is lower semi-continuous.

The last condition in assumption 1.3.1 is for instance automatically satisfied
if the set $S$ of streets is closed. Note, though, that it is strictly weaker
than requiring closedness of $S$ (which typically is not satisfied for
branched transport networks, see example 1.3.9).

######  Theorem 1.3.2 (Version of the Kantorovich–Rubinstein formula).

Let $(S,a,b)$ be a city such that assumption 1.3.1 is satisfied. Then the
Wasserstein-1 distance between $\mu_{+}$ and $\mu_{-}$ is given by

$W_{d_{S,a,b}}(\mu_{+},\mu_{-})=\sup_{\varphi}\int_{\mathcal{C}}\varphi\,\mathrm{d}(\mu_{+}-\mu_{-}),$

where the supremum is taken over functions $\varphi\in C^{1}(\mathcal{C})$
with $|\nabla\varphi|\leq b$ on $S$ and $|\nabla\varphi|\leq a$ in
$\mathcal{C}\backslash S$.

The work here is to show that one may restrict the supremum to differentiable
functions with the given gradient constraint; for lower regularity
requirements on $\varphi$ it is a standard result.

######  Assumption 1.3.3 (Finite friction outside network).

The cost $a$ for travelling outside the network is finite.

The Beckmann formulation of the Wasserstein distance will actually be true
under assumption 1.3.1 or assumption 1.3.3.

######  Theorem 1.3.4 (Beckmann-type formulation of
$W_{d_{S,a,b}}(\mu_{+},\mu_{-})$).

Let $(S,a,b)$ be a city and suppose that assumption 1.3.1 or assumption 1.3.3
is satisfied. Then we have

$W_{d_{S,a,b}}(\mu_{+},\mu_{-})=B_{S,a,b}(\mu_{+},\mu_{-})\qquad\text{for}\qquad
B_{S,a,b}(\mu_{+},\mu_{-})=\inf_{\xi,\mathcal{F}^{\perp}}\int_{S}b|\xi|\,\mathrm{d}\mathcal{H}^{1}+a|\mathcal{F}^{\perp}|(\mathcal{\mathcal{C}}),$

where the infimum is taken over $\xi\in L^{1}(\mathcal{H}^{1}\mathbin{\vrule
height=6.88889pt,depth=0.0pt,width=0.55974pt\vrule
height=0.55974pt,depth=0.0pt,width=5.59721pt}S;\mathbb{R}^{n})$ and
$\mathcal{F}^{\perp}\in\mathcal{M}^{n}(\mathcal{C})$ with
$\mathcal{F}^{\perp}\mathbin{\vrule
height=6.88889pt,depth=0.0pt,width=0.55974pt\vrule
height=0.55974pt,depth=0.0pt,width=5.59721pt}S=0$ and
$\textup{div}(\xi\mathcal{H}^{1}\mathbin{\vrule
height=6.88889pt,depth=0.0pt,width=0.55974pt\vrule
height=0.55974pt,depth=0.0pt,width=5.59721pt}S+\mathcal{F}^{\perp})=\mu_{+}-\mu_{-}$.

It is unclear whether the result even stays true if one drops all assumptions
– we expect this to be the case, but the method of proof via duality does not
allow to draw such conclusions. A brief summary of the Beckmann formulation of
the Wasserstein distance with respect to $d_{S,a,b}$ is given in figure 1.

$a$ | current article | [LSW22]
---|---|---
finite  | no assumption | [LSW22, Asm. 1.3.1]
infinite  | assumption 1.3.1 | [LSW22, Asm. 1.3.1]
Figure 1: Summary of the cases for which the Beckmann formulation of the
Wasserstein distance with respect to $d_{S,a,b}$ has been proven. The
requirement in [LSW22, Asm. 1.3.1] is that for every $C\in[0,a)$ we have
$\mathcal{H}^{1}(\\{b\leq C\\})<\infty$. In all four cases a minimizer for
$W_{d_{S,a,b}}(\mu_{+},\mu_{-})$ exists (if the Wasserstein distance is
finite). The same holds true for the Beckmann formulation except for
$a\in(0,\infty]$ with no additional condition (see [LSW22, Exm. 1.3.1]).

The analogue of assumption 1.3.3 in the context of branched transport turns
out to be the following.

######  Assumption 1.3.5 (Growth condition).

The average transportation cost per unit mass $m\mapsto\tau(m)/m$ is bounded,
i. e., $\tau^{\prime}(0)=\lim_{m\searrow 0}\tau(m)/m<\infty$.

The maintenance cost corresponding to a transportation cost for the branched
transport problem is defined via convex conjugation.

######  Definition 1.3.6 (Maintenance cost associated with $\tau$).

Let $\tau:[0,\infty)\to[0,\infty)$ be a transportation cost. We extend $\tau$
to a function on $\mathbb{R}$ via $\tau(m)=-\infty$ for all $m<0$. The
associated maintenance cost is defined by
$\varepsilon(b)=(-\tau)^{*}(-b)=\sup_{m\geq 0}\tau(m)-bm$ for any
$b\in[0,\infty)$.

It can be shown that the branched transport cost of a mass flux
$\mathcal{F}=\xi\mathcal{H}^{1}\mathbin{\vrule
height=6.88889pt,depth=0.0pt,width=0.55974pt\vrule
height=0.55974pt,depth=0.0pt,width=5.59721pt}S+\mathcal{F}^{\perp}$ with
divergence equal to $\mu_{+}-\mu_{-}$ can be decomposed into the total cost
for transportation on the network $S$ and a cost term for the diffuse part
$\mathcal{F}^{\perp}$ (see [BW18, Prop. 2.32] or [LSW22, Lemma 3.1.8]). The
next formula shows that the network cost term can be seen as an optimization
problem over friction coefficients.

######  Theorem 1.3.7 (Dual formula for total network transportation cost).

Assume that $S\subset\mathcal{C}$ is countably $1$-rectifiable and Borel
measurable. Furthermore, let $\xi\in L^{1}(\mathcal{H}^{1}\mathbin{\vrule
height=6.88889pt,depth=0.0pt,width=0.55974pt\vrule
height=0.55974pt,depth=0.0pt,width=5.59721pt}S;\mathbb{R}^{n})$ represent a
mass flux on $S$ and suppose that $\tau$ is a transportation cost which
satisfies assumption 1.3.5. Then we have

$\int_{S}\tau(|\xi|)\,\mathrm{d}\mathcal{H}^{1}=\inf_{b}\int_{S}b|\xi|\,\mathrm{d}\mathcal{H}^{1}+\int_{S}\varepsilon(b)\,\mathrm{d}\mathcal{H}^{1},$

where the infimum is taken over lower semi-continuous functions
$b:S\to[0,\tau^{\prime}(0)]$.

At the end of this article, we will use the previous duality results to
provide an alternative proof of the urban planning formulation of branched
transport under assumption 1.3.5.

######  Theorem 1.3.8 (Bilevel formulation of the branched transport problem
[LSW22, Theorem 1.3.4]).

Let $\tau$ be a transportation cost with associated maintenance cost
$\varepsilon$. Then the branched transport problem can equivalently be written
as urban planning problem,

$\inf_{\mathcal{F}}\mathcal{J}^{\tau,\mu_{+},\mu_{-}}[\mathcal{F}]=\inf_{S,b}\mathcal{U}^{\varepsilon,\mu_{+},\mu_{-}}[S,b],$

where the infima are taken over $\mathcal{F}\in\mathcal{M}^{n}(\mathcal{C})$
with $\textup{div}(\mathcal{F})=\mu_{+}-\mu_{-}$ and street networks $(S,b)$
with $S\subset\mathcal{C}$ and $b\leq a=\tau^{\prime}(0)$ on $S$.

Theorems 1.3.4, 1.3.8 and 1.3.7 reveal the convex duality structure that
connects branched transport with urban planning: Essentially, both problems
can be (formally) written as

$\inf_{S,b,\xi,\mathcal{F}^{\perp}}\int_{S}b|\xi|\,\mathrm{d}\mathcal{H}^{1}+a|\mathcal{F}^{\perp}|(\mathcal{\mathcal{C}})+\int_{S}\varepsilon(b)\,\mathrm{d}\mathcal{H}^{1}+\iota_{\\{\mu_{+}-\mu_{-}\\}}(\textup{div}(\xi\mathcal{H}^{1}\mathbin{\vrule
height=6.88889pt,depth=0.0pt,width=0.55974pt\vrule
height=0.55974pt,depth=0.0pt,width=5.59721pt}S+\mathcal{F}^{\perp}))$

with $a=\sup_{S}b$, which is separately convex in $(\xi,\mathcal{F}^{\perp})$
and in $b$. Eliminating $(\xi,\mathcal{F}^{\perp})$ (by minimizing in those
variables) leads to urban planning, eliminating $(b,a)$ to branched transport.
The nonconvexity of the problem arises from the bilinearity in which
$(|\xi|,|\mathcal{F}^{\perp}|)$ and $(b,a)$ are coupled.

To the end of this section, we briefly discuss assumption 1.3.1 and assumption
1.3.3 with regard to theorem 1.3.2. The conditions in theorem 1.3.2 are sharp
(cf. LABEL:sharp1 and LABEL:sharp2). We believe that the condition that $b$ is
bounded away from zero in theorem 1.3.2 can be dropped under assumption 1.3.3.
We use this condition in the proof of proposition 2.1.1 to get uniformly
bounded lenghts of certain almost optimal paths with respect to $d_{S,a,b}$.
It is possible to relax this condition to the requirement that there exists
some constant $C>0$ such that $\mathcal{H}^{1}(\\{b\leq C\\})<\infty$ (an
implication of [LSW22, Asm. 1.3.1]), but this would make the arguments more
technical. Moreover, we will use the boundedness away from zero in the proof
of theorem 1.3.4 under assumption 1.3.1. For the sake of completeness, we
finally give an example which shows that it is reasonable not to restrict to
closed networks $S$ in the context of branched transport. The requirement that
$b$, extended with value $a$, is lower semi-continuous in $\mathbb{R}^{n}$
from assumption 1.3.1 turns out to be a natural weakening of the requirement
that $S$ is closed.

(a) Polyhedral mass flux.

$v$ (b) Network not closed.

$\alpha 4^{1-\alpha}$$\alpha 8^{1-\alpha}$$\alpha 16^{1-\alpha}$ (c)
Approximate irrigation of a ring.

Figure 2: Sketches for example 1.3.9.

######  Example 1.3.9 (Examples of branched transport networks).

  1. (a)

Clearly, any polyhedral mass flux induces a closed network $S$ of finite
length (figure 2(a)). If $b$ is lower semi-continuous on $S$ with $b\leq
a\in[0,\infty]$, then the extension of $b$ with value $a$ to $\mathbb{R}^{n}$
is automatically lower semi-continuous so that assumption 1.3.1 is fulfilled
as soon as $b$ is bounded away from zero.

  2. (b)

Recall from theorem 1.3.8 that, in the context of branched transport, the
friction coefficient $a$ equals $\tau^{\prime}(0)$, where $\tau$ is some
transportation cost of the branched transport problem. For finite $a$, e. g.
for $\tau(m)=m$ (Wasserstein transport), the network $S$ induced by an optimal
mass flux is not necessarily closed: Let $\mu_{+}=\sum_{i}m_{i}\delta_{x_{i}}$
with $m_{i}\in(0,1]$ be a probability measure concentrated on pairwise
disjoint points $x_{i}\in\mathbb{R}^{n}$ such that $\bigcup_{i}\\{x_{i}\\}$ is
not closed (e. g. the point cloud $(\mathbb{Q}\cap(0,1))^{2}$ in figure 2(b)).
Define $\mu_{-}(B)=\mu_{+}(B-v)$ for some fixed
$v\in\mathbb{R}^{n}\backslash\\{0\\}$. Then an optimal Wasserstein mass flux
is concentrated on the set $S=\bigcup_{i}[x_{i},x_{i}+v]$, which is not
closed. Nevertheless, the induced city satisfies assumption 1.3.1: From
theorem 1.3.7 we see directly that $b\equiv 1$ on $S$ is the right choice so
that the extension to $\mathbb{R}^{n}$ with value $a=\tau^{\prime}(0)=1$ is
lower semi-continuous.

  3. (c)

For an example with $a=\infty$ we can choose $\mu_{+}=\delta_{0}$ and
$\mu_{-}=\mathcal{L}^{n}\mathbin{\vrule
height=6.88889pt,depth=0.0pt,width=0.55974pt\vrule
height=0.55974pt,depth=0.0pt,width=5.59721pt}U$ the Lebesgue measure on some
open and bounded set $U\subset\mathbb{R}^{n}$ with $\mathcal{L}^{n}(U)=1$ (in
figure 2(c) given by a ring). It can then be shown that the branched transport
problem with classical transportation cost $\tau(m)=m^{\alpha}$ admits a
minimizer with finite energy if $\alpha\in(1-1/n,1)$ [Xia03, Thm. 3.1], where
any optimal mass flux is of the form
$\mathcal{F}=\xi\mathcal{H}^{1}\mathbin{\vrule
height=6.88889pt,depth=0.0pt,width=0.55974pt\vrule
height=0.55974pt,depth=0.0pt,width=5.59721pt}S$ with $S$ countably
$1$-rectifiable (which we will later see from the formula in lemma 3.0.1, in
which the diffuse part $\mathcal{F}^{\perp}$ must vanish). If $S$ was closed,
then we would get $U\subset S$ which cannot be true for $n>1$ by
$\mathcal{L}^{n}(S)=0$ – rather $S$ will be an infinitely refining, fractal
network whose first iterations are illustrated in figure 2(c) and whose mass
flux becomes the smaller the finer the branches are. From theorem 1.3.7 one
can already guess that the corresponding $b$ will tend to infinity the smaller
the flux and branches are (its values along one path are indicated in figure
2(c); compare with the formula in 3.1.6. Since $a=\tau^{\prime}(0)=\infty$,
assumption 1.3.1 is fulfilled.

###  1.4 Notation and definitions

Throughout the article we will use the following notation and definitions.

  * •

$I=[0,1]$ denotes the _unit interval_. We will use this notation if $I$
represents the domain of a path.

  * •

$\mathcal{S}^{n-1}$ denotes the _unit sphere_.

  * •

$\mathcal{C}$ denotes the _hypercube_ $[-1,1]^{n}$.

  * •

We write $B_{r}(x)$ for the _open Euclidean ball_ with radius $r>0$ and centre
$x\in\mathbb{R}^{n}$ and $\overline{B}_{r}(x)$ for its closure.

  * •

$\mathcal{L}^{k}$ denotes the $k$-dimensional _Lebesgue measure_. We write
$\mathcal{L}=\mathcal{L}^{1}$.

  * •

$\mathcal{H}^{k}$ indicates the $k$-dimensional _Hausdorff measure_.

  * •

Let $V$ be a normed vector space. We write $V^{*}$ for the _topological dual
space_. For $v\in V$ and $v^{*}\in V^{*}$ we denote the pairing between $v$
and $v^{*}$ by $\langle v,v^{*}\rangle$.

  * •

Let $A$ be a topological space. We write $\mathcal{B}(A)$ for the _$\sigma$
-algebra of Borel subsets_ of $A$.

  * •

$C(\mathcal{C})$ denotes the space of real-valued continuous functions on
$\mathcal{C}$. The subspace of Lipschitz functions is denoted
$C^{0,1}(\mathcal{C})$. Further, we write $C^{1}(\mathcal{C})$ for the space
of functions $f\in C(\mathcal{C})$ which are continuously differentiable on
$(-1,1)^{n}$ such that $f^{\prime}$ can be continued to an element of
$C(\mathcal{C})$.

  * •

Assume that $(\Omega,\mathcal{A},\mu)$ is a measure space. We write
$L^{1}(\mu;\mathbb{R}^{n})$ for the _Lebesgue space_ of equivalence classes of
$\mathcal{A}$-$\mathcal{B}(\mathbb{R}^{n})$-measurable functions
$f:\Omega\to\mathbb{R}^{n}$ with $\int_{\Omega}|f|\,\mathrm{d}\mu<\infty$,
where two such functions belong to the same class if they coincide
$\mu$-almost everywhere. For $\sigma$-finite $\mu$ this definition corresponds
to the quotient of the Lebesgue space $L_{1}(\mu,\mathbb{R}^{n})$ defined in
[Fed69, § 2.4.12] by the subspace $\\{f\,|\,f=0\,\mu\text{-almost
everywhere}\\}$.

  * •

Let $\mu:\mathcal{A}\to X$ be a map from a $\sigma$-algebra $\mathcal{A}$ to
some set $X$ (e. g., a scalar- or vector-valued measure). For any
$A\in\mathcal{A}$ we define the _restriction_ $\mu\mathbin{\vrule
height=6.88889pt,depth=0.0pt,width=0.55974pt\vrule
height=0.55974pt,depth=0.0pt,width=5.59721pt}A:\mathcal{A}\to X$ of $\mu$ to
$A$ by

$(\mu\mathbin{\vrule height=6.88889pt,depth=0.0pt,width=0.55974pt\vrule
height=0.55974pt,depth=0.0pt,width=5.59721pt}A)(B)=\mu(A\cap B)\quad\text{for
all }B\in\mathcal{A}.$

  * •

A set $S\subset\mathbb{R}^{n}$ is said to be _countably $k$-rectifiable_
(following [Fed69, p. 251]) if it is the countable union of $k$-rectifiable
sets. More precisely,

$S=\bigcup_{i=1}^{\infty}f_{i}(A_{i}),$

where $A_{i}\subset\mathbb{R}^{k}$ is bounded and
$f_{i}:A_{i}\to\mathbb{R}^{n}$ Lipschitz continuous. If $S$ is countably
$k$-rectifiable and $\mathcal{H}^{k}$-measurable, then we can apply [Fed69,
Lem. 3.2.18] which yields the existence of bi-Lipschitz functions
$g_{i}:C_{i}\to S$ with $C_{i}\subset\mathbb{R}^{k}$ compact,
$T_{i}=g_{i}(C_{i})$ pairwise disjoint and

$S=T_{0}\cup\bigcup_{i=1}^{\infty}T_{i}$

with $\mathcal{H}^{k}(T_{0})=0$. The sequence

$S^{N}=\bigcup_{i=1}^{N}T_{i}$

will be called an _approximating sequence for_ $S$.

  * •

$\mathcal{M}^{k}(A)=\\{\mathcal{F}:\mathcal{B}(A)\to\mathbb{R}^{k}\,\sigma\text{-additive}\\}$
denotes the set of $\mathbb{R}^{k}$-valued _Radon measures_ on a Polish space
$A$. Note that every $\mathcal{F}\in\mathcal{M}^{k}(A)$ is automatically
regular and of bounded variation (cf. [Els18, p. 343] and [Lan69, XI, 4.5.,
Thm. 8]). More specifically, the _total variation measure_ $|\mathcal{F}|$ is
regular and satisfies $|\mathcal{F}|(A)<\infty$. We indicate the weak-$*$
convergence of Radon measures by
$\stackrel{{\scriptstyle*}}{{\rightharpoonup}}$. The measure
$\mathcal{F}\in\mathcal{M}^{k}(A)$ is called $\mathcal{H}^{l}$_-diffuse_ if
$\mathcal{F}(B)=0$ for all $B\in\mathcal{B}(A)$ with
$\mathcal{H}^{l}(B)<\infty$ [Šil08, p. 2].

  * •

For any closed subset $A\subset\mathbb{R}^{n}$ we write
$\mathcal{DM}^{n}(A)=\\{\mathcal{F}\in\mathcal{M}^{n}(A)\,|\,\textup{div}(\mathcal{F})\in\mathcal{M}^{1}(A)\\}$,
where div denotes the distributional divergence. These vector-valued Radon
measures were termed _divergence measure vector fields_ in [Šil08, p. 2].

  * •

We write the _arc length_ of a Lipschitz path $\gamma:I\to\mathcal{C}$ as
$\text{len}(\gamma)=\int_{I}|\dot{\gamma}|\,\mathrm{d}\mathcal{L}$.

  * •

We write $\Gamma^{xy}=\\{f:I\to\mathcal{C}\textup{
Lipschitz}\,|\,f(0)=x,f(1)=y\\}$ for $x,y\in\mathcal{C}$.

  * •

We will identify the image of a Lipschitz path $\gamma:I\to\mathcal{C}$ with
its parameterization, i. e., we simply write $\gamma$ instead of $\gamma(I)$
when no confusion is possible (for instance when we integrate over
$\gamma(I)$).

  * •

For any Lipschitz continuous function $f:(X,d_{X})\to(Y,d_{Y})$ from one
metric space to another we denote the _Lipschitz constant_ by
$\text{Lip}(f)=\sup_{x_{1}\neq
x_{2}}d_{Y}(f(x_{1}),f(x_{2}))/d_{X}(x_{1},x_{2})$.

  * •

For any set $A$ we write $\iota_{A}$ for the _indicator function_ and $1_{A}$
for the _characteristic function_ ,

$\iota_{A}(x)=\begin{cases*}0&if $x\in A$,\\\ \infty&else,\end{cases*}\qquad
1_{A}(x)=\begin{cases*}1&if $x\in A$,\\\ 0&else.\end{cases*}$

  * •

For $x,y\in\mathcal{C}$ we define $[x,y]$ as the _line segment_
$\\{x+t(y-x)\,|\,t\in[0,1]\\}$. The sets $(x,y],[x,y)$ and $(x,y)$ are defined
similarly, e. g., $(x,y]=[x,y]\setminus\\{x\\}$.

  * •

For any function $f:X\to V$ with values in some normed vector space
$(V,\|.\|)$ and $A\subset X$ we write

$|f|_{\infty,A}=\sup_{x\in A}\|f(x)\|.$

  * •

The _effective domain_ of a convex function
$f:\mathbb{R}\to\mathbb{R}\cup\\{\infty\\}$ is denoted
$\text{dom}(f)=\\{x\in\mathbb{R}\,|\,f(x)<\infty\\}$.

  * •

We write the _convex conjugate_ of a function
$f:\mathbb{R}\to\mathbb{R}\cup\\{\infty\\}$ as

$f^{*}(x)=\sup_{m\in\mathbb{R}}mx-f(m).$

  * •

A sequence $x:\mathbb{N}\to M$ of elements in some set $M$ will be indicated
by the notation $(x_{i})\subset M$ with $x_{i}=x(i)$.

  * •

If a sequence of Lipschitz paths $\gamma_{j}:I\to\mathbb{R}^{n}$ converges
uniformly to some $\gamma$, then we write $\gamma_{j}\rightrightarrows\gamma$.

  * •

For two functions $f,g:M\to\mathbb{R}$ on some set $M$ we write $f\wedge
g=\min\\{f,g\\}$ and $f\vee g=\max\\{f,g\\}$ for the pointwise
minimum/maximum.

##  2 Beckmann formulation of $\boldsymbol{W_{d_{S,a,b}}}$ using duality

Let $\mu_{+},\mu_{-}:\mathcal{B}(\mathcal{C})\to[0,1]$ be probability
measures. Further, assume that $(S,a,b)$ is a city. Throughout this section,
we abbreviate the generalized urban metric $d=d_{S,a,b}$. Recall that $d(x,y)$
is the cost to travel from $x$ to $y$ in terms of the (friction) coefficients
$a$ and $b:S\to[0,\infty)$. We extend $b$ to $\mathcal{C}\setminus S$ with
value $a$ so that we may write

$d(x,y)=\inf_{\gamma\in\Gamma^{xy}}\int_{\gamma}b\,\mathrm{d}\mathcal{H}^{1}.$

In section 2.1 we prove theorem 1.3.2, i. e., under assumption 1.3.1 we have

$W_{d}(\mu_{+},\mu_{-})=\sup_{\varphi\in
C_{d}^{1}}\int_{\mathcal{C}}\varphi\,\mathrm{d}(\mu_{+}-\mu_{-}),$

where the set $C_{d}^{1}$ is defined by

$C_{d}^{1}=\\{\varphi\in C^{1}(\mathcal{C})\,|\,|\nabla\varphi|\leq b\text{ in
}\mathcal{C}\\}.$

To this end, we show that $C_{d}^{1}$ is dense (with respect to
$|.|_{\infty,\mathcal{C}}$) in

$C_{d}=\\{\varphi\in C(\mathcal{C})\,|\,|\varphi(x)-\varphi(y)|\leq
d(x,y)\text{ for all }x,y\in\mathcal{C}\\}$

and then essentially apply the classical Kantorovich–Rubinstein formula
[Edw11, Thm. 4.1]. Note that the Lipschitz condition
$|\varphi(x)-\varphi(y)|\leq d(x,y)$ does not directly imply continuity if
$a=\infty$. Further, observe that we have $C_{d}^{1}\subset C_{d}$. Indeed,
for $\varphi\in C_{d}^{1}$ we get

$|\varphi(x)-\varphi(y)|\leq\int_{\gamma}|\nabla\varphi|\,\mathrm{d}\mathcal{H}^{1}\leq\int_{\gamma}b\,\mathrm{d}\mathcal{H}^{1}$

for all $x,y\in\mathcal{C}$ and $\gamma\in\Gamma^{xy}$. By taking the infimum
over all such $\gamma$ we conclude

$|\varphi(x)-\varphi(y)|\leq d(x,y),$

which implies $\varphi\in C_{d}$. In LABEL:subs62 we will then prove theorem
1.3.4, the Beckmann formulation of the Wasserstein distance
$W_{d}(\mu_{+},\mu_{-})$, under assumption 1.3.1 or assumption 1.3.3. We will
occasionally write

$L(\gamma)=\int_{I}b(\gamma)|\dot{\gamma}|\mathrm{d}\mathcal{L}$

for the length of a Lipschitz path $\gamma:I\to\mathcal{C}$ associated with
$d$.

######  Remark 2.0.1 (Formula for $d$).

It is easy to see that (cf. [LSW22, Lemma 2.2.1])

$d(x,y)=\inf_{\gamma\in\Gamma^{xy}}L(\gamma).$

###  2.1 Kantorovich–Rubinstein duality in urban planning

In this section we prove theorem 1.3.2. To this end, we elaborate a version of
the Stone–Weierstraß theorem to work out that $C_{d}^{1}$ is a dense subset of
$C_{d}$. The first step is to provide a point separation statement for
$C_{d}^{1}$ (LABEL:psepa). We will need to approximate the urban metric $d$.
For this purpose, we define $b_{k}:\mathcal{C}\to[0,\infty)$ by

$b_{k}(z)=k\wedge\min_{\mathcal{C}\cap\overline{B}_{1/k}(z)}b$

and abbreviate $d_{k}=d_{S,a,b_{k}}$ (which is well-defined if $b_{k}$ is
lower semi-continuous, see proposition 2.1.1 below). Moreover, we write
$L_{k}$ for the path length associated with $d_{k}$.

######  Proposition 2.1.1 (Pointwise approximation of urban metric).

Let assumption 1.3.1 be satisfied. Then the $b_{k}$ are lower semi-continuous,
and we have $d_{k}\to d$ pointwise.

###### Proof.

Fix $k$ and let $(z_{j})\subset\mathcal{C}$ be a sequence such that $z_{j}\to
z\in\mathcal{C}$. We can assume that
$\liminf_{j}b_{k}(z_{j})=\lim_{j}b_{k}(z_{j})<\infty$ so that every
subsequence of $j\mapsto b_{k}(z_{j})$ has the same limit. For every $z_{j}$
there exists some $\tilde{z}_{j}\in\mathcal{C}\cap\overline{B}_{1/k}(z_{j})$
such that $b_{k}(z_{j})=k\wedge b(\tilde{z}_{j})$. By the compactness of
$\mathcal{C}$ we have $\tilde{z}_{j}\to\tilde{z}\in\mathcal{C}$ up to a
subsequence. Note that $|\tilde{z}_{j}-z|\leq 1/k+|z_{j}-z|$ and thus
$\tilde{z}\in\mathcal{C}\cap\overline{B}_{1/k}(z)$ by letting $j\to\infty$.
This yields

$b_{k}(z)\leq k\wedge b(\tilde{z})\leq\liminf_{j}(k\wedge
b(\tilde{z}_{j}))=\liminf_{j}b_{k}(z_{j}),$

where we used the lower semi-continuity of $b$. It remains to prove that
$d_{k}\to d$ pointwise. Let $(x,y)\in\mathcal{C}\times\mathcal{C}$ be
arbitrary with $x\neq y$. Since $d_{k}\leq d$ it sufficies to show
$d(x,y)\leq\liminf_{k}d_{k}(x,y)$ under the assumption that the right hand
side is finite. Let $(\gamma_{k})\subset\Gamma^{xy}$ be a sequence of
Lipschitz paths such that $L_{k}(\gamma_{k})\leq d_{k}(x,y)+1/k$. Using that
$b$ is bounded away from zero we obtain

$0<\textup{len}(\gamma_{k})\inf_{\mathcal{C}}b\leq L_{k}(\gamma_{k})\leq
const.<\infty$

for all $k>\inf b$. Thus, the lengths of the $\gamma_{k}$ are uniformly
bounded. We can thus reparameterize each $\gamma_{k}$ by arc length and get
$\gamma_{k}\rightrightarrows\gamma:I\to\mathcal{C}$ up to a subsequence by the
Arzelà–Ascoli theorem. This also yields
$|\dot{\gamma}|\leq\liminf_{k}|\dot{\gamma}_{k}|$ almost everywhere in $I$.
Now fix any $t\in I$. Once more we get $b_{k}(\gamma_{k}(t))=k\wedge b(z_{k})$
for some $z_{k}\in\mathcal{C}\cap\overline{B}_{1/k}(\gamma_{k}(t))$. Clearly,
we must have $z_{k}\to\gamma(t)$. Using again the lower semi-continuity of $b$
we estimate

$b(\gamma(t))\leq\liminf_{k}(k\wedge
b(z_{k}))=\liminf_{k}b_{k}(\gamma_{k}(t)).$

Finally, using Fatou’s lemma

$d(x,y)\leq\int_{I}b(\gamma)|\dot{\gamma}|\mathrm{d}\mathcal{L}\leq\int_{I}\liminf_{k}b_{k}(\gamma_{k})\liminf_{k}|\dot{\gamma}_{k}|\mathrm{d}\mathcal{L}\leq\liminf_{k}\int_{I}b_{k}(\gamma_{k})|\dot{\gamma}_{k}|\mathrm{d}\mathcal{L}=\liminf_{k}L_{k}(\gamma_{k})\leq\liminf_{k}d_{k}(x,y)+\frac{1}{k},$

which shows the pointwise convergence $d_{k}\to d$. ∎

###### Proof of theorem 1.3.4 under assumption 1.3.3.

$W_{d}(\mu_{+},\mu_{-})\leq B(\mu_{+},\mu_{-})$: Initially, we show the
inequality for the case $\inf b>0$. Let $\delta>0$ and fix $\xi$ and
$\mathcal{F}^{\perp}$ as in the Beckmann problem. We define measures by
$\mathcal{G}_{N}=\xi\mathcal{H}^{1}\mathbin{\vrule
height=6.88889pt,depth=0.0pt,width=0.55974pt\vrule
height=0.55974pt,depth=0.0pt,width=5.59721pt}(S\setminus
S^{N})+\mathcal{F}^{\perp}$. The function $|\xi|$ is integrable with respect
to $\mathcal{H}^{1}\mathbin{\vrule
height=6.88889pt,depth=0.0pt,width=0.55974pt\vrule
height=0.55974pt,depth=0.0pt,width=5.59721pt}S$. Consequently, we have

$|\mathcal{G}_{N}-\mathcal{F}^{\perp}|(\mathcal{C})=\int_{S\setminus
S^{N}}|\xi|\,\mathrm{d}\mathcal{H}^{1}\to 0$

for $N\to\infty$. Thus, we can choose $N$ sufficiently large such that
$|\mathcal{G}_{N}-\mathcal{F}^{\perp}|(\mathcal{C})<\delta/a$. Using in this
order $\textup{div}(\xi\mathcal{H}^{1}\mathbin{\vrule
height=6.88889pt,depth=0.0pt,width=0.55974pt\vrule
height=0.55974pt,depth=0.0pt,width=5.59721pt}S^{N}+\mathcal{G}_{N})=\textup{div}(\xi\mathcal{H}^{1}\mathbin{\vrule
height=6.88889pt,depth=0.0pt,width=0.55974pt\vrule
height=0.55974pt,depth=0.0pt,width=5.59721pt}S+\mathcal{F}^{\perp})=\mu_{+}-\mu_{-}$,
LABEL:Fenchel, theorem 1.3.2, and $d^{N}\geq d$, we can estimate

$\int_{S}b|\xi|\,\mathrm{d}\mathcal{H}^{1}+a|\mathcal{F}^{\perp}|(\mathcal{C})\geq\int_{S^{N}}b|\xi|\,\mathrm{d}\mathcal{H}^{1}+a|\mathcal{G}_{N}|(\mathcal{C})-\delta\geq
B_{S^{N},a,b|_{S^{N}}}(\mu_{+},\mu_{-})-\delta\\\ =\sup_{\varphi\in
C_{d^{N}}^{1}}\int_{\mathcal{C}}\varphi\,\mathrm{d}(\mu_{+}-\mu_{-})-\delta=W_{d^{N}}(\mu_{+},\mu_{-})-\delta\geq
W_{d}(\mu_{+},\mu_{-})-\delta,$

where $C_{d^{N}}^{1}=\\{\varphi\in C^{1}(\mathcal{C})\,|\,|\nabla\varphi|\leq
b\text{ on }S^{N},|\nabla\varphi|\leq a\text{ in }\mathcal{C}\\}$. Letting
$\delta\to 0$ yields the desired inequality. Now we concentrate on the case
$\inf b=0$. Using the functions $b_{\lambda}$ we obtain

$\int_{S}b_{\lambda}|\xi|\,\mathrm{d}\mathcal{H}^{1}+a|\mathcal{F}^{\perp}|(\mathcal{C})\geq
W_{d}(\mu_{+},\mu_{-}).$

Moreover, we have

$\int_{S}b_{\lambda}|\xi|\,\mathrm{d}\mathcal{H}^{1}\leq
a\int_{S}|\xi|\,\mathrm{d}\mathcal{H}^{1}<\infty$

and therefore (monotone convergence)

$\int_{S}b|\xi|\,\mathrm{d}\mathcal{H}^{1}+a|\mathcal{F}^{\perp}|(\mathcal{C})\geq
W_{d}(\mu_{+},\mu_{-})$

by letting $\lambda\to 0$.
$W_{d}(\mu_{+},\mu_{-})\geq B(\mu_{+},\mu_{-})$: First assume that $\inf b>0$.
By LABEL:optplan there exists an optimal transport plan
$\pi\in\Pi(\mu_{+},\mu_{-})$ such that $W_{d}(\mu_{+},\mu_{-})=\langle
d,\pi\rangle$. Let $\delta>0$ be arbitrary. Using $\langle
d^{N},\pi\rangle<\infty$ and $d^{N}\searrow d$ pointwise by LABEL:Siconv the
monotone convergence theorem implies the existence of some $N=N(\delta)$ such
that $|\langle d^{N}-d,\pi\rangle|\leq\delta$. Application of LABEL:Fenchel
and LABEL:rem:monotonicityBeckmann yields

$W_{d}(\mu_{+},\mu_{-})=\langle d,\pi\rangle\geq\langle
d^{N},\pi\rangle-\delta\geq
W_{d^{N}}(\mu_{+},\mu_{-})-\delta=B_{S^{N},a,b|_{S^{N}}}(\mu_{+},\mu_{-})-\delta\geq
B_{S,a,b}(\mu_{+},\mu_{-})-\delta.$

Letting $\delta\to 0$ yields the desired inequality. Now assume that $\inf
b=0$. Once more let $\delta>0$. Again, by $\langle
d_{\lambda},\pi\rangle<\infty$ and $d_{\lambda}\searrow d$ pointwise by
LABEL:Siconv we can apply the monotone convergence theorem and choose
$\lambda$ sufficiently small such that

$W_{d}(\mu_{+},\mu_{-})=\langle d,\pi\rangle\geq\langle
d_{\lambda},\pi\rangle-\delta\geq W_{d_{\lambda}}(\mu_{+},\mu_{-})-\delta\geq
B_{S,a,b_{\lambda}}(\mu_{+},\mu_{-})-\delta\geq
B_{S,a,b}(\mu_{+},\mu_{-})-\delta.$

Letting $\delta\to 0$ we obtain the desired inequality. ∎

##  3 Urban planning formulation of branched transport using duality

In this section we prove theorem 1.3.8 under assumption 1.3.5. We will use the
following formula for the branched transport problem [LSW22, Lemma 3.1.8],
which can be derived from [BCM09, Lem. 5.15], [BW18, Prop. 2.32], and [Šil08,
Thm. 3.1].

######  Lemma 3.0.1 (Version of the branched transport problem).

The branched transport problem can be written as

$\inf_{\mathcal{F}\in\mathcal{DM}^{n}(\mathcal{C})}\mathcal{J}^{\tau,\mu_{+},\mu_{-}}[\mathcal{F}]=\inf_{S,\xi,\mathcal{F}^{\perp}}\int_{S}\tau(|\xi|)\,\mathrm{d}\mathcal{H}^{1}+\tau^{\prime}(0)|\mathcal{F}^{\perp}|(\mathcal{C})+\iota_{\\{\mu_{+}-\mu_{-}\\}}(\textup{div}(\xi\mathcal{H}^{1}\mathbin{\vrule
height=6.88889pt,depth=0.0pt,width=0.55974pt\vrule
height=0.55974pt,depth=0.0pt,width=5.59721pt}S+\mathcal{F}^{\perp}))$

with $S\subset\mathcal{C}$ countably $1$-rectifiable and Borel measurable,
$\xi\in L^{1}(\mathcal{H}^{1}\mathbin{\vrule
height=6.88889pt,depth=0.0pt,width=0.55974pt\vrule
height=0.55974pt,depth=0.0pt,width=5.59721pt}S;\mathbb{R}^{n})$ and
$\mathcal{F}^{\perp}\in\mathcal{M}^{n}(\mathcal{C})$ with
$\mathcal{F}^{\perp}\mathbin{\vrule
height=6.88889pt,depth=0.0pt,width=0.55974pt\vrule
height=0.55974pt,depth=0.0pt,width=5.59721pt}S=0$.

In section 3.1 we will prove a dual formula for the first network cost term,
which will be used to introduce the friction coefficients $b$. Based on this
formula and theorem 1.3.4, we will provide a short proof of theorem 1.3.8
under assumption 1.3.5.

###  3.1 Duality for the total network transportation cost

We apply a generalization of Rockafellar’s duality theorem between a pair of
decomposable spaces of vector-valued functions [CV77, Thm. VII-7]. Let
$S\subset\mathcal{C}$ be countably $k$-rectifiable and
$\mathcal{H}^{k}$-measurable ($k=1$ and $S$ even Borel in our setting). We
denote the $\sigma$-algebra of $\mathcal{H}^{k}$-measurable subsets of $S$ (or
more precisely subsets that are Carathéodory-measurable relative to
$\mathcal{H}^{k}$) by $\mathscr{H}^{k}(S)$. Using that the restriction of an
outer measure like $\mathcal{H}^{k}$ on $\mathbb{R}^{n}$ to the Carathéodory-
measurable sets yields a complete measure space, this property also holds for
$(S,\mathscr{H}^{k}(S),\mathcal{H}^{k}\mathbin{\vrule
height=6.88889pt,depth=0.0pt,width=0.55974pt\vrule
height=0.55974pt,depth=0.0pt,width=5.59721pt}S)$. Furthermore, the measure
space $(S,\mathscr{H}^{k}(S),\mathcal{H}^{k}\mathbin{\vrule
height=6.88889pt,depth=0.0pt,width=0.55974pt\vrule
height=0.55974pt,depth=0.0pt,width=5.59721pt}S)$ is $\sigma$-finite (every
member of an approximating sequence for $S$ has finite measure).

######  Convention 3.1.1.

In this section “measurability” and “integrability” will refer to the measure
space $(S,\mathscr{H}^{k}(S),\mathcal{H}^{k}\mathbin{\vrule
height=6.88889pt,depth=0.0pt,width=0.55974pt\vrule
height=0.55974pt,depth=0.0pt,width=5.59721pt}S)$.

We remind the reader that a subset $A\subset S$ is in $\mathscr{H}^{k}(S)$ if
and only if $\mathcal{H}^{k}(B)=\mathcal{H}^{k}(B\cap
A)+\mathcal{H}^{k}(B\backslash A)$ for all $B\subset S$. By Carathéodory’s
criterion [Sim14, Thm. 1.13] we have
$\mathcal{B}(S)\subset\mathscr{H}^{k}(S)$. In our case, the “vector-valued
functions” from [CV77, Chap. VII-7] are given through integrable and real-
valued functions on $S$. We consider the following vector spaces:

$\displaystyle\mathscr{L}$ $\displaystyle=\\{f:S\to\mathbb{R}\text{ measurable
and integrable}\\},$ $\displaystyle\mathscr{L}_{\text{b}}$
$\displaystyle=\\{f\in\mathscr{L}\,|\,f\text{ bounded}\\},$
$\displaystyle\mathscr{M}_{\text{b}}$ $\displaystyle=\\{f:S\to\mathbb{R}\text{
measurable and bounded}\\}.$

Note that the elements of $\mathscr{L},\mathscr{L}_{\text{b}}$, and
$\mathscr{M}_{\text{b}}$ are not equivalence classes. We follow here the
setting in [CV77, Def. VII-3].

######  Definition 3.1.2 (Decomposable [CV77, Def. VII-3]).

Let $V\subset\mathscr{L}$ be a subspace. The space $V$ is said to be
decomposable if $1_{A}f+1_{S\setminus A}g\in V$ for all
$A\in\mathscr{H}^{k}(S)$ with $\mathcal{H}^{k}(A)<\infty$,
$f\in\mathscr{M}_{\text{b}}$ and $g\in V$.

The vector spaces $\mathscr{L}$ and $\mathscr{L}_{\text{b}}$ are decomposable:
Let either $V=\mathscr{L}$ or $V=\mathscr{L}_{\text{b}}$ and $A,f,g$ as in
definition 3.1.2. Then we have

$\int_{S}|1_{A}f+1_{S\setminus
A}g|\,\mathrm{d}\mathcal{H}^{k}\leq\mathcal{H}^{k}(A)|f|_{\infty,A}+\int_{S\setminus
A}|g|\,\mathrm{d}\mathcal{H}^{k}<\infty$

and thus $1_{A}f+1_{S\setminus A}g\in\mathscr{L}$. Further, if
$V=\mathscr{L}_{\text{b}}$, then we obtain $|1_{A}f+1_{S\setminus
A}g|\leq|f|_{\infty,A}+|g|_{\infty,A}<\infty$. Moreover, we get $x\mapsto
f(x)g(x)\in\mathscr{L}$ for all $f\in\mathscr{L},g\in\mathscr{L}_{\text{b}}$
(cf. [CV77, Def. VII-3]), which needs to be satisfied to apply [CV77, Thm.
VII-7]. For $g\in\mathscr{L}$ and lower semi-continuous functions
$f:\mathbb{R}\to\mathbb{R}\cup\\{\infty\\}$ we write

$I_{f}(g)=\begin{cases}\int_{S}f(g)\,\mathrm{d}\mathcal{H}^{k}&\text{if
}\int_{S}f(g)^{+}\,\mathrm{d}\mathcal{H}^{k}<\infty,\\\
\infty&\text{else},\end{cases}$

where $f(g)^{+}$ denotes the positive part of
$f(g):S\to\mathbb{R}\cup\\{\infty\\}$. By our construction we can apply the
following statement to generate the friction coefficients $b:S\to[0,\infty)$
of the urban planning problem. Essentially it characterizes the convex
conjugate of integral functionals using $L^{1}$-$L^{\infty}$-type duality
pairings: One may pull the convex conjugation inside the integral.

######  Proposition 3.1.3 (First part of [CV77, Thm. VII-7]).

Let $f:\mathbb{R}\to\mathbb{R}\cup\\{\infty\\}$ be lower semi-continuous.
Assume that $I_{f}(g_{0})$ is finite for at least one
$g_{0}\in\mathscr{L}_{\text{b}}$. Then we obtain

$I_{f^{*}}(h)=\sup_{g\in\mathscr{L}_{\text{b}}}\int_{S}gh\,\mathrm{d}\mathcal{H}^{k}-I_{f}(g)$

for all $h\in\mathscr{L}$.

Fix a maintenance cost $\varepsilon$ induced by a transportation cost $\tau$,
i. e., $\varepsilon(b)=(-\tau)^{*}(-b)$, where $\tau(m)=-\infty$ for $m<0$.
Then we get the following formula for the network cost term from lemma 3.0.1.

######  Corollary 3.1.4 (Substitution of maintenance cost).

Assume that $\mathcal{H}^{k}(S)<\infty$. Furthermore, let
$\xi:S\to\mathbb{R}^{n}$ be integrable. Let the transportation cost $\tau$ be
right-continuous in $0$. Then we have

$\int_{S}\tau(|\xi|)\,\mathrm{d}\mathcal{H}^{k}=\inf_{b}\int_{S}b|\xi|\,\mathrm{d}\mathcal{H}^{k}+\int_{S}\varepsilon(b)\,\mathrm{d}\mathcal{H}^{k},$

where the infimum is taken over $b\in\mathscr{L}_{\text{b}}$.

###### Proof.

The biconjugate equals the convex and lower semi-continuous envelope [Rin18,
Prop. 2.28]. The function $-\tau$ is already convex and lower semi-continuous
by assumption. Thus, we conclude

$\tau(m)=-(-\tau)^{**}(m)=-\left(\sup_{v\in\mathbb{R}}vm-(-\tau)^{*}(v)\right)=-\left(\sup_{v\in\mathbb{R}}-vm-\varepsilon(v)\right)=-\varepsilon^{*}(-m).$

Furthermore, we have $I_{\varepsilon}(v)<\infty$ for all $v\in\mathbb{R}$ with
$\varepsilon(v)<\infty$ using $\mathcal{H}^{k}(S)<\infty$. We presumed
$|\xi|\in\mathscr{L}$ and can therefore apply proposition 3.1.3:

$\int_{S}\tau(|\xi|)\,\mathrm{d}\mathcal{H}^{k}=-\int_{S}\varepsilon^{*}(-|\xi|)\,\mathrm{d}\mathcal{H}^{k}=-I_{\varepsilon^{*}}(-|\xi|)=-\sup_{b\in\mathscr{L}_{\text{b}}}-\int_{S}b|\xi|\,\mathrm{d}\mathcal{H}^{k}-I_{\varepsilon}(b)=\inf_{b\in\mathscr{L}_{\text{b}}}\int_{S}b|\xi|\,\mathrm{d}\mathcal{H}^{k}+\int_{S}\varepsilon(b)\,\mathrm{d}\mathcal{H}^{k}.\qed$

We now prove theorem 1.3.7 in a slightly generalized setting (for arbitrary
$k$ and $S$ not necessarily Borel measurable).

######  Theorem 3.1.5 (Generalization of theorem 1.3.7).

Let $\xi:S\to\mathbb{R}^{n}$ be integrable. Assume that $\tau$ satisfies
assumption 1.3.5. Then we have

$\int_{S}\tau(|\xi|)\,\mathrm{d}\mathcal{H}^{k}=\inf_{b}\int_{S}b|\xi|\,\mathrm{d}\mathcal{H}^{k}+\int_{S}\varepsilon(b)\,\mathrm{d}\mathcal{H}^{k},$

where the infimum is taken over lower semi-continuous functions
$b:S\to[0,\tau^{\prime}(0)]$.

###### Proof.

Formula true for functions $b\in\mathscr{M}_{b}$: Using the procedure in
section 1.4 (compare with the sets $T_{i}$), we can assume that $S$ is a
disjoint countable union of finitely $k$-rectifiable sets $S_{i}$, i. e., the
$S_{i}\subset S$ are measurable with $\mathcal{H}^{k}(S_{i})<\infty$ (we
neglect nullsets due to the integration). Let $\delta>0$ and $\delta_{i}>0$
such that $\sum_{i}\delta_{i}=\delta$. By 3.1.4 we can find functions
$b_{i}\in\mathscr{L}_{b}$ with

$\int_{S_{i}}\tau(|\xi|)\,\mathrm{d}\mathcal{H}^{k}\geq\int_{S_{i}}|\xi|b_{i}+\varepsilon(b_{i})\,\mathrm{d}\mathcal{H}^{k}-\delta_{i}.$

Define $\tilde{b}\in\mathscr{M}_{\text{b}}$ by $\tilde{b}=b_{i}$ on $S_{i}$.
Note that we can assume that each $b_{i}$ is bounded by $\tau^{\prime}(0)$
because of $\varepsilon([\tau^{\prime}(0),\infty))=\\{0\\}$. Application of
the monotone convergence theorem yields

$\int_{S}\tau(|\xi|)\,\mathrm{d}\mathcal{H}^{k}=\sum_{i}\int_{S_{i}}\tau(|\xi|)\,\mathrm{d}\mathcal{H}^{k}\geq\sum_{i}\int_{S_{i}}|\xi|b_{i}+\varepsilon(b_{i})\,\mathrm{d}\mathcal{H}^{k}-\delta=\int_{S}|\xi|\tilde{b}+\varepsilon(\tilde{b})\,\mathrm{d}\mathcal{H}^{k}-\delta\\\
\geq\inf_{b}\int_{S}|\xi|b+\varepsilon(b)\,\mathrm{d}\mathcal{H}^{k}-\delta=\inf_{b}\int_{S}|\xi|b\,\mathrm{d}\mathcal{H}^{k}+\int_{S}\varepsilon(b)\,\mathrm{d}\mathcal{H}^{k}-\delta,$

where the infima are taken over functions $b\in\mathscr{M}_{\text{b}}$. Notice
that $\varepsilon,b\geq 0$ was used in the last equation. The reverse
inequality is a direct consequence of the definition of the convex conjugate.
More precisely, let $b:S\to[0,\infty)$ be any measurable and bounded function.
Then we obtain

$\int_{S}\tau(|\xi|)\,\mathrm{d}\mathcal{H}^{k}=-\int_{S}\varepsilon^{*}(-|\xi|)\,\mathrm{d}\mathcal{H}^{k}=-\int_{S}\sup_{v\in\mathbb{R}}-v|\xi(x)|-\varepsilon(v)\,\mathrm{d}\mathcal{H}^{k}(x)\leq\int_{S}b|\xi|\,\mathrm{d}\mathcal{H}^{k}+\int_{S}\varepsilon(b)\,\mathrm{d}\mathcal{H}^{k}$

by choosing $v=v(x)=b(x)$ in the inequality. Taking the infimum over $b$ shows
the stated formula for $b\in\mathscr{M}_{\text{b}}$.
The functions $b$ can be assumed to be lower semi-continuous: As a first step,
we simplify the statement to be shown. Write $c=\inf\text{dom}(\varepsilon)$.
Note that every function in the infimum of the stated formula of the theorem
can be assumed to have values in $[c,\tau^{\prime}(0)]$ by the properties of
$\varepsilon$. For $f\in\mathscr{M}_{\text{b}}$ with $f\geq 0$ define

$F(f)=\int_{S}f|\xi|+\varepsilon(f)\,\mathrm{d}\mathcal{H}^{k}\in[0,\infty].$

Let $b\in\mathscr{M}_{\text{b}}$ be arbitrary with $F(b)<\infty$ (note that
$F(\tau^{\prime}(0))<\infty$ by the integrability of $|\xi|$ and
$\varepsilon(\tau^{\prime}(0))=0$). Let $S^{N}$ be an approximating sequence
for $S$. Define functions by

$b_{N}=\begin{cases}b&\text{on }S^{N},\\\ \tau^{\prime}(0)&\text{on
}S\setminus S^{N}.\end{cases}$

We have $\varepsilon(b_{N})\nearrow\varepsilon(b)$ and $b_{N}|\xi|\searrow
b|\xi|$ for $N\to\infty$ pointwise $\mathcal{H}^{k}\mathbin{\vrule
height=6.88889pt,depth=0.0pt,width=0.55974pt\vrule
height=0.55974pt,depth=0.0pt,width=5.59721pt}S$-almost everywhere.
Furthermore, the $b_{N}|\xi|$ satisfy

$\int_{S}b_{N}|\xi|\,\mathrm{d}\mathcal{H}^{k}\leq\tau^{\prime}(0)\int_{S}|\xi|\,\mathrm{d}\mathcal{H}^{k}<\infty.$

Hence, we get $F(b_{N})\to F(b)$ for $N\to\infty$ by the monotone convergence
theorem. Thus, for fixed $N$ it is enough to find a lower semi-continuous
funcion $\ell_{N}:S\to[c,\tau^{\prime}(0)]$ such that $F(\ell_{N})$ is
arbitrarily close to $F(b_{N})$. This reduces to the problem of finding a
lower semi-continuous function $\ell_{N}:S^{N}\to[c,\tau^{\prime}(0)]$ with
$F_{N}(\ell_{N})$ being arbitrarily close to $F_{N}(b_{N})$, where

$F_{N}(f)=\int_{S^{N}}f|\xi|+\varepsilon(f)\,\mathrm{d}\mathcal{H}^{k}$

for $f\in\mathscr{M}_{\text{b}}$ with $f\geq 0$, because we can then replace
$\ell_{N}$ by the lower semi-continuous function ($S^{N}$ is closed)

$\tilde{\ell}_{N}=\begin{cases}\ell_{N}&\text{on }S^{N},\\\
\tau^{\prime}(0)&\text{on }S\setminus S^{N}.\end{cases}$

Note that $F_{N}(b_{N})$ is finite by $F(b)<\infty$. For simplicity, we write
$S,F,b$ instead of $S^{N},F_{N},b_{N}$ and assume that $S$ is closed with
$\mathcal{H}^{k}(S)<\infty$ (like the $S^{N}$) and $F(b)<\infty$ (which
implies $\varepsilon(b)\in\mathscr{L}$) for the rest of the proof. By [AFP00,
Rem. 2.50] (which refers to [AFP00, Ex. 1.3]) the function
$b\in\mathscr{M}_{\text{b}}$ can be assumed to be Borel measurable. We will
below use the functions $b_{\delta}=b+\delta$ for $\delta>0$. Without loss of
generality the $b_{\delta}$ have values in
$[c+\delta,\tau^{\prime}(0)+\delta]$. Since the restriction of
$\mathcal{H}^{k}\mathbin{\vrule
height=6.88889pt,depth=0.0pt,width=0.55974pt\vrule
height=0.55974pt,depth=0.0pt,width=5.59721pt}S$ to $\mathcal{B}(S)$ now is a
finite Radon measure on a compact set, we can apply the Vitali–Carathéodory
theorem [Rud86, 2.25] to the functions $b_{\delta}\in\mathscr{L}$: for all
$\delta>0$ there exists a sequence of lower semi-continuous functions
$\ell_{\delta}^{i}$ with
$b_{\delta}\leq\ell_{\delta}^{i}\leq\tau^{\prime}(0)+\delta$ on $S$ and

$\int_{S}(\ell_{\delta}^{i}-b_{\delta})\,\mathrm{d}\mathcal{H}^{k}\to 0\text{
for }i\to\infty.$

This yields $\ell_{\delta}^{i}\to b_{\delta}$ pointwise
$(\mathcal{H}^{k}\mathbin{\vrule
height=6.88889pt,depth=0.0pt,width=0.55974pt\vrule
height=0.55974pt,depth=0.0pt,width=5.59721pt}S)$-almost everywhere for
$i\to\infty$ up to a subsequence. Now let
$f_{\delta}^{i}=\ell_{\delta}^{i}|\xi|+\varepsilon(\ell_{\delta}^{i})$. We
obtain
$|f_{\delta}^{i}|\leq(\tau^{\prime}(0)+\delta)|\xi|+\varepsilon(c+\delta)\in\mathscr{L}$
and $f_{\delta}^{i}\to b_{\delta}|\xi|+\varepsilon(b_{\delta})$ pointwise
$\mathcal{H}^{k}\mathbin{\vrule
height=6.88889pt,depth=0.0pt,width=0.55974pt\vrule
height=0.55974pt,depth=0.0pt,width=5.59721pt}S$-almost everywhere for
$i\to\infty$ ($\varepsilon$ is continuous on $(c,\infty)$). Thus, we have
$F(\ell_{\delta}^{i})\to F(b_{\delta})$ for $i\to\infty$ by Lebesgue’s
dominated convergence theorem. In addition, we have
$h_{\delta}=b_{\delta}|\xi|+\varepsilon(b_{\delta})\to b|\xi|+\varepsilon(b)$
pointwise for $\delta\to 0$ ($\varepsilon$ is right-continuous in $c$) and
$|h_{\delta}|\leq(\tau^{\prime}(0)+\delta)|\xi|+\varepsilon(b)\in\mathscr{L}$,
which yields $F(b_{\delta})\to F(b)$ for $\delta\to 0$. This shows that $b$
can be assumed to be lower semi-continuous (choose $\delta$ sufficiently small
and then $i$ sufficiently large for the corresponding subsequence of the
$\ell_{\delta}^{i}$). ∎

######  Remark 3.1.6 (Construction of minimizer).

If $|\xi|$ is upper semi-continuous, then a minimizer $b$ is given by (cf.
proof of [LSW22, Theorem 1.3.4])

$b=-\max\partial(-\tau)(|\xi|).$

###  3.2 Branched transport as street network optimization

###### Proof of theorem 1.3.8 under assumption 1.3.5.

We apply lemma 3.0.1, theorem 1.3.7, and theorem 1.3.4 (the variables are as
in the problems and statements):

$\displaystyle\inf_{\mathcal{F}}\mathcal{J}^{\tau,\mu_{+},\mu_{-}}[\mathcal{F}]$
$\displaystyle=\inf_{\xi,S,\mathcal{F}^{\perp}}\int_{S}\tau(|\xi|)\mathrm{d}\mathcal{H}^{1}+\tau^{\prime}(0)|\mathcal{F}^{\perp}|(\mathcal{C})+\iota_{\\{\mu_{+}-\mu_{-}\\}}(\textup{div}(\xi\mathcal{H}^{1}\mathbin{\vrule
height=6.88889pt,depth=0.0pt,width=0.55974pt\vrule
height=0.55974pt,depth=0.0pt,width=5.59721pt}S+\mathcal{F}^{\perp}))$
$\displaystyle=\inf_{\xi,S,\mathcal{F}^{\perp}}\inf_{b}\int_{S}b|\xi|\mathrm{d}\mathcal{H}^{1}+\int_{S}\varepsilon(b)\mathrm{d}\mathcal{H}^{1}+\tau^{\prime}(0)|\mathcal{F}^{\perp}|(\mathcal{C})+\iota_{\\{\mu_{+}-\mu_{-}\\}}(\textup{div}(\xi\mathcal{H}^{1}\mathbin{\vrule
height=6.88889pt,depth=0.0pt,width=0.55974pt\vrule
height=0.55974pt,depth=0.0pt,width=5.59721pt}S+\mathcal{F}^{\perp}))$
$\displaystyle=\inf_{S,b}\inf_{\xi,\mathcal{F}^{\perp}}\int_{S}b|\xi|\mathrm{d}\mathcal{H}^{1}+\tau^{\prime}(0)|\mathcal{F}^{\perp}|(\mathcal{C})+\iota_{\\{\mu_{+}-\mu_{-}\\}}(\textup{div}(\xi\mathcal{H}^{1}\mathbin{\vrule
height=6.88889pt,depth=0.0pt,width=0.55974pt\vrule
height=0.55974pt,depth=0.0pt,width=5.59721pt}S+\mathcal{F}^{\perp}))+\int_{S}\varepsilon(b)\mathrm{d}\mathcal{H}^{1}$
$\displaystyle=\inf_{S,b}W_{d_{S,\tau^{\prime}(0),b}}(\mu_{+},\mu_{-})+\int_{S}\varepsilon(b)\mathrm{d}\mathcal{H}^{1}$
$\displaystyle=\inf_{S,b}\mathcal{U}^{\varepsilon,\mu_{+},\mu_{-}}[S,b].\qed$

######  Remark 3.2.1 (Branched transport problem has minimizer under
assumption 1.3.5).

The growth condition $\tau^{\prime}(0)<\infty$ implies

$\int_{0}^{1}\frac{\tau(m)}{m^{2-1/n}}\mathrm{d}m\leq\tau^{\prime}(0)\int_{0}^{1}\frac{1}{m^{1-1/n}}\mathrm{d}m=\tau^{\prime}(0)n<\infty,$

which by [BW18, Corollaries 2.19 & 2.20] guarantees that the branched
transport problem is finite and has a solution $\mathcal{F}$.

##  4 Acknowledgements

This work was supported by the Deutsche Forschungsgemeinschaft (DFG, German
Research Foundation) under the priority program SPP 1962, grant WI 4654/1-1,
and under Germany’s Excellence Strategy EXC 2044 – 390685587, Mathematics
Münster: Dynamics–Geometry–Structure. B.W.’s and J.L.’s research was supported
by the Alfried Krupp Prize for Young University Teachers awarded by the
Alfried Krupp von Bohlen und Halbach-Stiftung. B.S.’s research was supported
by the Emmy Noether Programme of the DFG, grant SCHM 3462/1-1.

## References

  * [AFP00] Luigi Ambrosio, Nicola Fusco and Diego Pallara  “Functions of bounded variation and free discontinuity problems”, Oxford Mathematical Monographs  New York: Oxford University Press, 2000
  * [AGS08] Luigi Ambrosio, Nicola Gigli and Giuseppe Savare  “Gradient Flows”, Lectures in Mathematics. ETH Zürich  Birkhäuser Basel, 2008
  * [BB05] Alessio Brancolini and Giuseppe Buttazzo  “Optimal networks for mass transportation problems”  In _ESAIM: Control, Optimisation and Calculus of Variations_ 11.1, 2005, pp. 88–101
  * [BCM09] Marc Bernot, Vicent Caselles and Jean-Michel Morel  “Optimal Transportation Networks”, Lecture notes in Mathematics  Berlin: Springer-Verlag, 2009
  * [Bri96] Egbert Brieskorn  “Felix Hausdorff zum Gedächtnis - Band I”  Wiesbaden: Vieweg+Teubner Verlag, 1996
  * [But+09] Giuseppe Buttazzo, Aldo Pratelli, Eugene Stepanov and Sergio Solimini  “Optimal Urban Networks via Mass Transportation”  Berlin Heidelberg: Springer-Verlag, 2009
  * [BV10] Jonathan Michael Borwein and Jon Vanderwerff  “Convex Functions”  New York: Cambridge University Press, 2010
  * [BW16] Alessio Brancolini and Benedikt Wirth  “Equivalent formulations for the branched transport and urban planning problems”  In _J. Math. Pures Appl. (9)_ 106.4, 2016, pp. 695–724
  * [BW18] Alessio Brancolini and Benedikt Wirth  “General transport problems with branched minimizers as functionals of 1-currents with prescribed boundary”  In _Calc. Var. Partial Differential Equations_ 57.3, 2018, pp. Paper No. 8239
  * [CV77] Charles Castaing and Michel Valadier  “Convex Analysis and Measurable Multifunctions”, Lecture Notes in Mathematics  Berlin: Springer-Verlag, 1977
  * [Edw11] David A. Edwards  “On the Kantorovich–Rubinstein theorem”  In _Expositiones Mathematicae_ 29.4, 2011, pp. 387–398
  * [Els18] Jürgen Elstrodt  “Maß- und Integrationstheorie”  Berlin, Heidelberg: Springer Spektrum, 2018
  * [Fal86] Kenneth John Falconer  “The geometry of fractal sets”  Cambridge: Cambridge University Press, 1986
  * [Fed69] Herbert Federer  “Geometric measure theory”, Die Grundlehren der mathematischen Wissenschaften  New York: Springer-Verlag, 1969
  * [Lan69] Serge Lang  “Real Analysis”, Addison-Wesley Series in Mathematics  Reading MA: Addison-Wesley, 1969
  * [LSW22] Julius Lohmann, Bernhard Schmitzer and Benedikt Wirth  “Formulation of branched transport as geometry optimization” DOI: 10.1016/j.matpur.2022.05.021,, 2022
  * [Rin18] Filip Rindler  “Calculus of variations”  Basel: Springer International Publishing, 2018
  * [Rud86] Walter Rudin  “Real and Complex Analysis”  New York City: McGraw-Hill Education Ltd, 1986
  * [San15] Filippo Santambrogio  “Optimal Transport for Applied Mathematicians”  Basel: Birkhäuser Verlag, 2015
  * [Šil08] Miroslav Šilhavý  “Divergence measure vectorfields: their structure and the divergence theorem”  Napoli: Aracne, 2008, pp. 217–237
  * [Sim14] Leon M. Simon  “Introduction to Geometric Measure Theory”, 2014  URL: https://web.stanford.edu/class/math285/ts-gmt.pdf
  * [SW19] Bernhard Schmitzer and Benedikt Wirth  “Dynamic models of Wasserstein-1-type unbalanced transport”  In _ESAIM Control Optim. Calc. Var._ 25, 2019, pp. Paper No. 2354
  * [Vil09] C. Villani  “Optimal Transport: Old and New” 338, Grundlehren der mathematischen Wissenschaften  Springer, 2009
  * [Xia03] Qinglan Xia  “Optimal paths related to transport problems”  In _Communications in Contemporary Mathematics_ 5.2, 2003, pp. 251–279


$\displaystyle=-\frac{\alpha_{g}}{\eta}\ln\left(\frac{\sum_{j\in\Omega_{g}\cap\text{supp}({\bm{x}}^{*})}x_{j}}{x_{p_{j}}}\right)$
$\displaystyle\leq-\frac{\alpha_{g}}{\eta}\ln\left(\frac{\sum_{j\in\Omega_{g}\cap\text{supp}({\bm{x}}^{*})}(x_{j}^{*}-c)}{x_{p_{j}}^{*}+c}\right)$
($\|{\bm{z}}^{*}-{\bm{z}}\|\leq\frac{\eta^{2}\xi\epsilon_{\text{dil}}^{2}}{40P^{3}\|{\bm{\alpha}}\|_{\infty}}$)
$\displaystyle\leq-\frac{\alpha_{g}}{\eta}\ln\left(\frac{x_{p_{j}}^{*}-c|\Omega_{g}|}{x_{p_{j}}^{*}+c}\right)$
$\displaystyle=-\frac{\alpha_{g}}{\eta}\ln\left(1-\frac{c(|\Omega_{g}|+1)}{x_{p_{j}}^{*}+c}\right)$
$\displaystyle\leq-\frac{\alpha_{g}}{\eta}\ln\left(1-\frac{cP}{\epsilon_{\text{dil}}}\right)$
($x_{p_{j}}^{*}+c\geq x_{p_{j}}^{*}\geq\epsilon_{\text{dil}}$ and
$|\Omega_{g}|+1\leq P$)
$\displaystyle\leq-\frac{\alpha_{g}}{\eta}\ln\left(1-\frac{\eta^{2}\xi}{40\alpha_{g}P^{2}}\right)$
(by definition of $c$) $\displaystyle\leq\frac{\eta\xi}{20P^{2}}.$
($-\ln(1-x)<2x$ for $0<x<0.5$)

Plugging this back to the original inequalities, we get

$\displaystyle L_{i}$
$\displaystyle\leq(\bm{G}{\bm{y}})_{i}+\sum_{g\in\mathcal{H}_{i}}\left(V^{*}_{g}+\frac{\eta\xi}{10P}f(g)+\frac{\eta\xi}{20P^{2}}\right)$
$\displaystyle\leq(\bm{G}{\bm{y}}^{*})_{i}+\frac{\eta\xi}{20P^{2}}+\sum_{g\in\mathcal{H}_{i}}\left(V^{*}_{g}+\frac{\eta\xi}{10P}f(g)+\frac{\eta\xi}{20P^{2}}\right)$
($\|{\bm{y}}-{\bm{y}}^{*}\|_{1}\leq\frac{\eta\xi}{10P^{2}}$)
$\displaystyle\leq(\bm{G}{\bm{y}}^{*})_{i}+\sum_{g\in\mathcal{H}_{i}}\left(V^{*}_{g}+\frac{\eta\xi}{10P}f(g)+\frac{\eta\xi}{10P^{2}}\right)$
($i$ is nonterminal)
$\displaystyle=(\bm{G}{\bm{y}}^{*})_{i}+\sum_{g\in\mathcal{H}_{i}}V^{*}_{g}+\frac{\eta\xi}{10P}\sum_{g\in\mathcal{H}_{i}}\left(f(g)+\frac{1}{P}\right)$
$\displaystyle\leq
V^{*}_{h}+\frac{\eta\xi}{10P}\sum_{g\in\mathcal{H}_{i}}\left(f(g)+\frac{1}{P}\right)$
(Lemma 13) $\displaystyle\leq V^{*}_{h}+\frac{\eta\xi}{10P}f(h(i)),$ (Eq.
(48))

which shows Eq. (47) by induction, and thus shows Eq. (45). ∎

######  Lemma 23.

Define $f:\mathcal{H}^{\mathcal{X}}\to\mathbb{R}^{+}$ as follows.

$\displaystyle f(g)=\left\\{\begin{aligned} &1,&&\text{if $\Omega_{g}$
contains terminal indices only;}\\\
&\max_{k\in\Omega_{g}}\sum_{s\in\mathcal{H}_{k}}\left(f(s)+\frac{1}{P}\right),&&\text{otherwise.}\end{aligned}\right.$

Then for every $g\in\mathcal{H}^{\mathcal{X}}$, we have

$\displaystyle f(g)\leq I_{g}\left(1+\frac{1}{P}\right),$ (50)

where $I_{g}$ is the number of indices that are the descendants of $g$ (we say
that index $j$ is a descendant of simplex $g$ if $j\in\Omega_{g}$ or index $j$
is a descendant of index $i$ for some $i\in\Omega_{g}$).

###### Proof.

If $\Omega_{g}$ contains terminal indices only, since $I_{g}\geq 1$, Eq. (50)
holds. Otherwise, suppose Eq. (50) holds for all simplexes that are
descendants of $g$ (we say that simplex $h$ is a descendant of simplex $g$ if
there exists a sequence of simplexes $s_{0},\dots,s_{K}$ for some $K>0$ such
that $s_{0}=h$, $s_{K}=g$, and $\sigma({s_{k-1}})\in\Omega_{s_{k}}$ for every
$k\in[K]$). We define

$k^{*}=\operatorname*{argmax}_{k\in\Omega_{g}}\sum_{s\in\mathcal{H}_{k}}\left(f(s)+\frac{1}{P}\right).$

Then we have

$\displaystyle f(g)$
$\displaystyle=\sum_{s\in\mathcal{H}_{k^{*}}}\left(f(s)+\frac{1}{P}\right)$
(by definition of $f$)
$\displaystyle\leq\sum_{s\in\mathcal{H}_{k^{*}}}\left[I_{s}\left(1+\frac{1}{P}\right)+\frac{1}{P}\right]$
(by assumption) $\displaystyle\leq
1+\sum_{s\in\mathcal{H}_{k^{*}}}\left[I_{s}\left(1+\frac{1}{P}\right)\right]$
($|\mathcal{H}_{k^{*}}|\leq P$)
$\displaystyle\leq(I_{g}-1)\left(1+\frac{1}{P}\right)+{1}$ $\displaystyle\leq
I_{g}\left(1+\frac{1}{P}\right),$

where the third inequality is because $k^{*}$ is not a descendant of any
$s\in\mathcal{H}_{k^{*}}$, and thus

$\sum_{s\in\mathcal{H}_{k^{*}}}I_{s}\leq I_{g}-1.$

Therefore, we show Eq. (50) by induction. ∎

####  E.5.2 The Counterpart of Eq. (11) for DOMWU

With Lemma 22, we can prove the following lemma, the counterpart of Eq. (11)
for DOMWU.

######  Lemma 24.

Under the uniqueness assumption, there exists a constant $C_{14}>0$ that
depends on the game, $\eta$, and $\widehat{\bm{z}}_{1}$ such that for any
$t\geq 1$, DOMWU with step size $\eta\leq\frac{1}{8P}$ guarantees

$\displaystyle
D_{\Psi^{\text{dil}}_{{\bm{\alpha}}}}(\widehat{\bm{z}}_{t+1},{\bm{z}}_{t})+D_{\Psi^{\text{dil}}_{{\bm{\alpha}}}}({\bm{z}}_{t},\widehat{\bm{z}}_{t})\geq
C_{14}D_{\Psi^{\text{dil}}_{{\bm{\alpha}}}}({\bm{z}}^{*},\widehat{\bm{z}}_{t+1})$

as long as
$\max\\{\|{\bm{z}}^{*}-\widehat{\bm{z}}_{t}\|_{1},\|{\bm{z}}^{*}-{\bm{z}}_{t}\|_{1}\\}\leq\frac{\eta^{2}\xi\epsilon_{\text{dil}}^{2}}{40P^{3}\|{\bm{\alpha}}\|_{\infty}}$.

###### Proof.

We define $\alpha_{\min}=\min_{h\in\mathcal{H}^{\mathcal{Z}}}\alpha_{h}>0$.
Note that

$\displaystyle
D_{\Psi^{\text{dil}}_{{\bm{\alpha}}}}(\widehat{\bm{z}}_{t+1},{\bm{z}}_{t})+D_{\Psi^{\text{dil}}_{{\bm{\alpha}}}}({\bm{z}}_{t},\widehat{\bm{z}}_{t})$
$\displaystyle=\sum_{g\in\mathcal{H}^{\mathcal{Z}}}\alpha_{g}\cdot\widehat{z}_{t+1,\sigma(g)}\text{\rm
KL}(\widehat{\bm{q}}_{t+1,g},{\bm{q}}_{t,g})+\alpha_{g}\cdot
z_{t,\sigma(g)}\text{\rm KL}({\bm{q}}_{t,g},\widehat{\bm{q}}_{t,g})$ (Eq.
(24))
$\displaystyle\geq\alpha_{\min}\sum_{g\in\mathcal{H}^{\mathcal{Z}}}\widehat{z}_{t+1,\sigma(g)}\text{\rm
KL}(\widehat{\bm{q}}_{t+1,g},{\bm{q}}_{t,g})+z_{t,\sigma(g)}\text{\rm
KL}({\bm{q}}_{t,g},\widehat{\bm{q}}_{t,g})$
$\displaystyle\geq\alpha_{\min}\epsilon_{\text{dil}}\sum_{g\in\mathcal{H},~{}\sigma(g)\in\text{supp}({\bm{z}}^{*})}\text{\rm
KL}(\widehat{\bm{q}}_{t+1,g},{\bm{q}}_{t,g})+\text{\rm
KL}({\bm{q}}_{t,g},\widehat{\bm{q}}_{t,g})$ (Lemma 20 )
$\displaystyle\geq\frac{\alpha_{\min}\epsilon_{\text{dil}}}{3}\sum_{i\notin\text{supp}({\bm{z}}^{*}),p_{i}\in\text{supp}({\bm{z}}^{*})}\left(\frac{(\widehat{q}_{t+1,i}-q_{t,i})^{2}}{\widehat{q}_{t+1,i}}+\frac{(q_{t,i}-\widehat{q}_{t,i})^{2}}{q_{t,i}}\right)$
([Wei et al., 2021, Lemma 18])
$\displaystyle\geq\frac{\alpha_{\min}\epsilon_{\text{dil}}}{4}\sum_{i\notin\text{supp}({\bm{z}}^{*}),p_{i}\in\text{supp}({\bm{z}}^{*})}\left(\frac{(\widehat{q}_{t+1,i}-q_{t,i})^{2}}{\widehat{q}_{t,i}}+\frac{(q_{t,i}-\widehat{q}_{t,i})^{2}}{\widehat{q}_{t,i}}\right)$
(Lemma 18)
$\displaystyle\geq\frac{\alpha_{\min}\epsilon_{\text{dil}}}{8}\sum_{i\notin\text{supp}({\bm{z}}^{*}),p_{i}\in\text{supp}({\bm{z}}^{*})}\frac{(\widehat{q}_{t+1,i}-\widehat{q}_{t,i})^{2}}{\widehat{q}_{t,i}}.$
(51)

Below we continue to bound
$\sum_{i\notin\text{supp}({\bm{z}}^{*}),p_{i}\in\text{supp}({\bm{z}}^{*})}\frac{(\widehat{q}_{t+1,i}-\widehat{q}_{t,i})^{2}}{\widehat{q}_{t,i}}$.

By the assumption, we have $\|\widehat{\bm{q}}_{t}-{\bm{q}}^{*}\|_{1}\leq
P\|\widehat{\bm{z}}_{t}-{\bm{z}}^{*}\|_{1}/\epsilon_{\text{dil}}^{2}\leq\frac{\eta\xi}{10\alpha_{i}}$
and for index $i$ such that $i\notin\text{supp}({\bm{x}}^{*})$ and
$p_{i}\in\text{supp}({\bm{x}}^{*})$,

$\displaystyle\sum_{j\in\Omega_{h(i)},j\notin\text{supp}({\bm{x}}^{*})}\widehat{q}_{t,j}\leq\frac{\eta\xi}{10\alpha_{i}}.$
(52)

Moreover, by Lemma 22, we have (denote $h=h(i)$)

$\displaystyle\widehat{q}_{t+1,i}$
$\displaystyle=\frac{\widehat{q}_{t,i}\exp(-\eta\widehat{L}_{i}/\alpha_{i})}{\sum_{j\in\Omega_{h}}\widehat{q}_{t,j}\exp(-\eta\widehat{L}_{j}/\alpha_{i})}\leq\frac{\widehat{q}_{t,i}\exp(-\eta\widehat{L}_{i}/\alpha_{i})}{\sum_{j\in\Omega_{h}\cap\text{supp}({\bm{z}}^{*})}\widehat{q}_{t,j}\exp(-\eta\widehat{L}_{j}/\alpha_{i})}$
$\displaystyle\leq\frac{\widehat{q}_{t,i}\exp(-\eta(V^{*}_{h}+\frac{9\xi}{10})/\alpha_{i})}{\sum_{j\in\Omega_{h}\cap\text{supp}({\bm{z}}^{*})}\widehat{q}_{t,j}\exp(-\eta(V^{*}_{h}+\frac{\xi}{10})/\alpha_{i})}$
(Lemma 22)
$\displaystyle=\frac{\widehat{q}_{t,i}\exp\left(-\frac{8}{10}\eta\xi/\alpha_{i}\right)}{\left(1-\sum_{j\in\Omega_{h},j\notin\text{supp}({\bm{z}}^{*})}\widehat{q}_{t,j}\right)}$
$\displaystyle\leq\frac{\widehat{q}_{t,i}\exp\left(-\frac{8}{10}\eta\xi/\alpha_{i}\right)}{\left(1-\frac{\eta\xi/\alpha_{i}}{10}\right)}$
(Eq. (52))
$\displaystyle\leq\widehat{q}_{t,i}\left(1-\frac{1}{2}\frac{\eta\xi}{\alpha_{i}}\right).$
($\frac{\exp(-0.8u)}{1-0.1u}\leq 1-0.5u$ for $u\in[0,1]$)

Rearranging gives

$\displaystyle\frac{|\widehat{q}_{t+1,i}-\widehat{q}_{t,i}|^{2}}{\widehat{q}_{t,i}}\geq\frac{\eta^{2}\xi^{2}}{4\|{\bm{\alpha}}\|_{\infty}^{2}}\widehat{q}_{t,i}\geq\frac{\eta^{2}\xi^{2}}{8\|{\bm{\alpha}}\|_{\infty}^{2}}\widehat{q}_{t+1,i},$

where the last step uses Lemma 18. The case for $\widehat{\bm{y}}_{t}$ is
similar. Combining this with Eq. (51), we get

$\displaystyle
D_{\Psi^{\text{dil}}_{{\bm{\alpha}}}}(\widehat{\bm{z}}_{t+1},{\bm{z}}_{t})+D_{\Psi^{\text{dil}}_{{\bm{\alpha}}}}({\bm{z}}_{t},\widehat{\bm{z}}_{t})$
$\displaystyle\geq
C_{12}^{\prime}\sum_{i\notin\text{supp}({\bm{z}}^{*}),p_{i}\in\text{supp}({\bm{z}}^{*})}\widehat{q}_{t+1,i}$
$\displaystyle\geq
C_{12}^{\prime}\sum_{i\notin\text{supp}({\bm{z}}^{*})}z_{p_{i}}^{*}\widehat{q}_{t+1,i}$
(53)

for some $C_{12}^{\prime}>0$. Now we combine two lower bounds of
$D_{\Psi^{\text{dil}}_{{\bm{\alpha}}}}(\widehat{\bm{z}}_{t+1},{\bm{z}}_{t})+D_{\Psi^{\text{dil}}_{{\bm{\alpha}}}}({\bm{z}}_{t},\widehat{\bm{z}}_{t})$.
Using Lemma 12 and Eq. (53), we get

$\displaystyle
D_{\Psi^{\text{dil}}_{{\bm{\alpha}}}}(\widehat{\bm{z}}_{t+1},{\bm{z}}_{t})+D_{\Psi^{\text{dil}}_{{\bm{\alpha}}}}({\bm{z}}_{t},\widehat{\bm{z}}_{t})$
$\displaystyle=\frac{1}{2}\left(D_{\Psi^{\text{dil}}_{{\bm{\alpha}}}}(\widehat{\bm{z}}_{t+1},{\bm{z}}_{t})+D_{\Psi^{\text{dil}}_{{\bm{\alpha}}}}({\bm{z}}_{t},\widehat{\bm{z}}_{t})\right)+\frac{1}{2}\left(D_{\Psi^{\text{dil}}_{{\bm{\alpha}}}}(\widehat{\bm{z}}_{t+1},{\bm{z}}_{t})+D_{\Psi^{\text{dil}}_{{\bm{\alpha}}}}({\bm{z}}_{t},\widehat{\bm{z}}_{t})\right)$
$\displaystyle\geq\frac{C_{12}}{2}\|{\bm{z}}^{*}-\widehat{\bm{z}}_{t+1}\|_{1}^{2}+\frac{C_{12}^{\prime}}{2}\sum_{i\notin\text{supp}({\bm{z}}^{*})}z_{p_{i}}^{*}\widehat{q}_{t+1,i}.$
(54)

Also note that by Lemma 17, we have

$\displaystyle
D_{\Psi^{\text{dil}}_{{\bm{\alpha}}}}({\bm{z}}^{*},\widehat{\bm{z}}_{t+1})$
$\displaystyle\leq\|{\bm{\alpha}}\|_{\infty}\left(\sum_{i\in\text{supp}({\bm{z}}^{*})}\frac{4P}{z_{i}^{*}}\frac{\left({z^{*}_{i}-\widehat{z}_{t+1,i}}\right)^{2}}{\widehat{q}_{t+1,i}}+\sum_{i\notin\text{supp}({\bm{z}}^{*})}z_{p_{i}}^{*}\widehat{q}_{t+1,i}\right)$
$\displaystyle\leq\frac{4\|{\bm{\alpha}}\|_{\infty}P}{\epsilon_{\text{dil}}^{2}}\left(\sum_{i\in\text{supp}({\bm{z}}^{*})}{\left({z^{*}_{i}-\widehat{z}_{t+1,i}}\right)^{2}}+\sum_{i\notin\text{supp}({\bm{z}}^{*})}z_{p_{i}}^{*}\widehat{q}_{t+1,i}\right).$
(Lemma 20)

Combining this with Eq. (54), we conclude that

$\displaystyle
D_{\Psi^{\text{dil}}_{{\bm{\alpha}}}}(\widehat{\bm{z}}_{t+1},{\bm{z}}_{t})+D_{\Psi^{\text{dil}}_{{\bm{\alpha}}}}({\bm{z}}_{t},\widehat{\bm{z}}_{t})$
$\displaystyle\geq\frac{\min\\{C_{12},C_{12}^{\prime}\\}}{2}\left(\|{\bm{z}}^{*}-\widehat{\bm{z}}_{t+1}\|_{1}^{2}+\sum_{i\notin\text{supp}({\bm{z}}^{*})}z_{p_{i}}^{*}\widehat{q}_{t+1,i}\right)$
$\displaystyle\geq\frac{\epsilon_{\text{dil}}^{2}}{8\|{\bm{\alpha}}\|_{\infty}P}\min\left\\{C_{12},C_{12}^{\prime}\right\\}D_{\Psi^{\text{dil}}_{{\bm{\alpha}}}}({\bm{z}}^{*},\widehat{\bm{z}}_{t+1}),$

which finishes the proof.

∎

####  E.5.3 Proof of Theorem 7

With Lemma 24, we are ready to prove Theorem 7.

###### Proof of Theorem 7.

Set $T_{0}=\frac{64C_{13}^{\prime}}{c^{2}}$, where
$c=\frac{\eta^{2}\xi\epsilon_{\text{dil}}^{2}}{40P^{3}\|{\bm{\alpha}}\|_{\infty}}$.
For $t\geq T_{0}$, we have using Theorem 21,

$\displaystyle\|{\bm{z}}^{*}-\widehat{\bm{z}}_{t}\|_{1}^{2}$
$\displaystyle\leq
2D_{\Psi^{\text{dil}}_{{\bm{\alpha}}}}({\bm{z}}^{*},\widehat{\bm{z}}_{t})\leq\frac{2C_{13}^{\prime}}{T_{0}}\leq
c^{2},$ $\displaystyle\|{\bm{z}}^{*}-{\bm{z}}_{t}\|_{1}^{2}$
$\displaystyle\leq
2\|{\bm{z}}^{*}-\widehat{\bm{z}}_{t+1}\|_{1}^{2}+2\|\widehat{\bm{z}}_{t+1}-{\bm{z}}_{t}\|_{1}^{2}$
$\displaystyle\leq
4D_{\Psi^{\text{dil}}_{{\bm{\alpha}}}}({\bm{z}}^{*},\widehat{\bm{z}}_{t+1})+4D_{\Psi^{\text{dil}}_{{\bm{\alpha}}}}(\widehat{\bm{z}}_{t+1},{\bm{z}}_{t})$
$\displaystyle\leq 64\Theta_{t+1}\leq\frac{64C_{13}^{\prime}}{T_{0}}\leq
c^{2}.$

Therefore, when $t\geq T_{0}$, the condition of the second part of Lemma 24 is
satisfied, and we have

$\displaystyle\zeta_{t}$
$\displaystyle\geq\frac{1}{2}D_{\Psi^{\text{dil}}_{{\bm{\alpha}}}}(\widehat{\bm{z}}_{t+1},{\bm{z}}_{t})+\frac{1}{2}\zeta_{t}$
$\displaystyle\geq\frac{1}{2}D_{\Psi^{\text{dil}}_{{\bm{\alpha}}}}(\widehat{\bm{z}}_{t+1},{\bm{z}}_{t})+\frac{C_{14}}{2}D_{\Psi^{\text{dil}}_{{\bm{\alpha}}}}({\bm{z}}^{*},\widehat{\bm{z}}_{t+1})$
(by Lemma 24) $\displaystyle\geq C_{15}\Theta_{t+1}.$

for some constant $C_{15}>0$. Therefore, when $t\geq T_{0}$,
$\Theta_{t+1}\leq\Theta_{t}-\frac{15}{16}C_{15}\Theta_{t+1}$, which further
leads to

$\Theta_{t}\leq\Theta_{T_{0}}\cdot\left(1+\frac{15}{16}C_{15}\right)^{T_{0}-t}\leq\Theta_{1}\cdot\left(1+\frac{15}{16}C_{15}\right)^{T_{0}-t}=D_{\Psi^{\text{dil}}_{{\bm{\alpha}}}}({\bm{z}}^{*},\widehat{\bm{z}}_{1})\cdot\left(1+\frac{15}{16}C_{15}\right)^{T_{0}-t},$

where the second inequality uses Eq. (43). The inequality trivially holds for
$t<T_{0}$ as well, so it holds for all $t$. We finish the proof by relating
$D_{\Psi^{\text{dil}}_{{\bm{\alpha}}}}({\bm{z}}^{*},{\bm{z}}_{t})$ and
$\Theta_{t+1}$. Note that by Lemma 17,

$\displaystyle
D_{\Psi^{\text{dil}}_{{\bm{\alpha}}}}({\bm{z}}^{*},{\bm{z}}_{t})^{2}$
$\displaystyle\leq\frac{16P\|{\bm{\alpha}}\|_{\infty}^{2}}{\epsilon_{\text{dil}}^{4}}\|{\bm{z}}^{*}-{\bm{z}}_{t}\|_{1}^{2}$
$\displaystyle\leq\frac{32P\|{\bm{\alpha}}\|_{\infty}^{2}}{\epsilon_{\text{dil}}^{4}}\left(\|{\bm{z}}^{*}-\widehat{\bm{z}}_{t+1}\|_{1}^{2}+\|\widehat{\bm{z}}_{t+1}-{\bm{z}}_{t}\|_{1}^{2}\right)$
$\displaystyle\leq\frac{1024P\|{\bm{\alpha}}\|_{\infty}^{2}}{\epsilon_{\text{dil}}^{4}}\Theta_{t+1}.$

Therefore, we conclude

$\displaystyle
D_{\Psi^{\text{dil}}_{{\bm{\alpha}}}}({\bm{z}}^{*},{\bm{z}}_{t})\leq\sqrt{\frac{1024P\|{\bm{\alpha}}\|_{\infty}^{2}}{\epsilon_{\text{dil}}^{4}}\Theta_{t+1}}\leq\sqrt{\frac{1024P\|{\bm{\alpha}}\|_{\infty}^{2}D_{\Psi^{\text{dil}}_{{\bm{\alpha}}}}({\bm{z}}^{*},\widehat{\bm{z}}_{1})}{\epsilon_{\text{dil}}^{4}}}\left(1+\frac{15}{16}C_{15}\right)^{\frac{T_{0}-t-1}{2}},$

which finishes the proof by setting

$C_{3}=\sqrt{\frac{1024P\|{\bm{\alpha}}\|_{\infty}^{2}D_{\Psi^{\text{dil}}_{{\bm{\alpha}}}}({\bm{z}}^{*},\widehat{\bm{z}}_{1})}{\epsilon_{\text{dil}}^{4}}}\left(1+\frac{15}{16}C_{15}\right)^{\frac{T_{0}-1}{2}},~{}C_{4}=\left(1+\frac{15}{16}C_{15}\right)^{\frac{1}{2}}-1.$

∎

###  E.6 Remarks on DOGDA

In this subsection, we discuss the technical difficulties to get a convergence
rate for DOGDA. This is challenging even if we assume the uniqueness of the
Nash equilibrium. From the analysis of VOMWU and DOMWU, we can see that Lemma
19 and Lemma 20 play an important role. The lemmas lower bound
$\widehat{z}_{t,i}$ with some game-dependent constants for $i$ in
$\text{supp}({{\bm{z}}^{*}})$, and the proofs are based on the observation
that $D_{\Psi^{\text{van}}}({\bm{z}}^{*},{\bm{z}})$ and
$D_{\Psi^{\text{dil}}_{{\bm{\alpha}}}}({\bm{z}}^{*},{\bm{z}})$ approach
infinity as $z_{i}$ approaches zero for $i\in\text{supp}({\bm{z}}^{*})$. This
property of the entropy regularizers, however, does not hold for the dilated
Euclidean regularizer $\Phi^{\text{dil}}_{{\bm{\alpha}}}$ in general. Lower
bounding $\widehat{z}_{t,i}$ for DOGDA could be possible when
$\widehat{\bm{z}}_{t}$ is sufficiently close to ${\bm{z}}^{*}$. For example,
when

$\|\widehat{\bm{z}}_{t}-{\bm{z}}^{*}\|\leq\frac{1}{2}\min_{i\in\text{supp}({\bm{z}}^{*})}z^{*}_{i},$

we can lower bound $\widehat{z}_{t,i}$ by
$\frac{1}{2}\min_{i\in\text{supp}({\bm{z}}^{*})}z^{*}_{i}$ for
$i\in\text{supp}({\bm{z}}^{*})$. This must happen when $t$ is large by Theorem
4, but the entire analysis will then depend on a potentially large
“asymptotic” constant. Therefore, even though we know that asymptotically,
DOGDA has linear convergence, getting a concrete rate as VOMWU and DOMWU is
still an open question.

Another direction is to follow the analysis of VOGDA, which gives a linear
convergence rate by Corollary 5. However, in the analysis of VOGDA, Wei et al.
[2021] implicitly use the fact that $\Phi^{\text{van}}$ is $\beta$-smooth,
that is,

$D_{\Phi^{\text{van}}}({\bm{z}},{\bm{z}}^{\prime})\leq\frac{\beta}{2}\|{\bm{z}}-{\bm{z}}^{\prime}\|^{2},$

for some $\beta>0$. In fact, $\Phi^{\text{van}}$ is $1$-smooth. This property,
unfortunately, does not hold for $\Phi^{\text{dil}}_{{\bm{\alpha}}}$. We
believe one can still show that $\Phi^{\text{dil}}_{{\bm{\alpha}}}$ is
$\beta$-smooth for some game-dependent $\beta$ once $\widehat{\bm{z}}_{t}$ is
sufficiently close to ${\bm{z}}^{*}$. However, this again involves the
asymptotic result in Theorem 4 and may prevent us from getting a concrete
rate. In summary, using the existing techniques, we met some difficulties to
obtain a concrete convergence rate for DOGDA. However, DOGDA performs well in
the experiments. Moreover, it reduces to VOGDA in the normal-form games and
achieves linear convergence in this case. Therefore, we still believe that it
is a promising direction to get a (linear) convergence rate for DOGDA in
theory.