UN Security Council

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₁, . . . ,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

Example

Let us take ann×nrigid magic square with thresholdqandn² 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₁, . . . ,X_j;Y₁, . . . ,Y_j)

is called atrading transformif the coalitionsX₁, . . . ,X_j can be converted into the coalitionsY₁, . . . ,Y_j by rearranging players.

In Gabelman’s gameGab₃with 9 players

T = (Row₁,Row₂,Row₃;Col₁,Col₂,Col₃) 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₁, . . . ,X_j;Y₁, . . . ,Y_j)

exists whereX₁, . . . ,X_j are winning andY₁, . . . ,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²ⁿ-trade robust.

A criterion of weightedness

Definition

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

T = (X₁, . . . ,X_j;Y₁, . . . ,Y_j)

exists whereX₁, . . . ,X_j are winning andY₁, . . . ,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²ⁿ-trade robust.

Function f

Definition

LetGbe a simple game and

T = (X₁, . . . ,X_j;Y₁, . . . ,Y_j)

a trading transform whereX₁, . . . ,X_j are winning andY₁, . . . ,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₁, . . . ,X_j;Y₁, . . . ,Y_j)

a trading transform whereX₁, . . . ,X_j are winning andY₁, . . . ,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²ⁿ.

We prove:

Theorem (Gvozdeva-Slinko, 2009)

jn 2

k≤f(n)≤2^12(n+1)log2n.

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²ⁿ. We prove:

Theorem (Gvozdeva-Slinko, 2009)

jn 2

k≤f(n)≤2^12(n+1)log2n.

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²ⁿ. We prove:

Theorem (Gvozdeva-Slinko, 2009)

jn 2

k≤f(n)≤2^12(n+1)log2n.

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

The Idea of the Lower Bound

Consider weights(w₁,w₂,w₃,w₄,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₆,w₇,w₈,w₉) = (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ⁿ=T ×T ×. . .×T (ntimes).

Definition

Lete_i = (0, . . . ,1, . . . ,0), where the only nonzero element 1 is in theith position. Then a subsetI⊆Tⁿwill be called anideal inTⁿif for anyi=1,2, . . . ,n

(v∈Iandv+e_i∈Tⁿ) =⇒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ⁿ,

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ⁿ=T ×T ×. . .×T (ntimes).

Definition

Lete_i = (0, . . . ,1, . . . ,0), where the only nonzero element 1 is in theith position. Then a subsetI⊆Tⁿwill be called anideal inTⁿif for anyi=1,2, . . . ,n

(v∈Iandv+e_i∈Tⁿ) =⇒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ⁿ,

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₁, . . . ,X_j are winning and all coalitions Y₁, . . . ,Y_j are losing. Then the sequence

T = (X₁, . . . ,X_j;Y₁, . . . ,Y_j) is a certificate of non-weightedness iff

v_X1,Y1+. . .+v_Xj,Yj =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₁, . . . ,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

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?

The Fano plane game

We take P = {1,2, . . . ,7} and the lines X₁, . . . ,X₇ 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₁, . . . ,X7,P;X₁^c, . . . ,X₇^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₁, . . . ,X_j,P;Y₁, . . . ,Y_j,∅). (?)

We will call such a certificatepotent.

In the ideal, (?) is equivalent to

j

X

i=1

v_Xi,Yi +v_P,∅ =0.

wherev_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₁, . . . ,X_j,P;Y₁, . . . ,Y_j,∅). (?)

We will call such a certificatepotent.

In the ideal, (?) is equivalent to

j

X

i=1

v_Xi,Yi +v_P,∅ =0.

wherev_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_Xi,Yi + (1,1, . . . ,1) =0.

is the shortest potent certificate of absence of

non-weightedness. The sum of coefficients in everyv_Xi,Yi 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_Xi,Yi + (1,1, . . . ,1) =0.

is the shortest potent certificate of absence of

non-weightedness. The sum of coefficients in everyv_Xi,Yi 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^12(n+1)log2n.

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}ⁿ,{3,4,5}ⁿ⁺²,P;{2,3,5}³,{2,3,4}³, {2,3,6}, . . . ,{2,3,n}

| {z }

n−5

,{1,3,4},{1,3,5},{1,4,5}ⁿ⁻¹,∅}

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 vectorw∈Zⁿ₂and all its cyclic permutations. We will denote itC(w).

The Fano game is cyclic.

Theorem

Let the Hamming weight ofw∈Zⁿ₂is smaller than n/2. Then, if C(w)is proper, it is not roughly weighted.

Proof:The sequence

T = (X₁, . . . ,X_n,P, . . . ,P

| {z }

n−2k

;X₁^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 vectorw∈Zⁿ₂and all its cyclic permutations. We will denote itC(w).

The Fano game is cyclic.

Theorem

Let the Hamming weight ofw∈Zⁿ₂is smaller than n/2. Then, if C(w)is proper, it is not roughly weighted.

Proof:The sequence

T = (X₁, . . . ,X_n,P, . . . ,P

| {z }

n−2k

;X₁^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.

Thank you for your

attention!