Decisions in Economics and Finance
Proper strong-Fibonacci games
--Manuscript
Draft--Manuscript Number: DEAF-D-16-00068R1
Full Title: Proper strong-Fibonacci games
Article Type: Original research
Corresponding Author: Laura Ziani, Ph.D.
Universita degli Studi di Udine Udine, Italy ITALY
Corresponding Author Secondary Information:
Corresponding Author's Institution: Universita degli Studi di Udine Corresponding Author's Secondary
Institution:
First Author: Laura Ziani, Ph.D.
First Author Secondary Information:
Order of Authors: Laura Ziani, Ph.D.
Flavio Pressacco Order of Authors Secondary Information:
Funding Information:
Abstract: We define proper strong-Fibonacci (PSF) games the subset of proper homogeneous weighted majority games whose minimal homogeneous representation exhibits the following strong connection with Fibonacci numbers: the increasing sequence of type weights and winning quota is a string of consecutive Fibonacci numbers. A simple characterization of the PSF games is given in terms of their profile. This opens the way to a
straightforward formula which gives the number $\Psi(t)$ of such games as a function of $t$, number of non-dummy players'
types. Moreover, it turns out that the growth rate of $\Psi(t)$ is exponential; precisely, the ratio between the number of the PSF games for two consecutive $t$ values of the same parity, $\Psi(t+2)/\Psi(t)$, converges toward the golden ratio $\Phi$.
Decisions in Economics and Finance manuscript No. (will be inserted by the editor)
Proper strong-Fibonacci games
Flavio Pressacco · Laura Ziani
Received: date / Accepted: date
Reply to reviewer n. 1
1. As the paper is concerned with enumeration results one should mentioned the known results for weighted majority games and homogeneous games in the introduction in order to justify the analysis of a rather special subclass (which I indeed find interesting).
Reply. In the introduction we devoted a specific indent (the third one) to a recall of the most important enumeration results concerning homogeneous weighted majority games and some more general results regarding complete simple games.
2. Several umlauts are missing in the spelling of names like Rosenm¨uller or Sudh¨olter at many places.
Reply. Done.
3. At several places you talk of types of players or classes of players. However, the respective meaning is different. The three classes step, sum, and dummy for homogeneous games are different from the concept of equivalence classes of players that you use later on. You should be more precise at those points. Reply. Definition 1 has been introduced in section 2 in order to clarify the meaning of players of the same type.
Flavio Pressacco
Dept. of Economics and Statistics D.I.E.S., Udine University, Italy via Tomadini 30/a, 33100 Udine, Italy
Tel.: +39-0432-249310 Fax: +39-0432-249329
E-mail: flavio.pressacco@uniud.it Laura Ziani
Dept. of Economics and Statistics D.I.E.S., Udine University, Italy via Tomadini 30/a, 33100 Udine, Italy
2 Flavio Pressacco, Laura Ziani
4. The so-called minimal homogeneous representation is of special importance for the entire paper. However, there is no precise definition. It would make sense to relate this concept with other minimal (integer) representations for weighted majority games.
Reply. In section 2 we introduce a precise definition of minimal integral representation as well as a new formal proposition (n. 1) on the uniqueness of such a representation for homogeneous games, followed by its relevant properties and by proper bibliographic references.
5. The concept of types of players is essential for the entire paper, so please provide an explicit definition.
Reply. See item n.3.
6. Footnote 4: The concept of a profile is essential for the understanding of the remaining part of the paper, so that is definition should not be hidden in a footnote. (Applies to other definitions as well.)
Reply. Definition 2 has been introduced in section 2 in order to clarify the meaning of the game profile, followed by a statement on the meaning of the coalition profile.
7. Notation in Section 4: There is no explicit ki(t; z) in Theorem 1, so please
be more precise at this point. It is no waste to explicitly introduce the used notation.
Reply. Definition 5 has been introduced in section 3 in order to clarify the meaning of kj(t, z) in the subsequent theorem 1.
8. Footnote 6: Please do not move complicated argumentations to footnotes. Reply. We moved the footnote in the text. Precisely in subsection 4.2, proof of Lemma 3, case t even.
9. The proofs in sections 5, 6 and the appendix can be simplified and short-ened if some well known facts about Fibonacci numbers are outsourced to separate statements (with or without proofs). The explicit formula for the Fibonacci number is an example as well as the sum of Fibonacci numbers appearing on page 11.
Reply. We inserted a new section 5 to summarize statements (without proofs) about well-known results concerning the standard Fibonacci se-quence and their extension (with proofs, if needed) to the delayed frame-work, which had been used in the proofs of the fundamental results ap-pearing now in the new sections 6-7 (old 5 and 6). This makes proofs more fluent. Moreover, the appendix has been inserted as proof of Proposition n. 5 in the new section 7 (old 6).
and some minor points:
10. p1, l-2: As far as I know the von Neumann-Morgenstern book is published in 1944. Since this is a huge book, please make your citation more precise. Reply. Done.
11. p2, l15: I do not think that Parsimonious games is a proper noun so that one should use lower cases (and an explanation).
Reply. Done.
strictly positive, in order to meet the properness quality of weighted ma-jority games.
13. p4, l-8: Please provide a reference for the constant sum case.
Reply. Done in the comments after the new Proposition 1, section 2. 14. Theorem 1: Why are you using j0as an index when there is no j1?
Reply. In the revised version we actually used j∗ in place of j0.
15. p5, l-2: Numerousness should be replaced by number (occurs at many places).
Reply. Done.
16. p7, l4: Proof is misplaced.
Reply. In the revised version, which has been modified also to take into account the comments of the other reviewers, this suggestion has been accepted.
17. p7, l10: Is there a difference between j0 and j0?
Reply. None. See also item 14.
Reply to reviewer n. 2
1. After Definition 1 the concept of profile of a game is introduced, but no example is provided, while examples are given only for profiles of coalitions. Reply. We introduced the formal definition (n. 2) of the game profile in section 2 as well as the new definition (n. 3) of type representation of a game in section 3. Immediately after, we add the example 2 as an example, among other things, of the profile of a game.
2. The definition of strategically equivalent players (page 4, line 19) is given for non-dummy players, but the definition applies also to dummy players, as the authors notice.
Reply. The new Definition 1 is provided as a formal definition of strategi-cally equivalent players, or players of the same type, and immediately after that, it is underlined that one type groups all dummies.
3. Some abbreviations may result not so obvious. Reply. Done.
4. I suggest to add an example after Theorem 1 in order to make clearer the notations k(t, z) (analogously for k(p, t, z)).
Reply. Done. We provided Definition n. 4 for k(t, z) and Definition n. 6 for k(t, z, p), followed respectively by examples n. 4 and n. 5.
5. A the end of Remark 2, the summations lack of the set over which the sum is taken.
Reply. Done.
6. The notation S/i (page 4, line 16) is intuitive but mathematically incorrect, S i is preferable.
4 Flavio Pressacco, Laura Ziani
7. Finally, the origin of game theory is in the book by von Neumann and Morgenstern (1944) instead of (1947) and there are two typos in the names of Rosenm¨uller and Sudh¨olter.
Reply. Done.
Reply to reviewer n. 3
1. Page2-Paragraph3. To mention (2016, [2]) as it is, and to add previous papers where Fibonacci numbers also appear: [3], “J. Freixas, X. Mo-linero, and S. Roura. Complete voting systems with two types of vot-ers: weightedness and counting. Ann. Oper. Res., 193:273-287, 2012 (doi: 10.1007/s10479-011-0863-x)”, etc.
Reply. We inserted “J. Freixas, X. Molinero, and S. Roura. Complete voting systems with two types of voters: weightedness and counting. Ann. Oper. Res., 193:273-287, 2012 (doi: 10.1007/s10479-011-0863-x)” in addi-tion to the paper of Freixas-Kurz in bibliography concerning the arising of connections with the Golden section and Fibonacci numbers in the enu-meration of classes of complete simple games. At the same time, we wish to point out that this is a different connection to the one that links the weights and the winning quota to Fibonacci numbers set, which is the common framework between Fragnelli et al. approach and ours. This is the reason why we have chosen to insert the respective bibliographic references in different places in the introduction.
2. Page3-Paragraph1. To mention (2013, [3]) as it is, and other previous pa-pers as “J. Freixas, X. Molinero, and S. Roura. Complete voting systems with two types of voters: weightedness and counting. Ann. Oper. Res., 193:273-287, 2012 (doi: 10.1007/s10479-011-0863-x)”, etc.
Reply. See the previous reply.
3. Page3-Paragraph1. To comment specific applications about PSF games. Reply. Concerning this point, we confirm that in the present paper we do not treat any application of PSF games, and so we limit ourselves to suggest in the conclusions that possible applications may be linked to the specific character of this class of games.
4. Page5-Line8. To write the meaning of “c.s.h.w.m.g”. Reply. Done.
5. Page6-Line24: Explain how to compute ki(p, t, z). It is described in Lemma
3’s proof?
Reply. We provided Definition n. 4 for k(t, z) and Definition n. 6 for k(t, z, p), followed respectively by examples n. 4 and n. 5. Theorem 2 ex-plains how to compute those components.
6. Page6-Line27-28-29-30. To give an intuition about the meaning of ki(p, t, z).
Reply. See previous reply.
7. Page6-Line51. I can see whyPtj=2kj(t, z) = t. Please, explain more.
9. Page7-Line12. “do satisfy”: “satisfy”. Reply. Done.
10. Maybe, Examples and Remarks inside the proof of Lemma 3 (Page7-8-9) are not suitable.
Reply. We split in three different subsections (4.1 Fundamental results, 4.2 Proof of theorem 2, and 4.3 Some clarifying examples) the proofs and the examples previously embedded in the old section 4.
11. To put properly all squares. Why does an square appear in Page9-Line49. Reply. Done.
12. Page10-Line29: Correct the English sentence. Reply. Done.
13. I think Section 5, 6 and 7 should be together “homogeneous notation”, at least Section 5 and 6.
Reply. Done.
14. Furthermore, I consider such results as Lemmata: Lemma with its proof for the result of Section 5, with just one proof with two cases: For t even... For t odd... Lemma with its proof for Result 1 of Section 6. Previously, to put here the Appendix as a Proposition. Lemma with its proof for the first result of Section 7. Corollary or Remark with its proof for the last result of Section 7 (p = 3).
Decisions in Economics and Finance manuscript No. (will be inserted by the editor)
Proper strong-Fibonacci games
Flavio Pressacco · Laura Ziani
Received: date / Accepted: date
Abstract We define proper strong-Fibonacci (PSF) games the subset of proper homogeneous weighted majority games whose minimal homogeneous represen-tation exhibits the following strong connection with Fibonacci numbers: the increasing sequence of type weights and winning quota is a string of consecu-tive Fibonacci numbers. A simple characterization of the PSF games is given in terms of their profile. This opens the way to a straightforward formula which gives the number Ψ (t) of such games as a function of t, number of non-dummy players’ types. Moreover, it turns out that the growth rate of Ψ (t) is exponential; precisely, the ratio between the number of the PSF games for two consecutive t values of the same parity, Ψ (t + 2)/Ψ (t), converges toward the golden ratio Φ.
Keywords Weighted majority games· minimal homogeneous representation · profile vector· Fibonacci numbers · Golden ratio
Preamble
In order to avoid misunderstandings, in the title of this paper the word “strong” should be intended as the strong connection between the class of games we
Flavio Pressacco
Dept. of Economics and Statistics D.I.E.S., Udine University, Italy via Tomadini 30/a, 33100 Udine, Italy
Tel.: +39-0432-249310 Fax: +39-0432-249329
E-mail: flavio.pressacco@uniud.it Laura Ziani
Dept. of Economics and Statistics D.I.E.S., Udine University, Italy via Tomadini 30/a, 33100 Udine, Italy
Tel.: +39-0432-249307 Fax: +39-0432-249329 E-mail: laura.ziani@uniud.it
study here and the Fibonacci numbers. Hence, it doesn’t mean strong in the well-known terminology used in the theory of simple games. A fortiori, the same remark applies to our previous paper (2015, [16]), titled Constant sum strong Fibonacci games, which is often recalled here. Coherently in this paper we will use “strong-Fibonacci” to remark this connection.
1 Introduction
At the origins of modern game theory Von Neumann-Morgenstern (1944, [21], chapt. X, p. 435) introduced the class of homogeneous weighted majority games and studied some of their properties. Since then, many other authors have been focusing on such games as they are the ideal framework for analyz-ing strategic behavior in areas such as coalitions formation and negotiation of payoff division within coalitions, both in the economic and political spheres.
Theoretical contributions of outstanding importance to these games were then given by: Isbell (1956, [6]), who gave the proof that any constant-sum homogeneous weighted majority game has a unique minimal integral homoge-neous representation; Maschler-Peleg (1966, [11]), who introduced the idea of desirability relation among players in simple games and discussed the connec-tion between the kernel and the homogeneous weights of a game; Peleg (1968, [14]) and Schmeidler (1969, [20]), who applied the nucleolus theory to such games; Ostmann (1987, [13]), who extended the Isbell (1956) results to homo-geneous non-constant sum weighted majority game; Rosenm¨uller (1984, [17] and 1987, [18]), who analyzed the structure of homogeneous weighted majority games based on the concept of players’ characters (step, sum and dummy) and the role of satellite games; Rosenm¨uller-Sudh¨olter (1994, [19]), who treated the nucleolus of homogeneous games with steps.
As for the enumeration issue, in addition to the pioneering contribution al-ready cited by Von Neumann-Morgenstern (who provided the list of 7 constant-sum homogeneous weighted majority games with less than 6 non-dummy play-ers), we recall here Gurk-Isbell (1959, [5], pp. 263-264), who gave the list of the 14 constant-sum weighted majority games− 8 out of which homogeneous − with exactly 6 non-dummy players; Isbell (1959, [7], pp. 27-28), who presented a combinatorial method for the enumeration of all constant-sum homogeneous weighted majority games, listing 114 games of such kinds− 23 out of which ho-mogeneous− with exactly 7 non-dummy players; Krohn-Sudh¨olter (1995, [9]), who provided algorithms for enumerating the classes of directed and weighted majority games (see table 1, p. 213). An exhaustive survey of the enumera-tion results concerning several classes of simple games, included the weighted majority ones, may be found in Le Breton et al. (2012, [10], tables 17-20, pp. 171-172).
In this paper we extend the results of our previous article (2015, [16]), which in turn was inspired by Isbell’s (1956). There he observed an inter-esting connection between a particular subset of constant-sum homogeneous weighted majority games and Fibonacci numbers. On this basis, we introduced
Proper strong-Fibonacci games 3
and studied the class of constant sum strong-Fibonacci (CSSF) games. Such games are constant sum homogeneous weighted majority games, whose min-imal homogeneous representation is characterized by the following “strong” connection with the Fibonacci sequence: the whole sequence of type weights (in bottom-top order) and the minimal winning quota is the corresponding initial string of the “delayed” Fibonacci sequence. We found the basic rule that provides the profiles of all CSSF games and showed that a very simple formula gives their number as a parity-specific linear function of the number t of non-dummy players’ types in the game.
Some time later Fragnelli et al (2016, [2]) named “Fibonacci representa-tions” of homogeneous weighted majority games those ones characterized by a “weaker” link with the Fibonacci sequence: the authors preserved the con-dition that all weights must be Fibonacci numbers, but they did not require either the consecutiveness of such numbers or a Fibonacci number as the win-ning quota. They have studied some properties of such representations without dealing with enumeration problems.
Here, we carry on the “strong approach” of [16] to defining and studying the largest class of proper (not necessarily constant sum) strong-Fibonacci (PSF) games. We find that this extension is governed by a very simple rule: each CSSF game is the seed of a set of PSF games (including the seed), whose profiles replicate the one of the seed in all but the first component (number of the weakest non-dummy players). This component may be any positive integer (but 1, for a few “special” seeds) not greater than the first one of the seed. Hence, a closed form formula still gives the number of PSF games as a function of t. Its growth rate follows an exponential trend. Analyzing the asymptotic behaviour of this rate, we find another unexpected strong connection between PSF games and Fibonacci numbers, which is the fundamental result of the paper: the ratio between the number of the PSF games for two consecutive t values of the same parity converges to the golden section.
For the sake of comparison, we signal that other interesting connections between the golden section and Fibonacci sequences in some particular classes of voting games have been discovered and discussed by Freixas et al. (2012, [4]) and Freixas-Kurz (2013, [3]). The point will be quickly described in the section 9.
Lastly, we emphasize that in this paper we do not discuss the possible applications of our Fibonacci games, although we feel confident on future po-tential applications for weighted voting systems in parliamentary elections. Anyway, among the vast body of literature concerning significant applications of homogeneous weighted majority games to political issues, we recall those by: Montero (2008, [12]), who discussed a bargaining protocol (which modifies the one proposed by Baron-Ferejohn (1989, [1])) in which both the expected payoffs and actual payoff division are proportional to the voting weights; Ka-landrakis (2006, [8]) and Le Breton et al. (2012, [10]) on the applications of homogeneous weighted majority games (constant as well as non-constant sum) to the analysis of voting power and committees interactions.
The plan of the paper is as follows: section 2 gives a short recall of the basics of homogeneous weighted majority games; in section 3 a synthesis of the main results of our previous paper on CSSF games is given, stressing in particular those which are pillars of the new setup; in section 4, divided in three subsec-tions, we introduce the extension from constant-sum to proper games (section 4.1), give proofs of the results concerning the connection between the respec-tive profiles (section 4.2) and discuss some enlightening examples (sect. 4.3); in section 5 we recall some well known results on Fibonacci numbers, useful in the next sections, extending them to the delayed framework; in section 6 we obtain the closed form formula for the number of PSF games as a function of t; section 7 gives the proof of the main result of the paper, i.e. the convergence of the ratio between the number of PSF games for two consecutive values of t of the same parity toward the golden section; section 8 is devoted to a quick discussion of some subsets of PSF games with special properties; in section 9 a connection between our approach and a recent paper of Freixas-Kurz [3] is provided; conclusions follow in the final section 10.
2 Notations
We now recall some well-known definitions.
The Fibonacci sequence f is defined by the well known finite difference equation:
fn = fn−1+ fn−2
holding for any natural n > 2 with initial conditions f1= f2= 1.
Henceforth, we will exploit the “delayed Fibonacci sequence” g, defined by gn = fn+1 for any positive n; for any integer m, we denote by gm∈ Nm the
m vector (g1, g2, . . . , gm). Sometimes we will use also g0= f1= 1.
A simple game is a pair (Ω, v) with Ω ={1, 2, . . . , n} the set of players of the game. The elements S ofP(Ω) are called coalitions. The characteristic function of the game, v, is a mapping v :P(Ω) → {0, 1} such that v(∅) = 0, v(Ω) = 1 and the monotonicity property holds: v(S) = 1⇒ v(T ) = 1 for any S⊆ T .
A coalition S∈ P(Ω) is winning if its payoff v(S) = 1 and losing otherwise. A simple game is proper if, for any S, v(S) = 1⇒ v(Ω \S) = 0; it is strong if v(S) = 0⇒ v(Ω\S) = 1; it is constant-sum if, for any S, v(S)+v(Ω\S) = 1. A player i is at least as desirable as a player j, denoted i j, if for any S such that S∩ ({i} ∪ {j}) = ∅, it is v(S ∪ {i}) ≥ v(S ∪ {j}). The desirability relation is reflexive and transitive. It is complete if it holds for any pair of players (see [11], 1966, p. 316). A simple game is called complete if its desirability relation is complete.
Proper strong-Fibonacci games 5
A coalition S is minimal winning if v(S) = 1 and, for any i∈ S, v(S\{i}) = 0. The set of all minimal winning coalitions is denoted by Wm. If, for any
S∈ Wm, (S
∩ {i}) = ∅, i is said a dummy player. Clearly, for any pair (i, j), of dummies, it is i∼ j.
In a complete game, the players may be divided in t+1 sets; each one groups all players of the same type; in particular, one type groups all dummies.
Weighted majority (w.m.) games are proper simple games described by a representation (w; q). In the representation w is a vector of (without losing generality in non-decreasing order1) non negative numbers called weights of the
players, or individual weights; the weight of any coalition S is w(S) =Pi∈Swi.
The scalar q > 1
2w(Ω) is the winning quota, so that v(S) = 1 iff w(S)≥ q. A representation (w; q) of a weighted majority game is homogeneous (hom) if S∈ Wm
⇔ w(S) = q. This implies that w(S) − w(Ω \ S) = c > 0 (constant for all S∈ Wm).
A weighted majority game is hom if there exists (at least) one hom repre-sentation of the game.
Both hom and not hom w.m. games have a lot of representations. Among them the so called integral representations are of overwhelming importance.
A representation (w; q) is integral if q ∈ N and if, for any i ∈ Ω, wi ∈
N∪ {0}.
Henceforth we will consider only integral representations.
A representation (w′, q′) is minimal if there exists no (integral) represen-tation (w; q)6= (w′
, q′) such that wi ≤ w∗i for i = 1, . . . , n.
A representation (w′, q′) is minimum if, for any other (integral) represen-tation (w; q), it is w′i≤ wi for i = 1, . . . , n.
The following fundamental result holds:
Proposition 1 A hom w.m. game has a unique minimal integral representa-tion; it is homogeneous.
For constant-sum hom w.m. games the theorem has been proved by Isbell (1956, [6], p. 184). See also Peleg (1968, [14], p. 528). The theorem has been extended to non-constant sum hom w.m. games by Ostmann (1987, [13], p. 79-81).
The unique minimal hom representation has the following relevant prop-erties. It preserves types: formally i ∼ j ⇔ wi = wj, that is strategically
equivalent players have the same weight (and players of different types have different weights); in particular, dummy players have zero weight and the weakest non-dummies have unit weight. Moreover, in the constant-sum case (see Isbell [6], Cor. 2, p. 184):
w(Ω) =X
i∈Ω
wi= 2q− 1
1
or
w(S)− w(Ω \ S) = 1 for S ∈ Wm
Remark 1 Note that also “many” non hom games have a unique minimal integral representation (obviously non hom) and, in particular, constant-sum non hom w.m. games may satisfy w(Ω) = 2q− 1.
Example 1 The non hom constant-sum w.m. game with minimal integral rep-resentation (w; q) = (1, 1, 2, 2, 3, 4; 7).
Isbell was the first to provide an example of a non hom game with two minimal integral representations ([7], p. 27).
Remark 2 Up to now we used individual representations, that is (wn; q) with
wn an ordered n vector of individual weights. Henceforth, we will use also the
notation (w∗
t; q∗) where w∗t is an ordered t vector of non-dummy type weights.
Of course, this is not sufficient to describe a game. As we shall see hereafter, we need also the so called profile vector (see definition 3).
Let us recall that the non-dummy players of a hom weighted majority game may be divided into non overlapping sets (K1, K2, . . . , Kj, . . . , Kt); each set
groups all players of a given type j.
Just as individual players, also types are bottom-top ordered (of course strictly), i.e. from the weakest player to the strongest. The common weight of any player of type j is w∗
j.
The following definition holds:
Definition 2 The profile of a game with t dummy types and n non-dummy players is the ordered vector
kt= (k1, k2, . . . , kj, . . . , kt)
kj being the number of players of type j in the game, so that Ptj=1kj = n.
By analogy, the profile of a coalition S (see Rosenm¨uller [18], p. 311) in a game with t types is:
st= (s1, s2, . . . , sj, . . . , st)
with sj=|S ∩ Kj|, that is the number of players of type j in the coalition S.
3 Short recall of some results on CSSF games
Henceforth we shall consider only the class of homogeneous weighted ma-jority games. In particular, starting from the existence for such games of a unique minimal integral individual representation (wn; q), we associate to it
the corresponding unique minimal integral type representation, according to the following definition:
Proper strong-Fibonacci games 7
Definition 3 The type representation of a hom weighted majority game with t non-dummy types is the triplet (kt; wt∗; q∗) associated to the unique minimal
integral individual representation (wn; q), with q∗ = q, w∗j = wi ∀i ∈ Kj,
j = 1, . . . , t and kt the profile of the game. Hence, in a type representation
there are one profile vector, one type weight vector and the winning quota. Example 2 Let us consider the constant-sum hom w.m. game with unique minimal integral individual representation (w6; q) = (1, 1, 1, 2, 2, 4; 6). There
are three types and the associated type representation is (k3; w∗3; q∗) = (3, 2, 1; 1, 2, 4; 6).
Clearly, the game profile is k3= (3, 2, 1).
Now let us recall that the following definition of constant-sum strong-Fibonacci (CSSF) games has been introduced in Pressacco-Ziani [16]:
Definition 4 CSSF games are the subset of constant-sum homogeneous weighted majority game whose minimal hom type representation (kt; wt∗; q∗) is such that
the bottom-top ordered sequence of type weights and winning quota (w∗ t; q∗) is
(gt; gt+1) = gt+1.
In words, the sequence of type weights and the winning quota is a string of consecutive Fibonacci numbers, and of course ktis a feasible profile coherent
with the homogeneity condition under minimal representation.
Example 3 Let us consider the game whose minimal hom individual repre-sentation, is (w10; q) = (1, 1, 1, 1, 1, 2, 2, 3, 5, 8; 13). There are t = 5 types and
the associated type representation is (k5; w5∗; q∗) = (5, 2, 1, 1, 1; 1, 2, 3, 5, 8; 13).
This representation satisfies the condition (w∗
5; q∗) = (g5; g6) = g6. The
coali-tion profiles, for any S ∈ Wm, are (0, 0, 0, 1, 1), (0, 1, 1, 0, 1), (1, 2, 0, 0, 1),
(1, 2, 1, 1, 0), (2, 0, 1, 0, 1), (3, 1, 0, 0, 1), (3, 1, 1, 1, 0), (5, 0, 0, 0, 1), (5, 0, 1, 1, 0), and it is easy to check that P5j=1sj· gj = q = g6. Hence, the profile of the
game is coherent with homogeneity.
Concerning CSSF games the following results hold:
Proposition 2 For any given t > 2, there are in general several CSSF games, precisely ζ(t) =⌊(t + 1)/2⌋ (see [16], Cor. 3.1).
Proposition 3 All games with the same t differ (i.e. there are no ties) for the total number of non-dummy players (see [16], Th. 3.2).
Then, they may be ordered according to such number from the smallest to the largest. Denoting by z the counter coherent with such an order z∈ N := {1 ≤ z ≤ ⌊(t + 1)/2⌋}, we introduce the following definition:
Definition 5 The two parameters profile vector of the CSSF game with t types and counter z is the ordered vector
k(t, z) = (k1(t, z), k2(t, z), . . . , kj(t, z), . . . , kt(t, z))
kj(t, z) being the number of players of type j in the game, so thatPtj=1kj(t, z) =
n(t, z) is the total number of non-dummy players in such a game.
The following theorem holds (see [16], Th. 3.1):
Theorem 1 For any2positive integer t, a game is CSSF iff the profile k(t, z)
is given by3: k(t, z) = ( (k1, k ′ , kj∗, k ′′ ) if z = 1, . . . ,⌊(t − 1)/2⌋ (2 + gt−1, 1t−1) if z =⌊(t + 1)/2⌋ (1a) (1b) with, in formula (1a): j∗= j(t, z) = t + 1
− 2z, k1= k1(t, z) = 2 + gt−1− gj∗,
k′ = k′(t, z) = 1j∗−2, kj∗ = kj(t,z)= 2, k ′′
= k′′(t, z) = 12z−1.
Example 4 For t = 3 there are ⌊(t + 1)/2⌋ = 2 CSSF games. For z = 1 it is j∗ = t + 1 − 2z = 2, so that k1 = 2 + gt−1− gj∗ = 2 + g2− g2 = 2. The dimension of k′ is j∗ − 2 = 0, kj∗ = k2= 2, the dimension of k ′′ is 2z− 1 = 1. Hence, the game profile k(3, 1) = (2, 10, 2, 11) = (2, 2, 1). For z = 2, the game
profile is k(3, 2) = (2 + gt−1, 1t−1= 2 + g2, 12) = (4, 12) = (4, 1, 1).
This confirms that there are n(3, 1) = 5 < n(3, 2) = 6 players, coherently with Th. 3.2. in [16].
Remark 3 For z = 1, . . . ,⌊(t−1)/2⌋, k′ and k′′ are unit vectors of dimension respectively (j∗− 2) = (t − 2z − 1) and (2z − 1), whose sum is just (t − 2).
Hence, there is just one player for each non-weakest type t, except for the type in place j∗= t + 1− 2z, (i.e. t − 1 or t − 3 or t − h with h odd) for which there
are two players. Then, the total number of non-weakest non-dummy players is Pt
j=2kj(t, z) = (t− 2) + 2 = t.
For z =⌊(t+1)/2⌋ there is just one player for any non-weakest type. Then, the total number of non-weakest non-dummy players isPtj=2kj(t, z) = t− 1.
In any case, it is easy to check that there are as many weakest type players, either (2+gt−1−gj∗) or (2+gt−1), as needed in order to meet the constant-sum
condition w(Ω) =Ptj=1kjw∗j =
Pt
j=1kjgj= 2q− 1 = 2gt+1− 1.
Remark 4 k1 = k1(t, z), the number of players of the weakest non-dummy
type (with unit weight), is for any given t an increasing function of z. Indeed, it is obtained subtracting gj∗ from 2 + gt−1. Now, j∗ = j(t, z) = t + 1− 2z
is decreasing with z, which implies that gj∗ is a decreasing function of z, too.
Hence, the conclusion.
4 Proper strong-Fibonacci games 4.1 Fundamental results
In this section we extend the definition of CSSF games to proper, not neces-sarily constant-sum, strong-Fibonacci games (PSF games).
2
Both for t = 1 and t = 2, there is a unique feasible value of z = ⌊(t + 1)/2⌋ = 1. Hence, in both cases there is just one CSSF game, whose game profiles are, according to formula (1b), k(1, 1) = (3) and k(2, 1) = (3, 1), respectively.
3
Henceforth, the subscript in the vectorial notation 1hmeans that the unit vector has
Proper strong-Fibonacci games 9
Definition 6 PSF games are the subset of proper homogeneous weighted ma-jority game whose minimal hom type representation (kt; wt∗; q∗) is such that
the bottom-top ordered sequence of type weights and winning quota (w∗ t; q∗) is
(gt; gt+1) = gt+1.
Remark 5 Note that for any given t, the winning quota is still q∗ = g t+1,
as in the constant-sum case; hence the only difference with CSSF game is embedded in the profile kt of the game.
To understand the behavior of feasible profiles of PSF games, the starting point is the set of feasible profiles k(t, z) described by Theorem 1 in section 3.
Here we need the following definition: Definition 7
k(t, z, p) = (k1(t, z, p), k2(t, z, p), . . . , kj(t, z, p), . . . , kt(t, z, p))
is the three parameters profile vector of a PSF game with t types, counter z and index p. Obviously, kj(t, z, p) is the number of players of type j in the PSF
game with t types, counter z and index p.
The parameter p may be seen as a new index added to the pair (t, z). Then, let us call “truncated” profiles the vectors
b
k(t, z) = (k2(t, z), . . . , kj(t, z), . . . , kt(t, z))
b
k(t, z, p) = (k2(t, z, p), . . . , kj(t, z, p), . . . , kt(t, z, p))
obtained by the “complete” profiles k(t, z) and k(t, z, p) cutting their first component k1, so that
k(t, z) = (k1(t, z), bk(t, z))
k(t, z, p) = (k1(t, z, p), bk(t, z, p))
The following theorem about feasible profiles of PSF games holds: Theorem 2
k(t, z, p) = (p, bk(t, z)) (2) with bk(t, z) coherent with (1a) and (1b), and p any positive integer satisfying:
1
≤ p ≤ k1(t, z) for z <⌊(t + 1)/2⌋
1 < p≤ k1(t, z) for z =⌊(t + 1)/2⌋
(3a) (3b) Example 5 Let us consider the CSSF game with t = 7 and z = 2 whose profile is k(7, 2) = (10, 12, 2, 13). It is bk(7, 2) = (12, 2, 13), and putting p = 4,
by Th. 2, k(7, 2, 4) = (4, bk(7, 2)) = (4, 12, 2, 13). This profile corresponds to
the individual representation (w11; q) = (1, 1, 1, 1, 2, 3, 5, 5, 8, 13, 21; 34).
Remark 6 Any CSSF game with profile k(t, z) may be thought as the seed of a set of PSF games (including the seed).
Corollary 1 The number Ψ (t, z) of PSF games with t types and counter z is: Ψ (t, z) = k 1(t, z) if z = 1, . . . ,⌊(t − 1)/2⌋ k1(t, z)− 1 if z = ⌊(t + 1)/2⌋ (4a) (4b) with k1(t, z) given by formulae (1a) and (1b).
Remark 7 All the PSF games of the set generated by a given constant-sum seed share the same bk(t, z); hence, their profiles differ only for the first compo-nent, i.e. the number of weakest non-dummy players. This may be any positive integer within the upper bound k1(t, z) of the seed for any z <⌊(t + 1)/2⌋; for
z = ⌊(t + 1)/2⌋ at least two weakest players are required. In turn, keeping account that (see Remark 3) for z <⌊(t + 1)/2⌋ it is Ptj=2kj(t, z) = t, this
implies that the smallest number of non-dummy players in any PSF game with t types is t + 1.
4.2 Proof of Theorem 2
The proof of Th. 2 may be divided into two parts. The first one (Lemma 1) concerns a necessary condition for the feasibility of bk(t, z, p), while the second (Lemma 2 e Lemma 3) regards k1(t, z, p).
Lemma 1 A necessary condition for the feasibility of a complete profile k(t, z, p) of a PSF game is that its truncated version bk(t, z, p) satisfy the conditions re-sumed by Th. 1 for the feasibility of profiles k(t, z) of the CSSF seed.
To demonstrate this Lemma, it is convenient to recall Property 6.7 in [16] (p. 41) in the following version:
Proposition 4 In a feasible profile of a CSSF game there is at most one positive odd integer h < (t− 1) such that kj∗ = kt−h = 2; for all other j > 1
and different from j∗, it is k j = 1.
We remind that, for CSSF games, the proof of Proposition 4 came from the fact that, if the necessary conditions are not satisfied, there are coalitions S∈ Wmwithout players of type 1 (or, more formally, with first component of the
coalition profile s1 = 0) and with coalition weight w(S) > q (a contradiction
with the hom quality of the game). Hence the proof did not involve the first component of the profile.
As, given t, the winning quota q of any PSF game remains fixed at q = gt+1,
independently from the number of weakest players in the game, the same argument may be applied to derive the necessity of the conditions given by Proposition 4 also in the profiles of PSF games.
The second part of the proof gives, at first, an upper bound for the value of k1(t, z, p).
Lemma 2 The upper bound for k1(t, z, p) is k1(t, z).
Proper strong-Fibonacci games 11
Proof The choice of k1(t, z), according to Th. 1, grants that in the CSSF game
w(Ω) =Ptj=1kjgj= 2q−1. As in proper games neither the winning quota nor
the truncated profile are modified with respect to the ones of the CSSF seed, a choice of the first component of the complete profile k1(t, z, p) > k1(t, z) would
give w(Ω)≥ 2q (a contradiction with the proper quality of the game). ⊓⊔ It remains to check which values of the first component k1(t, z, p), among
those respecting the upper bound, are feasible for a proper game. The answer is given by:
Lemma 3 The feasible values of k1 are all positive integers respecting the
following conditions: 1 < k 1≤ k1(t,⌊(t + 1)/2⌋) if z = ⌊(t + 1)/2⌋ 1≤ k1≤ k1(t, z) if z = 1, . . . ,⌊(t − 1)/2⌋ (5a) (5b) Proof
Case z =⌊(t + 1)/2⌋. The truncated profile is bk(t, z, p) = bk(t, z) = (1t−1).
Let us distinguish two subcases depending on the parity of t.
– If t even, for any player of type j > 1 odd, it is immediate to see by induction that there exists a coalition S ∈ Wm such that the player of
type j is the weakest in S. In particular, this is true for j = 3.
By the same argument there is no player of type j > 1 even, which is weakest in a min win coalition. In particular this is true for j = 2. Suppose k1= 1. Then, the couple of players of type 1 and 2 would replace
the player of type 3 in S, which in turn implies that type 1 player is not a dummy. Moreover, this is clearly the only way for type 1 and type 2 players to be members of a min win coalition. Hence, players of type 1 and type 2 would be strategically equivalent weakest players and should have the same weight 1 in the min hom representation of the game. This is a contradiction, so k1= 1 is not feasible.
On the contrary, suppose k1 = 2. Then, one player of type 1 and the
unique one of type 2 may still replace the player of type 3 in S, which still implies that type 1 players are not dummies. Yet types 1 and 2 are no more equivalent. Indeed, let S′ the coalition obtained by replacing the player of type 3 in S with the first player of type 1 and the player of type 2. If we replace in S′
the player of type 2 with the other player of type 1 the coalition is no more winning; this confirms that players of type 1 are not equivalent to the player of type 2. Hence, k1= 2 is feasible.
– If t odd, for any player of type j > 1 even, there exists a coalition S∈ Wm
such that the player j is the weakest in S. In particular this is true for j = 2.
Moreover there is no player of type j > 1 odd weakest in a min win coal. Suppose k1= 1. This implies that the player of type 1 would be a dummy
and in addition we could check that player 2 and 3 become equivalent
players, contrary to the hypothesis that they have different weights: again k1= 1 is not feasible.
On the contrary suppose k1= 2. Then the couple of players of type 1 would
replace the player of type 2 in S, which still implies that type 1 players are weakest non-dummy, of course not equivalent to the type 2 player; hence k1= 2 is feasible.
It is intuitive (and easy to check) that also any value of k1 > 2 and of
course respecting the upper bound is feasible for a PSF game, irrespective of the parity. Indeed, as k1 increases, there is a wider ability of the weakest
players to replace not only the player of type 2, but also other single or groups of more powerful players.
Case z ≤ ⌊(t − 1)/2⌋. The structure of the truncated profile is bk = (k′, kj∗, k
′′
) with k′ = 1j∗−2; kj∗ = 2; k ′′
= 12z−1 with j∗= t + 1− 2z.
Suppose to add k1= 1 to obtain the complete profile k = (1, k
′
, kj∗, k ′′
). The following results are relevant to grant the feasibility of k1 = 1 (and a
fortiori for k1> 1) for any z≤ ⌊(t − 1)/2:
Result 1 t and j∗ are surely of alternative parity.
Result 2 Consider any player of type j with the same parity of j∗ (including
the couple of players of type j∗): there exists a minimal winning coalition in
which such player is weakest. Proof by induction. It is true for j = t−1, and if true for some j (through a coalition S′), it is true for j−2: indeed, the weakest player in S′ is replaced by the players of type j− 1 and (by one if j − 2 = j∗)
of type j− 2.
Result 3 Consider any player of type j < j∗ and of alternative parity: there
exists a minimal winning coalition in which such player is weakest. Proof by induction. It is true for j = j∗
− 1 (indeed the sum of the weights of the player type j∗− 1 and of both players of type j∗ is equal to the weight of the player
type j∗+ 2 if j∗+ 2 < t, or to g
t+1= q if j∗+ 2 = t + 1), and if true for some
j (through a coalition S′′) it is true (by the same replacement argument used in b) for j− 2.
Result 4 Jointly results 2 and 3 imply that the player of type 1 as well as the player(s) of type 2 are weakest member of a min win coal. This again implies that the weakest player is not dummy and is less powerful than the the next type player(s), so that the complete profile with k1 = 1 (and a fortiori for
k1> 1) is feasible.
⊓ ⊔ 4.3 Some clarifying examples
Proper strong-Fibonacci games 13
Example 6 Suppose t = 6 (even) so that z = 3. Hence, bk(6, 3) = (15).
Suppose k1 = 1 and consider the corresponding complete profile k(6, 3, 1) =
(1, 15). The individual representation of the corresponding proper Fibonacci
game would be (1,2,3,5,8,13;21). The profiles of the S ∈ Wm are S 1 =
(0,0,0,0,1,1); S2 = (0,0,1,1,0,1); S3 = (1,1,0,1,0,1). Hence, the players of
weight 1 and weight 2 are strategically equivalent, 1∼ 2. The suggested rep-resentation does not preserve types and can not be a minimal hom represen-tation (see Remark 7), even though it is a hom represenrepresen-tation involving all the first 7 components of the Fibonacci sequence. The minimal hom individual representation of the game4 with such minimal winning coalitions is actually
(1,1,2,3,5,8;13), with complete profile k(t, z, p) = k(5, 3, 2) = (2, 14).
Example 7 Suppose t = 6 (even) so that z = 3. Hence, bk(6, 3) = (15).
Suppose k1 = 2 and consider the corresponding complete profile k(6, 3, 2) =
(2, 15). The individual representation of the corresponding proper Fibonacci
game would be (1,1,2,3,5,8,13;21). The profiles of the S∈ Wm are still S 1 =
(0,0,0,0,1,1); S2 = (0,0,1,1,0,1); S3 = (1,1,0,1,0,1). On one side, this
con-firms that type 1 players are not dummies, but despite the coincidence with the coalition profiles of Example 1, there is no equivalence now between the type 2 player and each player of type 1. The explanation is that the profile (2,0,0,1,0,1) is not the one of a winning coalition. In other words, while it is true that the player of type 2 enters in min win coal with one of the players of type 1, two weakest players are not able to replace the player of type 2 in a minimal winning coalition.
Remark 8 We stress that in the game of Example 7 the fact that the player of type 2 is more powerful than each of the bottom type players does not come from a replacement property (one for two) in some min win coalitions. The character of such a player, in the language of modern game theory (see [19], is step.
Example 8 Suppose t = 7 (odd) so that z = 4. Hence, bk(7, 4) = (16). Suppose
k1= 1 and consider the corresponding complete profile k(7, 4, 1) = (1, 16). The
individual representation of the corresponding proper Fibonacci game would be (1,2,3,5,8,13,21;34). The profiles of the S ∈ Wm are S
1 = (0,0,0,0,0,1,1);
S2= (0,0,0,1,1,0,1); S3= (0,1,1,0,1,0,1). Then the weakest player turns out
to be dummy. Deleting this player we obtain that the S ∈ Wm are S 1 =
(0,0,0,0,1,1); S2= (0,0,1,1,0,1); S3= (1,1,0,1,0,1), i.e. exactly the one of the
previous examples. Once more, k1= 1 is not feasible.
Example 9 Suppose t = 7 (odd) so that z = 4. Hence, bk(7, 4) = (16).
Suppose k1 = 2 and consider the corresponding complete profile k(7, 4, 2) =
(2, 16). The individual representation of the corresponding proper Fibonacci
game would be (1,1,2,3,5,8,13,21;34). The profiles of the S ∈ Wm are now
S1= (0,0,0,0,0,1,1); S2= (0,0,0,1,1,0,1); S3= (0,1,1,0,1,0,1); S4= (2,0,1,0,1,0,1).
It is immediate to check that in S4 two bottom players replace the role of the
4
This is an example of a game with a veto player; see section 8.
player with weight 2 in S3. This makes clear that any value of k1 > 1 and
within the upper bound gives rise to feasible complete profiles.
Remark 9 Here the source of the fact that player of type 2 is more powerful than each of the weakest type players comes from the replacement property (one for two) in a min win coalition. Its character is sum.
Example 10 Suppose t = 6 so that z = 3. Hence, bk(6, 3) = (15). Suppose
k1= 3 and consider the corresponding complete profile k(6, 3, 3) = (3, 15). The
individual representation of the corresponding proper Fibonacci game would be (1,1,1,2,3,5,8,13;21). The profiles of the S∈ Wm are now S
1= (0,0,0,0,1,1);
S2= (0,0,1,1,0,1); S3= (1,1,0,1,0,1); S4= (3, 0, 0, 1, 0, 1); S5= (3,1,1,0,0,1);
S6 = (3,1,1,1,1,0). It is immediate to check that in S4 two weakest players
replace5 the role of the player with weight 2 in S
3. This makes clear that any
value of k1 > 1 and within the upper bound gives rise to feasible complete
profiles.
Example 11 Suppose t = 2 so that z = 1. Hence, by formula (1b) the profile is k(2, 1) = (3, 11) and, coherently with formula (3b), there are k1− 1 = 2
feasible values of p: p = 2 and p = 3. At the end there are two PSF games with complete profile k(2, 1, 3) = k(2, 1) = (3, 11) corresponding to the seed,
and the other k(2, 1, 2) = (2, 11).
Example 12 Suppose t = 1 so that still z = 1. Hence, by formula (1b) the profile is k(1, 1) = (3, 10) and, coherently with formula (3b), there are k1−1 =
2 feasible values of p: p = 2 and p = 3. At the end there are two PSF games with complete profile k(1, 1, 3) = k(1, 1) = (3, 10) corresponding to the seed,
and the other k(1, 1, 2) = (2, 10). In this game with two players of the same
type the only winning coalition is Ω. Case z≤ ⌊(t − 1)/2⌋.
Example 13 Suppose t = 7 and z = 2. Hence, bk(7, 2) = (12, 2, 13). Suppose
k1= 1 and consider the corresponding complete profile k(7, 2, 1) = (1, 12, 2, 13).
Here j∗ = 4. The individual representation of the corresponding PSF game
would be (1,2,3,5,5,8,13,21;34). The profiles of min win coalitions are S1 =
(0,0,0,0,0,1,1); S2= (0,0,0,1,1,0,1); S3= (0,1,1,0,1,0,1); S4= (0,0,1,2,0,0,1);
S5 = (1,1,0,2,0,0,1). Coalition S3 satisfies result 2 as player of type 2 of the
same parity of type j∗ = 4 is the weakest; coalitions S
4 and S5 satisfy result
3 as player of type 3 of alternative parity is the weakest in S4 and hence the
weakest player of the game is the weakest in S5. Hence, k1= 1 is feasible.
5
Proper strong-Fibonacci games 15
5 Statements and results about Fibonacci in the standard and delayed framework
In what follows we will exploit some well known results on Fibonacci num-bers, recalled here as statements, and extend them to the delayed Fibonacci sequence introduced at the beginning of sect. 2.
Statement 1 With the initial position f1= f2= 1, for all t≥ 1 it is:
ft+2= ft+1+ ft (6)
Statement 2 For all t≥ 2 it is:
ft+1= 1 + t−1
X
j=1
fj (7)
Statement 3 For all t≥ 2 it is:
(f2 t − ft−1ft+1) = − 1 for t even + 1 for t odd (8a) (8b) Statement 4 Denoting by Φ = 1 + √ 5
2 = 1, 6180339887 . . . the Golden Ratio, it is:
lim
t→∞
ft+1
ft = Φ (9)
In the delayed framework, it is:
gt= ft+1for all t∈ N ∪ 0 (10)
and by formula (6):
gt+2= gt+1+ gt (11)
From formulae (7) and (10) we obtain, for all t≥ 2: 1 + t−2 X j=0 gj= gt (12) and 1 + t−2 X j=1 gj= gt− 1 (13)
and g1+ g3+ g5+ . . . + gt−1= g1+ t−2 X j=1 gj= gt− 1 (15)
From Statement 3 and formula (10) it is: (g2 t − gt−1gt+1) = − 1 for t odd + 1 for t even (16a) (16b) From Statement 4 and formula (10) it is:
lim
t→∞
gt+1
gt = Φ (17)
6 The number of Proper strong-Fibonacci games
Denoting by Ψ (t) the total number of PSF games with t types and recalling that Ψ (t, z) is the number of PSF games with t types and counter z, the following lemma holds:
Lemma 4 For any t:
Ψ (t) = ⌊(t+1)/2⌋X z=1 Ψ (t, z) = ⌊(t−1)/2⌋X z=1 Ψ (t, z) + Ψ (t,⌊(t + 1)/2⌋) (18) Then we claim that:
Theorem 3 For any t it is:
Ψ (t) = (2 + gt−1)· ⌊(t + 1)/2⌋ + − (gt− 1) for t even − gtfor t odd (19a) (19b) Proof Inserting formulae (4a) and (4b) in Lemma 4, we have:
Ψ (t) = ⌊(t−1)/2⌋ X z=1 k1(t, z) + k1(t,⌊(t + 1)/2⌋) − 1 = =− 1 + ⌊(t+1)/2⌋ X z=1 k1(t, z) (20)
Substituting the values of k1(t, z) provided by formulae (1a) and (1b), and
applying elementary algebra, we get:
Proper strong-Fibonacci games 17
To obtain a closed form formula, it remains to compute the term (1 + P⌊(t−1)/2⌋
z=1 gj∗) as a function of t (not involving z). Of course, in case t = 1
or t = 2 this term reduces to 1, as⌊(t − 1)/2⌋ = 0; hence, in formulae (19a) and (19b) the addends after the curly brackets become−1, and immediately Ψ (t) = 2 in both cases. – Case t > 2 even. ⌊(t−1)/2⌋X z=1 gj∗ = (g3+ g5+ . . . + gt−1) so that, by formula (15): Ψ (t) = (2 + gt−1)⌊(t + 1)/2⌋ − (1 + g3+ g5+ . . . + gt−1) = (2 + gt−1)⌊(t + 1)/2⌋ − (gt− 1) (22) – Case t > 1 odd. ⌊(t−1)/2⌋X z=1 gj∗ = (g2+ g4+ . . . + gt−1) so that, by formula (14): Ψ (t) = (2 + gt−1)⌊(t + 1)/2⌋ − (1 + g2+ g4+ . . . + gt−1) = (2 + gt−1)⌊(t + 1)/2⌋ − gt (23) ⊓ ⊔ The following table is built applying formulae (1a), (1b), (4a), (4b), (19a) and (19b). z 1 2 3 4 t Ψ (t, z) Ψ (t) ζ(t) Ψ (t)/ζ(t) 1 2 2 1 2,00 2 2 2 1 2,00 3 2 3 5 2 2,50 4 2 4 6 2 3,00 5 2 5 6 13 3 4,33 6 2 7 9 18 3 6,00 7 2 10 13 14 39 4 9,75 8 2 15 20 22 59 4 14,75 ... ... ... ... ... ... ... ...
7 Proper strong-Fibonacci games and the Golden ratio Let us consider the following ratio:
ξ(t) = Ψ (t + 2)− Ψ(t)
Ψ (t) (24)
It represents the local growth rate of Ψ (t) (for two consecutive values of t of the same parity). In fact ξ(t) = Ψ (t + 2)
Ψ (t) − 1 or
Ψ (t + 2)
Ψ (t) = 1 + ξ(t). In order to understand the behaviour of ξ(t), we study the difference Ψ (t + 2)−Ψ(t); here we treat only the odd case as the even one is a trivial extension. Lemma 5
Ψ (t + 2)− Ψ(t) = 2 + gt· ⌊(t + 1)/2⌋ (25)
Proof Exploiting ⌊(t + 3)/2⌋ = ⌊(t + 1)/2⌋ + 1 and recalling formula (11) we obtain, by elementary algebra:
Ψ (t + 2)− Ψ(t) = [(2 + gt+1)⌊(t + 3)/2⌋ − gt+2]− [(2 + gt−1)⌊(t + 1)/2⌋ − gt] = (2 + gt−1) + gt· ⌊(t + 1)/2⌋ − gt+1+ gt = 2 + gt· ⌊(t + 1)/2⌋ ⊓ ⊔ Hence: ξ(t) = Ψ (t + 2)− Ψ(t) Ψ (t) = 2 + gt· ⌊(t + 1)/2⌋ (2 + gt−1)· ⌊(t + 1)/2⌋ − gt (26) Proposition 5 ξ(t) is, after a few steps, definitively monotone decreasing.
We have to prove that ξ(t)− ξ(t + 2) > 0, at least for some t > t0. Let us
put6 α = ⌊(t + 1)/2⌋ and, in turn, 1 + α = ⌊(t + 3)/2⌋. Proof ξ(t)− ξ(t + 2) = 2 + gt· α (2 + gt−1)· α − gt− 2 + gt+2· (1 + α) (2 + gt+1)· (1 + α) − gt+2 > 0 We have just to prove that:
(2 + gt·α)·[(2+gt+1)·(1+α)−gt+2]−[2+gt+2·(1+α)]·[(2+gt−1)·α−gt] > 0
By elementary algebra it is:
2(2 + gt+1)(1 + α)− 2gt+2+ α(1 + α)(2 + gt+1)gt− αgtgt+2
− 2α(2 + gt−1) + 2gt− α(1 + α)(2 + gt−1)gt+2+ (1 + α)gtgt+2=
6
Actually, for t odd, ⌊(t + 1)/2⌋ = (t + 1)/2.
Proper strong-Fibonacci games 19
= α(1 + α)[(2 + gt−1+ gt)gt− (2 + gt−1)(gt+ gt+1)]+
+ (1 + α)[2(2 + gt+1) + gtgt+2]− α[gtgt+2+ 2(2 + gt−1)]− 2(gt+1+ gt) + 2gt=
= α(1 + α)[(gt2− gt−1gt+1− 2gt+1]+
+ (1 + α)[2(2 + gt+1) + gtgt+2]− α[2(2 + gt−1) + gtgt+2]− 2gt+1
and exploiting formula (16a):
= α(1 + α)(−1 − 2gt+1) + 2(2 + gt+1) + gtgt+2− 2gt+1+ +α[2(2 + gt+ gt−1)− 2(2 + gt−1)] = = α(1 + α)[−1 − 2(gt−1+ gt)] + (4 + gtgt+2) + 2αgt= = α2(−1 − 2gt−1− 2gt) + α(−1 − 2gt−1− 2gt+ 2gt) + 4 + gtgt+2= =−α(1 + α)(1 + 2gt−1)− 2α2gt+ 4 + gtgt+2= = 4− α(1 + α) − α(1 + α)2gt−1− 2α2gt+ gt(gt+ gt+1) = = 4− α(1 + α) − α(1 + α)2gt−1− 2α2gt+ gt(gt+ gt−1+ gt) = and finally: = 4 + gt(gt− 2α2) + gt−1(gt− 2α(1 + α)) + (gt2− α(1 + α)) (27) By the inequalities g2
t > gtfor all t > 1 and 2α(1 + α) > 2α2 > α(1 + α)
for any t odd greater than 1, a sufficient condition for all addends in formula (27) to be positive is that gt> 2α(1 + α); and it could be easily checked that
t gt Ψ (t) ξ(t) 3 3 5 1,6000 5 8 13 2,0000 7 21 39 2,2051 9 55 125 2,2160 11 144 402 2,1542 ... ... ... ... 21 ... ... 1,8967 31 ... ... 1,8001 41 ... ... 1,7531 51 ... ... 1,7254 61 ... ... 1,7071 71 ... ... 1,6942 81 ... ... 1,6845 ... ... ... ... 99 3.542·1017 106·1020 1,6721 199 ... 1.706·1040 1,6446 399 ... 215.817·1080 1,6312 599 ... 20.364.984·10120 1,6268 799 ... 17.058·10165 1,6246 999 ... 1.338.844·10205 1,6233 1499 ... ... 1,6215 1999 ... ... 1,6207 2999 ... ... 1,6198 3999 ... ... 1,6193 4399 ... ... 1,6191 ... ... ... ...
Table 2: Table of Ψ (t) and ξ(t) for some odd values of t.
8 Some games with special properties
PSF games with p = 2 or p = 3 have some special properties for the extreme values of z.
Lemma 7 For p = 2 and z = 1, we have, for any t > 2, one CSSF game whose profile is k(t, 1, 2) = (2, bk(t, 1)) = k(t, 1) = (2, 1t−3, 2, 11). Such games
have n = t + 2 non-dummy players as well as t + 2 minimal winning coalitions. The proof of this lemma has been given by Isbell ([6], p. 185), who studied these games in the context of the wider class of minimal winning parsimonious games. Such games are the subset of constant-sum homogeneous weighted majority games which have, for any given value n of non-dummy players, the smallest number (that is exactly n) of minimal winning coalitions. More details in [15].
Lemma 8 For p = 2 and for z =⌊(t + 1)/2⌋, we have, for any t > 2, one non-constant sum PSF game whose top player is a veto player7, i.e. belongs
to all min win coalitions.
Proof For t > 2, k(t,⌊(t + 1)/2⌋, 2) = (2, bk(t, ⌊(t + 1)/2⌋)) = (2, 1t−1) with 2
a lower bound for k1 (see Lemma 3). Indeed: t−1 X j=1 kjw∗j = t−1 X j=1 kjgj= 1 + t−1 X j=1 gj= gt+1− 1 < q = gt+1 7
On the point see [2], Theorem 2 and Corollary 1.
Proper strong-Fibonacci games 21
It is easy to check that it is the unique veto player. ⊓⊔ Corollary 2 For p = 3 and still for z = ⌊(t + 1)/2⌋, the top player is a semiveto (see [3], Sect. 2, def. 5), i.e. belongs to all min win coalitions except for the coalition of all other players.
Proof For t > 2, k(t,⌊(t + 1)/2⌋, 3) = (3, bk(t, ⌊(t + 1)/2⌋)) = (3, 1t−1) Indeed: t−1 X j=1 kjw∗j = t−1 X j=1 kjgj = 2 + t−1 X j=1 gj = gt+1= q
so that the coalition of all but the top player is the unique minimal winning coalition without the top player, which is then the (unique) semiveto. ⊓⊔ Lemma 9 For p = 1 and z =⌊(t − 1)/2⌋, we have, for any t > 2 odd, a PSF game in which the top player is semiveto.
Proof For t > 2 odd, k(t,⌊(t − 1)/2⌋, 1) = (1, bk(t, ⌊(t − 1)/2⌋)) = (1, 2, 1t−2)
Indeed: t−1 X j=1 kjw∗j = t−1 X j=1 kjgj = 2 + t−1 X j=1 gj = gt+1= q ⊓ ⊔ Remark 10 It is clear that, besides these cases, for t > 2 there are no other PSF games with veto or semiveto players.
9 A connection with Freixas-Kurz approach
As said in the introduction, apparently similar results have been recently ob-tained by Freixas-Kurz in [3], extending and generalizing results previously introduced by Freixas et al. [4]. Indeed, their paper [3] makes (in the title) explicit reference to the “golden number and Fibonacci sequences” in voting structures. Their main result too is a formula which gives the number of a class of voting games with different structures; such a formula too highlights the role of the golden section as a limiting value of the rate of growth of such number. But, even if the enumeration goal is in some sense the common core of their as well as of our paper, there are also relevant differences to be stressed. Indeed, they treat a large class of complete simple games, not necessarily proper, with at least one type of “special” players (vetoes, semivetoes, passers, semipassers and null), and do not restrict the attention to weighted majority games, re-quiring a fortiori neither homogeneity nor the “strong-Fibonacci property”.
On the contrary, we precisely regard the restricted class of simple proper homogeneous weighted majority games characterized by that specific prop-erty. Hence, it could be said that for this particular class of games we give a solution to the enumeration problem put by Freixas-Kurz (see the last but one paragraph of sect. 6 in [3]), as we provide a closed form formula for the number of our games as a function of t (see formulae (19a) and (19b)).
10 Conclusions
In this paper we define and study the class of proper strong-Fibonacci (PSF) games. We show that this class may be obtained through a generalization of constant-sum strong Fibonacci (CSSF) games. The latter are constant-sum homogeneous weighted majority games, whose minimal homogeneous repre-sentation is characterized by the following “strong Fibonacci property”: the whole sequence of type weights (in bottom-top order) and the minimal winning quota is the corresponding initial string of the “delayed” Fibonacci sequence. The generalization is obtained by relaxing the constant-sum condition, pre-serving the proper quality.
Indeed we find that each CSSF game is the seed of a set of PSF games (including the seed), whose profiles replicate the one of the seed in all but the first component (the number of the weakest non-dummy players). This one may be any positive integer (but 1 for a few “special” seeds) not greater than the first component of the seed. Then we provide a closed form formula for the number of PSF games as a function of the number t of non-dummy players’ types in the game. The growth rate of this function follows an exponential pattern. Analyzing the limiting behaviour of this rate (as t diverges) we find the key result of the paper: the ratio between the number of the PSF games for two consecutive values of t of the same parity converges to the golden section. This way, for this particular class of games, we solve the enumeration problem posed by Freixas-Kurz. We show that particular values of the parameters generate “special games”, i.e. games in which special types of players, according to Freixas-Kurz terminology, emerge (either one veto or one semiveto).
Compared to other weighted majority games, PSF games combine two spe-cific characteristics: the presence of some, or perhaps many, “peones” (players with minimum weight), along with an almost total ranking (with one tie at most) of all the other players, whose individual power grows at the speed of the Fibonacci sequence. Even if our paper is wholly theoretical, this feature could be particularly useful in applications to weighted voting systems. Verification of this conjecture on real data of national parliaments could be the object of further research.
References
1. Baron D.P., Ferejohn J.A., Bargaining in legislatures, American Political Science Re-view, 83, 1181-1206 (1989)
2. Fragnelli, V., Gambarelli, G., Gnocchi, N., Pressacco, F. and L. Ziani, Fibonacci Repre-sentations of Homogeneous Weighted Majority Games, Transactions on Computational Collective Intelligence XXIII, Springer Berlin Heidelberg, N.T. Nguyen, R. Kowalczyk, and J. Mercik (eds.), Lecture Notes in Computer Science, 9760, 162-171 (2016) 3. Freixas J., Kurz S., The golden number and Fibonacci sequences in the design of voting
structures, European Journal of Operational Research, 226, 246-257 (2013)
4. Freixas J., Molinero X., Roura S., Complete voting systems with two classes of voters: weightedness and counting, Annals of Operations Research, 193-1, 273-289, (2012)
Proper strong-Fibonacci games 23 5. H. M. Gurk, Isbell J. R. , Simple solutions, Contributions to the theory of games, Vol. IV, Annals of Mathematics Studies, no. 40, Princeton University Press, Princeton, N.J., pp. 247-265, (1959)
6. Isbell R., A class of majority games, Quarterly Journal of Mathematics, 7, 183-187 (1956)
7. Isbell R., On the enumeration of majority games, Math. Tables Aids Comput., 13, 21-28 (1959)
8. Kalandrakis T., Proposal rights and political power, American Journal of Political Sci-ence, 50-2, 441-448 (2006)
9. Krohn I., Sudh¨olter P., Directed and Weighted Majority Games, ZOR - Mathematical Methods of Operations Research, 42, 189-216, (1995)
10. Le Breton M., Montero M., Zaporozhets V., Voting power in the EU council of ministers and fair decision making in distributive politics, Mathematical Social Sciences, 63, 159-173 (2012)
11. Maschler M., Peleg B., A characterization, existence proof and dimension bounds for the kernel of a game, Pacific J. Math., 18-2, 289-328 (1966)
12. Montero M., Proportional Payoffs in Majority Games, available at SSRN: http://ssrn.com/abstract=1112626(2008)
13. Ostmann A., On the minimal representation of homogeneous games, International Jour-nal of Game Theory, 16, 69-81 (1987)
14. Peleg B., On weights of constant-sum majority games, SIAM J. Appl. Math., 16-3, 527-532 (1968)
15. Pressacco F., Plazzotta G. and L. Ziani, Bilateral symmetry and modified Pascal trian-gles in Parsimonious games, available on http://hal.archives-ouvertes.fr/ with validation no.: hal-00948123 (2013)
16. Pressacco F., Ziani L., A Fibonacci approach to weighted majority games, Journal of Game Theory, 4, 36-44 (2015)
17. Rosenm¨uller J., Weighted majority games and the matrix of Homogeneity, Operations Research, 28, 123-141 (1984)
18. Rosenm¨uller J., Homogeneous games: recursive structure and computation, Mathemat-ics of Operations Research, 12-2, 309-330 (1987)
19. Rosenm¨uller J., Sudh¨olter P., The nucleolus of homogeneous games with steps, Discrete Applied Mathematics, 50, 53-76 (1994)
20. Schmeidler D., The Nucleolus of a Characteristic Function Game, SIAM Journal on Applied Mathematics, 17-6, 1163-1170 (1969)
21. Von Neumann J. and O. Morgenstern, Theory of games and economic behaviour, Prince-ton University Press (1944)
