Damien Regnault

Nicolas Schabanel

Eric Thierry

A study of stochastic 2D Minority CA: Would wearing stripes be a fatality for snob people?

Keywords: stochastic cellular automata, asynchronism, minority rule automate cellulaire stochastique, asynchronisme, automate minorité

Cellular automata are usually associated with synchronous deterministic dynamics, and their asynchronous or stochastic versions have been far less studied although relevant for modeling purposes. The study of their asynchronous dynamics is all the more needed that their asynchronous behaviors are drastically different from their synchronous ones. This paper analyzes the dynamics of a two-dimensional cellular automaton, 2D Minority, under fully asynchronous dynamics, where only one random cell updates at each time step. This cellular automaton is of particular interest in computer science, biology or social science for instance, and already presents a rich variety of behaviors although the apparent simplicity of its transition rule. In particular, it captures some important features, like the emergence of striped patterns, which are common, according to experiments, to other important automata, such as Game of Life. In this paper, we present a mathematical analysis of the first steps and the last steps of the asynchronous dynamics of 2D Minority. Our results are based on the definition of an interaction energy and rely on the analysis of the dynamics of the borders between competing regions. Our results are a first step towards a complete analysis of this stochastic cellular automaton. Many questions remain open: in particular describing mathematically the middle part of the evolution of 2D Minority where many regions compete with each other, or defining similar parameters (energy, borders,...) for other automata (such as Game of Life) that present similarities with 2D Minority in their asynchronous behaviors.

Life a random Totalistic Minority

Synchronous dynamics Fully asynchronous dynamics Figure 1: Some examples of 2D cellular automata where similar stripes emerge in asynchronous regime even if their synchronous behavior differ drastically.

Introduction

In this paper, we study the behavior of a classical two-dimensional cellular automaton called 2D Minority in a stochastic version introducing asynchronism in the dynamics.

A cellular automaton consists in a set of cells which interact by updating their states according to local transition rules; a typical example is the famous Game of Life. In the literature, cellular automata have been both studied as a model of computation presenting massive parallelism, and used to model phenomena in physics, social sciences, biology... When viewed as a computational model, cellular automata have been mainly studied under synchronous dynamics (at each time step, all the cells update simultaneously). However models for real systems rarely fulfill this assumption and the cell updates rather occur in an asynchronous mode often described by stochastic processes.

Cellular automata under asynchronous updates and in stochastic versions have been far less studied than their synchronous deterministic counterparts. One must mention several important works concerning the ergodicity of deterministic cellular automata subject to random noise, including Toom et al work [START_REF] Toom | Nonergodic multidimensional systems of automata[END_REF][START_REF] Toom | Stochastic Cellular Systems: Ergodicity, Memory, Morphogenesis, chapter Discrete local Markov systems[END_REF][START_REF] Toom | Cellular automata with errors: Problems for students of probability[END_REF] and Gács et al work [START_REF] Gács | Reliable computation with cellular automata[END_REF][START_REF] Gray | A reader's guide to gacs's 'positive rates' paper[END_REF][START_REF] Park | Ergodicity and mixing rate of one-dimensional cellular automata[END_REF]. They study some necessary and some sufficient conditions of ergodicity, and state some undecidability results about it. Non-ergodicity can be interpreted as resilience to noise which is not necessarily the same as resilience to asynchronism.

Over the past 20 years, many empirical studies [START_REF] Bersini | Asynchrony induces stability in cellular automata based models[END_REF][START_REF] Buvel | Structure in asynchronous cellular automata[END_REF][START_REF] Fatès | An experimental study of robustness to asynchronism for elementary cellular automata[END_REF][START_REF] Huberman | Evolutionary games and computer simulations[END_REF][START_REF] Kanada | Asynchronous 1d cellular automata and the effects of fluctuation and randomness[END_REF][START_REF] Lumer | Synchronous versus asynchronous dynamics in spatially distributed systems[END_REF][START_REF] Schönfisch | Synchronous and asynchronous updating in cellular automata[END_REF] have been carried out showing that the behavior of a cellular automaton may widely vary when introducing asynchronism. The few mathematical analyses of the effects of asynchronism focus on onedimensional probabilistic cellular automata, either on single examples like [START_REF] Fukś | Non-deterministic density classification with diffusive probabilistic cellular automata[END_REF][START_REF] Fuks | Probabilistic cellular automata with conserved quantities[END_REF] or on specific classes like [START_REF] Fatès | Asynchronous behaviour of double-quiescent elementary cellular automata[END_REF][START_REF] Fatès | Asynchronous behaviour of double-quiescent elementary cellular automata[END_REF]. In comparison the case of two-dimensional cellular automata has not been much addressed and providing analyses of 2D "classic" rules remains a real challenge. Fig. 1 illustrates for three classical 2D cellular automata the differences between the synchronous dynamics and the fully asynchronous dynamics where only one random cell updates at each time step: typical configurations are given for Game of Life, a random outer totalistic automaton1 and 2D Minority.

In this paper, we choose to tackle the analysis for 2D Minority under fully asynchronous α = 1 α = 0.95 α = 0.75 α = 0.5 α = 0.25 α = 0

Step 50 dynamics, where each updated cell is given the minority state among its eight closest neighbors and itself. This threshold cellular automaton is of particular interest in computer science (for instance to compute a coloring minimizing interferences in some frequency allocation problems), in biology (when the expression of a gene inhibits its expression in the neighboring cells), or in social science (study of people who tries to mark difference from their neighbors, i.e., snob people). Minority is also a good start for building a theory. First, although the apparent simplicity of the rule, it already presents a rich variety of behaviors. It captures important features, such as the emergence of "striped patterns", observed on a lot of other more complex automata. Moreover when simulating a continuous range of asynchronism from full asynchronism to full synchronism thanks to the α-asynchronous dynamics where each cell independently updates with probability 0 < α 1 at each time step, 2D Minority exhibits a phase transition illustrated on Fig. 2 by a abrupt change of patterns when α goes from 0,5 to 0,75 (α = 0 refers to full asynchronism and then one step correspond to N minority updates). Second, this automaton is simple enough to hope to prove indeed something, and since it shares some remarkable features with many different automata under full asynchronism, like the "stripe patterns", there are some chances that the tools developed here may apply to other more complex automata as well. This paper provides an analysis of the first steps and last steps of the fully asynchronous dynamics. We manage to prove how final stable (horizontally or vertically) striped configurations are reached almost surely from some specific but typical initial configurations, and we provide bounds on the relaxation time (i.e. the expected time to reach such fixed points). The analysis is based on an energy function which give insights into the drift of the random process and its speed, and on a decomposition of configurations which indicates how the emerging patterns are organized. We also present some questions left open in analysis of this challenging automaton.

Definitions and preliminary results

We consider in this paper the 2D 2-states cellular automaton Minority under fully asynchronous dynamics over finite configurations with periodic boundary conditions.

Configuration.

We are given two positive integers n and m. We denote by U = Z/nZ × Z/mZ the set of cells and Q = {0, 1} the set of states (0 stands for white and 1 for black in the figures). We consider the Moore neighborhood: two cells (i, j) and (k, l) are neighbors if max(|i-k| n , |j -l| m ) 1 (where |i-j| p denotes the distance in Z/pZ). A n×m-configuration c is a function c : U → Q; c ij is the state of the cell (i, j) in configuration c. Stochastic 2D Minority. We consider the following fully asynchronous dynamics of 2D Minority. Time is discrete and let c t denote the configuration at time t; c 0 is the initial configuration. The configuration at time t + 1 is a random variable defined by the following process: a cell (i, j) is selected uniformly at random in U and its states is updated to the minority state in its neighborhood (we say that cell (i, j) fires at time t), all the other cells remains in their current state:

c t+1 ij =    1 if (c t ij +c t i-1,j + c t i+1,j + c t i,j-1 + c t i,j+1 +c t i-1,j+1 + c t i-1,j-1 + c t i+1,j-1 + c t i+1,j+1
) 4 0 otherwise and c t+1 kl = c t kl for all (k, l) = (i, j). A cell is said active if its state changes when fired.

Experiments. Like other 2D automata (such as Game of Life [START_REF] Bersini | Asynchrony induces stability in cellular automata based models[END_REF][START_REF] Fatès | Perturbing the topology of the game of life increases its robustness to asynchrony[END_REF]), the asynchronous behavior of 2D Minority differs radically from its synchronous dynamics. In particular, [START_REF] Goles | Neural and automata networks, dynamical behavior and applications[END_REF] proved that the synchronous dynamics eventually leads to fixed points or cycles of two opposite configurations. The latter case is the typical behavior in synchronous simulations where one can observe big flashing islands (Fig. 1). On the contrary, as can be observed in Fig. 3, the configurations are very stable over time in asynchronous regime and present typically very rapidly striped patterns (horizontal or vertical) that tend to extend and merge until one gets over the others and covers the whole configuration (when at least one of the dimensions n or m is even). The goal of this paper is to explore how such stripes arise and end up covering the whole configuration. Note that very rarely a random initial configuration may converge to more exotic stable configurations. Fig. 5 gives some examples of more or less exotic stable configurations under 2D minority dynamics.

Stable configurations. We say that a configuration c is a fixed point if for all cells, the state of the cell is unchanged when the cell fires, i.e., if each cell has at most 3 neighbors in the same state as itself. Various examples of such fixed point configurations are given below in Fig. 5. According to experiments, any initial configuration tends to converge in finite time to a fixed point configuration, when at least one of the dimensions n or m is even. Furthermore, it most likely converges to one of the four configurations consisting of horizontal or vertical stripes (see Fig. 3), while converging to other more exotic fixed point remains a very rare event in experiment.

Interaction Energy

In order to explain these observations, we define the following important global parameter that one can consider to be the interaction energy of the system.

Definition 1

The potential v ij of cell (i, j) is the number of its neighboring cells in the same state as itself minus 2.

By definition, if v ij

1 then the cell is inactive and its state will not change if the cell fires; otherwise, if v ij 2 then the cell is active and its state will change if it fires, and in that case, its new potential will be v ij := 4 -v ij (note that if v ij = 2, its potential remains unchanged). Note that a configuration c is a fixed point iff for all cell (i, j) ∈ U , v ij 1.

Definition 2 Let say that a subset of cells R is a region if for each cell (i, j) ∈ R, there exists a square Q = {(i, j), (i + , j), (i + , j + η), (i, j + η)}, for some , η ∈ {1, -1}, such that Q ⊂ R. The interaction energy E R of region R in a given configuration is defined as: E R = (i,j)∈R v ij . We denote by E the interaction energy of the whole configuration c.

The next proposition shows that the energy is non-negative for almost every subset of cells of a configuration. This means that there cannot be too many cells with negative potential. This implies that the decrease of energy over time (Proposition 3 and Theorem 4) is not due to the increase of the number of cells with negative potential, but to the decrease of the potentials of the cells with positive potential, which explains intuitively why the striped patterns which have minimum energy (Proposition 2) arise naturally very rapidly.

Proposition 1 For any finite region R of size N : 0 E R 6N .

Proof. Since the potential of each cell is at most 6, clearly E 6N . Now, we rearrange the potentials locally within region R. Place an edge between any two neighboring cells in the same state. The potential of a cell is exactly its degree in the resulting graph minus 2. We color the edges in blue or red. We say that three cells (i, j)-(i + , j)-(i, j + η), for some , η ∈ {1, -1}, form a L if there are all in the same state and if the cell (i + , j + η) is in the opposite state. Each L contains exactly 3 edges, two on the sides and one diagonal. All the edges are blue except the diagonals of each L which are paint in red. For each L, we reassign the extremities in R of its red edge to the cell (i + , j + η) (which increases its degree up to 2 depending on the number of extremities belonging to R). We can verify on Fig. 4 that since every cell with potential 0 belongs to a square in R (R is a region), whatever this square is, the cell has degree at least 2 after reassigning the extremities of the red edges (even if the cell loses red edges during the reassignment). Consider now a cell with potential 1. Its degree decreases only if it gives at least one red edge to one of its neighbors. Since each cell has a blue edge (the side of the L) for every red edge, its degree could drop below 2 only if it owns two red edges sharing the same blue edge, but in that case, its potential would be exactly 1 and it would then have 5 neighbors next to each other in the opposite state from which it would receive at least one extremity of a red edge in R. It follows that after the reassignment, every node has degree 2 which implies that E R 0. We say that c is a horizontally (resp. vertically) striped configuration if two cells (i, j) and (k, l) are in opposite state iff j and l (resp. i and k) have opposite parity. We say that a cell belongs to a striped neighborhood, if it forms with its neighbors a striped configuration.

Proposition 2 (Configurations of minimal energy) The interaction energy of a configuration c is 0 iff c is a striped configuration (horizontal or vertical).

Proposition 3 Under asynchronous dynamics, the interaction energy is a non-increasing function of time and decreases each time a cell with potential at least 3 fires. Initial energy drop. In experiment, the energy of a configuration drops very fast during the first steps until it converges, most of the time to a striped configuration of minimal energy.

The following theorem provides a bound on the speed of this initial energy drop. Interaction energy of fixed points. According to the experiments, when at least one of the dimensions n or m is even, the configuration converges to a fixed point configuration, most of the time composed only of stripes, which is the fixed point of minimum energy. Other fixed point configurations, of higher energy, exist, but seems to be much less probable as one would expect from a thermodynamic point of view: the lower the energy, the higher the probability to be.

Proposition 5

The interaction energy of the fixed point configurations belongs to {0, . . . , N }.

There is only one configuration of minimum energy up to symmetries and translations: 1 × 2pattern "stripes". There are only three fixed point configurations of maximum interaction energy N up to symmetries and translation: 2 × 4-pattern "fat checkerboard", 8 × 8-patterns "squares of squares" and "squares of spirals" (see Fig. 5).

Theoretical analysis of the last steps

As mentioned above, in most of the experiments the energy drops very fast during the first time steps, until striped regions arise, then they extend, compete, merge until only one covers the whole configuration. In this section, we provide an analysis of the very last steps of the convergence to this fixed point: the case where there remains only one single horizontally striped region within a vertically striped background. We then show that the background ends up covering the whole configuration in polynomial time on expectation.

Our result relies on a bijection with an other random process. Basically, we place a diamond over each cell whose state disagrees with the background and study the evolution of the set of diamonds. We show that the boundary of this set can extend from the hollows and can be dug from the corners. We show thanks to the interaction energy that the resulting shape tends to vanish. Interestingly enough, we show that the horizontally striped region can flip the parity of its stripes but cannot extend further than its initial surrounding rectangle (see Definition 3).

Definition 3 (Configurations as diamond sets)

We suppose that n is even. We say that a cell (i, j) belongs to the (vertically striped) background if its state is (i + 1) mod 2. We say that a cell (i, j) is even if (i + j) is even, and odd otherwise. A cell (i, j) is said horizontal if its state is i mod 2, and vertical otherwise (i.e. the state of an horizontal cell disagrees with the background).

We place over each horizontal cell c a blue diamond (resp. green diamond ) of radius 1 if c is even (resp. odd), as illustrated on Fig. 6. Since there is a diamond over each horizontal cell, a configuration is completely defined by its corresponding set of diamonds. We shall now define a configuration as its set of diamonds.

We say that there is a border between two neighboring cells of the same parity if they are in the same state, and in that case, we say that the border is blue if their parity is even and green otherwise. It is easy to show that the set of the blue (resp. green) borders is exactly the boundary of the union of the blue (resp. green) diamonds.

A blue rectangle (resp. green rectangle) is a rectangle such that its sides are parallel to the diagonals and its corners are centered on odd (resp. even) cells. A blue or green rectangle is enclosing a set of diamonds D if all the diamonds are contained in the rectangle, and it is surrounding D if it is the smallest enclosing rectangle of that color for D.

We say that a configuration is standard if it consists in a finite set of diamonds of the same color forming a rectangle (i.e., a set of diamonds whose borders match its surrounding rectangle).

In this section, we analyze the very last steps of the process and show that any standard configuration converges almost surely to the background configuration, in a polynomial number of steps on expectation. Furthermore, we are able to describe recursively the exact set of the configurations reachable from a standard configuration (valid configurations). This description allows to understand the convergence from such a configuration: at first sight the emerging patterns seem very complex, but in fact they keep a strong underlying structure disclosed by this recursive description.

Valid configurations

This section defines recursively the set of valid configurations that will be shown to be exactly the set of configurations reachable from a standard configuration. Definition 4 Two diamonds are neighbors if they have a side in common. A set D of diamonds is:

• connected if D is connected for the neighborhood relationship.

• convex if for all ∈ {1, -1} and for any pair of diamonds centered on cells (i, j) and (i+k, j + k) in D, the diamonds centered on cells (i+ , j + ) for 0 k belong to D. • an island if it is connected and convex.

Definition 5 A set of diamonds is valid if it is:

• an island, or • the composition of two valid diamond sets D 1 and D 2 enclosed by two rectangles R 1 and R 2 of some given colors laying next to each other according to the patterns given in Fig. 6.

A configuration is valid if its corresponding set of diamonds is valid. Each valid configuration is recursively described by a construction tree: a binary tree where each leaf is an island and each internal node stands for a join operation whose two edges pointing downwards are labeled by the two, blue or green, joined rectangles enclosing the two valid diamond sets described by the left and right subtrees. Fig. 6 gives an example of a valid configuration. Note that the rectangles used in the composition in steps 3 and 4 do not need to fit one into the other. However the rectangles can be resized such that two rectangles on a branch of the construction tree either fit one into the other if they have the same color or fit up to a one square shift if they have different colors (like in steps 3 and 4). A valid configuration can be represented by several construction trees. Rearranging construction trees according to certain rules is useful in the proofs (like Proposition 7).

Valid configurations are stable

Under fully asynchronous dynamics only one cell fires at each time step. Thus only one diamond is added or removed at each time step. Since there are horizontal stripes inside an island, the cells which are not at the border are not active. All the removals and additions of diamonds are done at the border. Now we characterize the active cells by means of diamonds.

Proposition 6 In a valid configuration, up to horizontal, vertical and color symmetries, there are 11 kinds of active cells which are listed in Fig. 7 and which can be split into augmenting cells if a new diamond can appear and decreasing cells if a diamond can disappear.

Proposition 7 A valid configuration always yields a valid configuration after a minority update.

If R1 and R2 have the same color:

Simple joins:

R 1 R 2 R 1 R 2
Shifted joins:

R 1 R 2 R 1 R 2 R 1 R 2 R 1 R 2
If R2 consists of a diamond line of the same color as R1: Line joins: for all x in {0,...,(length (in diamonds) of the side of R1)-1}

R 1 R 2 x R 1 R 2 x R 1 R 2 x R 1 R 2
x

If R1 and R2 have opposite colors: Heterogenous joins:

Shifted heterogeneous joins:

R 1 R 2
The corners at the junction are both covered by a diamond matching the color of the corresponding englobing rectangle Proof. We consider the 11 kinds of possible active cells and check that the configuration is still valid after firing these cells. Sets of connected diamonds remain convex and thus remain islands. In case of apparition/disappearance (for isolated, isolated heterogeneous and isolated bridge) of islands, fusion/division (homogeneous bridge and corner ) of islands and modification of the type of joins (for isolated bridge and heterogeneous bridge) then the construction tree can be rearranged such that the joins and islands implied into the phenomenon form a subtree. For each case, this subtree can be easily replaced by the correct subtree for the updated configuration without taking into account what happens in the rest of the construction.

Proposition 8 Any valid configuration can be obtained by a sequence of minority updates from the standard configuration fitting its blue surrounding rectangle. The same holds for the green surrounding rectangle. Proof. The proof is made by induction on the construction tree. An island of diamonds can be reached from a rectangle of diamonds of the same color which surrounds it by using decreasing cells to trim the corners of the borders. Join constructions can be reached by firing appropriate sequences of decreasing and augmenting cells. As an example the following figure shows the successive steps of the construction of an heterogeneous link where one can reduce the initial rectangle and then grow the rectangle of opposite color. The next theorem is an immediate corollary of the two previous propositions.

initial R 1 R 1 R 1 R 1 R 2
Theorem [START_REF] Gács | Reliable computation with cellular automata[END_REF] The set of valid configurations is the set of all reachable configurations from standard configurations.

Convergence time

The interaction energy function is not precise enough to explain the behavior of the valid configurations. But the diamonds and borders provide other information useful to prove the fast convergence to a fixed point. The area A of the configuration is its number of diamonds.

Proposition 10

The interaction energy of a valid configuration is equal to two times the number of its blue and green borders minus two times the number of intersections of blue and green borders. Thus, E 8A.

Given a configuration let Φ = A + E/4 and E[∆Φ] denotes the expected variation of Φ for this configuration after a fully asynchronous minority update.

Proposition 11 For any valid configuration defined from k islands with joining operations:

E[∆Φ] 3 -3k N .
Proof. The proof is made by induction on the construction tree of the valid configuration. By following clockwise the borders of the island and counting the active cells, we can show that the expected variation of Φ for a configuration with only one island is less than -3 N . If the configuration is obtained by joining two valid configurations then whatever the join is, it can be checked that an active cell in one of the two configurations remains active with the same characterization in the joined configuration. A cell which is not active in both configurations is not active in the joined configuration, except around the join where at most three cells change their behavior. Then the expected variation of Φ is the sum of the expected variation of the two configurations plus the effect of these three cells which is in every case at most + 3 N .

Theorem 12 Every valid configuration of area A converges to the background configuration in finite time with probability 1. The expected convergence time is O(AN ), which is thus

O(N 2 ).
Proof. The construction of a valid configuration can be expressed as a binary tree where the leaves are the islands and the internal nodes are the joins. Thus, = k -1 if the tree is not empty and by Proposition 10 and 11:

E[∆Φ] -3 N if the configuration is not the fixed point, Φ
3A for the initial configuration and Φ = 0 means that the configuration is the fixed point with vertical stripes. Thus it converges in finite time with probability 1 to this fixed point and the expected convergence time is O(AN ).

Conclusion

Beyond our analysis of the beginning and the end of the dynamics, many questions remain open to complete the mathematical description of the asynchronous behavior of 2D minority. In particular, we do not know how to prove that striped regions emerge initially and how they compete with each other in the general setting. We believe that the definition of the borders given in this paper is relevant for the general case as well, since experiments support this intuition. It should also be possible to define other thermodynamic parameters such as entropy or temperature, that may be useful to describe more precisely the dynamics. When at least one dimension n or m is even, we conjecture that any configuration converges to a fixed point in polynomial expected time, namely O(N 3 ) steps on expectation where N is the number of cells. Surprisingly enough, listing the fixed point configurations is already a challenging question.

A Omitted and extended proofs.

Proposition 2

The interaction energy of a configuration c is 0 iff c is a striped configuration (horizontal or vertical).

Proof. Clearly, if c is a striped configuration, its energy is 0. Suppose now that c's interaction energy is zero. Recall the potential reassignment given in the proof of Proposition 1: as illustrated in Fig. 4, after reassigning the red edges, every cell of non-positive potential has degree 3 if its neighborhood is not striped, and all the other cells have degree 2. Since the interaction energy is equal to the sum of degree minus 2N , it follows that if x denotes the number of cells with non-positive potential whose neighborhood is not striped, E x. Since E = 0, x = 0. Thus, all the cells have non-negative potential, and their potentials must sum up to zero; the only possibility left is thus that all the cells belong to a striped neighborhood which implies that c is striped.

Proposition 3 Under asynchronous dynamics, the interaction energy is a non-increasing function of time and decreases each time a cell with potential at least 3 fires.

Proof. Let (i, j) be the cell fired at time t.

If v t ij 1, the configuration is unchanged. If v t ij
2, the state c ij changes and the potentials of cell (i, j) and its neighbors are the only affected: v t+1 ij = 4-v t ij , and for the v t ij +2 neighbors in the same state as (i, j) their potentials decrease by 1 and for the other 6 -v t ij neighbors their potential increase by 1. It follows that the energy varies by: -

v t ij + 4 -v t ij -(v t ij + 2) + (6 -v t ij ) = 8 -4v t ij 0 (< 0 if v t ij
3).

Theorem 4

The interaction energy of any configuration of size N is at most N + 2N/3 after O(N 2 ) fully asynchronous minority updates on expectation.

Proof. First if a configuration c has an energy E > 2N , there exists at least one cell with potential 3 and firing such a cell decreases the energy by at least 4. Moreover firing any cell with potential 2 does not change the energy. Since a cell with potential 3 is fired with probability 1/N , the energy decreases by at least 4 after at most O(N ) steps on expectation. Consequently the energy drops below 2N after at most O(N 2 ) steps on expectation. Suppose now that N + 2N/3 < E 2N , one can not guarantee the existence of a cell with potential 3 any longer: either such a cell exists or all cells have a potential 2. In this later case, one can prove the existence of a good pattern, namely two adjacent cells with potential 2 and with different colors. Suppose the absence of such a pattern, let b 2 (resp. b 1 ) be the number of black cells of potential 2 (resp. 1) and w 2 , w 1 the same for white cells. Then each of the b 2 cells is adjacent to 4 of the w 1 cells. Inversely, each of the w 1 cells has at most 8 adjacent cells. Thus 4b 2 8w 1 . Symmetrically, 4w 2 8b 1 . It involves

N = b 1 +w 1 +b 2 +w 2 3(b 2 +w 2 )/2. But we have N +2N/3 < E b 1 +w 1 +2(b 2 +w 2 ) = N + b 2 +
w 2 which gives 2N/3 < b 2 + w 2 and contradicts the previous inequality. Now that the existence of a cell of potential 3 or two adjacent cells with potential 2 and with different colors is ensured, consider a variant of the energy Ψ = 3E -N 3 where N 3 is the number of cells of potential 3. It is bounded by 0 Ψ 6N . Let N 2-2 (resp. N 2-3 ) be the number of couples of adjacent cells with potential 2 and 2 (resp. 2 and 3) and with different (resp. same) colors, then the expected variation of E is -3 × 4N 3 /N and the expected variation of

N 3 is (N 3 -N 2-2 + N 2-3 )/N . Since N 2-3 8N 3 , the expected variation of Ψ is (-12N 3 + 9N 3 -N 2-2 )/N = (-3N 3 -N 2-2 )/N -2/N if E > N + 2N/3
. By applying a stopping time evaluation, after at most O(N 2 ) steps on expectation, E drops below N + 2N/3 or Ψ drops below N + 2N/3 which also implies that E is below N + 2N/3.

Proposition 5

The interaction energy of the fixed point configurations belongs to {0, . . . , N }. There is only one configuration of minimum energy up to symmetries and translations: 1 × 2pattern "stripes". There are only three fixed point configurations of maximum interaction energy N up to symmetries and translation: 2 × 4-pattern "fat checkerboard", 8 × 8-patterns "squares of squares" and "squares of spirals" (see Fig. 5).

Proof. Since in a fixed point all cells are inactive, their potentials are at most 1 and E N . Proposition 2 gives the only configuration (up to symmetries) of minimal energy 0: it is a fixed point. In a fixed point of maximal energy, all cells have potential 1; an enumerations of the possible neighborhoods followed by an enumeration of the possible combinations of these neighborhood allow to conclude that only three configurations (up to symmetries) are in this category, the only ones given in Fig. 5.

The next lemma gives a rule to rearrange construction trees (i.e. rearrange the sequence of joins). It is useful for Proposition 7.

Lemma (corner lemma) Consider the construction tree of a valid configuration. Consider a node x of the construction tree which is not labeled by a line join and its two sons y and z. Let R 1 the rectangle labeling xy and R 2 the rectangle labeling xz. Let t a node of the subtree rooted at y and R 3 the rectangle labeling the edge linking t to its father. Since x is not labeled by a line join, this join connects a corner of R 1 to a corner of R 2 . If there is a diamond in this corner of R 1 and if R 3 include it, then the subtree rooted at x of the construction tree can be replaced by a tree containing the subtree rooted at t and the subtree rooted at z directly joined together.

Proof. Consider a valid configuration and its construction tree. For a node x, we call T (x) the subtree of the construction tree rooted at x, I(x) the set of islands which label the leaves of T (x) and for a set of islands C, S(C) is the surrounding rectangle of C. Consider x, y , z, t, R 1 , R 2 and R 3 as described in the lemma. Let (u i ) 0 i k the path from t = u 0 to y = u k . By induction on j from 0 to k, there exists a construction tree for the set of islands I(z) ∪ I(u j ) where T (z) and T (t) are directly joined. j = 0 : The islands contained in I(z) (resp. I(t)) can be joined together according to the construction tree T (z) (resp. T (t)). Since S(I(t)) contain the diamond in the corner of R 1 , by enclosing I(t) in S(I(t)) and I(z) in R 2 , I(t) and I(z) can be joined by the join which labels x. j → j + 1 : By induction there is a construction for the set of islands I(z) ∪ I(u j ) where T (z) and T (t) are linked together. In the original construction tree, u j+1 has two sons u j and v. Let R j the rectangle labeling u j u j+1 and R j the rectangle labeling vu j+1 . We have I(v) = I(u j+1 )\I(u j ) and T (v) is a construction tree for I(v). Since these two sets of islands can be joined together S(I(v))∩S(I(u j )) does not contain a complete diamond. Since S(I(u j )) is containing the diamond in the corner of R 1 , S(I(v)) ∩ (S(I(u j )) ∪ R 1 ) does not contain a complete diamond and the join between R j and R j still works if we replace R j by S(R j ∪ R 1 ) (See figure 8). By including I(z) ∪ I(u j ) in S(R j ∪ R 1 ) and I(v) in R j , the sets of islands I(z) ∪ I(u j ) and I(v) can be joined by the join which labels u j+1 (if R j is a line and the join is a line join, it can be changed to a shifted join).

Thus we obtain a construction tree for I(x) where T (z) and T (t) are linked together. And this tree can replace the subtree rooted in x in the original construction tree.

Proposition 6 In a valid configuration, up to horizontal, vertical and color symmetries, there are 11 kinds of active cells which are listed in Fig. 7 and which can be split into augmenting cells if a new diamond can appear and decreasing cells if a diamond can disappear.

Proof. Consider a decreasing cell, the cell is covered by a diamond and there are no diamonds of the opposite color above or below this diamond if the configuration is valid. Thus in a valid configuration, the potential of a decreasing cell is 4 minus the number of blue and green diamonds among the 6 other neighbors. So there are at most 2 diamonds among these neighbors. It leads to 7 different kind of decreasing cells up to symmetries.

Consider an augmenting cell, the potential of the cell is 1 minus the number of diamonds above or below the cell plus the number of diamonds among the 6 other neighbors. Thus if the cell is active the number of diamonds among the 6 other neighbors is larger by 2 than the number of diamonds above or below the cell. If there are more than 3 diamonds among the 6 other neighbors then the configuration is not valid: there are green diamonds above or below blue diamonds or there is no possibility to join the different islands which appear in the neighborhood or there is an island which is not convex. Thus in a valid configuration, there are no diamond above or below the augmenting cell and 2 diamonds among the 6 other neighbors. It leads to 4 different kinds of augmenting cells up to symmetries. Proposition 7 A valid configuration always yields a valid configuration after a minority update.

Proof. We consider the 11 kinds of possible active cells and check that the configuration is still valid after firing such cells. We begin with the decreasing cells:

• isolated cell fires: In the construction tree, the isolated diamond is enclosed in rectangle R 1 . A diamond set is enclosed in a rectangle R 2 . R 1 and R 2 are joined together and their join is enclosed in the rectangle R 3 . Firing the isolated cell leads to delete the rectangle R 1 and R 2 and the isolated diamond. The diamond set previously enclosed in R 2 is now enclosed in R 3 . initial configuration configuration after firing the cell

R 2 R 1 R 3 R 3
• peninsula cell fires: the modified island is still convex. All the enclosing rectangles are still enclosing rectangles. There is no need to modify the construction tree, the configuration remains valid.

• isolated heterogeneous cell fires: using the corner lemma, we can consider the following construction tree. A single blue diamond is enclosed in a rectangle R 1 . A green island is enclosed in a rectangle R 2 . These two rectangle are linked by an heterogeneous join and the construction is enclosed in R 3 . Firing the isolated cell leads to delete the rectangles R 1 and R 2 and the isolated diamond. The green island previously enclosed in R 2 is now enclosed in R 3 . initial configuration configuration after firing the cell

R 1 R 3 R 2 R 3
• corner cell fires: there are two cases. In the first one, the island where the firing cell is located remains connected and thus there is no need to modify the construction tree and the configuration remains valid. In the other case, the island is divided into two islands which are joined by a simple join. initial configuration configuration after firing the cell

R 3 R 1 R 2 R 3
• homogeneous bridge cell fires: the island is divided into two islands which are joined by a shifted or line join. initial configuration configuration after firing the cell

R 3 R 3 R 1 R 2
• heterogeneous bridge cell fires: by two iterations of the corner lemma, we can consider the following construction tree. The blue island is enclosed in a rectangle R 1 . The green island is enclosed in a rectangle R 2 . These two rectangle are linked by an heterogeneous join and the construction is enclosed in R 3 . Firing the isolated cell leads to decrease the size of R 1 in order to replace the join by a shifted heterogeneous join. initial configuration configuration after firing the cell

R 1 R 2 R 3 R 1 R 1 R 2 R 3
• isolated bridge cell fires: by two iterations of the corner lemma, we can consider the following construction tree. One of the green island is enclosed in R 1 . It is joined to the blue diamond by a heterogeneous join and enclosed in R 4 . The other green island is enclosed in R 2 and joined to R 4 by a heterogeneous join. This construction is enclosed in R 3 . Firing the isolated cell leads to remove the blue diamond and R 4 , and to join R 1 to R 3 by a simple join. initial configuration configuration after firing the cell

R 2 R 1 R 3 R 4 R 2 R 1 R 3
The study of the four kind of augmenting cell is similar to their decreasing counterparts where the initial and final configurations are switched.

Proposition 8 Any valid configuration can be obtained by a sequence of minority updates from the standard configuration fitting its blue surrounding rectangle. The same holds for the green surrounding rectangle.

Proof. The proof is made by induction on the construction tree by considering the leaves and then the different types of joins. An island of diamonds can be reached from a rectangle of diamonds of the same color which surrounds it by using decreasing corner cells to remove the cells in the corners of its boundary.

Two rectangles of diamonds joined together by a simple, shifted or line join can be reached from the rectangle of diamonds of the same color surrounding them. Up to one missing diamond the two rectangles are connected and form only one island. Such an island can be reached as seen above and then the connecting diamond can be removed by firing a decreasing corner or homogeneous bridge cell.

Two rectangles R 1 and R 2 of diamonds joined by an heterogeneous or shifted heterogeneous join can be reached from the rectangle of blue or green diamonds surrounding them. The following figures show the different steps of the construction of an heterogeneous join. It works for both the blue and green rectangles surrounding the whole configuration, as long as R 1 and R 2 are inside this surrounding rectangle. The construction and the remark are similar for shifted heterogeneous joins. Whatever is the join between two rectangles, there is a special case not treated yet when at least one of the two rectangles has not the same color as the rectangle surrounding their union: such a rectangle R can be greater than the surrounding rectangle as shown in Fig. 6. In this case, another heterogeneous of shifted heterogeneous join necessarily occurred during the construction of R and the surrounding rectangle encloses the two rectangles of this latter join. In this case we generate the two joins and the three rectangles simultaneously by a construction similar to the heterogeneous case.

initial R 1 R 1 R 1 R 1 R 2
The rectangles used in the definition of joins are enclosing rectangles and not necessarily surrounding rectangles, and their colors are not necessarily the same as the ones of the surrounding rectangles. Thus to achieve the induction properly, we use the next two remarks. First, a rectangle of diamonds can reach a smaller rectangle of diamonds of the same color: one can remove a line of diamonds at the boundary by repeatedly firing decreasing corner cells until the only diamond left on the line is removed by firing a decreasing peninsula cell. Secondly, a rectangle of diamonds R can be reached from its surrounding rectangle R of diamonds of the opposite color: it is sufficient to reach from R the configuration where an island made of one diamond colored like R is linked by a heterogeneous join to the rectangle R. After following the sequence presented for heterogeneous joins, the diamond colored like R can be removed by firing the decreasing isolated heterogeneous cell it covers.

Proposition 10

The interaction energy of a valid configuration is equal to two times the number of its blue and green borders minus two times the number of intersections of blue and green borders. Thus, E 8A.

Proof. We recall that a border is the side of one diamond and thus given a configuration, the number of its blue and green borders is the total length of the boundaries of blue and green islands.

For each island the number of its border is the number of borders of its surrounding rectangle which is its perimeter. Thus there is an even number of borders and there is no configuration with 2 borders. The proof is made by recurrence on the number 4 + 2 × i of borders:

Initialization: The weight of the configuration with no borders is the weight of the fixed point that is to say 0. If i = 0, there is only one configuration with four borders, the configuration with one diamond. The weight of this configuration is 8.

Induction step: We suppose that there are x borders and y intersections. We call E the interaction energy of the configuration. Suppose that the configuration has one of the following kinds of decreasing cell:

• decreasing isolated cell: by firing this cell, 4 borders and 0 intersection disappear and the interaction energy is decreased by 8. The interaction energy of the updated configuration is 2(x -4) -2y by induction. Thus E = 2(x -4) -2y + 8 = 2x -2y.

• decreasing peninsula cell: by firing this cell, 2 borders and 0 intersection disappear and the interaction energy is decreased by 4. The interaction energy of the updated configuration is 2(x -2) -2y by induction. Thus E = 2(x -2) -2y + 4 = 2x -2y.

• decreasing isolated heterogeneous cell: by firing this cell, 4 borders and 2 intersections disappear and the interaction energy is decreased by 4. The interaction energy of the updated configuration is 2(x -4) -2(y -2) by induction. Thus E = 2(x -4) -2(y -2) + 4 = 2x -2y.

• decreasing heterogeneous bridge cell: by firing this cell, 2 borders and 2 intersections disappear and the interaction energy is not decreased. The interaction energy of the updated configuration is 2(x -2) -2(y -2) = 2x -2y by induction. Thus E = 2x -2y.

• decreasing isolated bridge cell: if the cells fires 4 borders and 4 intersections disappear and the interaction energy is not decreased. The interaction energy of the updated configuration is 2(x -4) -2(y -4) = 2x -2y by induction. Thus E = 2x -2y.

Suppose that none of these kinds of decreasing cells are present in the configuration. Then we select an island. We select one line of diamonds on the side of the surrounding rectangle of this island. We remove diamonds from this line by firing decreasing corner cells. Firing a decreasing corner cell does not change the number of borders and intersections of the configuration and does not change the interaction energy of the configuration. When there is only one diamond left on the line, a decreasing peninsula or heterogeneous bridge cell appears and we can apply the previous cases. This ends the induction and thus E = 2x -2y Proposition 11 For any valid configuration defined from k islands with merging operations:

E[∆Φ] 3 -3k N Proof.
Let c be a valid configuration with k islands and joins. Consider a construction tree of this configuration, with internal nodes and k leaves labeled by the islands. Each internal node is characterized by a set of diamonds which is the union of the two set of diamonds of its two sons and by the name of the link which has been used to join this two subsets. For each node v, E v [∆Φ] denotes the expected variation of Φ for the configuration corresponding to the set of diamonds of v under a minority update. The area of the configuration is increased by one each time an augmenting cell is updated and decreased by one each time a decreasing cell is updated. Let N c a be the number of augmenting cells and N c d the number of decreasing cells of configuration c, then

E[∆A] = N c a -N c d N
. The interaction energy is decreased by 8 when a decreasing isolated cell fires (4 borders disappear) and decreased by 4 when a decreasing peninsula cell fires (2 borders disappear) or a decreasing isolated heterogeneous cell fires (4 borders and 2 intersections disappear). Let N c iso (resp. N c pen , N c het ) the number of decreasing isolated (resp. peninsula,isolated heterogeneous) cells in c. We have

E[∆(E/4)] = -2N c iso -N c pen -N c het N . Thus E[∆Φ] = N c a -N c d -2N c iso -N c pen -N c het N
. By induction on the construction tree, let us show that for a node v corresponding to k v islands and v joins, we have

E v [∆Φ] 3kv-3 v N .
Consider a leaf characterized by the island i. If the island is a single diamond, then for the corresponding configuration, we have N i a = 0, N i d = 1, N i iso = 1, N i pen = 0 and N i het = 0 and thus E i [∆Φ] = -3 N . If the island is a line of j 2 diamonds then the two diamonds at the extremities of the line correspond to decreasing peninsula cells and other diamonds of the line correspond to decreasing homogeneous bridge cells. Then N i a = 0, N i d = j, N i iso = 0, N i pen = 2 and N i het = 0 and thus E i [∆Φ] = -j-2 N -4 N . If the island has more than 3 diamonds and is not a line then we consider the borders of the island which form a cycle. Consider the following algorithm: we make one clockwise turn along the frontier beginning from an arbitrary point with a counter initialized at 0. Each time we turn clockwise we decrement the counter (we have reached a decreasing cell or a peninsula). Each time we turn counterclockwise we increment the counter (we have reach an augmenting cell). At the end of the first turn the counter is less than N c a -N c d -2N c iso -N c pen -N c het (Since that during our analysis we have neglected the homogeneous bridge decreasing cells). Since the frontier is convex, it is known that the counter is equal to 4 (The direction is the same at the beginning and at the end of the turn, thus we have turned by 360 • ). Thus E i [∆Φ] -4 N .

Consider an internal vertex v which has two sons s and s , the set of diamonds corresponding to s(resp. s ) is made of k s (resp. k s ) islands joined by s (resp. s ) joins. The set of diamonds of v is made of k s + k s islands joined by s + s + 1 joins. We consider the different kinds of joins between s and s :

• simple join: the behavior of s and s is not changed but the join may create two augmenting corner cells (firing one of these active cells connects the two islands in the neighborhood of the join) and one augmenting isolated bridge cell (firing this cell creates a new island between the two islands in the neighborhood of the join). Thus this join creates at most three augmenting cells. We have N v a = N s a + N . • shifted join: the behavior of s and s is not changed but the join may create an augmenting homogeneous bridge cell between the two islands (firing this active cell connects the two islands in the neighborhood of the join). Thus this join creates at most one augmenting cell and E v [∆Φ] -3ks-3k s +3 s+3 s +1 N -3kv+3 v N . • line join: same as shifted join.

• shifted heterogeneous join: the behavior of s and s is not changed but the join may create two augmenting heterogeneous bridge cells (firing one of these augmenting cells changes the link into an heterogeneous join). Thus this join creates at most two augmenting cells and

E v [∆Φ] -3ks-3k s +3 s+3 s +2 N -3kv+3 v N .
• heterogeneous join: no augmenting cell appears but the behavior of s and s is modified. An heterogeneous join requires that the cells of the corners are covered by diamonds. One of these diamonds belongs to the set of diamonds of s and the other from the set of diamonds of s . In s and s they have at most two diamonds of their color in their neighborhood. Thus in s and s they cover a corner or peninsula or (isolated or isolated heterogeneous decreasing cell. If one of these cells is a decreasing corner cell in s or s then in v it is no more active. If one of these cells is a decreasing peninsula cell in s or s then in v it becomes a decreasing heterogeneous cell. If one of these cells is a decreasing isolated heterogeneous cell in s or s then in v it becomes a decreasing isolated bridge cell. If one of these cells is a decreasing isolated cell in s or s then in v it becomes a decreasing isolated heterogeneous cell. The two corners at the join are modified this way and thus E v [∆Φ]

Figure 2 :

 2 Figure 2: 2D Minority under different α-asynchronous dynamics with N = 50 × 50 cells.

Figure 3 :

 3 Figure 3: A typical execution of stochastic 2D minority with N = 50 × 50 cells.

Figure 4 :

 4 Figure 4: The list of the possible configurations for cells with potential 0 and the diagonal edges that are reassigned (in red).

Theorem 4 Figure 5 :

 45 Figure 5: Examples of fixed points for 2D Minority at various levels of energy.

Figure 6 :

 6 Figure 6: To the left: valid combinations of valid configurations (the underlying cells of the automaton are shown at the junction of the rectangles). To the right: a valid configuration and its diamond set with a valid decomposition

Figure 7 :

 7 Figure 7: The list of all possible active cells in a valid configuration.

Figure 8 :

 8 Figure 8: A step of the induction.

-

  3ks-3k s +3 s+3 s +2 N -3kv+3 v N . Thus for any vertex v, E v [∆Φ] -3kv+3 v N . Finally E[∆Φ] 3 -3kN .

An automaton is totalistic if its cells update according to the number of their neighbors in a given state.


Yi Yang

Jean Dezert
email: jean.dezert@onera.fr

Deqiang Han
email: deqhan@gmail.com

Jean-Marc Tacnet
email: jean-marc.tacnet@irstea.fr

Simon Carladous
email: simon.carladous@irstea.fr

Decision-Making

Keywords: belief functions, decision-making, distance between BBAs

Introduction

Dempster-Shafer Theory (DST), also known as the Mathematical Theory of Evidence or the Theory of Belief Functions (BF), was introduced by Shafer in 1976 [START_REF] Shafer | A Mathematical Theory of Evidence[END_REF] based on Dempster's previous works [START_REF] Dempster | Upper and lower probabilities induced by a multivalued mapping[END_REF]. This theory offers an elegant theoretical framework for modeling uncertainty, and provides a method for combining distinct bodies of evidence collected from different sources. In the past more than three decades, DST has been used in many applications, in fields including information fusion, pattern recognition, and decision making [START_REF] Smets | Practical uses of belief functions[END_REF]. Although belief functions are very appealing for modeling epistemic uncertainty, the two main important questions related to them remain still open:

How to combine efficiently several independent belief functions?

This open question is out of the scope of this paper and it has been widely disputed by many experts [START_REF] Zadeh | On the validity of Dempster's rule of combination[END_REF][START_REF] Lemmer | Confidence factors, empiricism and the Dempster-Shafer theory of evidence[END_REF][START_REF] Pearl | Reasoning with belief functions: An analysis of compatibility[END_REF][START_REF] Voorbraak | On the justification of Dempster's rule of combination[END_REF][START_REF] Wang | A defect in Dempster-Shafer theory[END_REF][START_REF] Gelman | The boxer, the wrestler, and the coin flip: a paradox of robust Bayesian inference and belief functions[END_REF][START_REF] Dezert | On The Validity of Dempster-Shafer Theory[END_REF][START_REF] Tchamova | On the Behavior of Dempster's Rule of Combination and the Foundations of Dempster-Shafer Theory[END_REF][START_REF] Dezert | Why Dempster's rule doesn't behave as Bayes rule with informative priors[END_REF][START_REF] Dezert | On the validity of Dempster's fusion rule and its interpretation as a generalization of Bayesian fusion rule[END_REF][START_REF] Smarandache | Advances and applications of DSmT for information fusion[END_REF]. In this short paper, we focus on the second question below.

How to take a final decision from a belief function?

This second question is also very crucial in many problems involving epistemic uncertainty where the final step (after beliefs elicitation, and beliefs combination) is to make a decision.

In the sequel, we assume that the reader is familiar with Demspter-Shafer Theory of belief functions [START_REF] Shafer | A Mathematical Theory of Evidence[END_REF] and its notations. Due to space restriction, we will not recall the definitions of basic belief assignment m(•), belief Bel(•) (also called credibility by some authors), and plausibility functions P l(•) functions defined over a given finite discrete frame of discernment (FoD) Θ. For any focal element X of the powerset of Θ, denoted by 2 Θ , the interval BI(X) [Bel(X), P l(X)] is called the belief interval of X. Its length P l(X) -BeI(X) characterizes the uncertainty on X (also called ambiguity in [START_REF] Srivastava | Decision Making Under Ambiguity: A Belief-Function Perspective[END_REF]). This paper is organized as follows. In section 2, we recall the common decision-making techniques used so far to make a decision from belief functions. In section 3 we recall the new distance measure based on Belief interval, and we present a new general method for decision-making with belief functions. Finally, examples of this new approach are given in section 4, with concluding remarks in section 5.

Classical decision-making methods with belief functions

We assume a given FoD Θ = {θ 1 , . . . , θ n } and a given BBA m(•) defined on 2 Θ . We want to make a decision from m(•). It consists in choosing a particular element of the FoD that solves the problem under consideration, which is represented by the set of potential solutions (choices) θ i , i = 1, . . . , n. How to do this in an effective manner is the fundamental question of decision-making under epistemic uncertainty. Many decision-making criteria have been proposed in the literature. Some advanced techniques developed in the 1990s [START_REF] Nguyen | On Decision Making Using Belief Functions, in Advances in the Dempster-Shafer Theory of Evidence[END_REF][START_REF] Jaffray | Utility Theory for Belief Functions[END_REF][START_REF] Strat | Decision Analysis Using Belief Functions[END_REF][START_REF] Yager | Decision making under Dempster-Shafer uncertainties[END_REF][START_REF] Srivastava | Decision Making Under Ambiguity: A Belief-Function Perspective[END_REF] have not been widely used so far in the BF community, probably because of their complexity of implementation. In this section, we only present briefly the simplest ones frequently used.

Decision based on maximum of credibility:

This decision-making scheme is the so-called prudent (or pessimistic) scheme. It consists in choosing the element of the FoD Θ that has the maximum of credibility. In other terms, one will decide θ = θ i with1

θ i = arg max i Bel(θ i ) (1)
2. Decision based on maximum of plausibility: On the contrary, if we prefer to adopt a more optimistic decision-making (less prudent) attitude, one will choose the element of the FoD Θ that has the maximum of plausibility. In other terms, one will decide θ = θ i with

θ i = arg max i P l(θ i ) (2)
3. Decision based on maximum of probability: Usually decision-makers prefer to adopt a more balanced decisional attitude making a compromise between the aforementioned pessimistic and optimistic attitudes. For this, the BBA m(•) is transformed into a subjective probability measure P (•) compatible with the belief interval [Bel(•), P l(•)], and one will choose the element of the FoD Θ that has the maximum of probability. In other terms, one will decide θ = θ i with

θ i = arg max i P (θ i ) (3)
In practice, many probabilistic transformations are available to approximate (or transform) a BBA m(•) in a probability measure P (•). By example, the pignistic transformation [START_REF] Smets | The transferable belief model[END_REF], the plausibility transformation [START_REF] Cobb | On the plausibility transformation method for translating belief function models to probability models[END_REF], the DSmP transformation and other ones presented in [START_REF] Dezert | A new probabilistic transformation of belief mass assignment[END_REF], etc.

Of course, in case of multiple maximum values, no decision can be clearly drawn. Usually if only one decision must be made, a random sample between elements θ i generating the maximal decision-making criterion value is used to make a unique final decision θ. Another more prudent decision scheme is to use the disjunction of all elements generating the maximal decision-making criterion value, to provide a less specific final decision (if it is allowed for the problem under concern).

Our main criticism about using these decision-making schemes is that they do not use the whole information contained in the original BBA, which is in fact expressed by the whole belief interval. The pessimistic attitude uses only the credibility values, whereas the optimistic attitude uses only the plausibility values. The prudent attitude based on the criteria (3) requires a particular choice of probabilistic transformation which is often disputed by users. Making a decision from the P (.) measure is theoretically not satisfactory at all because the transformation is lossy since we cannot retrieve m(•) from P (•) when some focal elements of m(•) are not singletons. In the next section, we propose a better justified decision scheme based on the belief interval distance [START_REF] Han | New Distance Measures of Evidence based on Belief Intervals[END_REF][START_REF] Han | Belief Interval Based Distance Measures in the Theory of Belief Functions[END_REF].

Decision-making method using belief interval distance

In our previous works [START_REF] Han | New Distance Measures of Evidence based on Belief Intervals[END_REF][START_REF] Han | Belief Interval Based Distance Measures in the Theory of Belief Functions[END_REF], we have defined a Euclidean belief interval distance between two BBAs m 1 (•) and m 2 (•) defined on the powerset of a given FoD Θ = {θ 1 , . . . , θ n } as follows

d BI (m 1 , m 2 ) N c • X∈2 Θ d 2 W (BI 1 (X), BI 2 (X)) (4)
where

N c = 1/2 n-1 is a normalization factor to have d BI (m 1 , m 2 ) ∈ [0, 1], and d W (BI 1 (X), BI 2 (X)) is the Wassertein's distance [25] between belief intervals BI 1 (X) [Bel 1 (X), P l 1 (X)] = [a 1 , b 1 ] and BI 2 (X) [Bel 2 (X), P l 2 (X)] = [a 2 , b 2 ]. More specificly, d W ([a 1 , b 1 ], [a 2 , b 2 ]) a 1 + b 1 2 - a 2 + b 2 2 2 + 1 3 b 1 -a 1 2 - b 2 -a 2 2 2 (5)
In [START_REF] Han | New Distance Measures of Evidence based on Belief Intervals[END_REF], we have proved that d BI (x, y) is a true distance metric because it satisfies the properties of non-negativity (d(x, y) ≥ 0), non-degeneracy (d(x, y) = 0 ⇔ x = y), symmetry (d(x, y) = d(y, x)), and the triangle inequality (d(x, y) + d(y, z) ≥ d(x, z), for any BBAs x, y and z defined on 2 Θ . The choice of Wasserstein's distance in d BI definition is justified by the fact that Wasserstein's distance is a true distance metric and it fits well with our needs because we have to compute a distance between [Bel 1 (X), P l 1 (X)] and [Bel 2 (X), P l 2 (X)].

For notation convenience, we denote m X the categorical BBA having only X as focal element, where X = ∅ is an element of the powerset of Θ. More precisely, m X is the particular (categorical) BBA defined by m X (X) = 1 and m X (Y ) = 0 for any Y = X. Such basic BBA plays an important role in our new decision scheme because its corresponding belief interval reduces to the degenerate interval [START_REF] Shafer | A Mathematical Theory of Evidence[END_REF][START_REF] Shafer | A Mathematical Theory of Evidence[END_REF] which represents the certainty on X. The basic principle of the new decision scheme we propose is very simple and intuitively makes sense. It consists in selecting as the final decision (denoted by X) the element of the powerset for which the belief interval distance between the BBA m(•) and m X , X ∈ 2 Θ \ {∅} is the smallest one 7 . Therefore, take as the final decision X given by X = arg min

X∈2 Θ \{∅} d BI (m, m X ) (6)
where d BI (m, m X ) is computed according to (4). m(•) is the BBA under test and m X (.) the categorical BBA focused on X defined above.

This decision scheme is very general in the sense that the decision making can be done on any type of element 2 of the power-set 2 Θ , and not necessarily only on the elements (singletons) of the FoD (see examples in the next section). This method not only provides the final decision X to make, but also it evaluates how good this decision is with respect to its alternatives if we define the quality indicator q( X) as follows

q( X) 1 - d BI (m, m X ) X∈2 Θ \{∅} d BI (m, m X ) (7)
One sees that the quality indicator q( X) of the decision X made will become maximum (equal to one) when the distance between the BBA m(•) and m X is zero, which means that the BBA m(•) is focused in fact only on the element X. The higher q( X) is, the more confident in the decision X we should be.

Of course, if a decision must be made with some extra constraint 3 defined by a (or several) condition(s), denoted c(X), then we must take into account c(X) in Eq. ( 6), that is X = arg min X∈2 Θ \{∅} s.t. c(X) d BI (m, m X ), and also in the derivation of quality indicator by taking X∈2 Θ \{∅} s.t. c(X) d BI (m, m X ) as denominator in [START_REF] Voorbraak | On the justification of Dempster's rule of combination[END_REF]. Theoretically any other strict distance metric, for instance Jousselme's distance [START_REF] Jousselme | A new distance between two bodies of evidence[END_REF][START_REF] Jousselme | Distances in evidence theory: Comprehensive survey and generalizations[END_REF][START_REF] Bouchard | A proof for the positive definiteness of the Jaccard index matrix[END_REF], could be used instead of d BI (•, •). We have chosen d BI distance because of its ability to provide good and reasonable behavior [START_REF] Han | New Distance Measures of Evidence based on Belief Intervals[END_REF] as will be shown. When there exists a tie between multiple decisions { Xj , j > 1}, then the prudent decision corresponding to their disjunction X = ∪ j Xj should be preferred (if allowed), otherwise the final decision X is made by a random selection of elements Xj .

Examples and comparisons

In this section we present several examples when the cardinality of the FoD |Θ| is only 2 and 3 because it is easier to see whether the decision-making results make sense or not. We compare and discuss decisions only made with the belief interval distance d BI and Jousselme's distance d J because the other lossy decision schemes do not exploit both credibility and plausibility values. The examples corresponding to cases where the BBA m(•) is focused on a single element X of 2 Θ are not presented because one trivially gets X = X using either d BI or d J distances. The next tables present several BBAs from which a decision has to be made. By convention, and since we work with normal BBAs satisfying m(∅) = 0, the empty set is not included in the tables. The rows for d min BI (m i , m X ) and for d min J (m i , m X ) list the minimal values obtained for d BI (m i , m X ) and d J (m i , m X ). The rows for Xd BI and for Xd J list the decision(s) X made when using d BI (m i , m X ) and d J (m i , m X ) respectively. The rows for q( Xd BI ) and q( Xd J ) list the quality indicators of decision(s) made using d BI (m i , m X ) and d J (m i , m X ) respectively. Depending on the BBA, it is possible to have multiple decisions { Xj } in case of a tie. If a tie occurs either a random sampling of { Xj } must be drawn, or (if allowed) the disjunction of decisions Xj is preferred. In the next subsections, we present results in free-constraint case (i.e. c(X) = ∅), as well as when the decisions are restricted to be singletons (i.e. c(X) ≡ "|X| = 1").

Examples with Θ = {A, B}

Table 1 shows the decisions made when there is no constraint on the cardinality of the decision X.

One sees that methods based on min of d BI (m, m X ) and on min of d J (m, m X ) yield the same reasonable decisions in almost all cases. With m 2 , one has multiple decisions Xd J = {A, B, A ∪ B} with quality 0.6667 when using d J , which is a bit surprising in our opinion because there is a real tie between A and B. Consequently, the decision A ∪ B should be preferred when there is no constraint on the cardinality of decisions. For this m 2 case, one gets a unique decision Xd BI = A ∪ B with a better quality 0.776 which seems more reasonable. We see also that all minimal distance values obtained with d BI are less (or equal in case m 1 ) to the minimal values obtained with d J . In fact, when the mass function is distributed symmetrically, it is naturally expected that no real decision can be easily taken (as illustrated for BBA's m 2 (•) and m 5 (•) in Table 1). Here, the Table 1. Examples of several BBA's and decisions made (no constraint case).

X ∈ 2 Θ m1(•) m2(•) m3(•) m4(•) m5(•) m6(•) m7(•) A 0.
A A ∪ B A A ∪ B A ∪ B A A ∪ B
d min J (mi, mX ) 0.1000 0.5000 0.1581 0.1000 0.4000 0.0707 0.0707 q( Xd J ) 0.9390 0.6667 0.8999 0.9276 0.6409 0.9574 0.9501

Xd J A A, B, A ∪ B A A ∪ B A ∪ B A A ∪ B
decision A ∪ B for BBA's m 2 (•) and m 5 (•) can be interpreted as a no proper decision, in the sense that A ∪ B is the whole universe of discourse, hence we are merely selecting anything (and discarding nothing). Such kind of no proper decision may however be very helpful in some fusion systems because it warns that input information is not rich enough, and that one needs more information to take a proper decision (by including more sensors or more experts reports in the system for instance). For symmetrical mass function, the decision drawn from the new proposed decision rule is consistent with what we can reasonably get because. To make a proper decision we will always need to introduce some possibly arbitrary additional constraints. Table 2 shows the decisions made for same examples when we force the decision to be a singleton, that is when the constraint is c(X) ≡ "|X| = 1". One sees that the decisions restricted to the set of singletons using d BI (m, m X ) or d J (m, m X ) are the same but the quality indicators are a bit better when using d BI (m, m X ) with respect to d J (m, m X ). The values of the quality indicators in Table 2 are different to those of Table 1 which is normal because we use the constraint c(X) in the denominator of the formula [START_REF] Voorbraak | On the justification of Dempster's rule of combination[END_REF]. 3 shows the decisions made when there is no constraint on the cardinality of the decision X, whereas Table 4 shows the results for the same examples when the decisions made are restricted to singletons. As shown in the tables all minimal distance values obtained with d BI are less (or equal) to the minimal values obtained with d J and the quality indicator decisions is better when computed with d BI (except in case m 1 of Table 3). The decisions results obtained with d J are mostly consistent with those obtained with d BI (except in case m 2 and m 3 of Table 3) where a larger set of decisions (tie) is obtained using d J . If the decisions are restricted to singletons (see Table 4), then the decision-making based on d BI and on d J provides the same results with a better quality of decisions using d BI .

Table 3. Examples of several BBA's and decisions made (no constraint case).

X ∈ 2 Θ m1(•) m2(•) m3(•) m4(•) m5(•) m6(•) m7(•) m8(•) A 0.9 0.5 1/3 0.5 0 0 0 0.2 B 0.1 0.5 1/3 0 0 0 0 0.1 A ∪ B 0 0 0 0.5 0.5 2/3 1/3 0.05 C 0 0 1/3 0 0 0 0 0.05 A ∪ C 0 0 0 0 0 0 1/3 0.1 B ∪ C 0 0 0 0 0.5 1/3 1/3 0.2 A ∪ B ∪ C 0 0 0 0 0 0 0 0.3 d min BI (mi, m X ) 0.
A A ∪ B 2 Θ \ {∅, A, B, C} A, A ∪ B, A ∪ B A ∪ B ∪ C A ∪ B ∪ C A ∪ B B ∪ C, Θ d min J (mi, m X ) 0.

Conclusions

We have presented a new method for decision-making with belief functions which truly exploits the belief interval value of each focal element of a BBA. It is easy to implement and can be applied with any strict distance metric between two BBAs. We have considered and compared the well-known Jousselme's distance and the recent belief interval distance. This method is general because the decision can be made not only on singletons, but also on any other compound focal elements (if needed and allowed). It also provides a quality indicator of the decision made.

X ∈ 2 Θ

 2 m1(•) m2(•) m3(•) m4(•) m5(•) m6(•) m7(•) m8(BI (mi, m X ) 0.1000 0.5000 0.5774 0.2887 0.5000 0.5092 0.6236 0.5770 q( Xd BI ) 0.9488 0.7321 0.6667 0.8531 0.7388 0.7364 0.6667 0

Table 2 .

 2 Examples of several BBA's and decisions made (restricted to singletons).

	X ∈ 2 Θ	m1(•) m2(•) m3(•) m4(•) m5(•) m6(•) m7(•)
		A	0.9	0.5	0.8	0.1	0.4	0.9	0.1
		B	0.1	0.5	0.1	0.1	0.4	0	0
	A ∪ B	0	0	0.1	0.8	0.2	0.1	0.9
	d min BI (mi, m X ) 0.1000 0.5000 0.1528 0.5508 0.5033 0.0577 0.5196
	q( Xd BI )	0.9000 0.5000 0.8477 0.5000 0.5000 0.9427 0.5393
		Xd BI	A	A, B	A	A, B A, B	A	A
	d min J	(mi, m X ) 0.1000 0.5000 0.1581 0.6403 0.5099 0.0707 0.6364
	q( Xd J )	0.9000 0.5000 0.8434 0.5000 0.5000 0.9308 0.5276
		Xd J	A	A, B	A	A, B A, B	A	A

Table 4 .

 4 Examples of several BBA's and decisions made (restricted to singletons).

		1000 0.5000	0.5774	0.3536 0.4082 0.2722 0.3333	0.3149
	q( Xd J )	0.9798 0.8870	0.8571	0.9225 0.8989 0.9337 0.9111	0.9152
	Xd J	A	A, B,	2 Θ \ {∅}	A,

A ∪ B, A ∪ B A ∪ B ∪ C A ∪ B ∪ C A ∪ B A ∪ B B ∪ C, Θ

The notation with hat indicates the decision taken. Here θ specifies that the decision taken is only a singleton of Θ.