# Robust optimization with belief functions

Marc Goerigk, Romain Guillaume, Adam Kasperski, Pawel Zieliński

► To cite this version:

Marc Goerigk, Romain Guillaume, Adam Kasperski, Pawel Zieliński. Robust optimization with belief functions. International Journal of Approximate Reasoning, 2023, 159, pp.108941. 10.1016/j.ijar.2023.108941. hal-04940888

HAL Id: hal-04940888

https://hal.science/hal-04940888v1

Submitted on 29 Apr 2025

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_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
<figure><img src="image_2.png" /></figure>

# Robust optimization with belief functions

Marc Goerigk<sup>a</sup>, Romain Guillaume<sup>b</sup>, Adam Kasperski<sup>c, *,</sup>, Paweł Zieliński<sup>c</sup>

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

Check for
updates

## ARTICLE INFO

**Article history:**

Received 2 March 2023

Received in revised form 22 April 2023

Accepted 9 May 2023

Available online 12 May 2023

**Keywords:**

Robust optimization

Hurwicz criterion

Belief function

Possibility theory

## ABSTRACT

In this paper, an optimization problem with uncertain objective function coefficients is considered. The uncertainty is specified by providing a discrete scenario set containing possible realizations of the objective function coefficients. The concept of belief function in the traditional and possibilistic setting is applied to define a set of admissible probability distributions over the scenario set. The generalized Hurwicz criterion is then used to compute a solution. In this paper, the complexity of the resulting problem is explored. Some exact and approximation methods of solving it are proposed.

© 2023 The Author(s). Published by Elsevier Inc. This is an open access article under the CC BY license (http://creativecommons.org/licenses/by/4.0/).

## 1. Introduction

In this paper, we wish to investigate a version of the following generic optimization problem under uncertainty in the objective function coefficients:

$$ \min_{\mathbf{x} \in \mathcal{X}} f(\mathbf{x}, \mathcal{C}) \qquad (1) $$

where $\mathcal{C} \in \mathbb{R}^l$ is a vector of the objective function coefficients and $\mathcal{X} \subseteq \mathbb{R}^n$ is a set of feasible solutions. We will assume that $\mathcal{X}$ is not empty, $f$ takes only nonnegative values, $f: \mathcal{X} \times \mathbb{R}^l \to \mathbb{R}_+$, and attains a minimum in $\mathcal{X}$ for each fixed vector of coefficients $\mathcal{C}$. If $\mathcal{X}$ is a polytope, described by a system of linear constraints, and $f$ is linear, then we get the class of linear programming problems. In a more general case, if $\mathcal{X}$ is a convex set and $f$ is a convex function, then we get the class of convex optimization problems (see, e.g., [3]). If $\mathcal{X} \subseteq \{0, 1\}^n$, then (1) is a combinatorial problem. Depending on the structure of $\mathcal{X}$ and the definition of the cost function $f$, the problem (1) can be solved in polynomial time or becomes NP-hard.

In many practical applications, the vector of the objective function coefficients $\mathcal{C}$ is uncertain. Namely, $\tilde{\mathcal{C}} = (\tilde{c}_1, \dots, \tilde{c}_l)$ is then a random vector in $\mathbb{R}^l$, whose probability distribution is known, partially known or completely unknown. Accordingly, the cost $f(\mathbf{x}, \tilde{\mathcal{C}})$ of a given solution $\mathbf{x} \in \mathcal{X}$ is a random variable in $\mathbb{R}_+$. Let $\mathcal{U}$ be a set of scenarios containing possible realizations of $\tilde{\mathcal{C}}$ called scenarios. In this paper, we will assume that $\mathcal{U} = \{\mathcal{C}_1, \dots, \mathcal{C}_K\} \subseteq \mathbb{R}^l$ contains a finite number of $K \ge 1$, explicitly listed, scenarios. Scenarios in $\mathcal{U}$ may correspond to possible states of the world or can be a result of sampling of the random vector $\tilde{\mathcal{C}}$. We will use $\mathcal{P}(\mathcal{U})$ to denote the set of all discrete probability distributions in $\mathcal{U}$, that is,

<footnote><sup>a</sup> Business Decisions and Data Science, University of Passau, Passau, Germany</footnote>

<footnote><sup>b</sup> Université de Toulouse-IRIT Toulouse, France</footnote>

<footnote><sup>c</sup> Wrocław University of Science and Technology, Wrocław, Poland</footnote>

<footnote>* Corresponding author.</footnote>

<footnote>E-mail addresses: marc.goerigk@uni-passau.de (M. Goerigk), romain.guillaume@irit.fr (R. Guillaume), adam.kasperski@pwr.edu.pl (A. Kasperski), pawel.zielinski@pwr.edu.pl (P. Zieliński).</footnote>
$\mathcal{P}(\mathcal{U}) = \{\mathbf{p} \in [0, 1]^K : \sum_{k \in [K]} p_k = 1\}$, where $[K]$ is the shortcut for the set $\{1, \dots, K\}$. If some additional knowledge in $\mathcal{P}(\mathcal{U})$ is available, then one can use it to provide a set of admissible probability distributions $\mathcal{P} \subseteq \mathcal{P}(\mathcal{U})$, which is a restriction of $\mathcal{P}(\mathcal{U})$. For example, one can add some bounds $p_k \le p_k \le \bar{p}_k$, $k \in [K]$, on the probabilities [19], or some bounds on the mean or covariance matrix for $\tilde{\mathbf{c}}$, which leads to various descriptions of $\mathcal{P}$ (see, e.g., [5,23]). Fix $\alpha \in [0, 1]$ and define

$$H_{\alpha}(\mathbf{x}) = \alpha \bar{E}[f(\mathbf{x}, \tilde{\mathbf{c}})] + (1 - \alpha) \underline{E}[f(\mathbf{x}, \tilde{\mathbf{c}})],$$

where

$$\bar{E}[f(\mathbf{x}, \tilde{\mathbf{c}})] = \sup_{\mathbf{p} \in \mathcal{P}} \mathbb{E}_{\mathbf{p}}[f(\mathbf{x}, \tilde{\mathbf{c}})] = \sup_{\mathbf{p} \in \mathcal{P}} \sum_{k \in [K]} p_k f(\mathbf{x}, \mathbf{c}_k),$$

$$\underline{E}[f(\mathbf{x}, \tilde{\mathbf{c}})] = \inf_{\mathbf{p} \in \mathcal{P}} \mathbb{E}_{\mathbf{p}}[f(\mathbf{x}, \tilde{\mathbf{c}})] = \inf_{\mathbf{p} \in \mathcal{P}} \sum_{k \in [K]} p_k f(\mathbf{x}, \mathbf{c}_k),$$

and $\mathbb{E}_{\mathbf{p}}[\cdot]$ is the expected value with respect to the probability distribution $\mathbf{p}$. The quantity $H_{\alpha}$ is called a generalized Hurwicz criterion, and $\bar{E}[\cdot]$, $\underline{E}[\cdot]$ are called the upper and lower expected values of $f(\mathbf{x}, \tilde{\mathbf{c}})$, respectively, representing the largest and smallest expected solution costs for the probability distributions in $\mathcal{P}$ (see, e.g., [7]). The parameter $\alpha \in [0, 1]$ is called a *pessimism-optimism degree* and models a decision maker's risk aversion.

In this paper, we consider the following optimization problem:

$$\min_{\mathbf{x} \in \mathcal{X}} H_{\alpha}(\mathbf{x}) \qquad (2)$$

Hence, we seek a feasible solution that minimizes the generalized Hurwicz criterion for a specified value of the pessimism-optimism degree $\alpha \in [0, 1]$.

Let us focus on some special cases of (2). If $\mathcal{P} = \mathcal{P}(\mathcal{U})$, then $\bar{E}[f(\mathbf{x}, \tilde{\mathbf{c}})] = \max_{k \in [K]} f(\mathbf{x}, \mathbf{c}_k)$. Indeed, in this case, the worst probability distribution assigns the probability equal to 1 to scenario $\mathbf{c}_k$ maximizing the cost of $\mathbf{x}$. Similarly, $\underline{E}[f(\mathbf{x}, \tilde{\mathbf{c}})] = \min_{k \in [K]} f(\mathbf{x}, \mathbf{c}_k)$. Problem (2) reduces then to minimizing the traditional Hurwicz criterion under scenario set $\mathcal{U}$:

$$\min_{\mathbf{x} \in \mathcal{X}} \alpha \max_{k \in [K]} f(\mathbf{x}, \mathbf{c}_k) + (1 - \alpha) \min_{k \in [K]} f(\mathbf{x}, \mathbf{c}_k) \qquad (3)$$

If $\alpha = 1$ in (3), then we get the *robust min-max problem*, discussed for example, in [18].

If $\mathcal{P}$ contains only one probability distribution, $\mathbf{p}$, then (2) is equivalent to minimizing the expected solution cost under $\mathbf{p}$, i.e.

$$\min_{\mathbf{x} \in \mathcal{X}} \mathbb{E}_{\mathbf{p}}[f(\mathbf{x}, \tilde{\mathbf{c}})] = \sum_{k \in [K]} p_k f(\mathbf{x}, \mathbf{c}_k) \qquad (4)$$

In the traditional robust optimization approach (see, e.g., [2,18]), no additional information in a scenario set $\mathcal{U}$ is provided. This is equivalent to saying that any probability distribution in $\mathcal{P}(\mathcal{U})$ for $\tilde{\mathbf{c}}$ is admissible. The problem of type (3) can then be solved. However, some additional knowledge in $\mathcal{U}$ can be available in many practical applications. In particular, some evidence can indicate that scenarios from one subset of $\mathcal{U}$ are more likely to occur than scenarios from another subset. This knowledge can be naturally taken into account by using Dempster and Shafer theory of evidence [6,22]. The key concept of this theory is a nonnegative mass function defined in $2^{\mathcal{U}}$. Given a subset of scenarios $A \subseteq \mathcal{U}$, the mass assigned to A can be interpreted as a *subjective probability* of the event A, which supports the claim that the true scenario will belong to A. The masses provided induce a *belief function* in $2^{\mathcal{U}}$, which constitutes a lower bound on the probability distribution in $\mathcal{U}$. This fact can be used to define the set $\mathcal{P} \subseteq \mathcal{P}(\mathcal{U})$ of admissible probability distributions for $\tilde{\mathbf{c}}$ and then apply the solution concept (2). The concept of belief function can be extended by using *possibility theory* (see, e.g., [11]). That is, a mass can be assigned to a fuzzy subset of scenarios. The membership function of such a fuzzy subset is a *possibility distribution* in $\mathcal{U}$. The belief of an event $A \subseteq \mathcal{U}$ is then the expected necessity of A. By decomposing fuzzy sets into $\lambda$-cuts [12], we can reduce the possibilistic model of uncertainty into a model based on the traditional theory of evidence.

This paper is an extended version of the conference papers [13,14]. We generalize the results to a broader class of optimization problems. We strengthen the negative complexity result shown in [13]. We propose another approximation algorithm for (2), which is an alternative to the one constructed in [13]. Finally, we show how to solve the problem with a possibilistic uncertainty model, which remained open in [13].

This paper is organized as follows. In Section 2, we recall basic notions of the theory of evidence, namely the notions of the mass and belief functions. In Section 3, we apply them to define the set $\mathcal{P} \subseteq \mathcal{P}(\mathcal{U})$ of admissible probability distributions in $\mathcal{U}$. We then consider the optimization problem (2) with $\mathcal{P}$. In Section 4, we investigate the complexity of the problem (2). We show that it is NP-hard for each $\alpha \in [0, 1]$ even in the very restrictive case when $\mathcal{X}$ is a polytope in $[0, 1]^n$ and the function $f$ is linear. In Section 5, we propose a mixed integer programming problem for solving (2). We also identify some
special cases of the problem which can be solved in polynomial time. In Section 6, we construct approximation algorithms for (2). Finally, in Section 7, we extend the uncertainty model to the possibilistic (fuzzy) case. An example illustrating this model is shown in Section 8.

## 2. Belief functions and imprecise probabilities

In this section, we recall the concept of a belief function and its relationships with imprecise probabilities (more details can be found in [6,22,7]). Let $\Omega = \{\omega_1, \dots, \omega_K\}$ be a finite non-empty set of states. A mass function is a mapping $m$ from $2^\Omega$ to $[0, 1]$ such that

$$ \sum_{A \subseteq \Omega} m(A) = 1 $$

and $m(\emptyset) = 0$. Given $A \subseteq \Omega$, $m(A)$ is available evidence that supports the claim that the actual state belongs to A. Set $A \subseteq \Omega$ such that $m(A) > 0$ is called a focal set. The mass function $m$ induces the following belief function:

$$ \mathrm{Bel}(A) = \sum_{B \subseteq A} m(B). \qquad (5) $$

If all focal sets are singletons, then Bel is a probability distribution in $\Omega$, providing complete probabilistic information in $\Omega$. On the other hand, if there is only one focal set, say $E$, then Bel is a logical measure, describing imprecise information in $\Omega$. We only know for sure that event $E$ will occur and nothing more. In the extreme case when $E = \Omega$, there is complete uncertainty in $\Omega$.

A probability distribution $P$ in $\Omega$ is compatible with Bel if $P(A) \geq \mathrm{Bel}(A)$ for each event $A \subseteq \Omega$ (see, e.g., [7]). Therefore, $\mathrm{Bel}(A)$ is a lower bound on the probability $P(A)$. If Bel is induced by the mass function $m$, then the credal set $\mathcal{P}(m)$ contains all probability distributions compatible with Bel, i.e.

$$ \mathcal{P}(m) = \{P \in \mathcal{P}(\Omega) : P(A) \geq \mathrm{Bel}(A), A \subseteq [K]\}, \qquad (6) $$

where $\mathcal{P}(\Omega)$ is the set of all probability distributions in $\Omega$. As $\Omega$ is finite, the set $\mathcal{P}(m)$ can be described by the following system of linear constraints:

$$ \begin{aligned} & \sum_{k \in A} p_k \geq \mathrm{Bel}(A) \quad A \subseteq [K] \\ & \sum_{k \in [K]} p_k = 1 \\ & p_k \geq 0 \quad k \in [K], \end{aligned} \qquad (7) $$

where $p_k$ is a probability that state $\omega_k$ will occur. Notice that $\mathcal{P}(m)$ is bounded, closed and convex. Each element of $\mathcal{P}(m)$ is a vector $\mathbf{p} \in [0, 1]^K$ being a discrete probability distribution in $[K]$. In Section 7, we will study a generalization of the belief function (5). In particular, we will show that (7) has at least one solution, so $\mathcal{P}(m)$ is also nonempty.

## 3. Robust optimization with belief functions (ROBF)

In this section, we will use the concept of belief function described in Section 2 to model the uncertainty in the objective function of (1). Recall that the vector of the objective function coefficients $\tilde{c}$ can take one of a finite set of values in $\mathcal{U} = \{\mathbf{c}_1, \dots, \mathbf{c}_K\} \subseteq \mathbb{R}^l, K \geq 1$. In order to apply the concepts from Section 2, we will identify scenarios with states $\omega_1, \dots, \omega_K$, i.e. $\Omega = \mathcal{U}$. Let $m: 2^l \to [0, 1]$ be a mass function in $\mathcal{U}$. To simplify notation, we will identify each subset of scenarios $A \subseteq \mathcal{U}$ with the set of indices of the elements of A. Therefore, $m$ can be equivalently defined as a mass function in the power set $2^l$ of the indices, i.e. $m: 2^l \to [0, 1]$. Let

$$ \mathcal{F} = \{F \subseteq [K] : m(F) > 0\} = \{F_1, \dots, F_\ell\} $$

be the set of all focal sets of $[K]$ and $z(\mathcal{F}) = \max_{F \in \mathcal{F}} |F|$ be the size of the largest focal set. The mass function $m$ induces the belief function Bel in $\mathcal{U}$, which in turn provides us a set of $\mathcal{P}(m)$ of admissible probability distributions in $\mathcal{U}$. The set $\mathcal{P}(m)$ is described by (7), where $p_k$ is now the probability that scenario $\mathbf{c}_k$ will occur. The following equations are true (see, e.g., [7]):

$$ \bar{E}[f(\mathbf{x}, \tilde{\mathbf{c}})] = \max_{\mathbf{p} \in \mathcal{P}(m)} \mathbb{E}_{\mathbf{p}}[f(\mathbf{x}, \tilde{\mathbf{c}})] = \sum_{F \in \mathcal{F}} m(F) \max_{k \in F} f(\mathbf{x}, \mathbf{c}_k), \qquad (8) $$

$$ \underline{E}[f(\mathbf{x}, \tilde{\mathbf{c}})] = \min_{\mathbf{p} \in \mathcal{P}(m)} \mathbb{E}_{\mathbf{p}}[f(\mathbf{x}, \tilde{\mathbf{c}})] = \sum_{F \in \mathcal{F}} m(F) \min_{k \in F} f(\mathbf{x}, \mathbf{c}_k). \qquad (9) $$
A proof of (8) and (9) is shown in Appendix A for completeness. Using (8) and (9) we can represent the problem (2) as the following robust optimization problem with belief functions:

$$ (\text{ROBF}) \quad \min_{\mathbf{x} \in \mathcal{X}} H_{\alpha}(\mathbf{x}) = \sum_{F \in \mathcal{F}} m(F) \left( \alpha \max_{k \in F} f(\mathbf{x}, \mathbf{c}_k) + (1-\alpha) \min_{k \in F} f(\mathbf{x}, \mathbf{c}_k) \right) \quad (10) $$

If $\bar{\mathbf{p}} \in \mathcal{P}(m)$ maximizes and $\underline{\mathbf{p}} \in \mathcal{P}(m)$ minimizes the expected cost of $\mathbf{x}$, then $H_{\alpha}(\mathbf{x})$ is the expected cost with respect to $\hat{\mathbf{p}} = \alpha \bar{\mathbf{p}} + (1-\alpha) \underline{\mathbf{p}}$. Because $\alpha \in [0, 1]$ and $\mathcal{P}(m)$ is convex set, $\hat{\mathbf{p}} \in \mathcal{P}(m)$. Hence $H_{\alpha}(\mathbf{x})$ is the expected cost of $\mathbf{x}$ with respect to a probability distribution in $\mathcal{P}(m)$, being a convex combination of the worst and the best probability distribution for $\mathbf{x}$. A method of computing $\bar{\mathbf{p}}$ and $\underline{\mathbf{p}}$ for a given solution $\mathbf{x}$ is shown in Appendix A.

Let us focus on the first complexity issue that can arise while solving (10). In general, specifying the mass function $m$ may require providing up to $2^K$ numbers, which can be intractable for larger $K$. In practice, we can assume that the number of focal sets $|\mathcal{F}|$ is bounded by a polynomial in $K$. Alternatively, one can also provide a rule for assigning the masses to subsets of $K$, which leads to a reformulation of (10) of a polynomial size in $n$ and $K$ (i.e. in the size of the problem).

We now show several special cases of (10), already discussed in the literature. If $m([K]) = 1$, then we get the problem with the Hurwicz criterion (3), which reduces to the robust min-max problem when additionally $\alpha = 1$. On the other hand, if $z(\mathcal{F}) = 1$ (i.e. all focal sets are singletons), then (10) reduces to minimizing the expected solution cost for the probability distribution $p_k = m([k])$, $k \in [K]$, i.e. to the problem (4).

Let us describe yet another special case of (10). In robust optimization with scenario set $\mathcal{U}$ the Ordered Weighted Averaging criterion (OWA for short), proposed in [24], is commonly used (see, e.g., [4,15,20]). Let $\mathbf{w} = (w_1, \dots, w_K)$ be a vector of nonnegative weights that sum up to 1. Given a solution $\mathbf{x} \in \mathcal{X}$, let $\sigma$ be a permutation of $[K]$ such that $f(\mathbf{x}, \mathbf{c}_{\sigma(1)}) \ge \dots \ge f(\mathbf{x}, \mathbf{c}_{\sigma(K)})$, then

$$ \text{Owa}_{\mathbf{w}}(\mathbf{x}) = \sum_{k \in [K]} w_k f(\mathbf{x}, \mathbf{c}_{\sigma(k)}). $$

It is easy to see that $\text{Owa}_{\mathbf{w}}(\mathbf{x}) = \max_{k \in [K]} f(\mathbf{x}, \mathbf{c}_k)$, when $\mathbf{w} = (1, 0, \dots, 0)$ and $\text{Owa}_{\mathbf{w}}(\mathbf{x}) = \min_{k \in [K]} f(\mathbf{x}, \mathbf{c}_k)$, when $\mathbf{w} = (0, 0, \dots, 1)$.

Define $m(A) = \frac{2}{K(K-1)}$ for each $A \subseteq [K]$ such that $|A| = 2$ and $m(A) = 0$, otherwise. Hence, all focal sets are cardinality of 2, and they are assigned the same mass value. Making use of (8), we obtain

$$ \bar{E}[f(\mathbf{x}, \tilde{\mathbf{c}})] = \frac{2}{K(K-1)} \sum_{\{i, j\} \subseteq [K]: i \neq j} \max\{f(\mathbf{x}, \mathbf{c}_i), f(\mathbf{x}, \mathbf{c}_j)\}. $$

Order the scenarios so that $f(\mathbf{x}, \mathbf{c}_1) \ge \dots \ge f(\mathbf{x}, \mathbf{c}_K)$. Then

$$ \bar{E}[f(\mathbf{x}, \tilde{\mathbf{c}})] = \frac{2}{K(K-1)} \left( (K-1)f(\mathbf{x}, \mathbf{c}_1) + (K-2)f(\mathbf{x}, \mathbf{c}_2) + \dots + (K-K)f(\mathbf{x}, \mathbf{c}_K) \right) $$

Hence,

$$ \bar{E}[f(\mathbf{x}, \tilde{\mathbf{c}})] = \text{Owa}_{\mathbf{w}}(\mathbf{x}), $$

where $\mathbf{w} = (\frac{2(K-1)}{K(K-1)}, \frac{2(K-2)}{K(K-1)}, \dots, 0)$. Similarly, using (9) we get

$$ \underline{E}[f(\mathbf{x}, \tilde{\mathbf{c}})] = \text{Owa}_{\mathbf{w}'}(\mathbf{x}), $$

where $\mathbf{w}' = (0, \frac{2-1}{K(K-1)}, \frac{2-2}{K(K-1)}, \dots, \frac{2(K-1)}{K(K-1)})$. So, $w_k' = w_{K-k+1}$, $k \in [K]$. It is not difficult to generalize this example, and this case is described in the following proposition:

**Proposition 1.** Suppose that $m(A) = 1/(K)$ for each $A \subseteq [K]$ such that $|A| = l \le K$ and $m(A) = 0$, otherwise. Then $\bar{E}[f(\mathbf{x}, \tilde{\mathbf{c}})]$ is the OWA criterion with weights $w_k = (\frac{K-k}{l-1})/(K)$ for $k = 1, \dots, K-l+1$ and $w_k = 0$ for $k = K-l+2, \dots, K$. Similarly, $\underline{E}[f(\mathbf{x}, \tilde{\mathbf{c}})]$ is the OWA criterion with weights $w_k' = w_{K-k+1}$, $k \in [K]$.

**Proof.** The following equation

$$ \bar{E}[f(\mathbf{x}, \tilde{\mathbf{c}})] = 1/(K) \sum_{A \subseteq [K]: |A|=l} \max_{k \in A} f(\mathbf{x}, \mathbf{c}_k) $$

holds. Let us order the scenarios so that $f(\mathbf{x}, \mathbf{c}_1) \ge \dots \ge f(\mathbf{x}, \mathbf{c}_K)$. There are exactly $\binom{K-k}{l-1}$ subsets $A \subseteq [K]$ such that $A = \{k\} \cup A'$, $|A'| = l-1$, and $A' \subseteq \{k+1, \dots, K\}$. Therefore, $f(\mathbf{x}, \mathbf{c}_k)$ is the maximizer over $k \in A$. Thus,
<table><caption>**Table 1**
Scenarios for the sample instance of MINSAT.</caption><thead><tr><th>x</th><th>c<sub>1</sub></th><th>c<sub>2</sub></th><th>c<sub>3</sub></th><th>c<sub>4</sub></th><th>c<sub>5</sub></th><th>c<sub>6</sub></th><th>c<sub>7</sub></th><th>c<sub>8</sub></th><th>c'<sub>1</sub></th><th>c'<sub>2</sub></th><th>c'<sub>3</sub></th><th>c'<sub>4</sub></th></tr></thead><tbody><tr><td>0</td><td>x<sub>1</sub></td><td>1</td><td>0</td><td>1</td><td>0</td><td>1</td><td>0</td><td>0</td><td>1</td><td>0</td><td>0</td><td>0</td><td>0</td></tr><tr><td>1</td><td>x&#773;<sub>1</sub></td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>1</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td></tr><tr><td>1</td><td>x<sub>2</sub></td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>1</td><td>1</td><td>0</td><td>0</td><td>0</td><td>0</td></tr><tr><td>0</td><td>x&#773;<sub>2</sub></td><td>1</td><td>1</td><td>0</td><td>0</td><td>0</td><td>1</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td></tr><tr><td>0</td><td>x<sub>3</sub></td><td>0</td><td>1</td><td>1</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td></tr><tr><td>1</td><td>x&#773;<sub>3</sub></td><td>0</td><td>0</td><td>0</td><td>1</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td></tr><tr><td>0</td><td>x<sub>4</sub></td><td>0</td><td>0</td><td>0</td><td>1</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td></tr><tr><td>1</td><td>x&#773;<sub>4</sub></td><td>0</td><td>0</td><td>0</td><td>0</td><td>1</td><td>1</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td></tr><tr><td>x<sub>5</sub></td><td></td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>2</td><td>2</td><td>2</td><td>2</td><td>2</td></tr><tr><td>x&#773;<sub>5</sub></td><td></td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>2</td><td>2</td><td>2</td><td>2</td><td>2</td></tr></tbody></table>

$$ \bar{E}[f(\mathbf{x}, \tilde{\mathbf{c}})] = 1/\binom{K}{l} \left( \binom{K-1}{l-1} f(\mathbf{x}, c_1) + \binom{K-2}{l-1} f(\mathbf{x}, c_2) + \dots + \binom{l-1}{l-1} f(\mathbf{x}, c_{K-l+1}) \right) $$

and the proposition follows. The case for $\bar{E}[f(\mathbf{x}, \tilde{\mathbf{c}})]$ is just symmetric. □

### 4. Computational complexity of the ROBF problem

From the known results in robust combinatorial optimization, it immediately follows that (10) is NP-hard when $\mathbb{X} \subseteq \{0, 1\}^n$. Indeed, the min-max problem, being a special case of (10), is already NP-hard for $K=2$ and strongly NP-hard when $K$ is unbounded for basic selection and network problems (see [16] for a survey). The following result for $\alpha \in [0, 1)$ shows that (10) can also be NP-hard if the underlying problem (1) is a linear programming problem (a continuous case). We show in Section 5 that the case $\alpha = 1$ is easier to solve.

**Theorem 1.** The problem (10) is NP-hard for each $\alpha \in [0, 1)$, when $\mathbb{X}$ is a polyhedron in $[0, 1]^n$ and the function $f$ is linear.

**Proof.** Consider the following MINSAT problem. Given a set of $s$ boolean variables $q_1, \dots, q_s$, a collection of $t$ clauses $C_1, \dots, C_t$ over the boolean variables and a positive integer $r < t$. We ask if there is a truth assignment to the variables in which at least $r$ clauses are unsatisfied. The MINSAT problem is known to be NP-complete, even if each clause contains at most two literals [17].

We now propose a reduction from MINSAT to problem (10). Given an instance of MINSAT, we build the corresponding instance of problem (10). We can assume w.l.o.g. that $t$ is even and $r = t/2$ (as we can add a valid number of dummy clauses to the instance). Let us define variables $x_i$ and $\bar{x}_i$ for each $i \in [s+1]$, so the number of variables is $n = 2s+2$. Define the polyhedron $\mathbb{X}$ by using constraints $x_i \ge 0$, $\bar{x}_i \ge 0$ and $x_i + \bar{x}_i = 1$, $i \in [s+1]$. For each clause $C_i$, we form scenario $c_i$ as follows. If $q_j \in C_i$, then the cost of $x_j$ is 1; if $\bar{q}_j \in C_i$ ($\bar{q}_j$ is the negation of $q_j$), then the cost of $\bar{x}_j$ is 1 under $c_i$; the costs of the remaining variables under $c_i$ are set to 0. Next, we add $r$ scenarios $c'_1, \dots, c'_r$ under which the costs of $x_{s+1}$ and $\bar{x}_{s+1}$ are 2 and the costs of the remaining variables are 0. Hence, the total number of scenarios formed is $K = t + r = 3r$. We choose the linear cost function $f(\mathbf{x}, \mathbf{c}) = \mathbf{c}^T \mathbf{x}$. Finally, the mass function $m$ assigns the mass $1/(2^{t+r}) = 1/(2^{3r})$ to each subset of scenarios with the cardinality of $2r+1$ and mass 0 to all the remaining subsets. Observe (see Proposition 1), that

$$ H_{\alpha}(\mathbf{x}) = \alpha Owa_{\mathbf{w}}(\mathbf{x}) + (1 - \alpha) Owa_{\mathbf{w}'}(\mathbf{x}), \quad (11) $$

where

$$ \mathbf{w} = \left( \underbrace{\left( \frac{3r-1}{2r} \right), \dots, \left( \frac{3r-r}{2r} \right)}_{r \text{ positive weights}}, \underbrace{0, \dots, 0}_{2r \text{ weights}} \right), \quad \mathbf{w}' = \left( \underbrace{0, \dots, 0}_{2r \text{ weights}}, \underbrace{\left( \frac{3r-r}{2r}, \dots, \left( \frac{3r-1}{2r} \right)}_{r \text{ positive weights}}}_{\frac{3r}{2r+1}, \dots, \frac{3r-1}{2r+1}} \right) $$

Therefore, only the first $r$ weights are positive in $\mathbf{w}$, and only the last $r$ weights are positive in $\mathbf{w}'$.

To illustrate the reduction, consider a sample instance with variables $q_1, q_2, q_3, q_4$, clauses $(q_1 \lor \bar{q}_2)$, $(\bar{q}_2 \lor q_3)$, $(q_1 \lor q_3)$, $(\bar{q}_3 \lor q_4)$, $(q_1 \lor \bar{q}_4)$, $(\bar{q}_2 \lor \bar{q}_4)$, $(\bar{q}_1 \lor q_2)$, $(q_1 \lor q_2)$ and $r=4$. The scenarios for this instance are shown in Table 1.

We fix $m(A) = 1/(9)$ for each $A \subseteq [K]$ such that $|A| = 9$ and 0, otherwise. Polyhedron $\mathbb{X}$ is defined by $x_i + \bar{x}_i = 1$, $x_i, \bar{x}_i \ge 0$, $i = 1, \dots, 5$. The weights in (11) are then $\mathbf{w} = (\frac{165}{220}, \frac{45}{220}, \frac{9}{220}, \frac{1}{220}, 0, 0, 0, 0, 0, 0, 0)$ and $\mathbf{w}' = (0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, \frac{1}{220}, \frac{9}{220}, \frac{45}{220}, \frac{165}{220})$.

Observe that in this proof, we have constructed an instance of the problem (10) with an exponential number of focal sets. However, it is possible to describe this instance in a polynomial of the size of the instance of MINSAT due to Proposition 1. Hence, the reduction is polynomial.
We now show that the answer to MINSAT is yes if and only if $H_\alpha(\mathbf{x}) \le 2\alpha$ for some feasible solution $\mathbf{x} \in \mathbb{X}$. Because the cost of any solution $\mathbf{x}$ under scenarios $c'_1, \dots, c'_r$ is equal to 2 and under scenarios $c_1, \dots, c_t$ is not greater than 2, we get $Owa_{\mathbf{w}}(\mathbf{x}) = 2$ for each $\mathbf{x} \in \mathbb{X}$. Hence, it is enough to show that the answer to MINSAT is yes if and only if $Owa_{\mathbf{w}}(\mathbf{x}) = 0$ for some feasible solution $\mathbf{x} \in \mathbb{X}$.

Assume that the answer to MINSAT is yes and let $q_1, \dots, q_s$ be a truth assignment to the variables that satisfies no more than $r$ clauses. Let us form a feasible solution $\mathbf{x} \in \mathbb{X}$ such that $x_j = 1, \bar{x}_j = 0$ if $q_j = 1$ and $x_j = 0, \bar{x}_j = 1$ if $q_j = 0$. We also fix $x_{s+1} = 1$ and $\bar{x}_{s+1} = 0$. By the construction, there are at least $r$ scenarios under which the cost of $\mathbf{x}$ is 0 and thus no more than $2r$ scenarios under which the cost of $\mathbf{x}$ is positive. Hence, $Owa_{\mathbf{w}}(\mathbf{x}) = 0$.

Assume that $Owa_{\mathbf{w}}(\mathbf{x}) = 0$ for some feasible solution $\mathbf{x} \in \mathbb{X}$. Because the costs under scenarios are nonnegative, there must be at least $r$ scenarios, say $c_1, \dots, c_r$ under which the cost of $\mathbf{x}$ is 0. We get $c_i^T \mathbf{x} = 0$ if and only if $x_j = 0, \bar{x}_j = 1$ ($\bar{x}_j = 0, x_j = 1$) if $q_j \in C_i$ ($\bar{q}_j \in C_i$). It is possible for some $j \in [s]$ that neither $x_j$ nor $\bar{x}_j$ appears in the clauses $C_1, \dots, C_r$ corresponding to $c_1, \dots, c_r$ (so $x_j$ can be fractional). In this case, we assign any value to $q_j$ which does not change the values of $C_1, \dots, C_r$ (they are still not satisfied). This defines a truth assignment to $q_1, \dots, q_s$ under which at least the $r$ clauses are not satisfied. $\square$

**Corollary 1.** If $\alpha = 0$, then the problem (10) is not approximable, if $\mathbb{X}$ is a polyhedron in $[0, 1]^n$ and the function $f$ is linear, unless $P=NP$.

**Proof.** In the proof of Theorem 1 for $\alpha = 0$, the answer to MINSAT is yes if and only if there is a solution $\mathbf{x} \in \mathbb{X}$ such that $H_\alpha(\mathbf{x}) \le 0$. Hence, any approximation algorithm would be used to solve the NP-hard MINSAT problem. $\square$

## 5. Solving the ROBF problem

In this section, we propose some solving methods (10). We also identify some special cases of this problem which can be solved in polynomial time. Problem (10) can be represented as the following mixed integer program:

$$ \begin{array}{ll} \min & \sum_{F \in \mathcal{F}} m(F)y(F) \\ & y(F) \ge \alpha f(\mathbf{x}, \mathbf{c}_k) + (1-\alpha)u(F) \quad F \in \mathcal{F}, k \in F \\ & u(F) \ge f(\mathbf{x}, \mathbf{c}_k) - M(1-\delta_k(F)) \quad F \in \mathcal{F}, k \in F \\ & \sum_{k \in F} \delta_k(F) = 1 \quad F \in \mathcal{F} \\ & \delta_k(F) \in \{0, 1\} \quad F \in \mathcal{F}, k \in F \\ & y(F), u(F) \ge 0 \quad F \in \mathcal{F} \\ & \mathbf{x} \in \mathbb{X}, \end{array} \quad (12) $$

where $M$ is a large constant. The variables $u(F) \ge 0$ and $\delta_k(F) \in \{0, 1\}$ are used to model the terms $\min_{k \in F} f(\mathbf{x}, \mathbf{c}_k)$ in (10). Namely, $\delta_k^*(F) = 1$ if $k^* = \arg \min_{k \in F} f(\mathbf{x}, \mathbf{c}_k)$ and $u(F) = f(\mathbf{x}, \mathbf{c}_k^*)$. The computational complexity of solving (12) depends on the number of focal sets and the definition of the cost function $f$. In particular, when $|\mathcal{F}|$ is not very large and the function $f$ is linear, the problem can be solved using some MIP solvers. The problem simplifies when $\alpha = 1$. Using (8) we immediately get the following result:

**Proposition 2.** If $\alpha = 1$, then the problem (10) is equivalent to the following optimization problem:

$$ \begin{array}{ll} \min & \sum_{F \in \mathcal{F}} m(F)y(F) \\ & y(F) \ge f(\mathbf{x}, \mathbf{c}_k) \quad F \in \mathcal{F}, k \in F \\ & \mathbf{x} \in \mathbb{X} \end{array} \quad (13) $$

If the function $f$ is convex in $\mathbf{x}$ and the set $\mathbb{X}$ is convex, then (13) is a convex optimization problem, which in most cases can be solved efficiently (see, e.g., [3]). In particular, if the function $f$ is linear, then (13) is a linear programming problem.

**Proposition 3.** If $\alpha \in [0.5, 1]$ and $z(\mathcal{F}) = 2$, then problem (10) is equivalent to the following optimization problem:

$$ \begin{array}{ll} \min & \sum_{k \in [K]} m_k f(\mathbf{x}, \mathbf{c}_k) + \sum_{\{i,j\} \in \mathcal{F}} m_{ij} y_{ij} \\ & y_{ij} \ge \alpha f(\mathbf{x}, \mathbf{c}_i) + (1-\alpha) f(\mathbf{x}, \mathbf{c}_j) \quad \{i, j\} \in \mathcal{F} \\ & y_{ij} \ge \alpha f(\mathbf{x}, \mathbf{c}_j) + (1-\alpha) f(\mathbf{x}, \mathbf{c}_i) \quad \{i, j\} \in \mathcal{F} \\ & \mathbf{x} \in \mathbb{X}, \end{array} \quad (14) $$
where $m_k = m(k)$, $k \in [K]$, and $m_{ij} = m(i, j)$ for $\{i, j\} \in \mathcal{F}$.

**Proof.** From (8) and (9), it follows that the objective function of (10) can be expressed as

$$ \sum_{k \in [K]} m_k f(\mathbf{x}, \mathbf{c}_k) + \sum_{\{i, j\} \in \mathcal{F}} m_{ij} (\alpha \max\{f(\mathbf{x}, \mathbf{c}_i), f(\mathbf{x}, \mathbf{c}_j)\} + (1-\alpha) \min\{f(\mathbf{x}, \mathbf{c}_i), f(\mathbf{x}, \mathbf{c}_j)\}) = $$

$$ \sum_{k \in [K]} m_k f(\mathbf{x}, \mathbf{c}_k) + \sum_{\{i, j\} \in \mathcal{F}} m_{ij} \max\{\alpha f(\mathbf{x}, \mathbf{c}_i) + (1-\alpha) f(\mathbf{x}, \mathbf{c}_j), \alpha f(\mathbf{x}, \mathbf{c}_j) + (1-\alpha) f(\mathbf{x}, \mathbf{c}_i)\}. $$

To see that this equality is true, consider two cases for each $\{i, j\} \in \mathcal{F}$. In the first case $f(\mathbf{x}, \mathbf{c}_j) \ge f(\mathbf{x}, \mathbf{c}_i)$. Then, because $\alpha \ge 0.5$, we get $\alpha f(\mathbf{x}, \mathbf{c}_j) + (1-\alpha) f(\mathbf{x}, \mathbf{c}_i) \ge \alpha f(\mathbf{x}, \mathbf{c}_i) + (1-\alpha) f(\mathbf{x}, \mathbf{c}_j)$ and the terms in summations in both sides of the equality are the same. The second case, $f(\mathbf{x}, \mathbf{c}_j) \le (\mathbf{x}, \mathbf{c}_i)$ is just symmetric. Introducing additional variables $y_{ij}$ for $\{i, j\} \in \mathcal{F}$ to express the inner maxima yields (14). □

Observe that if the function $f$ is convex in $\mathcal{X}$, then (14) is a convex optimization problem. In particular, if the function $f$ is linear, then it becomes a linear programming problem.

**Theorem 2.** If $\mathcal{X}$ is a convex set in $\mathbb{R}^n$ and $f$ is a convex function, then (10) can be solved by solving a family $z(\mathcal{F})^\ell$ of convex problems, where $\ell = |\mathcal{F}|$.

**Proof.** Observe that for each $F \in \mathcal{F}$, there is exactly one binary variable $\delta_k(F)$, $k \in F$, in (12) which is equal to 1. Denote the index of this variable by $k_F$. If we could guess the optimal values for $k_F$, $F \in \mathcal{F}$, then the model (12) simplifies to the following convex problem:

$$ \begin{array}{ll} \min & \sum_{F \in \mathcal{F}} m(F)y(F) \\ & y(F) \ge \alpha f(\mathbf{x}, \mathbf{c}_k) + (1-\alpha) f(\mathbf{x}, \mathbf{c}_{k_F}) \quad F \in \mathcal{F} \\ & y(F) \ge 0 \quad F \in \mathcal{F} \\ & \mathbf{x} \in \mathcal{X}, \end{array} \quad (15) $$

There are at most $z(\mathcal{F})^\ell$ possible choices of $k_F$, $F \in \mathcal{F}$, and we can try all of them to find the one that minimizes (15). Hence (12) can be decomposed into solving $z(\mathcal{F})^\ell$ problems of the type (15). □

Theorem 2 can be applied when the number of focal sets in $\mathcal{F}$ is not large. In particular, if problem (1) is a linear programming problem and $z(\mathcal{F})$ is bounded by a constant, then problem (10) can be solved in polynomial time.

## 6. Approximation algorithms for the ROBF problem

In this section, we will propose two approximation algorithms for (10). In the first, we will assume w.l.o.g. that $|F| \ge 2$ for each focal set $F \in \mathcal{F}$. Indeed, if a positive mass is assigned to a single scenario $\mathbf{c}_k$, then we add a copy $\mathbf{c}'_k$ of this scenario to $\mathcal{U}$ and fix $m(k, k') := m(k)$ and $m(k') := 0$. This transformation does not change the values of $\bar{E}[f(\mathbf{x}, \bar{\mathbf{c}})]$ and $\underline{E}[f(\mathbf{x}, \underline{\mathbf{c}})]$ (see equations (8) and (9)). Define

$$ v_k = \sum_{F \in \mathcal{F}: k \in F} m(F), \quad k \in [K]. $$

If $\{F \in \mathcal{F}: k \in F\} = \emptyset$, then we set $v_k = 0$. Consider the following optimization problem:

$$ \min \sum_{\substack{k \in [K] \\ \mathbf{x} \in \mathcal{X}}} v_k f(\mathbf{x}, \mathbf{c}_k) \quad (16) $$

Observe that (16) is a convex optimization problem if $\mathcal{X}$ is a convex set, and $f$ is a convex function. For linear cost functions, $f(\mathbf{x}, \mathbf{c}_k) = \mathbf{c}'_k \mathbf{x}$, (16) is equivalent to the deterministic problem $\min_{\mathbf{x} \in \mathcal{X}} \mathbf{c}'_k \mathbf{x}$, with the cost vector $\mathbf{c} = \sum_{k \in [K]} v_k \mathbf{c}_k$. In particular, (16) is then a linear programming problem if $\mathcal{X}$ is a polytope described by a system of linear constraints.

**Theorem 3.** Let $\hat{\mathbf{x}} \in \mathcal{X}$ be an optimal solution to (16) and let $\mathbf{x}^* \in \mathcal{X}$ be an optimal solution to (10). Then

$$ H_{\alpha}(\hat{\mathbf{x}}) \le z(\mathcal{F}) H_{\alpha}(\mathbf{x}^*) \quad \text{for } \alpha \in [0.5, 1] \quad (17) $$

$$ H_{\alpha}(\hat{\mathbf{x}}) \le \frac{1-\alpha}{\alpha} z(\mathcal{F}) H_{\alpha}(\mathbf{x}^*) \quad \text{for } \alpha \in (0, 0.5] \quad (18) $$
**Proof.** We will show first that for each $\alpha \in [0, 1]$ the following inequality holds:

$$H_{\alpha}(\mathbf{x}^*) \geq \frac{\alpha}{z(\mathcal{F})} \sum_{F \in \mathcal{F}} m(F) \sum_{k \in F} f(\hat{\mathbf{x}}, \mathbf{c}_k). \quad (19)$$

Using equations (8) and (9) we get

$$\begin{align*} H_{\alpha}(\mathbf{x}^*) &\geq \alpha \sum_{F \in \mathcal{F}} m(F) \max_{k \in F} f(\mathbf{x}^*, \mathbf{c}_k) \geq \alpha \sum_{F \in \mathcal{F}} m(F) \frac{1}{|F|} \sum_{k \in F} f(\mathbf{x}^*, \mathbf{c}_k) &\overset{(a)}{\geq} \\ \alpha \sum_{F \in \mathcal{F}} m(F) \frac{1}{z(\mathcal{F})} \sum_{k \in F} f(\mathbf{x}^*, \mathbf{c}_k) &= \frac{\alpha}{z(\mathcal{F})} \sum_{k \in [K]} \sum_{F \in \mathcal{F}: k \in F} m(F) f(\mathbf{x}^*, \mathbf{c}_k) = \\ \frac{\alpha}{z(\mathcal{F})} \sum_{k \in [K]} v_k f(\mathbf{x}^*, \mathbf{c}_k) &\overset{(b)}{\geq} \frac{\alpha}{z(\mathcal{F})} \sum_{k \in [K]} v_k f(\hat{\mathbf{x}}, \mathbf{c}_k) = \frac{\alpha}{z(\mathcal{F})} \sum_{F \in \mathcal{F}} m(F) \sum_{k \in F} f(\hat{\mathbf{x}}, \mathbf{c}_k). \end{align*}$$

Inequality (a) follows from the fact that $z(\mathcal{F}) \geq |F|$ for each $F \in \mathcal{F}$. In the inequality (b) we use the optimality of $\hat{\mathbf{x}}$ in (16). If $\alpha \in [0.5, 1]$ and $|F| \geq 2$, then

$$\alpha \sum_{k \in F} f(\hat{\mathbf{x}}, \mathbf{c}_k) \geq \alpha \max_{k \in F} f(\hat{\mathbf{x}}, \mathbf{c}_k) + (1 - \alpha) \min_{k \in F} f(\hat{\mathbf{x}}, \mathbf{c}_k)$$

and (19) implies $H_{\alpha}(\mathbf{x}^*) \geq \frac{1}{z(\mathcal{F})} H_{\alpha}(\hat{\mathbf{x}})$, which yields (17). On the other hand, if $\alpha \in (0, 0.5]$ and $|F| \geq 2$, then

$$(1 - \alpha) \sum_{k \in F} f(\hat{\mathbf{x}}, \mathbf{c}_k) \geq \alpha \max_{k \in F} f(\hat{\mathbf{x}}, \mathbf{c}_k) + (1 - \alpha) \min_{k \in F} f(\hat{\mathbf{x}}, \mathbf{c}_k)$$

and (19) implies $H_{\alpha}(\mathbf{x}^*) \geq \frac{\alpha}{(1-\alpha)z(\mathcal{F})} H_{\alpha}(\hat{\mathbf{x}})$, which yields (18). $\square$

In some cases, we are able to compute an exact or approximate solution to problem (13), which is more general than (16). This is true, for example, when the cost functions are linear and set $\mathcal{X}$ is convex. In this case, we can use the following approximation result.

**Theorem 4.** If problem (13) is approximable within $\gamma \geq 1$, then (10) is approximable within $\gamma \left(1 + \frac{(1-\alpha)}{\alpha} \frac{\sum_{F \in \mathcal{F}} \min_{k \in F} f(\hat{\mathbf{x}}, \mathbf{c}_k)}{\sum_{F \in \mathcal{F}} \max_{k \in F} f(\hat{\mathbf{x}}, \mathbf{c}_k)} \right)$ for every $\alpha \in [0, 1]$, where $\hat{\mathbf{x}}$ is a $\gamma$-approximate solution to (13).

**Proof.** Let $\mathbf{x}^*$ be an optimal solution to (10) and $\hat{\mathbf{x}}$ be a $\gamma$-approximate solution to (13). This gives a lower bound on $H_{\alpha}(\mathbf{x}^*)$, i.e.

$$H_{\alpha}(\mathbf{x}^*) \geq \alpha \sum_{F \in \mathcal{F}} \max_{k \in F} f(\mathbf{x}^*, \mathbf{c}_k) \geq \frac{\alpha}{\gamma} \sum_{F \in \mathcal{F}} \max_{k \in F} f(\hat{\mathbf{x}}, \mathbf{c}_k). \quad (20)$$

Consider an upper bound on the relative error of $H_{\alpha}(\hat{\mathbf{x}})$:

$$\begin{align*} \frac{H_{\alpha}(\hat{\mathbf{x}}) - H_{\alpha}(\mathbf{x}^*)}{H_{\alpha}(\mathbf{x}^*)} &\overset{(20)}{\leq} \frac{H_{\alpha}(\hat{\mathbf{x}}) - \frac{\alpha}{\gamma} \sum_{F \in \mathcal{F}} \max_{k \in F} f(\hat{\mathbf{x}}, \mathbf{c}_k)}{\frac{\alpha}{\gamma} \sum_{F \in \mathcal{F}} \max_{k \in F} f(\hat{\mathbf{x}}, \mathbf{c}_k)} \\ &= \frac{\alpha \sum_{F \in \mathcal{F}} \max_{k \in F} f(\hat{\mathbf{x}}, \mathbf{c}_k) + (1-\alpha) \sum_{F \in \mathcal{F}} \min_{k \in F} f(\hat{\mathbf{x}}, \mathbf{c}_k) - \frac{\alpha}{\gamma} \sum_{F \in \mathcal{F}} \max_{k \in F} f(\hat{\mathbf{x}}, \mathbf{c}_k)}{\frac{\alpha}{\gamma} \sum_{F \in \mathcal{F}} \max_{k \in F} f(\hat{\mathbf{x}}, \mathbf{c}_k)} \\ &= \gamma \left( 1 + \frac{(1-\alpha)}{\alpha} \frac{\sum_{F \in \mathcal{F}} \min_{k \in F} f(\hat{\mathbf{x}}, \mathbf{c}_k)}{\sum_{F \in \mathcal{F}} \max_{k \in F} f(\hat{\mathbf{x}}, \mathbf{c}_k)} \right) - 1. \end{align*}$$

Thus, we get

$$H_{\alpha}(\hat{\mathbf{x}}) \leq \gamma \left( 1 + \frac{(1-\alpha)}{\alpha} \frac{\sum_{F \in \mathcal{F}} \min_{k \in F} f(\hat{\mathbf{x}}, \mathbf{c}_k)}{\sum_{F \in \mathcal{F}} \max_{k \in F} f(\hat{\mathbf{x}}, \mathbf{c}_k)} \right) H_{\alpha}(\mathbf{x}^*),$$

where $\frac{\sum_{F \in \mathcal{F}} \min_{k \in F} f(\hat{\mathbf{x}}, \mathbf{c}_k)}{\sum_{F \in \mathcal{F}} \max_{k \in F} f(\hat{\mathbf{x}}, \mathbf{c}_k)} \in [0, 1]$. $\square$
Observe that (13) is a special case of the mixed-uncertainty robust optimization problem discussed in [9], where uncertainty sets are given, and we would like to solve

$$ \min_{\mathbf{x} \in \mathcal{X}} \sum_{F \in \mathcal{F}} m(F) \max_{k \in F} f(\mathbf{x}, \mathbf{c}_k), $$

In [9] it has been shown that solving the nominal problem $\min_{\mathbf{x} \in \mathcal{X}} f(\mathbf{x}, \hat{\mathbf{c}})$ with the cost vector $\hat{\mathbf{c}} = \sum_{F \in \mathcal{F}} m(F) \frac{1}{|F|} \sum_{k \in F} \mathbf{c}_k$, for linear cost functions $f$, gives a $z(\mathcal{F})$-approximation to (13). In combination with Theorem 4, this allows us to derive approximation algorithms for a wide range of the ROBF problems if the underlying deterministic problem (1) is polynomially solvable, in particular for a wide class of network problems (see [1] for a comprehensive review). Note also that in most cases, $\gamma = 1$ if (13) is a convex problem (in particular linear programming one).

## 7. Extension to possibilistic optimization

In this section, we will show how to use possibility theory (see, e.g., [11]) to extend the model of uncertainty described in Section 3. We will follow the reasoning of [8]. In the uncertainty representation used in Section 3, each focal set $F \in \mathcal{F}$ can be described by a characteristic function $\pi_F : [K] \to \{0, 1\}$ such that $\pi_F(u) = 1$ if $u \in F$ and $\pi_F(u) = 0$ if $u \notin F$. We can interpret $\pi_F$ as a possibility distribution for evidence $F$, i.e. scenarios whose indices are in $F$ are possible, whereas scenarios with indices not in $F$ are impossible. The possibility distribution $\pi_F$ induces the following possibility and necessity measures on $2^{[K]}$:

$$ \Pi_F(A) = \max_{u \in A} \pi_F(u) \qquad (21) $$

$$ N_F(A) = 1 - \Pi_F(A^c) = \min_{u \notin A} (1 - \pi_F(u)), \qquad (22) $$

where the set $A^c = [K] \setminus A$ is the complement of $A$. The belief function (5) can be alternatively represented as follows:

$$ \text{Bel}(A) = \sum_{F \in \mathcal{F}} m(F) N_F(A), $$

which easily follows from the fact that $N_F(A) = 1$ if $F \subseteq A$ and $N_F(A) = 0$, otherwise.

A generalization of the model (see [8]) consists in allowing evidence to be represented by a fuzzy set $\tilde{F}$ in $[K]$ with the membership function $\mu_{\tilde{F}} : [K] \to [0, 1]$. We only assume that $\tilde{F}$ is a normal fuzzy set, i.e. $\mu_{\tilde{F}}(u) = 1$ for some $u \in [K]$. Now any possibility distribution $\pi_{\tilde{F}}$, $\pi_{\tilde{F}} = \mu_{\tilde{F}}$, can be used to characterize the evidence $\tilde{F}$ and $\tilde{\mathcal{F}} = \{\tilde{F}_1, \dots, \tilde{F}_l\}$ is a family of fuzzy sets in $[K]$ with membership functions $\mu_{\tilde{F}_i}$ (possibility distributions $\pi_{\tilde{F}_i}$), $i \in [l]$. A mass $m(\tilde{F}_i) \in (0, 1]$ is specified for each fuzzy focal set $\tilde{F}_i$ and is such that $\sum_{i \in [l]} m(\tilde{F}_i) = 1$. The family $\tilde{\mathcal{F}}$ with the mass function $m$ can be seen as a random fuzzy set.

We can provide the following interpretation of this uncertainty representation. The fuzzy focal set $\tilde{F}_i$ is some evidence that the decision-maker knows about scenarios in $\mathcal{U}$ (it represents a knowledge possessed in the scenario set). As previously, the mass $m(\tilde{F}_i)$ supports this evidence, and the mass function $m$ can be interpreted as a subjective probability distribution in $\tilde{\mathcal{F}}$. For a detailed interpretation of the model, we refer the reader to [8]. We can now extend the definition of the belief function in the following way:

$$ \text{Bel}(A) = \sum_{\tilde{F} \in \tilde{\mathcal{F}}} m(\tilde{F}) N_{\tilde{F}}(A) = \sum_{\tilde{F} \in \tilde{\mathcal{F}}} m(\tilde{F}) \min_{u \in A} (1 - \pi_{\tilde{F}}(u)). \qquad (23) $$

Hence, the belief of $A$ can be seen as the expected necessity of $A$ [8].

As previously, $\mathcal{P}(m) \subseteq [0, 1]^K$ is the set of all probability distributions in $[K]$ compatible with Bel, i.e. $\mathcal{P}(A) \ge \text{Bel}(A)$ for each $A \subseteq [K]$. Set $\mathcal{P}(m)$ is characterized by the system of linear constraints (7) with the belief function defined as (23). As Bel($A$) is constant for each $A \subseteq [K]$, we conclude that $\mathcal{P}(m)$ is a polytope in $[0, 1]^K$. The next proposition shows that there is at least one probability distribution in $\mathcal{P}(m)$.

**Proposition 4.** The set $\mathcal{P}(m)$ is nonempty.

**Proof.** See Appendix B. □

In the following, we will show that the possibilistic model of uncertainty can be reduced to the model described in Section 3. Therefore, all the results shown in Sections 5 and 6 also apply to it. Consider a fuzzy set $\tilde{F}$ in $[K]$. Let $(\alpha_1, \dots, \alpha_f)$, $0 < \alpha_1 < \dots < \alpha_f = 1$, be an ordered sequence of the distinct positive values of $\pi_{\tilde{F}}(1), \dots, \pi_{\tilde{F}}(K)$. The sets, called $\alpha_i$-cuts or $\alpha_i$-level sets
$$ \tilde{F}^{[\alpha_i]} = \{k \in [K] : \pi_{\tilde{F}}(k) \ge \alpha_i\} $$

form a family of nested sets

$$ \tilde{F}^{[\alpha_1]} \supset \tilde{F}^{[\alpha_2]} \supset \dots \supset \tilde{F}^{[\alpha_f]} $$

Define $m_{\tilde{F}}(\tilde{F}^{[\alpha_1]}) = \alpha_1$, $m_{\tilde{F}}(\tilde{F}^{[\alpha_i]}) = \alpha_i - \alpha_{i-1}$ for $i = 2, \dots, f$ and $m_{\tilde{F}}(B) = 0$ for all the remaining subsets of $[K]$. Observe that

$$ \sum_{A \subseteq [K]} m_{\tilde{F}}(A) = \sum_{i=1}^{f} m_{\tilde{F}}(\tilde{F}^{[\alpha_i]}) = 1. \qquad (24) $$

**Proposition 5.** For any subset $A \subseteq [K]$ the following equation is true:

$$ N_{\tilde{F}}(A) = \sum_{B \subseteq A} m_{\tilde{F}}(B). \qquad (25) $$

**Proof.** If $\tilde{F}^{[\alpha_i]} \not\subseteq A$ for each $i \in [f]$, then $N_{\tilde{F}}(A) = \min_{u \notin A}(1 - \pi_{\tilde{F}}(u)) = 0$ and (25) is true. If $\tilde{F}^{[\alpha_i]} \subseteq A$ for each $i \in [f]$, then $N_{\tilde{F}}(A) = \min_{u \notin A}(1 - \pi_{\tilde{F}}(u)) = 1$ and (25) is also true. Let $j = 2, \dots, f$ be the smallest number such that $\tilde{F}^{[\alpha_j]} \subseteq A$. Then,

$$ N_{\tilde{F}}(A) = \min_{u \notin A} (1 - \pi_{\tilde{F}}(u)) = 1 - \alpha_{j-1}. $$

On the other hand,

$$ \sum_{B \subseteq A} m_{\tilde{F}}(B) = \sum_{i=j}^{f} m_{\tilde{F}}(\tilde{F}^{[\alpha_i]}) = (1 - \alpha_{f-1}) + (\alpha_{f-1} - \alpha_{f-2}) + \dots + (\alpha_j - \alpha_{j-1}) = 1 - \alpha_{j-1}, $$

which implies (25). □

Using Proposition 5 we can represent (23) in the following way:

$$ \mathrm{Bel}(A) = \sum_{\tilde{F} \in \tilde{\mathcal{F}}} m(\tilde{F}) \mathrm{N}_{\tilde{F}}(A) = \sum_{\tilde{F} \in \tilde{\mathcal{F}}} m(\tilde{F}) \sum_{B \subseteq A} m_{\tilde{F}}(B) = \sum_{B \subseteq A} \sum_{\tilde{F} \in \tilde{\mathcal{F}}} m(\tilde{F}) m_{\tilde{F}}(B). \qquad (26) $$

Define

$$ m'(A) = \sum_{\tilde{F} \in \tilde{\mathcal{F}}} m(\tilde{F}) m_{\tilde{F}}(A), \quad A \subseteq [K]. $$

Using (24) and the fact that $m$ is a mass function in $\tilde{\mathcal{F}}$, we conclude that $m'(A) \ge 0$ for any $A \subseteq [K]$ and $\sum_{A \subseteq [K]} m'(A) = 1$. Therefore, $m'$ is a mass function defined in $2^{[K]}$ and the belief function (26) can be equivalently defined as

$$ \mathrm{Bel}(A) = \sum_{B \subseteq A} m'(B). $$

This allows us to use all the results from Sections 5 and 6 for the possibilistic uncertainty model. Notice also that the number of focal sets in $\tilde{\mathcal{F}}'$ for the new mass function $m'$ is at most $K\ell$, so it is polynomially bounded by $K$ and $\ell$. An example illustrating this model of uncertainty will be shown in the next section.

## 8. Numerical example

In this section, we will show a small numerical example that will illustrate the ROBF problem under the possibilistic model of uncertainty. Consider an instance of the shortest path problem shown in Fig. 1.

The set $X$ contains the characteristic vectors of 3 possible paths from $s$ to $t$ in $G$. There are 6 cost scenarios listed in Fig. 1 and the cost of the path described by $x$ under scenario $c_k$ equals $c_k^T x$. In the absence of additional evidence, we can seek a path minimizing the cost in the worst case. By solving the minmax problem we get the path $\{a_2, a_5\}$ (corresponding to solution $x_2 = x_5 = 1$, $x_1 = x_3 = x_4 = 0$), which has the largest cost equal to 11 under scenario $c_1$. Taking into account a more optimistic point of view, we can minimize the traditional Hurwicz criterion (3) for some $\alpha \in [0, 1]$. It is easy to verify that the path $\{a_2, a_5\}$ is optimal for $\alpha \in [0.25, 1]$. For $\alpha \in [0, 0.25)$ the path $\{a_1, a_3, a_5\}$ becomes optimal.

Assume now that we have some additional evidence about the problem, specified as two fuzzy sets $\tilde{F}_1$ and $\tilde{F}_2$ in $[K]$, with masses $m(\tilde{F}_1) = 0.4$, $m(\tilde{F}_2) = 0.6$, respectively. These fuzzy sets are shown in Fig. 2.
<figure><img src="image_4.png" /><figcaption>Fig. 1. An instance of the shortest path problem with $K = 6$ cost scenarios.</figcaption></figure>

<figure><img src="image_5.png" /><figcaption>Fig. 2. Fuzzy sets $\tilde{F}_1$ and $\tilde{F}_2$ with $\pi_{\tilde{F}_1}(1) = 0.2$, $\pi_{\tilde{F}_1}(2) = 0.5$, $\pi_{\tilde{F}_1}(3) = 1$, $\pi_{\tilde{F}_1}(4) = 0.7$, $\pi_{\tilde{F}_1}(5) = 0.9$, $\pi_{\tilde{F}_1}(6) = 0.3$ (filled circles) and $\pi_{\tilde{F}_2}(1) = 0$, $\pi_{\tilde{F}_2}(2) = 0.3$, $\pi_{\tilde{F}_2}(3) = 0.4$, $\pi_{\tilde{F}_2}(4) = 1$, $\pi_{\tilde{F}_2}(5) = 0.7$, $\pi_{\tilde{F}_2}(6) = 0.4$ (blank circles).</figcaption></figure>

<table><caption>Table 2
The mass function $m'(A)$ for $\tilde{F} = \{\tilde{F}_1, \tilde{F}_2\}$.</caption><thead><tr><th>A</th><th>m<sub>tilde{F}_1</sub>(A)</th><th>m<sub>tilde{F}_2</sub>(A)</th><th>m'(A)</th></tr></thead><tbody><tr><td>{1, 2, 3, 4, 5, 6}</td><td>0.2</td><td>0</td><td>0.08</td></tr><tr><td>{2, 3, 4, 5, 6}</td><td>0.1</td><td>0.3</td><td>0.22</td></tr><tr><td>{2, 3, 4, 5}</td><td>0.2</td><td>0</td><td>0.08</td></tr><tr><td>{3, 4, 5}</td><td>0.2</td><td>0</td><td>0.08</td></tr><tr><td>{3, 5}</td><td>0.2</td><td>0</td><td>0.08</td></tr><tr><td>{3}</td><td>0.1</td><td>0</td><td>0.04</td></tr><tr><td>{3, 4, 5, 6}</td><td>0</td><td>0.1</td><td>0.06</td></tr><tr><td>{4, 5}</td><td>0</td><td>0.3</td><td>0.18</td></tr><tr><td>{4}</td><td>0</td><td>0.3</td><td>0.18</td></tr></tbody></table>

Let us first construct the mass $m' : 2^{[K]} \to [0, 1]$, using the results from Section 7. For the fuzzy set $\tilde{F}_1$, we form the sequence $0.2 < 0.3 < 0.5 < 0.7 < 0.9 < 1$, which yields $\tilde{F}^{[0.2]} = \{1, 2, 3, 4, 5, 6\}$, $\tilde{F}^{[0.3]} = \{2, 3, 4, 5, 6\}$, $\tilde{F}^{[0.5]} = \{2, 3, 4, 5\}$, $\tilde{F}^{[0.7]} = \{3, 4, 5\}$, $\tilde{F}^{[0.9]} = \{3, 5\}$, $\tilde{F}^{[1]} = \{3\}$. For the fuzzy set $\tilde{F}_2$ the corresponding sequence is $0.3 < 0.4 < 0.7 < 1$ and $\tilde{F}^{[0.3]} = \{2, 3, 4, 5, 6\}$, $\tilde{F}^{[0.4]} = \{3, 4, 5, 6\}$, $\tilde{F}^{[0.7]} = \{4, 5\}$ and $\tilde{F}^{[1]} = \{4\}$.

The mass function $m'$ for $\tilde{F}$ is shown in Table 2. Recall that $m'(A) = 0.4 \cdot m_{\tilde{F}_1}(A) + 0.6 \cdot m_{\tilde{F}_2}(A)$ for each $A \subseteq [K]$. If $B \subseteq [K]$ is not listed in the first column of Table 2, then $m'(B) = 0$.

The refined model of uncertainty provides us some information about the probabilities of scenario realizations. For example, the probability that scenario $c_1$ will occur is now at most 0.08. Indeed, the inequality $p_2 + \dots + p_6 \ge \text{Bel}(\{2, 3, 4, 5, 6\}) = 0.92$ implies $p_1 \le 0.08$. Let us choose first $\alpha = 1$. Solving the model (13) we get the path $\{a_1, a_4\}$. The worst probability distribution in $\mathcal{P}(m')$ for this path is $\bar{p} = (0.08, 0, 0.04, 0.18, 0.7, 0)$, which yields the worst expected value equal to 6.3. This worst probability distribution can be computed by using (28) and (30) (see Appendix A). If we choose $\alpha = 0.4$, then the optimal path becomes $\{a_2, a_5\}$. The worst probability distribution for this path is also $\bar{p} = (0.08, 0, 0.04, 0.18, 0.7, 0)$ and the best equals to $\underline{p} = (0, 0, 0.12, 0.88, 0, 0)$. The value of $H_{0.4}(\mathbf{x}) = 5.344$, where $\mathbf{x}$ is the characteristic vector of $\{a_2, a_5\}$, is the expected cost of $\mathbf{x}$ under the probability distribution $\hat{p} = 0.4 \cdot \bar{p} + 0.6 \cdot \underline{p} = (0.032, 0, 0.088, 0.6, 0.28, 0) \in \mathcal{P}(m')$.
## 9. Conclusions

In this paper, we discussed a new approach to optimization under uncertainty in the objective function. We assumed that the uncertainty is described by a belief function based on masses assigned to subsets of scenarios. The masses represent subjective probabilities of the respective events (subsets of scenarios) and can be provided by the decision-maker to take into account additional knowledge about the problem parameters. The belief function induces a set of probability distributions such that the probability of each event is lower bounded by its belief. We used the generalized Hurwicz criterion to compute a solution. This criterion allows us to establish a trade-off between the worst-case and the best-case performance of solutions over all probability distributions compatible with the belief function. The worst-case performance is consistent with distributionally robust optimization, which has attracted considerable attention recently. For some specific choices of the mass function, our approach leads to optimizing the OWA criterion, which has been well studied on its own.

In this paper, we identified a special case of the uncertain linear programming problem, which is NP-hard and also hard to approximate. On the other hand, we described some cases of the problem which can be solved or approximated in polynomial time. Finally, we extended our setting using fuzzy sets with a possibilistic interpretation. In this case, scenarios belong to focal sets with some degrees between zero and one. We showed that the fuzzy case can be reduced in polynomial time to the previous, traditional one, and all the results for the traditional case can still be applied.

## Declaration of competing interest

The authors declare the following financial interests/personal relationships which may be considered as potential competing interests:

Adam Kasperski reports financial support was provided by National Science Centre Poland. Pawel Zielinski reports financial support was provided by National Science Centre Poland. Marc Goerigk reports financial support was provided by Deutsche Forschungsgemeinschaft. Romain Guillaume reports financial support was provided by AI Interdisciplinary Institute ANITI.

## Data availability

No data was used for the research described in the article.

## Acknowledgements

Marc Goerigk was partially supported by the Deutsche Forschungsgemeinschaft (DFG), grant GO 2069/2-1. Romain Guillaume has benefitted from the AI Interdisciplinary Institute ANITI funding. ANITI is funded by the French Investing for the Future – PIA3 program under the Grant agreement ANR-19-PI3A-0004. Adam Kasperski and Paweł Zieliński were supported by the National Science Centre, Poland, grant 2022/45/B/HS4/00355.

## Appendix A. Proof of equations (8) and (9)

**Proof.** Set $\mathcal{P}(m)$, described by (7), contains exactly the elements $\mathbf{p}$ which can be obtained as follows (see Section 3 in [7] and also [6]). Let $a(k, F) \ge 0, F \in \mathcal{F}, k \in F$, be nonnegative numbers satisfying the following system of equations:

$$ \sum_{k \in F} a(k, F) = m(F), \quad F \in \mathcal{F}. \qquad (27) $$

Hence $a(k, F)$ can be interpreted as a part of the mass $m(F)$ of the focal set $F \in \mathcal{F}$ assigned to scenario $k \in [K]$. Define vector $\mathbf{p} \in [0, 1]^K$ as follows:

$$ p_k = \sum_{\{F \in \mathcal{F}: k \in F\}} a(k, F), \quad k \in [K]. \qquad (28) $$

Given a solution $\mathbf{x} \in \mathcal{X}$, consider the optimization problem

$$ \max \quad \mathbb{E}_{\mathbf{p}}[f(\mathbf{x}, \tilde{\mathbf{c}})] = \sum_{k \in [K]} p_k f(\mathbf{x}, \mathbf{c}_k) \qquad (29) \\ \mathbf{p} \in \mathcal{P}(m). $$

Substituting (27) and (28) in (29), we get the following linear program:

$$ \begin{aligned} \max \quad & \sum_{k \in [K]} \sum_{F \in \mathcal{F}: k \in F} a(k, F) f(\mathbf{x}, \mathbf{c}_k) \\ & \sum_{k \in F} a(k, F) = m(F) \quad F \in \mathcal{F} \\ & a(k, F) \ge 0 \quad F \in \mathcal{F}, k \in F \end{aligned} $$
After exchanging the summation in the objective function, we get the equivalent formulation:

$$ 
\begin{aligned}
\max & \sum_{F \in \mathcal{F}} \sum_{k \in F} a(k, F) f(\mathbf{x}, \mathbf{c}_k) \\
& \sum_{k \in F} a(k, F) = m(F) \quad F \in \mathcal{F} \\
& a(k, F) \ge 0 \quad F \in \mathcal{F}, k \in F
\end{aligned} 
\qquad (30) $$

It is easy to verify that in an optimal solution to (30), one can fix $a(k^*, F) = m(F)$ for $k^* = \arg \max_{k \in F} f(\mathbf{x}, \mathbf{c}_k)$ and $a(k, F) = 0$ for $k \in F \setminus \{k^*\}$ for each $F \in \mathcal{F}$. Hence, (30) is equivalent to the right-hand side of (8). The proof of (9) is analogous. □

## Appendix B. Proof of Proposition 4

**Proof.** We show first that the necessity measure is supermodular, i.e.

$$ N(A \cup B) + N(A \cap B) \ge N(A) + N(B) $$

for any $A, B \subseteq [K]$. Indeed $N(A \cup B) \ge \max\{N(A), N(B)\}$, since $1 - \max_{u \in (A \cup B)^c} \pi(u) \ge 1 - \max_{u \in A^c} \pi(u)$ and $1 - \max_{u \in (A \cup B)^c} \pi(u) \ge 1 - \max_{u \in B^c} \pi(u)$. Hence, $N(A \cup B) + N(A \cap B) \ge \max\{N(A), N(B)\} + \min\{N(A), N(B)\} = N(A) + N(B)$. The equation $N(A \cap B) = \min\{N(A), N(B)\}$ follows from the minitivity axiom which the necessity measure satisfies [11]. The supermodularity can be stated equivalently (see, e.g., [10]) as

$$ N(A \cup \{i\}) - N(A) \ge N(B \cup \{i\}) - N(B) \qquad (31) $$

for each $B \subseteq A$ and $i \notin A$. Now it is easy to see that the belief function Bel is also supermodular, as $\text{Bel}(A \cup \{i\}) - \text{Bel}(A) \ge \text{Bel}(B \cup \{i\}) - \text{Bel}(B)$ for each $B \subseteq A$ and $i \notin A$. This inequality follows immediately from (31) and the fact that the belief function is a conic (nonnegative) linear combination of necessity measures. The constraints (7) for $\mathcal{P}(m)$ describe a core of a convex game with the player set $[K]$ and characteristic function Bel. The core (and thus $\mathcal{P}(m)$) of such games is nonempty (see, e.g., [21]). □

## References

[1] R.K. Ahuja, T.L. Magnanti, J.B. Orlin, Network Flows: Theory, Algorithms, and Applications, Prentice Hall, Englewood Cliffs, New Jersey, 1993.

[2] A. Ben-Tal, L. El Ghaoui, A. Nemirovski, Robust Optimization, Princeton Series in Applied Mathematics, Princeton University Press, Princeton, NJ, 2009.

[3] S. Boyd, L. Vandenberghe, Convex Optimization, Cambridge University Press, 2004.

[4] A.B. Chassein, M. Goerigk, Alternative formulations for the ordered weighted averaging objective, Inf. Process. Lett. 115 (2015) 604–608.

[5] E. Delage, Y. Ye, Distributionally robust optimization under moment uncertainty with application to data-deriven problems, Oper. Res. 58 (2010) 595–612.

[6] A. Dempster, Upper and lower probabilities induced by a multivalued mapping, Ann. Math. Stat. 38 (1967) 325–339.

[7] T. Denoeux, Decision-making with belief functions: a review, Int. J. Approx. Reason. 109 (2019) 87–110.

[8] T. Denoeux, Belief functions induced by random fuzzy sets: a general framework for representing uncertain and fuzzy evidence, Fuzzy Sets Syst. 424 (2021) 63–91.

[9] T. Dokka, M. Goerigk, R. Roy, Mixed uncertainty sets for robust combinatorial optimization, Optim. Lett. 14 (6) (2020) 1323–1337.

[10] T. Driessen, Cooperative Games, Solutions and Applications, Kluwer Academic Publishers, 1988.

[11] D. Dubois, H. Prade, Possibility Theory: an Approach to Computerized Processing of Uncertainty, Plenum Press, New York, 1988.

[12] D. Dubois, H. Prade, Consonant approximations of belief functions, Int. J. Approx. Reason. 4 (5–6) (1990) 419–449.

[13] R. Guillaume, A. Kasperski, P. Zieliński, Robust optimization with scenarios using random fuzzy sets, in: 2021 IEEE International Conference on Fuzzy Systems (FUZZ-IEEE), 2021, pp. 1–6.

[14] R. Guillaume, A. Kasperski, P. Zieliński, Robust optimization with scenarios using belief functions, in: N. Trautmann, M. Gnägi (Eds.), Operations Research Proceedings 2021, Springer International Publishing, Cham, 2022, pp. 114–119.

[15] A. Kasperski, P. Zieliński, Combinatorial optimization problems with uncertain costs and the OWA criterion, Theor. Comput. Sci. 565 (2015) 102–112.

[16] A. Kasperski, P. Zieliński, Robust discrete optimization under discrete and interval uncertainty: a survey, in: Robustness Analysis in Decision Aiding, Optimization, and Analytics, Springer-Verlag, 2016, pp. 113–143.

[17] R. Kohli, R. Krishnamurti, P. Mirchandani, The minimum satisfiability problem, SIAM J. Discrete Math. 7 (1994) 275–283.

[18] P. Kouvelis, G. Yu, Robust Discrete Optimization and Its Applications, Kluwer Academic Publishers, 1997.

[19] W. Oglyczak, Robust decisions under risk for imprecise probabilities, in: Y. Ermoliev, M. Makowski, K. Marti (Eds.), Managing Safety of Heterogeneous Systems, Springer-Verlag, 2012, pp. 51–66.

[20] W. Oglyczak, P. Olender, On MILP models for the OWA optimization, J. Telecommun. Inf. Technol. 2 (2012) 5–12.

[21] H.E. Scarf, The core of an n person game, Econometrica 35 (1967) 50–69.

[22] G. Shafer, A Mathematical Theory of Evidence, Princeton Univ. Press, 1976.

[23] W. Wiesemann, D. Kuhn, M. Sim, Distributionally robust convex optimization, Oper. Res. 62 (2014) 1358–1376.

[24] R.R. Yager, On ordered weighted averaging aggregation operators in multi-criteria decision making, IEEE Trans. Syst. Man Cybern. 18 (1988) 183–190.