Representations of political power structures by strategically stable game forms: A survey

Peleg, Bezalel; Holzman, Ron Article Representations of political power structures by strategically stable game forms: A survey Games Provided in Cooperation with: MDPI – Multidisciplinary Digital Publishing Institute, Basel Suggested Citation: Peleg, Bezalel; Holzman, Ron (2017) : Representations of political power structures by strategically stable game forms: A survey, Games, ISSN 2073-4336, MDPI, Basel, Vol. 8, Iss. 4, pp. 1-17, https://doi.org/10.3390/g8040046 This Version is available at: https://hdl.handle.net/10419/179156 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/ games Review Representations of Political Power Structures by Strategically Stable Game Forms: A Survey Bezalel Peleg 1,* and Ron Holzman 2 1Institute of Mathematics and Center for the Study of Rationality, The Hebrew University of Jerusalem, 91904 Jerusalem, Israel 2Department of Mathematics, Technion-Israel Institute of Technology, 32000 Haifa, Israel; [email protected] *Correspondence: [email protected]; Tel.: +972-2-658-4134 Received: 1 September 2017; Accepted: 17 October 2017; Published: 23 October 2017 Abstract: We survey the results on representations of committees and constitutions by game forms that possess some kind of equilibrium strategies for each profile of preferences of the players. The survey is restricted to discrete models, that is, we deal with finitely many players and alternatives. No prior knowledge of social choice is assumed: As far as definitions are concerned, the paper is self-contained. Section 2 supplies the necessary general tools for the rest of the paper. Each definition is followed by a simple (but nontrivial) example. In Section 3 we give a complete account of representations of committees (proper and monotonic simple games), by exactly and strongly consistent social choice functions. We start with Peleg’s representations of weak games, and then provide a complete and detailed account of Holzman’s solution of the representation problem for simple games without veto players. In Section 4 we deal with representations of constitutions by game forms. Following Gärdenfors we model a constitution by a monotonic and superadditive effectivity function. We fully characterize the representations for three kinds of equilibrium: Nash equilibrium; acceptable equilibrium (Pareto optimal Nash equilibrium); and strong Nash equilibrium. We conclude in Section 5 with a report on two recent works on representations of constitutions under incomplete information. Keywords: committee; simple game; constitution; effectivity function; representation; game form; social choice function; equilibrium; incomplete information 1. Introduction In this paper we survey results on two kinds of power distributions: committees and constitutions. Committees are well known and appear in many applications (constitutions will be discussed later). For example, every town council is a committee, the UN Security council is a committee, etc. For a recent and comprehensive study of committees the reader is referred to Taylor and Zwicker [ 1 ]. The founder of the modern theory of committees is L.S. Shapley (see, e.g., [ 2 ]). Formally, a committee is a proper and monotonic simple game. The usual task of the members of a committee Gis to choose one alternative out of a set Aof alternatives. Thus, we deal with choice problems (G, A). The working of a committee may be quite complex and include several stages. We focus on the voting stage which occurs after the members of Ghave formed their preferences on A. Our idea is to construct a social choice function that associates with every profile of (linear) preferences of the voters an alternative in Asuch that the following properties are satisfied: (1) The power structure induced by the social choice function coincides with the original G. (2) The outcome of the social choice function belongs to the set of outcomes of strong Nash equilibria of the voting game (for every profile of linear preferences). Condition (2) implies, by well-known results, that the result of the voting, according to our social Games 2017,8, 46; doi:10.3390/g8040046 www.mdpi.com/journal/games Games 2017,8, 46 2 of 17 choice function, is in the (beta) core of the voting game (for each profile). Thus, our voting rules enjoy the strongest possible type of stability. In Section 3we survey our construction of social choice functions for all committees. The first step was taken by Peleg [ 3 ] who dealt (mainly) with weak games (games with veto players). Our methods can handle any number of alternatives for such games. Holzman, in two lucid but highly technical papers [ 4 , 5 ], succeeded in giving a complete solution to the strong representation problem of committees without vetoers (a strong representation of a committee is, roughly, a voting rule satisfying (1) and (2)). He determined the entire interval of orders of possible strong representations of a committee and, in particular, its maximum—the capacity of the committee. The first (modern) model of a constitution is, as far as we know, Arrow’s social welfare function [ 6 ]. However, because of Arrow’s Impossibility Theorem, we are left only with dictatorial social welfare functions. Thus, as we insist on democratic constitutions, we have used Gärdenfors’ [ 7 ] definition of a constitution. As we explain in Section 4, Gärdenfors’ model is, essentially, a monotonic and superadditive effectivity function (as defined independently by Moulin and Peleg [ 8 ]). Given a (monotonic and superadditive) effectivity function we enquire whether there exists a game form such that: (1) Representation: the effectivity function of the game form coincides with the given effectivity function; and (2) Stability: For every profile of the preferences of the citizens the resulting game has a (Pareto optimal) equilibrium point (of a pre-specified type of equilibrium). Criterion (1) guarantees that the members of society (and also groups of members) can exercise their rights simultaneously; (2) guarantees that society is in equilibrium (of some kind). The first question we address in Section 4.1 is the above question with respect to Nash equilibrium. If the effectivity function is monotonic and superadditive then it has a representation by a game form. However, the game form may have no Nash equilibrium for certain profiles of preferences (think about the Gibbard Paradox [ 9 ]). The (necessary and sufficient) condition for stability is quite delicate. It is formulated with respect to the dual effectivity function and it says that rights for individuals should be “weak” (that is, exclude only few social states). For the exact condition, see Theorem 8. In Section 4.2 we consider effectivity functions that may be represented with Pareto optimal Nash equilibria. A game form is acceptable (Hurwicz and Schmeidler [ 10 ]) if it is Nash consistent and all its Nash equilibria are Pareto optimal (for every profile of preferences). An effectivity function is acceptable if it may be represented by an acceptable game form. Acceptable effectivity functions are characterized by the two conditions of Theorem 8 and the following additional condition: Two disjoint coalitions cannot veto the same alternative. We conclude Section 4with representation by strong Nash equilibria. An effectivity function is representable by a strongly consistent game form if, and only if, it is convex and maximal. In the last section, Section 5, we report two recent results on representation of constitutions under incomplete information. Also, we devote the final section to concluding remarks. The reader may find it interesting to read our remarks on the relationship between our results and the major paradoxes of social choice theory. We close the introduction with the following important remark. This survey covers only finite problems of representations: finitely many players and social alternatives. This allows the use of discrete mathematics. There are quite a few studies with a topological or measure space of alternatives. These studies may be relevant in particular cases. The interested reader is referred to Peleg and Peters [11]. 2. Preliminaries Let Nbe a set of nplayers (also voters or agents), and let Abe a set of moutcomes (also alternatives or social states). We shall assume that Nand Aare finite and m, n ≥2. Games 2017,8, 46 3 of 17 Definition 1. Agame form (GF) is a list Γ = (N; S 1 , . . . , S n ; ∏ ; A), where N and A are as above; S i is a nonempty set, the (finite) set of strategies of player i ε N; and ∏ : S 1×. . . × S n→ A is the (surjective) outcome function. We shall now give an example of a GF. Example 1. Let N ={1, 2, 3} and let A ={a, b, c}.Further, let S 1 ={2, 3} and S 2 =S 3 =A. Finally, we define the outcome function ∏ as follows: ∏ (2, x, y) = x, and ∏ (3, x, y) = y, for all x, y ε A. This is a kingmaker GF: Player 1, the kingmaker, chooses the king of the day from {2, 3},and the chosen king may pick any alternative from A. As we shall see, this example has some nice properties. It is due to Hurwicz and Schmeidler [10]. Let Γ = (N; S 1 , . . . , S n ; ∏ ; A) be a GF. Usually the players have some preferences over the outcomes, that is, the members of A. The GF together with the preferences of the players define an (ordinal) n-person game in strategic form. We shall now make these remarks precise. Definition 2. Let A be a set of alternatives and let R be a binary relation on A. R is complete if for all x, y ε A, xRyoryRx.Ristransitive if for all x, y, z ε A, if x R y and y R z, then x R z. R is a weak order if R is complete and transitive. Let Abe a set of alternatives. We denote by K(A) = K the set of all weak orders on A. If Xand Y are finite sets, then we denote by X Y the set of all functions from Yto X. Finally, if Γ is a GF and R N ε K N ,then g( Γ , R N )denotes the n-person ordinal game in strategic form induced by the pair ( Γ , R N ). We are now able to define Nash equilibrium of ordinal strategic games. Definition 3. Let Γ = (N; S 1 , . . . , S n ; ∏ ; A) be a GF and let R Nε K N be a profile of preferences (i.e., weak orders) of the players. s Nε S N is a Nash equilibrium (NE) of the game g( Γ , R N ) if, for every player i, we have ∏ (s N ) Ri ∏ (ti, sN\i), for all tiεSi. Remark 1. Let Γ0 be the GF of Example 1. Then the game g( Γ0 , R N ) has an NE for every R Nε K N . Indeed, let R Nε K N and let each of the players 2 and 3 choose a best alternative. Then player 1 can choose a player whose chosen alternative maximizes his preference. The resulting triple of strategies is an NE. Let Abe a set of alternatives, let RεK(A), and let x, y εA. We denote xIyif xRyand yRx; and (1) xPyif xRyand not y R x. (2) The foregoing notations enable us to proceed with the following definition. Definition 4. Let A be a set of alternatives, let N be a set of players, and let R Nε K N (A). An alternative x ε A is Pareto optimal (PO) with respect to RNif there exists no y εA such that y Pix for all i εN. Remark 2. Every NE outcome for Γ0is PO (see Example 1 and Remark 1). In most political games communication is possible; consider, for example, parliaments and committees. This implies that coordination of strategies among members of coalitions is possible. In such situations, NEs can be upset by coalitions of players. This leads us to consider more robust concepts of equilibrium. We proceed with the following definition. Games 2017,8, 46 4 of 17 Definition 5. Let Γ = (N; S 1 , . . . , S n ; ∏ ; A) be a GF and let R Nε K N . An n-tuple of strategies s N is a strong NE (SNE) of the ordinal game g( Γ , R N ) if for every nonempty subset T of N, and for every q Tε S T , there exists hεT such that ∏ (sN) Rh ∏ (qT, sN\T). Example 2. Let Γ0 be the GF of Example 1 and let R 1 = (a, b, c), R 2 = (b, c, a), and R 3 = (c, a, b). Then, as the reader may easily check, the game g(Γ0, RN) has no SNE. This is the Condorcet Paradox. We shall now proceed to construct a GF that has an SNE for every profile of preferences. We start with a definition. Definition 6. Let A be a set of alternatives and let R be a weak order. R is a linear order if for all x, y ε A, x I y if, and only if, x = y. Let Abe a set of alternatives. We denote by L = L(A) the set of all linear orders of A. Definition 7. Let A be a set of alternatives and let N be a set of voters. A social choice function (SCF) is a function F: LN→A. Clearly, every SCF is a GF. We shall now give an example of an SCF that has an SNE for each profile of linear preferences. Example 3. (Sequential sincere vetoing) Let A be a set of m alternatives and let N be a set of n voters, m = n + 1. Let R Nε L N . We shall define F(R N ) in n steps. In the first step player 1 vetoes his last (i.e., worst) alternative. Denote the vetoed alternative by x 1 . Now R 1 and x 1 are removed. We are left with the profile R N\1| (A \ {x 1 }). At this point, player 2 vetoes his worst alternative x 2 and the first step is repeated with respect to the second (restricted) profile, and so on. There is precisely one alternative x that is not vetoed, and we define F(R N ) = x. We claim that x is an SNE outcome of the game g(F, R N ). Let Q Nε L N satisfy that the bottom alternative of Q i is x i for i = 1, . . . , n. Obviously, F(Q N ) = x. We claim that Q N is an SNE in g(F, R N ). Assume, on the contrary, that there exists a nonempty subset T of N and P Tε L T such that F(Q N\T , P T )=x j for some j ε N, and x j R i x for all i ε T. Then j is not in T because x R j x j . Hence, x j is blocked at (Q N\T , P T ), which is impossible. The reader may also prove that games g(F, R N ) = ((N; L, . . . , L; F; A), R N ), where R Nε K N (A), have SNEs (see also Section 7.4 in Peleg [12]). Von Neumann and Morgenstern [ 13 ] associated with every strategic game with side payments a coalitional game (also with side payments). They relied on the maxmin principle for correlated strategies (for coalitions) in their definitions. A large part of their book is devoted to the analysis of coalitional games. An axiomatic theory of coalitional games without side payments (NTU games) was introduced by Aumann and Peleg [ 14 ]. We are now going to follow this tradition and define coalitional functions for GFs. We start with the following definition. Definition 8. Let Γ = (N; S ! , . . . , S n ; slantbox ∏ ; A) be a GF, let T be a nonempty subset of N, and let B be a nonempty subset of A. T is effective for B if there exists s Tε S T such that ∏ (s T , q N\T ) ε B for all q N\Tε S N\T . For the continuation of our discussion of effectiveness we need the following notations. Let Dbe a nonempty finite set. We denote: P(D) = {D’:D’ is a subset of D} and P 0 (D) = {D’: D’ is a nonempty subset of D}. Also, | D | denotes the number of elements of D. Finally, if Bis a subset of D, then B + = {B’: B’ contains Band is contained in D}. Definition 9. Let Γ = (N; S 1 , . . . , S n ; ∏ ; A) be a GF. The effectivity function (EF) of Γ , E Γ : P 0 (N) → P(P0(A)), is defined by EΓ(T) = {B: T is effective for B}, for all T εP0(N). Games 2017,8, 46 5 of 17 Definition 9 is due to Moulin and Peleg [ 8 ]. As the reader may check, the EF E 0 of the GF Γ0 of Example 1 is given by: E 0 (T) = {A} if | T | ≤ 1, and E 0 (T) = P 0 (A) if | T | ≥ 2. The reader may also compute the EF E 1 of Example 3. Indeed, if Tis a nonempty subset of N, then B ε E 1 (T) if, and only if, |B| ≥ m− |T|. Definition 9 leads us to consider general EFs, that is, EFs that are not necessarily derived from GFs. For example, a TU coalitional game is superadditive if, and only if, it is derived from a (TU) game in strategic form. Thus, as we consider TU games that are not superadditive, we shall also consider general EFs. Definition 10. Let N be a set of players and let A be a set of alternatives. An effectivity function (EF) is a function E: P0(N) →P(P0(A)) that satisfies (1) A εE(T) for all T εP0(N); and (2) E(N) = P0(A). Let Γ be a GF. Then E Γ satisfies (1) of the last definition. It satisfies (2) if, and only if, its outcome function is surjective. However, EΓis monotonic and superadditive. That is: If BεEΓ(T) and B’ contains B, then B’ εEΓ(T). (Monotonicity) (3) If BjεEΓ(Tj), j = 1, 2, and T1∩T2=∅,then B1∩B2εEΓ(T1∪T2).(Superadditivity) (4) Equations (3) and (4) follow from Definition 9. One of the central solutions of coalitional games is the core. We shall now define the core, as was done in [8], for EFs. Definition 11. Let E be an EF and let R Nε K N . Further, let T ⊂ N, let B ε E(T), and let x ε A \ B. B dominates x via T at R N if b P h x for all h ε T and b ε B. x is dominated at R N if there exist T ⊂ N and B ε E(T) such that B dominates x via T at RN. The core of E and RN, C(E, RN), is the set of all undominated alternatives at RN. The core of an EF may be empty for some preference profiles. (The reader may consider, for example, Example 2.) However, there is an interesting connection between cores of EFs and SNEs of GFs. Theorem 1. Let Γ = (N; S 1 , . . . , S n ; ∏ ; A) be a GF, and let R Nε K N be a profile of preferences. If s N is an SNE of the game g(Γ, RN), then ∏ (sN)εC(EΓ, RN). See Aumann [ 15 ] for a discussion of this connection in another context, and Section 4.1 in Peleg [ 12 ] for a proof of a similar result. Theorem 1 has multiple applications in Sections 3and 4. 3. Representations of Simple Games Let Nbe a set of nplayers, n ≥ 2, and let Abe a set of malternatives, m ≥ 2. We assume in the sequel that all SCFs are surjective. Definition 12. An SCF F: L N→ A is exactly and strongly consistent (ESC) if for every R Nε L N there exists an SNE QNof the game g(F, RN) such that F(RN) = F(QN). The SCF of Example 3 is an ESC SCF. In this part we shall look for ESC SCFs that may serve as voting procedures to committees. We shall soon make the connection to committees, that is, (monotonic and proper) simple games. However, we first remark the following fact. Remark 3. Let F be an ESC SCF. Then, for every RNεLN, F(RN) is in the core C(EF, RN). Thus, if Fis exactly and strongly consistent, then sincere voting itself leads to a (coalitionally) stable outcome! (See Theorem 1.) We now connect simple games and SCFs. Games 2017,8, 46 6 of 17 Definition 13. Asimple game is a pair G = (N, W) where N is a set of players and W is a (nonempty) set of coalitions (that is, nonempty subsets of N). The members of W are called winning coalitions. We always assume that a superset of a winning set is winning (monotonicity), and that the complement of a winning set is losing (that is, not winning) (properness). G = (N, W) is symmetric if winning depends only on the number of players: T εW if, and only if, |T| ≥q. In this case we write G = (n, q). We now associate with every SCF a simple game G*(F) = (N, W*(F)) by defining: W*(F) = {T: E F (T) = P 0 (A)}. For example, the simple game in Example 3 is the unanimity game (n, n) = (N, {N}). We are now ready for the central definition of this section. Definition 14. Let G = (N, W) be a (proper and monotonic) simple game and let A be a set of (at least two) alternatives. An SCF F: LN→A is a strong representation of G if G*(F) = G; and (5) F is exactly and strongly consistent. (6) |A|is called the order of the strong representation F. There are some simple desirable properties of strong representations. The first that we shall consider is the monotonicity of the representing SCF. Definition 15. An SCF F: L N→ A is monotonic if for all R Nε L N , h ε N, and x ε A, if F(R N ) = x and Q N is obtained from R N by moving x one place up in R h and leaving all other preferences unchanged, then F(Q N ) = x. For example, the SCF of Example 3 is monotonic. Another natural assumption is that the simple game and the representing SCF have the same symmetries. We shall soon make this idea precise, however we first reconsider the SCF Fof Example 3. For G*(F) = (n, n) every permutation of the players is a symmetry, whereas Fitself has no symmetries except the identity. Definition 16. Let F: L N→ A be an SCF, let G = (N, W) be a simple game, and let t be a permutation of N. t is asymmetry of F if F(R 1 , . . . , R n ) = F(R t(1) , . . . , R t(n) ) for all R Nε L N . t is a symmetry of G if for all U ε W, t(U) = {t(h): h ε U} ε W. We denote by sym(F) (sym(G)) the set of all symmetries of F (G). F is faithful if sym(F) = sym(G*(F)). We need one more definition in order to formulate our first representation theorem. Definition 17. Let G = (N, W) be a (proper and monotonic) simple game. G is weak if V = ∩ {S: S ε W} 6=∅ . V is the set of veto players of G. Theorem 2. Every weak game has a monotonic and faithful strong representation of every order greater than or equal to 2. We shall now illustrate Theorem 2 for a “simple” weak game. First, we need a definition. Definition 18. A simple game G = (N, W) is a weighted majority game if there exist non-negative numbers w 1 , . . . , w n and a positive number q such that for all T ε P 0 (N), T ε W if, and only if, ∑hεT w h≥ q. (Notation: G = [q; w1,. . ., wn].) Games 2017,8, 46 7 of 17 Example 4. Let G = [3; 2, 1, 1].Then player 1 is a veto player and G is weak. Let A be a set of m alternatives, m ≥ 2, and let b ε A. We now define an SCF F that will strongly represent G. Let R Nε L N where N = {1, 2, 3}. We denote R1= (x(1), x(2), . . ., x(m)). Our construction is given by the following rules: If b 6=x(1), then F(RN) = x(1). (7) If b = x(1) and {h: b Rhx(2)} is winning (in G), then F(RN) = b. (8) If b = x(1) and x(2) R2b and x(2) R3b, then F(RN) = x(2). (9) The reader is invited to check that G*(F) = G and that the transposition (2, 3) is a symmetry of F. We now introduce an additional notation. For R ε L we denote by t k (R) the k-th alternative in the order R. Thus, t 1 (R) is the top alternative in the order R; t2(R) is the second alternative in the order R, and so on. Let R Nε L N and denote as above R 1 = (x(1), x(2), . . . , x(m)). In cases (7) or (8), R N itself is an SNE of g(F, R N ). In case (9) let Q Nε L N satisfy t 1 (Q h ) = x(2) and t m (Q h ) = x(1) for all h ε N. Then F(Q N ) = x(2) and QNis an SNE (only b might dominate x(2); however, this is blocked by {2, 3}). From now on, we consider a (proper and monotonic) simple game G = (N, W) which is not weak, that is, V = ∩ {S: S ε W} = ∅ . While a monotonic and faithful strong representation of order 2still exists, strong representations of higher orders need not exist. A simple way to see that the orders of strong representations are bounded in this case is based on the following definition and remark. Definition 19. Let G = (N, W) be a non-weak simple game. The Nakamura number of G, denoted ν (G), is the least k for which there exist k winning coalitions S1,. . . , Skwith an empty intersection. Remark 4. Let E G be the EF associated with the simple game G = (N, W), i.e., E G (T) = P 0 (A) if T ε W and EG(T) = {A} otherwise. If |A| ≥ν(G) then one can construct RNεLNfor which the core C(EG, RN) is empty. Hence, no strong representation of G of order m ≥ν (G) can exist; indeed, if F were such a representation we would have E G (T) ⊂ E F (T) for all T ε P 0 (N), and therefore C(E F , R N ) ⊂ C(E G , R N ) for all R Nε L N , contradicting Remark 3 for the profile RNfound above. Thus, for a given simple game without veto players, the orders of its strong representations are bounded. This means that such a committee can only handle relatively small sets of alternatives in an exactly and strongly consistent manner. In order to quantify this phenomenon, we introduce the following definition. Definition 20. Let G = (N, W) be a non-weak simple game. The capacity of G, denoted µ (G), is the largest m for which G has a strong representation of order m. By Remark 4 we always have µ (G) < ν (G). Since ν (G) ≤ n(in a non-weak game, one can find for each player a winning coalition not containing him), we conclude that µ(G) ≤n−1. In some natural cases, the limitation is much stricter, as shown in the next remark. Remark 5. Assume that G = (N, W) is not weak, and that the complement of any losing coalition is winning (such games are called strong; they include simple majority games with an odd number of players). Then the reader can check that ν(G) = 3, and therefore µ(G) = 2. On the positive side, there is a way to generalize the idea of sequential vetoing (Example 3 above) so as to obtain a class of exactly and strongly consistent SCFs which allows some flexibility in the allocation of power to coalitions. We proceed to define these voting procedures, in order to use them later as strong representations of simple games, with orders lying in a certain range depending on the game. Games 2017,8, 46 8 of 17 Definition 21. Assume that m ≤ n + 1, and let β : A → {1, . . . , n} satisfy ∑xεAβ (x) = n + 1. The number β (x) is called the blocking coefficient of x, intended as the number of voters required to block the alternative x (in Example 3 we had β (x) = 1 for all x ε A). The effectivity function E β associated with β is defined by: B ε E β (T) if, and only if, |T| ≥∑xεA\Bβ(x). An SCF F: LN→A is an Eβ–core selection if F(RN)εC(Eβ, RN) for all RNεLN. Remark 6. A different but equivalent way to obtain the SCFs in the above definition is to consider feasible elimination procedures with respect to β , as introduced by Peleg [ 16 ]. Roughly speaking, given R Nε L N , one allows sequential vetoing as in Example 3, but at each stage an alternative x i is vetoed by β (x i ) voters who consider it the worst among the remaining alternatives, ending with one surviving alternative. It can be proved that the set of surviving alternatives corresponding to all possible orders of elimination is precisely C(Eβ, RN). This shows in particular that C(Eβ, RN)6=∅for all RNεLN, and thus guarantees the existence of an Eβ–core selection. The following facts about E β –core selections are based mostly on Peleg [ 16 ], Oren [ 17 ], and Polishchuk [18]. Theorem 3. Let β: A →{1, . . . , n} satisfy ∑xεAβ(x) = n + 1. Then: (a) For every Eβ–core selection F, we have EF= Eβ. (b) Every Eβ–core selection F is exactly and strongly consistent. (c) There exists an E β –core selection F which is monotonic and anonymous (i.e., invariant under any permutation of the voters). Example 5. Consider the symmetric simple game G = (5, 4), in other words, a committee of 5 members with full power allocated to coalitions of 4 or more members. If the committee has to choose among 3 alternatives a, b, and c, we can assign the blocking coefficients β (a) = β (b) = β (c) = 2. Then B ε E β (T) if, and only if, |T| ≥ 2|A \ B|, meaning that any two players can block an alternative, but it takes four players to enforce an alternative. The latter agrees with the initially given allocation of power in G = (5, 4). Let R Nε L N be given by: R 1 = (a, b, c), R 2 = (a, c, b), R 3 = R 4 = (b, c, a), and R 5 = (c, b, a). Then {b, c} dominates a via {3, 4, 5}, while b and c are undominated, and so C(E β , R N ) = {b, c}. Thus, an E β –core selection F gives either F(R N ) = b or F(R N ) = c. In the former case, a Q N having t 3 (Q 1 ) = t 3 (Q 3 ) = c and t 3 (Q 4 ) = t 3 (Q 5 ) = a is an SNE of g(F, R N ) with F(Q N ) = F(R N ). In the latter case, a Q N having t 3 (Q 2 )=t 3 (Q 5 ) = b and t 3 (Q 3 )=t 3 (Q 4 ) = a is an SNE of g(F, R N ) with F(Q N ) = F(R N ). Similar constructions yield exact SNEs for any RNεLN, confirming that F is ESC. Thus, F provides a strong representation of G = (5, 4) of order 3. We are now ready to state the following theorem, which fully describes the faithful strong representations of symmetric, non-weak simple games. Theorem 4. Let G = (n, q) be a (proper) symmetric, non-weak simple game, i.e., n 2< q < n. Then: (a) µ(G) = bn+1 n−q+1c, where b c denotes the integer part. (b) For every 2 ≤m≤ b n+1 n−q+1c,there exists a monotonic and faithful strong representation of G of order m. (c) For every 2 ≤ m ≤ b n+1 n−q+1c ,an SCF F: L N→ A is a faithful strong representation of G of order m if, and only if, F is an anonymous E β –core selection for some β : A → {n–q+1, . . . , n} satisfying ∑xεAβ(x) = n + 1 and minxεAβ(x) = n −q + 1. One direction of part (c), namely the fact that E β –core selections with the appropriate blocking coefficients β ( · )yield strong representations of G, follows directly from Theorem 3. This also confirms part (b) and the inequality µ (G) ≥ b n+1 n−q+1c in part (a), because the condition 2 ≤ m ≤ b n+1 n−q+1c allows Games 2017,8, 46 15 of 17 A DS defines a social choice correspondence (SCC) H: K N× T → P 0 (A) by H(R N , t) = {x: d(x; R N , t) > 0}. With the SCC Hwe associate an EF E H in a way that generalizes Definitions 8 and 9: A set Q ε P 0 (N) is effective for B ε P 0 (A) if there exist R Qε K Q and t Qε T Q such that H((R Q , R N\Q ), (t Q , t N\Q )) ⊂ B for all R N\Qε K N\Q and t N\Qε T N\Q . Finally, E H (Q) = {B: Q is effective for B} for all Q ε P 0 (N). The EF of d, Ed,is defined by Ed= EH, and dis a representation of Eif Ed= E. The (von Neumann–Morgenstern) payoff functions of the players are given by u h : A × T → Re, for all h ε N. We are now able to describe the game with incomplete information confronted by the players: M = (N;K, . . . , K; T 1 , . . . , T n ; p 1 , . . . , p n ; u 1 , . . . , u n ; d) where all the components have already been defined. Now a (pure) strategy of player his a function s h : T h→ K × T h (for all h ε N). The payoff to type thεThwhen an n-tuple of strategies s = (s1,. . ., sn)is used is Uh(s|th) = ∑ph(t −h|th)∑xεAuh(x, t) d(x; s1(t1), . . ., sn(tn)), where the outer summation is over all th εTN\h.(19) An n-tuple of strategies s = (s 1 , . . . , s n )is a Bayesian Nash equilibrium (BNE) of Mif for all h ε N, t hε Th, and (Rh, t*h)εK×Thwe have Uh(s|th)≥∑ph(t −h|th)∑xεAuh(x, t) d(x; s −h(t −h), (Rh, t*h)), where, again, the outer summation is over all th εTN\h.(C) The main result on representation under incomplete information is the following. Theorem 14. Let E: P 0 (N) → P(P 0 (A)) be a monotonic and superadditive EF, let (T 1 , . . . , T n ; p 1 , . . . , p n ) be an information structure, and let u 1 , . . . , u n be vNM utilities for the players. Then there exists a decision scheme d: KN×T→∆(A) such that (1) d is a representation of E (E = Ed); and (2) the Bayesian game M = (N; K, . . . , K; T 1 , . . . , T n ; p 1 , . . . , p n ; u 1 , . . . , u n ; d) has a Bayesian Nash equilibrium in pure strategies. The proof uses the concept of the uniform core of an EF. Abdou and Keiding [ 23 ] proved that the uniform core of a monotonic and superadditive EF is nonempty. Keiding and Peleg [ 24 ] showed that the uniform core correspondence is a representation of its EF. For a recent lucid discussion of the uniform core the reader is referred to Section 6.4 of [11]. Theorem 14 is due to Peleg and Zamir [25]. Peters, Schröder, and Vermeulen [ 26 ] deal also with representations of constitutions under incomplete information. They make the special assumption of private values (the utility function of a player depends only on his type) and prove existence of ex-post NEs. 5.2. Concluding Remarks In this survey we do not attempt to give an historical account of (the old branch of science of) social choice. We also do not assume any formal knowledge of social choice. We address ourselves to the reader who knows the details of (the formulation of) Arrow’s Impossibility Theorem and the Gibbard–Satterthwaite Theorem (and perhaps has also heard about Sen’s Liberal Paradox), and is more or less convinced that social choice theory is the land of impossibilities or, at least, of second-best solutions. Proofs of the Arrow Impossibility Theorem (AIT) and the Gibbard–Satterthwaite (G-S) Theorem are nowadays abundant; indeed, almost every new book on game theory contains detailed proofs (see, e.g., Peters [ 27 ] and Maschler, Solan, and Zamir [ 28 ]). But, of course, we shall give a precise formulation of both AIT and G-S in this section and indicate how the foregoing text may resolve some difficulties that they raise. We know that this sounds very ambitious, and indeed the solutions that we offered are conceptually and mathematically somewhat sophisticated. However, for finitely many alternatives and voters, as in our text, everything is “elementary and constructive”. Our main tool Games 2017,8, 46 16 of 17 is the axiomatic method as has been advanced by Arrow. Characterizing our solutions axiomatically gives the reader the possibility to judge clearly what options are available to remove difficulties. We start our discussion with the G-S Theorem. We shall discuss its implications for social choice functions (see Definition 7). (We assume that the reader is familiar with the context of the G-S Theorem; otherwise, we direct them to the relevant definitions in Section 2). Let, as usual, Abe a set of at least three alternatives and let Nbe a set of at least two voters. Let F: L N→ Abe an SCF and let R N be a profile of linear preferences. Fis nonmanipulable at R N if R N itself is a Nash equilibrium of the voting game g(F, R N )generated by Fand R N . F is nonmanipulable if it is nonmanipulable at every profile of linear preferences. Fis dictatorial if there exists a player d, a dictator, such that F(R N ) R d xfor all R N and for all xin the range of F. The G-S Theorem [ 29 , 30 ] says that if an SCF is nonmanipulable and its range contains at least three alternatives, then it is dictatorial. We have seen above that there do exist non-dictatorial and even anonymous SCFs, which are exactly and strongly consistent (see Definition 12). In what sense does the use of such SCFs offer a solution to the manipulability problem? Let F: L N→ Abe an ESC SCF. For R N in L N let H(R N )be the set of all SNEs with outcome F(R N ). This set is nonempty by the definition of ESC. All the players are indifferent between the points of H(R N ). Let h(R N )be an arbitrary selection from H( · )known to all players (the games g(F, · )are “noncooperative” in the sense that communication and correlation of strategies are possible, but not binding agreements). The rule “play h t (R N )when R N is the sincere profile”, tin N, is self-enforcing in the sense that no coalition has a profitable deviation. Thus, although the rule “vote sincerely” is manipulable by G-S, we have found a different, more sophisticated rule of voting behavior, which cannot be manipulated and still yields the sincere outcome. Another interpretation of the merits of using an ESC SCF is that it allows the punishment of manipulators, thus making the sincere profile an equilibrium of threats (see Pattanaik [31] and Section 8.5 in [11]). We now recall Arrow’s Impossibility Theorem (AIT). A social welfare function (SWF) is a function V: L N→ L. V is Paretian if for all R Nε L N and all x, y ε A, the condition x R h yfor all h ε Nimplies that x V(R N ) y.Vsatisfies Independence of Irrelevant Alternatives (IIA) if for all R N , Q Nε L N and all x, y ε A, the condition x R h yif, and only if, x Q h yfor all h ε Nimplies that x V(R N ) y if, and only if, x V(Q N ) y. V is dictatorial if there exists a voter dsuch that V(R N ) = R d for all R Nε L N . AIT [ 6 , 32 ] says that if Vis Paretian and satisfies IIA, then Vis dictatorial (we have assumed that there are at least three alternatives). If we follow Arrow and define a constitution as a “well-behaved” SWF, then we are left only with dictatorial constitutions. However, we have followed Gärdenfors [ 7 ] in Section 4and found stable “nice” constitutions. In our model, all the citizens may exercise their rights precisely as specified by the (relevant) constitution. We conclude this section with the remark that there are still many open problems in the theory of representations of political power structures by stable GFs. For example, we have not succeeded to examine representations by coalition-proof Nash equilibrium. Also, there is urgent need to investigate dynamic models of representation. Conflicts of Interest: The authors declare no conflict of interest. References 1. Taylor, A.D.; Zwicker, W.S. Simple Games: Desirability Relations, Trading, Pseudoweightings; Princeton University Press: Princeton, NJ, USA, 1999. 2. Shapley, L.S. Simple games: An outline of the descriptive theory. Behav. Sci. 1962 ,7, 59–66. [CrossRef] [PubMed] 3. Peleg, B. Representation of simple games by social choice functions. Int. J. Game Theory 1978 ,7, 81–94. [CrossRef] 4. Holzman, R. On strong representations of games by social choice functions. J. Math. Econ. 1986 ,15, 39–57. [CrossRef] 5. Holzman, R. The capacity of a committee. Math. Soc. Sci. 1986,12, 139–157. [CrossRef] 6. Arrow, K.J. Social Choice and Individual Values; Wiley: New York, NY, USA, 1963. Games 2017,8, 46 17 of 17 7. Gärdenfors, P. Rights, games and social choice. Noûs 1981,15, 341–356. [CrossRef] 8. Moulin, H.; Peleg, B. Cores of effectivity functions and implementation theory. J. Math. Econ. 1982 ,10, 115–145. [CrossRef] 9. Gibbard, A. A Pareto-consistent libertarian claim. J. Econ. Theory 1974,7, 388–410. [CrossRef] 10. Hurwicz, L.; Schmeidler, D. Construction of outcome functions guaranteeing existence and Pareto optimality of Nash equilibria. Econometrica 1978,46, 1447–1474. [CrossRef] 11. Peleg, B.; Peters, H. Strategic Social Choice; Springer: Berlin, Germany, 2010. 12. Peleg, B. Game Theoretic Analysis of Voting in Committees; Cambridge University Press: Cambridge, UK, 1984. 13. Von Neumann, J.; Morgenstern, O. Theory of Games and Economic Behavior; Princeton University Press: Princeton, NJ, USA, 1944. 14. Aumann, R.J.; Peleg, B. Von Neumann-Morgenstern solutions to cooperative games without side payments. Bull. Amer. Math. Soc. 1960,66, 173–179. [CrossRef] 15. Aumann, R.J. A survey of cooperative games without side payments. In Essays in Mathematical Economics; Shubik, M., Ed.; Princeton University Press: Princeton, NJ, USA, 1967; pp. 3–27. 16. Peleg, B. Consistent voting systems. Econometrica 1978,46, 153–161. [CrossRef] 17. Oren, I. The structure of exactly strongly consistent social choice functions. J. Math. Econ. 1981 ,8, 207–220. [CrossRef] 18. Polishchuk, I. Monotonicity and Uniqueness of Consistent Voting Systems; Center for Research in Mathematical Economics and Game Theory, Hebrew University of Jerusalem: Israel, Jerusalem, 1978. 19. Peleg, B. Effectivity functions, game forms, games, and rights. Soc. Choice Welf. 1998,15, 67–80. [CrossRef] 20. Peleg, B.; Peters, H.; Storcken, T. Nash consistent representation of constitutions: A reaction to the Gibbard paradox. Math. Soc. Sci. 2002,43, 267–287. [CrossRef] 21. Sen, A.K. The impossibility of a Paretian liberal. J. Polit. Econ. 1970,78, 152–157. [CrossRef] 22. Peleg, B. Representation of effectivity functions by acceptable game forms: A complete characterization. Math. Soc. Sci. 2004,47, 275–287. [CrossRef] 23. Abdou, J.; Keiding, H. Effectivity Functions in Social Choice; Kluwer Academic Publishers: Dordrecht, The Netherlands, 1991. 24. Keiding, H.; Peleg, B. Binary effectivity rules. Rev. Econ. Des. 2006,10, 167–181. [CrossRef] 25. Peleg, B.; Zamir, S. Representation of constitutions under incomplete information. Econ. Theory 2014 ,57, 279–302. [CrossRef] 26. Peters, H.; Schröder, M.; Vermeulen, D. On existence of ex post Nash consistent representation for effectivity functions. Soc. Choice Welf. 2015,45, 287–307. [CrossRef] 27. Peters, H. Game Theory: A Multi-Leveled Approach; Springer: Berlin, Germany, 2008. 28. Maschler, M.; Solan, E.; Zamir, S. Game Theory; Cambridge University Press: Cambridge, UK, 2013. 29. Gibbard, A. Manipulation of voting schemes: A general result. Econometrica 1973,41, 587–602. [CrossRef] 30. Satterthwaite, M. Strategy-proofness and Arrow’s conditions: Existence and correspondence theorems for voting procedures and social welfare functions. J. Econ. Theory 1975,10, 187–217. [CrossRef] 31. Pattanaik, P.K. Counter-threats and strategic manipulation under voting schemes. Rev. Econ. Stud. 1976 ,43, 11–18. [CrossRef] 32. Arrow, K.J. Values and collective decision-making. In Philosophy, Politics and Society; Laslett, P., Runciman, W.G., Eds.; Basil Blackwell: Oxford, UK, 1967. © 2017 by the authors. Licensee MDPI, Basel, Switzerland. This article is an open access article distributed under the terms and conditions of the Creative Commons Attribution (CC BY) license (http://creativecommons.org/licenses/by/4.0/).