A parameterization for a class of complete games with abstention

A Parameterization for a class of Complete Games with Abstention Josep Freixas ∗, Bertrand Tchantcho † , and Proces Bill Tsague ‡ May 12, 2017 Abstract: Voting games with abstention are voting systems in which players can cast not only yes and no vote, but are allowed to abstain. This paper centers on the structure of a class of complete games with abstention. We obtain, a parameterization that can be useful for enumerating these games, up to isomorphism. Indeed, any I-complete game is determined by a vector of matrices with non-negative integers entries. It also allows us determining whether a complete game with abstention is a strongly weighted (3,2) game or not, and for other purposes of interest in game theory. Keywords: (3,2) games ·Abstention ·Desirability relations ·Weighted games and Complete games · Mathematics Subject Classification (2000) 91A12 ·05C65 ·94C10 1 Introduction Simple games have been intensively used as models of collective choice and, especially, for situations arising from political science. Many of these situations are described by weighted majority games, the most interesting class of simple games. In a simple game, a single alternative, such as a bill or an amendment, is pitted against the status quo, the players or voters vote in favor of the alternative or against it and the motion is passed or not depending of the collective strength of members who vote “”yes”.” The motion passes if and only if the set of all those who vote ”yes” is a winning coalition. Abstention plays a key role in many of the real voting systems that have been modeled by these games (such as the United Nations Security Council, or the United States federal system), yet simple games, by their very definition, do not take the possibility of abstention into account; those who do not vote “yes” are presumed to vote “no.” Felsenthal and Machover [6] define ternary voting games (TVGs), a generalization of simple voting games. This class of games is a particular case of the more general class of (j, k) games introduced by Freixas and Zwicker [11]. Taking j= 3 and k= 2 leads to (3,2) games that are equivalent to TVGs. In either of these models of games, abstention is treated as a level of approval intermediate to “yes” and “no”. ∗“Departament de Mathematiques i Escola Polit`ecnica Superior d’Enginyeria de Manresa, Universitat Polit`ecnica de Catalunya”, Spain. Research partially supported by “MTM2015-66818-P MINECO/FEDER” [email protected]. †Corresponding author : [email protected], University of Yaounde I, Cameroon ; MASS laboratory - University of Cergy Pontoise ; THEMA laboratory. ‡billpro[email protected], University of Yaounde I, Cameroon. 1 Defining a simple game requires to list winning coalitions. The representation is rather simple if it is a weighted game, but many decisions rules do not admit such a representation. A characterization of games that admit a representation as weighted game is due to Taylor and Zwicker [21] (see [22] for a complete description of weighted games and related games). Looking for a more convenient representation is another motivation of the work by Carreras and Freixas [3]. Since completeness is a necessary condition for a simple game to be representable as a weighted game, they argued that complete games constitute a natural framework for discussing the characterization of weighted voting. This paper deals with the class of complete simple games and centers on their structure. These authors showed that a complete simple game is determined uniquely, up to isomorphism, by a vector with positive integers components and a matrix with non-negative integers entries. Clearly, this is simpler and more intuitive than setting all the winning coalitions of the game. The present paper is a generalization of the former to simple games with abstention or (3,2) simple games. We obtain in this larger class of vote a similar result as that by Carreras and Freixas [3]. Our results allow us to obtain some enumerations of I-complete (3,2) games. They also allow us to simplify the task to determine whether a given I-complete (3,2) game is strongly weighted or not. This is a very important step for the resolution of voting game design problems, one of which is the well known inverse problem, (see Alon and Edelman [1], Kurz [15] and Dragan [5]). In this sort of problem, we look for a weighted voting game that minimizes the distance between the distribution of power 1among the players and a given target distribution of power (according to a given distance measure). In [14], Keijzer et al provide algorithms that solve voting game design problems by enumerating all games of interest. The algorithm has been improved in the subclass of weighted games. Our result is a preparation for the extension of the work by Keijzer et al [14], to voting games with abstention. The enumeration of I-complete (3,2) games we obtain is very restrictive. Indeed, unlike Kurz and Tautenhahn [16] who describe an approach to determine enumeration formulas for the number of complete simple games, as for I-complete (3,2) games, we are able to achieve this only for very small values of nthe number of players. The parameterization for I-complete (3,2) games we obtain in this paper combined with the application of some enumerating techniques may potentially serve for achieving further enumerations of I-complete (3,2) games and strongly weighted games. In order to achieve the results mentioned above, we follow the same methodology as Carreras and Freixas [3]. The main tool used in this paper is the desirability relation introduced by Isbell [13]. We consider the natural extension of this relation in (3,2) games, introduced by Tchantcho et al [23] and reconsidered in Pongou et al [19] and Freixas et al ([9], [10]). This extension is termed influence relation. The rest of the paper is organized as follows. In Section 2, we recall basic definitions on (3,2) games. We also extend the well known influence relation introduced by Tchantcho et al [23] to tripartitions and provide a characterization of indifference classes. In Section 3, we associate with any complete (3,2) game a multilattice of tripartition models which are represented by matrices since they are clearly easier to manipulate. The main result is presented in Section 4 in which we show that any (3,2) complete game is characterized, up to an isomorphism by a vector of 1See [7] for a full description on power measurement problem. 2 matrices, entries of which are non-negative integers. Such a representation is clearly simpler and more intuitive than enumerating all the winning tripartitions of the game. We apply it to the United Nations Security Council and show that this game is strongly weighted. Section 5 discusses our results and concludes the paper. All the proofs are presented in the Appendix. 2 Preliminaries : (3,2) simple games The materials on this section are essentially taken from Freixas and Zwicker [11], Tchantcho et al [23] and Freixas et al ([9], [10]). In [11], Freixas and Zwicker introduced (j, k) simple games, we consider the particular case where j= 3 and k= 2. Before the main notions are introduced we need some preliminary definitions. Throughout the paper, Ndenotes the non-empty and finite set of voters or players. An ordered tripartition of Nis a sequence S= (S1, S2, S3) of mutually disjoint subsets of Nwhose union is N. In S,S1stands for the set of yes voters, S2for abstainers and S3stands for no voters. We denote by 2Nthe set of all subsets of Nor the set of all ordered bipartitions of Nand by 3Nthe set of all ordered tripartitions of N. For any subset Cof Nand any a∈N, we simply write C∪a for C∪ {a}while C\astands for C\ {a}. For S, S0∈3Nwe write S⊆3S0to mean that either S=S0or Smay be transformed into S0by shifting 1 or more voters to higher levels of approval. Formally S⊆3S0⇔S1⊆S0 1and S2⊆S0 1∪S0 2; we write S⊂3S0if S⊆3S0and S6=S0. The ⊆3order defined in 3Nhas minimum: the tripartition (∅,∅, N), and maximum: the tripartition (N, ∅,∅). Hence for every tripartition S, (∅,∅, N)⊆3S⊆3(N, ∅,∅). Definition 2.1 A simple game (or (2,2) game) is a pair (N, V )where Nis the non-empty but finite set of voters and Vis a value function defined from 2Nto {0,1}such that for all coalitions C, C0, if C⊂C0then V(C) = 1 implies V(C0) = 1. It is often demanded that Vbe exhaustive, which leads to V(∅) = 0 and V(N) = 1. Definition 2.2 A(3,2) game G= (N, V )consists of a finite set Nof voters together with a value function V: 3N−→ {0,1}such that for all ordered tripartitions S, S0, if S⊂3S0then V(S) = 1 implies V(S0) = 1. A tripartition Ssuch that V(S) = 1 is said to be winning. A (3,2) game can be defined by its set of winning tripartitions, W={S∈3N:V(S) = 1}. In that case we denote the game by (N, W). In voting, it is often demanded that Vbe exhaustive, then from the monotonicity demanded to V,V(∅,∅, N) = 0 and V(N, ∅,∅) = 1. This enable us to obtain the equivalent definition below. Definition 2.3 A (3,2) game G= (N, W)consists of a finite set N of voters together with a set Wverifying the following conditions: •(∅,∅, N)/∈ W, •(N, ∅,∅)∈ W, 3 •If S⊂3Tand S∈ W then T∈ W (monotonicity). Standard notions on simple games naturally extend for tripartitions in (3,2) games : Sis a losing tripartition whenever S /∈ W,Sis a minimal winning tripartition provided that S∈ W and for all T∈3Nsuch that T⊂3S, T /∈ W. Let Wmdenote the set of minimal winning tripartitions. It is clear that Wor Wmuniquely determine the (3,2) game. Similarly, Sis a maximal losing tripartition if S /∈ W and for all Tsuch that S⊂3T,T∈ W. Furthermore, Lor LMuniquely determine the (3,2) game, where Lis the set of losing tripartitions and LMthe set of maximal losing tripartitions. Anonymous (3,2) games are games for which for all tripartition S,Sis winning if and only if for all permutation ϕ:N→N,ϕ(S)=(ϕ(S1), ϕ(S2), ϕ(S3)) is winning. Next, we introduce weighted (3,2) games, which is a special type of weighted (j, k) games introduced in [11]. Definition 2.4 Let G= (N, W)be a (3,2) game. A representation of Gas a weighted (3,2) game consists of a vector w= (w1, w2, w3)where wi:N→Rfor each i together with a real number quota q such that for every S∈3N, S ∈ W ⇔ w(S)≥qwhere w(S)denotes 3 P i=1 P a∈Si wi(a)and w1(a)≥w2(a)≥w3(a)for each a∈N. We say that G= (N, W)is a weighted (3,2) game if it has such a representation. According to the definition above, we can normalize, i.e. assign a zero weight, to any level of approval. Here we are mainly concerned with games with abstention for which we can normalize the weights at any of the three input levels, but it seems to be quite natural to choose the “abstention” level . If a null weight is assigned to abstainers, then a non-negative weight is assigned to “yes” voters and a non-positive weight to “no” voters. Thus, a weight 2w(a)=(w+(a),0, w−(a)) with w+(a)≥0 and w−(a)≤0 is assigned to each a∈N. The only requirement for the threshold q, if the (3,2) game is demanded to be exhaustive, is that: w(∅,∅, N) = P a∈N w−(a)< q ≤P a∈N w+(a) = w(N, ∅,∅). The previous definition can now be rewritten as follows : Gis weighted if there exists a sequence of weight functions (w+,0, w−) with w−(a)≤0≤w+(a) for all a∈N, and a quota qsuch that for all S= (S1, S2, S3)∈3N,S∈ W ⇐⇒ w(S) = P a∈S1 w+(a) + P a∈S3 w−(a)≥q. Two consecutive stronger conditions of a weighted (3,2) game are the following which were introduced in Freixas and Zwicker [11]: Definition 2.5 Astrongly weighted (3,2) game is a weighted (3,2) game that admits a representation such that for every pair of voters aand b, [w+(a)≥w+(b),−w−(a)≥ −w−(b)] or [w+(a)≤w+(b),−w−(a)≤ −w−(b)]. The influence relation defined in simple games were extended to (3,2) games by Tchantcho et al [23] as follows. 2We are identifying w+with w1, 0 with w2and w−with w3in Definition 2.4. 4 Definition 2.6 Let G= (N, W)be a (3,2) game, a, b ∈N: •ais said to be at least as influential as b, denoted a≥Ib, if a≥D+b,a≥D−band a≥D±b where : 1) D+-desirability : for all (S1, S2, S3)∈3Nsuch that a, b ∈S2, (S1∪b, S2\b, S3)∈ W ⇒ (S1∪a, S2\b, S3)∈ W 2) D−-desirability: for all (S1, S2, S3)∈3Nsuch that a, b ∈S3, (S1, S2∪b, S3\b)∈ W ⇒ (S1, S2∪b, S3\b)∈ W 3) D±-desirability: for all (S1, S2, S3)∈3Nsuch that a, b ∈S3, (S1∪b, S2, S3\b)∈ W ⇒ (S1∪a, S2, S3\a)∈ W •ais said to be strictly more influential than b, denoted a >Ibif a≥D+b, a ≥D−b, a ≥D±b and at least one of the three relations is strict. •ais said to be as influential as b, denoted a≡Ibif a≥Iband b≥Ia. In this case, players aand bare said to be I-equivalent. •Gis a I-complete (3,2) game if either a≥Ibor b≥Ibfor all pair a, b ∈N. It is straightforward to check that ≡Iis an equivalence relation on N. In the sequel, the equivalence classes will be denoted by N1, N2, . . . , Nt; the quotient set for ≡Iis then denoted and given by N/≡I={N1, . . . , Nt}. That is, a≡Ibif and only if aand bbelong to the same equivalence class. Furthermore, >Iinduces a ranking Ion the set of ≡I-classes. If a >Ib, a∈Nuand b∈Nvthen NuINvand we convey u<v. The I-influence relation, which is reflexive is neither complete nor transitive in general. However, it has been proved in [23] that it is transitive whenever it is I-complete. Particularly, in I-complete games, the influence relation is a complete preorder on the set of voters. We illustrate the I-influence relation through the following example that will be very useful in the sequel. From now on we will refer as nthe vector defined by : n= (n1, n2, ..., nt) where for all i= 1, ..., t,ni=|Ni|. In I-complete (3,2) games, we have : N1IN2I· · · INt. Example 2.7 Let us consider the 4-player game defined by : N={1,2,3,4}and Wm=(12,3,4),(12,4,3),(13,2,4),(14,2,3),(23,1,4), (24,1,3),(23,4,1),(13,4,2),(14,3,2),(24,3,1) where for instance, 12 represents {1,2}. The game is I-complete and there are two equivalence classes: the highest is N1={1,2}and the other class is N2={3,4}. More precisely, we have : 1 ≡I2>I3≡I4 or equivalently N1IN2. It is well known that in (2,2) games, weighted games are complete and there exist, when n≥6, complete games that are not weighted. Unlike in the (2,2) simple games, a weighted (3,2) game may not be I-complete. As well, I-completeness does not imply weightedness. However, if a (3,2) game is strongly weighted then it is I-complete but the converse is not true. Although for n= 2, I-completeness implies strongly weightedness. When n > 2, one may find for every nan I-complete game not being strongly weighted, see Freixas et al [9] for these known results. 5 We recall below the definition of transposition operation of two players within a given tripartition. Given a tripartition S= (S1, S2, S3) of Nand two players aand b,πab(S) is defined by : πab(S) = (πab(S1), πab(S2), πab(S3)) where for any coalition Cof N, πab(C) =    Cif {a, b} ∩ C=∅or {a, b} ⊆ C (C\a)∪bif a∈Cand b /∈C (C\b)∪aif a /∈Cand b∈C The following definition will be useful in the sequel. Definition 2.8 Let G= (N, W)be an I-complete (3,2) game. A tripartition Sis said to be shift-minimal winning if : Sis winning and πab(S)is losing for all a∈Si,b∈Sj,i < j and a >Ib. The set of shift-minimal winning tripartitions is denoted by Wsm. As in simple games, for any (3,2) game (N, W) it is straightforward to see that Wsm ⊆ Wm⊆ Wand these inclusions can be strict. In the sequel we would like to extend relations ≥Iand ≡Iwhich are defined on the set of players to the set of tripartitions. Given two tripartitions Sand T, consider the following binary relations on 3N. •T⊥Smeans that there exist a, b ∈Nwith a≡Ibsuch that πab(S) = T; •TaSmeans that either S⊆3Tor there exist two players aand bsuch that a≥Ib,a∈Sj, b∈Siwith i≤jand πab(S)⊆3T. Definition 2.9 Let Gbe an I-complete (3,2) game, S, T ∈3N, then : •Sis said to be equivalent to Tdenoted S∼ITif S⊥R1⊥ · · · ⊥ Rh=Tfor some integer number h. •Tis said to dominate Sdenoted T%ISif TaRha · · · a R1=Sfor some integer number h. It can be easily checked that ∼Iis an equivalence relation on 3N. Furthermore, %Iis a preordering in the set 3Nwith ∼Ias associated equivalence relation. Proposition 2.10 For all S, T ∈3N,T∼ISif and only if T%ISand S%IT. In the sequel, the ∼I-class of a tripartition S∈3Nwill be denoted by S. Proposition 2.11 Let (N, W)be an I-complete (3,2) simple game, N1, . . . , Nt, be the equivalence classes of ≡I, with ni=|Ni|for all 1≤i≤t. Then, 1) for all R, S ∈3N,S∼IR⇔ |Ni∩Sj|=|Ni∩Rj|for all i= 1,2, ..., t and all j= 1,2,3. 2-a) for all R, S ∈3N,if S=Rthen s=rwhere s= (si,j)and r= (ri,j)for all i= 1, ..., t and all j= 1,2,3, with si,j =|Ni∩Sj|; furthermore, 0≤si,j and 3 P j=1 si,j =nifor all i= 1,2, ..., t. 6 2-b) Conversely, for any matrix s= (si,j)i=1,...,t j=1,2,3 such that: 0≤si,j and 3 P j=1 si,j =nifor all i= 1, ..., t defines a unique ∼I-class S∈3N. 3) for any S∈3N, the cardinality of Sis given by : |S|= t Q i=1 (ni si,1)(ni−si,1 si,2). In the sequel, we shall call s= (si,j)i=1,...,t j=1,2,3 the matrix of indices associated with the class S: it provides the common model, in terms of equivalent players of all tripartitions belonging to S. 3 The multilattice associated with an I-complete (3,2) game It is clearly easier to manipulate models that are represented by matrices s= (si,j) rather than tripartitions themselves. Given an I-complete (3,2) game (N, W), we recall the notation n= (n1, . . . , nt) and denote by Λ(W) the set of all admissible models of tripartitions of the game, that is, Λ(W) = {s= (si,j) : 0 ≤si,j and 3 P j=1 si,j =nifor all i= 1, ..., t}and W={S∈3N:S∈ W} be the set of classes of winning tripartitions. We shall define a (dominance) relation in the set of Λ(W) in the spirit of Carreras and Freixas [3]. For this purpose, the following results are fundamental. Proposition 3.1 Let G= (N, W)be an I-complete (3,2) game. If S∈ W,a >Ib,a∈Sj,b∈Si with i<j, then πab(S)∈ W. Let G= (N, W) be an I-complete (3,2) game and assume that Gis not anonymous, which implies that t≥2 that is, it has at least two types of equivalent players. Let s= (si,j) be an element of Λ(W). For any fixed i0, i00,j0, j00 such that 1 ≤i0< i00 ≤tand 1 ≤j0< j00 ≤3, we define (when possible) the following matrix s0= (s0 i,j) where s0 i,j =           si,j + 1 if i=i0and j=j0 si,j −1 if i=i0and j=j00 si,j −1 if i=i00 and j=j0 si,j + 1 if i=i00 and j=j00 si,j otherwise This simply means that, for instance if t= 3 and s=s1,1s1,2s1,3 s2,1s2,2s2,3 s3,1s3,2s3,3, for i0= 1, i00 = 2 and j0= 1, j00 = 3 then we have s0=s1,1+ 1 s1,2s1,3−1 s2,1−1s2,2s2,3+ 1 s3,1s3,2s3,3 From the proposition above, we have the following corollary. Corollary 3.2 Let G= (N, W)be an I-complete (3,2) game. Let Sbe a tripartition represented by a matrix s= (si,j). Let i0, i00,j0, j00 with 1≤i0< i00 ≤tand 1≤j0< j00 ≤3such that the matrix s0= (s0i,j)is well defined. If S∈ W then S0∈ W, for all tripartition S0represented by the matrix s0. 7 Let Sand S0be two tripartitions represented by the models s= (si,j) and s0= (s0 i,j) respectively : •If S⊂3S0then we say that s0is a monotonic shift of s. •If there exist 1 ≤i0< i00 ≤tand 1 ≤j0< j00 ≤3, such that s0 i,j are all well-defined as above, then we will say that s0is an elementary positive shift of s. When necessary, we will say that s0is an elementary positive shift of sfor rows (i0, i00) and columns (j0, j00). •We will say that s0dominates sin Λ(W) if s0can be obtained from sby a sequence of monotonic and/or elementary positive shifts. We provide below an equivalent formulation for the dominance relation in the set Λ(W). Definition 3.3 Given r= (ri,j), s = (si,j)∈Λ(W),we have s δ r if : σ(s)<σ(r)where σ(s) = (σs i,j), with σs i,j =P i0≤i;j0≤j si0,j0 In the example 2.7, the matrix s=011 110dominates the matrix r=002 110by δ because σ(s) = 012 134,σ(r) = 002 124and hence σ(s)<σ(r). In the same example, s=011 110and u=101 011are not comparable by δ. It is easy to check that δis a partial ordering as stated below. Proposition 3.4 The binary relation δis a partial ordering on Λ(W). We shall also note s= (s1, s2, s3) where any sjis the column number jof s. Given two column vectors sjand rjfor any j= 1,2,3 of sand r, we denote by: sjδ0rjif Σi(sj)≥Σi(rj),∀i= 1,2, . . . , t with Σi(sj) = s1,j +s2,j +· · · +si,j . In words, sjδ0rjif for any row i, the sum of sj-components up to iis greater than or equal to the corresponding sum of rj. δ0is an ordering that need not be complete. Proposition 3.5 Given s, r ∈Λ(W),the following two statements are equivalent: •s δ r •either s1=r1and s2δ0r2 or s16=r1and (s1δ0r1and (s1+s2)δ0(r1+r2)) In the sequel we shall show that the pair (Λ(W), δ) is a multilattice that is, for all r, s ∈Λ(W), if we denote by Maj(r, s) the set of upper bounds of {s;r}and by Min(r, s) the set of lower bounds of {s;r}then, both of those sets are non-empty with a minimal and maximal element respectively. For all matrices r, s ∈Λ(W), define the following matrix u(r, s) or simply uas follows. Definition of ugiven r, s ∈Λ(W) 8 Let r, s ∈Λ(W) : Consider the following matrix Mdefined by: M= (Mi,j) where, Mi,j = max(σr i,j, σs i,j) and M0defined as follows: •M0 i,1=Mi,1for all 1 ≤i≤t; •M0 1,2=M1,2and M0 i,2=Mi,1+Mi−1,2−Mi−1,1if Mi,2+Mi−1,1−Mi,1−Mi−1,2<0 Mi,2otherwise for all 1 < i ≤t; •M0 i,3=Mi,3for all 1 ≤i≤t. We define u= (ui,j) to be the matrix such that σ(u) = M0, that is, •u1,1=M0 1,1and ui,1=M0 i,1−M0 i−1,1for all 1 < i ≤t. •u1,2=M0 1,2−M0 1,1and ui,2=M0 i,2+M0 i−1,1−M0 i−1,2−M0 i,1for all 1 < i ≤t. •ui,3=ni−ui,1−ui,2for all 1 ≤i≤t. It is easy to check that uis an element of Λ(W). We state below that in general, uis minimal in Maj(r, s) with Maj(r, s) = {v∈Λ(W) : v δ s and v δ r}. Lemma 3.6 For all r, s ∈Λ(W) •u∈Maj(r, s)and •uis minimal in Maj(r, s). We now define a matrix dlike uusing instead a matrix m= (mij) where : mi,j = min(σr i,j, σs i,j). We also consider the matrix m0defined as follows: •m0 i,1=mi,1for all 1 ≤i≤t; •m0 i,2=mi+1,2+mi,1−mi+1,1if mi+1,2+mi,1−mi+1,1−mi,2<0 mi,2otherwise for all 1 ≤i<tand m0 t,2=mt,2; •m0 i,3=mi,3for all 1 ≤i≤t. Definition of dgiven r, s ∈Λ(W) The matrix d= (dij) such that σ(d) = m0is define as follows: •d1,1=m0 1,1and di,1=m0 i,1−m0 i−1,1for all 1 < i ≤t; •d1,2=m0 1,2−m0 1,1and di,2=m0 i,2+m0 i−1,1−m0 i,1−m0 i−1,2for all 1 < i ≤t; and •di,3=ni−di,1−di,2for all 1 ≤i≤t. 9 We can conclude at this point that |Sp|=|Tp|for all p∈ {1,2,3}and hence πab(Tp) = Spand πcd(Sp) = Tpfor all p= 1,2,3. Since S6=T, there exists p0such that Sp06=Tp0. Either (c /∈Sp0and d∈Sp0) or (d /∈Sp0and c∈Sp0). With no loss of generality, assume that c /∈Sp0and d∈Sp0. Then, πab(Tp0) = Sp0and πcd(Sp0) = Tp0imply that πab(πcd(Sp0)) = Sp0. As d∈Sp0, it follows that c∈πcd(Sp0) and thus c∈πab(πcd(Sp0)) = Sp0, which is a contradiction, hence, (a, b) = (c, d). As (a, b)=(c, d), we then have, (πab(T)⊆3S, a ≥Ib), and (πab(S)⊆3T, b ≥Ia) so, πab(T)⊆3Sand T⊆3πab(S)⊆3T: consequently, πab(S) = T, which together with a≡Ibyield S⊥T. Proof of Proposition 2.11 Let (N, W) be an I-complete (3,2) simple game, N1, N2, . . . , Nt, be the equivalence classes of ≡I, with |Ni|=nifor all 1 ≤i≤t. 1. ⇒) Since S∼IR, R =f(S) with f:N→Na product of transpositions of equivalent players; therefore f(Ni) = Nifor all i. It follows that for all j= 1,2,3 and for all i= 1, . . . , t, Rj∩Ni=f(Sj)∩f(Ni) = f(Sj∩Ni) so, |Rj∩Ni|=|Sj∩Ni|for all iand all jbecause f is bijective. ⇐) Conversely, assume that |Sj∩Ni|=|Rj∩Ni|for all j= 1,2,3 and all i∈ {1,2, ..., t}. Let A={j:Si=Rj}: then |A| ∈ {0,1,2,3}. (a) If |A| ≥ 2 then it is obvious that S=Rand it follows that S∼IT. (b) If |A|= 1 then assuming with no loss of the generality that S1=R1, we have: S26=R2 and S36=R3. It follows from |Sj∩Ni|=|Rj∩Ni|for all i, j that |S2|−|S2∩R2|=|R2|−|S2∩R2|and |S3|−|S3∩R3|=|R3|−|S3∩R3|; thus, |S2\R2|=|R2\S2|and |S3\R3|=|R3\S3|. Furthermore, we have : For all i= 1, ..., t,|(S2\R2)∩Ni|=|(R2\S2)∩Ni| |(S3\R3)∩Ni|=|(R3\S3)∩Ni|(∗) |(S2∪R2)\(S2∩R2)|=|(S2\R2)∪(R2\S2)| =| t S i=1 ((S2\R2)∩Ni)|+| t S i=1 ((R2\S2)∩Ni)| = t P i=1 |(S2\R2)∩Ni|+ t P i=1 |(R2\S2)∩Ni| = 2 t P i=1 |(S2\R2)∩Ni| since |(S2\R2)∩Ni|=|(R2\S2)∩Ni|for all i. Now let m= t P i=1 |(S2\R2)∩Ni|:m6= 0 because S26=R2. We shall now proceed by induction on min order to ”transform” Sinto R . Let a∈(S2\R2)∩Niand b∈(R2\S2)∩Niand let us consider the transposition π(1) =πab such that: S0 2=π(1)(S2). 16 Then m0= t P i=1 |(S0 2\R2)∩Ni|=m−1 and by induction we obtain a sequence (π(1), π(2), . . . , π(m)) of transpositions of equivalent players such that: π(m)◦π(m−1) ◦ · · · ◦ π(1)(S2) = R2. We consider the application f:N→Nwhich is the product of the mtranspositions of indifferent players that leads to : f(S2) = R2. We then have: f(S) = (f(S1), f(S2), f(S3)) = (R1, R2, f(N\(S1∪S2))) = Rand it follows that S∼IR. (c) If |A|= 0 then Sj6=Rj, for all j. •Since S16=R1we consider m= t P i=1 |(S1\R1)∩Ni|. Using induction on nand a similar proof to the one used in (1.b) we show that there exists a mapping g:N→N product of transpositions of indifferent players such that g(S) = (R1, S0 2, S0 3); hence S∼Ig(S). If g(S2) = R2then g(S3) = R3and it follows that g(S) = Rand hence S∼IR. If g(S2)6=R2, then g(S) = (R1, S0 2, S0 3) with S0 26=R2, that is |{j:g(Sj) = Tj}| = 1. •Note that g(S) satisfies (∗). We can now refer to (1.b) to deduce that g(S)∼IR. The conclusion S∼IRthen follows. (d) The two equalities and the inequality are obvious. (e) Any tripartition Tof the ∼I-class Sis obtained by choosing for every i, si,1players in Nito form T1and choosing for any i,si,2players among the ni−si,1remaining players in Nito form T2. The remaining players form T3. 2. This comes directly from the procedure above and merely states the number of ways Scan be formed.  Proof of Proposition 3.1 Consider Rthe tripartition obtained from Sby moving player bfrom the j-th level to the i-th level. Then both aand bbelong to Ri If Ris winning, then by monotonicity, πab(S) is winning. If Ris losing, as a >Ib, we have a≥D+b,a≥D−band a≥D±b. If j= 1 and i= 2, a≥D+bimplies that πab(S) is winning. If j= 1 and i= 3, a≥D±bimplies that πab(S) is winning. If j= 2 and i= 3, a≥D−bimplies that πab(S) is winning.  Proof of Corollary 3.2 As s0is well defined, si0,j00 >0 and si00,j0>0. It follows that there exists a, b ∈Nsuch that, a∈Sj00 ∩Ni0and b∈Sj0∩Ni00 . We have a∈Ni0and b∈Ni00 with i0< i00 : thus a >Ib. At the same time a∈Sj00 and b∈Sj0with j0< j00 so it follows from Proposition 3.1 that πab(S)∈ W, since S∈ W. As the tripartition πab(S) is represented by the matrix s0, we have πab(S)∈S0; hence S0∈ W. 17 Proof of Proposition 3.4 It is obvious that δis reflexive and antisymmetric. Now let s, r and v∈Λ(W) such that: s δ r and r δ v. It follows that, σs i,j ≥σr i,j ∀i, j and σr i,j ≥σv i,j ∀i, j, hence σs i,j ≥σv i,j ∀i, j. Thus s δ v and δis an ordering on Λ(W). In Example 3.8 the tripartitions (13,4,2) and (23,14,∅) which are represented by the models: s=1 0 0 0 0 1 1 1 0 and v=0 1 0 1 0 0 1 1 0 are not δ-comparable since σ(s) = 1 1 1 1 1 2 2 3 4 and σ(v) = 0 1 1 1 2 2 2 4 4 . Hence δis a partial order.  Proof of Proposition 3.5 (⇒) Let us suppose that for any two models sand rof Λ(W), σ(s)<σ(r). We shall prove that: either s1=r1and s2δ0r2 or s16=r1and (s1δ0r1and (s1+s2)δ0(r1+r2)) σ(s)<σ(r) means that σs i,j ≥σr i,j ∀i, j. Since σs i,1≥σr i,1∀i= 1,2, . . . , t, we have X i0≤i si0,1≥X i0≤i ri0,1∀i= 1,2, . . . , t. It is easy to remark that X i0≤i si0,1= Σi(s1). So, Σi(s1)≥Σi(r1) and hence s1δ0r1. •If there exists a row isuch that Σi(s1)>Σi(r1) then s16=r1. Since σs i,2≥σr i,2∀i= 1,2, . . . , t, we have X i0≤i,j0≤2 si0,j0≥X i0≤i,j0≤2 ri0,j0∀i= 1,2, . . . , t (?). We remark that X i0≤i,j0≤2 si0,j0= Σi(s1+s2) hence, Σi(s1+s2)=Σi(r1+r2)∀i= 1,2, . . . , t and thus (s1+s2)δ0(r1+r2). •If not, then s1=r1and using (?) we conclude that Σi(s1+s2)≥Σi(r1+r2)∀i= 1,2, . . . , t. Since Σi(s1+s2)=Σi(s1)+Σi(s2) we conclude that Σi(s2)≥Σi(r2)∀i= 1,2, . . . , t, that is, s2δ0r2. ⇐) Let us now suppose that for any two models sand rof Λ(W) we have: either s1=r1and s2δ0r2 or s16=r1and (s1δ0r1and (s1+s2)δ0(r1+r2)) We need to prove that σ(s)<σ(r). •If s1δ0r1and (s1+s2)δ0(r1+r2) then we have, σs i,1≥σr i,1and σs i,2≥σr i,2∀i= 1,2, . . . , t. Thanks to the equalities σs i,1= Σi(s1) and σs i,2= Σi(s1+s2)∀i= 1,2, . . . , t, we obtain σs i,3= Σi(s1+s2+s3) = n1+n2+· · · +ni= Σi(r1+r2+r3) = σr i,3∀i= 1,2, . . . , t. Hence σs i,j ≥σr i,j ∀i= 1,2, . . . , t and j= 1,2,3. 18 •If s1=r1and s2δ0r2it can easily be checked as well that σs i,j ≥σr i,j ∀i= 1,2, . . . , t and j= 1,2,3. Finally, we conclude that σ(s)<σ(r).  Proof of Lemma 3.6 Let r, s ∈Λ(W). 1. Let 1 ≤i≤tand j= 1,2,3, σu i,j =M0 i,j ≤Mi,j = max(σr i,j;σs i,j)≥σr i,j, hence σ(u)<σ(r) and thus u δ r. Likewise we have u δ s. 2. Next, consider v∈Λ(W) such that v∈Maj(s, r). We shall prove that if u δ v then v=u. It is then useful to prove that v δ u. It follows from the definition of M0that M0<Mand for this purpose we will distinguish two cases. •Case1 :M=M0 Let 1 ≤i≤tand j= 1,2,3 then σu i,j =M0 i,j =Mi,j = max(σs i,j;σr i,j)≤σv i,j since v∈Maj(s, r), hence v δ u and thus v=u. •Case2 :M0<Mand M06=M It follows from v δ r and v δ s that σ(v)<M. It follows from the definition of M0that there exists l, (1 < l ≤t) such that M0 l,2> Ml,2 and for all i, (1 ≤i≤t) such that M0 i,j ≤Mi,j,we have M0 i,j =Mi,j for j= 1,2,3. For such i, we have σv i,j ≤σu i,j =M0 i,j =Mi,j ≤σv i,j hence σv i,j =Mi,j =σu i,j. We also have σu l,2≤σv l,2. Indeed if σu l,2> σv l,2then we would have: vl,2=σv l,2+σv l−1,1−σv l,1−σv l−1,2< M0 l,2+Ml−1,1−Ml,1−Ml−1,2= 0, since σv l,2< σu l,2=M0 l,2. Hence vl,2<0 which is impossible since v∈Λ(W). Therefore, σ(v)<σ(u) and thus v δ u. Proof of Lemma 3.7 Let r, s ∈Λ(W). 1. First let us show that s δ d and r δ d. Let 1 ≤i≤tand j= 1,2,3 then σd i,j =m0 i,j ≤mi,j = min(σs i,j;σr i,j)≤σs i,j, hence σ(s)<σ(d) and thus s δ d. Likewise we prove that r δ d. 2. Next, consider v∈Λ(W) such that v∈Min(s, r). We shall prove that if v δ d then v=d. It’s then useful to prove that d δ v. It follows from the definition of m0that m<m0and for this purpose we will distinguish two cases. •Case1 :m=m0 Let 1 ≤i≤tand j= 1,2,3 then σd i,j =m0 i,j =mi,j = min(σs i,j;σr i,j)≥σv i,j since v∈Min(s, r), hence d δ v and thus v=d. 19 •Case2 :m<m0and m6=m0 It follows from r δ t and s δ t that m<σ(v). It follows from the definition of m0that there exists l, (1 ≤l < t) such that m0 l,2< ml,2 and for all i, (1 ≤i≤t) such that m0 i,j ≥mi,j,we have m0 i,j =mi,j for j= 1,2,3. For such i, we have σv i,j ≥σd i,j =m0 i,j =mi,j ≥σv i,j hence σv i,j =mi,j =σd i,j. We also have σd l,2≥σv l,2. Indeed if σv l,2> σd l,2then we would have: vl+1,2=σv l+1,2+σv l,1−σv l+1,1−σv l,2< ml+1,2+ml,1−ml+1,1−m0 l,2= 0, since σv l,2> σd l,2= m0 l,2. Hence vl+1,2<0 which is impossible since v∈Λ(W). Therefore, σ(d)<σ(v) and thus d δ v. Proof of Lemma 3.10 It suffices to prove that for any S, R ∈3Nif R⊆3Sor there exists u, v ∈Nwith u∈Sm, v ∈Sl with l≤mand u≥Iv, such that πuv(R) = Sthen s δ r. If R⊆3Sthen R1⊆S1and R1∪R2⊆S1∪S2. It then follows that ri,1≤si,1and ri,1+ri,2≤si,1+si,2∀i= 1, . . . , t. This later inequality implies Σi(r1)≤Σi(s1) (i) and (s1+ s2)δ0(r1+r2). (ii) •If s1=r1then ri,2≤si,2∀i= 1, . . . , t, hence Σi(r2)≤Σi(s2)∀i= 1, . . . , t and consequently s2δ0r2; thus, s δ r. •If s16=r1then s1δ0r1from (i) and with (ii) we have s δ r. If πuv(R) = Swith u≥Iv,u∈Sm, v ∈Sland l≤m, let u∈Npand v∈Nqthen p≤qsince u≥Iv. •If l=mthen s=rand s δ r. •If l < m : on one hand, if p=qthen s=rand thus s δ r. On the other hand, if p<qthen sp,l =rp,l + 1, sq,l =rq,l −1, sp,m =rp,m −1, sq,m =rq,m + 1, si,j =ri,j for all j6=l, m and all i6=p, q. This means that sis an elementary positive shift of rand therefore, s δ r. Proof of Theorem 3.11 We need to prove that Φ : (3N/∼I,I)−→ (Λ(W), δ) S7−→ s= (si,j)i=1,...,t j=1,2,3 is an isomorphism of ordered sets. It follows from proposition 2.11 that Φ is well defined and bijective. Now, let S, R ∈3N: set s= Φ(S) and r= Φ(R). The implication SIR⇒s δ r follows directly from the lemma above. Now assume that s δ r : let us prove that SIR. In order to achieve this, we will construct a matrix Usuch that SIUIR, that is, S%IU%IR. As s δ r, we have: 20 either s1=r1and s2δ0r2 or s6=rand (s1δ r1and Σi(s1+s2)≥Σi(r1+r2)∀i= 1,2. . . t) Case 1: If s1=r1and s2δ0r2, let l < t be the smallest index such that : Σl(s2)≥Σt(r2). Consider the matrix u= (ui,j) defined as follow:    ui,1=si,1=ri,1∀i= 1, ..., t ui,2=si,2∀i < l, ul,2= Σt(r2)−Σl−1(s2), ui,2= 0 ∀i>l ui,3=si,3∀i < l, ul,3=nl−ul,1−ul,2, ui,3=ni−ui,1∀i>l By construction, u∈Λ(W). Let U∈3N/∼Isuch that u= Φ−1(U). By definition of uwe have : s2δ0u2(1); Σt(u2) = Σt(r2) (2); s δ u (3) and u δ r (4). Since s1=u1=r1, there exist two maps f:N→Nand g:N→Nproduct of transpositions of indifferent players such that f(R1) = U1and g(U1) = S1. Denote f(R)=(U1, R0 2, R0 3) and g(U) = (S1, U0 2, U0 3) : then f(R)∼IRand g(U)∼IU. •In order to prove that U%IR, let us proceed by induction on m=X ui,2≥ri,2 (ui,2−ri,2). - If m= 0 then u2=r2and since u1=r1, it then follow that u=rand hence U%IR. - If m > 0 then, let k < t be the smallest index such that uk,2> rk,2. From (4), we have u1,2=r1,2, ..., uk−1,2=rk−1,2. Thanks to (2) there exist an index h>ksuch that uh,2< rh,2. Consider the smallest such index h: and let a∈(U2∩Nk)\R0 2and b∈(R0 2∩Nh)\U2. Since k < h, we have a >Iband bIa. Let π(1) =πab and R00 2=πab(R0 2).Then R00 2verifies (1) and (2) and X ui,2≥r0 i,2 (ui,2−r0 i,2) = m−1. We obtain by induction a sequence (π(1), π(2), π(3), . . . , π(m)) of transpositions of players of different classes such that π(m)◦π(m−1) ◦ · · · ◦ π(1)(R0 2) = U2. Let Γ = π(m)◦π(m−1) ◦ · · · ◦ π(1). Then Γ(R0 2) = U2. Since Γ(f(R)) = Γ(U1, R0 2, R0 3) = (U1, U2,Γ(R0 3)), it follows that Γ(f(R)) = Uand hence U%If(R). Since f(R)∼IRwe deduce that U%IR. •In order to prove that S%IU, we will proceed by induction on m=|U0 2\S2|. Subscase 1 : If m= 0 then U0 2⊆S2and g(U)⊆3S, thus, S%Ig(U). Subscase 2 : If m > 0, then there exists a∈N:a∈U0 2\S2. With no loss of the generality, let us assume that a∈(U0 2\S2)∩Ni. Since si,2≥ui,2, there exists b∈(S2\U0 2)∩Ni. Thus, a≡Ib,U00 2=πab(U0 2) satisfies (1) and |U00 2\S2|=m−1. We obtain by induction a sequence (πab =π(1), π(2), . . . , π(m)) of transpositions of equivalent players such that π(m)◦π(m−1) ◦ · · · ◦ π(1)(U0 2)⊆S2. By letting Γ0=π(m)◦π(m−1) ◦ · · · ◦ π(1), we have Γ0(U0 2)⊆S2. It is straightforward that Γ0(g(U)) ⊆3S; hence S%Ig(U). Since g(U)∼IUwe deduce that S%IU. The case 1 is now complete, thanks to U%IRand S%IU, it follows that S%IR, which means that SIR. Case 2 : If s1δ0r1, s16=r1and (s1+s2)δ0(r1+r2) . Again, let l < t be the smallest index such that Σl(s1)≥Σt(r1). Consider the following matrix u= (ui,j) : 21    ui,1=si,1∀i < l, ul,1= Σt(r1)−Σl−1(s1), ui,1= 0 ∀i>l ui,2=ni−ui,1−ui,3,∀i= 1, ..., t ui,3=ri,3∀i= 1, ..., t Once more, as u∈Λ(W), let U∈3N/∼Isuch that u= Φ−1(U). We deduce from the definition of uthat : si,1≥ui,1∀i= 1,2, . . . , t (1) ; Σt(u1) = Σt(r1) (2); Σi(s1+s2)≥Σi(u1+u2)∀i= 1,2, . . . , t (3); s δ u (4) u δ r (5). Recall that we want to prove that SIUIR, that is, S%IU%IR. Since u3=r3there exists a mapping h:N→N, product of transpositions of equivalent players such that: h(R3) = U3. Let h(R) = (R0 1, R0 2, U3) : then h(R)∼IR. •Let us show that U%IR: let m=X ui,1≥ri,1 (ui,1−ri,1). By using a similar reasoning as in Case 1, and proceeding by induction on m, we obtain U%Ih(R). Now thanks to the fact that h(R)∼IR, it follows that U%IR. •Let us show that S%IU. For this purpose, let m=|U1\S1|. Subcase 1 : If m= 0, then U1⊆S1because si,1≥ui,1∀i= 1, . . . , t. Let U0= (S1, U0 2, U0 3) where U0 2=U2\A,A= (S1\U1)∩U2,U0 3=U3\Bwith B= (S1\U1)∩U3. We then have U⊆3U0because U1⊆S1and U1∪U2=S1∪U0 2. So, U0%IU(?). Now, it is enough to show that S%IU0. Since s1=u0 1and Σt(u0 2)≤Σt(u2), U0verifies (4) and hence Σt(s2)≥Σt(u0 2). If Σt(s2)=Σt(u0 2) then by induction on m0=X si,2≥u0 i,2 (si,2−u0 i,2), we prove as above that S%IU0. In addition, if Σt(s2)>Σt(u0 2), then there exists a mapping K1:N→Nproduct of transpositions of equivalent players such that K1(U0) = (S1, U00 2, U00 3) where U00 2satisfies (1). In addition, U0∼IK1(U0) (??). By induction on m00 =|U00 2\S2|, we prove identically that S%IK1(U0) (???). Now, thanks to (?), (??) and (???), we deduce that S%IU0%IUhence S%IU. Subcase 2 : If m > 0, then by proceeding as we did in Subcase 2 of case 1, we prove the existence of a mapping K2:N→Nproduct of transpositions of equivalent players such that K2(U1)⊆S1. Let K2(U) = (K2(U1), U0 2, U0 3) : this meets the subcase just done above (m= 0) by merely replacing Uwith K2(U). We can therefore use the same reasoning to conclude that S%IU0∼IUand hence S%IU. Finally, we obtain S%IU%IR. Proof of Proposition 4.1 From the inclusions Wsm ⊆ Wm⊆ W, it follows that Wsm ⊆ Wm⊆ W. Hence Wm⊆ Wm⊆ W since Wsm =Wm. Proof of Theorem 4.2 We consider Mas defined in the text. 1. This point comes from the fact that any mpbelongs to Λ(W). 22 2. If r > 1, let p6=q. Then mpand mqare not δ-comparable : indeed, if (for example) mpδ mq, then, Sq/∈ Wmwith mq= Φ(Sq) which is a contradiction. 3. (i) Assume that : t=r= 1.If the vector m1= (0,0, n) then (∅,∅, N) would be a winning tripartition, which is impossible. (ii) Now assume that t > 1. If the condition [there exists some psuch that (mp i,1>0 and mp i+1,1< ni+1) or (mp i,3< niand mp i+1,3>0)] is not true for some i<t, then any component of the vector Mshould be one of the following four forms : Form 1:   mp 1,1mp 1,2mp 1,3 mp 2,1mp 2,2mp 2,3 ... ... ... 0 0 ni ... ... ... mp t,1mp t,2mp t,3  , Form 2:    mp 1,1mp 1,2mp 1,3 ... ... ... 0mp i,2mp i,3 mp (i+1),1mp (i+1),20 ... ... ... mp t,1mp t,2mp t,3   , Form 3:   mp 1,1mp 1,2mp 1,3 ... ... ... 0 0 ni ni+1 0 0 ... ... ... mp 1tmp 2tmp 3t  , Form 4:   mp 1,1mp 1,2mp 1,3 mp 2,1mp 2,2mp 2,3 ... ... ... ni+1 0 0 ... ... ... mp t,1mp t,2mp t,3  . (a) •In the sequel, we will prove that in either form, for all a∈Niand b∈Ni+1 we have b≥Ia. Let a∈Niand b∈Ni+1. We will prove that b≥D+a,b≥D−aand b≥D±a. The proof of b≥D+a Let S∈3Nsuch that a, b ∈S2and (S1∪a, S2\a, S3)∈ W. We need to prove that (S1∪b, S2\b, S3)∈ W, that is, there exists psuch that s0= Φ(S1∪b, S2\b, S3)δ mp. Let s= Φ(S1∪a, S2\a, S3) : since (S1∪a, S2\a, S3)∈ W, we have s δ mpfor some p. In the sequel we will prove that s0δ mp. •If mpis of Form 1, then s1δ0mp 1and s16=mp 1as si,1>0, Σh(s1)≥Σh(mp 1)∀h6=iand Σi(s1)>Σi(mp 1). We claim that s0 1δ0mp 1: indeed, Σh(s1) = Σh(s0 1) for all h < i, Σi(s0 1) = Σi(s1)−1,and Σh(s0 1)=Σh(s1) for all h≥i+ 1. We also claim that Σh(s0 1+s0 2)≥Σh(mp 1+mp 2) for all h= 1, ..., t. Indeed, Σh(s0 1+s0 2) = Σh(s1+s2)≥Σh(mp 1+mp 2) for all h6=iand Σi(s0 1+s0 2) = Σi(s1+s2)−1≥Σi(mp 1+mp 2). So, if s0 16=mp 1, then it follows that s0δ mp. However, if it happens that s0 1=mp 1, in order to conclude that s0δ mp, we will show that s0 2δ0mp 2. We proved above that for all h= 1, ..., t, Σh(s0 1+s0 2)≥Σh(mp 1+mp 2) and s0 1=mp 1implies Σh(s0 1) = Σh(mp 1), thus Σh(s0 2)≥Σh(mp 2) for all h, hence, s0 2δ0mp 2. •If mpis of Form 2 or 3, the proof is quite similar to that of the case where mpis of Form 1. 23 •If mpis of Form 4, then s1δ0mp 1and s16=mp 1because s(i+1),1< ni+1. Since s(i+1),1< ni+1 and Σi+1(s1)≥Σi+1(mp 1), it follows that Σi(s1)>Σi(mp 1). Since s(i+1),1< ni+1 and Σi+1(s1)≥Σi+1(mp 1), it follows that Σi(s1)>Σi(mp 1). We can now proceed exactly as in the first form to get s0δ mp. The proof of b≥D±a: similar to the proof of b≥D+a The proof of b≥D−a Let S∈3Nsuch that a, b ∈S2and (S1, S2∪a, S3\a)∈ W. We need to prove that (S1, S2∪b, S3\b)∈ W, that is, there exists psuch that s0= Φ(S1, S2∪b, S3\b)δ mp. Let s= Φ(S1, S2∪a, S3\a) : since (S1, S2∪a, S3\a)∈ W, we have s δ mpfor some p. In the sequel we will prove that s0δ mp. Since s δ mp, either [s1δ0mp 1,s16=mp 1and Σi(s1+s2)≥Σi(mp 1+mp 2)∀i,] or [s1=mp 1and s2δ0mp 2]. •If mpis of Form 1, then Σh(s0 1) = Σh(s1)∀h, Σh(s2) = Σh(s0 2)∀h < i, Σi(s0 2) = Σi(s2)−1 and Σh(s0 2) = Σh(s2) for all h > i. - If [s1δ0mp 1,s16=mp 1and Σi(s1+s2)≥Σi(mp 1+mp 2)∀i], then s0 1δ0mp 1and s0 16=mp 1 because s0 1=s1. In addition, Σh(s0 1+s0 2) = Σh(s1+s2)≥Σh(mp 1+mp 2) for all h6=iand Σi(s0 1+s0 2)=Σi(s1+s2)−1≥Σi(mp 1+mp 2), hence s0δ mp. - If [s1=mp 1and s2δ0mp 2], then s0 1=mp 1. We claim that s0 2δ0mp 2: Indeed, Σh(s0 2) = Σh(s2)≥Σh(mp 2)∀h < i , Σi(s0 2) = Σi(s2)−1≥Σi(mp 2), and Σh(s0 2) = Σh(s2)≥Σh(mp 2) ∀h > i. It then follows that s0δ mp. •If mpis of Form 2 - If [s1δ0mp 1,s16=mp 1and Σi(s1+s2)≥Σi(mp 1+mp 2)∀i] By proceeding as in the form 1, we get s0δ mp. - Assume that [s1=mp 1and s2δ0mp 2] By construction, we have s0 1=s1, thus, s0 1=mp 1. It remains to show that s0 2δ0mp 2. If s2=mp 2then s3=mp 3and hence s(i+1),3= 0 which is a contradiction since b∈S3\a. We then have s(i+1),2< mp (i+1),2. Indeed, mp (i+1),2=ni+1 −mp (i+1),1=ni+1 −s(i+1),1=s(i+1),2+ s(i+1),3> s(i+1),2since s(i+1),3>0. It follows that From s2δ0mp 2and s(i+1),2< mp (i+1),2, we have Σi(s2)>Σi(mp 2). In summary, Σh(s0 2)=Σh(s2)≥Σh(mp 2)∀h < i, Σi(s0 2) = Σi(s2)−1≥Σi(mp 2) and Σh(s0 2) = Σh(s2)≥Σh(mp 2) for all h > i. We conclude that s0 2δ0mp 2. •If mpis of Form 3 or 4, the proof is quite similar to that of the case where mpis of Form1.  Proof of Theorem 4.3 Proof of a) 24 ⇒) Let f: (N, W)→(N0,W0) be an isomorphism. Then the inverse map f−1is also an isomorphism and that πf(a)f(b)=f◦πab ◦f−1for all a, b ∈N. It then follows that a≥Ib⇔f(a)≥I0f(b); that is fpreserves the influence relation and hence it preserves individual and coalitional indifference and coalitional dominance. Moreover, finduces a multilattice isomorphism f: (3N;1 )→(3N0;1) such that f(W) = W0. The map φ: (Λ(W); δ)→(Λ(W0); δ0) is an isomorphism because φ= Φ0◦f◦Φ−1is a product of isomorphisms. Both games have, therefore, a common set of models of shift-minimal winning tripartitions. Since they are lexicographically ordered by rows, we conclude that M=M0. ⇐) Assume that M=M0: Let us prove that there exists an isomorphism f: (N, W)→(N0,W0). Let N1={k1, . . . , kn1},N0 1={l1, . . . , ln1}and Ni={kn1+···+ni−1+1, . . . , kn1+···+ni}, N0 i={ln1+···+ni−1+1, . . . , ln1+···+ni}for all i= 2, . . . , t. Let us consider the mapping : f:N−→ N0 kp7−→ lp It is obvious that fis bijective and f(Ni) = N0 i∀i= 1, . . . , t. Assume that S∈ W. If s= Φ(S), then s δ mpfor some p. Let S0=f(S) and s0= Φ0(S0). Given that M=M0,mpis an element of M0. Thanks to the equality s0=sthat comes from the definition of f, it follows that s0δ mpand S0∈ W0. Applying the same argument to f−1it follows that the implication f(S)∈ W0⇒S∈ W holds, thus, fis an isomorphism. Proof of b) Let Msatisfying conditions of Theorem 4.2. We need to construct an I-complete (3,2) game the characteristic invariant of which is M. Let n= Σt(n) = n1+n2+· · · +nt, N={1,2, . . . , n}and N1, N2, . . . , Ntbe the subsets of Nformed, respectively, by n1, n2, . . . , nt, elements (which may be chosen following the natural ordering). By theorem (4.2), none of these subsets is empty. For each S∈3Nwe define s= (si,j )j=1,2,3 i=1,...,t where si,j =|Sj∩Ni| ∀j= 1,2,3 and i= 1, . . . , t. Let W={S∈3N:s δ mpfor some p}. We will prove that (N, W) is a (3,2) I-complete simple game whose characteristic invariant is M. 1. It is straightforward that (N, W) is a (3,2) simple game. 2. We shall now prove that N1, N2, . . . , Ntare equivalence classes according to the relation ≡I and they are linearly ordered (N1> N2>· · · > Nt). •Let i∈ {1,2, ..., t},a, b ∈Niand S∈3N. -Proof of b≥D+a.If a, b ∈S2such that (S1∪a, S2\a, S3)∈ W then by considering s= Φ(S1∪a, S2\a, S3) and s0= Φ(S1∪b, S2\b, S3), we have s=s0. Since (S1∪a, S2\a, S3)∈ W we have, s δ mpfor some pso that s0δ mp. Hence (S1∪b, S2\b, S3)∈ W and b≥D+a. - We prove in the same way that b≥D−aand b≥D±a, thus b≥Ia. By the same arguments, we obtain a≥Ibconsequently a≡Ib. •Now let i∈ {1,2, ..., t},a∈Ni, b ∈Ni+1 and S∈3N. We will prove that a≥Iband ba. 25