On the characterization of weighted simple games

On the characterization of weighted simple games Josep Freixas∗ , Marc Freixas†and Sascha Kurz‡ Abstract This paper has a twofold scope. The first one is to clarify and put in evidence the isomorphic character of two theories developed in quite different fields: on one side, threshold logic, on the other side, simple games. One of the main purposes in both theories is to determine when a simple game is representable as a weighted game, which allows a very compact and easily comprehensible representation. Deep results were found in threshold logic in the sixties and seventies for this problem. However, game theory has taken the lead and some new results have been obtained for the problem in the last two decades. The second and main goal of this paper is to provide some new results on this problem and propose several open questions and conjectures for future research. The results we obtain depend on two significant parameters of the game: the number of types of equivalent players and the number of types of shift-minimal winning coalitions. Key words: simple games; weighted games; characterization of weighted games; trade robustness; invariant-trade robustness, asummability AMS codes: 91A12; 06E30; 94C10; 68T27; 92B20 1 Introduction The study of switching functions goes back at least to Dedekind’s 1897 work [9], in which he determined the exact number of simple games with four or fewer players. Since that time these structures have been investigated in a variety of different contexts either theoretically [26, 29, 28, 30, 5] in the context of Boolean functions or because of their numerous applications: neural networks [1], simple games [48, 34, 35, 51], threshold logic [13, 8, 25, 33, 44], hypergraphs [54], coherent structures [53], learning theory [42], complexity theory [4], and secret sharing [57, 59, 3]. Several books on neural networks have studied these structures: [49, 55, 58, 52]. Logic gates, switching functions or Boolean functions can be thought of as simple games, with weighted games playing the role of threshold functions. To the best of our knowledge the first work linking threshold logic and simple games is due to Dubey and Shapley [11] and a compact study encompassing knowledge in both fields is due to Taylor and Zwicker [63]. As an example for a switching function or a simple game one may consider the process of coordination of the weekend activities of a family. Assume that the family consists of the parents Ann and Bob and their children Claire and Dylan. A proposal is accepted if at least one of the parents and at least one of the children agrees, while each person can either agree or disagree. The underlying decision rule can be modeled as a simple game.1A compact way to represent a simple game is by using weights for each player such that a proposal is accepted if and only if the weight sum of its supporters meets or exceeds a given quota (or threshold). If such a representation exists, the simple game is called a weighted game. In our example no weighted representation exists, since the coalitions of the parents and of the children cannot push through a proposal, while they can if they split differently in coalitions of size two.2However, every simple game can be written as the intersection of some weighted games. The Lisbon voting rules of the EU Council provide a non-weighted real–world example where quite a few weighted games are need in such a representation, see [40] for the details. ∗Universitat Polit`ecnica de Catalunya (Campus Manresa), in the Department of Mathematics; Av. Bases de Manresa, 61-73, E-08242 Manresa, Spain. †Industrial Engineer working for Cirprotec, E-08233 Terrassa, Spain. ‡University of Bayreuth, in the Department of Mathematics; 95440 Bayreuth, Germany. 1The minimal winning coalitions are given by {A, C},{A, D},{B, C}, and {B, D}, see Section 2 for the definitions. 2Using the notation from Section 3, h{A, C},{B, D}k{A, B},{C, D}i is a trading transform, which certifies non-weightedness. 1 One of the most fundamental questions in all of the above mentioned areas is to characterize which monotonic switching functions (simple games) are weighted threshold functions (weighted games). In threshold logic this is known as the linear separability problem. This question has also been posed in other research fields by using different terminologies, which are essentially equivalent. Three different treatments to solve this problem have been considered. The first consists in studying the consistency of a system of inequalities. Each inequality is formed by the inner product of two vectors: a non-negative integer vector of weights which represents the unknown variables and the vector formed by the subtraction of a true vector (winning coalition) minus a false vector (losing coalition). The system is formed by considering all possible subtractions of true and false vectors. If the switching function is a threshold function then each inequality must be positive and the system of inequalities is consistent. A theorem on the existence of solutions for systems of linear inequalities was given in [7]. Linear programming is also a useful tool as shown in [41, 16]. The second treatment, very close to the previous one, is a geometric approach based on the existence of a separating hyperplane that separates true vectors from false vectors. This procedure is elegant but not very efficient in practice. A use of the geometrical approach can be found in [12]. Reference [32] proposes a variant of it. The idea behind the third approach lies in the consideration of exchanges among vectors and the possibility to convert some true vectors into false vectors, no matter the number of vectors involved in these exchanges. The early works of [13] and [8], reexamined for simple games in [61], are the central point of this work. The class of threshold functions admits a structural characterization, the asummability property, that is both natural and elegant. Some of the deepest results on this subject were obtained in the area of threshold logic during two decades from the fifties to the seventies by Chow, Elgot, Gabelman and Winder, as reported by Hu [33], and continued by Muroga [44] and Muroga et al. [46, 45, 47]. The interpretation of Taylor and Zwicker for the asummability condition in terms of trades among coalitions in [61] together with the work in [62] stimulated the interest for the problem of characterizing weighted games within simple games. In their book [63] they adapted, for simple games, the most important results of threshold logic in relation to the linear separability problem. In particular, their property of trade-robustness is equivalent to the property of asummability. However, trade-robustness is more transparent in the theoretical context of voting since it gives rise to some intuitions concerning the idea of trading players among coalitions. Freixas and Molinero [17] propose a relaxation of trade-robustness for complete simple games and called it invariant-trade robustness, which is less costly in terms of the lenght of the corresponding certificates. In this paper we deduce some new results using this property. As mentioned before, each simple can can be represented as an intersection of weighted games, which allows a compact representation once the number of required weighted games is small. In general this number, called dimension of the simple game, can be large, see e.g. [39], where the worst case asymptotics has been determined via a connection to coding theory. If the dimension is small, e.g. power indices can in general be more simply and efficiently computed. Here we treat the extreme case of dimension 1, i.e., we consider the relavant issue whether a given simple game (switching function) is weighted and propose some new characterizations. The organization of the paper is as follows. The necessary basic terminology of simple games is reviewed in Section 2. Section 3 recalls the main general results on the characterization of weighted games within the class of simple games, and it identifies the analogue terminologies used in threshold logic and simple games. The problem of the characterization of weighted games can be restricted to the class of complete games, a parametrization result for classifying them, up to isomorphisms, which will be intensively used in the next sections, is recalled in Section 4. Sections 5, 6 and 7 provide new results on the characterization of weighted games. Cases for which 2-invariant trade robustness is conclusive are presented in Section 5. m-invariant trade robustness is studied in Section 6, while Section 7 gives some numerical and experimental data. Several questions and conjectures are proposed for future research in Section 8. In Section 9 we draw a conclusion. 2 Terminology in the context of voting simple games Simple games or binary voting systems can be viewed as models of voting systems in which a single alternative, such as a bill or an amendment, is pitted against the status quo. A simple game Gis a pair (N, W) in which N={1,2, . . . , n}is the set of players or voters and Wis a collection of subsets of Nthat satisfies: (1) N∈ W,(2) ∅/∈ W and (3) the monotonicity property: S∈ W and S⊆T⊆Nimplies T∈ W. 2 Any set of voters is called a coalition, and the set Nis called the grand coalition. Members of Nare called players or voters, and the subsets of Nthat are in Ware called winning coalitions. The intuition here is that a set Sis a winning coalition if and only if the bill or amendment passes when the players in Sare precisely the ones who voted for it. A subset of Nthat is not in Wis called a losing coalition. Aminimal winning coalition is a winning coalition all of whose proper subsets are losing. A maximal losing coalition is a losing coalition all of whose proper supersets are winning. Because of monotonicity, any simple game is completely determined by its set of minimal winning coalitions, which is denoted by Wmor by its set of maximal losing coalitions, which is denoted here LM. A voter a∈Nis null if adoes not belong to any minimal winning coalition. A player a∈Nhas veto if abelongs to all winning coalitions. Before proceeding, we present two real-world examples of simple games (see Taylor and Pacelli [60] for a thorough presentation of these two examples). Example 2.1 The United Nations Security Council. The voters in this system are the fifteen countries that make up the Security Council, five of which are permanent members whereas the other ten are non-permanent members. Passage requires a total of at least nine of the fifteen possible votes, subject to a veto due to a no vote from any one of the five permanent members. This model ignores abstention. For a treatment of this example considering the possibility of abstention we refer the reader to [23]. Example 2.2 The System to amend the Canadian Constitution. Since 1982, an amendment to the Canadian Constitution can become law only if it is approved by at least seven out of the ten Canadian provinces, subject to the proviso that the approving provinces have, among them, at least half of Canada’s population. It was first studied in Kilgour [37]. An old census (in percentages) for the Canadian provinces was: 1. Ontario (34%), 2. Quebec (29%), 3. British Columbia (9%), 4. Alberta (7%), 5. Saskatchewan (5%), 6. Manitoba (5%), 7. Nova Scotia (4%), 8. New Brunswick (3%), 9. Newfoundland (3%), 10. Prince Edward Island (1%). For example observe that coalitions (from now on we use abridgments to denote the provinces): X1={Que, BC, Alb, Sas, Man, NS, NB}and X2={Ont, Sas, Man, NS, NB, Newf, PEI}are minimal winning coalitions because they both have exactly 7provinces and their total population surpasses the 50%. Instead, coalitions: Y1={Ont, Que, Sas, Man, NS, NB}and Y2={BC, Alb, Sas, Man, NS, NB, Newf, PEI}are both losing because Y1does not have 7or more members and Y2does not reach the 50% of the total Canada’s population. A fundamental subclass of simple games are the classes of weighted simple games and complete simple games. A simple game G= (N, W) is said to be weighted if there exists a “weight function” w:N→R≥0and a “quota” q∈R>0such that a coalition Sis winning precisely when the sum of the weights of the players in Smeets or exceeds the quota. Any specific example of such a weight function w:N→Rand quota qare said to realize Gas a weighted game. A particular realization of a weighted simple game is denoted as [q;w1, . . . , wn]. For instance, [k; n z }| { 1,...,1] for some k= 1, . . . , n is a feasible realization for a weighted game in which all players are symmetric; here the game is called a k–out–of–nsimple game. A realization of Example 2.1 is [39; 7,7,7,7,7,1,1,1,1,1,1,1,1,1,1], where 7 is the weight for a permanent member and 1 the weight for a nonpermanent member. Instead, Example 2.2 cannot be represented as a weighted game. Indeed, if the game was weighted we would have w(X1)> w(Y1) and w(X2)> w(Y2), i.e., w2+ (w3+· · · +w8)>(w1+w2)+(w5+· · · +w8) and w1+ (w5+· · · +w10)>(w3+· · · +w10). After simplification we obtain w3+w4> w1and w1> w3+w4, which is a contradiction. In these inequalities, w1 represents, the weight for Ontario, the most populated province; w2represents, the weight for Quebec, the second most populated province; and so on. It is quite intuitive to observe that a permanent member has more influence than a non-permanent member in the voting systems described in Example 2.1. The same occurs in Example 2.2 where any of the two big provinces are more influential than any other of the remaining eight provinces. The “desirability relation” represents a way to make the idea, that a particular voting system may give to one voter more influence than another, more precise. Isbell already used it in [35]. Let G= (N, W) be a simple game, aand bbe two voters. Player ais said to be at least as desirable as bas coalitional partner if for every coalition Ssuch that a /∈Sand b /∈S,S∪{b}∈Wimplies S∪{a}∈W. If moreover, there exists a coalition Tsuch that a /∈Tand b /∈T,T∪ {a}∈Wand T∪ {b}/∈ W, then ais (strictly) more 3 desirable than b. Finally, aand bare said to be equally desirable if ais at least as desirable as band the converse is also true. The notations a%b,aband a∼brespectively stand for: ais at least as desirable as b,ais strictly more desirable than b, and aand bare equally desirable. It is straightforward to check that ∼is an equivalence relation, and that the desirability relation %is a partial ordering of the resulting equivalence classes. A simple game G= (N, W) is complete (or linear) if the desirability relation is a complete preordering. Note that every weighted game is complete, since for any realization it holds that wa≥wbimplies a%b. But the converse is not true as Example 2.2 shows. In a complete simple game we may decompose Ninto a collection of subsets, called classes, N1> N2>· · · > Nt forming a partition of N. Those classe should be the equivalence classes ordered by desirability, i.e., if a∈Np and b∈Nqthen: p=qif and only if a∼band, p<qif and only if ab. Two parameters are of fundamental importance in our study. One of them is the number of equivalence classes, t, in a complete game, i.e., a measurement of heterogeneity. In Example 2.1 we have N1> N2where N1is formed by the five permanent members and N2for the non-permanent ones, while in Example 2.2 we have N1> N2, where N1is formed by the two big provinces and N2for the other eight provinces. Thus, in both examples t= 2. To define the second fundamental parameter for our study we need another definition. Given a simple game, ashift-minimal winning coalition Sis a minimal winning coalition such that (S\ {a})∪ {b}is losing whenever abwith a∈Sand b /∈S. Note that a coalition of seven members in Example 2.2 containing both, Quebec and Ontario, is a minimal winning coalition but it is not shift-minimal winning, since a replacement of a big province in the coalition for a province not belonging to the coalition still leaves the new coalition winning. Analogously, a shift-maximal losing coalition Sis a maximal losing coalition such that (S\ {b})∪ {a}is winning whenever ab with b∈Sand a /∈S. Two shift-minimal winning coalitions, Sand T, are said to be equivalent coalitions if Tcan be obtained from S by any sequence of one–to–one exchanges of equally desirable voters. If the game is complete we can consider the parameter rwhich is the maximal number of non-equivalent shift-minimal winning coalitions. Observe that the complete game from Example 2.1 has 10 4= 210 minimal winning coalitions which are also shift-minimal winning coalitions, each consisting of all five permanent members and four arbitrary non-permanent members. However, all of them are equivalent in the previous sense. Thus, for Example 2.1 the two parameters we lay stress on are r= 1 and t= 2. The simple game from Example 2.2 has 112 minimal winning coalitions, 56 of them formed by one of the two big provinces and six other provinces, which are also shift-minimal winning coalitions. The game has 56 additional winning coalitions formed by the two big provinces and five other provinces, but these are not shift-minimal winning coalitions. The 56 shift-minimal winning coalitions are equivalent among them in the previous sense. Thus, for Example 2.2 the two parameters we lay stress on again are r= 1 and t= 2. The case r= 1 is considered in Subsection 5.1. 3 Some results on the characterization of weighted games We introduce a notion of trades among coalitions, which is natural in game theory and in economic applications, see [63] for motivating examples. Suppose G= (N, W) is a simple game. Then a trading transform is a coalition sequence hX1, . . . , Xk|Y1, . . . , Ykiof even length satisfying the following condition: |{i:a∈Xi}| =|{i:a∈Yi}| for all a∈N. The Xs are called the pre-trade coalitions and the Ys are called the post-trade coalitions. A k-trade for a simple game Gis a trading transform hX1, . . . , Xj|Y1, . . . , Yjiwith j≤k. The simple game Gis k-trade robust if there is no trading transform for which all the Xs are winning in Gand all the Ys are losing in G. If Gis k-trade robust for all k∈N, then Gis said to be trade robust. Loosely speaking, Gis k-trade robust if a sequence of kor fewer (not necessarily distinct) winning coalitions can never be rendered losing by a trade. Theorem 3.1 (Theorem 2.4.2 in [63], see also [61]) Let G= (N, W)be a simple game. Then, Gis weighted if and only if Gis trade robust. 4 This result is equivalent to the one given by Elgot [13] and Chow [8] in threshold logic. Instead the notation of trade robustness, these authors used an equivalent condition of asummability of vectors. If we are restricted to complete simple games and only allow pre-trades of shift-minimal winning coalitions, then we may refer to the property of invariant-trade robustness instead of trade robustness and Theorem 3.1 can be reformulated in an equivalent way. Theorem 3.2 (Theorem 4.7 in [17]) Let G= (N, W)be a complete simple game. Then, Gis weighted if and only if Gis invariant-trade robust. As seen in Example 2.2 the trading transform hX1, X2|Y1, Y2icertifies a failure of 2-invariant-trade robustness and therefore this complete simple game is not weighted. It is also trivial to see that the simple game described in Example 2.1 is invariant-trade robust and therefore weighted. Suppose G= (N, W) is a simple game. Then, Gis said to be swap robust if a one–for–one exchange between two winning coalitions can never render both losing. Thus, swap robustness differs from trade robustness in two ways: the trades involve only two coalitions, and the exchanges are one–for–one. That is to say, swap robustness considers m-trades of the following type: m= 2 and hX1, X2|X1\ {a}, X2∪ {a}i with a∈X1and a /∈X2. It is fairly easy to generate simple games that are not swap robust. The following theorem is a characterization of complete simple games. Theorem 3.3 (Proposition 3.2.6 in [63]) Gis a complete simple game if and only if Gis swap robust. Clearly, non–complete games are not 2-invariant trade robust. In fact, it is always possible to find two shiftminimal winning coalitions which convert into losing coalitions after a one–for–one exchange. Thus, the difficulty of the problem of determining when a given simple game is weighted can be focused exclusively on the class of complete games. To obtain significant results it is helpful to have a compact and manageable presentation of these games. If, in a complete game, the number of the equivalence classes is lower than the number of players, i.e., t < |N|, we have such a presentation. Indeed, Carreras and Freixas [6] provide a classification theorem for complete simple games, here Theorem 4.2, that allows to enumerate all these games up to isomorphism by listing the possible values of certain invariants. An advantage of using the classification theorem is that it usually allows to work with a smaller number of vectors than would be required with minimal winning coalitions. In the next section we introduce a notion of trade-robustness based on these invariants. As the basic game theoretic notions for simple games, we use in this paper, have already been introduced, we list a list of language analogies between these notions to the fields of threshold logic or Boolean algebra in next subsection. These analogies allow the easy translation of the results from one field to the other. In particular, this list will be useful for scholars in threshold logic to be aware of the new results we find in this paper and the questions and conjectures we propose to be studied. 3.1 A list of analogies in the context of threshold logic For the sake of simplicity, clarity, and for being coherent with the historical studies we write the notions in the language of Boolean algebra (very similar to that of neural networks or threshold logic). Tables 1 and 2 contain the main equivalences. The list is not exhaustive. Throughout the rest of the paper we exclusively deal with simple games and refer to these two tables for direct analogies of the results we find and the questions and conjectures we pose. 4 Symmetries and a parametrization of complete simple games For t < |N|types of voters we can represent coalitions in a more compact way. Let (N, W) be a simple game and N1, . . . , Ntbe a partition of the player set into tequivalence classes of voters cf. Section 2. A coalition type (or coalition vector) is a vector s= (s1, . . . , st)∈(N∪ {0})twith 0 ≤si≤ |Ni|for all 1 ≤i≤t. We say that a coalition S⊆Nhas type sif si=|S∩Ni|for all 1 ≤i≤t. A coalition type sis called winning if the coalitions of that type are winning. Analogously, the notions of minimal winning, shift-minimal winning, losing, maximal losing and shift-maximal losing are translated similarly for coalitional types. So, the simple game from Example 2.1 can be described by the unique minimal winning coalition type (5,4) which represents all coalitions with 5 permanent 5 Table 1: Variables and vectors versus players and coalitions. variable or node player or voter irrelevant variable null player essential variable vetoer vector coalition true vector winning coalition false vector losing coalition minimal true vector minimal winning coalition maximal false vector maximal losing coalition shift-minimal true vector shift-minimal winning coalition Table 2: Types of functions versus types of simple games. switching function non-monotonic (simple) game monotonic switching function (monotonic) simple game threshold function weighted game k-out-of-n switching function k-out-of-n simple game regular function complete game k-summable not k-trade robust k-asummable k-trade robust k-invariant summable not k-invariant trade robust k-invariant asummable k-invariant trade robust members and 4 non-permanent members, and the simple game from Example 2.2 can be described by the unique minimal winning coalition type (1,6) which represents all coalitions with 1 big province and 6 small provinces. The notion of a trading transform for coalitions can be transferred to coalitional types for vectors. 4.1 Coalitional types Let G= (N, W) be a simple game and N1, . . . , Ntbe a partition into tequivalence classes of players. A vectorial trading transform for Gis a sequence hx1, . . . , xj;y1, . . . , yjiof coalition types of even length such that j X i=1 xi,k = j X i=1 yi,k for all 1 ≤k≤t. (1) The definition of a vectorial trading transform means that for each component 1 ≤k≤t, the sum of the kth xs components coincides with the sum of the kth ys components. Avectorial m-trade is a vectorial trading transform with j≤msuch that the xis are winning and after trades, as described in 1, convert into yis. A given m-trade can easily be converted into a vectorial m-trade. The following lemma shows that the converse is also true, i.e., each given vectorial m-trade can be converted into an m-trade. Lemma 4.1 For each pair of vectors a= (a1, . . . , ar)∈Nr >0,b= (b1, . . . , bs)∈Ns >0with Pr i=1 ai=Ps i=1 biand m= max (maxiai,maxibi)there exist two sequences of sets A1, . . . , Ar⊆ {1, . . . , m}and B1, . . . , Bs⊆ {1, . . . , m} with |Ai|=ai,|Bi|=biand |{i:j∈Ai}| =|{i:j∈Bi}| for all j∈ {1, . . . , m}. Proof: W.l.o.g. we assume a1≥ · · · ≥ arand b1≥ · · · ≥ bs. We prove the statement by induction on σ=Pr i=1 ai. For σ= 1 we have r=s=a1=b1=m= 1 and can choose A1=B1={1}. We remark that the statement is also true for σ= 0, i.e., where r=s= 0. 6 If there exist indices i, j with ai=bj, then we can choose Ai={1, . . . , ai},Bj={1, . . . , bj=ai}and apply the induction hypothesis on (a1, . . . , ai−1, ai+1, . . . , ar) and (b1, . . . , bj−1, bj+1, . . . , bs). In the remaining cases we assume w.l.o.g. a1=mand b1< m. Now let lbe the maximal index with al=m. Since Pr i=1 ai=Ps i=1 biwe have s≥l. So, we can consider the reduction to (a1−1, . . . , al−1, al+1, . . . , ar) and (b1−1, . . . , bl−1, bl+1, . . . , bs), where we possibly have to remove some zero entries and the maximum entry decreases to m−1. Let A0 1, . . . , A0 r, B0 1, . . . , B0 s⊆ {1, . . . , m −1}be suitable coalitions (allowing A0 i=∅or B0 i=∅ for the ease of notation). Adding player mto the first lcoalitions in both cases yields the desired sequences of coalitions.  The construction in Lemma 4.1 for each equivalence class of voters separately converts a vectorial m-trade into an m-trade. Also for vectorial m-trades we may assume that the winning coalition types are minimal winning or that the losing coalition types are maximal losing. Since the number of coalition types is at most as large as the number of coalitions we can computationally benefit from considering vectorial m-trades if the number of types of voters is less than the number of voters. 4.2 A parametrization of complete simple games In a complete simple game G= (N, W) we have a strict ordering between two voters of different equivalence classes. This ordering entails a hierarchy among voters. Some studies on allowable hierarchies can be found in [2, 20, 24]. As before, we denote by N1>· · · > Ntthe equivalence classes which form the unique partition of Nwhere ab for all a∈Niand b∈Njwith i<j. Let n= (n1, . . . , nt) where ni=|Ni|for all i= 1, . . . , t. Consider Λ(n) = {s∈(N∪ {0})t:n≥s}, where ≥stands for the ordinary componentwise ordering, that is, a≥bif and only if ak≥bkfor every k= 1, ..., t. and also consider the weaker ordering given by comparison of partial sums, that is, abif and only if k X i=1 ai≥ k X i=1 bifor k= 1, .., t. If abwe say that adominates b. The couple (Λ(n),) is a distributive lattice and possesses a maximum (respectively, minimum) element, namely n= (n1, ..., nt) (resp. 0 = (0, ..., 0)). As abbreviations we use abfor the cases where abbut a6=band a ./ b for the cases where neither abnor ba. The interpretation of abis as follows. If bis a winning coalitional vector and ab, then also ais winning. Similarly, if ais losing then bis losing too for all ab. A winning coalitional vector asuch that bis losing for all abis called shift-minimal winning. Similarly, a losing coalition type bsuch that ais winning for all abare called shift-maximal losing. Each complete simple game can be uniquely described by either its set of shift-minimal winning coalition types or its set of shift-maximal losing coalition types. Based on this insight, Carreras and Freixas ([6] pp. 148-150) provided a classification theorem for complete simple games that allow to enumerate all these games up to isomorphism by listing the possible values of certain invariants. Indeed, to each complete simple game (N, W) one can associate the vector n∈Ntas defined above and the list of shift-minimal winning coalitional vectors: mp= (mp,1, mp,2, . . . , mp,t) for 1 ≤p≤r. Recall that two simple games (N, W) and (N0,W0) are said to be isomorphic if there exists a bijective map f:N→N0such that S∈ W if only if f(S)∈ W0. Theorem 4.2 (Theorem 4.1 in [6]) (a) Given a vector n∈Ntand a matrix Mwhose rows mp= (mp,1, mp,2, . . . , mp,t) for 1≤p≤rsatisfy the following properties: (i) 0≤mp≤nfor 1≤p≤r; (ii) mpand mqare not –comparable if p6=q; i.e., mp./ mq (iii) if t= 1, then m1,1>0; if t > 1, then for every k < t there exists some psuch that mp,k >0, mp,k+1 < nk+1; 7 and (iv) Mis lexicographically ordered by partial sums, if p<qeither mp,1> mq,1or there exists some k≥1such that mp,k > mq,k and mp,i =mq,i for h < k. Then, there exists a complete simple game (N, W)associated to (n, M). (Theorem 4.2 in [6]) (b) Two complete games (N, W)and (N0,W0)are isomorphic if and only if n=n0and M=M0. The pair (n, M) is referred as the characteristic invariants of game (N, W). The authors prove that these parameters determine the game in the sense that one is able to define a unique up to isomorphism complete simple game which possesses these invariants. The characteristic invariants allow us to count and generate all these games for small values of n. Other applications of the characteristic invariants are to considerably reduce the calculus of some solutions, as values or power indices, of the game (see e.g., [21] for the nucleolus [56]) or to study whether a game admits a representation as a weighted game by studying the consistency of a system of inequalities as we will see below. If matrix Mhas only one row, i.e. a unique shift-minimal coalitional vector, then the characteristic invariants reduce to the couple (n, m) with 1≤m1≤n1 1≤mk≤nk−1 if 2 ≤k≤t−1, 0≤mt≤nt−1, where the first subindex in matrix Mis omitted. It is said, see [21], that (n, m) is a complete game with minimum. We sketch here how to obtain the characteristic invariants (n, M) for the complete game from winning coalitions and reciprocally. Given a simple game (N, W), for each coalition Swe consider the vector or coalitional type s= (|S∩N1|, ..., |S∩Nt|), in Λ(n) where Niare the equivalence classes with N1> ... > Nt.The vector nis (|N1|, ..., |Nt|).The rows of matrix Mare those ssuch that any Sis a shift-minimal winning coalition in the lattice (Λ(n),).Observe that each vector of indices that –dominates a row of Mcorresponds to winning coalitions. Conversely, given (n, M) the game (N, W) can be reconstructed, up to isomorphism, as follows. The cardinality of Nis n=Pt i=1 ni, the elements of Nare denoted by {1,2, . . . , n}.The equivalent classes of (N, W) are N1= {1, . . . , n1}, N2={n1+ 1, . . . , n1+n2},and so on. Each S⊆Nwith vector s= (|S∩N1|, ..., |S∩Nt|) is a winning coalition if smfor some mbeing a row of M. Hence, the set of winning coalitions is W={S⊆N:smp,where mpis a row of M}. Notice that a winning vector is a vector rsuch that the coalition representative Ris winning. In particular, the shift-minimal winning coalitions are those with a vector being a row of M. Precisely, Ws={S⊆N:s=mpfor some p= 1,...r}. Analogously, one can define the coalitional types of shift–maximal losing coalitions which can be written as rows in a matrix Ylexicographically ordered, as requested also for M, to preserve uniqueness. These coalitional types are the maximal vectors which are not -comparable among them and do not dominate by any row of M. Some particular forms of the pair (n, M) reveal the presence of players being either vetoers or nulls. For instance, if mp,t = 0 for all p= 1, . . . , r the game has ntnull players. If mp,1=n1for all p= 1, . . . , r the game has n1 vetoers. Using the well known fact that any weighted game admits normalized representations, where i∼jif and only if wi=wj, we will consider from now on, w= (w1, ..., wt),the vector of weights to be assigned to the members of each of the tequivalence classes. Using normalized representations a weighted game may be expressed as [q;w1(n1), . . . , wt(nt)] in which repetition of weights is indicated within parentheses and qstands for the quota or threshold. However, these parentheses will be omitted provided that n= (n1, . . . , nt) is a known vector. A complete 8 simple game, (N, W), is weighted if and only if there is a vector w= (w1, ..., wt),such that w1> ... > wt≥0, which satisfies the system of inequalities (mp−αq)·w > 0 for all p= 1,2, ..., r, q = 1, . . . , s where ris the number of rows of M,sthe number of rows of Y, and αqare the rows of Y. Only for n≥6 there are complete simple games which are not weighted. The following example is the smallest possible illustration of a complete simple game with minimum, i.e., with one shift-minimal winning vector, that is not a weighted game. It helps us to understand better this kind of games, which are extensively used in the next section. Example 4.3 a. (Example 2.1 revisited) The characteristic invariants for this example are: n= (5,10) and M= (5 4). Thus, W={(5, x)∈Λ(5,10) : x≥4} Wm=Ws={(5,4)} Note also that Y=5 3 4 10 whose rows are the shift-maximal coalitional types. As shown, this game is weighted. In the next section we will show that to prove this it suffices to verify k-invariant trade robustness, where kis 2. b. (Example 2.2 revisited) The characteristic invariants for this example are: n= (2,8) and M= (1 6). Thus, W={(x, y)∈Λ(2,8) : x≥1and x+y≥7} Wm={(2,5),(1,6)} Ws={(1,6)} Note also that Y=2 4 0 8 whose rows are the shift-maximal coalitional types. Note that Example 2.2 is not 2-invariant trade robust since the coalitional type trading transform: <(1,6),(1,6)|(2,4),(0,8) >is a certificate for it. Hence, the game is not weighted. 4.3 Two parameters for complete simple games Two parameters for a complete simple game are significant for our studies: rthe number of rows of Mor number of shift-minimal coalitional vectors and tthe number of equivalence classes of players in the game. The conditions that Mmust fulfill are described in Theorem 4.2. The question we pose here is the following: Are there some values for rand tfor which 2-invariant trade robustness is conclusive? The purpose of Section 5 is to prove that the posed question has an affirmative answer for either r= 1 (no matter the value of t) or t= 2 (no matter the value of r), while in Section 6 we investigate the remaining cases. Let us remark that the number of complete and weighted games as a function of |N|up to isomorphisms has been determined for these two parameters. We use below the notations cg(n, ?, r), cg(n, t, ?), wg(n, ?, r), and wg(n, t, ?) depending on whether we consider complete or weighted games or parameter ror parameter t. The first (trivial) exact counting establishes the number of k–out–of–nsimple games. Each of such games admits [k; 1,1,...,1 | {z } n ] as a weighted representation where k∈ {1, . . . , n}. As t= 1 implies r= 1 we have cg(n, 1, ?) = wg(n, 1, ?) = n. For r= 1, we have cg(n, ?, 1) = 2n−1 (see [22]) complete simple games with minimum with nplayers up to isomorphism and the number of weighted games with minimum, wg(n, ?, 1), is given by wg(n, ?, 1) =    2n−1,if n≤5 n4−6n3+ 23n2−18n+ 12 12 ,if n≥6 cf. [15]. For t= 2 we have the nice formula cg(n, 2, ?) = F(n+ 6) −(n2+ 4n+ 8) (cf. [19]) where F(n) are the Fibonacci numbers which constitute a well–known sequence of integer numbers defined by the following recurrence relation: 9 Since a3, b4≥1 and b5∈Z≥0, we have b5≥2. k=a1+a2+a3+a4≤mplus mtimes Inequality (13) plus Inequality (15) minus 2m+ 1 times Inequality (12) yields 2a2−(m+ 1)a4≤ −2b2−4b3−(m+ 3)b4−(m+ 1)b5+m. (21) Since b5≥2 and a4∈Z≥0, we have a4≥2. From Inequality (20) and a2, b2, b3≥0 we conclude b5≥a3 2+a4, so that b5≥a4+1 due to a3≥1 and b5∈Z≥0. From Inequality (21) and a2, b2, b3, b4≥0 we conclude (m+ 1)a4≥(m+ 1)b5−m. Inserting b5≥a4+ 1 finally yields the contradiction (m+ 1)a4≥(m+ 1)a4+ 1.  We remark that the proof of Lemma 6.2 looks rather technical and complicated at first sight. However, the underlying idea is very simple. We have to show that the parametric ILP given by inequalities (12)-(15) and 9 nonnegative integer variables a1, . . . , a4, b1, . . . , b5has a minimum value of m+1 for the target function a1+a2+a3+a4. By relaxing the integrality conditions we obtain a corresponding linear program. Minimizing a suitable variable yields a fractional lower bound that can be rounded up. The corresponding dual multipliers are used to conclude the respective lower bounds directly. Conjecture 6.3 For each r≥5, i.e. at least 5coalitional types of shift-minimal winning coalitions, there exists a sequence (Gr m)m≥3of complete simple games, such that Gr mis m-invariant trade robust but not (m+ 1)-invariant trade robust. Lemma 6.4 Let G= (n, M)be a complete simple game with ttypes of voters and rshift-minimal winning coalition types, being m-invariant trade robust, but not (m+ 1)-invariant trade robust for some m > 1. Then, there exists a complete simple game G0with t+1 types of voters and rshift-minimal winning coalition types, which is m-invariant trade robust, but not (m+ 1)-invariant trade robust. Proof: Let em1,..., emrdenote the rows of M. If Gcontains nulls, i.e., if emi t= 0 for all 1 ≤i≤r, we set bmi j=emi j, bmi t= 1, bmi t+1 = 0, bnj=nj,bnt= 2, and bnt+1 =ntfor all 1 ≤j≤t−1, 1 ≤i≤r. Otherwise we set bmi j=emi j, bmi t= 1, bnj=nj, and bnt+1 = 2 for all 1 ≤j≤t, 1 ≤i≤r. With this, we choose G0= (bn, M0), where M0is composed of the rrows bm1,..., bmr. We can easily check that G0is indeed weighted. Let l= (l1, . . . , lt+1) be a losing coalitional vector in G0. If Gcontains no nulls, then (l1, . . . , lt) is a losing vector in G. Otherwise, (l1, . . . , lt−1, lt+1) is a losing coalitional vector in G. Thus, a possible certificate for the failure of m-invariant trade robustness for G0could be converted into a certificate for the failure of m-invariant trade robustness for Gby deleting the (t−1)th or tth column of the corresponding vectors – a contradiction. Similarly, we can convert a certificate for the failure of (m+ 1)-invariant trade robustness for Ginto a certificate for the failure of (m+ 1)-invariant trade robustness for G0by inserting ones into the (t−1)th or tth column of the corresponding vectors.  The same proof is literally valid in the case of trade robustness: Lemma 6.5 Let G= (n, M)be a complete simple game with ttypes of voters and rshift-minimal winning coalition types, being m-trade robust, but not (m+ 1)-trade robust for some m > 1. Then, there exists a complete simple game G0with t+ 1 types of voters and rshift-minimal winning coalition types, which is m-trade robust, but not (m+ 1)-trade robust. With these results at hand we may prove that larger classes of games according to parameters rand tnever reduce the largest failures of invariant-trade robustness. Table 3 summarizes the invariant trade robust test to be used for a game to determine whether this is weighted. Looking at this table we conclude that 2-invariant trade robustness is conclusive exactly for the cases determined in Section 5 (conjectured values are printed in bold face), while for others there is no combination of rand tfor which some m > 2 be enough to ensure that the game is weighted. In words, if one wishes to study the class of complete games with a given pair (r, t) then 2-invariant trade robustness is a very powerful tool to check weightedness for t≤2 and r= 1, but for the rest of combinations (r, t) we need to look at trade-robustness, which is the purpose of the next section. 16 Table 3: W: weighted; −: not possible; 2-I-T-R: either weighted or not 2-invariant trade robust; ∞-I-T-R: there are games that are not m-invariant trade robust for all m; NW: not a weighted game; conjectured values in bold face. r↓ | t→1 2 3 4 . . . 1 W 2-I-T-R 2-I-T-R 2-I-T-R NW 2 - 2-I-T-R ∞-I-T-R ∞-I-T-R ∞-I-T-R 3 - 2-I-T-R ∞-I-T-R ∞-I-T-R ∞-I-T-R 4 - 2-I-T-R ∞-I-T-R ∞-I-T-R ∞-I-T-R . . . - 2-I-T-R ∞-I-T-R ∞-I-T-R ∞-I-T-R 7 Further trade characterizations It is well known that all simple games with up to 3 voters are weighted while there are non-weighted simple games for n≥4 voters. Restricting the class of simple games to swap robust simple games, i.e. complete simple games, one can state that up to 5 voters each such game is weighted while for n≥6 voters there are non-weighted complete simple games. Going over to 2-invariant trade robustness does not help too much. As shown in [17], precisely 3 of the 60 non-weighted complete simple games with n= 6 voters are 2-invariant trade robust but not 3-invariant trade robust. For the classical trade robustness the same authors have shown that all 2-trade robust complete simple games with up to seven voters are weighted. By an exhaustive enumeration we have shown that the same statement is true for n= 8 voters, i.e., there are exactly 2 730 164 weighted games and the remaining 13 445 024 complete simple games are not 2-trade robust. As shown in [27], there are complete simple games with n= 9 voters, which are 3-trade robust but not 4-trade robust. The corresponding example, belonging to a parametric family, consists of nine different types of players, i.e., no two players are equivalent. If the number tof types of players is restricted we can obtain tighter weighted characterizations. For t= 1 the games are always weighted and for t= 2 weightedness is equivalent with 2-trade robustness (or 2-invariant trade robustness for complete simple games). Based on this characterization one can computationally determine the number of complete simple games with two types of voters which are either weighted, i.e. 2-invariant trade robust, or not weighted, i.e. not 2-invariant trade robust. In [19] this calculation was executed for n≤40 voters. It turns out that the fraction of non 2-invariant trade robust complete simple games quickly tends to 1. An exact, easy-to-evaluate, and exponentially growing formula for the number of complete simple games with two types of voters is proven in [19, 41]. From the upper bound n5/15 + 4n4, see [16], for the number of weighted games with two types of voters, we can conclude that this is generally true. We remark that it is not too hard to compute the number of 2-invariant trade robust complete simple games with t= 2 for n≤200, see [14], so that we abstain from giving a larger table. Table 4: Classification of complete simple games with three types of up to 15 voters. Parameters: size (n), number of complete simple games (#CG), number of weighted simple games (#WG), number of non 2-trade robust complete simple games (#N-2T), number of non 3-trade, but 2-trade, robust complete simple games (#N-3T). n#CG #WG #N-2T #N-3T 3 0 0 0 0 4 6 6 0 0 5 50 50 0 0 6 262 256 6 0 7 1114 976 138 0 8 4278 3112 1166 0 9 15769 8710 7059 0 10 58147 22084 36063 0 11 221089 51665 169420 4 12 886411 113211 773186 14 13 3806475 234649 3571788 38 14 17681979 463872 17218019 88 15 89337562 879989 88457385 188 16 492188528 1610011 490578137 380 17 2959459154 2852050 2956606348 756 For t= 3 types of voters we have checked by an exhaustive enumeration that up to n= 10 voters each complete simple game is either weighted or not 2-trade robust. For n= 11 voters we have the four examples given by 17 n= (3,3,5), M1=223 125,M2=112 014,M3=    330 304 232 035    , and M4=    300 202 031 005    , which are all 2-trade robust but not 3-trade robust. This resolves an open problem from [17]. We have computationally checked all complete simple games with three types of voters, i.e. t= 3, and up to 15 voters, i.e. |N| ≤ 15, see Table 7. It seems that the number of games which are 2-trade robust but not 3-trade robust grows rather slowly. Indeed, up to 15 players every 3-trade robust game is weighted. For t= 4 types and n= 9 voters there are several complete simple games which are 2-trade robust but not 3-trade robust, e.g. the one given by n= (1,2,3,3) and M=       1010 0201 0120 0112 0032      . For t= 4 and n= 10 there are already 120 complete simple games which are 2-trade robust but not 3-trade robust. The next cases to look at, are t= 3 and r= 2. For both cases we have already presented examples which are 2-trade robust but not 3-trade robust. In the next section we state a conjecture and ask for several questions related to the problem in relation with the two parameters rand tof a complete game. 8 Open problems Still we found no example which is 3-trade robust but not 4-trade robust. Question 8.1 Is every 3-trade robust complete simple game with t= 3 types of voters weighted? Question 8.2 Is every 3-trade robust complete simple game with r= 2 shift-minimal winning coalition types weighted? As a first step into the direction of these two questions, we have looked at the intersection of both classes, i.e., complete simple games with t= 3 and r= 2. The game corresponding to the previously presented matrices M1 and M2for n= 11 voters are of this type and can be generalized: Lemma 8.3 For each k1, k2, k3, l ∈Nthe games uniquely characterized by n1= (n1, n2, n3), M1=n1−(l+ 1) n2−1n3−(l+ 2) n1−2(l+ 1) n2−1n3, where n1= 3 + k1+ 2l,n2= 3 + k2,n3= 5 + k3+ 2l, and n2= (n1, n2,5+2l),M2=l+ 1 1 l+ 2 0 1 2(l+ 2)are 2-trade robust but not 3-trade robust. We skip the easy but somewhat technical and lengthy proof. Having the nice parametrization at hand, we can easily state the corresponding generating function, whose coefficients in the resulting power series serve to count the number of those games, where the exponent denotes the number of players: x11 1 (1 −x)3(1 −x4)+1 (1 −x)2(1 −x4)=x11(x−2) (1 −x)3(1 −x4) We deduce that asymptotically there are n3 24 +O(n2) such games.3 Conjecture 8.4 All 3-trade robust complete simple games with t= 3 and r= 2 are weighted. Additionally, the 2-trade robust but not 3-trade robust games are exactly those from Lemma 8.3. By an exhaustive enumeration we have checked Conjecture 8.4 up to n= 20 voters. From the previous results it is not clear whether a small number of types or shift-minimal winning coalition types allows to restrict the check of m-trade robustness to a finite m. 3There is no connection to the efficient computation of power indices. In general, generating functions are just a theoretical tool from enumerative combinatorics in order to compute exact formulas for recurrence relations. 18 Question 8.5 For which values of tdoes a sequence Gkof complete simple games with ttypes of voters exist such that Gkis k-trade robust but not (k+ 1)-trade robust for all k≥2? Question 8.6 For which values of rdoes a sequence Gkof complete simple games with rshift-minimal winning coalition types exist such that Gkis k-trade robust but not (k+ 1)-trade robust for all k≥2? Any progress concerning answers for either the conjecture or the questions posed would be of interest. In Table 5 we combine the results from Section 5 with the questions of this section. For r= 2 or t= 3 we have not found any example being 3-trade robust but not weighted, but this should be checked formally and become conjectures for future work (in Table 5 it appears in black). Table 5: W: weighted; −: not possible; 2-I-T-R: either weighted or not 2-invariant trade robust; 3-T-R for small values of nall games are either weighted or not 3-trade robust – still a conjecture; NW: not a weighted game; ?: it is not known if some m > 2 suffices to assert that m-trade robustness implies weighted. r↓ | t→1 2 3 4 . . . 1 W 2-I-T-R 2-I-T-R 2-I-T-R NW 2 - 2-I-T-R 3-T-R 3-T-R 3-T-R 3 - 2-I-T-R 3-T-R ? ? 4 - 2-I-T-R 3-T-R ? ? . . . - 2-I-T-R 3-T-R ? ? 9 Conclusion This paper looks at the characterization of weighted games (threshold functions) within the class of simple games (switching functions). We have tried to gather results and efforts that have taken place in different areas of study. The new results presented in this paper have been exposed in the simple game terminology since some significant advances have been held in this area in the last two decades. To study the main problem we have restricted ourselves to the class of complete games since non-complete games are not swap-robust and therefore not weighted. For complete games the test of trade robustness can be computationally relaxed to invariant trade robustness. The strongest condition for invariant trade robustness, 2-invariant trade robustness, is conclusive for deciding if a given complete game is weighted if the complete game has either a unique coalitional type of shift-minimal winning coalitions or two types of equivalent voters. Larger values for the number of shift-minimal winning coalitions or for the number of equivalence classes show that the tests of trade robustness and invariant trade robustness are complementary. We have found some conspicuous examples of non-weighted games being k-trade robust (or k0invariant trade robust for some k0≥k) but not k+ 1-trade robust (or not k0+ 1-invariant trade robust). We have incorporated a number of open questions in hopes of others taking up the challenges that we have left over. Acknowledgements This research was partially supported by funds from the Spanish Ministry of Economy and Competitiveness (MINECO) and from the European Union (FEDER funds) under grant MTM2015-66818-P (MINECO/FEDER). References [1] M. Anthony and S. Holden, Quantifying generalization in linearly weighted neural networks, Complex Systems 8 (1994), pp. 91–114. [2] D. Bean and J. Friedman and C. Parker, Simple majority achievable hierarchies, Theory and Decision 65 (2008), pp. 285–302. [3] A. Beimel, T. Tassa, and E. Weinreb, Characterizing ideal weighted threshold secret sharing, SIAM Journal on Discrete Mathematics 22 (2008), pp. 360–397. 19 [4] A. Beimel and E. Weinreb, Monotone circuits for monotone weighted threshold families, Information Processing Letters 97 (2006), pp. 12–18. [5] V. Bohossian and J. Bruck, Algebraic techniques for constructing minimal weights threshold functions, SIAM Journal on Discrete Mathematics 16 (2003), pp. 114–126. [6] F. Carreras and J. Freixas, Complete simple games, Mathematical Social Sciences 32 (1996), pp. 139–155. [7] V. Chv´atal, Linear Programming, W.H. Freeman, New York, USA, 1983. [8] C. Chow, Boolean functions realizable with single threshold devices, in Proceedings of the Institute of Radio Engineers, Vol. 49, 1961, pp. 370–371. [9] R. Dedekind, ¨ Uber Zerlegungen von Zahlen durch ihre gr¨oßten gemeinsammen Teiler, in Gesammelte Werke, Vol. 1. (1897), pp. 103–148. [10] B. de Keijzer, T. Klos, and Y. Zhang, Finding optimal solutions for voting game design problems, Journal of Artificial Intelligence 50 (2014), pp. 105–140. [11] P. Dubey and L. Shapley, Mathematical properties of the Banzhaf power index, Mathematics of Operations Research 4 (1979), pp. 99–131. [12] E. Einy and E. Lehrer, Regular simple games, International Journal of Game Theory 18 (1989), pp. 195–207. [13] C. Elgot, Truth functions realizable by single threshold organs, in AIEE Conference Paper 60-1311 (October), revised November 1960; paper presented at IEEE Symposium on Switching Circuit Theory and Logical Design, September 1961. [14] J. Freixas and S. Kurz, The golden number and Fibonacci sequences in the design of voting systems, European Journal of Operational Research 226 (2013), pp. 246–257. [15] J. Freixas and S. Kurz, Enumerations of weighted games with minimum and an analysis of voting power for bipartite complete games with minimum, Annals of Operations Research 222 (2014), pp. 317–339. [16] J. Freixas and S. Kurz, On minimum integer representations of weighted games, Mathematical Social Sciences 67 (2014), pp. 9–22. [17] J. Freixas and X. Molinero, Simple games and weighted games: a theoretical and computational viewpoint, Discrete Applied Mathematics 157 (2009), pp. 1496–1508. [18] J. Freixas and X. Molinero, Weighted games without a unique minimal representation in integers, Optimization Methods and Software 25 (2010), pp. 203–215. [19] J. Freixas, X. Molinero, and S. Roura, Complete voting systems with two types of voters: weightedness and counting, Annals of Operations Research 193 (2012), pp. 273–289. [20] J. Freixas and M. Pons, Hierarchies achievable in simple games, Theory and Decision 68 (2010), pp. 393–404. [21] J. Freixas and M.A. Puente, Complete games with minimum, Annals of Operations Research 84 (1998), pp. 97–109. [22] J. Freixas and M.A. Puente, Dimension of complete simple games with minimum, European Journal of Operational Research 188 (2008), pp. 555–568. [23] J. Freixas and W. Zwicker, Weighted voting, abstention, and multiple levels of approval, Social Choice and Welfare 21 (2003), pp. 399–431. [24] J. Friedman and L. McGrath and C. Parker, Achievable hierarchies in voting games, Theory and Decision 61 (2006), pp. 305–318. [25] I. Gabelman, The functional behavior of majority (threshold) elements, Ph.D. dissertation, Electrical Engineering Department, Syracuse University, 1961. [26] S. Golomb, On the classification of boolean functions, IRE Trans. Circuit Theory 6 (1959), pp. 176–186. 20 [27] T. Gvozdeva and A. Slinko, Weighted and roughly weighted simple games, Mathematical Social Sciences 61 (2011), pp. 20–30. [28] P. Hammer and R. Holzman, Approximations of pseudoboolean functions; applications to game theory, ZOR Methods and Models of Operations Research 36 (1992), pp. 3–21. [29] P. Hammer, T. Ibaraki, and U. Peled, Threshold numbers and threshold completions, Annals of Discrete Mathematics 11 (1981), pp. 125–145. [30] P. Hammer, A. Kogan, and U. Rothblum, Evaluation, strength and relevance of Boolean functions, SIAM Journal on Discrete Mathematics 13 (2000), pp. 302–312. [31] J. Herranz, Any 2-asummable bipartite function is weighted threshold, Discrete Applied Mathematics 159 (2011), pp. 1079–1084. [32] N. Houy and W. Zwicker, The geometry of voting power: Weighted voting and hyper-ellipsoids, Games and Economic Behavior 84 (2014), pp. 7–16. [33] S. Hu, Threshold Logic, Univ. of California Press, Berkeley and Los Angeles, USA, 1965. [34] J. Isbell, A class of majority games, Quarterly Journal of Mathematics Oxford Ser. 7 (1956), pp. 183–187. [35] J. Isbell, A class of simple games, Duke Mathematics Journal 25 (1958), pp. 423–439. [36] V.M. Kartak, S. Kurz, A.V. Ripatti, and G. Scheithauer, Minimal proper non-IRUP instances of the onedimensional cutting stock problem., Discrete Applied Mathematics 187 (2015), pp. 120-129. [37] D. Kilgour, A formal analysis of the amending formula of Canada’s Constitution Act, Canadian Journal of Political Science 16 (1983), pp. 771–777. [38] S. Kurz, On minimum sum representations for weighted voting games, Annals of Operations Research 196 (2012), pp. 361–369. [39] S. Kurz, X. Molinero, and M. Olsen, On the construction of high-dimensional simple games, in Proceedings of the 22nd European Conference on Artificial Intelligence (2016), pp. 1–13. [40] S. Kurz and S. Napel, Dimension of the Lisbon voting rules in the EU Council: a challenge and new world record, Optimization Letters 10 (2016), pp. 1245–1256. [41] S. Kurz and N. Tautenhahn, On Dedekind’s problem for complete simple games, International Journal of Game Theory 42 (2013), pp. 411–437. [42] N. Littlestone, Learning when irrelevant attributes abound: A new linear-threshold algorithm, Machine Learning 2 (1988), pp. 285–318. [43] K. May, A set of independent, necessary and sufficient conditions for simple majority decision, Econometrica 20 (1952), pp. 680–684. [44] S. Muroga, Threshold logic and its applications, Wiley–Interscience, New York, USA, 1971. [45] S. Muroga, I. Toda, and M. Kondo, Majority decision functions of up to six variables, Math. Computation 16 (1962), pp. 459–472. [46] S. Muroga, I. Toda, and S. Takasu, Theory of majority decision elements, Journal Franklin Institute 271 (1961), pp. 376–418. [47] S. Muroga, T. Tsuboi, and R. Baugh, Enumeration of threshold functions of eight variables, IEEE Transactions on Computers C-19 (1970). [48] J.V. Neumann and O. Morgenstern, Theory of Games and Economic Behavior, Princeton University Press, Princeton, New Jersey, USA, 1944. [49] I. Parberry, Circuit Complexity and Neural Networks, The M.I.T. Press, Cambridge, Massachusetts, London, England, 1994. 21 [50] U. Peled and B. Simeone, Polynomial-time algorithms for regular set-covering and threshold synthesis, Discrete Appl. Math. 12 (1985), pp. 57–69. [51] B. Peleg, On weight of constant sum majority games, SIAM Journal of Applied Mathematics 16 (1968), pp. 527–532. [52] P. Picton, Neural Networks, The Macmillan Press LTD (2nd Edition), London, Great Britain, 2000. [53] K. Ramamurthy, Coherent structures and simple games, Kluwer Academic Publishers, Dordrecht, The Netherlands, 1990. [54] J. Reiterman, V. R¨odl, E. Sinajova, and M. Tuma, Threshold hypergraphs, Discrete Applied Mathematics 54 (1985), pp. 193–200. [55] V. Roychowdhury, K. Siu, and A.O. (Eds.), Theoretical Advances in Neural Computation and Learning, Kluwer Academic Publishers, Stanford, USA, 1994. [56] D. Schmeidler, The nucleolus of a characteristic function game, SIAM J. Appl. Math 17 (1969), pp. 1163–1170. [57] G. Simmons, How to (really) share a secret, in Proceedings of the 8th Annual International Cryptology Conference on Advances in Cryptology, Spinger-Verlag, London, UK, 1990, pp. 390–448. [58] K. Siu, V. Roychowdhury, and T. Kailath, Discrete Neural Computation: A Theoretical Foundation, Prentice Hall, New Jersey, USA, 1995. [59] T. Tassa, Hierarchical threshold secret sharing, Journal of Cryptology 20 (2007), pp. 237–264. [60] A.D. Taylor and A. Pacelli, Mathematics and Politics, second edition, Springer Verlag, New York, USA, 2008. [61] A.D. Taylor and W.S. Zwicker, A characterization of weighted voting, Proceedings of the American Mathematical Society 115 (1992), pp. 1089–1094. [62] A.D. Taylor and W.S. Zwicker, Simple games and magic squares, Journal of Combinatorial Theory, ser. A 71 (1995), pp. 67–88. [63] A.D. Taylor and W.S. Zwicker, Simple games: desirability relations, trading, and pseudoweightings, Princeton University Press, New Jersey, USA, 1999. 22