# Algorithms for a Risk-Averse Stackelberg Game with Multiple Adversaries

Renaud Chicoisne, Fernando Ordóñez

<figure><img src="image_1.png" /></figure>

## To cite this version:

Renaud Chicoisne, Fernando Ordóñez. Algorithms for a Risk-Averse Stackelberg Game with Multiple Adversaries. Computers and Operations Research, 2023, 160, pp.106367. 10.1016/j.cor.2023.106367. hal-02915077v2

HAL Id: hal-02915077

https://hal.science/hal-02915077v2

Submitted on 1 Aug 2021

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_2.png" /></figure>
# Algorithms for a Risk-Averse Stackelberg Game with Multiple Adversaries

Renaud Chicoisne<fnref n="1" />

ULB, Computer Science Department, Boulevard du Triomphe, Brussels, Belgium

Fernando Ordóñez<fnref n="2" />

Universidad de Chile, Industrial Engineering Department, Beauchef 850, Santiago, Chile

## Abstract

We consider a Stackelberg game that arises in a security domain (SSG), where a defender can simultaneously protect $m$ out of $n$ targets from an adversary that observes the defense strategy before deciding on an utility maximizing attack. Given the high stakes in security settings, it is reasonable that the defender in this game is risk averse with respect to the attacker's decisions.

Here we focus on developing efficient solution algorithms for a specific SSG, where the defender uses an entropic risk measure to model risk aversion to the attacker's strategies, and where multiple attackers select targets following logit quantal response equilibrium models. This problem can be formulated as a nonconvex nonlinear optimization problem. We propose two solution methods: (1) approximate the problem through convex mixed integer nonlinear programs (MINR) and (2) a general purpose methodology (CELL) to optimize nonconvex and nonseparable fractional problems through mixed integer linear programming approximations. Both methods provide arbitrarily good incumbents and lower bounds on SSG. We present cutting plane methods to solve these problems for large instances. Our computational experiments illustrate the advantages of introducing risk aversion into the defender's behavior and show that MINR dominates CELL, producing in 2 hours solutions that are within 2% of optimal

<footnote n="1">¹renaud.chicoisne@gmail.com</footnote>

<footnote n="2">²fordon@dii.uchile.cl</footnote>
on average.

*Keywords:* Stackelberg Security Games, Risk Averse Optimization, Entropic Risk Measure, Quantal Response, Piecewise Linear Approximation, Decomposition

# 1. Introduction

In this work we develop efficient solution methods for a fractional nonconvex optimization problem motivated from a Stackelberg game model in security applications. A Stackelberg game is defined as a game where the leader decides a mixed strategy to maximize its utility, taking into account that the follower will observe this strategy and in turn decide the action to maximize its utility [1]. In particular, Stackelberg game models have been used to represent the interaction between defenders (that act as the leader) and attackers (corresponding to followers) in diverse security settings [2, 3, 4]. For example, when defenders patrol a subset of targets that can be attacked by multiple adversary types, who - knowing the patrolling strategy - select the target to attack [5, 6]. Examples of such Stackelberg security games (SSGs) have been successfully deployed in real-world security applications to help plan the patrols conducted by the Los Angeles International Airport Police on LAX and the US Federal Air Marshal Service on transatlantic flights [6], the LA Sheriff department on Los Angeles' subway system [7], and the US Coast Guard on ports and waterways in Boston and New York City [8]. In particular, the applications with Airport Police, Federal Air Marshal Service and LA Sheriff department consider multiple attacker types.

The SSG model we study makes two additional considerations, which have appeared previously: 1) it assumes adversaries use a logit discrete choice model to select their action [9], and 2) the leader includes risk considerations on its objective function, optimizing an entropic risk measure objective [10]. The SSG models with a single adversary, introduced in [9], lead to problems with the
following structure:

$$
\begin{align*}
\min_{x} & \frac{1}{\sum_{i=1}^{n} \beta_i e^{-\gamma_i x_i}} \sum_{i=1}^{n} \beta_i e^{-\gamma_i x_i} (a_i - b_i x_i) \\
\text{s.t.} & \quad Hx \leq h.
\end{align*}
$$

These models are extended in [10] to the case when the defender uses an en-
tropic risk measure, giving problems that maintain the above problem structure.
Solution strategies for these SSG against a single adversary consider a binary
search procedure on the fractional objective and either (1) a non-linear variable
transformation to obtain convex subproblems, when there are simple defender
strategy constraints and (2) a piecewise linear approximation giving mixed linear
optimization problems, when the defender strategy satisfies general polyhedral
constraints.

Extending these solution strategies for the case with multiple attacker types
has not been investigated. In this paper we focus on the computational challenge
of efficiently solving this SSG model when facing multiple adversaries.

1.1. Boundedly rational adversaries and Quantal Response

Stackelberg games typically assume a perfectly rational attacker that maximizes its expected utility given the defense strategy [5, 6], or that can deviate slightly from the optimal attack [11]. Nevertheless, humans sometimes make decisions that are different from the policy that optimizes a given reward function [12]. Consequently, assuming a highly intelligent adversary can lead to weak defense strategies, that fail to take advantage of our knowledge about the attacker. The Quantal Response (QR) Equilibrium model presented in [13] assumes that human adversaries do not behave rationally, sometimes selecting actions that do not maximize their utility. In this model, followers use a logit discrete choice model to decide between n possible actions, where action i (that gives a payoff U_i) is selected with probability:

$$
\mathbb{P}(\text{selecting action } i) = \frac{1}{\sum_{j=1}^{n} e^{\lambda U_j}} e^{\lambda U_i},
$$
where the parameter $\lambda$ represents a degree of rationality, with perfect rationality ($\lambda \to \infty$) or indifference ($\lambda = 0$) as special cases. The QR model has been used to model human behavior in various settings, including economics [14, 15], game theory [16], transportation engineering [17], marketing [18], and security applications [19].

## 1.2. Risk-Averse defender and Entropic risk measure

As mentioned above, rational players in standard game theory models optimize expected reward functions. Even when considering mixed strategies, the objective can be seen as the expected reward with respect to the adversary's probability distribution over actions. However, in a security domain, the consequences of catastrophic unlikely events could far outweigh that of more common expected occurrences. Planning for the worst case can focus resources on scenarios that rarely occur, while planning for expected reward could divert key resources from catastrophic events. Different risk measures have been used to balance likely outcomes with rare but catastrophic ones in decision models. Less common is to consider risk measures to model risk-adverse behavior against the uncertainty due to the adversary's probability distribution over actions.

In this work, we use an entropic risk measure [20] that amplifies the importance of outcomes that exceed a given threshold to model risk-adverse behavior against the attacker's probability over actions. The entropic risk measure of parameter $\alpha \ge 0$ of a random variable $Y$ is defined by $\alpha \ln \mathbb{E}[e^{Y/\alpha}]$. While all outcomes are weighted, scenarios with a payoff larger than $\alpha$ contribute more to this measure. Therefore, the parameter $\alpha$ corresponds to a payoff value of risky outcomes and must be chosen carefully to tune the risk aversion level of the decision maker.

Consider now the example in Table 1 to illustrate the risk that can be present in an expected value maximizing policy. This example presents the expected value, variance and worst case probability for the optimal solutions of the SSG with an expected value objective ($x^*$) and the SSG with an entropic measure objective ($\tilde{x}$). The example has two targets, a single patrol, and a single attacker
with rationality factor $\lambda = 0.25$. The payoffs of this game (where the defender is the row player and the attacker is the column player) are given in Table 1a.

<table><thead><tr><th></th><th>attack 1</th><th>attack 2</th><th>E</th><th>V</th><th>w.c. P</th></tr></thead><tbody><tr><th>patrol 1</th><td>3, -1</td><td>-3, 1</td><td>x*</td><td>0.245</td><td>4.980</td><td>0.192</td></tr><tr><th>patrol 2</th><td>-1, 3</td><td>1, -3</td><td>x̃</td><td>0.233</td><td>4.546</td><td>0.159</td></tr><tr><th></th><th></th><th></th><th>Diff.</th><td>-4.9%</td><td>-8.7%</td><td>-16.9%</td></tr></tbody></table>

(a) Payoffs matrix. Each cell contains the utilities [defender, attacker].

(b) Comparing $x^*$ and $\tilde{x}$ wrt their expected values, variances and worst case probabilities.

<caption>Table 1: Two targets, one defender resource example</caption>

Both the expected utility objective problem and the entropic risk measure problem for this example can be expressed as a single variable non-linear maximization problem (presented in Section 2) that give the results summarized in Table 1b. The solution that optimizes the entropic risk measure, $\tilde{x}$, has a smaller variance and a smaller probability of the worst case scenario than the solution that optimizes the expected value, $x^*$. Using an Entropic risk measure gives a solution that reduces the possible bad outcomes, thus reducing the variance that the solution observes at the expense of a worse expected value.

## 1.3. Contributions and paper structure

To the best of our knowledge there is no prior work on risk averse SSGs with multiple QR followers. Given that multiple adversaries in Stackelberg games are modeled using a Bayesian model [21], considering multiple adversaries is equivalent to considering uncertainty in the payoff functions. This makes the multiple follower problem a stochastic version of the single follower problem introduced in [9, 10]. In this work we develop efficient solution methods for the stochastic SSG with QR followers, which considers algorithms for problems
with the following form:

$$ \min_x \sum_{l=1}^{p} \pi^l \frac{1}{\sum_{i=1}^{n} \beta_i^l e^{-\gamma_i^l x_i}} \sum_{i=1}^{n} \beta_i^l e^{-\gamma_i^l x_i} (a_i^l - b_i^l x_i) \quad (1a) $$

$$ \text{s.t.} \quad Hx \leq h, \quad (1b) $$

with non-negative coefficients $\beta_i^l, \gamma_i^l, a_i^l$, and $b_i^l$. We note that the use of multi-nomial logit models in various settings has led to formulating problems with similar structure to (1) for different applications, such as in bundle pricing [22] or transportation network design [23].

In this work we investigate solution strategies to solve problem (1). This problem has a non-linear non-convex objective with arbitrary polyhedral constraints. Due to the non-convexity of the problem, non-linear solution methods are not guaranteed to obtain the optimal solution. We therefore propose two decomposition solution strategies for problem (1) when it has general polyhedral constraints. The first solution method exploits problem structure to recast the problem as a non-convex nonlinear optimization problem that can be approximated using piecewise linear functions. The second uses a generic methodology to approximate multidimensional nonlinear functions via spatial discretization. Both solution strategies require efficiently solving sequences of mixed integer linear optimization problems and are able to provide upper and lower bounds on the exact optimal solution.

We structure the rest of the paper as follows: in the next section, we introduce the problem formulation. In Sections 3 and 4 we present two different solution methods that approximately solve the SSG with multiple QR followers and show that both can provide lower bounds and arbitrarily good defender strategies. In Section 5 we present repair heuristics for both models and strategies to select the discretization points in order to speed up the solution methods and strengthen the relaxation bounds. We show experimental results in Section 6 on mid-sized artificial instances and compare the performance of our algorithms and the quality of the solution they provide. We present our conclusions in Section 7.
## 2. Notation and problem formulation

The SSG we consider consists of a single leader (defender) that patrols n targets that could be attacked by one of p followers (attackers). The leader can patrol up to m < n targets simultaneously and each follower selects one target to attack. The payoffs for the leader and the followers both depend on whether the target attacked is patrolled or not. If follower l ∈ {1, ..., p} attacks target i ∈ {1, ..., n}, then the payoffs received by attacker l are either a reward $R_i^l > 0$ if the target is not patrolled or a penalty $P_i^l < 0$ if the target is patrolled. Similarly, if attacker l attacks target i, we let the payoffs for the defender be a reward $\bar{R}_i^l > 0$ when the target is patrolled and a penalty $\bar{P}_i^l < 0$ if it is not patrolled.

The set of actions for the defender are the feasible subsets of targets $\mathcal{I} \subseteq \{1, ..., n\}$ that can be patrolled simultaneously ($|\mathcal{I}| \le m$). We denote by $z := (z_{\mathcal{I}})_{\mathcal{I} \subseteq \{1, ..., n\}}$ the mixed strategy over this action space, so that $z_{\mathcal{I}}$ is the probability with which the defender patrols some set of targets $\mathcal{I}$. Letting $q_i^l$ denote the probability with which follower l attacks target i, we can express the defender and l-th attacker utility for given strategies z, q as

$$ 
\begin{aligned}
\bar{U}(z, q) &= \sum_{l=1}^{p} \sum_{\mathcal{I} \subseteq \{1 \dots n\}} \left( \sum_{i \in \{1 \dots n\}} \bar{R}_i^l z_{\mathcal{I}} q_i^l + \sum_{i \in \{1 \dots n\}} \bar{P}_i^l z_{\mathcal{I}} q_i^l \right) \\
U^l(z, q) &= \sum_{\mathcal{I} \subseteq \{1 \dots n\}} \left( \sum_{i \in \{1 \dots n\}} P_i^l z_{\mathcal{I}} q_i^l + \sum_{i \in \{1 \dots n\}} R_i^l z_{\mathcal{I}} q_i^l \right).
\end{aligned}
$$

Since the payoffs only depend on whether a target i is patrolled or not, we consider the frequency of protecting target i, given by $x_i = \sum_{\mathcal{I} \subseteq \{1, ..., n\}} z_{\mathcal{I}}$, the sum of probabilities of the defender strategies that patrol i. With the frequency of patrolling target i, $x_i \in [0, 1]$, we can express the expected utility of the defender and attacker l when target i is attacked by follower l as $\bar{U}_i^l(x_i) = x_i \bar{R}_i^l + (1 - x_i) \bar{P}_i^l$ and $U_i^l(x_i) = x_i P_i^l + (1 - x_i) R_i^l$, respectively.

Since follower l ∈ {1...p} selects targets according to a QR model with a rationality parameter $\lambda^l > 0$, we denote the probability of attacker l selecting
target i by

$$y_i^l(x) = \frac{1}{\sum_{j=1}^{n} e^{\lambda^l U_j^l(x_j)}} e^{\lambda^l U_i^l(x_i)} = \frac{e^{\lambda^l (x_i P_i^l + (1-x_i) R_i^l)}}{\sum_{j=1}^{n} e^{\lambda^l (x_j P_j^l + (1-x_j) R_j^l)}}. \quad (2)$$

## 2.1. Expected utility defender problem

Similar to prior work on Stackelberg security games [6, 9], we formulate the defender optimization problem in terms of the frequency variables $x$, which by definition satisfy $x \in [0, 1]^n$ and $\sum_{i=1}^n x_i \le m$. We assume that the vector of frequency variables must satisfy a set of linear constraints $Hx \le h$ that can represent additional constraints on feasible patrols (e.g. targets $i$ and $i'$ cannot (or must) be patrolled together). We denote $\mathcal{X} := \{x: Hx \le h\}$ the feasible set of defender frequency variables. For an integer $k$, let $[k] := \{1, ..., k\}$. Let $\pi^l$ represent the probability of facing follower $l$. With the notation introduced above, the defender decision problem that maximizes the expected defender utility by adjusting the frequency variables is:

$$\max_{x \in \mathcal{X}} \sum_{l=1}^{p} \sum_{i=1}^{n} \pi^l y_i^l(x) (x_i \bar{R}_i^l + (1-x_i) \bar{P}_i^l).$$

Substituting (2) above and multiplying the objective by -1 we observe that the above problem is equivalent to the minimization problem (1) by setting $\beta_i^l := e^{\lambda^l R_i^l} > 0$, $\gamma_i^l := \lambda^l (R_i^l - P_i^l) \ge 0$, $a_i^l := -\bar{P}_i^l \ge 0$ and $b_i^l := \bar{R}_i^l - \bar{P}_i^l \ge 0$.

## 2.2. Entropic utility defender problem

We now formulate the defender's problem with the entropic risk measure objective. The random variable of defender utilities takes the following values for each $l \in [p]$, $i \in [n]$:

$\bar{P}_i^l$ with probability $\pi^l y_i^l(x)(1-x_i)$

$\bar{R}_i^l$ with probability $\pi^l y_i^l(x)x_i$.

Recall that the entropic risk with parameter $\alpha \ge 0$ of a random variable $Y$ is $\alpha \ln \mathbb{E}[e^{Y/\alpha}]$, which penalizes values of $Y$ that exceed the threshold parameter $\alpha$. Since the defender is interested in maximizing its utility, the payoffs that
should be penalized by the risk measure are the small ones. This is achieved by minimizing minus the utility (i.e. a cost). The entropic risk objective of the cost of the defender is given by

$$ \mathcal{E}_{\alpha}(x) := \alpha \ln \sum_{l=1}^{p} \sum_{i=1}^{n} \pi^{l} y_{i}^{l}(x) \left( x_{i} e^{-\bar{R}_{i}^{l} / \alpha} + (1 - x_{i}) e^{-\bar{P}_{i}^{l} / \alpha} \right). $$

*Risk averse model.* The goal of the defender is to minimize this entropic risk objective by adjusting the frequency $x \in \mathcal{X}$ of the coverage variables, which is achieved by solving the following optimization problem:

$$ \min_{x \in \mathcal{X}} \alpha \ln \sum_{l=1}^{p} \sum_{i=1}^{n} \pi^{l} y_{i}^{l}(x) \left( x_{i} e^{-\bar{R}_{i}^{l} / \alpha} + (1 - x_{i}) e^{-\bar{P}_{i}^{l} / \alpha} \right). $$

After 1) defining the constants $\tilde{P}_{i}^{l} := e^{-\bar{P}_{i}^{l} / \alpha}$ and $\tilde{R}_{i}^{l} := e^{-\bar{R}_{i}^{l} / \alpha}$, 2) substituting the expression of the quantal response (2) in the problem above and 3) noting that $\alpha \ln$ is a monotonic increasing function, the problem above is equivalent to:

$$ \min_{x \in \mathcal{X}} \sum_{l=1}^{p} \pi^{l} \frac{\sum_{i=1}^{n} \beta_{i}^{l} e^{-\gamma_{i}^{l} x_{i}} (\tilde{P}_{i}^{l} - (\tilde{P}_{i}^{l} - \tilde{R}_{i}^{l}) x_{i})}{\sum_{i=1}^{n} \beta_{i}^{l} e^{-\gamma_{i}^{l} x_{i}}}. $$

Again, this problem is of the form of the minimization problem (1) with the same $\beta_{i}^{l} > 0$ and $\gamma_{i}^{l} \ge 0$ and with $a_{i}^{l} := \tilde{P}_{i}^{l} > 0$ and $b_{i}^{l} := \tilde{P}_{i}^{l} - \tilde{R}_{i}^{l} > 0$.

The solutions $x^*$ and $\tilde{x}$ of the example in Table 1 are obtained by solving the problems introduced respectively in Subsections 2.1 and 2.2. Both problems have a single adversary and the defender variables satisfy $x \in [0, 1]^2$ such that $x_1 + x_2 \le 1$.

### 2.3. Rescaling Trick

Observe that the numerators in each fractional term of the objective function in (1) can be considered non-negative without loss of generality. In fact, for any constant $A_l \in \mathbb{R}$ with $l \in [p]$ we have that

$$ \frac{\sum_{i=1}^{n} \beta_{i}^{l} e^{-\gamma_{i}^{l} x_{i}} (a_{i}^{l} - b_{i}^{l} x_{i})}{\sum_{i=1}^{n} \beta_{i}^{l} e^{-\gamma_{i}^{l} x_{i}}} = \frac{\sum_{i=1}^{n} \beta_{i}^{l} e^{-\gamma_{i}^{l} x_{i}} (A_{l} + a_{i}^{l} - b_{i}^{l} x_{i})}{\sum_{i=1}^{n} \beta_{i}^{l} e^{-\gamma_{i}^{l} x_{i}}} - A_{l}. $$
Assuming $A_l \ge \max_{i \in [n]} \{b_i^l - a_i^l\}$ and since $x_i \in [0, 1]$, we can show that each function $N_i^l(x_i) := \beta_i^l e^{-\gamma_i^l x_i} (A_l + a_i^l - b_i^l x_i)$ is convex and nonnegative. To simplify our exposition, we also introduce the functions

$$D_i^l(x_i) := \beta_i^l e^{-\gamma_i^l x_i}, \quad N_i^l(x) := \sum_{i=1}^n N_i^l(x_i), \quad \text{and} \quad D^l(x) := \sum_{i=1}^n D_i^l(x_i).$$

In the remainder of this paper, our goal is to solve the following scaled problem with constants $A_l$ satisfying the aforementioned condition:

$$\omega := \min_{x \in \mathcal{X}} \quad \omega(x) := \sum_{l=1}^{p} \pi^{l} \frac{N^{l}(x)}{D^{l}(x)} \qquad (3)$$

### 3. A Mixed Integer Nonlinear Reformulation (MINR)

In this Section, we present a reformulation of (3) that takes advantage of its structure and allows a straightforward piecewise-linear approximation of every non-convex constraint.

#### 3.1. A reformulation

We now use the fact that both the numerator and the denominator of these fractional components are positive to reformulate (3) as follows.

**Proposition 1.** For any $A_l \ge \max_{i \in [n]} \{b_i^l - a_i^l\}$ and defining:

$$L_l^u := \ln \sum_{i=1}^{n} N_i^l(1)$$

$$U_l^u := \ln \sum_{i=1}^{n} N_i^l(0)$$

$$L_l^v := \ln \sum_{i=1}^{n} D_i^l(1)$$

$$U_l^v := \ln \sum_{i=1}^{n} D_i^l(0),$$
problem (3) is equivalent to

$$ \omega = \min_{x,u,v} \sum_{l=1}^{p} \pi^l e^{u_l - v_l} \qquad (4a) $$

$$ \text{s.t.} \quad x \in \mathcal{X} \qquad (4b) $$

$$ -e^{u_l} + \sum_{i=1}^{n} \beta_i^l e^{-\gamma_i^l x_i} (A_l + a_i^l - b_i^l x_i) \le 0, \quad \forall l \in [p] \qquad (4c) $$

$$ e^{v_l} - \sum_{i=1}^{n} \beta_i^l e^{-\gamma_i^l x_i} \le 0, \quad \forall l \in [p] \qquad (4d) $$

$$ L_l^u \le u_l \le U_l^u, \quad \forall l \in [p] \qquad (4e) $$

$$ L_l^v \le v_l \le U_l^v, \quad \forall l \in [p] \qquad (4f) $$

*Proof.* For each $l \in [p]$ consider the extra variables $(u_l, v_l) \in \mathbb{R}^2$. Since the functions $N^l$ and $D^l$ are nonnegative, (3) can be rewritten as follows:

$$ \omega = \min_{x,u,v} \sum_{l=1}^{p} \pi^l e^{u_l - v_l} $$

$$ \text{s.t.} \quad x \in \mathcal{X} $$

$$ e^{u_l} \ge N^l(x), \quad \forall l \in [p] $$

$$ e^{v_l} \le D^l(x), \quad \forall l \in [p]. $$

Noticing that any optimal solution $(x^*, u^*, v^*)$ of the latter problem satisfies $e^{u_l^*} = N^l(x^*)$ and $e^{v_l^*} = D^l(x^*)$. The range constraints on each $u_l$ (respectively $v_l$) are obtained by maximizing and minimizing $N^l$ (respectively $D^l$) in $x \in [0, 1]^n \supset \mathcal{X}$. The facts that $A_l \ge \max_{i \in [n]} \{b_i^l - a_i^l\}$, $\gamma_i^l \ge 0$ and $b_i^l \ge 0$ imply that both $N^l$ and $D^l$ are decreasing functions of each $x_i$ that attain their maximum value for $x_i = 0$ and minimum value for $x_i = 1$. $\square$

Given the choice of $A_l$, the only sources of non-convexity of problem (4) are the univariate functions $u_l \to -e^{u_l}$ in constraints (4c) and $x_i \to -e^{-\gamma_i^l x_i}$ in constraints (4d). This motivates the use of piecewise linear functions to approximate (4).
### 3.2. Piecewise linear approximations

Piecewise linear approximations of non-linear, non-convex functions are an important part of the solution methods proposed. Here we set the notation used to construct piecewise linear approximations using a few binary variables (a logarithm of the number of partitions), as described in [24].

Consider a univariate function $f : [l, u] \to \mathbb{R}$ and a partition of the interval $[l, u]$ given by $K + 1$ points $l = t_0 < t_1 < ... < t_K = u$. A piecewise linear approximation of $f$ that matches the function at the partition points is given by $\sum_{k=0}^{K} \lambda_k f(t_k)$ with $\sum_{k=0}^{K} \lambda_k = 1$, $\lambda \ge 0$, and such that it has at most two coefficients that are non-zero and they must be consecutive (this last constraint is known as an SOS2 constraint). The work in [24] provides an efficient representation of these SOS2 constraints, which directly implies the next result.

Let $L(K) = [\log_2 K]$ and consider $B_K : [K] \mapsto \{0, 1\}^{L(K)}$ a bijective mapping such that for all $q \in [K - 1]$, $B_K(q)$ and $B_K(q + 1)$ differ in at most one component (See reflected binary or Gray code in [25]). Such a Gray code can be found quickly by the recursive algorithm of [26].

**Proposition 2.** [24] Given $f : [l, u] \to \mathbb{R}$ and a partition $l = t_0 < t_1 < ... < t_K = u$ of $[l, u]$, for every $x \in [l, u]$ the piecewise linear function that equals $f(x)$ at the partition points is given by $\mathcal{P}_t[f](x) = \sum_{k=0}^{K} \lambda_k f(t_k)$, for a $(\lambda, z)$ that satisfies

$$x = \sum_{k=0}^{K} \lambda_k t_k \qquad (5a)$$

$$\sum_{k=0}^{K} \lambda_k = 1 \qquad (5b)$$

$$\sum_{p \in S_K^+(l)} \lambda_p \le z_l, \qquad \forall l \in [L(K)] \qquad (5c)$$

$$\sum_{p \in S_K^-(l)} \lambda_p \le 1 - z_l, \qquad \forall l \in [L(K)] \qquad (5d)$$

$$z_l \in \{0, 1\}, \qquad \forall l \in [L(K)] \qquad (5e)$$

$$\lambda \ge 0, \qquad (5f)$$
where defining $Q_K(k) := \{k, k+1\}$ if $k \in [K-1]$ and $Q_K(K) = \{K\}$, for $k \in [L(K)]$ we have:

$$S_K^+(k) := \{p \in \{0, \dots, K\} : \forall q \in Q_K(p), (B_K(q))_k = 1\}$$

$$S_K^-(k) := \{p \in \{0, \dots, K\} : \forall q \in Q_K(p), (B_K(q))_k = 0\}.$$

This formulation uses only $[\log_2 K]$ extra binary variables. Given a partition set $t = (t_0, \dots, t_K)$ with $K+1$ points, we define the set of constraints that encode the piecewise linear approximation at $x$ by:

$$LPL(t, K, x) := \{((\lambda_k)_{k \in [K]}, (z_l)_{l \in [L(K)]}) \text{ satisfying (5)}\}.$$

We refer to this construction of a piecewise linear approximation as the Logarithmic Piecewise Linear approximation (LPL). We can therefore express the approximation of $f(x)$ by

$$\mathcal{P}_t[f](x) = \sum_{k=0}^{K} \lambda_k f(t_k) \quad \text{s.t.} \quad (\lambda, z) \in \text{LPL}(t, K, x).$$

The next (known) result gives us some information about LPL approximations:

**Proposition 1.** The piecewise linear function $\mathcal{P}_t[f]$ which equals function $f$ at all points in a partition set $t$ of the interval $[l, u]$ satisfies the following [27]:

1. If $f$ is a convex function, then $\mathcal{P}_t[f](x) \ge f(x)$ for all $x \in [l, u]$.

2. If $f$ is $\mathcal{L}$-Lipschitz over $[l, u]$ (i.e. $|f(x) - f(y)| \le \mathcal{L}||x - y||$ for any $x, y$), then

$$\max_{x \in [l, u]} |\mathcal{P}_t[f](x) - f(x)| \le \frac{\mathcal{L}}{2} \max_{i \in [K-1]} |t_{i+1} - t_i|.$$

### 3.3. A Lower-Bounding Approximated Problem

The LPL formulation is used below to construct piecewise linear approximations of the non-convex portions in (4). The range constraints $x_i \in [0, 1]$ and $u_l \in [L_l^u, U_l^u]$ inform where each approximation should be done.

For each target $i \in [n]$, consider a partition $t^i$ of $[0, 1]$ on $K+1$ points (i.e. $0 = t_0^i < t_1^i < \dots < t_K^i = 1$). For each follower $l \in [p]$, consider a partition $\tau^l$ of $[L_l^u, U_l^u]$ on $K+1$ points (i.e. $L_l^u = \tau_0^l < \tau_1^l < \dots < \tau_K^l = U_l^u$). Using
these partitions we construct the following mixed integer convex optimization problem:

$$
\hat{\omega} := \min_{\substack{x, u, v, \rho, \vartheta \\ \theta, \lambda, z, \xi, y}} \sum_{l=1}^{p} \pi^l \rho_l \quad (6a)
$$

$$
\text{s.t.} \quad x \in \mathcal{X} \tag{6b}
$$

$$
\rho_l \ge e^{u_l - v_l}, \qquad \forall l \in [p] \quad (6c)
$$

$$
\sum_{i=1}^{n} \theta_{l}^{i} \leq \sum_{k=0}^{K} \xi_{k}^{l} e^{\tau_{k}^{l}}, \quad \forall l \in [p] \quad (6d)
$$

$$
\theta_l^i \ge \beta_i^l e^{-\gamma_i^l x_i} (A^l + a_i^l - b_i^l x_i), \quad \forall l \in [p], i \in [n] \quad (6e)
$$

$$
\vartheta_l \le \sum_{i=1}^{n} \beta_i^l \sum_{k=0}^{K} \lambda_k^i e^{-\gamma_i^l t_k^i}, \quad \forall l \in [p] \quad (6f)
$$

$$
\vartheta_l \ge e^{v_l}, \qquad \forall l \in [p] \quad (6g)
$$

$$
L_l^u \le u_l \le U_l^u, \qquad \forall l \in [p] \quad (6h)
$$

$$
L_l^v \le v_l \le U_l^v, \qquad \forall l \in [p] \quad (6i)
$$

$$
e^{L_l^u - U_l^v} \le \rho_l \le e^{U_l^u - L_l^v}, \quad \forall l \in [p] \quad (6j)
$$

$$
e^{L_l^v} \le \vartheta_l \le e^{U_l^v}, \qquad \forall l \in [p] \quad (6k)
$$

$$
(\lambda^i, z^i) \in \text{LPL}(t^i, K, x_i), \quad \forall i \in [n] \quad (6l)
$$

$$
(\xi^l, y^l) \in \text{LPL}(\tau^l, K, u_l), \quad \forall l \in [p] \quad (6m)
$$

This approximate problem has integer variables *z* and *y* defined in the LPL constraints and convex constraints in (6c), (6e) and (6g). For any *x* ∈ 𝒳, let us define $\hat{\omega}(x)$ as the optimal value of (6) when *x* is fixed, implying that $\hat{\omega} = \min_{x \in \mathcal{X}} \hat{\omega}(x)$.

The next Proposition shows that (6) provides a lower bound for (3) and any
of its optimal solutions provides a good solution to (3).

**Proposition 3.** Given uniform partitions *t* and *τ* of *K* + 1 points in the defi-
nition of (6) and ($\hat{x}$, $\hat{u}$, $\hat{v}$, $\hat{\rho}$, $\hat{\vartheta}$, $\hat{\theta}$, $\hat{\lambda}$, $\hat{z}$, $\hat{\xi}$, $\hat{y}$) an optimal solution of (6). We have

$$
1. 0 \le \omega - \hat{\omega} \le O(1/K)
$$

2. $\hat{x}$ is feasible for (3) and $|\omega(\hat{x}) - \omega| \le O(1/K)$.
<figure><img src="image_3.png" /></figure>

### 3.4. A Cutting Plane Algorithm

Solving problem (6) is challenging as it is a problem with convex constraints and integer variables. To avoid the non-linearity, we approximate the convex portions of the constraint functions by exploiting the fact that a convex function is the upper envelope of the linear support functions at every point. In particular we replace the convex non-linear terms of the functions $e^{u_l-v_l}$, given $l \in [p]$, $e^{v_l}$, and $N_i^l(x_i) = \beta_i^l e^{-\gamma_i^l x_i} (A_l + a_i^l - b_i^l x_i)$ with their first order Taylor expansions. This modifies only constraints (6c), (6e), and (6g) giving the mixed integer linear optimization problem (with infinitely many constraints):

$$ \hat{\omega} = \min_{x, u, v, \rho, \vartheta, \lambda, z, \xi, y} \sum_{l=1}^{p} \pi^l \rho_l \quad (7a) $$

$$ \text{s.t.} \quad (6b), (6d), (6f), (6h-6m) \quad (7b) $$

$$ \rho_l \ge e^{\hat{u}_l - \hat{v}_l} (1 + u_l - v_l - \hat{u}_l + \hat{v}_l), \quad \forall (\hat{u}_l, \hat{v}_l), l \in [p] \quad (7c) $$

$$ \theta_l^i \ge N_i^l(\hat{x}_i) + (N_i^l)'(\hat{x}_i)(x_i - \hat{x}_i), \quad \forall \hat{x}_i, l \in [p], i \in [n] \quad (7d) $$

$$ \vartheta_l \ge e^{\hat{v}_l} (1 + v_l - \hat{v}_l), \quad \forall \hat{v}_l, l \in [p]. \quad (7e) $$

To tackle the infinitely many constraints in the above problem, we will generate them as we need them with a cutting plane procedure. We set up the problem with an initial set of linear support functions. Let $\mathcal{U}_l^{u,v}$ be the set of points used to build a linear support function of $(u_l, v_l) \to e^{u_l-v_l}$, given $l \in [p]$. Similarly let $\mathcal{U}_l^v$ and $\mathcal{U}_l^x$ be the set of points used to generate linear support functions of $v_l \to e^{v_l}$ and $N_i^l$, respectively. The tractable optimization problem is (7) replacing the last three constraints (7c-7e) with the following.

$$ \rho_l \ge e^{\hat{u}_l - \hat{v}_l} (1 + u_l - v_l - \hat{u}_l + \hat{v}_l), \quad \forall (\hat{u}_l, \hat{v}_l) \in \mathcal{U}_l^{u,v}, l \in [p] $$

$$ \theta_l^i \ge N_i^l(\hat{x}_i) + (N_i^l)'(\hat{x}_i)(x_i - \hat{x}_i), \quad \forall \hat{x}_i \in \mathcal{U}_{li}^x, l \in [p], i \in [n] $$

$$ \vartheta_l \ge e^{\hat{v}_l} (1 + v_l - \hat{v}_l), \quad \forall \hat{v}_l \in \mathcal{U}_l^v, l \in [p]. $$

We call $\hat{\omega}[\mathcal{U}]$ the optimal value of the corresponding relaxation.
## 4. Multidimensional cell approximation (CELL)

We now present a generic method to approximate nonseparable functions using linear constraints and variables, in the spirit of [28]. Akin to the previous model, introducing new variables $\rho$, we recast (3) into the equivalent form:

$$ \min_{x \in \mathcal{X}, \rho} \left\{ \sum_{l=1}^{p} \pi^l \rho_l : N^l(x) - \rho_l D^l(x) \le 0, \forall l \in [p] \right\}. \quad (8) $$

This problem is in general not convex because of the products $\rho_l D^l(x)$. To tackle this non-convexity, we take advantage of the partial separability in the constraints of (8) to efficiently approximate the products $\rho_l D_i^l(x_i)$ with a relatively small number of binary variables. We first present a generic way to approximate nonseparable multivariate functions.

### 4.1. Multidimensional Generic Approximations

The following Proposition is similar to a method coined *optimistic MILP model* in [28]. It presents a piecewise linear approximation of several non-separable multivariate functions defined on a common homogeneous grid.

**Proposition 4.** Consider a ground set $\mathcal{G} := \{x \in \mathbb{R}^I : l \le x \le u\}$ and J functions $f_j : \mathcal{G} \to \mathbb{R}$ being $\mathcal{L}_j$-Lipschitz. Given a discretization of $\mathcal{G}$ in each dimension: $l_i = t_0^i \le t_1^i \le \dots \le t_K^i = u_i$, where $t_{k_i}^i = l_i + k_i(u_i - l_i)/K$, $C_t[f_j]$ is an $\mathcal{L}_j$-approximation of every function $f_j$ on $\mathcal{G}$:

$$ C_t[f_j](x) = \min_{\mu, \lambda, z} \sum_{k \in \{0, \dots, K\}^I} \mu_k f_j(t_{k_1}^1, \dots, t_{k_I}^I) \quad (9a) $$

$$ \text{s.t.} \quad (\lambda^i, z^i) \in \text{LPL}(t^i, K, x_i), \quad \forall i \in [I] \quad (9b) $$

$$ \mu_k \le \lambda_{k_i}^i, \quad \forall k \in \{0, \dots, K\}^I, i \in [I] \quad (9c) $$

$$ \sum_{k \in \{0, \dots, K\}^I} \mu_k = 1 \quad (9d) $$

$$ \sum_{k \in \{0, \dots, K\}^I} \mu_k t_{k_i}^i = x_i, \quad \forall i \in [I] \quad (9e) $$

$$ \mu \ge 0 \quad (9f) $$
Proof. Annex Section 8.2. □

This result shows that the maximum distance between $C_t[f_j]$ and $f_j$ is $O(1/K)$. Notice that when $I = 1$, $C_t[f_j] = P_t[f_j]$. Also, the size of the optimization problem that approximates the functions $f_j$ does not depend on the number of functions $J$ to approximate. The optimization problem uses $L(K)I$ binary variables, $O(K^I)$ continuous variables and $O(IK^I)$ constraints. A direct consequence is the piecewise linear cell formulation of an optimization problem, stated below.

**Proposition 5.** *Given an optimization problem*

$$ \begin{array}{ll} \min_{x \in \mathcal{X}} & f(x) \\ \text{s.t.} & g_j(x) \le b_j \quad \forall j \in \{1, \dots, J\}, \end{array} $$

its cell-approximation is given by the following optimization problem

$$ \begin{array}{ll} \min_{x \in \mathcal{X}, \mu, \lambda, z} & \displaystyle\sum_{k \in \{0, \dots, K\}^I} \mu_k f(t_{k_1}^1, \dots, t_{k_I}^I) \\ \text{s.t.} & \displaystyle\sum_{k \in \{0, \dots, K\}^I} \mu_k g_j(t_{k_1}^1, \dots, t_{k_I}^I) \le b_j, \quad \forall j \in [J] \\ & (\lambda^i, z^i) \in \text{LPL}(t^i, K, x_i), \quad \forall i \in [I] \\ & \mu_k \le \lambda_{k_i}^i, \quad \forall k \in \{0, \dots, K\}^I, i \in [I] \quad (10) \\ & \displaystyle\sum_{k \in \{0, \dots, K\}^I} \mu_k = 1 \\ & \displaystyle\sum_{k \in \{0, \dots, K\}^I} \mu_k t_{k_i}^i = x_i, \quad \forall i \in [I] \\ & \mu \ge 0 \end{array} $$

This formulation takes advantage of the fact that we only need to determine once to which cell $x$ belongs and use this to approximate every function in the problem. The most important consequence of this fact is that the number of binary variables does not depend on the number of functions to approximate.

## 4.2. A Lower-Bounding Approximated Problem

We now show that the CELL-approximated problem provides a lower bound for (8) and any of its optimal solutions provides a good solution to (8). Consider
a discretization of the range of variables $x_i$ and $\rho_l$ into $K$ subintervals with homogeneous partitions $t^i = (t_0^i, ..., t_K^i)$ and $\tau^l = (\tau_0^l, ..., \tau_K^l)$. Defining

$$ \hat{\omega}(x) := \min_{\substack{\rho, \lambda \\ y, \xi \\ z, \mu}} \sum_{l=1}^{p} \pi^l \rho_l \qquad (11a) $$

$$ \text{s.t.} \quad \sum_{i=1}^{n} \sum_{k=0}^{K} \lambda_k^i N_i^l (t_k^i) \qquad (11b) $$

$$ - \sum_{i=1}^{n} \sum_{k_i=0}^{K} \sum_{k_{i-1}=0}^{K} \mu_{k_{i-1}, k_i}^{l, i} \tau_{k_i}^{l} D_i^l (t_{k_i}^i) \le 0, \quad \forall l \in [p] $$

$$ (\lambda^i, z^i) \in \text{LPL}(t^i, K, x_i), \quad \forall i \in [n] \quad (11c) $$

$$ (\xi^l, y^l) \in \text{LPL}(\tau^l, K, \rho_l), \quad \forall l \in [p] \quad (11d) $$

$$ 0 \le \mu_{kl, k_i}^{l, i} \le \xi_{kl}^l, \qquad (11e) $$

$$ \forall k_l, k_i \in \{0, ..., K\}, \forall l \in [p], i \in [n] $$

$$ 0 \le \mu_{kl, k_i}^{l, i} \le \lambda_{k_i}^i, \qquad (11f) $$

$$ \forall k_l, k_i \in \{0, ..., K\}, \forall l \in [p], i \in [n] $$

$$ \sum_{k_l=0}^{K} \sum_{k_i=0}^{K} \mu_{k_l, k_i}^{l, i} = 1, \quad \forall l \in [p], i \in [n] \quad (11g) $$

$$ \sum_{k_l=0}^{K} \sum_{k_i=0}^{K} \mu_{k_l, k_i}^{l, i} t_{k_l}^i = x_i, \quad \forall i \in [n] \quad (11h) $$

$$ \sum_{k_l=0}^{K} \sum_{k_i=0}^{K} \mu_{k_l, k_i}^{l, i} \tau_{k_l}^{l} = \rho_l, \quad \forall l \in [p], \quad (11i) $$

the CELL-approximation of (8) is $\hat{\omega} := \min_{x \in \mathcal{X}} \hat{\omega}(x)$.

**Proposition 6.** Given uniform partitions $t$ and $\tau$ with $K + 1$ points in the definition of (11) and $(\hat{x}, \hat{\rho}, \hat{\lambda}, \hat{y}, \hat{\xi}, \hat{z}, \hat{\mu})$ some optimal solution for (11) We have

$$ 1. \ 0 \le \omega - \hat{\omega} \le O(1/K) $$

$$ 2. \ \hat{x} \text{ is feasible for (3) and } |\omega(\hat{x}) - \omega| \le O(1/K). $$

*Proof.* Annex Section 8.3 □

<figure><img src="image_4.png" /></figure>
Notice that the approach is valid for any fractional programming problem having separable numerators and denominators. In our case, however, using the rescaling trick of Subsection 2.3 makes all the numerators convex. This implies that we are not forced to use an a priori cell approximation for them as depicted in (11b). In consequence we can use again a cutting plane approach by adding additional variables $\theta_l$ and replacing constraints (11b) by the following:

$$ \sum_{i=1}^{n} \theta_{l}^{i} \leq \sum_{i=1}^{n} \sum_{k_{l}=0}^{K} \sum_{k_{i}=0}^{K} \mu_{k_{l}, k_{i}}^{l, i} \tau_{k_{l}}^{l} D_{i}^{l} (t_{k_{i}}^{i}), \quad \forall l \in [p] \quad (12a) $$

$$ \theta_l^i \geq N_i^l(\hat{x}_i) + (N_i^l)'(\hat{x}_i)(x_i - \hat{x}_i), \quad \forall \hat{x}_i, l \in [p], i \in [n] \quad (12b) $$

The same approximation bound is achieved with smaller tolerances. We can also consider the bounds for the objective $\rho_l$ and the new variables $\theta_l$

$$ e^{L_l^u - U_l^v} \leq \rho_l \leq e^{U_l^u - L_l^v}, \quad \forall l \in [p] $$

$$ e^{L_l^u} \leq \theta_l \leq e^{U_l^u}, \quad \forall l \in [p] $$

### 4.3. A cutting plane approach

The main problem with the cell-approximation (9) is the number of constraints (9c) and the dimension $|\{0, ..., K\}^I|$ of the variable $\mu$. To bypass this issue, we now propose a cutting plane strategy for the generic optimization problem (10):

**Proposition 7.** Given fixed variables $(x, \lambda, z)$ for problem (10), consider the $\mu$-subproblem of (10) (i.e. that optimizes only with respect to $\mu$). Its dual is:

$$ \max_{p,c,d,s} - \sum_{i=1}^{I} \sum_{k \in \{0, \dots, K\}^I} p_{ki} \lambda_{k_i}^i + c + \sum_{i=1}^{I} d_i x_i - \sum_{j=1}^{J} s_j b_j $$

$$ \text{s.t.} \quad - \sum_{i=1}^{I} p_{ki} \lambda_{k_i}^{i} + c + \sum_{i=1}^{I} d_i t_{k_i}^{i} - \sum_{j=1}^{J} s_j g_j (t_{k_1}^{1}, \dots, t_{k_I}^{I}) \leq f(t_{k_1}^{1}, \dots, t_{k_I}^{I}), $$

$$ \forall k \in \{0, \dots, K\}^I $$

$$ p, s \geq 0. $$
It generates the following Benders cuts that are added to the relaxed problem:

$$ \eta \geq - \sum_{i=1}^{I} \sum_{k \in \{0, \dots, K\}^I} \hat{p}_{ki} \lambda_{ki}^{i} + \hat{c} + \sum_{i=1}^{I} \hat{d}_{i} x_{i} - \sum_{j=1}^{J} \hat{s}_{j} b_{j} $$

$$ 0 \geq - \sum_{i=1}^{I} \sum_{k \in \{0, \dots, K\}^I} \hat{p}_{ki} \lambda_{ki}^{i} + \hat{c} + \sum_{i=1}^{I} \hat{d}_{i} x_{i} - \sum_{j=1}^{J} \hat{s}_{j} b_{j} $$

Note that given a feasible solution $(\hat{x}, \hat{\lambda}, \hat{z})$ for (9), the variables $\hat{\lambda}$ are mostly zero except for at most $2I$ of them, meaning that we can fix to zero all the corresponding variables $p$. This suggests a Benders decomposition approach [29] to solve our cell-approximation problem (11). We begin with the following master problem

$$
\begin{array}{ll}
\min_{x, \rho, \theta, \lambda, y, \xi, z} & \displaystyle\sum_{l=1}^{p} \pi^l \rho_l \\
\text{s.t.} & x \in \mathcal{X} \\
& (\lambda^i, z^i) \in \text{LPL}(t^i, K, x_i), \quad \forall i \in [n] \\
& (\xi^l, y^l) \in \text{LPL}(\tau^l, K, \rho_l), \quad \forall l \in [p] \\
& e^{L_l^u - U_l^v} \le \rho_l \le e^{U_l^u - L_l^v}, \quad \forall l \in [p]
\end{array}
$$

and add the cutting planes described in the nest proposition as we need them:

**Proposition 8.** When solving problem (11) with a cut generation strategy, consider the current incumbent $(\hat{x}, \hat{\rho}, \hat{\theta}, \hat{\lambda}, \hat{\xi})$ of the master problem. If $\hat{x}$ violates a linear support function constraint (12) modeled by some $\theta_l^i$, the following cut is added to the master problem:

$$ \theta_l^i \geq N_i^l(\hat{x}_i) + (N_i^l)'(\hat{x}_i)(x_i - \hat{x}_i). $$

If $(\hat{x}, \hat{\rho}, \hat{\theta}, \hat{\lambda}, \hat{\xi})$ makes the subproblem in $\mu$ infeasible, the Benders cut to add to the master problem is:

$$ \sum_{l=1}^{p} \sum_{i=1}^{n} \sum_{k_i=0}^{K} \sum_{k_l=0}^{K} (\hat{r}_{kl}^{li} \xi_{kl}^{l} + \hat{s}_{kl}^{li} \lambda_{ki}^{i}) - \sum_{l=1}^{p} \hat{q}_l \sum_{i=1}^{n} \theta_l^i - \sum_{l=1}^{p} \sum_{i=1}^{n} (\hat{v}_{li} x_i + \hat{w}_{li} \rho_l) \geq \sum_{l=1}^{p} \sum_{i=1}^{n} \hat{u}_{li} $$

where $(\hat{q}, \hat{r}, \hat{s}, \hat{u}, \hat{v}, \hat{w})$ is an optimal ray of the dual of the subproblem in $\mu$.
Notice that the dual of the subproblem in $\mu$ of formulation (11) is in fact separable in $p$ smaller problems:

$$
\begin{align*}
\sum_{l=1}^{p} \max_{q_l, r^l, s^l, u_l, v_l, w_l} & \quad q_l \sum_{i=1}^{n} \theta_l^i - \sum_{i=1}^{n} \sum_{k_i=0}^{K} \sum_{k_l=0}^{K} \left( r_{klk_i}^{li} \hat{\xi}_{kl}^{l} + s_{klk_i}^{li} \hat{\lambda}_{k_i}^{i} \right) \\
& \quad + \sum_{i=1}^{n} (u_{li} + v_{li} \hat{x}_i + w_{li} \hat{\rho}_l) \\
\text{s.t.} \quad & q_l \tau_{kl}^l D_i^l (t_{k_i}^i) - r_{klk_i}^{li} - s_{klk_i}^{li} + u_{li} + v_{li} t_{k_i}^i + w_{li} \tau_{kl}^l \le 0, \\
& \quad \forall i \in [n], (k_l, k_i) \in \{0, \dots, K\}^2 \\
& q_l, r^l, s^l \ge 0
\end{align*}
$$

From this dual we observe that only feasibility cuts are added as the variables $\mu$ do not appear in the objective function. Whenever $\hat{\xi}_{kl}^l = 0$, the objective coefficient for all the variables $r_{klk_i}^{li}$ is zero, meaning that we can make $r_{klk_i}^{li}$ tend to infinity and turn redundant the only constraint where said variable appears. The same phenomenon occurs with $\hat{\lambda}_{k_i}^i = 0$ and the variables $s_{klk_i}^{li}$. Overall, when we are not cutting to solve the LP relaxation, for each pair $(l, i)$ we will have only four non-redundant constraints and eight non-obviously zero variables $r$ and $s$, leaving an LP of linear size in terms of $n$, $K$ and $p$.

As for MINR, let $\hat{\omega}[\mathcal{U}]$ be the optimal value of the relaxed master problem with some cuts only, with Taylor cuts defined by a subset $\mathcal{U}_{li}^x$ of primal points $\hat{x}_i$, and Benders cuts defined by a subset $\mathcal{U}^\mu$ of dual points $(\hat{q}, \hat{r}, \hat{s}, \hat{u}, \hat{v}, \hat{w})$.

# 5. Computational speedups

## 5.1. Primal upper bounds: embedded heuristics

When using a cutting plane approach, it can be hard to decide when to stop. Of course, we can stop whenever we cannot separate the current incumbent, in which case it is feasible and the objective value of our master relaxed problem is that of the full approximated problem. However, waiting for full feasibility can - and does - make the method sloppy in practice. Any valid upper bound for the master problem can provide an optimality gap, therefore having some
way to “repair” an incumbent (i.e. make it feasible for the full approximated problem) is of crucial importance.

The main idea of our heuristics is similar to the arguments “by construc-
tion” from Propositions 3 and 6. In both models, we fix the x components
of the current incumbent, and solve the nonlinear approximated problems: 1)
in (u, v, ρ, ϑ, θ, λ, z, ξ, y) at x fixed for MINR, which can be done by hand by
making constraints tight, and 2) in (ρ, λ, z, ξ, y, μ) at x fixed for CELL, where
optimizing in (ρ, λ, z, ξ, y, μ) is also doable by hand, but solving in μ requires to
solve p LPs with O(n) variables and O(n) constraints each.

5.2. *Smart grids*

From an implementation point of view, it is always interesting to use uniform
grids from their simplicity. However, it is well known that better approximations
can be constructed by choosing wisely the discretization points. We present here
a way to cleverly select a fixed number of points $K$ out of the $\mathcal{K} \gg K$ points of
a uniform grid, such that some error measure is minimized.

“Low Error” Selection with “a few” points. In [30], they show how to select a
subset of the $\mathcal{K}$ points - without any restriction on the size of the subset - such
that the loss in precision plus some ”storage cost” is minimized. They formulate
the problem as a shortest path problem in a directed acyclic network with $\mathcal{K}$
nodes and $\mathcal{K}$ ($\mathcal{K} - 1)/2$ edges. The problem can be seen as a minimization
problem taking the form $\min_{y \in \mathcal{Y}} \{l^\top y + \alpha \cdot e^\top y\}$ where $l$ and $s$ are respectively
a precision loss vector and a unitary weight vector $e$, the latter being ponderated
by some penalization $\alpha \ge 0$. In their formulation, using more edges means
selecting more points: the storage cost per point selected, $\alpha$, is in fact a proxy
to moderate the number of points selected.

*Lowest Error Selection with exactly K points.* With this observation in mind,
our objective is to minimize the same precision loss, while enforcing that the
number of points selected is exactly some number *K*. The problem can be
written as:

$$ \min_{y \in \mathcal{Y}} \{l^{\top} y : e^{\top} y = K\} . $$

Our main idea is to solve the latter problem via a Lagrangean algorithm that will select the best penalization $\alpha^*$ that will give a "good" selection - wrt to the precision loss $l$ - of exactly $K$ points. Given some penalization $\alpha > 0$, the lagrangean relaxation of our problem is

$$ \min_{y \in \mathcal{Y}} \{l^{\top} y + \alpha \cdot e^{\top} y\} - \alpha K . $$

If $\alpha = 0$, all the points are kept by the optimal solution of the lagrangean relaxation, whereas if $\alpha$ is very large, only the first and last point of the grid defined by the $K$ points will be selected. In between, the number of points selected by the optimal solution will be monotone nonincreasing wrt to $\alpha$. The main idea of our algorithm is to select the smallest $\alpha$ such that the optimal solution of the corresponding lagrangean relaxation uses exactly $K$ points.

Moreover, in the multiple adversaries setting, for each variable $x_i$ we use a single grid to approximate all the functions $D_i^l$ for each $l \in [p]$. In consequence, we have to make sure that we are minimizing some kind of joint error amongst the adversaries. The easiest and most straightforward way to attain this goal was to minimize the sum of the errors induced by every function involving $x_i$.

# 6. Computational results

The algorithms presented in this paper were coded in C programming language and run over Dell PowerEdge C6420 cluster nodes with Intel Xeon Gold 6152 CPUs at 2.10GHz with 64Gb RAM each. All the Mixed Integer Linear Programming problems are solved using the callable library of CPLEX[31]. When generating the gradient and Benders cuts or building heuristic solutions from incumbents, we use the user cuts and callbacks technology of the callable library of CPLEX 12.6.
## 6.1. Parameters and instance generation

**Parameters.** We solve all our problems at relative precision $10^{-9}$ in order to make sure that the cuts are taken into account and set a time limit of 3 hours for each run. During the Branch-and-Bound-and-Cut, we separate fractional incumbents only in the root node, and only integer incumbents during the tree search. The heuristics being very fast in practice, they are called each time an incumbent is found by the solver. $K$ initial gradient cuts are added to approximate each of the convex real valued function.

**Payoffs generation.** Although we do not assume zero sum games - i.e. the payoff of any attacker is equal to minus the payoff of the defender - it seems reasonable to assume that in practice, the payoffs should be somehow related. In this goal, we draw the payoffs $R_i^l, \bar{R}_i^l, -P_i^l$ and $-\bar{P}_i^l$ from a uniform distribution in $[0, 1]$.

**Adversaries.** We test our algorithms with $p \in \{5, 7, 10, 12, 15\}$. The rationality coefficient $\lambda^l$ of each attacker is drawn from a uniform distribution in $\lambda \cdot [0.9, 1.1]$, and we make vary $\lambda \in \{0.2, 0.7, 1.2, 1.7, 2.2\}$.

**Defender's risk aversion.** The parameter $\alpha$ captures an absolute risk aversion and penalizes greatly defense strategies whose bad realizations exceed $\alpha$. Noticing that $\alpha$ has units - the same as the payoffs - we selected the parameter $\alpha$ of the Entropic risk measure $\alpha \in \{0.1, 0.3, 0.5, 0.7, 0.9\} \subset [-1, 1]$. Notice that $\alpha$ is a very subjective measure of the risk aversion of the decision maker and as such, it can be difficult to adjust in practice.

**Instance size and operational constraints.** We consider instances with a number of targets $n \in \{10, 20, 30, 40, 50\}$ and a number of resources $m = d \cdot n$ where $d \in \{0.1, 0.2, 0.3, 0.4, 0.5\}$. We consider only the case where only the resource constraint is present, without any operational ones.

**Grids.** The approximation grids have $K$ segments with $K \in \{2, 4, 8, 16, 32\}$. When using smart grids, we consider $K = 256$ sampled points from which we select $K$.
*Base case.* To analyze the influence of each parameter, we took as a base case $n = 20$, $m = 20 \cdot 0.3 = 6$, $p = 7$, $\alpha = 0.5$, $\lambda = 0.7$ and $K = 4$. We then vary $n$, $d$, $p$, $\alpha$, $\lambda$ and $K$ independently and repeat the experiment 10 times.

## 6.2. Algorithmic performances

We test the MINR reformulation and the cell model (CELL) with uniform grids (U) or smart grids (S). For each experiment, we test the expected value maximization (EX) and the entropic risk minimization with $\alpha = 0.5$ (EN). For example, minimizing the entropic risk with the cell model using smart grids is denoted EN-CELL-S.

During the Branch and Bound and Cut procedure, let us define $L := \hat{\omega}[U]$ as the best relaxation bound so far, $U := \hat{\omega}(\hat{x})$ the objective value of the best solution so far $\hat{x}$ for the approximated problem, $R := \omega(\hat{x})$ the real objective value of the best solution so far $\hat{x}$ for the original problem. All the bounds found by each algorithm upon termination, $L$, $U$ and $R$, are presented as the fraction of the best bound $R^*$ found on the same instance by any algorithm.

*General impression.* We show high level performance indicators in Table 2. Solving EN and EXP take similar execution times, however, the bounds and gaps are better for ENT (higher $L$, lower $U$ and $R$). We can also see that MINR is faster and provides better bounds than CELL. Using smart grids makes the overall solution slightly slower for both algorithms and provides worse bounds for CELL but improves them for MINR. The process takes longer using smart grids because the optimization problems become harder: in fact, selecting $K$ points out of $K$ for all the functions to approximate takes on average 4 seconds and 11 seconds in the worst case.

*Parameters' influence.* In Table 3, we present the final gaps and the execution times in function of the parameters. The execution time steadily increases until reaching the limit of 3 hours (marked "*") with every parameter $n$, $d$, $p$, $K$, $\lambda$ and $\alpha$. We have the confirmation at a finer level that the MINR model outperforms CELL, and that the smart grids help to close the final gaps. More
<table><caption>Table 2: Overall average normalized bounds. Time in seconds, gaps in %.</caption><thead><tr><th rowspan="3">risk measure</th><th colspan="4">EX</th><th colspan="4">EN</th></tr><tr><th colspan="2">CELL</th><th colspan="2">MINR</th><th colspan="2">CELL</th><th colspan="2">MINR</th></tr><tr><th>U</th><th>S</th><th>U</th><th>S</th><th>U</th><th>S</th><th>U</th><th>S</th></tr></thead><tbody><tr><th>model</th><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><th>grid</th><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><th>time</th><td>9171</td><td>9534</td><td>7436</td><td>7458</td><td>9364</td><td>9503</td><td>7232</td><td>7280</td></tr><tr><th>L</th><td>0.870</td><td>0.869</td><td>0.973</td><td>0.975</td><td>0.894</td><td>0.892</td><td>0.977</td><td>0.980</td></tr><tr><th>U</th><td>0.962</td><td>0.968</td><td>0.983</td><td>0.984</td><td>0.969</td><td>0.973</td><td>0.986</td><td>0.987</td></tr><tr><th>R</th><td>1.001</td><td>1.001</td><td>1.000</td><td>1.000</td><td>1.002</td><td>1.002</td><td>1.000</td><td>1.000</td></tr><tr><th>appGap</th><td>9.852</td><td>10.480</td><td>1.045</td><td>0.883</td><td>7.955</td><td>8.615</td><td>0.941</td><td>0.792</td></tr><tr><th>realGap</th><td>13.071</td><td>13.171</td><td>2.755</td><td>2.490</td><td>10.808</td><td>10.991</td><td>2.294</td><td>2.041</td></tr></tbody></table>

detailed results can be found in the Appendix Section 8.4 (Tables 7, 8, 9, 10, 11 and 12).

*Example of bounds progress with time.* In Figure 1, we present an example of bound progression over time in the base case. It illustrates the fact that in terms of the relaxation bound L (solid line), LMINRP (no □ symbol) is very superior to CELL (□) and that the smart grids (in black) do outperform the uniform grids (in gray). We can also confirm that in terms of real objective value *R* (dotted line) both algorithms are quite equivalent. More importantly the algorithms begin to stall after an hour, suggesting that the cut generation mechanisms in use might be improved

## 6.3. Qualitative results

*Probability distribution calculation.* To compare a risk neutral defense policy with a risk averse one, we want to see if there is some kind of stochastic dominance of a risk averse strategy versus a risk neutral one. To do so, we compare the payoffs distributions of the defender depending on its risk aversion. In practice, the defender can cover *m* targets out of *n* and the attackers target a single place each. The only possible outcomes for the defender are: 1) being attacked on a defended target *i* by attacker *l* with payoff $V = \bar{R}_i^l > 0$ or 2) being attacked on an undefended target *i* by attacker *l* with payoff $V = \bar{P}_i^l < 0$. Consequently,
<figure><img src="image_5.png" /><figcaption>Figure 1: Normalized bounds over time (in seconds) in the base case.</figcaption></figure>

if we assume that all the payoffs $\bar{R}_i^l$ and $\bar{P}_i^l$ are different the only values possible are in

$$V \in \{V_1 < V_2 < \dots < V_{2np-1} < V_{2np}\} = \bigcup_{l=1}^{p} \bigcup_{i=1}^{n} \{\bar{R}_i^l, \bar{P}_i^l\}.$$

Recall from Section 2 that given a mixed defense strategy $x \in [0, 1]^n$ and the associated QR $y(x) \in [0, 1]^n$, the payoff of the defender is:

$\bar{P}_i^l$ with probability $\pi^l y_i^l(x)(1 - x_i)$

$\bar{R}_i^l$ with probability $\pi^l y_i^l(x)x_i$.

This way we can compute the probability distribution of the payoff of any defender without sampling a large number of simulations. We compare the expected value, variance, Value at Risk (VaR) at level 10%, Conditional Value at Risk (CVaR) at level 10% and entropic risk at level $\alpha' = 0.5$ in function of $\alpha$ and $\lambda$.

*General comments.* We now compare all the solutions obtained with MINR-S, as the solutions it provides showed to be the most reliable. All the indicators
are given as the fraction of the same indicator for the risk neutral solution with the base case parameter.

There is no clear influence of the parameters $n$, $p$ and the number of break-points $K$. However, the remaining parameters do have a strong influence on the characteristics of a risk averse solution.

*α influence.* In Table 4, we can see that by decreasing $α$ (i.e. getting more risk averse), there is a clear improvement in terms of all the risk aversion indicators. That can come, however, at the cost of a significant loss in expected payoff.

<table><caption>Table 4: Quality Vs. α. All indicators are losses.</caption><thead><tr><th>risk m.</th><th>E<sub>α=0.1</sub></th><th>E<sub>α=0.3</sub></th><th>E<sub>α=0.5</sub></th><th>E<sub>α=0.7</sub></th><th>E<sub>α=0.9</sub></th><th>E</th></tr></thead><tbody><tr><td>E</td><td>1.294</td><td>1.108</td><td>1.048</td><td>1.027</td><td>1.019</td><td>1</td></tr><tr><td>V</td><td>0.840</td><td>0.881</td><td>0.919</td><td>0.939</td><td>0.949</td><td>1</td></tr><tr><td>VaR<sub>10</sub></td><td>0.954</td><td>0.952</td><td>0.972</td><td>0.985</td><td>0.991</td><td>1</td></tr><tr><td>CVaR<sub>10</sub></td><td>0.957</td><td>0.973</td><td>0.985</td><td>0.990</td><td>0.991</td><td>1</td></tr><tr><td>E<sub>α=0.5</sub></td><td>1.029</td><td>0.981</td><td>0.978</td><td>0.980</td><td>0.983</td><td>1</td></tr></tbody></table>

*λ influence.* In Table 5, we can see that facing increasingly rational adversaries has a significant negative impact on the risk neutral solution, whereas the risk averse solutions hedge well against smarter ennemies.

<table><caption>Table 5: Quality Vs. λ. All indicators are losses.</caption><thead><tr><th>λ</th><th colspan="2">0.2</th><th colspan="2">0.7</th><th colspan="2">1.2</th><th colspan="2">1.7</th><th colspan="2">2.2</th></tr><tr><th>risk m.</th><th>ENT</th><th>EXP</th><th>ENT</th><th>EXP</th><th>ENT</th><th>EXP</th><th>ENT</th><th>EXP</th><th>ENT</th><th>EXP</th></tr></thead><tbody><tr><td>E</td><td>0.979</td><td>0.921</td><td>1.048</td><td>1</td><td>1.061</td><td>1.013</td><td>1.070</td><td>1.016</td><td>1.096</td><td>1.019</td></tr><tr><td>V</td><td>0.926</td><td>1.033</td><td>0.920</td><td>1</td><td>0.912</td><td>0.986</td><td>0.893</td><td>0.972</td><td>0.854</td><td>0.971</td></tr><tr><td>VaR<sub>10</sub></td><td>0.952</td><td>0.994</td><td>0.973</td><td>1</td><td>0.976</td><td>0.998</td><td>0.966</td><td>0.998</td><td>0.955</td><td>0.999</td></tr><tr><td>CVaR<sub>10</sub></td><td>0.974</td><td>0.992</td><td>0.985</td><td>1</td><td>0.987</td><td>1.001</td><td>0.983</td><td>0.999</td><td>0.977</td><td>0.999</td></tr><tr><td>E<sub>α=0.5</sub></td><td>0.952</td><td>0.977</td><td>0.979</td><td>1</td><td>0.981</td><td>1.000</td><td>0.975</td><td>0.995</td><td>0.966</td><td>0.995</td></tr></tbody></table>

*d influence.* In Table 6, we can observe - without surprise - that having more resources (higher values of $d$) has an extremely strong impact on the quality of
<figure><img src="image_6.png" /><figcaption>Figure 2: Cumulative distributions of the loss for $x(E_{0.5})$ (black) and $x(E)$ (gray)</figcaption></figure>

the solution: in fact, when we are able to cover simultaneously half the targets ($d = 0.5$), the expected losses of both the risk averse and risk neutral policies become negative.

<table><caption>Table 6: Quality Vs. $d$. All indicators are losses.</caption><thead><tr><th rowspan="2">risk m.</th><th colspan="2">0.1</th><th colspan="2">0.2</th><th colspan="2">0.3</th><th colspan="2">0.4</th><th colspan="2">0.5</th></tr><tr><th>ENT</th><th>EXP</th><th>ENT</th><th>EXP</th><th>ENT</th><th>EXP</th><th>ENT</th><th>EXP</th><th>ENT</th><th>EXP</th></tr></thead><tbody><tr><td>E</td><td>2.122</td><td>2.105</td><td>1.590</td><td>1.546</td><td>1.048</td><td>1</td><td>0.524</td><td>0.457</td><td>-0.027</td><td>-0.088</td></tr><tr><td>V</td><td>0.568</td><td>0.608</td><td>0.761</td><td>0.834</td><td>0.92</td><td>1</td><td>1.009</td><td>1.095</td><td>1.052</td><td>1.128</td></tr><tr><td>VaR<sub>10</sub></td><td>1.036</td><td>1.048</td><td>1.008</td><td>1.022</td><td>0.973</td><td>1</td><td>0.923</td><td>0.963</td><td>0.872</td><td>0.913</td></tr><tr><td>CVaR<sub>10</sub></td><td>1.018</td><td>1.023</td><td>1.001</td><td>1.012</td><td>0.985</td><td>1</td><td>0.96</td><td>0.985</td><td>0.933</td><td>0.963</td></tr><tr><td>E<sub>α=0.5</sub></td><td>1.262</td><td>1.271</td><td>1.124</td><td>1.138</td><td>0.979</td><td>1</td><td>0.82</td><td>0.844</td><td>0.641</td><td>0.669</td></tr></tbody></table>

*Example of distributions E*<sub>α</sub> Vs. E. In Figure 2, we compare the cumulative distributions of a risk averse solution (black) and that of a risk neutral solution (gray). We can see that past the *loss* 0.7, the risk averse solution dominates the risk averse one. The variance of the risk averse solution is 20% lower at the cost of losing a 30% in payoff.

## 7. Conclusions

In this paper, we extended the classic model of Stackelberg security games with quantal response to a risk averse setting for the defender and facing sev-
eral adversaries with different degrees of rationality. We presented two ways of
finding an approximately optimal defense strategy by solving nonlinear MIPs
via cutting planes. The first methodology (CELL) has a broader range of ap-
plications, but the second (MINR) is more efficient, both in solution quality
and execution time, and offers a reasonable performance for practical mid-sized
cases. Computational results showed that minimizing an Entropic risk measure
instead of maximizing the expected value can be advantageous from a qualita-
tive point of view, allowing to significantly reduce the overall payoff variance
and the probability of bad scenarios to occur.

Being cutting planes methods, our algorithms suffered from a sloppy behav-
ior towards the end of the tree search. In a future work, we should investigate
the use of stronger cuts, stabilization methods, or the fine tuning of the cut
generation process. The Entropic risk measure is not the only way to introduce
risk aversion in the behavior of an agent: In fact, there is a whole array of
risk aversion-inducing tools in the literature that can be used instead. In an
ongoing work, we show that using classical risk measures such as Value-at-Risk,
Conditional-Value-at-Risk, upper semi-deviations, etc... the resulting optimiza-
tion problems have the same structure as the ones described in this paper.

## Acknowledgements

Powered@NLHPC: This research was partially supported by the supercom-
puting infrastructure of the NLHPC (ECM-02) and funded by Conicyt through
grant FONDEF No. D10I1002.

## References

[1] H. Von Stackelberg, The theory of the market economy, William Hodge, 1952.

[2] V. M. Bier, Choosing what to protect, Risk Analysis 27 (3) (2007) 607–620.
[3] G. Brown, M. Carlyle, J. Salmerón, K. Wood, Defending critical infrastructure, Interfaces 36 (6) (2006) 530–544.

[4] D. Kar, T. H. Nguyen, F. Fang, M. Brown, A. Sinha, M. Tambe, A. X. Jiang, Trends and applications in stackelberg security games, Handbook of Dynamic Game Theory (2017) 1–47.

[5] P. Paruchuri, J. Pearce, J. Marecki, M. Tambe, F. Ordóñez, S. Kraus, Playing games for security: An efficient exact algorithm for solving bayesian stackelberg games, in: Proceedings of the 7th AAMAS Conference, Estoril, Portugal, International Foundation for AAMAS, 2008.

[6] M. Jain, J. Tsai, J. Pita, C. Kiekintveld, S. Rathi, M. Tambe, F. Ordóñez, Software assistants for randomized patrol planning for the LAX airport police and the federal air marshal service, Interfaces 40 (4) (2010) 276–290.

[7] F. M. Delle Fave, A. X. Jiang, Z. Yin, C. Zhang, M. Tambe, S. Kraus, J. P. Sullivan, Game-theoretic security patrolling with dynamic execution uncertainty and a case study on a real transit system, Journal of Artificial Intelligence Research 50 (2014) 321–367.

[8] B. An, F. Ordóñez, M. Tambe, E. Shieh, R. Yang, C. Baldwin, J. Di-Renzo III, K. Moretti, B. Maule, G. Meyer, A deployed quantal response-based patrol planning system for the U.S. Coast Guard, Interfaces 43 (5) (2013) 400–420.

[9] R. Yang, F. Ordóñez, M. Tambe, Computing optimal strategy against quantal response in security games, in: Proceedings of the 11th AAMAS, Valencia, Spain, Vol. 2, International Foundation for AAMAS, 2012, pp. 847–854.

[10] R. Chicoisne, F. Ordóñez, Risk averse stackelberg security games with quantal response, in: Proceedings of GameSec 2016, New York, Vol. LNCS 9996, 2016, pp. 83–100.
[11] J. Pita, M. Jain, F. Ordóñez, M. Tambe, S. Kraus, Solving stackelberg games in the real-world: Addressing bounded rationality and limited obser- vations in human preference models, Artificial Intelligence Journal 174 (15) (2010) 1142–1171.

[12] C. Camerer, T.-H. Ho, J.-K. Chong, A cognitive hierarchy model of games, The Quarterly Journal of Economics 119 (3) (2004) 861–898.

[13] R. McKelvey, T. Palfrey, Quantal response equilibria for normal form games, Games and economic behavior 10 (1) (1995) 6–38.

[14] P. Haile, A. Hortaçsu, G. Kosenok, On the empirical content of quantal response equilibrium, The American Economic Review 98 (1) (2008) 180–200.

[15] D. Stahl II, P. Wilson, Experimental evidence on players’ models of other players, Journal of economic behavior & organization 25 (3) (1994) 309–327.

[16] J. Wright, K. Leyton-Brown, Beyond equilibrium: Predicting human be- havior in normal-form games., in: Proceedings of the 24th AAAI conference on artificial intelligence, Atlanta, GA, 2010.

[17] M. Ben-Akiva, S. R. Lerman, Discrete choice analysis: theory and applica- tion to travel demand, Transportation Studies, 2018.

[18] D. H. Gensch, W. W. Recker, The multinomial, multiattribute logit choice model, Journal of Marketing Research 16 (1) (1979) 124–132.

[19] R. Yang, C. Kiekintveld, F. Ordóñez, M. Tambe, R. John, Improving re- source allocation strategy against human adversaries in security games, in: 22th IJCAI Proceedings, Barcelona, Spain, Vol. 22, AAAI Press, 2011, pp. 458–464.

[20] J. W. Pratt, Risk aversion in the small and in the large, Econometrica: Journal of the Econometric Society 32 (1/2) (1964) 122–136.
[21] J. C. Harsanyi, Games with incomplete information played by “bayesian” players, i-iii: Part i. the basic model, Management Science 14 (3) (1967) 159–182.

[22] G. R. Bitran, J.-C. Ferrer, On pricing and composition of bundles, Production and Operations Management 16 (1) (2007) 93–108.

[23] H. Liu, D. Z. Wang, Global optimization method for network design problem with stochastic user equilibrium, Transportation Research Part B: Methodological 72 (2015) 20–39.

[24] J. Vielma, G. Nemhauser, Modeling disjunctive constraints with a logarithmic number of binary variables and constraints, Mathematical Programming 128 (1-2) (2011) 49–72.

[25] E. Gilbert, Gray codes and paths on the n-cube, Bell System Technical Journal 37 (3) (1958) 815–826.

[26] D. E. Knuth, The art of computer programming: sorting and searching, Vol. 3, Pearson Education, 1998.

[27] L. S. Thakur, Error analysis for convex separable programs: the piecewise linear approximation and the bounds on the optimal objective value, SIAM Journal on Applied Mathematics 34 (4) (1978) 704–714.

[28] R. Rovatti, C. D'Ambrosio, A. Lodi, S. Martello, Optimistic milp modeling of non-linear optimization problems, European Journal of Operational Research 239 (1) (2014) 32–45.

[29] J. Benders, Partitioning procedures for solving mixed-variables programming problems, Numerische Mathematik 4 (1) (1962) 238–252.

[30] R. Ahuja, T. Magnanti, J. Orlin, Network flows: theory, algorithms, and applications, Prentice hall, 1993.

[31] CPLEX, V12. 1: User Manual for CPLEX (2009).
# 8. Appendix

## 8.1. Proof of Proposition 3

1) We first show that $\hat{\omega} \le \omega$. Since by Proposition 1, (4) is equivalent to (3), we now use an optimal solution $(\tilde{x}, \tilde{u}, \tilde{v})$ for (4) to construct a feasible point in (6). Given $\tilde{x}$ and $\tilde{u}$, there is a unique tuple $(\tilde{\lambda}, \tilde{z}, \tilde{\xi}, \tilde{y})$ that satisfies the LPL constraints (6l) and (6m). Setting $\tilde{\rho}_l := e^{\tilde{u}_l - \tilde{v}_l}$, $\tilde{\theta}_l^i := N_i^l(\tilde{x}_i)$ and $\tilde{\vartheta}_l := e^{\tilde{v}_l}$ we have that $(\tilde{x}, \tilde{u}, \tilde{v}, \tilde{\rho}, \tilde{\vartheta}, \tilde{\theta}, \tilde{\lambda}, \tilde{z}, \tilde{\xi}, \tilde{y})$ is feasible for (6) after using the constraints of (4) that $(\tilde{x}, \tilde{u}, \tilde{v})$ satisfies and Proposition 1. Its objective value in (6) is $\sum_{l=1}^p \pi^l e^{\tilde{u}_l - \tilde{v}_l} \ge \hat{\omega}$. Given that $\omega = \sum_{l=1}^p \pi^l e^{\tilde{u}_l - \tilde{v}_l}$, we obtain the result.

We now show that a slight change in $(\hat{x}, \hat{u}, \hat{v})$ is feasible for (4). Notice that $\hat{x} \in \mathcal{X}$ and is thus feasible for (1). We can see that $(\hat{x}, \hat{u}, \hat{v}, \hat{\rho}, \hat{\vartheta}, \hat{\theta}, \hat{\lambda}, \hat{z}, \hat{\xi}, \hat{y})$ satisfies:

$$ \hat{\rho}_l = e^{\hat{u}_l - \hat{v}_l}, \quad \mathcal{P}_{\tau^l}[e^l](\hat{u}_l) = N^l(\hat{x}), \quad e^{\hat{v}_l} = \mathcal{P}_l[D^l](\hat{x}) := \sum_{i=1}^n \mathcal{P}_{t_i}[D_i^l](\hat{x}_i). \quad (14) $$

However, feasible solutions to (4) must satisfy $e^{u_l} \ge N^l(x)$ and $e^{v_l} \le D^l(x)$. Recall that $\mathcal{P}_l[f]$ is the LPL approximation of $f$ on the grid $t$. From Proposition 1 we have that $D^l(x) \le \mathcal{P}_l[D^l](x) \le D^l(x) + \epsilon_1$ and that $e^{u_l} \le \mathcal{P}_{\tau^l}[e^l](u_l) \le e^{u_l} + \epsilon_2$. The values $\epsilon_1$ and $\epsilon_2$ are of the form $\mathcal{L}C/(2K) = O(1/K)$, where $\mathcal{L}$ is a constant that depends on the function being approximated and $C/K$ denotes the interval width in the uniform partition. Combining these bounds with the last two equalities in (14), we can define $u'$ and $v'$ such that

$$ e^{u'_l} := e^{\hat{u}_l} + \epsilon_2 \ge N^l(\hat{x}), \quad e^{v'_l} := e^{\hat{v}_l} - \epsilon_1 \le D^l(\hat{x}). \quad (15) $$

The solution $(\hat{x}, u', v')$ is then feasible for (4), which means that

$$ \omega \le \sum_{l=1}^{p} \pi^l e^{u'_l - v'_l} = \sum_{l=1}^{p} \pi^l \frac{e^{\hat{u}_l} + \epsilon_2}{e^{\hat{v}_l} - \epsilon_1}. \quad (16) $$

The first equation in (14) implies that $\hat{\omega} = \sum_{l=1}^p \pi^l e^{\hat{u}_l - \hat{v}_l}$. Combining this with (16) we obtain

$$ 0 \le \omega - \hat{\omega} \le \sum_{l=1}^{p} \pi^l \left( \frac{e^{\hat{u}_l} + \epsilon_2}{e^{\hat{v}_l} - \epsilon_1} - \frac{e^{\hat{u}_l}}{e^{\hat{v}_l}} \right) = \sum_{l=1}^{p} \pi^l \frac{\epsilon_2 e^{\hat{v}_l} + \epsilon_1 e^{\hat{u}_l}}{e^{\hat{v}_l} (e^{\hat{v}_l} - \epsilon_1)}. $$
From Proposition 1 and (14) we have that $N^l(\hat{x}) \ge e^{\hat{u}_l}$ and $e^{\hat{v}_l} \ge D^l(\hat{x})$. Defining $\epsilon = \max\{\epsilon_1, \epsilon_2\}$, $N^+ := \max_{l \in [p], x \in \mathcal{X}} N^l(x)$, $D^+ := \max_{l \in [p], x \in \mathcal{X}} D^l(x)$ and $D^- := \min_{l \in [p], x \in \mathcal{X}} D^l(x)$, the following gives the result since $\epsilon = O(1/K)$:

$$0 \le \omega - \hat{\omega} \le \epsilon \frac{N^+ + D^+ + \epsilon_1}{D^- (D^- - \epsilon_1)}.$$

2) Now we show that $|\omega - \omega(\hat{x})| \le O(1/K)$. We already have that $\hat{x}$ is feasible for (1) and $\omega \ge \hat{\omega}$. This, and the inequalities in (15) imply

$$\omega(\hat{x}) \ge \omega \ge \hat{\omega} = \sum_{l=1}^{p} \pi^l \frac{e^{\hat{u}_l}}{e^{\hat{v}_l}} \ge \sum_{l=1}^{p} \pi^l \frac{N^l(\hat{x}) - \epsilon_2}{D^l(\hat{x}) + \epsilon_1}.$$

Since $\omega(\hat{x}) = \sum_{l=1}^{p} \pi^l N^l(\hat{x})/D^l(\hat{x})$, similar to the previous derivation we have

$$0 \le \omega(\hat{x}) - \omega \le \sum_{l=1}^{p} \pi^l \left( \frac{N^l(\hat{x})}{D^l(\hat{x})} - \frac{N^l(\hat{x}) - \epsilon_2}{D^l(\hat{x}) + \epsilon_1} \right) \\ \le \epsilon \frac{N^+ + D^+}{D^- (D^- + \epsilon_1)} = O(1/K). \quad \square$$

## 8.2. Proof of Proposition 4

Consider some $j \in [J]$. By definition, for any $x \in \mathcal{G}$ there exists some tuple $(\mu, \lambda, z)$ satisfying (9) such that

$$\begin{aligned} \Delta_j(x) := |f_j(x) - C_t[f_j](x)| &= \left| f_j(x) - \sum_{k \in \{0, \dots, K\}^I} \mu_k f_j(t_{k_1}^1, \dots, t_{k_I}^I) \right| \\ &= \left| \sum_{k \in \{0, \dots, K\}^I} \mu_k [f_j(x) - f_j(t_{k_1}^1, \dots, t_{k_I}^I)] \right| \\ &\le \sum_{k \in \{0, \dots, K\}^I} \mu_{k_1, \dots, k_I} |f_j(x) - f_j(t_{k_1}^1, \dots, t_{k_I}^I)| . \end{aligned}$$

The second equality is due to $||\mu||_1 = 1$ and the inequality comes from the convexity of $|\cdot|$. Next, because we have $(\lambda^i, z^i) \in LPL(t^i, K, x_i)$ for any $i \in [I]$, there is an index $k_i^x \in \{0, \dots, K-1\}$ such that $t_{k_i^x}^i \le x_i \le t_{k_i^x+1}^i$ and the only possible nonzero values of $\lambda^i$ are $\lambda_{k_i^x}^i$ and $\lambda_{k_i^x+1}^i$. In consequence, constraints (9c) enforce that the only possible nonzero components of $\mu$ are the $\mu_{k_1, \dots, k_I}$
with $k_i \in \{k_i^x, k_i^x + 1\}$ for every $i \in [I]$. We then obtain:

$$
\begin{align*}
\Delta_j(x) &\le \sum_{k_1=k_1^x}^{k_1^x+1} \dots \sum_{k_I=k_I^x}^{k_I^x+1} \mu_{k_1, \dots, k_I} |f_j(x) - f_j(t_{k_1}^1, \dots, t_{k_I}^I)| \\
&\le \max_{k_i \in \{k_i^x, k_i^x+1\}, i \in [I]} |f_j(x) - f_j(t_{k_1}^1, \dots, t_{k_I}^I)| \|\mu\|_1 \\
&\le \max_{k_i \in \{k_i^x, k_i^x+1\}, i \in [I]} \mathcal{L}_j \|x - (t_{k_1}^1, \dots, t_{k_I}^I)\|_1 \\
&= \mathcal{L}_j \sum_{i=1}^I \max_{k_i \in \{k_i^x, k_i^x+1\}} |x_i - t_{k_i}^i|
\end{align*}
$$

Where the $\mathcal{L}_j$-Lipschitz assumption and $\|\mu\|_1 = 1$ are used. Define $\mathcal{G}(x)$ as the cell of the discretization of $\mathcal{G}$ that contains $x$, i.e.

$$
\mathcal{G}(x) := \{ x' \in \mathcal{G} : t_{k_i}^{i,x} \le x'_i \le t_{k_i}^{i,x+1}, \forall i \in [I] \}.
$$

Given that $x \in \mathcal{G}(x)$ we have that:

$$
\begin{align*}
\Delta_j(x) &\le \max_{x' \in \mathcal{G}(x)} \mathcal{L}_j \sum_{i=1}^{I} \max_{k_i \in \{k_i^x, k_i^x+1\}} |x'_i - t_{k_i}^i| \\
&= \mathcal{L}_j \sum_{i=1}^{I} \max_{k_i \in \{k_i^x, k_i^x+1\}} \max_{x'_i \in [t_{k_i^x}^1, t_{k_i^x+1}^1]} |x'_i - t_{k_i}^i| \\
&= \mathcal{L}_j \sum_{i=1}^{I} |t_{k_i^x+1}^i - t_{k_i^x}^i| = \frac{\mathcal{L}_j}{K} \sum_{i=1}^{I} |u_i - l_i| = \frac{\mathcal{L}_j}{K} \|u - l\|_1 . \quad \square
\end{align*}
$$

8.3. *Proof of Proposition 6*

For any $x \in \mathcal{X}$ and $\rho_l \in \mathbb{R}, l \in [p]$, let us define $\mathcal{N}^l(x) := \sum_{i=1}^n \mathcal{C}_{t_i}[N_i^l](x_i)$ and $\mathcal{D}^l(x, \rho_l) := \sum_{i=1}^n \mathcal{C}_{\tau^l, t_i}[\mathcal{D}_i^l(\cdot)](\rho_l, x_i)$. We have from Proposition 4 that
$$ - \epsilon_l \le \mathcal{N}^l(x) - \rho_l \mathcal{D}^l(x) - (\mathcal{N}^l(x) - \mathcal{D}^l(x, \rho_l)) \le \epsilon_l, $$

for some $\epsilon_l > 0$ that is $O(1/K)$. Defining $\tilde{\rho}_l(x) := N^l(x)/D^l(x)$ and using $D^l(x) > 0$, we obtain:

$$
\frac{\mathcal{N}^l(x) - \mathcal{D}^l(x, \rho_l) - \epsilon_l}{D^l(x)} + \rho_l \le \frac{\mathcal{N}^l(x) - \mathcal{D}^l(x, \rho_l) + \epsilon_l}{D^l(x)} + \rho_l. \quad (17)
$$
Because $(\hat{x}, \hat{\rho}, \hat{\lambda}, \hat{y}, \hat{\xi}, \hat{z}, \hat{\mu})$ is optimal - hence feasible - for (11), we have that $\mathcal{N}^l(\hat{x}) - \mathcal{D}^l(\hat{x}, \hat{\rho}) \le 0$. Letting $\tilde{x}$ be an optimal solution for (3) and using the right inequality in (17) at $(\hat{x}, \hat{\rho})$ gives

$$ \omega(\hat{x}) = \sum_{l=1}^{p} \pi^l \tilde{\rho}_l(\hat{x}) \le \sum_{l=1}^{p} \pi^l \left( \frac{\epsilon_l}{D^l(\hat{x})} + \hat{\rho}_l \right) \quad (18a) $$

$$ = \sum_{l=1}^{p} \frac{\pi^l \epsilon_l}{D^l(\hat{x})} + \hat{\omega} \quad (18b) $$

$$ \le \sum_{l=1}^{p} \frac{\pi^l \epsilon_l}{D^l(\tilde{x})} + \hat{\omega}(\tilde{x}) \quad (18c) $$

Second, consider a function $f: \mathbb{R}^n \to \mathbb{R}$ and its cell-approximation $C_t[f]$. Notice that if the function $y \to f(x_1, \dots, x_{i-1}, y, x_{i+1}, \dots, x_n)$ is nondecreasing, then so is the function $y \to C_t[f](x_1, \dots, x_{i-1}, y, x_{i+1}, \dots, x_n)$. Since $\rho \to -\rho D^l(x)$ is decreasing then so is $\rho \to -\mathcal{D}^l(x, \rho)$. This means that there is $\hat{\rho}_l(x)$ such that $\mathcal{N}^l(x) - \mathcal{D}^l(x, \hat{\rho}_l(x)) = 0$. The left inequality of (17) at $\tilde{x}$ and $\hat{\rho}_l(\tilde{x})$ implies

$$ \hat{\omega}(\tilde{x}) = \sum_{l=1}^{p} \pi^l \hat{\rho}_l(\tilde{x}) \le \sum_{l=1}^{p} \pi^l \left( \hat{\rho}_l(\tilde{x}) + \frac{\epsilon_l}{D^l(\tilde{x})} \right) \quad (19a) $$

$$ \le \omega + \sum_{l=1}^{p} \frac{\pi^l \epsilon_l}{D^l(\tilde{x})} \quad (19b) $$

Adding (18c) and (19b) together and defining $D^- := \min_{l \in [p], x \in \mathcal{X}} D^l(x)$ and $\epsilon := \max_{l \in [p]} \epsilon_l$, we get:

$$ 0 \le \omega(\hat{x}) - \omega \le \sum_{l=1}^{p} \pi^l \epsilon_l \left( \frac{1}{D^l(\hat{x})} + \frac{1}{D^l(\tilde{x})} \right) \le \frac{2\epsilon}{D^{-}} = O(1/K). $$

We now prove $|\omega - \hat{\omega}| = O(1/K)$. From (18b) and by optimality of $\tilde{x}$ we get

$$ \omega - \hat{\omega} \le \omega(\hat{x}) - \hat{\omega} \le \sum_{l=1}^{p} \frac{\pi^l \epsilon_l}{D^l(\hat{x})} \le \frac{\epsilon}{D^{-}} = O(1/K). $$

We now finish by proving $\hat{\omega} \le \omega$. Let $\bar{\rho}_l(x)$ such that $\mathcal{N}^l(x) - \mathcal{D}^l(x, \bar{\rho}_l(x)) = \epsilon_l$ and remark that from optimality considerations, we have $\bar{\rho}_l(x) \ge \hat{\rho}_l(x)$. The left inequality of (17) at $\tilde{x}$ and $\bar{\rho}_l(\tilde{x})$ implies that: $0 \le \tilde{\rho}_l(\tilde{x}) - \bar{\rho}_l(\tilde{x}) \le \tilde{\rho}_l(\tilde{x}) - \hat{\rho}_l(\tilde{x})$, implying in turn that

$$ 0 \le \sum_{l=1}^{p} \pi^l (\tilde{\rho}_l(\tilde{x}) - \hat{\rho}_l(\tilde{x})) = \omega - \hat{\omega} \quad \square $$
8.4. *Full result Tables*

In Tables 7, 8, 9, 10, 11 and 12 we present the full bounds over all the
parameters.
<table><caption>Table 7: Performances Vs. n. "*" = 3h time out</caption><thead><tr><th rowspan="3">risk measure</th><th colspan="8">EX</th><th colspan="2">EN</th></tr><tr><th colspan="2">model</th><th colspan="2">CELL</th><th colspan="2">MINR</th><th colspan="2">CELL</th><th colspan="2">MINR</th></tr><tr><th>grid</th><th>n</th><th>U</th><th>S</th><th>U</th><th>S</th><th>U</th><th>S</th><th>U</th><th>S</th></tr></thead><tbody><tr><td rowspan="5">time</td><td rowspan="5">n</td><td>10</td><td>2498</td><td>5354</td><td>14</td><td>6</td><td>1287</td><td>2809</td><td>10</td><td>7</td></tr><tr><td>20</td><td>*</td><td>*</td><td>3837</td><td>4387</td><td>*</td><td>*</td><td>5640</td><td>5479</td></tr><tr><td>30</td><td>*</td><td>*</td><td>*</td><td>*</td><td>*</td><td>*</td><td>*</td><td>*</td></tr><tr><td>40</td><td>*</td><td>*</td><td>*</td><td>*</td><td>*</td><td>*</td><td>*</td><td>10797</td><td>*</td></tr><tr><td>50</td><td>*</td><td>*</td><td>*</td><td>*</td><td>*</td><td>*</td><td>*</td><td>*</td><td>*</td></tr><tr><td rowspan="5">L</td><td rowspan="5">n</td><td>10</td><td>0.983</td><td>0.983</td><td>0.990</td><td>0.988</td><td>0.986</td><td>0.986</td><td>0.991</td><td>0.990</td></tr><tr><td>20</td><td>0.918</td><td>0.912</td><td>0.990</td><td>0.988</td><td>0.940</td><td>0.937</td><td>0.991</td><td>0.990</td></tr><tr><td>30</td><td>0.887</td><td>0.881</td><td>0.981</td><td>0.979</td><td>0.915</td><td>0.912</td><td>0.983</td><td>0.982</td></tr><tr><td>40</td><td>0.872</td><td>0.869</td><td>0.976</td><td>0.973</td><td>0.887</td><td>0.888</td><td>0.977</td><td>0.976</td></tr><tr><td>50</td><td>0.865</td><td>0.864</td><td>0.973</td><td>0.970</td><td>0.879</td><td>0.879</td><td>0.973</td><td>0.972</td></tr><tr><td rowspan="5">U</td><td rowspan="5">n</td><td>10</td><td>0.983</td><td>0.984</td><td>0.990</td><td>0.988</td><td>0.986</td><td>0.986</td><td>0.991</td><td>0.991</td></tr><tr><td>20</td><td>0.983</td><td>0.984</td><td>0.990</td><td>0.988</td><td>0.985</td><td>0.987</td><td>0.991</td><td>0.990</td></tr><tr><td>30</td><td>0.984</td><td>0.986</td><td>0.990</td><td>0.988</td><td>0.986</td><td>0.989</td><td>0.991</td><td>0.991</td></tr><tr><td>40</td><td>0.984</td><td>0.986</td><td>0.990</td><td>0.988</td><td>0.988</td><td>0.989</td><td>0.991</td><td>0.991</td></tr><tr><td>50</td><td>0.986</td><td>0.988</td><td>0.990</td><td>0.988</td><td>0.990</td><td>0.991</td><td>0.991</td><td>0.991</td></tr><tr><td rowspan="5">R</td><td rowspan="5">n</td><td>10</td><td>1.001</td><td>1.000</td><td>1.000</td><td>1.000</td><td>1.001</td><td>1.001</td><td>1.000</td><td>1.000</td></tr><tr><td>20</td><td>1.001</td><td>1.001</td><td>1.000</td><td>1.000</td><td>1.002</td><td>1.002</td><td>1.000</td><td>1.000</td></tr><tr><td>30</td><td>1.002</td><td>1.002</td><td>1.000</td><td>1.000</td><td>1.003</td><td>1.004</td><td>1.000</td><td>1.000</td></tr><tr><td>40</td><td>1.002</td><td>1.002</td><td>1.000</td><td>1.000</td><td>1.004</td><td>1.004</td><td>1.000</td><td>1.000</td></tr><tr><td>50</td><td>1.002</td><td>1.002</td><td>1.000</td><td>1.000</td><td>1.004</td><td>1.004</td><td>1.000</td><td>1.000</td></tr><tr><td rowspan="5">appGap</td><td rowspan="5">n</td><td>10</td><td>0.010</td><td>0.102</td><td>0.010</td><td>0.010</td><td>0.010</td><td>0.010</td><td>0.010</td><td>0.009</td></tr><tr><td>20</td><td>6.557</td><td>7.321</td><td>0.010</td><td>0.015</td><td>4.542</td><td>5.030</td><td>0.010</td><td>0.017</td></tr><tr><td>30</td><td>9.835</td><td>10.639</td><td>0.935</td><td>0.900</td><td>7.199</td><td>7.777</td><td>0.873</td><td>0.871</td></tr><tr><td>40</td><td>11.450</td><td>11.881</td><td>1.459</td><td>1.453</td><td>10.177</td><td>10.266</td><td>1.479</td><td>1.494</td></tr><tr><td>50</td><td>12.237</td><td>12.462</td><td>1.708</td><td>1.776</td><td>11.196</td><td>11.258</td><td>1.806</td><td>1.821</td></tr><tr><td rowspan="5">realGap</td><td rowspan="5">n</td><td>10</td><td>1.775</td><td>1.732</td><td>0.995</td><td>1.225</td><td>1.499</td><td>1.421</td><td>0.882</td><td>0.953</td></tr><tr><td>20</td><td>8.293</td><td>8.895</td><td>1.029</td><td>1.249</td><td>6.154</td><td>6.500</td><td>0.891</td><td>0.973</td></tr><tr><td>30</td><td>11.415</td><td>12.029</td><td>1.921</td><td>2.108</td><td>8.792</td><td>9.181</td><td>1.730</td><td>1.808</td></tr><tr><td>40</td><td>12.979</td><td>13.240</td><td>2.449</td><td>2.655</td><td>11.592</td><td>11.543</td><td>2.345</td><td>2.429</td></tr><tr><td>50</td><td>13.662</td><td>13.733</td><td>2.699</td><td>2.979</td><td>12.433</td><td>12.433</td><td>2.670</td><td>2.751</td></tr></tbody></table>
<table><caption>Table 8: Performances Vs. d. “*” = 3h time out</caption><thead><tr><th colspan="2">risk measure</th><th colspan="4">EX</th><th colspan="4">EN</th></tr><tr><th colspan="2">model</th><th colspan="2">CELL</th><th colspan="2">MINR</th><th colspan="2">CELL</th><th colspan="2">MINR</th></tr><tr><th colspan="2">grid</th><th>U</th><th>S</th><th>U</th><th>S</th><th>U</th><th>S</th><th>U</th><th>S</th></tr></thead><tbody><tr><th rowspan="5">time</th><th rowspan="5">d</th><th>0.1</th><td>783</td><td>2122</td><td>2</td><td>8</td><td>332</td><td>705</td><td>3</td><td>8</td></tr><tr><th>0.2</th><td>*</td><td>*</td><td>183</td><td>785</td><td>8591</td><td>10361</td><td>287</td><td>1603</td></tr><tr><th>0.3</th><td>*</td><td>*</td><td>3837</td><td>4387</td><td>*</td><td>*</td><td>5640</td><td>5479</td></tr><tr><th>0.4</th><td>*</td><td>*</td><td>*</td><td>*</td><td>*</td><td>*</td><td>10161</td><td>10334</td></tr><tr><th>0.5</th><td>*</td><td>*</td><td>*</td><td>*</td><td>*</td><td>*</td><td>*</td><td>*</td></tr><tr><th rowspan="5">L</th><th rowspan="5">d</th><th>0.1</th><td>0.984</td><td>0.986</td><td>0.986</td><td>0.989</td><td>0.988</td><td>0.989</td><td>0.990</td><td>0.992</td></tr><tr><th>0.2</th><td>0.952</td><td>0.946</td><td>0.988</td><td>0.994</td><td>0.971</td><td>0.967</td><td>0.992</td><td>0.995</td></tr><tr><th>0.3</th><td>0.918</td><td>0.912</td><td>0.990</td><td>0.988</td><td>0.940</td><td>0.937</td><td>0.991</td><td>0.990</td></tr><tr><th>0.4</th><td>0.889</td><td>0.887</td><td>0.982</td><td>0.984</td><td>0.906</td><td>0.911</td><td>0.986</td><td>0.988</td></tr><tr><th>0.5</th><td>0.885</td><td>0.884</td><td>0.984</td><td>0.984</td><td>0.893</td><td>0.886</td><td>0.981</td><td>0.985</td></tr><tr><th rowspan="5">U</th><th rowspan="5">d</th><th>0.1</th><td>0.984</td><td>0.986</td><td>0.986</td><td>0.989</td><td>0.989</td><td>0.990</td><td>0.990</td><td>0.992</td></tr><tr><th>0.2</th><td>0.982</td><td>0.984</td><td>0.988</td><td>0.994</td><td>0.986</td><td>0.987</td><td>0.992</td><td>0.995</td></tr><tr><th>0.3</th><td>0.983</td><td>0.984</td><td>0.990</td><td>0.988</td><td>0.985</td><td>0.987</td><td>0.991</td><td>0.990</td></tr><tr><th>0.4</th><td>0.986</td><td>0.986</td><td>0.985</td><td>0.988</td><td>0.987</td><td>0.988</td><td>0.989</td><td>0.991</td></tr><tr><th>0.5</th><td>0.990</td><td>0.990</td><td>0.993</td><td>0.990</td><td>0.990</td><td>0.990</td><td>0.994</td><td>0.992</td></tr><tr><th rowspan="5">R</th><th rowspan="5">d</th><th>0.1</th><td>1.001</td><td>1.001</td><td>1.000</td><td>1.000</td><td>1.001</td><td>1.001</td><td>1.000</td><td>1.000</td></tr><tr><th>0.2</th><td>1.001</td><td>1.001</td><td>1.000</td><td>1.000</td><td>1.002</td><td>1.001</td><td>1.000</td><td>1.000</td></tr><tr><th>0.3</th><td>1.001</td><td>1.001</td><td>1.000</td><td>1.000</td><td>1.002</td><td>1.002</td><td>1.000</td><td>1.000</td></tr><tr><th>0.4</th><td>1.001</td><td>1.001</td><td>1.000</td><td>1.000</td><td>1.002</td><td>1.002</td><td>1.000</td><td>1.000</td></tr><tr><th>0.5</th><td>1.001</td><td>1.001</td><td>1.000</td><td>1.000</td><td>1.002</td><td>1.002</td><td>1.000</td><td>1.000</td></tr><tr><th rowspan="5">appGap</th><th rowspan="5">d</th><th>0.1</th><td>0.010</td><td>0.010</td><td>0.010</td><td>0.010</td><td>0.010</td><td>0.010</td><td>0.010</td><td>0.010</td></tr><tr><th>0.2</th><td>3.075</td><td>3.836</td><td>0.010</td><td>0.010</td><td>1.544</td><td>2.086</td><td>0.010</td><td>0.010</td></tr><tr><th>0.3</th><td>6.557</td><td>7.321</td><td>0.010</td><td>0.015</td><td>4.542</td><td>5.030</td><td>0.010</td><td>0.017</td></tr><tr><th>0.4</th><td>9.776</td><td>10.108</td><td>0.274</td><td>0.402</td><td>8.168</td><td>7.745</td><td>0.301</td><td>0.368</td></tr><tr><th>0.5</th><td>10.635</td><td>10.651</td><td>0.923</td><td>0.616</td><td>9.787</td><td>10.544</td><td>1.320</td><td>0.694</td></tr><tr><th rowspan="5">realGap</th><th rowspan="5">d</th><th>0.1</th><td>1.667</td><td>1.501</td><td>1.413</td><td>1.093</td><td>1.252</td><td>1.152</td><td>1.007</td><td>0.799</td></tr><tr><th>0.2</th><td>4.902</td><td>5.474</td><td>1.170</td><td>0.648</td><td>3.095</td><td>3.461</td><td>0.784</td><td>0.509</td></tr><tr><th>0.3</th><td>8.293</td><td>8.895</td><td>1.029</td><td>1.249</td><td>6.154</td><td>6.500</td><td>0.891</td><td>0.973</td></tr><tr><th>0.4</th><td>11.175</td><td>11.423</td><td>1.784</td><td>1.565</td><td>9.544</td><td>9.037</td><td>1.404</td><td>1.239</td></tr><tr><th>0.5</th><td>11.566</td><td>11.651</td><td>1.642</td><td>1.575</td><td>10.836</td><td>11.576</td><td>1.961</td><td>1.519</td></tr></tbody></table>
<table><caption>Table 9: Performances Vs. *p.* "*" = 3h time out</caption><thead><tr><th rowspan="3">risk measure</th><th colspan="8">EX</th><th colspan="2">EN</th></tr><tr><th rowspan="2">model</th><th colspan="2">CELL</th><th colspan="2">MINR</th><th colspan="2">CELL</th><th colspan="2">MINR</th></tr><tr><th>U</th><th>S</th><th>U</th><th>S</th><th>U</th><th>S</th><th>U</th><th>S</th></tr></thead><tbody><tr><th colspan="9">grid</th></tr><tr><th rowspan="5">time</th><th rowspan="5">p</th><th>5</th><th>*</th><th>*</th><th>1248</th><th>2132</th><th>*</th><th>*</th><th>1922</th><th>2560</th></tr><tr><th>7</th><th>*</th><th>*</th><th>3837</th><th>4387</th><th>*</th><th>*</th><th>5640</th><th>5479</th></tr><tr><th>10</th><th>*</th><th>*</th><th>10409</th><th>8866</th><th>*</th><th>*</th><th>*</th><th>9907</th></tr><tr><th>12</th><th>*</th><th>*</th><th>*</th><th>*</th><th>*</th><th>*</th><th>*</th><th>10437</th></tr><tr><th>15</th><th>*</th><th>*</th><th>*</th><th>*</th><th>*</th><th>*</th><th>*</th><th>*</th></tr><tr><th rowspan="5">L</th><th rowspan="5">p</th><th>5</th><th>0.923</th><th>0.919</th><th>0.990</th><th>0.988</th><th>0.947</th><th>0.945</th><th>0.991</th><th>0.990</th></tr><tr><th>7</th><th>0.918</th><th>0.912</th><th>0.990</th><th>0.988</th><th>0.940</th><th>0.937</th><th>0.991</th><th>0.990</th></tr><tr><th>10</th><th>0.908</th><th>0.904</th><th>0.988</th><th>0.987</th><th>0.930</th><th>0.925</th><th>0.988</th><th>0.989</th></tr><tr><th>12</th><th>0.901</th><th>0.900</th><th>0.981</th><th>0.986</th><th>0.915</th><th>0.915</th><th>0.983</th><th>0.987</th></tr><tr><th>15</th><th>0.886</th><th>0.884</th><th>0.972</th><th>0.983</th><th>0.903</th><th>0.902</th><th>0.975</th><th>0.983</th></tr><tr><th rowspan="5">U</th><th rowspan="5">p</th><th>5</th><th>0.983</th><th>0.985</th><th>0.990</th><th>0.988</th><th>0.987</th><th>0.988</th><th>0.991</th><th>0.990</th></tr><tr><th>7</th><th>0.983</th><th>0.984</th><th>0.990</th><th>0.988</th><th>0.985</th><th>0.987</th><th>0.991</th><th>0.990</th></tr><tr><th>10</th><th>0.983</th><th>0.983</th><th>0.990</th><th>0.988</th><th>0.984</th><th>0.986</th><th>0.991</th><th>0.990</th></tr><tr><th>12</th><th>0.983</th><th>0.984</th><th>0.990</th><th>0.988</th><th>0.985</th><th>0.986</th><th>0.991</th><th>0.990</th></tr><tr><th>15</th><th>0.984</th><th>0.985</th><th>0.990</th><th>0.988</th><th>0.985</th><th>0.986</th><th>0.991</th><th>0.990</th></tr><tr><th rowspan="5">R</th><th rowspan="5">p</th><th>5</th><th>1.002</th><th>1.002</th><th>1.000</th><th>1.000</th><th>1.002</th><th>1.002</th><th>1.000</th><th>1.000</th></tr><tr><th>7</th><th>1.001</th><th>1.001</th><th>1.000</th><th>1.000</th><th>1.002</th><th>1.002</th><th>1.000</th><th>1.000</th></tr><tr><th>10</th><th>1.001</th><th>1.001</th><th>1.000</th><th>1.000</th><th>1.002</th><th>1.002</th><th>1.000</th><th>1.000</th></tr><tr><th>12</th><th>1.001</th><th>1.001</th><th>1.000</th><th>1.000</th><th>1.002</th><th>1.002</th><th>1.000</th><th>1.000</th></tr><tr><th>15</th><th>1.000</th><th>1.001</th><th>1.000</th><th>1.000</th><th>1.001</th><th>1.001</th><th>1.000</th><th>1.000</th></tr><tr><th rowspan="5">appGap</th><th rowspan="5">p</th><th>5</th><th>6.095</th><th>6.613</th><th>0.010</th><th>0.010</th><th>4.010</th><th>4.364</th><th>0.010</th><th>0.010</th></tr><tr><th>7</th><th>6.557</th><th>7.321</th><th>0.010</th><th>0.015</th><th>4.542</th><th>5.030</th><th>0.010</th><th>0.017</th></tr><tr><th>10</th><th>7.623</th><th>8.021</th><th>0.195</th><th>0.029</th><th>5.482</th><th>6.198</th><th>0.282</th><th>0.089</th></tr><tr><th>12</th><th>8.396</th><th>8.558</th><th>0.901</th><th>0.154</th><th>7.112</th><th>7.181</th><th>0.853</th><th>0.269</th></tr><tr><th>15</th><th>9.955</th><th>10.317</th><th>1.865</th><th>0.460</th><th>8.355</th><th>8.527</th><th>1.581</th><th>0.749</th></tr><tr><th rowspan="5">realGap</th><th rowspan="5">p</th><th>5</th><th>7.822</th><th>8.216</th><th>1.030</th><th>1.236</th><th>5.474</th><th>5.670</th><th>0.903</th><th>0.965</th></tr><tr><th>7</th><th>8.293</th><th>8.895</th><th>1.029</th><th>1.249</th><th>6.154</th><th>6.500</th><th>0.891</th><th>0.973</th></tr><tr><th>10</th><th>9.334</th><th>9.636</th><th>1.202</th><th>1.258</th><th>7.141</th><th>7.710</th><th>1.171</th><th>1.069</th></tr><tr><th>12</th><th>9.992</th><th>10.081</th><th>1.870</th><th>1.382</th><th>8.619</th><th>8.615</th><th>1.750</th><th>1.252</th></tr><tr><th>15</th><th>11.478</th><th>11.698</th><th>2.817</th><th>1.685</th><th>9.846</th><th>9.937</th><th>2.463</th><th>1.729</th></tr></tbody></table>
<table><caption>Table 10: Performances Vs. K. "*" = 3h time out</caption><thead><tr><th colspan="2">risk measure</th><th colspan="4">EX</th><th colspan="4">EN</th></tr><tr><th colspan="2">model</th><th colspan="2">CELL</th><th colspan="2">MINR</th><th colspan="2">CELL</th><th colspan="2">MINR</th></tr><tr><th colspan="2">grid</th><th>U</th><th>S</th><th>U</th><th>S</th><th>U</th><th>S</th><th>U</th><th>S</th></tr></thead><tbody><tr><th rowspan="5">time</th><th rowspan="5">K</th><th>2</th><td>909</td><td>3360</td><td>2</td><td>8</td><td>626</td><td>1864</td><td>3</td><td>8</td></tr><tr><th>4</th><td>*</td><td>*</td><td>3837</td><td>4387</td><td>*</td><td>*</td><td>5640</td><td>5479</td></tr><tr><th>8</th><td>*</td><td>*</td><td>*</td><td>*</td><td>*</td><td>*</td><td>*</td><td>*</td></tr><tr><th>16</th><td>8035</td><td>8131</td><td>*</td><td>*</td><td>9505</td><td>8439</td><td>*</td><td>*</td></tr><tr><th>32</th><td>10641</td><td>10763</td><td>*</td><td>*</td><td>*</td><td>10670</td><td>*</td><td>10761</td></tr><tr><th rowspan="5">L</th><th rowspan="5">K</th><th>2</th><td>0.914</td><td>0.920</td><td>0.942</td><td>0.954</td><td>0.920</td><td>0.925</td><td>0.958</td><td>0.965</td></tr><tr><th>4</th><td>0.918</td><td>0.912</td><td>0.990</td><td>0.988</td><td>0.940</td><td>0.937</td><td>0.991</td><td>0.990</td></tr><tr><th>8</th><td>0.871</td><td>0.869</td><td>0.991</td><td>0.992</td><td>0.888</td><td>0.887</td><td>0.992</td><td>0.993</td></tr><tr><th>16</th><td>0.862</td><td>0.861</td><td>0.988</td><td>0.991</td><td>0.874</td><td>0.874</td><td>0.990</td><td>0.991</td></tr><tr><th>32</th><td>0.842</td><td>0.855</td><td>0.988</td><td>0.990</td><td>0.857</td><td>0.839</td><td>0.989</td><td>0.990</td></tr><tr><th rowspan="5">U</th><th rowspan="5">K</th><th>2</th><td>0.914</td><td>0.920</td><td>0.942</td><td>0.955</td><td>0.920</td><td>0.925</td><td>0.958</td><td>0.966</td></tr><tr><th>4</th><td>0.983</td><td>0.984</td><td>0.990</td><td>0.988</td><td>0.985</td><td>0.987</td><td>0.991</td><td>0.990</td></tr><tr><th>8</th><td>0.998</td><td>0.998</td><td>0.997</td><td>0.997</td><td>0.999</td><td>1.000</td><td>0.997</td><td>0.998</td></tr><tr><th>16</th><td>1.000</td><td>1.001</td><td>0.999</td><td>0.999</td><td>1.002</td><td>1.002</td><td>0.999</td><td>0.999</td></tr><tr><th>32</th><td>1.002</td><td>1.001</td><td>1.000</td><td>1.000</td><td>1.004</td><td>1.004</td><td>1.000</td><td>1.000</td></tr><tr><th rowspan="5">R</th><th rowspan="5">K</th><th>2</th><td>1.002</td><td>1.002</td><td>1.001</td><td>1.001</td><td>1.005</td><td>1.004</td><td>1.001</td><td>1.001</td></tr><tr><th>4</th><td>1.001</td><td>1.001</td><td>1.000</td><td>1.000</td><td>1.002</td><td>1.002</td><td>1.000</td><td>1.000</td></tr><tr><th>8</th><td>1.001</td><td>1.001</td><td>1.000</td><td>1.000</td><td>1.002</td><td>1.002</td><td>1.000</td><td>1.000</td></tr><tr><th>16</th><td>1.001</td><td>1.001</td><td>1.000</td><td>1.000</td><td>1.002</td><td>1.003</td><td>1.000</td><td>1.000</td></tr><tr><th>32</th><td>1.002</td><td>1.002</td><td>1.000</td><td>1.000</td><td>1.004</td><td>1.004</td><td>1.000</td><td>1.000</td></tr><tr><th rowspan="5">appGap</th><th rowspan="5">K</th><th>2</th><td>0.010</td><td>0.010</td><td>0.009</td><td>0.010</td><td>0.009</td><td>0.009</td><td>0.009</td><td>0.010</td></tr><tr><th>4</th><td>6.557</td><td>7.321</td><td>0.010</td><td>0.015</td><td>4.542</td><td>5.030</td><td>0.010</td><td>0.017</td></tr><tr><th>8</th><td>12.726</td><td>12.879</td><td>0.587</td><td>0.457</td><td>11.043</td><td>11.220</td><td>0.563</td><td>0.514</td></tr><tr><th>16</th><td>13.816</td><td>13.938</td><td>1.055</td><td>0.846</td><td>12.724</td><td>12.832</td><td>0.891</td><td>0.817</td></tr><tr><th>32</th><td>15.902</td><td>14.593</td><td>1.204</td><td>0.968</td><td>14.684</td><td>16.495</td><td>1.048</td><td>0.942</td></tr><tr><th rowspan="5">realGap</th><th rowspan="5">K</th><th>2</th><td>8.786</td><td>8.166</td><td>5.866</td><td>4.634</td><td>8.445</td><td>7.924</td><td>4.287</td><td>3.542</td></tr><tr><th>4</th><td>8.293</td><td>8.895</td><td>1.029</td><td>1.249</td><td>6.154</td><td>6.500</td><td>0.891</td><td>0.973</td></tr><tr><th>8</th><td>13.004</td><td>13.157</td><td>0.914</td><td>0.740</td><td>11.332</td><td>11.459</td><td>0.807</td><td>0.716</td></tr><tr><th>16</th><td>13.872</td><td>13.987</td><td>1.128</td><td>0.905</td><td>12.771</td><td>12.876</td><td>0.934</td><td>0.853</td></tr><tr><th>32</th><td>15.914</td><td>14.602</td><td>1.215</td><td>0.975</td><td>14.682</td><td>16.495</td><td>1.048</td><td>0.944</td></tr></tbody></table>
<table><caption>Table 11: Performances Vs. λ. "*" = 3h time out</caption><thead><tr><th colspan="2">risk measure</th><th colspan="4">EX</th><th colspan="4">EN</th></tr><tr><th colspan="2">model</th><th colspan="2">CELL</th><th colspan="2">MINR</th><th colspan="2">CELL</th><th colspan="2">MINR</th></tr><tr><th colspan="2">grid</th><th>U</th><th>S</th><th>U</th><th>S</th><th>U</th><th>S</th><th>U</th><th>S</th></tr></thead><tbody><tr><td rowspan="5">time</td><td rowspan="5">λ</td><td>0.2</td><td>7743</td><td>8484</td><td>64</td><td>38</td><td>8567</td><td>8334</td><td>22</td><td>29</td></tr><tr><td>0.7</td><td>*</td><td>*</td><td>3837</td><td>4387</td><td>*</td><td>*</td><td>5640</td><td>5479</td></tr><tr><td>1.2</td><td>*</td><td>*</td><td>*</td><td>*</td><td>*</td><td>*</td><td>*</td><td>*</td></tr><tr><td>1.7</td><td>*</td><td>*</td><td>*</td><td>*</td><td>*</td><td>*</td><td>*</td><td>*</td></tr><tr><td>2.2</td><td>*</td><td>*</td><td>*</td><td>*</td><td>*</td><td>*</td><td>*</td><td>*</td></tr><tr><td rowspan="5">L</td><td rowspan="5">λ</td><td>0.2</td><td>0.995</td><td>0.995</td><td>0.998</td><td>0.997</td><td>0.997</td><td>0.997</td><td>0.998</td><td>0.998</td></tr><tr><td>0.7</td><td>0.918</td><td>0.912</td><td>0.990</td><td>0.988</td><td>0.940</td><td>0.937</td><td>0.991</td><td>0.990</td></tr><tr><td>1.2</td><td>0.793</td><td>0.793</td><td>0.963</td><td>0.963</td><td>0.816</td><td>0.815</td><td>0.963</td><td>0.966</td></tr><tr><td>1.7</td><td>0.628</td><td>0.626</td><td>0.916</td><td>0.924</td><td>0.643</td><td>0.644</td><td>0.914</td><td>0.926</td></tr><tr><td>2.2</td><td>0.518</td><td>0.514</td><td>0.856</td><td>0.874</td><td>0.530</td><td>0.527</td><td>0.857</td><td>0.876</td></tr><tr><td rowspan="5">U</td><td rowspan="5">λ</td><td>0.2</td><td>1.000</td><td>1.000</td><td>0.998</td><td>0.997</td><td>1.000</td><td>1.000</td><td>0.998</td><td>0.998</td></tr><tr><td>0.7</td><td>0.983</td><td>0.984</td><td>0.990</td><td>0.988</td><td>0.985</td><td>0.987</td><td>0.991</td><td>0.990</td></tr><tr><td>1.2</td><td>0.967</td><td>0.972</td><td>0.973</td><td>0.972</td><td>0.967</td><td>0.972</td><td>0.976</td><td>0.976</td></tr><tr><td>1.7</td><td>0.838</td><td>0.866</td><td>0.948</td><td>0.953</td><td>0.845</td><td>0.874</td><td>0.953</td><td>0.958</td></tr><tr><td>2.2</td><td>0.694</td><td>0.752</td><td>0.915</td><td>0.934</td><td>0.699</td><td>0.763</td><td>0.921</td><td>0.938</td></tr><tr><td rowspan="5">R</td><td rowspan="5">λ</td><td>0.2</td><td>1.000</td><td>1.000</td><td>1.000</td><td>1.000</td><td>1.000</td><td>1.000</td><td>1.000</td><td>1.000</td></tr><tr><td>0.7</td><td>1.001</td><td>1.001</td><td>1.000</td><td>1.000</td><td>1.002</td><td>1.002</td><td>1.000</td><td>1.000</td></tr><tr><td>1.2</td><td>1.001</td><td>1.001</td><td>1.000</td><td>1.000</td><td>1.002</td><td>1.002</td><td>1.000</td><td>1.000</td></tr><tr><td>1.7</td><td>1.001</td><td>1.001</td><td>1.000</td><td>1.000</td><td>1.004</td><td>1.005</td><td>1.001</td><td>1.000</td></tr><tr><td>2.2</td><td>1.001</td><td>1.001</td><td>1.000</td><td>1.001</td><td>1.006</td><td>1.005</td><td>1.001</td><td>1.000</td></tr><tr><td rowspan="5">appGap</td><td rowspan="5">λ</td><td>0.2</td><td>0.471</td><td>0.460</td><td>0.010</td><td>0.010</td><td>0.264</td><td>0.268</td><td>0.010</td><td>0.010</td></tr><tr><td>0.7</td><td>6.557</td><td>7.321</td><td>0.010</td><td>0.015</td><td>4.542</td><td>5.030</td><td>0.010</td><td>0.017</td></tr><tr><td>1.2</td><td>17.947</td><td>18.375</td><td>0.999</td><td>0.936</td><td>15.668</td><td>16.091</td><td>1.374</td><td>1.022</td></tr><tr><td>1.7</td><td>25.097</td><td>27.701</td><td>3.352</td><td>3.050</td><td>23.983</td><td>26.329</td><td>4.067</td><td>3.326</td></tr><tr><td>2.2</td><td>25.278</td><td>31.597</td><td>6.418</td><td>6.424</td><td>24.221</td><td>31.014</td><td>6.881</td><td>6.599</td></tr><tr><td rowspan="5">realGap</td><td rowspan="5">λ</td><td>0.2</td><td>0.521</td><td>0.509</td><td>0.212</td><td>0.289</td><td>0.300</td><td>0.302</td><td>0.170</td><td>0.181</td></tr><tr><td>0.7</td><td>8.293</td><td>8.895</td><td>1.029</td><td>1.249</td><td>6.154</td><td>6.500</td><td>0.891</td><td>0.973</td></tr><tr><td>1.2</td><td>20.762</td><td>20.790</td><td>3.686</td><td>3.753</td><td>18.609</td><td>18.631</td><td>3.773</td><td>3.387</td></tr><tr><td>1.7</td><td>37.306</td><td>37.440</td><td>8.423</td><td>7.667</td><td>36.022</td><td>35.908</td><td>8.679</td><td>7.408</td></tr><tr><td>2.2</td><td>48.272</td><td>48.624</td><td>14.400</td><td>12.667</td><td>47.343</td><td>47.604</td><td>14.365</td><td>12.443</td></tr></tbody></table>
<table><caption>Table 12: Performances Vs. α. “*” = 3h time out</caption><thead><tr><th colspan="2">model</th><th colspan="2">CELL</th><th colspan="2">MINR</th></tr><tr><th colspan="2">grid</th><th>U</th><th>S</th><th>U</th><th>S</th></tr></thead><tbody><tr><td rowspan="5">time</td><td rowspan="5">α</td><td>0.1</td><td>*</td><td>*</td><td>3968</td><td>2022</td></tr><tr><td>0.3</td><td>*</td><td>*</td><td>3905</td><td>3552</td></tr><tr><td>0.5</td><td>*</td><td>*</td><td>5640</td><td>5479</td></tr><tr><td>0.7</td><td>*</td><td>*</td><td>6829</td><td>7808</td></tr><tr><td>0.9</td><td>*</td><td>*</td><td>7672</td><td>9496</td></tr><tr><td rowspan="5">L</td><td rowspan="5">α</td><td>0.1</td><td>0.952</td><td>0.946</td><td>0.994</td><td>0.994</td></tr><tr><td>0.3</td><td>0.943</td><td>0.943</td><td>0.992</td><td>0.991</td></tr><tr><td>0.5</td><td>0.940</td><td>0.937</td><td>0.991</td><td>0.990</td></tr><tr><td>0.7</td><td>0.935</td><td>0.935</td><td>0.991</td><td>0.990</td></tr><tr><td>0.9</td><td>0.934</td><td>0.931</td><td>0.990</td><td>0.989</td></tr><tr><td rowspan="5">U</td><td rowspan="5">α</td><td>0.1</td><td>0.991</td><td>0.992</td><td>0.995</td><td>0.994</td></tr><tr><td>0.3</td><td>0.988</td><td>0.989</td><td>0.992</td><td>0.992</td></tr><tr><td>0.5</td><td>0.985</td><td>0.987</td><td>0.991</td><td>0.990</td></tr><tr><td>0.7</td><td>0.985</td><td>0.986</td><td>0.991</td><td>0.990</td></tr><tr><td>0.9</td><td>0.984</td><td>0.986</td><td>0.991</td><td>0.990</td></tr><tr><td rowspan="5">R</td><td rowspan="5">α</td><td>0.1</td><td>1.003</td><td>1.003</td><td>1.000</td><td>1.000</td></tr><tr><td>0.3</td><td>1.002</td><td>1.003</td><td>1.000</td><td>1.000</td></tr><tr><td>0.5</td><td>1.002</td><td>1.002</td><td>1.000</td><td>1.000</td></tr><tr><td>0.7</td><td>1.002</td><td>1.002</td><td>1.000</td><td>1.000</td></tr><tr><td>0.9</td><td>1.002</td><td>1.002</td><td>1.000</td><td>1.000</td></tr><tr><td rowspan="5">appGap</td><td rowspan="5">α</td><td>0.1</td><td>3.914</td><td>4.641</td><td>0.034</td><td>0.010</td></tr><tr><td>0.3</td><td>4.574</td><td>4.657</td><td>0.010</td><td>0.010</td></tr><tr><td>0.5</td><td>4.542</td><td>5.030</td><td>0.010</td><td>0.017</td></tr><tr><td>0.7</td><td>5.056</td><td>5.242</td><td>0.043</td><td>0.049</td></tr><tr><td>0.9</td><td>5.145</td><td>5.568</td><td>0.051</td><td>0.084</td></tr><tr><td rowspan="5">realGap</td><td rowspan="5">α</td><td>0.1</td><td>5.022</td><td>5.678</td><td>0.596</td><td>0.600</td></tr><tr><td>0.3</td><td>5.939</td><td>5.938</td><td>0.809</td><td>0.859</td></tr><tr><td>0.5</td><td>6.154</td><td>6.500</td><td>0.891</td><td>0.973</td></tr><tr><td>0.7</td><td>6.656</td><td>6.702</td><td>0.950</td><td>1.033</td></tr><tr><td>0.9</td><td>6.792</td><td>7.029</td><td>0.967</td><td>1.067</td></tr></tbody></table>