### New Bounds for Simple Games

Arkadii Slinko

Department of Mathematics The University of Auckland

(joint work with Tatiana Gvozdeva)

### Back in the USSR

Ustinov Brezhnev Kosygin

The three top state officials, the President, the Prime Minister, and the Minister of Defence,

all had “nuclear suitcases”. Any two of them could authorise a

launch of a nuclear warhead. No one could

do it alone.

### US Senate

United States Senaterules permit a senator, or a number of senators, to speak for as long as they wish and on any topic they choose, unless a supermajority of the Senate (60 Senators) brings debate to a close by invoking cloture.

### The European Economic Community

In 1958, theTreaty of Romeestablished the following voting system. The voters were: France, Germany, Italy, Belgium, the Netherlands and Luxembourg.

• France, Germany and Italy got 4 votes each,

• Belgium and the Netherlands got two votes,

• Luxembourg was given one vote.

Passage requires at least 9 of the 17 possible votes.

### UN Security Council

The 15 memberUN Security Councilconsists of five permanent and 10 non-permanent countries. A passage requires:

• approval of at least nine countries,

• subject to a veto by any one of the permanent members.

### Simple Games

Asimple gameis a mathematical object that is used to

describe the distribution of power among coalitions of players.

They have also been studied in a variety of other mathematical contexts under various names, e.g.:

• boolean or switching functions,

• threshold functions,

• hypergraphs,

• coherent structures,

• Sperner systems,

• abstract simplicial complexes.

A number of results have been discovered several times.

### Definition of a Simple Game

The setP={1,2, . . . ,n}denotes the set of players.

Definition

Asimple gameis a pairG= (P,W), whereW is a subset of
the power set 2^{P}, different from∅, which satisfies the

monotonicity condition:

if X ∈W and X ⊂Y ⊆P, then Y ∈W .

Coalitions fromW are calledwinning. We also denote
L=2^{P}\W

and call coalitions fromLlosing.

### Significant Publications

• von Neumann, J., and O. Morgenstern(1944)Theory of games and economic behavior. Princeton University Press. Princeton. NJ

• Shapley, L.S(1962)Simple games: an outline of the descriptive theory. Behavioral Science 7: 59–66.

• Winder, R.Threshold Logic, Doctoral Thesis, Princeton University, Princeton, 1962.

• Muroga, S.Threshold logic and Its Applications. Wiley Interscience, New York, 1971.

• Taylor, A.D., and W.S. Zwicker(1999)Simple games.

Princeton University Press. Princeton. NJ.

### Weighted Majority Games

Definition

A simple gameGis called aweighted majority gameif there
exists a weight functionw:P→R^{+}, whereR^{+}is the set of all
non-negative reals, and a real numberq, calledquota, such
that

X ∈W ⇐⇒X

i∈X

w_{i} ≥q.

Such game is denoted

[q;w_{1}, . . . ,wn].

### Weights for Games in Examples

Nuclear suitcases game:

[2;1,1,1].

American Senate game:

[60;1,1,1, . . . ,1]. European Community game:

[9;4,4,4,2,2,1]. UN Security Council game:

[39;7,7,7,7,7,1,1,1,1,1,1,1,1,1,1]. Does every simple game have weights?

### Weights for Games in Examples

Nuclear suitcases game:

[2;1,1,1].

American Senate game:

[60;1,1,1, . . . ,1].

European Community game:

[9;4,4,4,2,2,1]. UN Security Council game:

[39;7,7,7,7,7,1,1,1,1,1,1,1,1,1,1]. Does every simple game have weights?

### Weights for Games in Examples

Nuclear suitcases game:

[2;1,1,1].

American Senate game:

[60;1,1,1, . . . ,1].

European Community game:

[9;4,4,4,2,2,1].

UN Security Council game:

[39;7,7,7,7,7,1,1,1,1,1,1,1,1,1,1]. Does every simple game have weights?

### Weights for Games in Examples

Nuclear suitcases game:

[2;1,1,1].

American Senate game:

[60;1,1,1, . . . ,1].

European Community game:

[9;4,4,4,2,2,1].

UN Security Council game:

[39;7,7,7,7,7,1,1,1,1,1,1,1,1,1,1].

Does every simple game have weights?

### Weights for Games in Examples

Nuclear suitcases game:

[2;1,1,1].

American Senate game:

[60;1,1,1, . . . ,1].

European Community game:

[9;4,4,4,2,2,1].

UN Security Council game:

[39;7,7,7,7,7,1,1,1,1,1,1,1,1,1,1].

Does every simple game have weights?

### Rigid Magic Squares

On the right you see a magic square. A rigid magic square will for someq have:

• The sum in every row and in every column is equal toq.

• No other subset of the numbers has the sum equal toq.

Such numberq will be called athreshold.

### A Rigid Magic Square

Roughly Weighted Game: Gabelman Game Quota = 222222222

The quota is

q=222222222.

### Gabelman’s game Gab

_{n}

Example

Let us take ann×nrigid magic square with thresholdqandn^{2}
of players, one for each cell. We assign to a player the weight in
his cell.

• Coalitions whose weight is>qare winning.

• Coalitions whose weight is<qare losing.

• Rows are winning.

• Columns are losing.

No system of weights can be found for this game.

### Trading transform. Example

Definition

The sequence of coalitions

T = (X_{1}, . . . ,X_{j};Y_{1}, . . . ,Y_{j})

is called atrading transformif the coalitionsX_{1}, . . . ,X_{j} can be
converted into the coalitionsY_{1}, . . . ,Y_{j} by rearranging players.

In Gabelman’s gameGab_{3}with 9 players

T = (Row_{1},Row_{2},Row_{3};Col_{1},Col_{2},Col_{3})
is a trading transform.

### Yet another example of trading transform

### A criterion of weightedness

Definition

A simple gameGisk-trade robustif for allj≤k no trading transform

T = (X_{1}, . . . ,X_{j};Y_{1}, . . . ,Y_{j})

exists whereX_{1}, . . . ,X_{j} are winning andY_{1}, . . . ,Y_{j} are losing. It
is said to betrade robustif it isk-trade robustfor everyk.

Theorem (Taylor & Zwicker, 1992)

For a simple game G the following is equivalent: 1. G is weighted.

2. G is trade robust.
3. G is2^{2}^{n}-trade robust.

### A criterion of weightedness

Definition

A simple gameGisk-trade robustif for allj≤k no trading transform

T = (X_{1}, . . . ,X_{j};Y_{1}, . . . ,Y_{j})

exists whereX_{1}, . . . ,X_{j} are winning andY_{1}, . . . ,Y_{j} are losing. It
is said to betrade robustif it isk-trade robustfor everyk.

Theorem (Taylor & Zwicker, 1992)

For a simple game G the following is equivalent:

1. G is weighted.

2. G is trade robust.

3. G is2^{2}^{n}-trade robust.

### Function f

Definition

LetGbe a simple game and

T = (X_{1}, . . . ,X_{j};Y_{1}, . . . ,Y_{j})

a trading transform whereX_{1}, . . . ,X_{j} are winning andY_{1}, . . . ,Y_{j}
are losing (i.e.,Gis notj-trade robust). Then we callT a
certificate of non-weightedness.

Definition

IfGis weighted we setf(G) =∞. Otherwise,f(G)is the length of the shortest certificate of non-weightedness. For games with nplayers we define

f(n) = max

f(G)6=∞f(G).

### Function f

Definition

LetGbe a simple game and

T = (X_{1}, . . . ,X_{j};Y_{1}, . . . ,Y_{j})

a trading transform whereX_{1}, . . . ,X_{j} are winning andY_{1}, . . . ,Y_{j}
are losing (i.e.,Gis notj-trade robust). Then we callT a
certificate of non-weightedness.

Definition

IfGis weighted we setf(G) =∞. Otherwise,f(G)is the length of the shortest certificate of non-weightedness. For games with nplayers we define

f(n) = max

f(G)6=∞f(G).

### Bounds on function f

In terms of the functionf the results known before us can be summarised as follows:

b√

nc ≤f(n)≤2^{2}^{n}.

We prove:

Theorem (Gvozdeva-Slinko, 2009)

jn 2

k≤f(n)≤2^{1}^{2}^{(n+1)}^{log}^{2}^{n}.

Our proof for the lower bound uses results ofFishburnand Conder & Slinkoon comparative probability orders.

### Bounds on function f

In terms of the functionf the results known before us can be summarised as follows:

b√

nc ≤f(n)≤2^{2}^{n}.
We prove:

Theorem (Gvozdeva-Slinko, 2009)

jn 2

k≤f(n)≤2^{1}^{2}^{(n+1)}^{log}^{2}^{n}.

Our proof for the lower bound uses results ofFishburnand Conder & Slinkoon comparative probability orders.

### Bounds on function f

In terms of the functionf the results known before us can be summarised as follows:

b√

nc ≤f(n)≤2^{2}^{n}.
We prove:

Theorem (Gvozdeva-Slinko, 2009)

jn 2

k≤f(n)≤2^{1}^{2}^{(n+1)}^{log}^{2}^{n}.

Our proof for the lower bound uses results ofFishburnand Conder & Slinkoon comparative probability orders.

### The Idea of the Lower Bound

Consider weights(w_{1},w_{2},w_{3},w_{4},w5) = (1,2,5,6,10). Then:

Equality Total weight

13∼4 6

14∼23 7

25∼134 12

34∼15 11

−→

Equality Total weight
136∼46 6+106=112
147∼237 7+105=112
258∼1348 12+100=112
349∼159 11+101=112
We add :(w_{6},w_{7},w_{8},w_{9}) = (106,105,100,101)and define

• Coalitions whose weight is>112are winning.

• Coalitions whose weight is<112are losing.

• 46, 237, 1348, 159 are winning.

• 136, 147, 258, 349 are losing.

This gives usf(9)≥4. Gabelman’s example givesf(9)≥3.

### The Ideal of a Game

LetT ={−1,0,1}andT^{n}=T ×T ×. . .×T (ntimes).

Definition

Let**e**_{i} = (0, . . . ,1, . . . ,0), where the only nonzero element 1 is
in theith position. Then a subsetI⊆T^{n}will be called anideal
inT^{n}if for anyi=1,2, . . . ,n

(v∈Iand**v**+**e**_{i}∈T^{n}) =⇒**v**+**e**_{i} ∈I.

Any gameG= (P,W)is associated with an ideal. For any pair (X,Y), whereX ∈W andY ∈L, we define

**v**_{X,Y} =χ(X)−χ(Y)∈T^{n},

whereχ(X)andχ(Y)are the characteristic vectors ofX andY, respectively. The set of all such vectors we will denoteI(G)and call theidealofG.

### The Ideal of a Game

LetT ={−1,0,1}andT^{n}=T ×T ×. . .×T (ntimes).

Definition

Let**e**_{i} = (0, . . . ,1, . . . ,0), where the only nonzero element 1 is
in theith position. Then a subsetI⊆T^{n}will be called anideal
inT^{n}if for anyi=1,2, . . . ,n

(v∈Iand**v**+**e**_{i}∈T^{n}) =⇒**v**+**e**_{i} ∈I.

Any gameG= (P,W)is associated with an ideal. For any pair (X,Y), whereX ∈W andY ∈L, we define

**v**_{X,Y} =χ(X)−χ(Y)∈T^{n},

whereχ(X)andχ(Y)are the characteristic vectors ofX andY, respectively. The set of all such vectors we will denoteI(G)and call theidealofG.

### The Idea of the Upper Bound

Proposition

Let G be a game for which all coalitions X_{1}, . . . ,X_{j} are winning
and all coalitions Y_{1}, . . . ,Y_{j} are losing. Then the sequence

T = (X_{1}, . . . ,X_{j};Y_{1}, . . . ,Y_{j})
is a certificate of non-weightedness iff

**v**_{X}_{1}_{,Y}_{1}+. . .+**v**_{X}_{j}_{,Y}_{j} =**0.**

This reduces the problem to Linear Algebra. Further details are technical.

### Rough weights

Definition

A simple gameGis calledroughly weightedif there exists a
weight functionw:P →R^{+}, not identically equal to zero, and a
positive real numberq, calledquota, such that forX ∈2^{P}

X

i∈X

w_{i} >q =⇒X ∈W,

X

i∈X

w_{i} <q =⇒X ∈L.

We say[q;w_{1}, . . . ,w_{n}]is arough voting representationforG.

### An Example of Roughly Weighted Majority Game

This Kingdom has 9 provinces. A passage requires approval of at least three provinces, not all of which are neighbours.

We assign weight 1 to every province. Then:

• Coalitions whose weight is>3 are winning.

• Coalitions whose weight is<3 are losing.

Gabelman’s games are not weighted but they are roughly weighted. So are our examples. Does every simple game have rough weights?

### An Example of Roughly Weighted Majority Game

This Kingdom has 9 provinces. A passage requires approval of at least three provinces, not all of which are neighbours.

We assign weight 1 to every province. Then:

• Coalitions whose weight is>3 are winning.

• Coalitions whose weight is<3 are losing.

Gabelman’s games are not weighted but they are roughly weighted. So are our examples. Does every simple game have rough weights?

### An Example of Roughly Weighted Majority Game

This Kingdom has 9 provinces. A passage requires approval of at least three provinces, not all of which are neighbours.

We assign weight 1 to every province. Then:

• Coalitions whose weight is>3 are winning.

• Coalitions whose weight is<3 are losing.

Gabelman’s games are not weighted but they are roughly weighted. So are our examples. Does every simple game have rough weights?

### An Example of Roughly Weighted Majority Game

We assign weight 1 to every province. Then:

• Coalitions whose weight is>3 are winning.

• Coalitions whose weight is<3 are losing.

### An Example of Roughly Weighted Majority Game

We assign weight 1 to every province. Then:

• Coalitions whose weight is>3 are winning.

• Coalitions whose weight is<3 are losing.

### The Fano plane game

We take P = {1,2, . . . ,7} and
the lines X_{1}, . . . ,X_{7} as minimal
winning coalitions:

{1,2,3},{1,4,5},{1,6,7},{2,5,7}, {3,4,7},{3,5,6},{2,4,6}.

Then the sequence

T = (X_{1}, . . . ,X7,P;X_{1}^{c}, . . . ,X_{7}^{c},∅)

is a certificate of non-weightedness ofG. But it actually shows more: the absence of rough weights.

### A criterion of rough weightedness

Theorem (Gvozdeva-Slinko, 2009)

A game G is roughly weighted if for no j there exists a certificate of non-weightedness of the form

T = (X_{1}, . . . ,X_{j},P;Y_{1}, . . . ,Y_{j},∅). (?)

We will call such a certificatepotent.

In the ideal, (?) is equivalent to

j

X

i=1

**v**_{X}_{i}_{,Y}_{i} +**v**_{P,∅} =**0.**

where**v**_{P,∅} = (1,1, . . . ,1).

### A criterion of rough weightedness

Theorem (Gvozdeva-Slinko, 2009)

A game G is roughly weighted if for no j there exists a certificate of non-weightedness of the form

T = (X_{1}, . . . ,X_{j},P;Y_{1}, . . . ,Y_{j},∅). (?)

We will call such a certificatepotent.

In the ideal, (?) is equivalent to

j

X

i=1

**v**_{X}_{i}_{,Y}_{i} +**v**_{P,∅} =**0.**

where**v**_{P,∅} = (1,1, . . . ,1).

### Function g

This theorem leads to the introduction of another functiong.

Definition

Let the number of players ben. IfGis roughly weighted, then g(G) =∞. Else, letg(G)be the length of the shortest potent certificate of non-weightedness and define

g(n) = max

g(G)6=∞g(G).

### g(Fano) = 8

We saw thatg(Fano)≤8. However, it cannot be smaller than 8. Suppose

j

X

i=1

**v**_{X}_{i}_{,Y}_{i} + (1,1, . . . ,1) =**0.**

is the shortest potent certificate of absence of

non-weightedness. The sum of coefficients in every**v**_{X}_{i}_{,Y}_{i} is at
least−1. Hencej ≥7.

In particular,

g(7)≥8.

### g(Fano) = 8

We saw thatg(Fano)≤8. However, it cannot be smaller than 8. Suppose

j

X

i=1

**v**_{X}_{i}_{,Y}_{i} + (1,1, . . . ,1) =**0.**

is the shortest potent certificate of absence of

non-weightedness. The sum of coefficients in every**v**_{X}_{i}_{,Y}_{i} is at
least−1. Hencej ≥7.

In particular,

g(7)≥8.

### Bounds for g

Theorem (Gvozdeva-Slinko, 2009) For n≥5

2n+3≤g(n)<2^{1}^{2}^{(n+1)}^{log}^{2}^{n}.

The lower bound is proved by constructing a series of examples. The upper bound is the same as for functionf.

### The lower bound for g(n)

Let us define a gameG_{n,2}= ([n],W)for which the following
holds:

• {1,2} ∈W and{3,4,5} ∈W,

• If|S|>3, thenS∈W.

Note that all losing coalitions have cardinality of at most 3.

The trading transform

T ={{1,2}^{n},{3,4,5}^{n+2},P;{2,3,5}^{3},{2,3,4}^{3},
{2,3,6}, . . . ,{2,3,n}

| {z }

n−5

,{1,3,4},{1,3,5},{1,4,5}^{n−1},∅}

is a potent certificate of non-weightedness of length 2n+3.

### More Definitions

Definition

A simple gameGis calledproperif
X ∈W =⇒X^{c} ∈L,
strongif

X ∈L=⇒X^{c}∈W,

and aconstant sum gameifGis both proper and strong.

• Nuclear sutcases game and EEC: constant sum games

• American Senat and UN Security Council: proper but not strong.

• Gamelman’s game: strong but not proper.

### More Definitions

Definition

A simple gameGis calledproperif
X ∈W =⇒X^{c} ∈L,
strongif

X ∈L=⇒X^{c}∈W,

and aconstant sum gameifGis both proper and strong.

• Nuclear sutcases game and EEC: constant sum games

• American Senat and UN Security Council: proper but not strong.

• Gamelman’s game: strong but not proper.

### More Definitions

Definition

A simple gameGis calledproperif
X ∈W =⇒X^{c} ∈L,
strongif

X ∈L=⇒X^{c}∈W,

and aconstant sum gameifGis both proper and strong.

• Nuclear sutcases game and EEC: constant sum games

• American Senat and UN Security Council: proper but not strong.

• Gamelman’s game: strong but not proper.

### More Definitions

Definition

A simple gameGis calledproperif
X ∈W =⇒X^{c} ∈L,
strongif

X ∈L=⇒X^{c}∈W,

and aconstant sum gameifGis both proper and strong.

• Nuclear sutcases game and EEC: constant sum games

• American Senat and UN Security Council: proper but not strong.

• Gamelman’s game: strong but not proper.

### Cyclic games

Definition

A game withnplayers iscyclicif the characteristic vectors of
minimal winning coalitions consist of a vector**w**∈Z^{n}_{2}and all its
cyclic permutations. We will denote itC(w).

The Fano game is cyclic.

Theorem

Let the Hamming weight of**w**∈Z^{n}_{2}is smaller than n/2. Then, if
C(w)is proper, it is not roughly weighted.

Proof:The sequence

T = (X_{1}, . . . ,X_{n},P, . . . ,P

| {z }

n−2k

;X_{1}^{c}, . . . ,X_{n}^{c},∅, . . . ,∅

| {z }

n−2k

)

is a potent certificate of non-weightedness.

### Cyclic games

Definition

A game withnplayers iscyclicif the characteristic vectors of
minimal winning coalitions consist of a vector**w**∈Z^{n}_{2}and all its
cyclic permutations. We will denote itC(w).

The Fano game is cyclic.

Theorem

Let the Hamming weight of**w**∈Z^{n}_{2}is smaller than n/2. Then, if
C(w)is proper, it is not roughly weighted.

Proof:The sequence

T = (X_{1}, . . . ,X_{n},P, . . . ,P

| {z }

n−2k

;X_{1}^{c}, . . . ,X_{n}^{c},∅, . . . ,∅

| {z }

n−2k

)

is a potent certificate of non-weightedness.

### Projective Games

LetPG(n,q), whereq =p^{r}, be the projectiven-dimensional
space for a primep.After Richardson (1956) we define
projective game

Pr_{n,q}= (PG(n,q),W),

whereW is defined by the set of minimal winning coalitions:

W^{m} ={all(n−1)-dimensional subspaces ofPG(n,q)}.

Theorem

Any projective game is not roughly weighted.

Proof:By Singer’s theoremPrn,qis cyclic.

### Weightedness of Small Games

Theorem (Shapley, 1962)

The following games are weighted:

• every game with 3 or less players,

• every strong or proper game with 4 or less players,

• every constant sum game with 5 or less players.

### Rough Weightedness of Small Games

Theorem (Gvozdeva-Slinko, 2009) The following games are roughly weighted:

• every game with 4 or less players,

• every strong or proper game with 5 or less players,

• every constant sum game with 6 or less players.

### Possible Directions of Further Research

• To improve bounds forf(n)andg(n);

• Applications to secret sharing schemes, in particular: Which simple games can be access structures of ideal secret sharing schemes?

• Applications to threshold abstract simplicial complexes;

• Applications to effectivity functions.

### Possible Directions of Further Research

• To improve bounds forf(n)andg(n);

• Applications to secret sharing schemes, in particular:

Which simple games can be access structures of ideal secret sharing schemes?

• Applications to threshold abstract simplicial complexes;

• Applications to effectivity functions.

### Possible Directions of Further Research

• To improve bounds forf(n)andg(n);

• Applications to secret sharing schemes, in particular:

Which simple games can be access structures of ideal secret sharing schemes?

• Applications to threshold abstract simplicial complexes;

• Applications to effectivity functions.

### Possible Directions of Further Research

• To improve bounds forf(n)andg(n);

• Applications to secret sharing schemes, in particular:

Which simple games can be access structures of ideal secret sharing schemes?

• Applications to threshold abstract simplicial complexes;

• Applications to effectivity functions.