Multidimension: a dimensionality extension of simple games

Computational and Applied Mathematics (2023) 42:339 https://doi.org/10.1007/s40314-023-02471-y Multidimension: a dimensionality extension of simple games Xavier Molinero1·Fabián Riquelme2·Salvador Roura3·Maria Serna4 Received: 13 March 2023 / Revised: 10 August 2023 / Accepted: 12 September 2023 © The Author(s) 2023 Abstract In voting theory and social choice theory, decision systems can be represented as simple games, i.e., cooperative games defined through their players or voters and their set of winning coalitions. The weighted voting games form a well-known strict subclass of simple games, where each player has a voting weight so that a coalition wins if the sum of weights of their members exceeds a given quota. Since the number of winning coalitions can be exponential in the number of players, simple games can be represented much more compactly as intersections or unions of weighted voting games. A simple game’s dimension (codimension) is the minimum number of weighted voting games such that their intersection (union) is the given game. It is known there are voting systems with a high (co)dimension. This work introduces the multidimension as the minimum size of an expression with intersections and unions on weighted voting games necessary to obtain the considered simple game. We generalize this notion to subclasses of weighted voting games and analyze the generative properties of these subclasses. We also characterize the simple games with finite generalized Communicated by Antonio José Silva Neto. Fabián Riquelme, Salvador Roura, Maria Serna: These authors have contributed equally to this work. BXavier Molinero xavier[email protected] Fabián Riquelme [email protected] Salvador Roura [email protected] Maria Serna [email protected] 1Department of Mathematics (MAT), Universitat Politècnica de Catalunya - BarcelonaTech (UPC), Violinista Vellsolà 37, 08222 Terrassa, Spain 2Department of Computer Science (CS), Universitat Politècnica de Catalunya - BarcelonaTech (UPC), General Cruz 222, 2362905 Valparaíso, Chile 3Department of Computer Science (CS), Universitat Politècnica de Catalunya - BarcelonaTech (UPC), Jordi Girona Salgado 1-3, 08034 Barcelona, Spain 4Department of Computer Science (CS), IMTech, Institute of Mathematics of UPC - Barcelona Tech, Universitat Politècnica de Catalunya - BarcelonaTech (UPC), Jordi Girona Salgado 1-3, 08034 Barcelona, Spain 0123456789().: V,-vol 123 339 Page 2 of 30 X. Molinero et al. multidimension over the set of weighted voting games without dummy players. We provide a comprehensive classification for simple games up to a certain number of players. These results complement similar classification results for generalized (co)dimensions. Our results show how generalized multidimension allows representing more simple games and more compactly, even for a small number of players and for subclasses. Keywords Game theory ·Weighted voting games ·Dimensionality ·Codimensionality · Canonical minimum representation Mathematics Subject Classification 91 ·90 1 Introduction Simple games play a significant role across various disciplines, including mathematics, computer science, and social sciences. They have applications in solving and representing problems related to politics, voting theory, decision theory, social choice theory, threshold logic, circuit complexity, network reliability, linear programming, artificial intelligence, Sperner theory, and order theory, among others (Brams 1975; Taylor and Zwicker 1999; Eiter et al. 2008; Engel 1997; Judson et al. 2005). Additionally, they exhibit close connections with various mathematical and computational structures, such as dual hypergraphs, Sperner families, antichains, monotone Boolean functions, free distributive lattices, monotone collective decision-making systems, and multi-agent systems, to name a few (Taylor and Zwicker 1999; Eiter et al. 2008; Engel 1997). This article is particularly interested in voting system applications. Voting systems or electoral systems are the set of rules that different governments, social organizations, and other sociopolitical groups adopt for collective decision-making. There are numerous and diverse voting systems worldwide, and new voting systems are continually being created, looking for more fair, representative, or adequate systems for each context. A usual way to study voting systems is through simple games, i.e., a type of monotonous cooperative games with either 0 or 1 payoffs (von Neumann and Morgenstern 1944). A simple game is defined by a set of players or voters and a set of winning coalitions. A winning coalition is a subset of players that manages to win a motion (election, referendum, etc.), i.e., a coalition with payoff 1. The set of losing coalitions, i.e., those with payoff 0, is formed by all coalitions that are not winners. Simple games are monotonous in the sense that the superset of any winning coalition is also a winner, while the subset of any losing coalition is also a loser (Taylor and Zwicker 1999). A problem with simple games is that the set of winning (or losing) coalitions of a game can be exponential in the number of players (Molinero et al. 2015). Therefore, explicitly storing all the information needed to describe the game can be costly. Fortunately, it is known that any simple game can be represented as an intersection (Taylor and Zwicker 1993)or union (Freixas and Marciniak 2010) of weighted voting games. Weighted voting games are a subclass of simple games in which each player has a voting weight so that a coalition wins if the sum of its members’ weights manages to exceed a given quota for the game. The representation form for weighted voting games is a vector containing the quota and the player’s weights, so its size is linear in the number of players. Weighted voting games have garnered attention and investigation in multiple contexts, sometimes referred to by different names, including linearly separated truth functions in contact and rectifier nets (McNaughton 123 Multidimension: a dimensionality extension of simple games Page 3 of 30 339 1961), linearly separable switching functions or threshold Boolean functions, for separating circuits in switching circuit theory, and analyzing the threshold synthesis problem (Hu 1965; Freixas and Molinero 2008), trade robustness in voting theory and trade exchanges (Taylor andZwicker1992),orthresholdhypergraphs,forsynchronizingparallelprocesses(Golumbic 1980; Reiterman et al. 1985). Besides, its more succinct vectorial representation constitutes an advantage for computational treatment. The votes of the legislative power in countries with proportional representation party-list, mainlyfromLatinAmerica,Europe,andAfrica,canberepresentedasweightedvotinggames, where each player represents a political party, and the weights their number of parliamentary seats. The quota depends on the country and type of voting (e.g., common law, organic constitutional law, constitutional reform, etc.) (Riquelme and Gonzalez-Cantergiani 2017; Riquelme et al. 2019). However, it is important to remark that there are voting systems that cannot be represented as weighted voting games. For instance, the European Union Council under the Lisbon rules can be represented as the intersection of between 8 (Kober and Weltge 2021) and 25 weighted voting games (Chen et al. 2019) and as the union of at least 2000 weighted voting games (Kurz and Napel 2015). The above leads us to two key concepts: dimension and codimension. The dimension is the minimum number of weighted voting games whose intersections generate the considered simple game. Simple games formed by theintersectionofseveralweightedvotinggamesare calledvectorweightedvotinggamesand were initially defined to represent voting systems in multicameralism (Taylor and Zwicker 1993). Similarly, the codimension is the minimum number of weighted voting games whose unions generate the considered simple game. Hence, the EU Council under the Lisbon rules hasa dimension between8 (Kober and Weltge 2021)and 25 (Chenet al. 2019)and a codimension of at least 2000 (Kurz and Napel 2015). Note that simple games with small dimensions can be described with a reasonable amount of bits, and thus analyzing some of their properties might became computationally tractable. Several studies about dimension and codimension of simple games have appeared during thelasttwodecades (FreixasandMolinero 2010;Taylor andZwicker1999;Taylor andPacelli 2008). Some authors have focused on computing the dimension of simple games theoretically (Olsen et al. 2016; Freixas and Puente 2001,2008), others on finding high dimensions for voting systems in real life (Kurz and Napel 2015), and others on computational complexity results (Molinero et al. 2016; Freixas et al. 2011). It is known that finding exact values for dimension and codimension are NP-hard computational problems (De˘ıneko and Woeginger 2006). Moreover, dimensions in simple games can be exponential in the number of players (Olsen et al. 2016; Taylor and Zwicker 1999). The same occurs for codimensions since dimension and codimension are dual concepts (Kurz et al. 2016). Recently, in Molinero et al. (2023) it was introduced a generalization of dimension and codimension to subclasses of simple games. The main objective of this generalization is to analyze the ability to express simple games as intersections or unions of games from subclasses of weighted voting games, in particular for subclasses of pure games, i.e., games without dummy players. Besides the definitions, Molinero et al. (2023) characterizes the simple games that can be expressed as either intersection or union of pure weighted voting games. The same work also provides a systematic classification of generalized dimension and codimension for all simple games up to six players and all simple games obtained by weighted voting games with linear restrictions until seven players. In this article, we focus on another generalization of dimension that we call multidimension. Our idea is to use a well-formed expression (on unions and intersections) of weighted voting games to describe a simple game. The multidimension of a simple game measures the minimum number of operations in an expression on intersections and unions describing  123 339 Page 4 of 30 X. Molinero et al. (see definitions in Sect.3). Besides analyzing other properties, the multidimension of a simple game remains smaller or equal than the minimum of its dimension and codimension. In this way, we expect to provide a form of representation amenable to computational treatment for a bigger number of games. Our definition of multidimension is related to the minimum size of Boolean weighted voting games introduced in Faliszewski et al. (2009). In fact, as we will see later, the multidimension of a given simple game is the minimum size of a Boolean weighted voting game equivalent to . On the other hand, there are other similar concepts of Boolean dimension related to our multidimension (O’Dwyer and Slinko 2017;Kurz2021). We will comment on them in Sect.3were we introduce their definitions. As for dimension and codimension, we also consider generalized notions of multidimension by restricting the subclasses of weighted voting games allowed in an expression. As we will see, some subclasses of weighted voting games are not enough to represent some simple games through expressions over the union and intersection operations. In those cases, when a game cannot be obtained in such a way, following the notation used in Molinero et al. (2023), we say that its generalized multidimension is ∞. Given a simple game with (generalized) dimension dand (generalized) codimension c,it is clear that its (generalized) multidimension is at most min{c,d}. However, for some simple games, the multidimension could be much smaller. For example, the EU Council under the Lisbon rules can be represented as the union of one weighted voting game with the intersection of two weighted voting games (Kurz and Napel 2015), so it has multidimension (or Boolean dimension O’Dwyer and Slinko 2017) 3. As expected, we show that, for subclasses of weighted voting games closed under duality, the generalized multidimension of a game and that of its dual coincide. Another result is a characterization of the simple games with finite multidimension with respect to the class of pure weighted voting games. We show that all simple games except singleton games, i.e., games having only a singleton as a minimal winning coalition, have finite generalized multidimension on pure weighted voting games. In this way, we show that the expressiveness of expressions on intersections and unions is higher than when using only unions or only intersections. Interestingly enough, we show that expressions over a subclass of weighted voting games can generate all simple games if and only if they can generate all singleton games. In particular, this result allows us to show that the Boolean dimension of a game with nplayers, over the set of all singleton games, according to the definition in O’Dwyer and Slinko (2017), is upper bounded by n. Finally, we provide a systematic classification of generalized multidimension for several subclasses of weighted voting games with up to six players. Our results are compared to those provided for generalized dimension and codimension in Molinero et al. (2023). Our study shows that the generalized multidimension can be smaller than the generalized dimension and codimension, even for simple games with very few players. Surprisingly, the experiments also show that the generalized multidimension presents a discontinuity for some classes. This latter result differs from the generalized dimension and codimension continuity established in Molinero et al. (2023). The paper continues as follows. Section2presents the theoretical framework of this work. Section3introduces the (generalized) multidimension of simple games and gives some properties and examples. The main theoretical results are shown in Sect.4, and the experimental ones are in Sect.5. Section6is devoted to conclusions and future work. 123 Multidimension: a dimensionality extension of simple games Page 5 of 30 339 2 Preliminaries We start introducing basic notions and terminology for simple games. We also present the concepts of generalized dimension and codimension and recall some basic properties. We follow notation from Taylor and Zwicker (1999) and Molinero et al. (2023). 2.1 Simple games Let Nbe a finite set, we denote P(N)the power set of N.Asimple game is a pair (N,W), where N=[n]={1,...,n}is a finite set of players or voters and W⊆P(N)is a monotonic family of subsets of N,sothatifS⊆T⊆Nand S∈W,thenT∈W.Asusual,weassume that ∅/∈Wand N∈W.SG denotes the family of all simple games. A subset S⊆Nis called a coalition.Nis called the grand coalition.Wis the set of winning coalitions.Thesetoflosing coalitions, denoted by L, is formed by those coalitions that are not winning, i.e., L=P(N)\W.Thesetofminimal winning coalitions, denoted by Wm, is formed by those winning coalitions whose strict subsets are losing coalitions, i.e., Wm={S∈W|∀T∈W,T⊂ S}. Analogously, the set of maximal losing coalitions, denoted by LM, is formed by those losing coalitions whose strict supersets are winning coalitions, i.e., LM={S∈L|∀T∈L,S⊂ T}. Each one of these set families, W,L,Wm and LM, determine uniquely the game and constitute different forms of representations of simple games (Taylor and Zwicker 1999). Note that the size of these representations may not be polynomial in the number of players (Molinero et al. 2015). The operations of intersection and union are defined in a natural way over simple games. Let 1=(N,W1)and 2=(N,W2)be simple games. The intersection of 1and 2is the game with set of players Nand winning coalitions W1∩W2, i.e., the game 1∩2= (N,W1∩W2).Theunion of 1and 2is the game with set of players Nand winning coalitions W1∪W2, i.e., the game 1∪2=(N,W1∪W2). As the set of winning coalitions is monotone, the intersection and the union of simple games are simple games. We represent a permutation σ:[n]→[n], by a vector with ncomponents indicating the image of the nvalues. Given a game =(N,W)and a permutation σon N,thegameσ() is the simple game obtained from by replacing, in each winning coalition, each player i for σ(i). We say that two simple games 1=(N,W1)and 2=(N,W2)are isomorphic if there is a permutation σon Nsuch that 2=σ(1). Example 1 Let be 1=(N=[4],Wm 1={{1,2},{3,4}})and 2=(N=[4],Wm 2= {{1,3},{2,4}}. Both games are isomorphic, i.e., 1≃2, because 1=σ(2)where σ=(1324). Further, every simple game has an associated dual game. Let =(N,W)beasimple game, its dual is the game ∗=(N,W∗)such that W∗={S⊆N|N\S/∈W}.is said to be self-dual or decisive if =∗. We say that a class of games G⊆SG is closed under duality, if, for each ∈SG,∗∈G. We recall now some player properties in a simple game, a player iis: •Dummy if i∈Simplies S/∈Wm, i.e., i/∈S,forallS∈Wm; •Passer if i∈Simplies S∈W, i.e., {i}∈Wm; •Vetoer if i/∈Simplies S/∈W, i.e., N\{i}∈L; •Dictator if i∈S⇔S∈W, i.e., if it is passer and vetoer, i.e., if Wm={{i}}. Apure simple game is a simple game without dummy players. p-SG denotes the family of all pure simple games. 123 339 Page 6 of 30 X. Molinero et al. As we mentioned in Sect.1, many voting systems can be represented as weighted voting games, one of the most relevant subclasses of simple games. A simple game =(N,W)is aweighted voting game if there exists a weighted function on the real numbers, w:N→R, and a real quota q ∈R, such that for any coalition S⊆N,S∈W⇔w(S)=i∈Sw(i)≥ q.WVG and p-WVG denote the families of all weighted voting games and pure weighted voting games, respectively. In simple game theory, the weights of the players i∈Nare usually denoted as wiinstead of w(i). Furthermore, every weighted voting game with a weighted function w, a quota qand a set of players N={1,...,n}can be represented by a vector [q;w1,...,w n]. Moreover, it is well known that both quota and weights can be restricted to be non-negative integer numbers, without losing expressiveness (Taylor and Zwicker 1999). In the following, we will only consider such integer representations. In particular, it is worth mentioning that =[q;w1,...,w n]if and only if ∗=[w(N)−q+1;w1,...,w n]. Thus, is self-dual if and only if 2q=w(N)+1. Although there exist simple games that are not weighted simple games, i.e., WVG ⊂SG, itis knownthat anysimple gamecan berepresented as eitherintersection (Taylor andZwicker 1993) or union (Freixas and Marciniak 2010) of a finite number of weighted voting games. This property leads to the introduction of the dimension and the codimension concepts. Given asimplegame,thedimension of (dim(), in short) is the least number of weighted voting games whose intersection is equal to ,andthecodimension of (codim()) is the least number of weighted voting games whose union is equal to . It is well known that dim() ≤| LM|and codim() ≤|Wm|. Furthermore, dim() = codim(∗)because (1∩2)∗=∗ 1∪∗ 2. See Kurz et al. (2016) for further details. We finish this section by defining a subclass of simple games containing weighted voting games. It is defined from a desirability relation that orders the players according to their influence (Isbell 1958). Let =(N,W)be a simple game, a,b∈N,andS⊆N\{a,b}. We say that a player ais at least as desirable as another player bin if S∪{a}∈Wimplies S∪{b}∈W.Acomplete game is a simple game in which the desirability relation over their players is a complete preorder (Taylor and Pacelli 2008), i.e., a reflexive and transitive binary relation on their players in which any two elements are comparable. CSG and p-CSG denote the families of all complete games and all pure complete games, respectively. Note that WVG ⊂CSG ⊂SG and p-WVG ⊂p-CSG ⊂p-SG. 2.2 Representations Now, we recall some known definitions described by Molinero et al. (2023). Those definitions will be applied later to develop our experiments. Definition 1 Let ∈WVG. A representation [q;w1,w 2,...,w n]of is: •Aminimum representation if, for any representation [q;w 1,w  2,...,w  n]of ,wehave that wi≤w i,foralli∈[n]; •Aminimum sum representation (min-sum,forshort) if,foranyrepresentation [q;w 1,w  2, ...,w  n]of ,wehaven i=1wi≤n i=1w i; •Acanonical representation if and only if wi≥wjwhenever i<j; •An anti-canonical representation if and only if wi≤wjwhenever i<j.Notethatitis a canonical representation but with the weights in reversed order; •The canonical minimum representation (down, for short) of if it is canonical, minsum, and the vector (w1,w 2,...,w n)is lexicographically minimum among all player’s weight vectors of canonical and min-sum representations of . The last condition is 123 Multidimension: a dimensionality extension of simple games Page 7 of 30 339 equivalent to, for any other canonical min-sum representation [q;w 1,...,w  n]of ,if i=min{j∈[n]|wj= w j}then wi<w  i; •The anti-canonical minimum representation (up, for short) of if it is the canonical minimum representation but with the weights in reversed order; •Adown-up representation if it is the down or the up representation. Note that the canonical representation identifies exactly one game for a set of isomorphic games as the definition forces a particular isomorphism. Nevertheless, as a weighted voting game can have more that one min-sum representation, canonical representations might keep more than one game from each class of isomorphic games. According to (Molinero et al. 2023, Prop. 3), a min-sum representation [q;w1,w 2,...,w n]verifies that, for i∈[n], wi=0 if and only if player iis dummy. Note that a simple game (N,W)with a dummy player i∈Ncould be reduced to a simple game with a smaller grand coalition, (N\{i},W), keeping the same winning (and, therefore, losing) coalitions. Hence, we can generate infinite simple games with dummy players from a simple game without dummies only by increasing the set of players N.Weaddthesuffix-pto a representation name to denote the type of representation with the additional condition that all values (quota and weights) must be positive. Observe that such subclasses hold only representations of pure games. We also associate with a type of representation Rthe corresponding subclass of WVG, denoted as R-WVG. Observe that, in general, a game can have infinite representations and more than one representation of a particular type. However, a representation defines only one game. In this way, min-sum-WVG =WVG, but down-WVG (or up-WVG ) contains only one game from each class of isomorphic WVG. In the same way, down-p-WVG (or up-p-WVG ) contains only one game from each class of isomorphic p-WVG. We now recall the definitions of the closure under intersection and union, and the generalization of dimension and codimension to subfamilies of WVG introduced and studied in Molinero et al. (2023). Definition 2 Let Gbe a subclass of weighted voting games. The closure under intersection of G, denoted by SG∩(G), is the set of simple games that can be obtained as the intersection of a finite set of games in G.Thatis, SG∩(G)={∈SG |∃1,..., k∈G,k∈N,and =1∩...∩k}. In a similar way, the closure under union of G, denoted by SG∪(G), is defined using union instead of intersection, i.e., SG∪(G)={∈SG |∃1,..., k∈G,k∈N,and =1∪...∪k}. Definition 3 Let ∈SG and G⊆WVG.Thegeneric dimension of over G(g-dim (, G), in short) is g-dim (, G)=min{t|∃1,..., t∈Gand =1∩...∩t},if ∈SG∩(G) +∞,otherwise. The generic codimension of over G(denoted by g-codim (, G))is g-codim (, G)=min{t|∃1,..., t∈Gand =1∪...∪t},if ∈SG∪(G) +∞,otherwise. In Molinero et al. (2023), among other results comparing the generalized dimension and codimension over different subclasses of weighted voting games, the authors provide a characterization of the closure under intersection and union of the class p-WVG.Before 123 339 Page 8 of 30 X. Molinero et al. stating it, we need to introduce some notation. For, 1 ≤i≤k≤n,definen,[k]:ito be the simple game with set of players N=[n]such that all minimal winning coalitions are the subsets of [k]with ielements. Let Snbe the set of all permutations from [n]to [n]. We also consider the games obtained from n,[k]:iafter permuting the players according to σ∈Sn, denoted as n,σ([k]):i.Notethatn,[k]:iand n,σ ([k]):iare isomorphic and, moreover, ∗ n,σ([k]):i=n,σ([k]):k−i+1. Theorem 1 (Molinero et al. 2023)Let ∈SG with n >1players. Then, g-dim (, p-WVG)=∞,if =n,σ ([k]):1,for1≤k<n and σ∈Sn. <∞,otherwise. Furthermore, by duality, g-codim (, p-WVG)=∞,if =n,σ ([k]):k,for 1≤k<nand σ∈Sn. <∞,otherwise. 3 Generalized multidimension Now, we introduce an extension of the concepts of generalized dimension and codimension that we call generalized multidimension. To do so, we first generalize the type of expressions that can be used to generate a simple game. Definition 4 Let Gbe a subclass of weighted voting games with a set of players N.An N-G-expression is recursively defined by the following rules: •∈Gis an N-G-expression. •If Eand E are N-G-expressions, then so are (E∩E)and (E∪E). •Nothing else is an N-G-expression. Note that we formally combine expressions with the intersection or the union operator using parentheses. However, when there is no risk of ambiguity, we can say E∩E instead of (E∩E),andE∪E instead of (E∪E).Thesize of an N-G-expression E, denoted by size(E), is the number of operators appearing in Eplus one. To each N-G-expression E, we associate a simple game with set of players N, denoted by (N,E), recursively as follows: •If E=∈G,then(N,E)=. •If E=(E∩E),then(N,E)=(N,E)∩(N,E). •If E=(E∪E),then(N,E)=(N,E)∪(N,E). Observe that an N-G-expression can be represented by a binary tree whose internal nodes are labeled by either ∩or ∪and whose leaves are labeled by representations of games in G,all of them defined over the same set of players N. Furthermore, the size of an G-expression E coincides with the number of leaves in the binary tree. Now, we present a particular example where Gis WVG. Example 2 Let 1=[3;1,1,2],2=[2;1,1,2],3=[1;0,1,0]and 4=[3;1,2,1]be four different weighted voting games, and E1=(1∪2)∩3,E2=(1∩3)∪(2∩3) and E3=4be three N-WVG-expressions. Let N={a,b,c}be the set of players of the games. Note that (N,E1)=(N,E2)=(N,E3)since in the three cases we obtain the simple game (N,W)with Wm={{a,b},{b,c}}. Furthermore, the three expressions can be represented by the binary trees illustrated in Fig.1. Although the three expressions generate 4, note that size(E1)=3, size(E2)=4andsize(E3)=1. 123 Multidimension: a dimensionality extension of simple games Page 9 of 30 339 Fig. 1 Binary trees of three N-WVG-expressions generating 4 Note that a simple game with dimension dhas an associated N-WVG-expression formed by the intersection of ddifferent weighted voting games, 1∩ ··· ∩ d. The same occurs for a simple game with codimension d, replacing ∩by ∪in the N-WVG-expression. The size of both expressions is d, which is the number of operators ∩plus one, and also the number of weighted voting games in the expressions. Thus, our definition of the size of an N-WVG-expression is consistent with the concepts of dimension and codimension. It is useful to consider the set of all N-G-expressions. Definition 5 AG-expression is a N-G-expression, for some set of players N. To analyze the expressiveness of G-expressions for subclasses WVG, we introduce the closure concept. Definition 6 Let G⊆WVG be a subclass of weighted voting games. The closure under Gexpression of G, denoted by SGE(G), is the set of simple games associated to G-expressions, i.e., SGE(G)=∪ n∈N,|N|=n{(N,E)|Eis a N-G-expression}. Using this association, we define the generalized multidimension of a simple game over a subclass of weighted voting games G⊆WVG as follows. Definition 7 Let =(N,W)∈SG.Thegeneralized multidimension over a subclass of weighted voting games Gof ∈SGE(G)is the minimum size of an N-G-expression Ewith =(N,E). We denote such generalized multidimension over Gof by g-mdim (, G). When /∈SGE(G), we say that its multidimension is infinite, i.e., g-mdim (, G)=∞. Observe that the game defined on Example 2has generic dimension, generic codimension and generic multidimension over WVG equal to 1. It is clear that the generalized multidimension depends on the considered subclass. Example 3 Let 1=[1;1,1,0,0,0]and 2=[1;0,0,1,1,1]be two weighted voting games. Note that [1;1,1,0,0,0]is the down representation of 1,and[1;0,0,1,1,1]is the uprepresentationof2.Furthermore,2doesnotadmitanydownrepresentationasplayer1is a dummy player. Therefore, we have the following result: 1 =g-mdim (1,down-WVG)< g-mdim (2,down-WVG). In a similar way, g-mdim (1,up-WVG)> g-mdim (2,up-WVG)=1. Moreover, it is clear that g-mdim (1,down-up-WVG)= g-mdim (2,down-up-WVG)=1. Aseverysimplegamecan bedefinedasintersection orunionofafinite numberofweighted voting games, we always have a finite N-WVG-expression describing it. In particular, as every simple game has a finite dimension and codimension (Taylor and Zwicker 1999), every simple game also has a finite g-mdim (, WVG). Moreover, given a simple game ,g-mdim (, WVG)≤min{dim(), codim()}. As we have mentioned before, Boolean weighted voting games were introduced by Faliszewski et al. (2009). These games are defined by means of monotone Boolean formulas 123 339 Page 16 of 30 X. Molinero et al. From the enumeration of down-p-WVG , we are able to enumerate other subclasses of simple games. The games of up-p-WVG are obtained by considering the mirror of each game [q;w1,...,w n]∈down-p-WVG, i.e., [q;wn,...,w 1]. For instance, given [5;3,2,2,1]∈ down-p-WVG,weconsider[5;1,2,2,3]∈up-p-WVG. On the other hand, the games of down-up-p-WVG are generated doubling each game [q;w1,...,w n]∈down-p-WVG as a mirror[q;wn,...,w 1],e.g.,given[5;3,2,2,1],weconsider[5;3,2,2,1]and[5;1,2,2,3]. For each number of players, we use the list of the games in the considered class (e.g., down-WVG ,down-p-WVG or any class) together with an enumerator of the well-formed expressions over the intersection and union operators to obtain in increasing order of multidimension the new generated games. The first experiment (see Table 2b) computes the generalized multidimension over p-WVG.First,wegenerate newsimple gameswithintersectionor unionoftwopureweighted voting games, up to 6 players. Second, we compute new simple games combining intersections and unions of three pure weighted voting games, and, so on. As we said before, all multidimensionality results has been obtained with the stopping criteria described in Theorem 8. Finally, we count the number of generated simple games up to isomorphism. We follow the same procedure described before for all our experiments, but assuming the corresponding subclass of weighted voting games. Now, Table 1presents some known counting results for p-SG,p-CSG,andp-WVG,upto isomorphism. All these results appear in (or can be deduced from) the so-called The On-Line Encyclopedia of Integer Sequences (http://oeis.org/). Table 2presents the results for the generalized dimension and multidimension over p-WVG of p-SG having up to 6 players. From Theorems 1and 6, we know that not all SG have finite generalized dimension or multidimension with respect to the class p-WVG. The results over the generalized dimension come from (Molinero et al. 2023). The results over generalized multidimension come from our experiments and thus there are completely new. This table shows us that, with respect to p-WVG, as expected the multidimension of a game can be strictly smaller than its dimension. It is interesting to note that the highest value of the multidimension is smaller than the highest value of the dimension. Even more, the three simple games with 6 players having maximum dimension of 5 have also maximum multidimension of 4. In the next Example, we analyze these three games in more detail. Example 8 Table 2shows that there are only three simple games of 6 players with dimension andcodimensionequalto 5.Reproducing theexperimentsaccordingtoMolinero etal.(2023), these three simple games are 1=([6],Wm 1={{1,2,3},{1,3,6},{1,4,5},{1,5,6},{2,3,5},{2,4,6}, {2,5,6},{3,4,5},{3,4,6}}), 2=∗ 1, and the self-dual 3=([6],Wm 1={{1,3,4},{2,3,4},{1,2,5},{2,3,5},{1,4,5},{1,2,6}, {1,3,6},{2,4,6},{3,5,6},{4,5,6}}). We checked that no other intersection/union with less than 5 p-WVG gives i,fori∈[3], i.e., g-dim (p-WVG, i)=g-codim (p-WVG, i)=5. In particular, we get the following 123 Multidimension: a dimensionality extension of simple games Page 17 of 30 339 Table 1 Counting for SG,p-SG,p-CSG,andp-WVG, up to isomorphism (Molinero et al. 2023) (Sub)class Number of players 1234 5 6 7 8 9 SG 1 3 8 28 208 16,351 490,013,146 1,392,195,548,889,993,356 ? (oeis.org/A003182) p-SG 1 2 5 20 180 16,143 489,996,795 1,392,195,548,399,980,210 ? (oeis.org/A006602) p-CSG 1 2 5 17 92 1054 43,142 16,130,875 284,416,554,986 (oeis.org/A132183) p-WVG 1 2 5 17 92 994 28,262 2,700,791 990,331,318 (oeis.org/A000619) 123 339 Page 18 of 30 X. Molinero et al. Table 2 Counting pure simple games with g-dim (, p-WVG)=dand g-mdim (, p-WVG)=m (a)Numberofgames∈p-SG with g-dim (, p-WVG)=d, for the different values of d,upto isomorphism dNumber of players (n) 123456 11251792994 2000 38611,168 3 0 0 0 0 2 3595 4000 0 0383 5000 0 0 3 Total 1 2 5 20 180 16,143 p-SG 1 2 5 20 180 16,143 (b) Number of games ∈p-SG with g-mdim (, p-WVG)=m, for the different values of m,upto isomorphism mNumber of players (n) 123456 11251792994 2000 38612,755 3 0 0 0 0 2 2388 4000 0 0 6 5000 0 0 0 Total 1 2 5 20 180 16,143 p-SG 1 2 5 20 180 16,143 expressions: 1=[4;2,2,2,1,1,1]∩[4;2,1,1,2,2,1]∩[5;2,3,1,3,1,2]∩[8;1,2,5,3,4,3]∩[8;3,2,3,1,4,5] =σ1([6;2,2,2,1,1,1]∪[8;3,2,1,3,2,1]∪[8;3,1,2,1,2,3]∪[8;1,3,2,1,3,2]∪[8;1,1,3,3,2,2]), 2=σ1([4;2,2,2,1,1,1]∩[5;3,2,1,3,2,1]∩[5;3,1,2,1,2,3]∩[5;1,3,2,1,3,2]∩[5;1,1,3,3,2,2] =[6;2,2,2,1,1,1]∪[6;2,1,1,2,2,1]∪[ 8;2,3,1,3,1,2]∪[11;1,2,5,3,4,3]∪[11;3,2,3,1,4,5], 3=[5;3,3,2,2,1,1]∩[5;3,1,2,1,3,2]∩[5;1,3,2,1,2,3]∩[5;1,2,2,3,3,1]∩[5;2,1,2,3,1,3] =[8;3,3,2,2,1,1]∪[8;3,1,2,1,3,2]∪[8;1,3,2,1,2,3]∪[8;1,2,2,3,3,1]∪[8;2,1,2,3,1,3], where σ1=(643251 )is the corresponding permutation among players. However, our experiments show that g-mdim (p-WVG, 1)=4. Particular cases with minimum size for i,beingi∈[3],are 1=σ2([4;2,2,2,1,1,1]∩([5;3,3,2,2,1,1]∩([8;4,3,3,2,2,1]∪[11;5,4,3,3,2,1]))), 2=σ2([6;2,2,2,1,1,1]∪([8;3,3,2,2,1,1]∪([5;3,3,2,2,1,1]∩[8;4,3,3,2,2,1]))), 3=σ3([8;3,3,2,2,1,1]∪([10;6,5,4,3,2,1]∩([8;4,3,2,2,1,1]∪[8;4,3,3,2,2,1]))), where σ2=(264315 )and σ3=(341265 ). It is worth mentioning that only 3 out of 383 games with 6 players and generalized dimension with respect to p-WVG equal to 4 keep their generalized multidimension equal to 4. For up to 6 players the maximum value of the generalized dimension is strictly smaller that the maximum value of the generalized multidimension. It remains open to see if this property carries on for any number of players. 123 Multidimension: a dimensionality extension of simple games Page 19 of 30 339 Table 3 Countingpuresimplegameswithg-dim (, down-p-WVG)=dandg-mdim (, down-p-WVG)= m (a) Number of games ∈p-SG with g-dim (, down-p-WVG)=d,for the different values of d,upto isomorphism dNumber of players 1 234567 1 1 2 5 17 92 994 28,262 2 0 0 0 0 0 55 13,808 3 0 0 0 0 0 2 539 4000000 38 Total 1 2 5 17 92 1051 42,647 p-CSG 1 2 5 17 92 1054 43,142 p-SG 1 2 5 20 180 16,143 489,996,795 (b)Numberofgames∈p-SG with g-mdim (, down-p-WVG)=m,for the different values of m,up to isomorphism mNumber of players 1 234567 1 1 2 5 17 92 994 28,262 2 0 00006014,880 3000000 0 4000000 0 Total 1 2 5 17 92 1054 43,142 p-CSG 1 2 5 17 92 1054 43,142 p-SG 1 2 5 20 180 16,143 489,996,795 Experimental results about the generalized dimension and multidimension of p-SG with respect to games in down-p-WVG are presented in Table 3. As it was mentioned in Molinero et al. (2023), intersections (or unions) of games in down-p-WVG belong to p-CSG.We combined our multidimension enumeration algorithm with a checker for completeness. Our experiments show that, for up to 7 players, all simple games generated by G-expressions over down-p-WVG belong to CSG. It will be worth to see whether this property holds for any number of players. In the light of our experiments, we think that it is true, but we have not formally proved it yet. Another property is that G-expressions over down-p-WVG allow us to obtain more games that when using only intersections/unions. This phenomenon appears for 6 and 7 players in our experiments. We want to note that, for 6 and 7 players, down-p-WVG generate all games in CSG. Another unexpected property that we can extract from the table is that the maximum value of the multidimension is 2, while the maximum value of the dimension is 4. The experimental results about generalized multidimension of simple games with respect to the subclasses down-p-WVG and down-WVG appear in Table 4. In this experiment, we removed the filter checking pureness and kept the filter for completeness. All generated games belong to CSG. In particular, from Table 4a, we can see that it is not possible to generate all complete games with nplayers using down-p-WVG -expressions while, up to 7 players, it is possible with down-WVG -expressions. As we have mentioned before, for up 123 339 Page 20 of 30 X. Molinero et al. Table 4 Counting simple games with g-mdim (, down-p-WVG)=mand g-mdim (, down-WVG)=m (a) Number of games ∈SG with g-mdim (, down-p-WVG)=m,for the different values of m,upto isomorphism mNumber of players 1234567 1 125179299428,262 2 0 0 0 2 15 162 16,030 p-CSG 12517921054 43,142 CSG\p-CSG 0 0 0 2 15 2 1150 Total 125191071156 44,292 p-CSG 12517921054 43,142 CSG 138251171171 44,313 p-SG 1 2 5 20 180 16,143 489,996,795 (b) Number of games ∈SG with g-mdim (, down-WVG)=m,for the different values of m,upto isomorphism mNumber of players 1234567 1 138251171111 29,373 2 000 0 0 6014,940 p-CSG 12517921054 43,142 CSG\p-CSG 0 1 3 8 25 117 1171 Total 138251171171 44,313 p-CSG 12517921054 43,142 CSG 138251171171 44,313 p-SG 1 2 5 20 180 16,143 489,996,795 to 7 players, we can generate all p-CSG. Now we can see that some, but not all, games in CSG\p-CSG can be generated with down-p-WVG -expressions. For example, for n=6, we obtained only 2 of the 25 complete games that are not pure. Ourresultsaboutgeneralizeddimensionandmultidimensionofgamesindown-up-p-WVG are presented in Table 5. Molinero et al. (2023) shows that =(N,Wm)with Wm= {{1,2},{1,3,4},{2,3,4},{1,3,5,6},{2,3,5,6},{1,4,5,6},{2,4,5,6},{3,4,5,6}} verifies that g-dim (, p-WVG)=∞.However,=1∪2,where1=(N,Wm 1)with Wm 1={{1,2,3,4},{1,2,3,5},{1,2,4,5},{1,3,4,5},{2,3,4,5},{1,2,3,6},{1,2,4,6}, {1,3,4,6},{2,3,4,6},{1,2,5,6},{1,3,5,6},{2,3,5,6},{1,4,5,6},{2,4,5,6},{3,4,5,6}} has a representation [4;1,1,1,1,1,1]and 2=(N,Wm 2)with Wm 2={{1,2}, {1,3,4},{2,3,4},{1,3,5,6},{2,3,5,6},{1,4,5,6},{2,4,5,6}} has a representation [8;4,4,2,2,1,1]. Thus, g-mdim (, p-WVG)=2. That is why Table 5a shows that only 1053 pure complete games for 5 players can be obtained with intersections, but Table 5b shows that all 1054 p-CSG can be obtained with down-up-p-WVG -expressions. Table 6shows the experimental results about multidimension of SG with respect to the subclasses down-up-p-WVG and down-up-WVG . As expected, we can see that neither down-up-p-WVG -expressions nor down-up-WVG -expressions can generate all simple games. Comparing Tables 6aand4a, it is clear that even down-up-p-WVG -expression generate a much bigger quantity of games than down-p-WVG -expression. 123 Multidimension: a dimensionality extension of simple games Page 21 of 30 339 Table5 Countingpuresimplegameswithg-dim (, down-up-p-WVG)=dandg-mdim (, down-p-WVG)= m (a)Numberofgames∈p-SG with g-dim (, down-up-p-WVG)=d,for the different values of d,up to isomorphism dNumber of players 1 23456 1 1 2 5 17 92 994 2 0 0 0 3 66 3403 3 0 0 0 0 2 118 4000000 p-CSG 1 2 5 17 92 1053 p-SG\p-CSG 0 0 0 3 68 3462 Total 1 2 5 20 160 4515 p-CSG 1 2 5 17 92 1054 p-SG 1 2 5 20 180 16,143 (b) Number of games ∈p-SG with g-mdim (, down-up-p-WVG)=m,for the different values of m, up to isomorphism mNumber of players 1 23456 1 1 2 5 17 92 994 2 0 0 0 3 76 5342 3 0 0 0 0 10 6237 4 0 0 0 0 2 3273 5 0 0 0 0 0 163 60000069 7...12 0 0 0 0 0 0 p-CSG 1 2 5 17 92 1054 p-SG\p-CSG 0 0 0 3 88 15,024 Total 1 2 5 20 180 16,078 p-CSG 1 2 5 17 92 1054 p-SG 1 2 5 20 180 16,143 Note that the two games with 5 players and mutidimension 4 that appear in Table 5balso appearinTable6b,uptoisomorphism.Moreover,theybotharedualoneeachother.Ontheone hand, our experiments of Table 5bgiveus1=([5],Wm 1={{1,3,4},{2,3,4},{1,2,5}, {1,3,5},{2,4,5}})and 2=([5],Wm 2={{1,2},{2,3},{1,4}, {3,5},{4,5}}),where 1=[4;2,2,1,1,1]∩([5;1,1,2,2,3]∩([8;4,3,3,2,1]∪[8;1,2,2,3,3])) and 2=[4;2,2,1,1,1]∪([5;1,1,2,2,3]∪([6;4,3,3,2,1]∩[4;1,2,2,3,3])). On the other hand, our experiments of Table 6b generate 1=([5],Wm 1={{1,2,4}, {2,3,4},{1,3,5},{2,3,5},{1,4,5}})and 2=([5],Wm 2={{1,2},{1,3},{3,4},{2,5}, 123 339 Page 22 of 30 X. Molinero et al. Table 6 Counting simple games with g-mdim (, down-up-p-WVG)=mandg-mdim (, down-up-WVG) =m (a) Number of games ∈SG with g-mdim (, down-up-p-WVG)=m,for the different values of m, up to isomorphism mNumber of players 123456 11251792994 2 0 0 2 9 99 5462 3 0 0 0 1 13 6266 4 0 0 0 0 3 3306 5000 0 0173 6000 0 0 75 7...12 0 0 0 0 0 0 Total 1 2 7 27 207 16,276 CSG 1 3 8 25 117 1171 p-CSG 1 2 5 17 92 1054 SG 1 3 8 28 208 16,351 p-SG 1 2 5 20 180 16,143 (b)Numberofgames∈SG with g-mdim (, down-up-WVG)=m,for the different values of m,up to isomorphism mNumber of players 123456 1 1 3 8 25 117 1111 2 0 0 0 3 82 5566 3 0 0 0 0 6 6053 4 0 0 0 0 3 3299 5000 0 0173 6000 0 0 75 7...12 0 0 0 0 0 0 Total 1 3 8 28 208 16,277 CSG 1 3 8 25 117 1171 p-CSG 1 2 5 17 92 1054 SG 1 3 8 28 208 16,351 p-SG 1 2 5 20 180 16,143 {4,5}}),where 1=[1;0,0,0,1,1]∩([5;3,2,2,1,1]∩([3;0,0,1,1,2]∪[5;0,3,2,2,1)])) and 2=[2;0,0,0,1,1]∪([5;3,2,2,1,1]∪([2;0,0,1,1,2]∩[4;0,3,2,2,1)])). Observe that 1=σ(1)and 2=σ(2),whereσ=(14235 ). Our last experiment analyzes the generalized multidimension over S-SG.Remindthat Theorem 5shows us SGE(S-SG)is the set of all simple games. Now, Table 7enumerates the generalized multidimension of all simple games from unions and intersections of S-SG, up to 6 players. 123 Multidimension: a dimensionality extension of simple games Page 23 of 30 339 Table 7 Numberofgames∈p-SG withg-mdim , j∈N(j)=m,forvaluesofm,uptoisomorphism mNumber of players 1234 5 6 1111111 2022222 3004444 4 0 0 0 10 10 10 500122626 600061682 7 0 0 0 1 42 107 8 0 0 0 2 35 326 9 0 0 0 0 44 613 10 0 0 0 0 18 1258 11 0 0 0 0 3 2078 12 0 0 0 0 6 2902 13 0 0 0 0 0 3285 14 0 0 0 0 1 2878 15 0 0 0 0 0 1780 16 0 0 0 0 0 786 17 0 0 0 0 0 172 18 0 0 0 0 0 38 19 0 0 0 0 0 3 Total 1 3 8 28 208 16,351 CSG 1 3 8 25 117 1171 p-CSG 1 2 5 17 92 1054 SG 1 3 8 28 208 16,351 p-SG 1 2 5 20 180 16,143 Our new experiments for generalized multidimension, and the reproduced experiments according to Molinero et al. (2023) for generalized dimension and generalized codimension show us that, even for 3 players, there exists ∈SG such that g-mdim ⎛ ⎝,  j∈N (j) N⎞ ⎠<min ⎧ ⎨ ⎩ g-dim ⎛ ⎝,  j∈N (j) N⎞ ⎠,g-codim ⎛ ⎝,  j∈N (j) N⎞ ⎠⎫ ⎬ ⎭ . Example 9 For 3 players, =([1;1,0,0]∩[1;0,1,0])∪([1;0,0,1]∩([1;1,0,0]∪ [1;0,1,0])) really verifies g-mdim , j∈N(j) N=5, but g-dim , j∈N(j) N= g-codim , j∈N(j) N=6. 123 339 Page 24 of 30 X. Molinero et al. On the other hand, for N=[6]players, =(1) N∪(3) N∩(2) N∪(6) N∩(4) N∪(5) N∪ (1) N∪(5) N∩(2) N∪(3) N∩(4) N∪(6) N∪ (1) N∪(6) N∩(2) N∪(5) N∩(3) N∪(4) N verifies g-mdim ,j∈N(j) N=18. To give a brief idea how our experiments work, we show the output of our program with all specific information for using a structure that indents the level of the expression: (1;100000)1 (UNION) 1 3 (1;001000)3 (INTERSECTION) 124 234 125 235 146 346 156 356 (1;000010)5 (UNION) 4 5 (1;000100)4 (INTERSECTION) 24 25 46 56 (1;000001)6 (UNION) 2 6 (1;010000)2 (UNION) 123 124 134 234 125 135 235 14 5 245 345 126 136 236 146 246 346 156 256 356 456 (1;100000)1 (UNION) 1 5 (1;000010)5 (INTERSECTION) 124 134 245 345 126 136 256 356 (1;000001)6 (UNION) 4 6 (1;000100)4 (INTERSECTION) 24 34 26 36 (1;010000)2 (UNION) 2 3 (1;001000)3 (UNION) 123 124 134 135 145 245 345 126 136 236 246 256 356 456 (1;100000)1 (UNION) 1 6 (1;000001)6 (INTERSECTION) 123 124 135 145 236 246 356 456 (1;000010)5 (UNION) 2 5 (1;010000)2 (INTERSECTION) 23 24 35 45 (1;000100)4 (UNION) 3 4 (1;001000)3 Note that the elements to the right of each row give the minimal wining coalitions of the game. For instance, 24 25 46 56 at the 8th row indicates that the set of minimal winning coalitions of [1;0,0,0,0,1,0]∩[1;0,0,0,0,0,1]is Wm={{2,4},{2,5},{4,6},{5,6}}. Reproducing the experiments of Molinero et al. (2023), we obtain that, even though g-mdim ,j∈N(j) N=18, g-dim ,j∈N(j) N=g-codim ,j∈N(j) N= 60. In Appendix A, we show the output of some of our experiments. There we give the games with maximum generalized multidimension over S-SG and the corresponding G-expression certifying this fact, from three to six players. 123 Multidimension: a dimensionality extension of simple games Page 25 of 30 339 6 Conclusions and future work Inthis work,we considersubclasses ofsimple gamesgenerated from G-expressions,using the operators intersection and union, over restricted subclasses of weighted voting games. Using those expressions, we have introduced the multidimension as an extension of the notions of dimension and codimension of simple games. We have generalized this notion with respect to a subfamily of WVG, namely, the generalized multidimension. Most of the considered subclasses of WVG are formed by games without dummy players (pure weighted voting games) and are obtained by selecting particular types of representations of WVG. Thus, our work extends the theoretical and experimental results of Molinero et al. (2023). A theoretically relevant type of game is the singleton game, made up of exactly one minimal winning coalition formed by a single player. Singleton games are the unique games having one dictator while all the other players are dummies. According to Theorem 5,aclass able to generate all the singleton games, through union and intersection operations, generates allthe simple games.Furthermore, if weonly havepureweightedvotinggames,that is, games withoutdummies,theonlygameswecannotgenerate(throughunionand/orintersectionoperations) are the singleton games (see Theorem 6). Therefore, any other game than a singleton gamewillhavefinitegeneralized multidimensionwithrespect topureweightedvotinggames. From the point of view of voting systems, the above means that dictators can only emerge to the extent that we assume the existence of dummies. Comparing our characterization of the simple games that can be generated with expressions on p-WVG with respect to the ones having finite generalized dimension or codimension provided in Molinero et al. (2023), we can observe that the games that cannot be expressed in this way are the self-dual games that do not have finite generalized dimension/codimension. Thus, singleton games are the only self-dual games that do not have finite generalized dimension/codimension with respect to p-WVG. Besides the above, we have proved that the multidimension has properties quite different from the dimension or the codimension. We have shown that the generalized dimension, with respect to a class closed under duality, is the same for dual games. Surprisingly, we have demonstrated the existence of gaps in the attained multidimension values. The latter has to be seen in contraposition with the continuity of the dimension/codimension values proved in Molinero et al. (2023). Although the multidimension values are not contiguous, we have proved that having a big enough interval without games of these multidimension ensures that no game has higher multidimension. This result is the key ingredient in our enumeration algorithm. According to Theorem 8, we need a gap of half the size of the value. The gap size is relevant to programming the correct termination criterion in the enumeration algorithm. It remains an open question, both theoretically and practically, to see if this gap size can be reduced. Thus, experimentally, we were able to calculate the multidimensions for all simple games with respect to some subclasses of p-WVG up to 6 players and, in some cases, up to 7 players. Our results show how generalized multidimension allows representing more simple games than considering only intersections or only unions. Moreover, the representations tend to be more compact, even for a small number of players and for subclasses with a relatively small number of games. We can state several problems of interest. It remains open finding (if there exist) examples where the multidimension is linear on the number of players, but the dimension and the codimension are exponential on the number of players. In all our enumerations, the maximum generalized multidimension attained has been smaller than the maximum generalized 123