is optimal dual solution, we have that

$$ \Psi'_{\rho}(\mu^*)(\mu - \mu^*) \geq 0, \forall \mu \in [0, \bar{\mu}], $$

where the derivative of $\Psi_{\rho}$ is given by

$$ \Psi'_{\rho}(\mu) = \rho + \sum_{\theta \in \Theta} p_{\theta} g'_{\theta}(\mu) = \rho - \sum_{\theta \in \Theta} p_{\theta} \bar{m} \left( \beta \left( \frac{\theta}{1+\mu} \right) \right). \quad (\text{D-13}) $$

If $\mu^* = 0$, $\Psi'_{\rho}(0)\mu \geq 0$ and therefore $\Psi'_{\rho}(0) \geq 0$. Note that we also have $\Psi_{\rho}(\mu^*)\mu^* = 0$, and then primal feasibility and complementary slackness follows by (D-13) because $\sum_{\theta \in \Theta} p_{\theta} \bar{m} \left( \beta \left( \frac{\theta}{1+\mu^*} \right) \right)$ is the expected payment under the optimal bidding strategy.

If $\mu^* > 0$, there exists $\nu > 0$ such that $\mu^* + \nu$ and $\mu^* - \nu$ belongs to $[0, \bar{\mu}]$. Therefore both $\Psi'_{\rho}(\mu^*)\nu$ and $\Psi'_{\rho}(\mu^*)(-\nu)$ and non-negative, obtaining $\Psi'_{\rho}(\mu^*) = 0$, and primal feasibility and complementary slackness hold.

3. Lagrangian optimality. Note that

$$ \begin{aligned} \arg\max_{\phi \in \Phi} \mathcal{L}(\phi, \mu^*) &= \arg\max_{\phi \in \Phi} \left\{ \mu^* \rho + \sum_{\theta \in \Theta} p_{\theta} \int_{\mathcal{A}} (\theta \bar{q}(a) - (1+\mu^*) \bar{m}(a)) d\phi_{\theta}(a) \right\} \\ &= \left\{ \arg\max_{\phi_{\theta} \in \Delta(\mathcal{A})} \int_{\mathcal{A}} (\theta \bar{q}(a) - (1+\mu^*) \bar{m}(a)) d\phi_{\theta}(a) \right\}_{\theta \in \Theta} \\ &= \left\{ \arg\max_{a \in \mathcal{A}} g_{\theta}(a, \mu^*) \right\}_{\theta \in \Theta}, \end{aligned} $$

where the second equality holds because we can separate the problem for each $\theta$. But note that $g_{\theta}(a, \mu^*)$ is maximized at $a = \beta(\theta/(\mu^* + 1))$ and thus we have Lagrangian optimality.

Therefore, the four conditions holds and the proof is completed. □

If in addition Assumptions SC 7 and SC 8 hold, from Lemma 3 we obtain that Assumption 2 holds with $K = 1/\kappa$ and $\delta = (\nu\kappa)/2$. Below, we study the particular cases of second-price auction and first-price auction. Specifically, we provide sufficient conditions on the primitives of the problem for conditions SC 4 and SC 7 to be satisfied.

**Second-price auctions.** In a second-price auction, the bidder with the highest bid wins the auction and pays the second-highest bid. In this case, we reduce the definition of $\epsilon$ to a random variable capturing the maximum bid of the competitors and take $\mathcal{E} = \mathbb{R}_+$. Again, we assume
ϵ is distributed according to f, with density function f'. While the maximum competing bid ϵ is assumed to be independent of the values θ, our results can easily incorporate correlation (see Appendix A.1). Without loss, ties are broken in favor of the decision maker. The allocation and payment functions are given by $q(a, \epsilon) = 1_{\{a \ge \epsilon\}}$ and $m(a, \epsilon) = \epsilon 1_{\{a \ge \epsilon\}}$, respectively.

Suppose that the following conditions hold:

* The distribution of the maximum competing bid f is absolutely continuous and strictly increasing.

* The density f' is locally ξ-Lipschitz continuous with respect to $a_{\theta}^1$ in $N(a_{\theta}^1, \varphi)$, i.e., $|f'(a) - f'(a_\theta^1)| \le \xi|a - a_\theta^1|$ for all $a \in N(a_{\theta}^1, \varphi)$.

In the next Lemma, we show that these conditions are sufficient to apply Proposition 3 and Lemma 4 and, in turn, Corollary 3 holds. This leads to a revenue loss of logarithmic order in T.

**Lemma D-1.** If f absolutely continuous and strictly increasing and f' is locally ξ-Lipschitz continuous in $N(a_{\theta}^1, \varphi)$, then conditions SC 5-SC 11 hold.

*Proof.* Let us see that conditions SC 5- SC 11 hold.

* **Condition SC 5:** By hypothesis f is absolutely continuous and therefore both $\bar{q}$ and $\bar{m}$ are continuous.

* **Condition SC 6:** For each $\theta \in \Theta$, let us define the function $G_{\theta}: A \to \mathbb{R}$ by $G_{\theta}(a) = \theta f(a) - \int_{0}^{a} x df(x)$. Consider $\theta \in (0, \Theta_{\max})$. Note that $G'_{\theta}(a) = (\theta - a)f'(a)$. Because $\theta > 0$, then $\lim_{a \searrow 0} G'_{\theta}(a) > 0$ and $\beta(\theta) \ne 0$. Because $\theta \ne \Theta_{\max}$, we also have $\lim_{a \searrow \Theta_{\max}} G'_{\theta}(a) < 0$. Therefore, $\beta(\theta) \in \arg\max_a G_{\theta}(a)$ is interior and $\beta(\theta)$ satisfies the first-order condition

$$ (\theta - \beta(\theta))f'(\beta(\theta)) = 0. $$

Therefore, as the cumulative distribution function f is strictly increasing, the unique optimum is to bid truthfully, as it is known in the literature. We conclude that SC 6 holds because the optimal auction is interior almost surely.

* **Condition SC 9:** Due to the truthfulness property of the second price auction, from Proposition D-1, it follows that $a_{\theta}^1 = \theta/(1 + \mu^1)$ which belongs to $(0, \Theta_{\max})$ due to the fact that the bid is positive, and thus condition SC 9 holds.

* **Conditions SC 10 and SC 11:** Note first that $\bar{r}(\theta, a) = \theta f(a) - \bar{m}(\theta, a)$ and $\bar{y}(\theta, a) = \bar{m}(a)$, because f is absolutely continuous. Then, it is enough to show the conditions hold for
$h(\theta, \cdot) = \theta f(\cdot)$ and $\bar{m}(a) = \int_0^a x df(x)$. Specifically, we will show that if the density function $f'$ is locally $\xi$-Lipschitz continuous in $\mathcal{N}(a_\theta^1, \varphi)$, then the gradient of $h(\theta, \cdot) = \theta f(\cdot)$ is locally $(\xi\Theta_{\max})$-Lipschitz continuous in $\mathcal{N}(a_\theta^1, \varphi)$ and $\bar{m}'(a) = af'(a)$ is locally $((\varphi + \Theta_{\max})/(\mu^1 + 1))\xi + \eta$-Lipschitz continuous in $\mathcal{N}(a_\theta^1, \varphi)$.

To see the former note that

$$ \|\nabla_a h(\theta, a) - \nabla_a h(\theta, a_\theta^1)\| = \theta|f'(a) - f'(a_\theta^1)| \le \Theta_{\max}\xi|a - a_\theta^1|, $$

where the equality follows from the gradient of $h$ and the inequality holds due to the locally $\xi$-Lipschitz continuity of $f'$ and because $\theta \le \Theta_{\max}$.

For the latter, we first show that $f'(a_\theta^1) \le \eta$ with $\eta = 1/\varphi + \xi\varphi$. Because the density $f'$ is locally $\xi$-Lipschitz continuous in $\mathcal{N}(a_\theta^1, \varphi)$, we have that $f'(a_\theta^1) \le f'(x) + \xi\varphi$ for all $x \in [a_\theta^1, a_\theta^1 + \varphi]$. Integrating over $x \in [a_\theta^1, a_\theta^1 + \varphi]$ we obtain that $f'(a_\theta^1)\varphi \le 1 + \xi\varphi^2$ because $f'$ integrates to at most one. The result follows by dividing by $\varphi$. We now show that $\bar{m}'(a)$ is locally Lipschitz continuous:

$$ \begin{aligned} |\bar{m}'(a) - \bar{m}'(a_\theta^1)| &= |af(a) - a_\theta^1 f(a_\theta^1)| \\ &= |a[f'(a) - f'(a_\theta^1)] + f'(a_\theta^1)(a - a_\theta^1)| \\ &\le a|f'(a) - f'(a_\theta^1)| + f'(a_\theta^1)|a - a_\theta^1| \\ &\le \left(\left(\varphi + \frac{\Theta_{\max}}{\mu^1 + 1}\right)\xi + \eta\right)|a - a_\theta^1|, \end{aligned} $$

where the first inequality holds applying triangle inequality and the last follows from the bound of $f'(a_\theta^1)$, together with the locally $\xi$-Lipschitz continuity of $f'$, the equality $a_\theta^1 = \theta/(1 + \mu^1)$ and the bound $a_\theta^1 \le \Theta_{\max}$. The proof is completed. $\square$

**First-price auctions.** In a first-price auction, the winner is the highest bidder but pays his bid. Again, we reduce the definition of $\epsilon$ to a random variable capturing the maximum bid of the competitors. We assume $\epsilon$ is distributed according to $f$, with density function $f'$. The allocation and payment functions are given by $q(a, \epsilon) = 1_{\{a \ge \epsilon\}}$ and $m(a, \epsilon) = a1_{\{a \ge \epsilon\}}$, respectively.

Suppose the following conditions hold:

* The distribution of the maximum competing bid $f$ is absolutely continuous.

* The function $M(a) = a + f(a)/f'(a)$ is strictly increasing.

* The bid $a_\theta^1$ maximizing $\theta\bar{q}(a) - (1+\mu^1)\bar{m}(a)$ is interior. That is, there exists a positive number $\varphi$ such that $\mathcal{N}(a_\theta^1, \varphi) \subset \mathcal{A}$ for all $\theta \in \Theta$.
• The density $f'$ is locally $\xi$-Lipschitz continuous with respect to $a_{\theta}^1$ in $\mathcal{N}(a_{\theta}^1, \varphi)$.

Moreover, we show in the next Lemma that if we have $\mu^1 > 0$, then assumptions SC 5-SC 11 hold and, therefore, by Corollary 3 we obtain a revenue loss of logarithmic order in $T$.

**Lemma D-2.** If $f$ absolutely continuous, $M(a) = a + f(a)/f'(a)$ strictly increasing, the bid $a_{\theta}^1$ maximizing $\theta \bar{q}(a) - (\mu^1 + 1) \bar{m}(a)$ is interior, and the density function $f'$ is locally $\xi$-Lipschitz in $\mathcal{N}(a_{\theta}^1, \varphi)$, and $f'(a_{\theta}^1)$ is upper bounded by $\eta$, conditions SC 5-SC 11 hold.

*Proof.* As in the lemma for second-price auctions, condition SC 5 holds because $f$ is absolutely continuous. On the other hand, the bidder's problem in the static first price auction without budget constraints is to find a bid function $\beta(\theta)$ maximizing $(\theta - a)f(a)$. Note that $\arg\max \theta f(a) - af(a) = \arg\max \theta' f(a) - (\mu^1 + 1)af(a)$, where $\theta' = \theta/(\mu^1 + 1)$, is interior by hypothesis and then, computing the first order condition, we obtain that $\beta(\theta)$ should satisfy

$$f'(\beta(\theta))\theta - f(\beta(\theta)) - \beta(\theta)f'(\beta(\theta)) = 0. \qquad (\text{D-14})$$

Then, we have $\theta = \beta(\theta) + f(\beta(\theta))/f'(\beta(\theta)) = M(\beta(\theta))$ and by hypothesis we can compute the inverse of $M$ and therefore $\beta(\theta) = M^{-1}(\theta)$. Thus, payments at the optimal solution are unique and assumption SC 6 holds.

Note that condition SC 9 is directly assumed in the statement of the lemma, and therefore it holds.

It remains to see smoothness of both the expected reward $\bar{r}(\theta, a) = (\theta - a)f(a)$ and expected payment $\bar{y}(a) = af(a)$ functions, but it is enough to show that the gradient of $\bar{y}(\theta, a)$ is locally Lipschitz continuous. To this end, note that

$$|\nabla_a \bar{y}(\theta, a)| = |f(a) + af(a) - f(a_\theta^1) - a_\theta^1 f(a_\theta^1)| \le |f(a) - f(a_\theta^1)| + |af(a) - a_\theta^1 f'(a_\theta^1)|,$$

where the last expression in the inequality can be bound by using the local Lipschitz continuity of $f'$ together with the upper bound for $f'$ (as in the case of the second-price action, we have that $f'(a_\theta^1)$ is bounded) by using the mean value theorem. The remaining algebra is similar to the second-price case and the proof is completed. $\square$

## D.3 Network Revenue Management

Here, in contrast to the two problems exposed before, the set of actions is finite (binary).
In the case of finite customer classes (contexts), Problem (6) can be written as follows

$$ \bar{J}(\rho) = \max_{\phi_{\theta}(1) \in [0,1]} \sum_{\theta \in \Theta} p_{\theta} r_{\theta} \phi_{\theta}(1) \\ \text{s.t} \quad \sum_{\theta \in \Theta} p_{\theta} Q_{\theta} \phi_{\theta}(1) \leq \rho. \qquad (D-15) $$

Because the set of actions consists of $\mathcal{A} = \{0,1\}$, it is enough to consider decision variables $\phi_{\theta}(1)$ for all $\theta \in \Theta$ because $\phi_{\theta}(0) = 1 - \phi_{\theta}(1)$. Removing the variable $\phi_{\theta}(0)$ from the fluid problem requires a slight change in the statement of Lemma 1. In the standard form representation of the problem, the constraint matrix is $Q = (\tilde{Q}, I) \in \mathbb{R}^{(L+|\Theta|) \times (L+2|\Theta|)}$ where $\tilde{Q} \in \mathbb{R}^{(L+|\Theta|) \times |\Theta|}$ is the constraint matrix associated to the decision variables $(\phi_{\theta}(1))_{\theta \in \Theta}$ and the identity matrix $I \in \mathbb{R}^{(L+|\Theta|) \times (L+|\Theta|)}$ is associated to the slack variables of the resource constraints and the constraints $\phi_{\theta}(1) \leq 1$. The $\theta$-th column of $\tilde{Q}$ consists of the vector $(p_{\theta}Q_{\theta})_{e_{\theta}}^{n}$, where $e_{\theta} \in \mathbb{R}^{|\Theta|}$ is the canonical vector. Let $B$ be the submatrix of $Q$ corresponding to the columns associated to the basic variables at an optimal solution, and $B_{\rho_1}^{-1}$ the submatrix of $B^{-1}$ associated to the resource constraints. Then, under Assumption SC 1, Assumption 2 holds with $K = 0$ and $\delta = \min\{\phi_{\min}^*, x_{\min}^*\} / \|B_{\rho_1}^{-1}\|$, where $x_{\min}^* = \min_{l \in [L]} \{x_l^* : x_l^* > 0\}$ and $x_l^* = \rho_l - \sum_{\theta \in \Theta} p_{\theta} Q_{\theta l} \phi_{\theta}^*(1)$ is the slack of the $l$-th resource constraint. In the definition of $\phi_{\min}^*$ we now take into account how close the controls are to both zero and one. That is, $\phi_{\min}^* = \min_{\theta \in \Theta} \{\phi_{\theta}^*(1) : \phi_{\theta}^*(1) > 0\} \wedge \min_{\theta \in \Theta} \{1 - \phi_{\theta}^*(1) : \phi_{\theta}^*(1) < 1\}$, where $x \wedge y$ denotes the minimum between $x$ and $y$.

## D.4 Choice-Based Network Revenue Management

In this case, the set of actions is finite and the fluid problem can be expressed as

$$ \bar{J}(\rho) = \max_{\phi \in \Phi} \sum_{\theta \in \Theta} \sum_{a \in \mathcal{A}} \phi_{\theta}(a) p_{\theta} \sum_{n \in [N]} f_n g_{\theta a}^n \\ \text{s.t} \quad \sum_{\theta \in \Theta} \sum_{a \in \mathcal{A}} \phi_{\theta}(a) p_{\theta} \sum_{n \in [N]} Q_{\theta}^n g_{\theta a}^n \leq \rho. \qquad (D-16) $$

We can define the vector of variables and the associated matrix involved in the constraints of problem (D-16) by setting each column to $p_{\theta} \sum_{n \in [N]} Q_{\theta}^n g_{\theta a}^n$. Then, under Assumption SC 1, we can apply Lemma 1 and Assumption 2 holds for $K = 0$ and $\delta$ defined as in the statement of the lemma. Therefore, we obtain a constant bound on the revenue loss of the CE heuristic for the choice-based network revenue management problem.
## D.5 Online Matching

First, note that the fluid problem is given by

$$ 
\begin{aligned}
\bar{J}(\rho) = & \max_{\phi \ge 0} \sum_{\theta \in \Theta} \sum_{a \in [L]} \phi_{\theta}(a) p_{\theta} f_{\theta a} \\
& \text{s.t} \quad \sum_{\theta \in \Theta} p_{\theta} \operatorname{diag}(Q_{\theta}) \phi_{\theta} \le \rho \\
& \qquad \sum_{a \in [L]} \phi_{\theta}(a) \le 1 \quad \forall \theta \in \Theta,
\end{aligned}
\quad (D-17) $$

where $\phi_{\theta}^{\top} = (\phi_{\theta}(1), \dots, \phi_{\theta}(L))$ and where for a vector $x \in \mathbb{R}^L$, $\operatorname{diag}(x) \in \mathbb{R}^{L \times L}$ is a diagonal matrix with diagonal entry $i$ given by $x_i$.

Here, as in the network revenue management problem, we need a slight change in the statement of Lemma 1 because we removed the decision variable associated to the action $a = 0$. In the standard form representation of the problem, the constraint matrix is $Q = \begin{pmatrix} Q_1 \\ Q_2 \end{pmatrix} \in \mathbb{R}^{(L+|\Theta|) \times (L|\Theta|+L+|\Theta|)}$ where $Q_1 \in \mathbb{R}^{L \times (L|\Theta|+L+|\Theta|)}$ is the matrix associated to the resource constraints and $Q_2 \in \mathbb{R}^{|\Theta| \times (L|\Theta|+L+|\Theta|)}$ is the matrix associated to the constraints $\sum_{a \in [L]} \phi_{\theta}(a) \le 1$. The matrix $Q_1$ is obtained by horizontally stacking the matrices $\operatorname{diag}(p_{\theta}Q_{\theta}) \in \mathbb{R}^{L \times L}$, the identity matrix $I \in \mathbb{R}^{L \times L}$, and the zero matrix $0 \in \mathbb{R}^{L \times |\Theta|}$. The matrix $Q_2 \in \mathbb{R}^{|\Theta| \times (L|\Theta|+L+|\Theta|)}$ is obtained by horizontally stacking the matrices $e_1, e_2, \dots, e_{|\Theta|}, 0 \in \mathbb{R}^{|\Theta| \times L}$ and the identity matrix $I \in \mathbb{R}^{|\Theta|}$, where $e_{\theta} \in \mathbb{R}^{|\Theta| \times L}$ is the matrix with all columns equal to the $\theta$-th canonical vector of $\mathbb{R}^{|\Theta|}$. Let $B$ be the submatrix of $Q$ corresponding to the columns associated to the basic variables at an optimal solution, and $B_{\rho_1}^{-1}$ the submatrix of $B^{-1}$ associated to the resource constraints. Then, if the problem (D-17) has a non-degenerate optimal solution for $\rho = \rho_1$, Assumption 2 holds with $K = 0$ and $\delta = \min\{\phi_{\min}^{*}, x_{\min}^{*}\} / \|B_{\rho_1}^{-1}\|$, where $\phi_{\min}^{*} = \min_{\theta \in \Theta, a \in [L]} \{\phi_{\theta}^{*}(a) : \phi_{\theta}^{*}(a) > 0\} \wedge \min_{\theta \in \Theta} \{1 - \sum_{a \in [L]} \phi_{\theta}^{*}(a) : \sum_{a \in [L]} \phi_{\theta}^{*}(a) < 1\}$, $x_{\min}^{*} = \min_{l \in [L]} \{x_l^{*} : x_l^{*} > 0\}$ and $x_l^{*} = \rho_l - \sum_{\theta \in \Theta} p_{\theta} Q_{\theta l} \phi_{\theta}^{*}(l)$ is the slack of the $l$-th resource constraint, and the constant bound for the revenue loss is obtained.

## D.6 Order Fulfillment

In this case, the fluid problem can be expressed as follows

$$ 
\begin{aligned}
\bar{J}(\rho) = & \max_{\phi \in \Phi} \sum_{\theta \in \Theta} \sum_{a \in A} p_{\theta} \phi_{\theta}(a) \sum_{l \in \theta} \sum_{n \in N} f_{ln} 1_{\{a_l=n\}} \\
& \text{s.t} \quad \sum_{\theta \in \Theta} \sum_{a \in A} p_{\theta} \phi_{\theta}(a) 1_{\{a_l=n\}} \le \rho_{ln}.
\end{aligned}
\quad (D-18) $$

As in the previous problems, we can write the constraints of problem (D-18) in matrix form and,
thus, obtain an expression for $\delta$ involved in the assumption. We do not give an explicit formula for $\delta$ here to avoid introducing more notation. Moreover, if problem (D-18) has a non-degenerate optimal solution for $\rho = \rho_1$, Assumption 2 holds with $K = 0$ and we recover a constant revenue loss bound for the order fulfillment problem.

## E Auxiliary Results

The following lemma is a technical result we need to prove Lemma B-3.

**Lemma E-1.** For every $a > 1, b > 0$ we have

$$ \int_{0}^{T} a \exp(-b(T-t)) \wedge 1 \, dt \le \frac{1}{b}(\log(a) + 1). $$

*Proof.* We assume that $a \exp(-bT) < 1$. Otherwise, the integrand is always one and the bound trivially holds because $T < \log(a)/b$ if $a \exp(-bT) > 1$. Let $\tilde{T} \in [0, T]$ be such that $a \exp(-b(T - \tilde{T})) = 1$, which is always guaranteed to exist because the function $t \mapsto a \exp(-b(T - t))$ is continuous, increasing, and evaluates to $a \exp(-bT) < 1$ at $t = 0$ and $a > 1$ at $t = T$. Then, by partitioning the integral at $\tilde{T}$ we obtain

$$ \begin{aligned} \int_{0}^{T} a \exp(-b(T-t)) \wedge 1 \, dt &= \int_{0}^{\tilde{T}} a \exp(-b(T-t)) \, dt + T - \tilde{T} \\ &= \frac{a}{b} \exp(-b(T-t)) \Big|_{0}^{\tilde{T}} + T - \tilde{T} \\ &= \frac{a}{b} \exp(-b(T - \tilde{T})) - \frac{a}{b} \exp(-bT) + T - \tilde{T} \\ &\le \frac{1}{b} + T - \tilde{T}, \end{aligned} $$

where the last inequality follows from our choice of $\tilde{T}$ and discarding the second term. On the other hand, as $a \exp(-b(T - \tilde{T})) = 1$ we have that $T - \tilde{T} = \frac{\log a}{b}$, and therefore we conclude that

$$ \int_{0}^{T} a \exp(-b(T-t)) \wedge 1 \, dt \le \frac{1}{b}(\log a + 1). \quad \square $$

**Lemma E-2.** Let $\|x\|$ be a norm in the Euclidean space and let $\|z\|_* = \max_{\|x\| \le 1} \{z^\top x\}$ be its dual norm. Let $f(x) = \frac{1}{2}\|x\|^2$ if $\|x\| \le \varphi$ and $f(x) = \infty$ otherwise. Then, its convex conjugate
$f^*(z) = \max_x \{z^\top x - f(x)\} = \max_{x:\|x\| \le \varphi} \{z^\top x - \frac{1}{2} \|x\|^2\}$ is given by

$$f^*(z) = \begin{cases} \frac{1}{2} \|z\|_*^2 & \text{if } \|z\|_* \le \varphi \\ \varphi \|z\|_* - \frac{1}{2} \varphi^2 & \text{otherwise.} \end{cases}$$

*Proof.* Note that the convex conjugate can be more compactly written as $\min(\varphi, \|z\|_*) \cdot \|z\|_* - \frac{1}{2} \min(\varphi, \|z\|_*)^2$. We first show that the latter expression provides an upper bound and then show that the upper can be attained by choosing a suitable feasible solution.

For the upper bound, use Cauchy-Schwartz inequality to obtain that

$$f^*(z) \le \max_{x:\|x\| \le \varphi} \left\{ \|z\|_* \|x\| - \frac{1}{2} \|x\|^2 \right\} = \max_{\ell \in \mathbb{R}: 0 \le \ell \le \varphi} \left\{ \|z\|_* \ell - \frac{1}{2} \ell^2 \right\},$$

where the equality follows because we can equivalently optimize over the attainable norm values in $[0, \varphi]$. The objective value of the latter problem is a downward parabola with maximum at $\ell = \|z\|_*$. The claim follows because the optimal solution is $\ell = \min(\varphi, \|z\|_*)$.

For the lower bound, fix $z$ and let $\tilde{x} = \arg \max_{\|x\| \le 1} \{z^\top x\}$, i.e., a vector satisfying $\|z\|_* = z^\top \tilde{x}$. Such a vector exists because the dual norm always admits an optimal solution by Weierstrass theorem (the objective is continuous and the feasible set is compact). Consider the solution $x = \min(\varphi, \|z\|_*) \tilde{x}$. This solution is feasible because $\|x\| = \min(\varphi, \|z\|_*) \|\tilde{x}\| \le \varphi$ since $\|\tilde{x}\| \le 1$. Therefore,

$$\begin{aligned} f^*(z) &\ge z^\top x - \frac{1}{2} \|x\|^2 = z^\top \tilde{x} \cdot \min(\varphi, \|z\|_*) - \frac{1}{2} \|\tilde{x}\|^2 \cdot \min(\varphi, \|z\|_*)^2 \\ &\ge \min(\varphi, \|z\|_*) \cdot \|z\|_* - \frac{1}{2} \min(\varphi, \|z\|_*)^2, \end{aligned}$$

where the last inequality follows because $\|z\|_* = z^\top \tilde{x}$ and $\tilde{x} \le 1$. The result follows. $\square$

**Lemma E-3.** Consider the general linear program problem

$$\begin{array}{ll} \max_{x} & c^\top x \\ \text{s.t} & Ax = \xi + \epsilon u, \\ & x \ge 0, \end{array} \qquad (E-1)$$

where $c, x, \mathbf{0}, \mathbf{1} \in \mathbb{R}^n$, $\xi, u \in \mathbb{R}^m$, $A \in \mathbb{R}^{m \times n}$ matrix of rank $m$ and $\epsilon$ a real parameter. Define $x_{\min}^* = \min\{x_i^* : x_i^* > 0\}$, where $x^*$ denotes a non-degenerate optimal solution of problem (E-1) for $\epsilon = 0$, and denote by $A_B \in \mathbb{R}^{m \times m}$ its associated basis matrix. If $\delta = x_{\min}^* / \|A_B^{-1} u\|$, then $A_B$ remains optimal for problem (E-1) for all $0 \le \epsilon \le \delta$.
Proof. By permuting its columns, matrix A can be written as $A = (A_B|A_N)$, where $A_B \in \mathbb{R}^{m \times m}$ is the submatrix containing the columns associated to the basic variables of $x^*$ and $A_N \in \mathbb{R}^{m \times (n-m)}$ is the submatrix corresponding to the non-basic variables of $x^*$. Furthermore, we can write $x^* = (x_B^*, \mathbf{0})$, where $x_B^* = A_B^{-1}\xi \in \mathbb{R}^m$ is the subvector of basic variables and $\mathbf{0} \in \mathbb{R}^{n-m}$. Note that non-degeneracy of $x^*$ implies that $x_B^* > 0$.

Note that $\delta > 0$ is well defined because $\{x_i^* : x_i^* > 0\}$ is not empty due to the non-degeneracy condition on $x^*$. Take $\epsilon \le \delta$. We will prove that $A_B$ is an optimal basis for (E-1), that is, $x = (x_B, \mathbf{0})$ with $x_B = A_B^{-1}(\xi + \epsilon u)$ is an optimal solution for Problem (E-1). Changing the right-hand side of the equality constraints does not change the reduced cost vector and, therefore, it is enough to show that $x_B$ is non-negative.

To this end, take $j \in \{1, \dots, m\}$ such that $(A_B^{-1}u)_j < 0$. Note that if does not exist such $j$, the desired inequality follows trivially because $x_j^* = (A_B^{-1}\xi)_j > 0$ since $x^*$ is non-degenerate. Otherwise, we have that

$$ (x_B)_j = (A_B^{-1}(\xi + \epsilon u))_j = (x_B^*)_j + \epsilon (A_B^{-1}u)_j \ge x_{\min}^* - \epsilon \|A_B^{-1}u\| \ge x_{\min}^* - \delta \|A_B^{-1}u\| = 0, $$

where the first equation follows from the definition of $x_B$, the second because $(x_B^*)_j$ is a basic variable, the first inequality from the definition of $x_{\min}^*$ together with $|x_j| \le \|x\|$ for every $x_j \in \mathbb{R}^m$, the second inequality because $\epsilon \le \delta$, and the last from the definition of $\delta$. The proof is completed. $\square$