Improved lower bound on the dimension of the EU council’s voting rules

Kober, Stefan; Weltge, Stefan Article — Published Version Improved lower bound on the dimension of the EU council’s voting rules Optimization Letters Provided in Cooperation with: Springer Nature Suggested Citation: Kober, Stefan; Weltge, Stefan (2020) : Improved lower bound on the dimension of the EU council’s voting rules, Optimization Letters, ISSN 1862-4480, Springer, Berlin, Heidelberg, Vol. 15, Iss. 4, pp. 1293-1302, https://doi.org/10.1007/s11590-020-01637-5 This Version is available at: https://hdl.handle.net/10419/288939 Standard-Nutzungsbedingungen: Die Dokumente auf EconStor dürfen zu eigenen wissenschaftlichen Zwecken und zum Privatgebrauch gespeichert und kopiert werden. Sie dürfen die Dokumente nicht für öffentliche oder kommerzielle Zwecke vervielfältigen, öffentlich ausstellen, öffentlich zugänglich machen, vertreiben oder anderweitig nutzen. Sofern die Verfasser die Dokumente unter Open-Content-Lizenzen (insbesondere CC-Lizenzen) zur Verfügung gestellt haben sollten, gelten abweichend von diesen Nutzungsbedingungen die in der dort genannten Lizenz gewährten Nutzungsrechte. Terms of use: Documents in EconStor may be saved and copied for your personal and scholarly purposes. You are not to copy documents for public or commercial purposes, to exhibit the documents publicly, to make them publicly available on the internet, or to distribute or otherwise use the documents in public. If the documents have been made available under an Open Content Licence (especially Creative Commons Licences), you may exercise further usage rights as specified in the indicated licence. https://creativecommons.org/licenses/by/4.0/ Optimization Letters (2021) 15:1293–1302 https://doi.org/10.1007/s11590-020-01637-5 ORIGINAL PAPER Improved lower bound on the dimension of the EU council’s voting rules Stefan Kober1·Stefan Weltge1 Received: 26 March 2020 / Accepted: 24 August 2020 / Published online: 5 September 2020 © The Author(s) 2020 Abstract Kurz and Napel (Optim Lett 10(6):1245–1256, 2015, https://doi.org/10.1007/s11590015-0917-0) proved that the voting system of the EU council (based on the 2014 population data) cannot be represented as the intersection of six weighted games, i.e., its dimension is at least 7. This set a new record for real-world voting rules and the authors posed the exact determination as a challenge. Recently, Chen et al. (An upper bound on the dimension of the voting system of the European Union Council under the Lisbon rules, 2019, arXiv:1907.09711) showed that the dimension is at most 24. We provide the first improved lower bound and show that the dimension is at least 8. Keywords Simple games ·Weighted games ·Dimension ·Real-world voting systems 1 Introduction Simple games are cooperative games that are commonly used to describe real-world voting systems. Considering a fixed, finite set Mof voting members, a simple game is given by a collection Wof subsets of Msatisfying the monotonicity property: C∈W and C⊆C⊆Mimplies C∈W. The sets in Ware called winning coalitions, and each subset of Mthat is not in Wis called a losing coalition. It is convenient to require the empty coalition to be losing and the grand coalition of all voting members to be winning when dealing with real-world examples. A fundamental class of simple games are weighted games whose winning coalitions can be written as W=C⊆M: m∈C am≥β BStefan Kober [email protected] 1Advanced Optimization in a Networked Economy (AdONE), Technical University of Munich, Arcisstr. 21, 80333 Munich, Germany 123 1294 S. Kober, S. Weltge for some a∈RM ≥0and β∈R. Note that there exist winning and losing coalitions if and only if 0 <β≤m∈Mam. It is a basic fact that every simple game is the intersection of finitely many weighted games, and hence we may define the dimension of a simple game Wto be the smallest number of weighted games whose intersection is W. In a similar way, the codimension of a simple game was defined by replacing intersection with union in the above definition [7]. As a third measure for the complexity of the description of simple games, the boolean dimension was introduced, which allows arbitrary combinations of intersections and unions [5]. The three notions are similarly interesting from a mathematical point of view. Nevertheless, the notion of dimension stands out above the others for its analogy to the H-representation of polyhedra. Determining the dimension of (simple games associated to) real-world voting systems has been of particular interest in social choice theory, see, e.g., the books by Taylor and Zwicker [14] and Taylor and Pacelli [12]. Even though it is in general NP-hard to determine the exact dimension of a given simple game [3], the dimensions of many real voting rules are known. For instance, many real world examples actually have dimension one, which is easy to verify. Examples of dimension two are given by the US federal legislative system [13] and the amendment of the Canadian constitution [10]. A voting rule of dimension three has been adopted by the Council of the European Union under the treaty of Nice [6] and by the Legislative Council of Hong Kong [2]. A new record was set with the change of the EU (European Union) council’s voting system by the Treaty of Lisbon in 2014. Based on the population data of 2014, Kurz and Napel [11] showed that its dimension is at least 7 and at most 13,368, and they posed the exact determination as a challenge to the community. In response, Chen et al. [1] were able to reduce the upper bound to 24. We provide the first improved lower bound and show that the dimension is at least 8. Although we will not rely on this interpretation in what follows, the idea behind our lower bound is based on the observation that the dimension of a simple game Wcan be seen as the chromatic number of a particular hypergraph H: the nodes of Hare the losing coalitions, and a set of losing coalitions Nforms a hyperedge iff N∩W=∅for every weighted game W⊇W. The proof of Kurz and Napel [11] establishes that Hcontains a clique of cardinality 7, which directly implies that the chromatic number of His at least 7. This idea has been used previously in the context of lower bounds on sizes of integer programming formulations [4,8,9]. While we have not found any simple subgraph of larger chromatic number, we will show that Hcontains a hypergraph on 15 nodes whose chromatic number is 8. Outline In Sect. 2we introduce the concept of non-separable subsets of the losing coalitions of a simple game W. A family Fof such subsets can be thought of as a subgraph of the above hypergraph. Moreover, we consider the notion of a k-cover for such a set F, which can be seen as a node-coloring of the respective subgraph with kcolors. Accordingly, we will see that if the dimension of Wis at most k, then there exists a k-cover for each F. In Sect. 3we consider the simple game associated to the EU council and give a construction of a set F, for which no 7-cover exists. A proof of the latter fact will be given in Sect. 4. In the final Sect. 5, we comment on 123 Improved lower bound on the dimension of the EU council’s… 1295 the structure of the subgraph, that is used to obtain the improved lower bound and on possible further improvements. 2 Strategy In what follows, we consider simple games on a common fixed ground set M. Definition 1 Let Wbe a simple game and Nbe any set of losing coalitions of W. We say that Nis non-separable with respect to Wif every weighted game W⊇W satisfies W∩N=∅. From the definition it is immediate that a simple game is weighted if and only if no set of losing coalitions is non-separable. So, the existence of a single non-separable set yields that the dimension of a simple game is at least two. To obtain a larger lower bound, the following notion will be useful. Definition 2 Let Wbe a simple game with losing coalitions L, and let N1,...,Nt⊆L be non-separable with respect to W.Ak-cover of (N1,...,Nt)is a collection of sets L1,...,Lk⊆Lsuch that 1. L1∪···∪Lk=N1∪···∪Ntand 2. NiLjfor all i∈{1,...,t},j∈{1,...,k}. In order to obtain a lower bound on the dimension, we will exploit the following observation. Lemma 1 Let Wbe a simple game with non-separable sets N1,...,Nt.IfWhas dimension at most k, then there exists a k-cover for (N1,...,Nt). Proof If Whas dimension at most k, then there exist kweighted games W1,...,Wk such that k i=1Wi=W.Fori∈{1,...,k}define Lias the intersection of the losing coalitions in Wiand L∗:=N1∪···∪Nt. We claim that (L1,...,Lk)is a k-cover of (N1,...,Nt). In order to show Property 1., first observe that L1∪···∪Lk⊆L∗holds. Now, for any ∈L∗⊆Lwe have /∈Wand hence there is an i∈{1,...,k}with /∈Wi, which implies ∈Li. For Property 2., assume that Ni⊆Ljholds for some i∈{1,...,t}and j∈ {1,...,k}. This means that each coalition in Niis losing for Wj, meaning that Ni and Wjare disjoint. This contradicts the fact that Niis non-separable with respect to Wsince Wj⊇Wis weighted.  In what follows, we will consider the simple game associated with the EU council and construct a collection of non-separable losing coalitions that does not permit a 7-covering. By Lemma 1this implies that the dimension must be at least 8. 3 Our construction Let us give a formal definition of the simple game associated to the EU council based on the population data of 2014, as considered by Kurz and Napel [11]. In 2014, the 123 1296 S. Kober, S. Weltge European Union consisted of 28 members and hence we may fix M:={1,...,28}.In the voting system of the EU council, a coalition is winning if 1. it contains at least 55% of all members states and 2. it unites at least 65% of the total EU population, or 3. it consists of at least 25 of the 28 member states. Denoting the weighted game associated with rule iby Wiand the simple game that represents the voting system of the EU council by WEU, we thus have WEU =(W1.∩W2.)∪W3.. Note that W2.depends on the population of each member state. As in [11], we will work with the data depicted in Table 1. Out of the 228 possible coalitions, 30,340,718 are winning. It can be seen that the following coalitions are losing with respect to WEU. L1:=M\{1,4,7,13,14}L2:=M\{2,3,6,13} L3:=M\{1,4,5,28}L4:=M\{1,2,10,11,14} L5:=M\{1,3,8,11,15}L6:=M\{1,4,8,9,12} L7:=M\{1,2,7,17,18}L8:=M\{1,5,6,16,18} L9:=M\{2,4,6,15,21}L10:=M\{1,3,9,10,12} L11:=M\{3,4,5,20,22}L12:=M\{2,3,7,8,9} L13:=M\{1,3,6,26}L14:=M\{2,3,5,19} L15:=M\{16,17,...,28} In fact, note that each coalition Licontains less than 25 members. Now, L1,...,L14 are losing since each of them unites less than 65% of the total EU population, and L15 is losing since it contains less than 55% of all members. Next, we construct non-separable subsets with respect to WEU that consist of the above losing coalitions. In order to verify that these subsets are indeed non-separable, the following lemma is helpful. Lemma 2 Let Wbe a simple game and let W∗and Nbe sets of some winning and losing coalitions for W, respectively, such that |W∗|≥|N|.If |{W∈W∗:m∈W}| ≤ |{L∈N:m∈L}| holds for all m ∈M, then Nis non-separable with respect to W. Proof Consider any weighted game W={C⊆M:m∈Cam≥β}⊇Wwith a∈RM ≥0and β∈R. Then we have  L∈N m∈L am≥ W∈W∗ m∈W am≥βW∗. 123 Improved lower bound on the dimension of the EU council’s… 1297 Table 1 Population data of the European Union on 01.01.2014, see also [11, Table 1] # Member state Population Percentage (%) # Member state Population Percentage (%) 1Germany 80,780,000 15.9 15 Austria 8,507,786 1.7 2France 65,856,609 13.016Bulgaria7,245,677 1.4 3 United Kingdom 64,308,261 12.7 17 Denmark 5,627,235 1.1 4 Italy 60,782,668 12.0 18 Finland 5,451,270 1.1 5 Spain 46,507,760 9.219Slovakia5,415,949 1.1 6 Poland 38,495,659 7.6 20 Ireland 4,604,029 0.9 7 Romania 19,942,642 3.9 21 Croatia 4,246,700 0.8 8 Netherlands 16,829,289 3.3 22 Lithuania 2,943,472 0.6 9 Belgium 11,203,992 2.2 23 Slovenia 2,061,085 0.4 10 Greece 10,992,589 2.2 24 Latvia 2,001,468 0.4 11 Czech Republic 10,512,419 2.1 25 Estonia 1,315,819 0.3 12 Portugal 10,427,301 2.1 26 Cyprus 858,000 0.2 13 Hungary 9,879,000 1.9 27 Luxembourg 549,680 0.1 14 Sweden 9,644,864 1.9 28 Malta 425,384 0.1 123 1298 S. Kober, S. Weltge The last inequality holds because all elements of W∗are contained in W. Thus, there must exist some L∈N, such that  m∈L am≥β·|W∗| |N|≥β. Therefore, we have L∈Wand hence W∩N=∅. Since this holds for any weighted game W⊇W,Nis non-separable with respect to W. We claim that the following 2-element subsets of the above losing coalitions are non-separable. {L1,L5},{L1,L8},{L1,L9},{L1,L10},{L1,L11},{L1,L13},{L1,L14},{L1,L15}, {L2,L3},{L2,L4},{L2,L5},{L2,L6},{L2,L7}, {L2,L8},{L2,L10},{L2,L11},{L2,L15}, {L3,L4},{L3,L5},{L3,L7},{L3,L9},{L3,L10}, {L3,L12},{L3,L13},{L3,L14},{L3,L15}, {L4,L6},{L4,L8},{L4,L9},{L4,L11},{L4,L12},{L4,L13},{L4,L14},{L4,L15}, {L5,L7},{L5,L8},{L5,L11},{L5,L14},{L5,L15}, {L6,L7},{L6,L8},{L6,L9},{L6,L11},{L6,L13},{L6,L14},{L6,L15}, {L7,L9},{L7,L10},{L7,L11},{L7,L13},{L7,L14},{L7,L15}, {L8,L9},{L8,L10},{L8,L11},{L8,L12},{L8,L14},{L8,L15}, {L9,L10},{L9,L11},{L9,L12},{L9,L13},{L9,L14},{L9,L15}, {L10,L11},{L10,L14},{L10,L15}, {L11,L12},{L11,L13},{L11,L15}, {L12,L13},{L12,L15}, {L13,L14},{L13,L15}, {L14,L15}(1) To see that each above set N:={Li,Lj}is non-separable, we make use of Lemma 2 as follows. If Li,Lj= L15, we have that Liand Ljare contained in W1.\W2.. Pick a set of states A⊆Li∪Lj\(Li∩Lj)of minimum total population such that W1:= A∪(Li∩Lj)is contained in W3.⊆W. For all above pairs it can be checked that W2:= (Li∪Lj)\Ais contained in W1.∩W2.⊆W. By construction, Nand W∗:={W1,W2}satisfy the assumptions of Lemma 2and hence Nis indeed non-separable. Otherwise, we may assume that Lj=L15. For all above pairs, exchanging the two members with the least population in Li\L15 with the member of largest population in L15\Li, results in two winning sets W1,W2.Again,Nand W∗:={W1,W2}satisfy the assumptions of Lemma 2, implying that Nis non-separable. 123 Improved lower bound on the dimension of the EU council’s… 1299 Moreover, the following 3-element subsets of losing coalitions are also nonseparable. {L1,L2,L12},{L1,L4,L7},{L1,L6,L12},{L4,L5,L10},{L5,L10,L12}(2) To see that these sets are non-separable, consider the following sets of winning coalitions. W1:=M\{3,7,8,9,10,11,12,15}W2:=M\{1,2,3} W3:=M\{1,2,7,14}W4:=M\{3,4,7,8,9} W5:=M\{1,8,9,10,11,12,14,15}W6:=M\{1,3,8,9} W7:=M\{2,6,7,8,13}W8:=M\{1,7,8,9,12,13,14} W9:=M\{1,3,10,11}W10:=M\{1,2,4} W11:=M\{3,4,7,9,13,14}W12:=M\{1,7,10,11,13,14,17,18} Observing that the pairs ({W2,W7,W11},{L1,L2,L12}), ({W3,W10,W12},{L1,L4,L7}), ({W4,W8,W10},{L1,L6,L12}), ({W2,W5,W9},{L4,L5,L10}), and ({W1,W2,W6},{L5,L10,L12}) satisfy the assumptions of Lemma 2, we see that the sets in (2) are indeed nonseparable. In the next section, we show that the non-separable sets in (1) and (2) do not admit a 7-cover. Recall that this implies that the dimension must be at least 8 by Lemma 1. 4 Proof that no 7-Cover can exist For the sake of contradiction, let us assume that the non-separable sets in (1) and (2) admit a 7-cover. This implies that there exist sets L1,...,L7⊆{L1,...,L15}such that (i) each Ljis an inclusion-wise maximal subset of {L1,...,L15}that does not contain any of the sets in (1) and (2), and (ii) L1∪···∪L7={L1,...,L15}. It can be easily verified that the only sets satisfying (i) are the following. {L1,L2},{L1,L3,L6},{L1,L4},{L1,L7,L12},{L2,L9},{L2,L12,L14},{L2,L13}, {L3,L8},{L3,L11},{L4,L5},{L4,L7},{L4,L10},{L5,L6,L10},{L5,L6,L12}, {L5,L9},{L5,L10,L13},{L6,L10,L12},{L7,L8},{L8,L13},{L11,L14},{L15}(3) 123 1300 S. Kober, S. Weltge In what follows, for a weight-vector w=(w1,...,w 15)∈R15, let us define the weight of a set L⊆{L1,...,L15}as w(L):= i:Li∈Lwi. Suppose first that none of the sets L1,...,L7is equal to {L1,L3,L6}. In this case, consider the weight-vector w=(1 /2,0,1,1 /2,0,1,1 /2,0,1,0,0,0,1,1,1) and observe that the weight of each set in (3) that is distinct from {L1,L3,L6}is at most 1. Thus, the weight of each set L1,...,L7is at most 1, and we obtain 7<15 2=w({L1,...,L15})=w(L1∪···∪L7)≤w(L1)+···+w(L7)≤7, a contradiction. It remains to consider the case that one of the sets L1,...,L7is equal to {L1,L3,L6},sayL1. Consider the weight-vector w=(0,1 /3,0,2 /3,1 /3,0,1 /3,2 /3,2 /3,1 /3,1,2 /3,1 /3,0,1) and observe that the weight of each set in (3) is at most 1, and that w(L1)=0. Thus, we have 6<19 3=w({L1,...,L15})=w(L1∪···∪L7)≤w(L2)+···+w(L7)≤6, another contradiction. This completes our proof. 5 Comments on the approach As mentioned in Sect. 1, the dimension of WEU is equal to the chromatic number of a hypergraph that is formed by all losing coalitions. Actually, it is sufficient to consider the subgraph that is induced by maximally losing coalitions. Unfortunately, this subgraph still contains 270,179 nodes and determining its chromatic number seems computationally intractable. However, in order to obtain a lower bound on the chromatic number one may consider any smaller subgraph. Natural candidates for small subgraphs with a large chromatic number are subgraphs with many hyperedges of small cardinality. Kurz and Napel [11] considered the simple subgraph induced by L∗, which consists of all losing coalitions Lsuch that |L|∈{23,24}or L=L15. Note that our losing coalitions L1,...,L15 all belong to L∗. In fact, this subgraph contains many edges: If a coalition Lwith |L|∈{23,24}is losing, then its population is below 65% of the total EU population. For two such losing coalitions it is quite likely that exchanging a member with a high population against some members with a small population results in two winning coalitions. In this case the losing coalitions share an edge (see Lemma 2). In a similar manner, it is easy to see that L15 is adjacent to every other coalition in L∗. 123