# Normal cones corresponding to credal sets of lower probabilities

Damjan Škulj
University of Ljubljana  Faculty of Social Sciences
Kardeljeva pl. 5  SI-1000 Ljubljana  Slovenia
<EMAIL_ADDRESS>
###### Abstract

Credal sets are one of the most important models describing probabilistic
uncertainty. They usually arise as convex sets of probabilistic models
compatible with judgments provided in terms of coherent lower previsions or
more specific models such as lower probabilities or probability intervals. In
finite spaces, credal sets most often have the form of convex polyhedra. Many
properties of convex polyhedra can be derived from their normal cones that
form polyhedral complexes called normal fans. We analyze the properties of
normal cones corresponding to credal sets of lower probabilities. For two
important classes of lower probabilities, 2-monotone lower probabilities and
probability intervals, we provide a detailed description of the normal fan
structure. These structures are related to the structure of extreme points of
the credal sets. To obtain our main results, we provide some general results
on triangulated normal fans of convex polyhedra and their adjacency structure.

Keywords. normal cone, credal set, convex polyhedron, extreme point, imprecise
probability, lower probability

2020 Mathematics Subject Classification: 60A86, 52B11

##  1 Introduction

Applications of mathematical models involving probabilities often suffer from
insufficient evidence to support a single model. Sticking with classical
models consequently requires imposing unwarranted assumptions, leading to
unreliable results. The lack of evidence in probabilistic models is frequently
described as uncertainty or imprecision. While uncertainty can be understood
as a general concept tackled via probabilistic models, imprecision is the term
that more explicitly describes situations that no particular probabilistic
model can adequately describe. The theories of imprecise probabilities have
been developed to provide methods capable of dealing with such probabilistic
models and produce the outputs where the imprecision is faithfully reflected.
The probabilistic imprecision is in most cases described with sets of
probability distributions, consistent with the available information, instead
of a particular precise distribution. The sets are represented by various
types of constraints, ranging from the most general lower and upper previsions
to more specific lower and upper probabilities, probability intervals,
$p$-boxes, belief and possibility functions, and other models.

In recent years, methods of imprecise probabilities [3, 4, 37] have been
applied to various areas of probabilistic modelling, such as stochastic
processes [10, 52], game theory [26, 30], reliability theory [8, 21, 31, 49,
59], decision theory [19, 28, 46], financial risk theory [36, 51], computer
science [1, 38, 48, 50], copulas [14, 32, 33, 34, 60] and others.

The multiple probabilistic models encompassed by an imprecise model most often
form a set that is described via a finite number of constraints that may arise
directly from the pieces of available information. If the constraints are
linear, they result in convex sets, named _credal sets_. Indeed, all the
models mentioned above define convex credal sets. Convexity of the models
presents an advantage, as they allow efficient computations via implementing
of linear programming techniques.

Beside optimization with respect to credal sets, understanding of the related
structures is often important to understand the models. Thus, analysis of the
extreme points of credal sets of various models is frequently a subject of
interest [2, 25, 27, 57]. Nature and behaviour of the convex sets in extreme
points and their neighbourhoods is important in the cases of dynamical
systems, such as stochastic processes. These processes typically require
solving multiple optimization tasks, where the solution at earlier time steps
determine the initial conditions for the later ones. This is important in the
discrete time models [10, 52, 42], and even more in the continuous time [9,
22, 53, 54]. The latter models would in principle require optimization with
respect to credal set in every point of an interval, which is unfeasible.
Discretization methods are then used for calculating approximate solutions
[15, 22]. As an alternative to discretization, methods based on normal cones
were proposed [53, 54, 55]. Their advantage over discretization methods is
that in case a solution within a time interval remains in a single normal
cone, the process in that interval is linear. The application of linearity
within normal cones is a consequence of a general principle of normal cone
additivity that we explicitly state in Proposition 6. Another well-known
example is the so-called comonotonic additivity of lower expectations with
respect to 2-monotone lower probabilities [13, 40]. Another application of
normal cones in the theory of imprecise probabilities was proposed in [43],
where a method based on normal cones is developed to estimate the maximal
distance between a credal set and its approximation based on a finite number
of constraints.

The goal of the present article is to analyze the structure of complexes
comprising of normal cones, also called normal fans, corresponding to credal
sets generated by coherent lower probabilities. We propose several general
results, and then analyze in detail normal cones corresponding to 2-monotone
lower probabilities and probability intervals. The approach with normal cones
allows characterization of extreme points of the credal sets. In the case of
2-monotone lower probabilities, characterization previously known from the
literature is related with normal cones. However, in the case of probability
intervals, whose credal sets are more complex and diverse, our approach with
normal cones proves very useful, allowing a detailed analysis of their
structure.

The article has the following structure. In the subsequent section we review
the underlying theory of convex polyhedra and their normal cones. We are
primarily concerned with the minimal cones that may correspond to extreme
points. These are characterized in abstract terms of relations between support
vectors, which do not depend on particular realization of a convex polyhedron.
In Section 2.2, the abstract structure of all possible minimal cones is
endowed by an adjacency relation, allowing a graph theoretical interpretation.
In Section 3, essential elements of the models of imprecise probabilities are
introduced with a specific focus to finitely generated coherent lower
previsions and their credal sets. In Section 4 normal cones of credal sets of
lower probabilities are introduced and studied in details in the case of
2-monotone lower probabilities in Section 4.1. Finally, in Section 5, normal
cones of credal sets corresponding to probability intervals are analyzed.

##  2 Normal cones

###  2.1 Normal cones and normal fans of convex polyhedra

We first give some general elements from the theory of convex sets. Most of
the notation and results are taken from [16, 17, 18, 39, 61].

Let $\mathbb{R}^{n}$ be a finite dimensional vector space equipped with the
standard scalar product, which we denote by $xy$ or sometimes $x\cdot y$ for
any pair of vectors $x,y\in\mathbb{R}^{n}$. A _convex polyhedron_ in
$\mathbb{R}^{n}$ is a bounded convex set $\mathcal{C}$ with finitely many
extreme points. Equivalently, a convex polyhedron can be represented as an
intersection of a finite number of half spaces of the form
$\\{x\in\mathbb{R}^{n}\colon xf\geqslant b_{f}\\}$, where $f\in\mathbb{R}^{n}$
is a vector and $b_{f}$ a constant. A convex polyhedron can thus be defined as

$\mathcal{C}=\\{x\in\mathbb{R}^{n}\colon xf\geqslant b_{f}\text{ for all
}f\in\mathcal{F}\\},$ (1)

where $\mathcal{F}$ is a given finite collection of vectors and
$\\{b_{f}\colon f\in\mathcal{F}\\}$ a collection of constants. Some of the
inequalities $xf\geqslant b_{f}$ may in fact be equalities. This case,
however, can be unified with the general case by replacing an equality
condition $xf=b_{f}$ with two inequalities, $xf\geqslant b_{f}$ and
$x(-f)\geqslant-b_{f}$. This will allow us to use the simple description (1)
throughout the text.

The set $\mathcal{C}^{\prime}\subseteq\mathcal{C}$ obtained by turning one or
more inequalities $xf\geq b_{f}$ in (1) into an equality $xf=b_{f}$ is then a
_face_ of $\mathcal{C}$. It is also a convex polyhedron of a lower dimension.
A face of $\mathcal{C}$ that is not equal to $\mathcal{C}$ is called a _proper
face_. The set of elements of $\mathcal{C}$ that are not contained in any
proper face is called _relative interior_ of $\mathcal{C}$ and denoted by
$\mathrm{ri}(\mathcal{C})$.

Now take some point $x\in\mathcal{C}$ and define its _normal cone_ to be the
set

$N(\mathcal{C},x)=\\{f\in\mathbb{R}^{n}\colon xf\leqslant yf\text{ for every
}y\in\mathcal{C}\\}.$ (2)

That is, the normal cone of $x$ is the set of all vectors $f$ for which
$x=\arg\min_{y\in\mathcal{C}}yf$. The minimum of the above expression is
usually recognized as a linear programming problem where $\mathcal{C}$ is the
feasible set. Thus the normal cone of $x$ can be understood as the set of all
vectors $f$ such that the objective function $yf$ has an optimal solution in
$x$. It is well-known that only points in the boundary minimize objective
functions, and therefore only normal cones for those elements are non-empty.
Moreover, every objective function is minimized in at least one extreme point.
This implies that the union of the normal cones of extreme points is the
entire space $\mathbb{R}^{n}$. Basic theory of normal cones can be found in
most of the monographs on convex theory. A thorough analysis can also be found
in [23], especially from the point of view of normal fans, that also play an
important role in this article.

Throughout this article we will be concerned with cones generated as non-
negative linear combinations of finite sets of vectors $\mathcal{G}$, denoted
by $\mathrm{cone}(\mathcal{G})$. Thus,

$\mathrm{cone}(\mathcal{G})=\left\\{\sum_{f\in\mathcal{G}}\alpha_{f}f\colon\alpha_{f}\geq
0\text{ for all }f\in\mathcal{G}\right\\}.$ (3)

If a cone is of the form (3), we will simply say that it is _generated_ by
$\mathcal{G}$. A cone consists of its faces and relative interior which is
equal to the set of all strictly positive linear combinations of elements in
$\mathcal{G}$:

$\mathrm{ri}(\mathrm{cone}(\mathcal{G}))=\left\\{\sum_{f\in\mathcal{G}}\alpha_{f}f\colon\alpha_{f}>0\text{
for all }f\in\mathcal{G}\right\\}.$ (4)

The following proposition holds (see [16], Proposition 14.1).

######  Proposition 1.

Let $\mathcal{C}$ be a convex polyhedron represented in the form (1) and
$x\in\mathcal{C}$ a boundary point. Let
$\mathcal{G}(x)=\\{f\in\mathcal{F}\colon xf=b_{f}\\}$. Then

$N(\mathcal{C},x)=\mathrm{cone}(\mathcal{G}(x)).$ (5)

Moreover, if $x$ is an extreme point of $\mathcal{C}$, then $\dim
N(\mathcal{C},x)=n$ (dimension of the vector space).

In the case where $\mathcal{G}$ is linearly independent,
$\mathrm{cone}(\mathcal{G})$ is called a _simplicial cone_ , as the elements
of $\mathcal{G}$ form a simplex. Simplicial cones play a central role in this
paper. In general, a normal cone may not be simplicial, and will therefore be
subdivided into simplicial cone by means of triangulations.

######  Definition 1 ([20]).

A collection $\mathcal{P}$ of polyhedra in $\mathbb{R}^{n}$ is a _polyhedral
complex_ if

  1. (i)

all proper faces of $P\in\mathcal{P}$ are in $\mathcal{P}$;

  2. (ii)

an intersection of any two polyhedra in $\mathcal{P}$ is a face of both.

If the polyhedra in $\mathcal{P}$ are cones, then we have a _conical complex_
or a _fan_.

According to some definitions (see [18]), polyhedral complexes as defined
above are called _embedded_ , and fans are then embedded conical complexes. If
the union of all cones in a fan $\mathcal{P}$ forms the entire
$\mathbb{R}^{n}$, then the fan is called _complete_. A special case of a
complete fan is the collection of all normal cones of a set $\mathcal{C}$,
called _normal fan_ and denoted by
${\mathcal{N}(\mathcal{C})}=\\{N(\mathcal{C},x)\colon x\in\mathcal{C}\\}$.

For our analysis it will be important that all cones in a fan are simplicial,
in which case we are talking about a _simplicial fan_. To transform a
polyhedral complex into a simplicial one, the technique called _triangulation_
is used. It is a special form of _subdivision_. A _subdivision_ of a
polyhedral complex $\mathcal{P}$ is another complex $\mathcal{P}^{\prime}$
such that every polyhedron in $\mathcal{P}$ is a union of polyhedra of
$\mathcal{P}^{\prime}$. If a subdivision is a simplicial complex, then we are
talking about a _triangulation_ of $\mathcal{P}$. It is known that every
polyhedral complex has a triangulation, and specifically, every fan has a
triangulation. More precisely, the following theorem holds.

######  Theorem 1 ([18], Theorem 1.54).

Let $\mathcal{P}$ be a conical complex and $\mathcal{F}\subset|\mathcal{P}|$,
where $|\mathcal{P}|$ is the union of the cones in $\mathcal{P}$, be a finite
set of non-zero vectors such that $\mathcal{F}\cap C$ generates $C$ for every
$C\in\mathcal{P}$. Then there exists a triangulation $\mathcal{T}$ of
$\mathcal{P}$ such that $\mathrm{cone}(\\{f\\})$, for $f\in\mathcal{F}$, are
exactly the 1-dimensional faces of the elements of $\mathcal{T}$.

In our case we will need triangulations whose 1-dimensional faces are exactly
the elements of $\mathcal{F}$, where $\mathcal{F}$ is a set of vectors
generating $\mathcal{C}$ (see (1)).

######  Corollary 1.

Let $\mathcal{C}$ be a convex polyhedron of the form (1), where $\mathcal{F}$
is a given finite set of vectors in $\mathbb{R}^{n}$. Then a conical complex
$\mathcal{T}$ exists such that for every $C_{T}\in\mathcal{T}$ it holds that
it is contained in a single normal cone $C\in\mathcal{C}$ and is generated by
a linearly independent set $\mathcal{G}\subset\mathcal{F}$.

###### Proof.

Let ${\mathcal{N}(\mathcal{C})}$ be the normal fan of $\mathcal{C}$. By
Proposition 1, every $C\in{\mathcal{N}(\mathcal{C})}$ is generated by
$\mathcal{F}\cap C$, whence by Theorem 1, a triangulation $\mathcal{T}$ of
${\mathcal{N}(\mathcal{C})}$ exists such that $\mathrm{cone}(\\{f\\})$ are
exactly the 1-dimensional faces of $\mathcal{T}$. It follows by the definition
of triangulation that every cone $C_{T}\in\mathcal{T}$ is a simplicial cone,
whose 1-dimensional faces are of the form $\mathrm{cone}(\\{f\\})$. Further,
such a simplicial cone is then generated by the linearly independent set
$\mathcal{G}=\\{f\colon\mathrm{cone}(\\{f\\})\text{ is a face of }C_{T}\\}$.
Since $\mathcal{T}$ is a triangulation, every such $C_{T}$ is a subset of some
normal cone $C\in{\mathcal{N}(\mathcal{C})}$. ∎

A triangulation $\mathcal{T}$ of a normal fan ${\mathcal{N}(\mathcal{C})}$ is
also a fan and will be called _complete normal simplicial fan_. Note that the
elements of a complete fan cover entire $\mathbb{R}^{n}$. In addition to
requiring that $\mathcal{T}$ is a triangulation, we also require that all
elements of $\mathcal{F}$ are its 1-dimensional faces. That is, that no
$f\in\mathcal{F}$ is in relative interior of some $C_{T}\in\mathcal{T}$. A
characterization of the elements of complete simplicial fans follows.

######  Proposition 2.

Let $\mathrm{cone}(\mathcal{G})$ be an element of a complete normal simplicial
fan. Then

  1. (i)

$\mathcal{G}$ is linearly independent;

  2. (ii)

for every $f\in\mathcal{F}\backslash\mathcal{G}$ we have that
$f\not\in\mathrm{cone}(\mathcal{G})$;

  3. (iii)

if $|\mathcal{G}|=\dim\mathbb{R}^{n}$, then a convex set $\mathcal{C}$ exists
such that $\mathrm{cone}(\mathcal{G})$ is its normal cone in an extreme point;

  4. (iv)

a convex set $\mathcal{C}$ exists such that $\mathrm{cone}(\mathcal{G})$ is
its normal cone.

###### Proof.

While (i) and (ii) are direct consequences of the definitions, we only prove
(iii). Take some vector $x\in\mathbb{R}^{n}$ and set $b_{f}=xf$ for every
$f\in\mathcal{G}$ and $b_{f^{\prime}}=xf^{\prime}-1$. for
$f^{\prime}\in\mathcal{F}\backslash\mathcal{G}$. The set
$\mathcal{C}=\\{y\colon yf\geq b_{f},y\in\mathbb{R}^{n},f\in\mathcal{F}\\}$ is
clearly a convex subset of $\mathbb{R}^{n}$. By the definition, $xf\geq b_{f}$
for all $f\in\mathcal{F}$, whence $x\in\mathcal{C}$. To see that $x$ is an
extreme point, suppose it were a convex combination of two other points in
$\mathcal{C}$, say $u$ and $v$. By the construction, $uf=vf=b_{f}$ for every
$f\in\mathcal{G}$. But the corresponding linear system has full rank and
therefore $x$ is its unique solution, whence $u=v=x$. Also by construction,
$f\in\mathcal{G}$ are the only vectors in $\mathcal{F}$ that lie in
$N(\mathcal{C},x)$, whence by Proposition 1,
$N(\mathcal{C},x)=\mathrm{cone}(\mathcal{G})$, as claimed.

(iv). A linearly independent $\mathcal{G}$ can be completed to a basis
$\mathcal{G}^{\prime}$. By (iii), $\mathrm{cone}(\mathcal{G})^{\prime}$ is a
normal cone in an extreme point. Hence, $\mathrm{cone}(\mathcal{G})$ as its
face is a normal cone as well. ∎

######  Definition 2.

Let $\mathcal{G}\subseteq\mathcal{F}$ be a basis of $\mathbb{R}^{n}$, i.e.
linearly independent with $|\mathcal{G}|=\dim\mathbb{R}^{n}$. A cone of the
form $\mathrm{cone}(\mathcal{G})$, such that
$f\not\in\mathrm{cone}(\mathcal{G})$ for every
$f\in\mathcal{F}\backslash\mathcal{G}$, is called a _maximal elementary
simplicial cone (MESC)_.

As follows from Proposition 2, maximal elements of complete normal simplicial
fans of convex polyhedra are exactly MESCs. However, this does not mean that
every MESC is an element of a complete normal simplicial fan of a particular
polyhedron $\mathcal{C}$ generated by $\mathcal{F}$. There are two main
reasons for this. The first reason is that a normal fan
${\mathcal{N}(\mathcal{C})}$ may have multiple different triangulations. The
second, deeper reason is that different polyhedra in general have different
normal fans. Moreover, if two polyhedrons have the same normal fan, then they
are said to be _normally equivalent_ (see [11]).

In the sequel we focus on the set of possible MESC. We will analyze their
structure in particular cases related to models of imprecise probabilities.
Every complete normal simplicial fan contains MESCs together with their lower
dimensional faces as building blocks. Not all collections fit together,
though. A useful tool for the analysis of possible configurations of extreme
points in polyhedra is the endowment of the graph structure to the set of its
extreme points. In the next section we build on this idea to generate a graph
on the set of all MESCs, which can reveal some structural properties of normal
fans and especially their triangulated forms.

###  2.2 Adjacent cones and graph theoretical properties of maximal elementary
simplicial cones

A convex polyhedron $\mathcal{C}$ can be endowed a graph structure, where the
extreme points are taken as vertices. An edge between two vertices is then a
one dimensional face of $\mathcal{C}$ with the given vertices as extreme
points. In this section we extend the graph structure to the set of MESCs.
They are related to the extreme points in the sense described by Proposition
2. Every complete normal simplicial fan is obtained as a simplicial complex
comprising of MESCs. The graph structure introduced in the sequel will give us
some insights about combining MESCs to building the fans, and consequently
about the possible polyhedral structures obtained in the form (1).

We start with the notion of adjacency. Two extreme points of a convex
polyhedron $\mathcal{C}$ are adjacent if they are connected by an edge. The
normal cone corresponding to the edge, which is a one-dimensional face of
$\mathcal{C}$, is a common face of the normal cones corresponding to the two
extreme points. Moreover, the intersection of the two normal cones is exactly
the common face of codimension 1, which means that their relative interiors
are disjoint. We use this property as a definition of adjacency of two MESCs.

######  Definition 3.

Let $\mathcal{G}$ and $\mathcal{G}^{\prime}$ be two subsets of $\mathcal{F}$,
so that the corresponding cones $\mathrm{cone}(\mathcal{G})$ and
$\mathrm{cone}(\mathcal{G}^{\prime})$ are MESCs. Then the cones are said to be
adjacent if they intersect in a common face of codimension 1.

The following corollary is immediate.

######  Corollary 2.

Let cones $\mathrm{cone}(\mathcal{G})$ and
$\mathrm{cone}(\mathcal{G}^{\prime})$ be adjacent MESCs. Then
$|\mathcal{G}\cap\mathcal{G}^{\prime}|=|\mathcal{G}|-1=|\mathcal{G}^{\prime}|-1$.

The converse of the above corollary is not true, though. That is, if we have
two sets $\mathcal{G}$ and $\mathcal{G}^{\prime}$ differing in one element,
the corresponding cones are not necessarily adjacent. The reason is that their
intersection may be larger than the common face. The following lemma gives the
necessary and sufficient conditions for adjacency.

######  Lemma 1.

Let cones $\mathrm{cone}(\mathcal{G})$ and
$\mathrm{cone}(\mathcal{G}^{\prime})$ be MESCs such that
$|\mathcal{G}\cap\mathcal{G}^{\prime}|=|\mathcal{G}|-1=|\mathcal{G}^{\prime}|-1$.
Let $\mathcal{H}$ be the hyperplane generated by
$\mathcal{G}\cap\mathcal{G}^{\prime}$ and $t$ its normal (non-zero) vector.
Further let $f\in\mathcal{G}\backslash\mathcal{G}^{\prime}$ and
$f^{\prime}\in\mathcal{G}^{\prime}\backslash\mathcal{G}$. Then
$\mathrm{cone}(\mathcal{G})$ and $\mathrm{cone}(\mathcal{G}^{\prime})$ are
adjacent if and only if $(f\cdot t)(f^{\prime}\cdot t)<0$, i.e. the scalar
products with the normal vector have opposite signs.

###### Proof.

Denote the vectors in $\mathcal{G}\cap\mathcal{G}^{\prime}$ with
$f_{1},\ldots,f_{n-1}$ and without loss of generality we can assume that
$\|t\|=1$. By definition, $t\cdot f_{i}=0$ for $i=1,\ldots,n-1$ and
$\\{f_{1},\ldots,f_{n-1},t\\}$ forms a basis of $\mathbb{R}^{n}$. We can
therefore write

$\displaystyle f$ $\displaystyle=\sum_{i=1}^{n-1}\alpha_{i}f_{i}+\alpha t,$
(6) $\displaystyle f^{\prime}$
$\displaystyle=\sum_{i=1}^{n-1}\beta_{i}f_{i}+\beta t.$ (7)

We have that $f\cdot t=\alpha\|t\|^{2}=\alpha$ and $f^{\prime}\cdot t=\beta$.

We first prove that
$\mathrm{ri}(\mathrm{cone}(\mathcal{G}))\cap\mathrm{ri}(\mathrm{cone}(\mathcal{G}^{\prime}))\neq\emptyset$
implies that $\alpha\beta>0$. Let
$h\in\mathrm{ri}(\mathrm{cone}(\mathcal{G}))\cap\mathrm{ri}(\mathrm{cone}(\mathcal{G}^{\prime}))$.
Then we have that for some $\gamma_{i}>0,\delta_{i}>0$ for $i=1,\ldots,n-1$
and $\gamma,\delta>0$,

$\displaystyle h$ $\displaystyle=\sum_{i=1}^{n-1}\gamma_{i}f_{i}+\gamma
f=\sum_{i=1}^{n-1}\gamma_{i}f_{i}+\gamma\left(\sum_{i=1}^{n-1}\alpha_{i}f_{i}+\alpha
t\right)=\sum_{i=1}^{n-1}\gamma^{\prime}_{i}f_{i}+\gamma\alpha t$ (8) and
$\displaystyle h$ $\displaystyle=\sum_{i=1}^{n-1}\delta_{i}f_{i}+\delta
f^{\prime}=\sum_{i=1}^{n-1}\delta_{i}f_{i}+\delta\left(\sum_{i=1}^{n-1}\beta_{i}f_{i}+\beta
t\right)=\sum_{i=1}^{n-1}\delta^{\prime}_{i}f_{i}+\delta\beta t.$ (9)

By the uniqueness of linear combinations of the basis vectors, we obtain that
$\gamma\alpha=\delta\beta$. Now, since $\gamma$ and $\delta$ are strictly
positive, $\alpha$ and $\beta$ must be of equal sign. This completes the first
part of the proof.

The second part of the proof is to show conversely that $\alpha\beta>0$
implies
$\mathrm{ri}(\mathrm{cone}(\mathcal{G}))\cap\mathrm{ri}(\mathrm{cone}(\mathcal{G}^{\prime}))\neq\emptyset$.
To see this, we only need to show that an $h$ of the form (8) and (9) exists.
Suppose $\gamma_{i}>0$ and $\gamma>0$ are given. Then we set
$\delta=\frac{\alpha}{\beta}\gamma$, which is of positive sign because of the
equal sign of $\alpha$ and $\beta$. Now for every $i$ equating both expression
gives:

$\gamma^{\prime}_{i}=\gamma_{i}+\gamma\alpha_{i}=\delta^{\prime}_{i}=\delta_{i}+\delta\beta_{i}.$
(10)

Solving the above equation for $\delta_{i}$ gives
$\delta_{i}=\gamma_{i}+\gamma\alpha_{i}-\delta\beta_{i}$, which for
sufficiently large $\gamma_{i}$ can be made positive for every
$i=1,\ldots,n-1$. This concludes the proof of the proposition. ∎

######  Corollary 3.

Let $\mathcal{C}$ be a polyhedron and $\mathcal{T}$ its complete normal
simplicial fan. Let $C,C^{\prime}\in\mathcal{T}$ be a pair of adjacent MESCs.
Then exactly one of the following holds:

  1. (i)

An extreme point $x\in\mathcal{C}$ exists such that $C,C^{\prime}\subseteq
N(\mathcal{C},x)$.

  2. (ii)

A pair of extreme points $x,x^{\prime}$ exists that lie in a common
1-dimensional face of $\mathcal{T}$ such that $C\subseteq N(\mathcal{C},x)$
and $C^{\prime}\subseteq N(\mathcal{C},x^{\prime})$.

###### Proof.

Assume $\mathcal{C}$ in the form (1). Cones $C$ and $C^{\prime}$ are then of
the form $\mathrm{cone}(\mathcal{G})$ and
$\mathrm{cone}(\mathcal{G}^{\prime})$ respectively where both $\mathcal{G}$
and $\mathcal{G}^{\prime}$ are bases of $\mathbb{R}^{n}$. Moreover, both $C$
and $C^{\prime}$ lie within single normal cones – not necessarily the same,
that correspond to extreme points, say $x$ and $x^{\prime}$. If
$x=x^{\prime}$, then (i) holds. Now assume that $x\neq x^{\prime}$. By
adjacency, we have that $|\mathcal{G}\cap\mathcal{G}^{\prime}|=n-1$. Normal
cone containing $\mathrm{cone}(\mathcal{G}\cap\mathcal{G}^{\prime})$
corresponds to a face $F$ of $\mathcal{C}$ satisfying $yf=b_{f}$ for every
$f\in\mathcal{G}\cap\mathcal{G}^{\prime}$ and every $y\in F$. The face $F$ is
therefore a subset of the set of solutions of $n-1$ independent linear
equations, which is a 1-dimensional subspace of $\mathbb{R}^{n}$.
Consequently, $F$ must be an at most 1-dimensional face containing $x$ and
$x^{\prime}$, which are both particular solutions of the same set of linear
equations. As assumed, $x\neq x^{\prime}$, which implies that $F$ is exactly
one dimensional face containing both points. ∎

With $\mathbb{F}$ we now denote the set of all MESCs. This set represents all
possible maximal simplicial cones of polyhedra in the form (1). Let
$G=(\mathbb{F},\mathbb{E})$ be the graph with the set of vertices $\mathbb{F}$
and the set of edges $\mathbb{E}=\\{(C,C^{\prime})\colon
C,C^{\prime}\in\mathbb{F},C\text{ and }C^{\prime}\text{ are adjacent}\\}$.

######  Proposition 3.

Let $\mathcal{T}$ be a complete normal simplicial fan of a polyhedron of the
form (1) and let $\mathbb{T}$ denote the set of its $n$-dimensional simplices.
Then the subgraph $G(\mathcal{T})$ of $G(\mathbb{F},\mathbb{E})$ with vertices
$\mathbb{T}$ is connected and $n$-regular.

###### Proof.

To see that the graph is $n$-regular, recall that
$|\mathbb{T}|=\mathbb{R}^{n}$. Every cone $C_{T}\in\mathbb{T}$ is simplicial
and thus has exactly $n$ faces of codimension 1. As there are no border faces,
every such face is then also a part of another, adjacent cone.

It is also clear that every two simplicial cones are connected by a chain of
cones where each one has a common face of codimension 1 with the neighbours in
the chain. ∎

Every MESC $\mathrm{cone}(\mathcal{G})$ defines a unique vector $x$ satisfying
$xf=b_{f}$ for every $f\in\mathcal{G}$. Not every such vector however is an
extreme point in $\mathcal{C}$. A characterization follows.

######  Proposition 4.

A MESC $\mathrm{cone}(\mathcal{G})$ lies within the normal cone of an extreme
point $x\in\mathcal{C}$ of the form (1) if and only if the following
conditions are satisfied:

  1. (i)

$xf=b_{f}$ for every $f\in\mathcal{G}$;

  2. (ii)

$xf\geq b_{f}$ for every $f\in\mathcal{F}$.

###### Proof.

Condition (ii) implies that $x\in\mathcal{C}$, while condition (i) implies
that it is a face of dimension 0. The dimension follows by linear independence
of $\mathcal{G}$. Hence, $x$ is an extreme point in $\mathcal{C}$. ∎

Now let $\mathcal{C}$ be given and let $\mathrm{cone}(\mathcal{G})$ be a MESC
within a normal cone $N(\mathcal{C},x)$. The set $\mathbb{F}$ contains all
MESCs corresponding to extreme points in $\mathcal{C}$, but not every cone in
$\mathbb{F}$ corresponds to an extreme point. Additionally, we know that those
cones in $\mathbb{F}$ that are adjacent to $\mathrm{cone}(\mathcal{G})$ are
exactly those corresponding to the same extreme point $x$ or an adjacent one,
as follows by Corollary 3. Moreover, every adjacent MESC is of the form
$\mathrm{cone}(\mathcal{G}^{\prime})$, where, by Corollary 2,
$\mathcal{G}^{\prime}=(\mathcal{G}\backslash\\{f\\})\cup\\{f^{\prime}\\}$. The
following proposition shows that given $f\in\mathcal{G}$ adjacent cones must
correspond to the same adjacent extreme point.

######  Proposition 5.

Let MESC $\mathrm{cone}(\mathcal{G})$ lie within a normal cone
$N(\mathcal{C},x)$ and take some $f\in\mathcal{G}$. Now suppose that for some
$f^{\prime}$ and $f^{\prime\prime}\in\mathcal{F}$ both cones
$\mathcal{G}^{\prime}=(\mathcal{G}\backslash\\{f\\})\cup\\{f^{\prime}\\}$ and
$\mathcal{G}^{\prime\prime}=(\mathcal{G}\backslash\\{f\\})\cup\\{f^{\prime\prime}\\}$
are MESC and they lie within normal cones $N(\mathcal{C},x^{\prime})$ and
$N(\mathcal{C},x^{\prime\prime})$. Then $x^{\prime}=x^{\prime\prime}$.
(Possibly, $x^{\prime}=x^{\prime\prime}=x$.)

###### Proof.

By the assumptions, both $\mathrm{cone}(\mathcal{G}^{\prime})$ and
$\mathrm{cone}(\mathcal{G}^{\prime\prime})$ are adjacent to
$\mathrm{cone}(\mathcal{G})$. Let $t$ be the normal vector to the hyperplane
$\mathrm{lin}(G\backslash\\{f\\})$. By Lemma 1, $(f^{\prime}\cdot
t)(f^{\prime\prime}\cdot t)>0$, whence the relative interiors of the
corresponding cones intersect. Hence, the relative interiors of
$N(\mathcal{C},x^{\prime})$ and $N(\mathcal{C},x^{\prime\prime})$ intersect,
which is only possible if the cones are the same. ∎

######  Remark 1.

It is indeed possible that we have multiple adjacent cones to
$\mathrm{cone}(\mathcal{G})$ corresponding to the same adjacent extreme point,
as they might correspond to different triangulations of
$N(\mathcal{C},x^{\prime})$. Yet, when a triangulation is fixed, only one
adjacent cone of the form
$\mathrm{cone}((\mathcal{G}\backslash\\{f\\})\cup\\{f^{\prime}\\})$ exists per
fixed $f$.

The above propositions would therefore enable identification of all cones
corresponding to a complete normal simplicial fan of a convex polyhedron, and
consequently an identification and enumeration of its extreme points. The main
steps are given by Algorithm 1.

Algorithm 1 Algorithm: find complete simplicial fan and extreme points

1:function SimplicialFan($\mathcal{F},\mathbf{b}$)

2: $\triangleright$ Inputs: support vector and support function

3: Initialize: find $\mathcal{G}$, such that $\mathrm{cone}(\mathcal{G})$ is
MESC

4: $V\leftarrow\\{\mathcal{G}\\},E\leftarrow\emptyset,G\leftarrow(V,E)$

5: $\triangleright$ Adjacency graph of the members of complete simplicial fan

6: $\mathcal{E}\leftarrow\mathrm{ExtremePoint}(\mathcal{G})$

7: $\triangleright$ Collection of extreme points

8: repeat

9: Select $\mathcal{G}\in V$ such that $\deg(\mathcal{G})<n$

10: neighbours $\leftarrow$ Find all neighbour cones corresponding to extreme
points

11: neighbours $\leftarrow$ Remove all duplicate neighbours
$\mathcal{G}^{\prime}$ having the same intersection with $\mathcal{G}$

12: $V\leftarrow V\cup$ neighbours

13: $E\leftarrow E\cup\\{(\mathcal{G},\mathcal{G}^{\prime})\\}$ for all
$\mathcal{G}^{\prime}\in$ neighbours

14:
$\mathcal{E}\leftarrow\mathcal{E}\cup\\{\mathrm{ExtremePoint}(\mathcal{G}^{\prime})\\}$
for all $\mathcal{G}^{\prime}\in$ neighbours

15: until ($G$ is $n$-regular)

16:end function

##  3 Credal sets as imprecise probability models

In this section we introduce the basic concepts of imprecise probabilities
used in the paper. When possible, we will stick with the standard terminology
used in the theory of imprecise probabilities (see [3, 56]). The main goal of
this section is to relate the models of imprecise probabilities with the
concepts of convex analysis.

The object of our analysis are _coherent lower previsions_ [24, 47] which
present one of the most general models of imprecise probabilities. They
encompass several particular models, such as _coherent lower and upper
probabilities_ [12, 35, 58], 2- and n-_monotone capacities_ [5, 29, 45],
_belief_ and _plausibility functions_ [41, 44] and others. Mathematically,
coherent lower previsions are superlinear functionals that can be equivalently
represented as lower envelopes of expectation functionals.

Let $\mathcal{X}$ represent a finite set – _sample space_ , and
$\mathbb{R}^{n}$ the set of all real-valued maps on $\mathcal{X}$ – _gambles_.
By ${\mathbb{I}_{A}}$ we will denote the _indicator gamble_ of a set
$A\subseteq\mathcal{X}$:

${\mathbb{I}_{A}}(x)=\begin{cases}1&x\in A,\\\ 0&\text{otherwise}.\end{cases}$
(11)

We will write ${\mathbb{I}_{x}}$ instead of ${\mathbb{I}_{\\{x\\}}}$ for
singletons. A _linear prevision_ $P$ is an expectation functional with respect
to some probability mass vector $p$ on $\mathcal{X}$. It maps a gamble $f$
into a real number $P(f)$:

$P(f)=\sum_{x\in\mathcal{X}}p(x)f(x).$ (12)

Equivalently, we can write $P(f)=pf$. The set of linear previsions is
therefore a subset of $\mathbb{R}^{n}$. A _coherent lower prevision_ on an
arbitrary set of gambles $\mathcal{F}$ is a mapping
$\underline{P}\colon\mathcal{F}\to\mathbb{R}$ that allows the representation

$\underline{P}(f)=\min_{P\in\mathcal{M}(\underline{P})}P(f)$ (13)

for every $f\in\mathcal{F}$, where $\mathcal{M}(\underline{P})$ is a closed
and convex set of linear previsions. The set $\mathcal{M}(\underline{P})$ is
called the _credal set_ of ${\underline{P}}$, defined as

$\mathcal{M}(\underline{P})=\\{P\text{ a linear prevision }\colon
P(f)\geq\underline{P}(f)\text{ for every }f\in\mathcal{F}\\}.$ (14)

Given a coherent lower prevision $\underline{P}$ on $\mathcal{F}$, it is
possible to extend it to the set of all gambles $\mathbb{R}^{n}$ in possibly
several different ways. However, there is a unique minimal extension, called
the _natural extension_ :

${\underline{E}}(f)=\min_{P\in\mathcal{M}(\underline{P})}P(f).$ (15)

As the natural extension is the _lower envelope_ or the _support function_ of
a credal set, containing expectation functionals, we may call a coherent lower
prevision defined on the entire $\mathbb{R}^{n}$ a _lower expectation
functional_. A mapping $\underline{P}\colon\mathcal{F}\to\mathbb{R}$, where
$\mathcal{F}$ is a vector space, is a coherent lower prevision if and only if
it satisfies the following axioms ([24]) for all $f,g\in\mathcal{F}$ and
$\lambda\geq 0$:

  * (P1)

$\underline{P}(f)\geq\inf_{x\in\mathcal{X}}f(x)$ [accepting sure gains];

  * (P2)

$\underline{P}(\lambda f)=\lambda\underline{P}(f)$ [positive homogeneity];

  * (P3)

$\underline{P}(f+g)\geq\underline{P}(f)+\underline{P}(g)$ [superlinearity].

An easy consequence of the definitions is _constant additivity_ :

$\underline{P}(f+\lambda{\mathbb{I}_{\mathcal{X}}})=\underline{P}(f)+\lambda$
(16)

for any $\lambda\in\mathbb{R}$. In particular, the above relations hold for a
natural extension ${\underline{E}}$ of a coherent lower prevision
$\underline{P}$.

Together with a coherent lower prevision, the notion of _coherent upper
prevision_ $\overline{P}$ is often introduced. Assuming the domain is a vector
space, the conjugacy relation $\underline{P}(f)=-\overline{P}(-f)$ is a
straightforward consequence of coherence. Therefore, instead of considering
the pairs of lower and upper previsions, the set $-\mathcal{F}=\\{-f\colon
f\in\mathcal{F}\\}$ is added to the domain of $\underline{P}$ together with
the relations induced by conjugacy.

###  3.1 Lower probabilities and probability intervals

It follows from the definition of a lower prevision that its domain
$\mathcal{F}$ may only be a finite subset of $\mathbb{R}^{n}$. In fact,
$\underline{P}(f)$ are often some judgments representing the available
information regarding the expectations of gambles. According to the philosophy
of imprecise probabilities, probability models should not assume more
information than provided. Hence, in general multiple probabilistic models fit
given information. The natural extension then allows taking in consideration
all compatible models simultaneously, which is considered the main advantage
of imprecise models over classical ones.

A lower previsions whose domain $\mathcal{F}$ consists of indicator functions
${\mathbb{I}_{A}}$ of subsets $A\subset\mathcal{X}$ are called _lower
probabilities_. A lower probability is usually denoted by
$L\colon\mathcal{A}\to\mathbb{R}$, where $\mathcal{A}\subseteq
2^{\mathcal{X}}$. The mapping $L$ has the same role as $\underline{P}$ in the
previous section. The credal set of a lower probability $\mathcal{M}(L)$ is
again the set of all linear previsions
$\underline{P}\colon\mathcal{F}\to\mathbb{R}$ satisfying $P(A)\geq L(A)$ for
every $A\in\mathcal{A}$. A lower probability is _coherent_ if all bounds are
reachable: $L(A)=\min_{P\in\mathcal{A}}P(A)$.

In case where $\mathcal{A}\neq 2^{\mathcal{X}}$, the corresponding lower
probability is said to be partially specified. An important example of
partially specified lower probability is _probability interval model (PRI)_
[6, 58], where the domain $\mathcal{A}$ only contains singletons and their
complements. A more conventional way to introduce a probability interval is by
a pair of mappings $l,u\colon\mathcal{X}\to\mathbb{R}$, such that $l\leq u$.
Here, $l(x)$ is interpreted as the lower probability of $\\{x\\}$ and $u(x)$
its upper probability. The notion of coherence applies to this case
analogously. Conjugacy relation
$u(x)=\overline{P}({\mathbb{I}_{x}})=1-\underline{P}(-{\mathbb{I}_{x}})=1-L(\\{x\\}^{c})$,
implying $L(\\{x\\}^{c})=1-u(x)$, now allows us to regard probability
intervals as lower probabilities with the domain $\mathcal{A}=\\{\\{x\\}\colon
x\in\mathcal{X}\\}\cup\\{\\{x\\}^{c}\colon x\in\mathcal{X}\\}$. In general, we
will denote a PRI model by an ordered pair $(l,u)$, and where needed, it will
be interpreted as a partially specified lower probability $L$ with the domain
$\mathcal{A}$. Credal sets corresponding to lower probabilities and
probability interval models will be respectively denoted by $\mathcal{M}(L)$
and $\mathcal{M}(l,u)$.

###  3.2 Finitely generated credal sets as polyhedra

A credal set is a closed and convex set of linear previsions. Since every
linear prevision can be uniquely represented as a probability mass vector, a
credal set can be represented as a convex set of probability mass vectors. The
set $\mathcal{M}$ is therefore the maximal set of $n$-dimensional vectors $p$
satisfying

$\displaystyle pf$ $\displaystyle\geq\underline{P}(f)$ $\displaystyle\text{
for every }f\in\mathcal{F},$ (17) $\displaystyle p{\mathbb{I}_{x}}$
$\displaystyle\geq 0$ $\displaystyle\text{ for every }x\in\mathcal{X}\text{
and }$ (18) $\displaystyle p{\mathbb{I}_{\mathcal{X}}}$ $\displaystyle=1.$
(19)

In our case, $\mathcal{F}$ is assumed finite, the corresponding credal set is
therefore a convex polyhedron. A credal set that is a convex polyhedron is
called a _finitely generated credal set_ , and a lower prevision defined on
finite set of gambles is a _finitely generated coherent lower prevision_.

According to the above, it would be suitable to extend the domain of
$\underline{P}$ with the gambles of the form ${\mathbb{I}_{x}}$ for every
$x\in\mathcal{X}$. Doing so, however, may result in a non-coherent lower
prevision, because other constraints may already imply that
$\underline{P}({\mathbb{I}_{x}})\geq 0$, where the inequality may even be
strict. Therefore we adopt the following convention:

######  Convention 1.

The domain $\mathcal{F}$ of all lower previsions used will contain all gambles
of the form ${\mathbb{I}_{x}}$ together with the value
$\underline{P}({\mathbb{I}_{x}})=0$, unless
$\underline{P}({\mathbb{I}_{x}})\geq 0$ is already implied by other values of
$\underline{P}$ on $\mathcal{F}$.

Assuming the above convention, the credal set of a coherent lower prevision
$\mathcal{M}(\underline{P})$ is the set of vectors $p$ satisfying constraints
(17) and (19).

Normal cones corresponding to credal sets of lower previsions will be
equivalently denoted by
$N(\underline{P},P)=N(\mathcal{M}(\underline{P}),P)=\\{f\colon
P(f)=\underline{P}(f)\\}=\mathrm{cone}(\mathcal{F}(P))$, where
$\mathcal{F}(P)=\\{f\in\mathcal{F}\colon P(f)=\underline{P}(f)\\}$. In
addition to inequality constraints, credal sets satisfy the equality
constraint (19). This implies that every $\mathcal{F}(P)$ contains the
constant gamble ${\mathbb{I}_{\mathcal{X}}}$. Hence, every normal cone is of
the form

$\displaystyle N(\underline{P},P)$
$\displaystyle=\mathrm{cone}(\mathcal{F}(P)\backslash\\{{\mathbb{I}_{\mathcal{X}}}\\})+\mathrm{lin}\\{{\mathbb{I}_{\mathcal{X}}}\\}$
(20)
$\displaystyle=\left\\{\sum_{f\in\mathcal{F}(P)\backslash\\{{\mathbb{I}_{\mathcal{X}}}\\}}\alpha_{f}f+\beta{\mathbb{I}_{\mathcal{X}}}\colon\alpha_{f}\geq
0,\beta\in\mathbb{R}\right\\}.$ (21)

Technically, a normal cone as above is a union of two symmetrical cones, one
with $\beta\geq 0$ and the other with $\beta\leq 0$. The following result is
straightforward.

######  Proposition 6 (Normal cone additivity).

Take arbitrary vectors $g,h\in N(\underline{P},P)$. Then
$\underline{P}(g+h)=\underline{P}(g)+\underline{P}(h)$.

###### Proof.

The fact that $g$ and $h$ both belong to the same normal cone at $P$ implies
that $P(g)=\underline{P}(g)$ and $P(h)=\underline{P}(h)$. By the closure for
sums of the cone, we then also have that $P(g+h)=\underline{P}(g+h)$ and
therefore additivity of $P$ implies
$\underline{P}(g+h)=\underline{P}(g)+\underline{P}(h)$. ∎

##  4 Normal cones of lower probabilities

By a normal cone corresponding to a lower probability or a PRI model, we mean
a normal cone corresponding to its credal set, and denote it by $N(L,P)$ or
$N((l,u),P)$ respectively. Such a cone is then a non-negative hull of a set of
indicator functions corresponding to a collection of subsets of $\mathcal{X}$.
This set includes ${\mathbb{I}_{\mathcal{X}}}$, as follows from (20). Such a
normal cone can thus be represented with the corresponding collection of sets.
Let $\mathcal{A}$ be a collection of sets. Denote the cone generated by their
indicator functions by
$\mathrm{cone}(\mathcal{A}):=\mathrm{cone}(\\{{\mathbb{I}_{A}}\colon
A\in\mathcal{A}\backslash\\{\mathcal{X}\\}\\})+\mathrm{lin}\\{{\mathbb{I}_{\mathcal{X}}}\\}$.
In particular, we characterize elements of complete normal simplicial fans.
The following proposition holds.

######  Proposition 7.

Let $\mathrm{cone}(\mathcal{A})$ correspond to an element of a complete normal
simplicial fan. Then:

  1. (i)

The vectors $\\{{\mathbb{I}_{A}}\colon A\in\mathcal{A}\\}$ are linearly
independent.

  2. (ii)

No equation of the form
$\sum_{\mathcal{A}\backslash\\{\mathcal{X}\\}}\alpha_{A}{\mathbb{I}_{A}}+\alpha_{\mathcal{X}}{\mathbb{I}_{\mathcal{X}}}={\mathbb{I}_{B}}$,
where $B\not\in\mathcal{A}$, has a solution such that $\alpha_{A}\geq 0$ for
every $A\in\mathcal{A}\backslash\\{\mathcal{X}\\}$.

###### Proof.

The proposition is a direct consequence of Proposition 2. ∎

######  Corollary 4.

Let $\mathrm{cone}(\mathcal{A})$ be an element of a complete normal simplicial
fan corresponding to a credal set of a lower probability $L\colon
2^{\mathcal{X}}\to\mathbb{R}$. Then

  1. (i)

for every pair of sets $A_{1},A_{2}\in\mathcal{A},A_{1}\cap
A_{2}\neq\emptyset$, i.e. $\mathcal{A}$ is an intersecting collection;

  2. (ii)

for every pair of sets
$A_{1},A_{2}\in\mathcal{A}\backslash\\{\mathcal{X}\\},A\cup B\neq\mathcal{X}$.

###### Proof.

To see (i), suppose $A_{1},A_{2}\in\mathcal{A}$ exist such that $A_{1}\cap
A_{2}=\emptyset$. Then
${\mathbb{I}_{A_{1}}}+{\mathbb{I}_{A_{2}}}={\mathbb{I}_{A_{1}\cup A_{2}}}$.
Hence, either $A_{1}\cup A_{2}\in\mathcal{A}$, which makes it linearly
dependent or ${\mathbb{I}_{A_{1}\cup A_{2}}}\in\mathrm{cone}(\mathcal{A})$,
violating (ii) of Proposition 7.

To see (ii), suppose $A_{1}\cup A_{2}=\mathcal{X}$. Then, $A_{1}\cup
A_{2}={\mathbb{I}_{A_{1}\cup A_{2}}}+{\mathbb{I}_{A_{1}\cap
A_{2}}}={\mathbb{I}_{\mathcal{X}}}+{\mathbb{I}_{A_{1}\cap A_{2}}}$. Hence,
either $A_{1}\cap A_{2}=\emptyset$, which is violation of (i) or taking
$B=A_{1}\cap A_{2}$, ${\mathbb{I}_{B}}$ is contained in
$\mathrm{cone}(\mathcal{A})$. Then either, $\mathcal{A}$ is dependent, which
violates Proposition 7(i) or it contains ${\mathbb{I}_{B}}$, violating
Proposition 7(ii). ∎

Even though Corollary 4 turns out useful to characterize elements of complete
simplicial fans, in general, it is insufficient, as the following example
shows.

######  Example 1.

Let $\mathcal{X}=\\{x_{1},x_{2},x_{3},x_{4}\\}$. Consider the collection of
sets
$A_{1}=\\{x_{1},x_{2}\\},A_{2}=\\{x_{2},x_{3}\\},A_{3}=\\{x_{1},x_{3}\\},\mathcal{X}$.
It is an intersecting collection, yet it does not generate an element of a
complete simplicial fan. This is because
$\frac{1}{2}({\mathbb{I}_{A_{1}}}+{\mathbb{I}_{A_{2}}}+{\mathbb{I}_{A_{3}}})={\mathbb{I}_{\\{x_{1},x_{2},x_{3}\\}}}$,
which violates Proposition 7 (ii).

######  Example 2.

Let $\mathcal{X}=\\{x_{1},x_{2},x_{3}\\}$. Every MESC is a cone of the form
$\mathrm{cone}(\mathcal{A})$, where $\mathcal{A}$ is a collection of exactly 3
subsets of $\mathcal{X}$, including $\mathcal{X}$. Suppose
$\\{x_{1},x_{2}\\}\in\mathcal{A}$. According to Corollary 4, the only
possibilities for the second set (note that $\mathcal{X}$ is always a member)
in $\mathcal{A}$ are $\\{x_{1}\\}$ and $\\{x_{2}\\}$. Indeed, both these sets
correspond to adjacent MESCs. Similarly, in addition to a singleton set
$\\{x_{1}\\}$, the only possible sets are $\\{x_{1},x_{2}\\}$ and
$\\{x_{1},x_{3}\\}$, that both correspond to two adjacent MESCs corresponding
to adjacent extreme points.

###  4.1 Normal cones of 2-monotone lower probabilities

A lower probability $L$ is said to be _2-monotone (convex, supermodular)_ if
for every pair of sets $A,B$,

$L(A\cup B)+L(A\cap B)\geq L(A)+L(B).$ (22)

A collection of subsets $\mathcal{A}$ is a _chain_ if for any pair of sets
$A,B\in\mathcal{A}$, at least one of the relations $A\subseteq B$ or
$B\subseteq A$ holds. A maximal chain is then the one maximal with respect to
set inclusion. In our finite settings, a maximal chain $\mathcal{A}$ is of the
form $\mathcal{A}=\\{A_{0},A_{1},\ldots A_{n}\\}$ where
$A_{0}=\emptyset,A_{n}=\mathcal{X}$ and $|A_{i+1}\backslash A_{i}|=1$.

The following proposition gives a previously known result (see e.g. [5, 7,
27]).

######  Proposition 8.

Let $L$ be a 2-monotone lower probability on a finite space $\mathcal{X}$ and
$\mathcal{A}$ a maximal chain. Then there exists a linear prevision
$P_{\mathcal{A}}\in\mathcal{M}(L)$ such that $P(A)=L(A)$ for every
$A\in\mathcal{A}$.

Moreover, every extreme point $P\in\mathcal{M}(L)$ is of the form
$P_{\mathcal{A}}$ for some maximal chain $\mathcal{A}$.

The important claim of the above proposition is that the linear prevision with
this property belongs to $\mathcal{M}(L)$. This characterization of the
extreme points of credal sets of 2-monotone lower probabilities can now be
used to give a characterization of the normal cones of those credal sets. Two
vectors $g,h\in\mathbb{R}^{n}$ are said to be _comonotone_ if $g(x)>g(y)$
implies that $f(x)\geq f(y)$ for every pair $x,y\in\mathcal{X}$. A set of
vectors $\mathcal{H}$ is said to be _comonotone_ if all pairs of its elements
are.

######  Proposition 9 ([13]).

Let $\mathcal{H}$ be a set of vectors. The following conditions are
equivalent:

  1. (i)

$\mathcal{H}$ is comonotone;

  2. (ii)

the level set $\mathcal{L}=\\{\\{x\colon f(x)\leq\alpha\\}\colon
f\in\mathcal{H},\alpha\in\mathbb{R}\\}$ forms a chain;

  3. (iii)

an enumeration of elements $\mathcal{X}$ exists, denoted by
$x_{1},\ldots,x_{n}$, such that $f(x_{i})\leq f(x_{i+1})$ for every
$f\in\mathcal{H}$ and $1\leq i\leq n-1$.

######  Lemma 2.

A set of vectors $\mathcal{H}$ is comonotone if and only if
$\mathrm{cone}(\mathcal{H})$ is comonotone.

###### Proof.

The ’if’ part being trivial, we prove the ’only if’ part. Thus, assume
$\mathcal{H}$ being comonotone. By Proposition 9, the level set $\mathcal{L}$
then forms a chain. As by the assumption, $\mathcal{X}$ is finite,
$\mathcal{L}$ must be a finite chain. Moreover, every $f\in\mathcal{H}$ is of
the form $f=\sum_{L\in\mathcal{L}}\alpha_{L}{\mathbb{I}_{L}}$ for some non-
negative coefficients $\alpha_{L}$. Clearly, every positive linear combination
of positive linear combinations of the indicator sets in $\mathcal{L}$ is
again one; and its level sets belong to the same collection $\mathcal{L}$,
which is therefore the collection of the level sets of all elements of the
cone $\mathrm{cone}(\mathcal{A})$. Now, since $\mathcal{L}$ is a chain, the
cone must therefore be a comonotone set. ∎

######  Corollary 5.

Let $\mathcal{A}$ be a collection of sets and
$N_{\mathcal{A}}=\mathrm{cone}(\mathcal{A})$. Then $N_{\mathcal{A}}$ is
comonotone if an only if $\mathcal{A}$ forms a chain.

###### Proof.

Clearly, $\mathcal{A}$ is a comonotone set exactly if it forms a chain, which
by Lemma 2, is exactly if the cone it generates is comonotone. ∎

######  Definition 4.

A set of vectors $\mathcal{H}$ will be called _maximal comonotone_ if its
level sets $\mathcal{L}$ form a maximal chain.

The following corollary is obvious.

######  Corollary 6.

Let $\mathcal{H}$ be a maximal comonotone set. Then
$\mathrm{cone}(\mathcal{H})$ is a maximal comonotone set.

######  Theorem 2.

Let $\mathcal{X}$ be a finite set and let $\mathbb{A}=\\{\mathcal{A}\subset
2^{\mathcal{X}}\colon\mathcal{A}\text{ forms a chain}\\}$. Denote with
${\mathcal{N}(\mathbb{A})}=\\{\mathrm{cone}(\mathcal{A})\colon\mathcal{A}\in\mathbb{A}\\}$
the collection of cones generated by the chains. The following propositions
hold:

  1. (i)

${\mathcal{N}(\mathbb{A})}$ is a complete fan.

  2. (ii)

Let $L$ be a 2-monotone lower probability on $2^{\mathcal{X}}$ and
$\mathcal{A}\subseteq 2^{\mathcal{X}}$ a maximal chain. Every
$\mathrm{cone}(\mathcal{A})\in{\mathcal{N}(\mathbb{A})}$ is contained in a
single normal cone $N(L,P)$.

  3. (iii)

Every $\mathrm{cone}(\mathcal{A})\in{\mathcal{N}(\mathbb{A})}$ is a simplicial
cone.

  4. (iv)

${\mathcal{N}(\mathbb{A})}$ is a complete normal simplicial fan.

  5. (v)

The credal set $\mathcal{M}(L)$ of a 2-monotone lower probability $L$ in the
probability space $(\mathbb{R}^{n},2^{\mathbb{R}^{n}})$ has at most $n!$
extreme points.

  6. (vi)

Let $\mathcal{A}=\\{A_{1},\ldots,A_{n}\\}$ be a maximal chain. Then MESC
$\mathrm{cone}(\mathcal{A})$ is adjacent to exactly $n$ MESCs
$\mathrm{cone}(\mathcal{A}_{i})$ in $\mathbb{A}$ generated as follows. Take
some $i\in\\{1,\ldots,n\\}$. Then form $\mathcal{A}_{i}$ by removing $A_{i}$
and replacing it with $A^{\prime}_{i}=A_{i-1}\cup(A_{i+1}\backslash A_{i})$.
(We set $A_{0}=\emptyset$.)

  7. (vii)

The graph with vertices $\mathbb{A}$ and edges corresponding to adjacency is
$n$-regular and connected.

###### Proof.

The proof of (i) consists of three steps.

  1. Step 1.

Every vector in $\mathbb{R}^{n}$ is contained in at least one cone in
${\mathcal{N}(\mathbb{A})}$.

  2. Step 2.

The intersection of two cones in ${\mathcal{N}(\mathbb{A})}$ is a face of
both.

  3. Step 3.

Faces of all cones are contained in ${\mathcal{N}(\mathbb{A})}$.

Step 1: Take arbitrary vector $f\in\mathbb{R}^{n}$ and let $\mathcal{A}$ be
the collection of its level sets, which is always a chain. Then clearly $f$ is
a positive linear combination of elements in $\mathcal{A}$ and therefore
belongs to the cone $\mathrm{cone}(\mathcal{A})$.

Step 2: Let $\mathcal{A}_{1}$ and $\mathcal{A}_{2}$ be two chains in
$\mathbb{A}$ and $\mathrm{cone}(\mathcal{A}_{i})$ the corresponding cones. We
will show that

$\mathrm{cone}(\mathcal{A}_{1})\cap\mathrm{cone}(\mathcal{A}_{2})=\mathrm{cone}(\mathcal{A}_{1}\cap\mathcal{A}_{2}).$
(23)

The inclusion $\supseteq$ is clear, whence it remains to show the $\subseteq$
part. Thus let
$f\in\mathrm{cone}(\mathcal{A}_{1})\cap\mathrm{cone}(\mathcal{A}_{2})$. Take
only those members of $\mathcal{A}_{1}$ that have strictly positive
coefficients in $\sum_{A\in\mathcal{A}_{1}}\alpha_{A}{\mathbb{I}_{A}}$. It is
easy to check that the level sets of $\mathcal{F}$ are exactly these sets. And
by the same argument, the level sets must be exactly those with strictly
positive coefficients in the positive linear combinations of sets from
$\mathcal{A}_{2}$. Hence, these sets must be the same, and therefore lie in
the intersection $\mathcal{A}_{1}\cap\mathcal{A}_{2}$. It also follows by the
construction of this argument that these sets form a chain, and thus generate
a subcone of a possibly lower dimension that is a face both cones.

Step 3: A face of $\mathrm{cone}(\mathcal{A})$ is
$\mathrm{cone}(\mathcal{A}^{\prime})$ generated by a subset
$\mathcal{A}^{\prime}$ of $\mathcal{A}$. Clearly a subset of a chain is again
a chain, and therefore $\mathrm{cone}(\mathcal{A}^{\prime})$ belongs to
${\mathcal{N}(\mathbb{A})}$ by definition.

(ii) Let $\mathrm{cone}(\mathcal{A})$ be given corresponding to a maximal
chain $\mathcal{A}$. It follows from Proposition 8 that $P_{\mathcal{A}}$ is
an extreme point of $\mathcal{M}(L)$ such that $P_{\mathcal{A}}(A)=L(A)$ for
every $A\in\mathcal{A}$. Hence, $\mathcal{A}$ belongs to
$N(L,P_{\mathcal{A}})$ and so does the cone its generates.

(iii) Let $\mathcal{A}$ be a chain. The vectors ${\mathbb{I}_{A}}$ for
$A\in\mathcal{A}$ are then clearly linearly independent. To see this, combine
the corresponding 0-1 vectors to a matrix which has clearly a triangular form.
Hence $\mathrm{cone}(\mathcal{A})$ is simplicial by definition.

(iv) follows directly from the above.

(v) follows from (ii) and the fact that chains of subsets of $\mathcal{X}$ are
in a one-to-one correspondence with permutations. To see this, notice that
each permutation $\sigma$ induces the natural chain
$\mathcal{A}_{\sigma}=\\{A_{i}\colon
A_{i}=\\{x_{\sigma(1)},\ldots,x_{\sigma(i)}\\},i=1,\ldots,n\\}$ and that the
mapping $\Sigma\to 2^{\mathcal{X}}$ that maps
$\sigma\mapsto\mathcal{A}_{\sigma}$ is bijective. The number of maximal chains
is therefore equal to $n!$ and since every cone generated by a maximal chain
is contained in an $n$-dimensional normal cone. This limits the number of
normal cones to at most $n!$.

(vi) It follows clearly from the construction that collections
$\mathcal{A}_{i}$ are again chains and therefore
$\mathrm{cone}(\mathcal{A}_{i})\in\mathbb{A}$ for every $i=1,\ldots,n$. It is
also easy to see that sets $A^{\prime}_{i}$ are the only candidates to replace
$A_{i}$ so that the resulting collection is still a chain.

(vii) It follows immediately from (vi) that every $\mathrm{cone}(\mathcal{A})$
has exactly $n$ neighbours. ∎

A simple proof for the representation of comonotonic additive functionals with
2-monotone lower probabilities follows. This result is known in several forms
([40, 13]), yet we present it here as an application of our results presented
above.

######  Proposition 10.

Let ${\underline{E}}$ be a lower expectation functional. The following
conditions are equivalent:

  1. (i)

${\underline{E}}$ is comonotonic additive;

  2. (ii)

a 2-monotone lower probability $L$ exists so that ${\underline{E}}$ is its a
natural extension.

###### Proof.

We start with proving (i) $\implies$ (ii). Let
$L(A)={\underline{E}}({\mathbb{I}_{A}})$ for every subset of $\mathcal{X}$.
Take sets $A$ and $B$. Then ${\mathbb{I}_{A\cap B}}$ and ${\mathbb{I}_{A\cup
B}}$ are comonotone and ${\mathbb{I}_{A\cap B}}+{\mathbb{I}_{A\cup
B}}={\mathbb{I}_{A}}+{\mathbb{I}_{B}}$. Moreover, superadditivity of coherent
lower previsions implies that
${\underline{E}}({\mathbb{I}_{A}})+{\underline{E}}({\mathbb{I}_{B}})\leq{\underline{E}}({\mathbb{I}_{A}}+{\mathbb{I}_{B}})={\underline{E}}({\mathbb{I}_{A\cap
B}})+{\underline{E}}({\mathbb{I}_{A\cup B}})$, which amounts to 2-monotonicity
of $L$.

It remains to show that ${\underline{E}}$ is the natural extension of $L$. To
see this, take arbitrary vector $f\in\mathbb{R}^{n}$. Then $f$ can be
represented as a positive linear combination of its level sets, which also
form a chain, say $\mathcal{A}$. Now all vectors ${\mathbb{I}_{A}}$ for
$A\in\mathcal{A}$ and $f$ form a comonotone set and
$f=\sum_{A\in\mathcal{A}}\alpha_{A}{\mathbb{I}_{A}}$. By comonotonic
additivity we have that
${\underline{E}}(f)=\sum_{A\in\mathcal{A}}\alpha_{A}{\underline{E}}(A)=\sum_{A\in\mathcal{A}}\alpha_{A}L(A)={\underline{E}}_{L}(f)$,
where ${\underline{E}}_{L}$ denotes the natural extension of $L$. Hence, both
lower previsions coincide.

(ii) $\implies$ (i) is a well known property of 2-monotone lower
probabilities. It is directly implied by Theorem 2(ii) and Proposition 6. ∎

##  5 Normal cones of probability intervals models

According to the representation of credal sets (17)–(19), the support
functionals of credal sets induced by probability intervals are in the forms
of ${\mathbb{I}_{x}}$ and ${\mathbb{I}_{\\{x\\}^{c}}}$ respectively. In this
section we propose a full characterization of the complete normal simplicial
fans for PRI models. For the contrast with the case of 2-monotone lower
probabilities, their structure is not unique, or in other words, they are not
normally equivalent.

###  5.1 Maximal elementary simplicial cones corresponding to PRI models

######  Proposition 11.

Let $\mathrm{cone}(\mathcal{A})$ be a maximal elementary simplicial cone of a
credal set corresponding to a PRI model $(l,u)$. Then $\mathcal{A}$ is of the
following form. Enumerate the elements of $\mathcal{X}$ in some order and
choose $k$ so that $1\leq k\leq n-2$. Now the set $\mathcal{A}$ consists of
the following $n$ sets

  1. (i)

singleton sets $A_{i}=\\{x_{i}\\}$ for $1\leq i\leq k$;

  2. (ii)

complements of the singletons $A_{j}=\\{x_{j}\\}^{c}$ for $k+1\leq j\leq n-1$;

  3. (iii)

indicator set ${\mathbb{I}_{\mathcal{X}}}$.

###### Proof.

By the construction of a PRI model, the maximal simplicial cones are generated
by sets of the described form and obviously, $x_{i}\neq x_{i^{\prime}}$ for
$i\neq i^{\prime};i,i^{\prime}\leq k$ and $x_{j}\neq x_{j^{\prime}}$ for
$j\neq j^{\prime};j,j^{\prime}>k$. Thus, it remains to show that:

  1. 1.

$x_{i}\neq x_{j}$ for every $i\leq k$ and $j>k$. Indeed, if $x_{i}=x_{j}$ for
some pair of indices, then $\\{x_{i}\\}\cup\\{x_{i}\\}^{c}=\mathcal{X}$ and
therefore the set loses linear independence.

  2. 2.

$k\geq 1$. Suppose contrary that $k=0$. Then
$\mathcal{A}=\\{\\{x_{i}\\}^{c}\colon
x_{i}\in\\{x_{n}\\}^{c}\\}\cup\\{\mathcal{X}\\}$. Then,
$\sum_{A\in\mathcal{A}}{\mathbb{I}_{A}}=n{\mathbb{I}_{\mathcal{X}}}+{\mathbb{I}_{x_{n}}}$,
whence
${\mathbb{I}_{x_{n}}}=\sum_{A\in\mathcal{A}}{\mathbb{I}_{A}}-n{\mathbb{I}_{\mathcal{X}}}$
and thus ${\mathbb{I}_{x_{n}}}$ belongs to the cone generated by
$\mathcal{A}$. (Notice that ${\mathbb{I}_{\mathcal{X}}}$ may appear with a
negative coefficient by (20)). This contradicts Proposition 2(ii).

  3. 3.

$k<n-1$. This case is symmetrical to case 2. By assuming $k=n-1$ we would then
have $\mathcal{A}=\\{\\{x_{i}\\}\colon 1\leq i\leq
n-1\\}\cup\\{\mathcal{X}\\}$, whence
$\sum_{A\in\mathcal{A}}{\mathbb{I}_{A}}={\mathbb{I}_{\\{x_{n}\\}^{c}}}$ which
again violates Proposition 2(ii).

∎

A full characterization of elements of the cones follows.

######  Corollary 7.

Let $\mathrm{cone}(\mathcal{A})$ be a cone corresponding to a set
$\mathcal{A}$ constructed as in Proposition 11. Then
$h\in\mathrm{cone}(\mathcal{A})$ if and only if

  1. (i)

$h(x_{i})\geq h(x_{n})$ for $1\leq i\leq k$ and

  2. (ii)

$h(x_{j})\leq h(x_{n})$ for $k<j\leq n-1$.

###### Proof.

First we notice that every vector from $\mathcal{A}$ satisfies conditions (i)
and (ii), an so does its every positive multiple. It is also clear that the
sum of any two vectors complying with conditions (i) and (ii), satisfies them
too. The set of functions satisfying conditions (i) and (ii) is therefore a
cone that contains $\mathrm{cone}(\mathcal{A})$.

To verify that every $h$ satisfying (i) and (ii) is actually in
$\mathrm{cone}(\mathcal{A})$, we first notice that vectors
${\mathbb{I}_{\\{x_{j}\\}^{c}}}$ can be replaced by $-{\mathbb{I}_{x_{j}}}$,
as
$-{\mathbb{I}_{x_{j}}}={\mathbb{I}_{\\{x_{j}\\}^{c}}}-{\mathbb{I}_{\mathcal{X}}}$.
Now we take $\alpha_{n}=h(x_{n}),\alpha_{i}=h(x_{i})-h(x_{n})$ for $1\leq
i\leq k$ and $\alpha_{j}=h(x_{n})-h(x_{j})$, which gives

$\displaystyle h$
$\displaystyle=\sum_{i=1}^{k}\alpha_{i}{\mathbb{I}_{x_{i}}}+\sum_{j=k+1}^{n-1}\alpha_{j}(-{\mathbb{I}_{x_{j}}})+\alpha_{n}{\mathbb{I}_{\mathcal{X}}}$
(24)
$\displaystyle=\sum_{i=1}^{k}\alpha_{i}{\mathbb{I}_{x_{i}}}+\sum_{j=k+1}^{n-1}\alpha_{j}{\mathbb{I}_{\\{x_{j}\\}^{c}}}+\left(\alpha_{n}-\sum_{j=k+1}^{n-1}\alpha_{j}\right){\mathbb{I}_{\mathcal{X}}},$
(25)

where all $\alpha_{i}\geq 0$ for $1\leq i\leq n-1$. ∎

In the following text $f|_{A}\leq\alpha$ will state for $f(x)\leq\alpha$ for
every $x\in A$. We adopt analogous notation for other relations.

######  Definition 5.

Let $x\in\mathcal{X}$ and $A,B\subset\mathcal{X}$ be given such that
$A\neq\emptyset,B\neq\emptyset,x\not\in A\cup B$ and $A\cap B=\emptyset$. Then
we define the following set of vectors:

$N(x,A,B)=\\{f\in\mathbb{R}^{n}\colon f|_{A}\leq f(x)\leq
f|_{B},f|_{\mathcal{X}\backslash(A\cup B)}=f(x)\\}.$ (26)

######  Theorem 3.

Let $x\in\mathcal{X}$ and $A,B\subseteq\mathcal{X}$ be given such that
$A\neq\emptyset,B\neq\emptyset$ and $A\cap B=\emptyset$. Then the following
conditions hold:

  1. (i)

$N(x,A,B)$ is a cone.

  2. (ii)

A PRI model $(l,u)$ exists such that $N(x,A,B)$ is a normal cone of its credal
set.

  3. (iii)

If $A\cup B=\\{x\\}^{c}$, then $N(x,A,B)$ is MESC.

  4. (iv)

If $A^{\prime}\subseteq A,B^{\prime}\subseteq B$ then
$N(x,A^{\prime},B^{\prime})$ is a face of $N(x,A,B)$.

  5. (v)

$\mathrm{ri}(N(x,A,B))=\\{f\in\mathbb{R}^{n}\colon f_{A}\lneq f(x)\lneq
f|_{B},f|_{(A\cup B)^{c}}=f(x)\\}$.

  6. (vi)

For every vector $f\in\mathbb{R}^{n}$ and every $x\in\mathcal{X}$,
$f\in\mathrm{ri}(N(x,[x]^{f}_{+},[x]^{f}_{-}))$, where $[x]^{f}_{+}=\\{y\colon
f(y)>f(x)\\}$ and $[x]^{f}_{-}=\\{y\colon f(y)<f(x)\\}$, provided that neither
$[x]^{f}_{+}$ nor $[x]^{f}_{-}$ is empty. Moreover,
$f\in\mathrm{ri}(N(x,A,B))$ if and only if $A=[x]^{f}_{+}$ and
$B=[x]^{f}_{-}$.

  7. (vii)

Every vector $f\in\mathbb{R}^{n}$ belongs to at most $n-2$ cones of the form
(26).

  8. (viii)

Let $N(x,A,B)$ and a cone of the form $\mathrm{cone}(\mathcal{A})$, where
$\mathcal{A}$ is a maximal chain, be given. Then either
$\mathrm{ri}(\mathrm{cone}(\mathcal{A}))\subseteq N(x,A,B)$ or
$\mathrm{ri}(\mathrm{cone}(\mathcal{A}))\cap N(x,A,B)=\emptyset$.

  9. (ix)

Let ${\underline{E}}$ be the natural extension of a PRI model $(l,u)$. Then
${\underline{E}}$ is comonotonic additive.

  10. (x)

A 2-monotone lower probability $L$ exists that coincides with $(l,u)$ in the
sense that $L(\\{x\\})=l(x)$ and $L(\\{x\\}^{c})=1-u(x)$ for every
$x\in\mathcal{X}$ and whose natural extension coincides with the natural
extension of $(l,u)$.

###### Proof.

(i) is an immediate consequence of definitions and Corollary 7.

(ii) follows from Proposition 2(iv).

(iii) follows directly from Proposition 11.

(iv) the set $N(x,A^{\prime},B^{\prime})$ is clearly a subset of $N(x,A,B)$
where some inequality constraints are replaced by equalities. Hence,
$N(x,A^{\prime},B^{\prime})$ is a face of $N(x,A,B)$.

(v) Suppose $f\in N(x,A,B)$ and $f(y)=f(x)$ for some $y\in A$. Then $f\in
N(x,A\backslash\\{y\\},B)$ which by (iv) is a face of $N(x,A,B)$.

The relation $f\in\mathrm{ri}(N(x,[x]^{f}_{+},[x]^{f}_{-}))$ in (vi) is a
direct consequence of the construction and Corollary 7. It is also clear by
the definition that $f\in N(x,A,B)$ implies that $[x]^{f}_{+}\subseteq A$ and
$[x]^{f}_{-}\subseteq B$; however, if any of these set inclusions is strict,
then $N(x,[x]^{f}_{+},[x]^{f}_{-})$ is a proper face of $N(x,A,B)$, by (iv).
But an element cannot be contained in relative interiors of a polyhedron and
its proper face at the same time. Thus, the set inclusion must in fact be
equality relation.

We have that $[x]^{f}_{+}=\emptyset$ if $x=\arg\max_{x\in\mathcal{X}}f(x)$ and
$[x]^{f}_{-}=\emptyset$ if $x=\arg\in_{x\in\mathcal{X}}f(x)$. For those
choices of $x$, the cones of the form (26) therefore do not exist. So, cones
of this form only exist for at most $n-2$ choices of $x$, and for every such
choice only one such cone exists, by (vi), which consequently confirms (vii).

The set $\mathrm{ri}(\mathrm{cone}(\mathcal{A}))$ contains comonotone vectors
with strictly different components. Let some $x\in\mathcal{X}$ be given. It is
easy to see that any two such functions, say $f$ and $g$ satisfy
$[x]^{f}_{+}=[x]^{g}_{+}$ and $[x]^{f}_{-}=[x]^{g}_{-}$ and that
$[x]^{f}_{+}\cup[x]^{f}_{-}=\\{x\\}^{c}$, which makes
$N(x,[x]^{f}_{+},[x]^{f}_{-})$ the only cone of the form $N(x,A,B)$ that
contains $f$ and $g$, and with them the entire relative interior. Thus (viii)
is proved.

(ix) is a direct consequence of Proposition 6 and (viii).

(x) easily follows from Proposition 10 and (ix). ∎

###  5.2 Relating normal cones to extreme points

Normal cone structure described in the above proposition is closely related to
the extreme points of the credal sets corresponding the probability intervals.
Their characterization is known from the literature. Let $(l,u)$ be a
probability interval model on $\mathcal{X}$, $\mathcal{M}$ its credal set and
$h\in\mathbb{R}^{n}$ a vector. Let $P$ be a the extremal linear prevision such
that $P(h)=\min_{P\in\mathcal{M}}P(h)$. To construct $P$, let
$x_{1},\ldots,x_{n}$ be an enumeration of the elements of $\mathcal{X}$ such
that $h(x_{i})\leq h(x_{i+1})$. Let $k$ be an index such that

$l(x_{k})\leq 1-\sum_{i=k+1}^{n}l(x_{i})-\sum_{i=1}^{k-1}u(x_{i})\leq
u(x_{k}).$ (27)

Then take

$P(x_{i})=\begin{cases}u(x_{i}),&i<k;\\\ l(x_{i}),&i>k;\\\
1-\sum_{i=1}^{k}u(x_{i})-\sum_{i=k+1}^{n}l(x_{i}),&i=k.\end{cases}$ (28)

The proof that so defined $P$ minimizes $P(h)$ over $\mathcal{M}$ can be found
in [6]. Denote $A=\\{x_{k+1},\ldots,x_{n}\\}$ and
$B=\\{x_{1},\ldots,x_{k-1}\\}$. It follows directly from the construction that
given another vector $h^{\prime}$, the minimizing $P$ is the same whenever the
induced sets $A$ and $B$ are the same for $h$ and $h^{\prime}$. In our terms
of normal cones, such vectors $h$ and $h^{\prime}$ both lie in the same normal
cone $N(x_{k},A,B)$.

######  Remark 2.

The case where $k$ satisfying equation (27) equals 1 or $n$, deserves an
additional illumination. These two cases correspond to the cones of the form
$N(x,\emptyset,B)$ and $N(x,A,\emptyset)$ respectively, which have been shown
not to be maximal elementary simplicial cones. The cases can be treated in a
symmetric way; therefore, we only consider the case $k=1$. Equation (27) then
gives that $l(x_{1})\leq 1-\sum_{i=2}^{n}l(x_{i})\leq u(x_{1})$, which for
coherent PRI model can only be satisfied if
$1-\sum_{i=2}^{n}l(x_{i})=u(x_{1})$. It follows that
$l(x_{2})=1-u(x_{1})-\sum_{i=3}^{n}l(x_{i})$. Hence, $k=2$ also satisfies
(27). The cone corresponding to this case is
$N(x_{2},\\{x_{3},\ldots,x_{n}\\},\\{x_{1}\\})$, which is clearly a proper
subcone of $N(x_{1},\\{x_{2},\ldots,x_{n}\\},\emptyset)$, thus confirming that
the latter is not elementary. In general, the cone of the form
$N(x,\emptyset,B)$ is a simplicial complex of cones
$N(y,\\{x\\},B\backslash\\{y\\})$ with non-intersecting interiors.

###  5.3 Graph structure of the normal cones corresponding to PRI models

We now analyze the adjacency relations for the family of cones of the form
$N(x,A,B)$. The cone of this form is generated by the indicator functions of
the family of sets

$\mathcal{A}=\\{\\{z\\}\colon z\in B\\}\cup\\{\\{v\\}^{c}\colon v\in
A\\}\cup\\{\mathcal{X}\\}.$ (29)

The adjacent cones are formed by selecting an element of $\mathcal{A}$ and
replacing it by a suitable set to form a new cone. Not all candidates produce
adjacent cones, though. To select those that do, we will make use of Lemma 1.
Assume for the moment that $|A|,|B|>1$. We will return to the borderline cases
later. Take some $y\in A$ and consider possible candidates for the replacement
of $\\{y\\}^{c}\in\mathcal{A}$. These are $\\{y\\},\\{x\\}$ and $\\{x\\}^{c}$.
To see which induce adjacent cones, calculate the normal vector $t$ to the
hyperplane $\mathrm{lin}(\mathcal{A}\backslash\\{\\{y\\}^{c}\\})$ and denote
its elements by $t(x)$ for $x\in\mathcal{X}$. For every $\\{x\\}$,
${\mathbb{I}_{x}}\cdot t=0$ implies that $t(x)=0$. Similarly,
$t\cdot{\mathbb{I}_{\\{x\\}^{c}}}=t\cdot({\mathbb{I}_{\mathcal{X}}}-{\mathbb{I}_{x}})=-t\cdot{\mathbb{I}_{x}}$,
because of $\mathcal{X}\in\mathcal{A}\backslash\\{\\{y\\}^{c}\\}$, implies
$t(x)=0$ as well. Thus, because of $t\cdot{\mathbb{I}_{\mathcal{X}}}=0$, we
have that $t(y)+t(x)=0$. Take the solution where $t(x)=1$ and $t(y)=-1$. Since
${\mathbb{I}_{\\{y\\}^{c}}}\cdot t=1$, the scalar product of the new vector
with $t$ must be negative. The products of the candidates identified above are
the following: ${\mathbb{I}_{y}}\cdot t=-1,{\mathbb{I}_{x}}\cdot
t=1,{\mathbb{I}_{\\{x\\}^{c}}}\cdot t=-1$. Thus the candidates that induce
adjacent cones are $\\{y\\}$ and $\\{x\\}^{c}$, which gives us the following
adjacent cones

  1. (A1)

$N(x,A\backslash\\{y\\},B\cup\\{y\\})$,

  2. (A2)

$N(y,(A\backslash\\{y\\})\cup\\{x\\},B)$.

Let us now consider the case of $z\in B$, where $\\{z\\}\in\mathcal{A}$. The
candidates to replace $\\{z\\}$ are again $\\{z\\}^{c},\\{x\\}$ and
$\\{x\\}^{c}$. The same analysis as above now gives us a normal vector $t$,
such that $t(x)=1$ and $t(z)=-1$. Now we have that
$t\cdot{\mathbb{I}_{z}}=-1$, whence the candidates with positive scalar
product are those inducing adjacent cones. We have
${\mathbb{I}_{\\{z\\}^{c}}}\cdot t=1,{\mathbb{I}_{x}}\cdot
t=1,{\mathbb{I}_{\\{x\\}^{c}}}\cdot t=-1$. Now $\\{z\\}^{c}$ and $\\{x\\}$
fit, inducing the cones:

  1. (B1)

$N(x,A\cup\\{z\\},B\backslash\\{z\\})$,

  2. (B2)

$N(z,A,(B\backslash\\{z\\})\cup\\{x\\})$.

Now, in the case where $|A|=1$, only (A2) is possible in the first case, while
(B2) is the only possible neighbour if $|B|=1$.

In particular case of a PRI model $(l,u)$, only one of adjacent cones (A1) or
(A2) and (B1) or (B2) respectively corresponds to an extreme point. Let us
again first consider the case of $y\in A$. Whether the adjacent cone is (A1)
or (A2) depends on which $x$ or $y$ satisfies condition (27) in place of
$x_{k}$. The fact that $N(x,A,B)$ corresponds to an extreme point, implies
that

$l(x)\leq 1-\sum_{v\in A}l(v)-\sum_{z\in B}u(z)\leq u(x).$ (30)

Because of $y\in A$, it easily follows that

$l(y)\leq 1-\sum_{v\in(A\backslash\\{y\\})\cup\\{x\\}}l(v)-\sum_{z\in B}u(z),$
(31)

which corresponds to replacing $y$ with $x$ in $A$, as in the case of (A2). On
the other hand, we can either have

$l(x)\leq 1-\sum_{v\in A\backslash\\{y\\}}l(v)-\sum_{z\in B\cup\\{y\\}}u(z),$
(32)

which is equivalent to

$1-\sum_{v\in(A\backslash\\{y\\})\cup\\{x\\}}l(v)-\sum_{z\in B}u(z)\geq u(y).$
(33)

or the opposite inequalities in both equations. If the first inequality holds,
then (A1) is the cone corresponding to an extreme point, because $x$ is the
element satisfying (27). In the opposite case, where

$1-\sum_{v\in(A\backslash\\{y\\})\cup\\{x\\}}l(v)-\sum_{z\in B}u(z)\leq u(y),$
(34)

condition (27) is satisfied by $y$ and therefore (A2) corresponds to an
extreme point.

Now take some $z\in B$. Again, equation (30) implies

$1-\sum_{y\in A}l(y)-\sum_{v\in(B\backslash\\{z\\})\cup\\{x\\}}u(z)\leq u(z),$
(35)

corresponding to replacing $z$ with $x$ in $B$. Furthermore, we have the
following pair of equivalent equations

$1-\sum_{y\in A\cup\\{z\\}}l(y)-\sum_{v\in(B\backslash\\{z\\})}u(z)\leq u(x)$
(36)

and

$l(z)\geq 1-\sum_{y\in A}l(y)-\sum_{v\in(B\backslash\\{z\\})\cup\\{x\\}}u(z).$
(37)

If (36) holds, then (B1) corresponds to an extreme point and in the case of
the opposite inequality

$l(z)\leq 1-\sum_{y\in A}l(y)-\sum_{v\in(B\backslash\\{z\\})\cup\\{x\\}}u(z),$
(38)

(B2) corresponds to an extreme point.

Let us now summarize.

######  Theorem 4.

Let a cone of the form $N(x,A,B)$ correspond to an extreme point of a PRI
model $(l,u)$.

  1. (i)

The adjacent cones are then exactly the cones of the form

     * •

(A2) for every $y\in A$;

     * •

if $|A|>1$, (A1) for every $y\in A$;

     * •

(B2) for every $z\in B$;

     * •

if $|B|>1$, (B1) for every $z\in B$.

  2. (ii)

For a given $y\in A$, (A1) corresponds to an extreme point if (32) is
satisfied; and (A2) corresponds to an extreme point if (34) is satisfied.

  3. (iii)

For a given $z\in B$, (B1) corresponds to an extreme point if (36) is
satisfied; and (B2) corresponds to an extreme point if (38) is satisfied.

######  Remark 3.

The borderline case in the above theorem is if both (32) and (34) or (36) and
(38) are satisfied. This case corresponds to the situation where the two cones
correspond to different possible triangulations of the same normal cone.

###  5.4 Maximal number of extreme points

In this section we estimate the possible maximal number of extreme points of
credal sets of PRI models. By Proposition 2 (iv), every MESC is a normal cone
of some convex set corresponding to an extreme point. In general however, a
normal cone in an extreme point can be triangulized as a union of MESCs. Thus,
the maximal number of extreme points of a credal set is bounded by the number
of MESCs corresponding to a complete simplicial fan obtained as a
triangulation of the normal fan of the credal set. Moreover, by Theorem
3(viii), every cone generated by a maximal chain is contained in a single MESC
corresponding to credal set of a PRI model. As the number of maximal chains is
known to be equal to $n!$, the number of MESCs and therefore the maximal
number of extreme points can be estimated from the number of the chain
generated cones contained in the MESCs. We start with the following simple
result.

######  Proposition 12.

A cone of the form $N(x,A,B)$ contains exactly $|A|!\cdot|B|!$ cones of the
form $\mathrm{cone}(\mathcal{A})$, where $\mathcal{A}$ is a maximal chain.

###### Proof.

By Corollary 5, there is a one-to-one correspondence between comonotone
classes and chains, and thus also between maximal comonotone classes and
maximal chains. Further, a maximal comonotone classes correspond to strict
linear orderings in $\mathcal{X}$. A cone of the form $N(x,A,B)$ contains all
functions $f$ satisfying $f|_{A}\leq f(x)\leq f|_{B}$. This induces a partial
ordering $A\preceq x\preceq B$, which is compatible with exactly $|A|!$
orderings of $A$ and $|B|$ complete orderings in $B$, which gives exactly
$|A|!\cdot|B|!$ distinct complete orderings. ∎

######  Corollary 8.

The number $m$ of distinct MESCs in the triangulation of a normal cone of a
credal set corresponding to PRI models on a set $\mathcal{X}$ with $n$
elements satisfies the following inequality

$\frac{n!}{(n-2)!}=n(n-1)\leq
m\leq\frac{n!}{\left\lfloor\frac{n-1}{2}\right\rfloor\cdot\left\lceil\frac{n-1}{2}\right\rceil}.$
(39)

###### Proof.

By Proposition 12, the number of maximal comonotone cones contained within a
MESC is between $(n-2)!$ and
$\left\lfloor\frac{n-1}{2}\right\rfloor\cdot\left\lceil\frac{n-1}{2}\right\rceil$,
which readily implies the proposed bounds. ∎

The following examples demonstrate that both bounds are reachable.

######  Example 3.

Let $n=|\mathcal{X}|=10$ and set $l(x)=\frac{1}{11}$ and $u(x)=\frac{1}{9}$
for every $x\in\mathcal{X}$. Let $x_{1},\ldots,x_{10}$ be an ordering of the
elements. Taking $k=5$ we have that
$1-\sum_{6}^{10}\frac{1}{11}-\sum_{1}^{4}\frac{1}{9}=1-\frac{5}{11}-\frac{4}{9}=\frac{10}{99}\in\left[\frac{1}{11},\frac{1}{9}\right]$.
Hence, $x_{5}$ satisfies (27), and therefore $A=\\{x_{6},\ldots,x_{10}\\}$ and
$B=\\{x_{1},\ldots,x_{4}\\}$, and every cone $N(x,A,B)$ then satisfies $|A|=5$
and $|B|=4$. It then contains $5!\cdot 4!=2880$ maximal comonotone cones, and
therefore the number of all distinct MESCs is $\frac{10!}{5!\cdot 4!}=1260$,
which is then equal to the number of extreme points. Moreover, this is the
maximal number of extreme points for a credal set corresponding to a PRI model
on 10 elements.

######  Example 4.

Let this time $n=|\mathcal{X}|=10$ and set $l(x)=\frac{1}{20}$ and
$u(x)=\frac{1}{9}$ for every $x\in\mathcal{X}$. Given an ordering
$x_{1},\ldots,x_{10}$ of elements of $\mathcal{X}$, it turns out that $x_{9}$
is exactly the element satisfying (27). Due to symmetry, we can conclude that
every MESC in this case is of the form $N(x,A,B)$ where $|A|=1$ and $|B|=8$.
By Proposition 12, all of them contain exactly $8!=40320$ maximal comonotone
cones. The number of cones must therefore be exactly $\frac{10!}{8!}=90$,
which coincides with the lower bound in Corollary 8.

######  Remark 4.

The last inequality in (39) is known from the literature, and can be found in
[6], where the same estimate for the number of extreme points of PRI on 10
points is also reported as an example.

##  6 Conclusions

Normal cones prove to be a useful tool for better understanding of credal sets
and numerical procedures related to them. The goal of this paper is to provide
a comprehensive description of the structure of normal cones corresponding to
credal sets of lower probabilities. General properties introduced in the first
part were then used to give a detailed description of the normal cone
structure for two important families of imprecise probabilities, 2-monotone
lower probabilities and probability intervals.

The methods proposed in this paper will serve to supplement and improve the
existing results making use of the methods based on normal cones. Models whose
analysis has been shown to benefit from such approach are computations related
to imprecise stochastic processes, especially those in continuous time.
Another area within the theory of imprecise probabilities that is still
largely unexplored is the sensitivity analysis of lower probabilities to
perturbations. The better understanding of the structure of the corresponding
credal sets based on approaches presented in this paper could help with such
analysis within our future research. Exploration of other important classes of
lower probabilities, such as $p$-boxes and their multivariate generalizations,
could also benefit from the here proposed approach.

## Acknowledgement

The author acknowledges the financial support from the Slovenian Research
Agency (research core funding No. P5-0168).

## References

  * Abellan et al. [2018] Joaquin Abellan, Carlos J Mantas, Javier G Castellano, and SerafIn Moral-Garcia.  Increasing diversity in random forest learning algorithm via imprecise probabilities.  _Expert Systems with Applications_ , 97:228–243, 2018.
  * Antonucci and Cuzzolin [2010] Alessandro Antonucci and Fabio Cuzzolin.  Credal sets approximation by lower probabilities: Application to credal networks.  In Eyke Hüllermeier, Rudolf Kruse, and Frank Hoffmann, editors, _Computational Intelligence for Knowledge-Based Systems Design_ , pages 716–725, Berlin, Heidelberg, 2010. Springer Berlin Heidelberg.  ISBN 978-3-642-14049-5.
  * Augustin et al. [2014] Thomas Augustin, Frank PA Coolen, Gert de Cooman, and Matthias CM Troffaes.  _Introduction to imprecise probabilities_.  John Wiley & Sons, 2014.
  * Bradley [2019] Seamus Bradley.  Imprecise probabilities.  In _Computer Simulation Validation_ , pages 525–540. Springer, 2019\.
  * Bronevich and Augustin [2009] Andrew Bronevich and Thomas Augustin.  Approximation of coherent lower probabilities by 2-monotone measures.  In Thomas Augustin, Frank P. A. Coolen, Serafín Moral, and Matthias C. M. Troffaes, editors, _ISIPTA’09: Proceedings of the Sixth International Symposium on Imprecise Probability: Theories and Applications_ , pages 61–70, Durham, UK, July 2009. SIPTA.
  * Campos et al. [1994] L.M. De Campos, J.F. Huete, and S. Moral.  Probability intervals: a tool for uncertain reasoning.  _International Journal of Uncertainty, Fuzziness and Knowledge-Based Systems_ , 2(2), 1994.
  * Chateauneuf and Jaffray [1989] Alain Chateauneuf and Jean-Yves Jaffray.  Some characterizations of lower probabilities and other monotone capacities through the use of möbius inversion.  _Mathematical social sciences_ , 17(3):263–283, 1989.
  * Coolen [2004] FPA Coolen.  On the use of imprecise probabilities in reliability.  _Quality and Reliability Engineering International_ , 20(3):193–202, 2004.
  * De Bock [2017] Jasper De Bock.  The limit behaviour of imprecise continuous-time Markov chains.  _Journal of Nonlinear Science_ , 27(1):159–196, 2017.
  * de Cooman et al. [2009] Gert de Cooman, Filip Hermans, and Erik Quaeghebeur.  Imprecise Markov chains and their limit behavior.  _Probability in the Engineering and Informational Sciences_ , 23(4):597–635, 2009.  ISSN 0269-9648.  doi: 10.1017/S0269964809990039.
  * De Loera et al. [2010] Jesús De Loera, Jörg Rambau, and Francisco Santos.  _Triangulations: structures for algorithms and applications_ , volume 25.  Springer Science & Business Media, 2010.
  * Dempster [2008] Arthur P Dempster.  Upper and lower probabilities induced by a multivalued mapping.  In _Classic works of the Dempster-Shafer theory of belief functions_ , pages 57–72. Springer, 2008.
  * Denneberg [1994] Dieter Denneberg.  _Non-additive measure and integral_ , volume 27.  Springer Science & Business Media, 1994.
  * Dolžan et al. [2022] David Dolžan, Damjana Kokol Bukovšek, Matjaž Omladič, and Damjan Škulj.  Some multivariate imprecise shock model copulas.  _Fuzzy Sets and Systems_ , 428:34–57, 2022.
  * Erreygers et al. [2018] Alexander Erreygers, Cristina Rottondi, Giacomo Verticale, and Jasper De Bock.  Imprecise Markov models for scalable and robust performance evaluation of flexi-grid spectrum allocation policies.  _IEEE Transactions on Communications_ , 66(11):5401–5414, 2018.
  * Gruber [2007] Peter Gruber.  _Convex and Discrete Geometry_.  Springer-Verlag Berlin Heidelberg, 2007.  doi: 10.1007/978-3-540-71133-9.  URL http://dx.doi.org/10.1007/978-3-540-71133-9.
  * Grünbaum et al. [2003] B. Grünbaum, V. Kaibel, V. Klee, and G.M. Ziegler.  _Convex Polytopes_.  Graduate Texts in Mathematics. Springer, 2003.  ISBN 9780387404097.
  * [18] Joseph Gubeladze and Winfried Bruns.  _Polytopes, Rings, and K-Theory_.  Springer Monographs in Mathematics.  ISBN 978-0-387-76355-2.  doi: 10.1007/b105283.
  * Jansen et al. [2017] Christoph Jansen, Georg Schollmeyer, and Thomas Augustin.  Concepts for decision making under severe uncertainty with partial ordinal and partial cardinal preferences.  In _Proceedings of the tenth international symposium on imprecise probability: theories and applications_ , pages 181–192. PMLR, 2017\.
  * Jensen [2007] Anders Nedergaard Jensen.  A non-regular grobner fan.  _Discrete & Computational Geometry_, 37(3):443–453, 2007.
  * Khakzad [2019] Nima Khakzad.  System safety assessment under epistemic uncertainty: Using imprecise probabilities in bayesian network.  _Safety science_ , 116:149–160, 2019.
  * Krak et al. [2017] Thomas Krak, Jasper De Bock, and Arno Siebes.  Imprecise continuous-time Markov chains.  _International Journal of Approximate Reasoning_ , 88:452–528, 2017.
  * Lu and Robinson [2008] Shu Lu and Stephen M Robinson.  Normal fans of polyhedral convex sets.  _Set-Valued Analysis_ , 16(2):281–305, 2008.
  * Miranda [2008] Enrique Miranda.  A survey of the theory of coherent lower previsions.  _International Journal of Approximate Reasoning_ , 48(2):628 – 658, 2008.  ISSN 0888-613X.  doi: DOI:10.1016/j.ijar.2007.12.001.  In Memory of Philippe Smets (1938-2005).
  * Miranda and Destercke [2015] Enrique Miranda and Sébastien Destercke.  Extreme points of the credal sets generated by comparative probabilities.  _Journal of Mathematical Psychology_ , 64–-65:44 – 57, 2015.  ISSN 0022-2496.  doi: http://dx.doi.org/10.1016/j.jmp.2014.11.004.  URL http://www.sciencedirect.com/science/article/pii/S0022249614000820.
  * Miranda and Montes [2018] Enrique Miranda and Ignacio Montes.  Shapley and banzhaf values as probability transformations.  _International Journal of Uncertainty, Fuzziness and Knowledge-Based Systems_ , 26(06):917–947, 2018.
  * Miranda et al. [2003] Enrique Miranda, Inés Couso, and Pedro Gil.  Extreme points of credal sets generated by 2-alternating capacities.  _International Journal of Approximate Reasoning_ , 33(1):95–115, 2003.
  * Montes et al. [2014] Ignacio Montes, Enrique Miranda, and Susana Montes.  Decision making with imprecise probabilities and utilities by means of statistical preference and stochastic dominance.  _European Journal of Operational Research_ , 234(1):209–220, 2014.
  * Montes et al. [2018] Ignacio Montes, Enrique Miranda, and Paolo Vicig.  2-monotone outer approximations of coherent lower probabilities.  _International Journal of Approximate Reasoning_ , 101:181–205, 2018.
  * Nau [2011] Robert Nau.  Imprecise probabilities in non-cooperative games.  In _Proceedings of ISIPTA_ , pages 297–306. Citeseer, 2011.
  * Oberguggenberger et al. [2009] Michael Oberguggenberger, Julian King, and Bernhard Schmelzer.  Classical and imprecise probability methods for sensitivity analysis in engineering: A case study.  _International Journal of Approximate Reasoning_ , 50(4):680–693, 2009.
  * Omladič and Škulj [2020] Matjaž Omladič and Damjan Škulj.  Constructing copulas from shock models with imprecise distributions.  _International Journal of Approximate Reasoning_ , 118:27–46, 2020.
  * Omladič and Stopar [2020a] Matjaž Omladič and Nik Stopar.  Final solution to the problem of relating a true copula to an imprecise copula.  _Fuzzy sets and systems_ , 393:96–112, 2020a.
  * Omladič and Stopar [2020b] Matjaž Omladič and Nik Stopar.  A full scale sklar’s theorem in the imprecise setting.  _Fuzzy Sets and Systems_ , 393:113–125, 2020b.
  * Pearl [1988] Judea Pearl.  On probability intervals.  _International Journal of Approximate Reasoning_ , 2(3):211–216, 1988.
  * Pelessoni and Vicig [2003] Renato Pelessoni and Paolo Vicig.  Convex imprecise previsions.  _Reliable Computing_ , 9(6):465–485, 2003.
  * Quaeghebeur [2022] Erik Quaeghebeur.  Introduction to the theory of imprecise probability.  In _Uncertainty in Engineering_ , pages 37–50. Springer, Cham, 2022\.
  * Quost and Destercke [2018] Benjamin Quost and Sébastien Destercke.  Classification by pairwise coupling of imprecise probabilities.  _Pattern Recognition_ , 77:412–425, 2018.
  * Rockafellar [1970] R.T. Rockafellar.  _Convex Analysis_.  Princeton Landmarks in Mathematics and Physics. Princeton University Press, 1970.  ISBN 9780691015866.
  * Schmeidler [1986] D. Schmeidler.  Integral representation without additivity.  _Proceedings of the American Mathematical Society_ , 97:255–261, 1986.
  * Shafer [1987] Glenn Shafer.  Belief functions and possibility measures.  In _Anal of Fuzzy Inf_ , pages 51–84. CRC Press Inc, 1987.
  * Škulj [2017] Damjan Škulj.  Perturbation bounds and degree of imprecision for uniquely convergent imprecise Markov chains.  _Linear Algebra and its Applications_ , 533:336–356, 2017\.
  * Škulj [2019] Damjan Škulj.  Errors bounds for finite approximations of coherent lower previsions on finite probability spaces.  _International Journal of Approximate Reasoning_ , 105:98–111, 2019.
  * Smets [1993] Philippe Smets.  Belief functions: the disjunctive rule of combination and the generalized bayesian theorem.  _International Journal of approximate reasoning_ , 9(1):1–35, 1993.
  * Sundberg and Wagner [1992] Carl Sundberg and Carl Wagner.  Characterizations of monotone and 2-monotone capacities.  _Journal of Theoretical Probability_ , 5(1):159–167, 1992.
  * Troffaes [2007] Matthias CM Troffaes.  Decision making under uncertainty using imprecise probabilities.  _International journal of approximate reasoning_ , 45(1):17–29, 2007.
  * Troffaes and De Cooman [2014] Matthias CM Troffaes and Gert De Cooman.  _Lower previsions_.  John Wiley & Sons, 2014.
  * Utkin [2019] Lev V Utkin.  An imprecise extension of SVM-based machine learning models.  _Neurocomputing_ , 331:18–32, 2019.
  * Utkin and Coolen [2007] Lev V Utkin and Frank PA Coolen.  Imprecise reliability: an introductory overview.  _Computational intelligence in reliability engineering_ , pages 261–306, 2007.
  * Utkin et al. [2020] Lev V Utkin, Maxim S Kovalev, and Frank PA Coolen.  Imprecise weighted extensions of random forests for classification and regression.  _Applied Soft Computing_ , 92:106324, 2020.
  * Vicig [2008] Paolo Vicig.  Financial risk measurement with imprecise probabilities.  _International Journal of Approximate Reasoning_ , 49(1):159–174, 2008.
  * Škulj [2009] Damjan Škulj.  Discrete time Markov chains with interval probabilities.  _International Journal of Approximate Reasoning_ , 50(8):1314–1329, sep 2009.  ISSN 0888-613X.  doi: 10.1016/j.ijar.2009.06.007.  URL http://dx.doi.org/10.1016/j.ijar.2009.06.007.
  * Škulj [2015] Damjan Škulj.  Efficient computation of the bounds of continuous time imprecise Markov chains.  _Applied Mathematics and Computation_ , 250(0):165 – 180, jan 2015.  ISSN 0096-3003.  doi: http://dx.doi.org/10.1016/j.amc.2014.10.092.  URL http://www.sciencedirect.com/science/article/pii/S0096300314014672.
  * Škulj [2020] Damjan Škulj.  Computing bounds for imprecise continuous-time markov chains using normal cones.  In Massimiliano Vasile and Domenico Quagliarella, editors, _Advances in Uncertainty Quantification and Optimization Under Uncertainty with Aerospace Applications: Proceedings of the 2020 Uqop International Conf_ , 2020.
  * Škulj [2022] Damjan Škulj.  Application of normal cones to computing bounds for imprecise continuous-time markov chains.  Submitted, 2022.
  * Walley [1991] Peter Walley.  _Statistical Reasoning with Imprecise Probabilities_.  Chapman and Hall, London, New York, 1991.
  * Wallner [2007] Anton Wallner.  Extreme points of coherent probabilities in finite spaces.  _International Journal of Approximate Reasoning_ , 44(3):339 – 357, 2007.  ISSN 0888-613X.  doi: http://dx.doi.org/10.1016/j.ijar.2006.07.017.  URL http://www.sciencedirect.com/science/article/pii/S0888613X06001010.
  * Weichselberger [2001] K. Weichselberger.  _Elementare Grundbegriffe einer allgemeineren Wahrscheinlichkeitsrechnung. I: Intervallwahrscheinlichkeit als umfassendes Konzept._ Physica-Verlag, Heidelberg, 2001.
  * Yu et al. [2016] Lanting Yu, Sébastien Destercke, Mohamed Sallak, and Walter Schon.  Comparing system reliabilities with ill-known probabilities.  In _International Conference on Information Processing and Management of Uncertainty in Knowledge-Based Systems_ , pages 619–629. Springer, 2016.
  * Zhang and Shields [2020] Jiaxin Zhang and Michael Shields.  On the quantification and efficient propagation of imprecise probabilities with copula dependence.  _International Journal of Approximate Reasoning_ , 122:24–46, 2020.
  * Ziegler [2012] G.M. Ziegler.  _Lectures on Polytopes_.  Graduate Texts in Mathematics. Springer New York, 2012.  ISBN 9780387943657.