# UN Security Council

N/A
N/A
Protected

Share "UN Security Council"

Copied!
58
0
0

Full text

(1)

### New Bounds for Simple Games

Department of Mathematics The University of Auckland

(joint work with Tatiana Gvozdeva)

(2)

### 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.

(3)

### 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.

(4)

### 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.

(5)

### 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.

(6)

### 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.

(7)

### 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 2P, 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=2P\W

and call coalitions fromLlosing.

(8)

### 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.

(9)

### 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

wi ≥q.

Such game is denoted

[q;w1, . . . ,wn].

(10)

### 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?

(11)

### 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?

(12)

### 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?

(13)

### 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?

(14)

### 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?

(15)

### 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.

(16)

### A Rigid Magic Square

Roughly Weighted Game: Gabelman Game Quota = 222222222

The quota is

q=222222222.

(17)

### Gabelman’s game Gab

n

Example

Let us take ann×nrigid magic square with thresholdqandn2 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.

(18)

Definition

The sequence of coalitions

T = (X1, . . . ,Xj;Y1, . . . ,Yj)

is called atrading transformif the coalitionsX1, . . . ,Xj can be converted into the coalitionsY1, . . . ,Yj by rearranging players.

In Gabelman’s gameGab3with 9 players

T = (Row1,Row2,Row3;Col1,Col2,Col3) is a trading transform.

(19)

(20)

### A criterion of weightedness

Definition

T = (X1, . . . ,Xj;Y1, . . . ,Yj)

exists whereX1, . . . ,Xj are winning andY1, . . . ,Yj 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.

(21)

### A criterion of weightedness

Definition

T = (X1, . . . ,Xj;Y1, . . . ,Yj)

exists whereX1, . . . ,Xj are winning andY1, . . . ,Yj 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.

(22)

### Function f

Definition

LetGbe a simple game and

T = (X1, . . . ,Xj;Y1, . . . ,Yj)

a trading transform whereX1, . . . ,Xj are winning andY1, . . . ,Yj 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).

(23)

### Function f

Definition

LetGbe a simple game and

T = (X1, . . . ,Xj;Y1, . . . ,Yj)

a trading transform whereX1, . . . ,Xj are winning andY1, . . . ,Yj 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).

(24)

### Bounds on function f

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

b√

nc ≤f(n)≤22n.

We prove:

jn 2

k≤f(n)≤212(n+1)log2n.

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

(25)

### Bounds on function f

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

b√

nc ≤f(n)≤22n. We prove:

jn 2

k≤f(n)≤212(n+1)log2n.

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

(26)

### Bounds on function f

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

b√

nc ≤f(n)≤22n. We prove:

jn 2

k≤f(n)≤212(n+1)log2n.

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

(27)

### The Idea of the Lower Bound

Consider weights(w1,w2,w3,w4,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 :(w6,w7,w8,w9) = (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.

(28)

### The Ideal of a Game

LetT ={−1,0,1}andTn=T ×T ×. . .×T (ntimes).

Definition

Letei = (0, . . . ,1, . . . ,0), where the only nonzero element 1 is in theith position. Then a subsetI⊆Tnwill be called anideal inTnif for anyi=1,2, . . . ,n

(v∈Iandv+ei∈Tn) =⇒v+ei ∈I.

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

vX,Y =χ(X)−χ(Y)∈Tn,

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

(29)

### The Ideal of a Game

LetT ={−1,0,1}andTn=T ×T ×. . .×T (ntimes).

Definition

Letei = (0, . . . ,1, . . . ,0), where the only nonzero element 1 is in theith position. Then a subsetI⊆Tnwill be called anideal inTnif for anyi=1,2, . . . ,n

(v∈Iandv+ei∈Tn) =⇒v+ei ∈I.

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

vX,Y =χ(X)−χ(Y)∈Tn,

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

(30)

### The Idea of the Upper Bound

Proposition

Let G be a game for which all coalitions X1, . . . ,Xj are winning and all coalitions Y1, . . . ,Yj are losing. Then the sequence

T = (X1, . . . ,Xj;Y1, . . . ,Yj) is a certificate of non-weightedness iff

vX1,Y1+. . .+vXj,Yj =0.

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

(31)

### 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 ∈2P

X

i∈X

wi >q =⇒X ∈W,

X

i∈X

wi <q =⇒X ∈L.

We say[q;w1, . . . ,wn]is arough voting representationforG.

(32)

### 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?

(33)

### 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?

(34)

### 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?

(35)

### 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?

(36)

### 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?

(37)

### The Fano plane game

We take P = {1,2, . . . ,7} and the lines X1, . . . ,X7 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 = (X1, . . . ,X7,P;X1c, . . . ,X7c,∅)

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

(38)

### A criterion of rough weightedness

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

T = (X1, . . . ,Xj,P;Y1, . . . ,Yj,∅). (?)

We will call such a certificatepotent.

In the ideal, (?) is equivalent to

j

X

i=1

vXi,Yi +vP,∅ =0.

wherevP,∅ = (1,1, . . . ,1).

(39)

### A criterion of rough weightedness

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

T = (X1, . . . ,Xj,P;Y1, . . . ,Yj,∅). (?)

We will call such a certificatepotent.

In the ideal, (?) is equivalent to

j

X

i=1

vXi,Yi +vP,∅ =0.

wherevP,∅ = (1,1, . . . ,1).

(40)

### 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).

(41)

### g(Fano) = 8

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

j

X

i=1

vXi,Yi + (1,1, . . . ,1) =0.

is the shortest potent certificate of absence of

non-weightedness. The sum of coefficients in everyvXi,Yi is at least−1. Hencej ≥7.

In particular,

g(7)≥8.

(42)

### g(Fano) = 8

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

j

X

i=1

vXi,Yi + (1,1, . . . ,1) =0.

is the shortest potent certificate of absence of

non-weightedness. The sum of coefficients in everyvXi,Yi is at least−1. Hencej ≥7.

In particular,

g(7)≥8.

(43)

### Bounds for g

2n+3≤g(n)<212(n+1)log2n.

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

(44)

### The lower bound for g(n)

Let us define a gameGn,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.

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.

(45)

### More Definitions

Definition

A simple gameGis calledproperif X ∈W =⇒Xc ∈L, strongif

X ∈L=⇒Xc∈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.

(46)

### More Definitions

Definition

A simple gameGis calledproperif X ∈W =⇒Xc ∈L, strongif

X ∈L=⇒Xc∈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.

(47)

### More Definitions

Definition

A simple gameGis calledproperif X ∈W =⇒Xc ∈L, strongif

X ∈L=⇒Xc∈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.

(48)

### More Definitions

Definition

A simple gameGis calledproperif X ∈W =⇒Xc ∈L, strongif

X ∈L=⇒Xc∈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.

(49)

### Cyclic games

Definition

A game withnplayers iscyclicif the characteristic vectors of minimal winning coalitions consist of a vectorw∈Zn2and all its cyclic permutations. We will denote itC(w).

The Fano game is cyclic.

Theorem

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

Proof:The sequence

T = (X1, . . . ,Xn,P, . . . ,P

| {z }

n−2k

;X1c, . . . ,Xnc,∅, . . . ,∅

| {z }

n−2k

)

is a potent certificate of non-weightedness.

(50)

### Cyclic games

Definition

A game withnplayers iscyclicif the characteristic vectors of minimal winning coalitions consist of a vectorw∈Zn2and all its cyclic permutations. We will denote itC(w).

The Fano game is cyclic.

Theorem

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

Proof:The sequence

T = (X1, . . . ,Xn,P, . . . ,P

| {z }

n−2k

;X1c, . . . ,Xnc,∅, . . . ,∅

| {z }

n−2k

)

is a potent certificate of non-weightedness.

(51)

### Projective Games

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

Prn,q= (PG(n,q),W),

whereW is defined by the set of minimal winning coalitions:

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

Theorem

Any projective game is not roughly weighted.

Proof:By Singer’s theoremPrn,qis cyclic.

(52)

### 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.

(53)

### 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.

(54)

### 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.

(55)

### 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.

(56)

### 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.

(57)

### 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.

(58)

## attention!

References

Related documents

compare two data forwarding schemes, one which forwards each packet along (i) a single path (SP) using a simple ARQ mechanism subject to some maximum re-transmission at- tempts and

Location based service applications are supported by APIs that give access both to simple objects that encapsulate raw geolocation data and other more complex objects that

last two schemes, which seek a high level of self sufficiency, performed well mainly because the particular model used in this study ignored fixed costs and

Characterise access structures that can carry an ideal secret sharing scheme.... Ideal Secret

 Classifying “Maximal subgroups of Sym(X) and Alt(X)” (X finite) required. • O’Nan—Scott Theorem for the

- Data can be stored in XML format for machine readable access by other applications.

While New Zealand was an early adopter of the worldwide trend to shift risks from employers to individuals in private superannuation schemes, lump sum or DC

• We can use our secret key s to encrypt a message which everyone can decrypt using our public key p!. Simpler notation:

In the book The empire of illusion: The end of literacy and the triumph of spectacle (Hedges, 2009), the author examines the illusion of literacy, the illusion of love, the

Expanded and new particular provisions will be incorporated into planning schemes to help ensure ESD design and development responses with clear performance standards

For applications, covering more categories, focusing on the consistent needs of mobile users, and improving application quality can allow. applications in the

Basics of Symmetric Association Schemes Imprimitive Cometric Schemes Lines with Few Angles.. (Symmetric, Commutative)

Massey University and PSB Academy, one of Singapore’s leading private education institutions, signed a memorandum of understanding in July to explore opportunities to

Effectiveness Outcome Mortality, morbidity, readmission, length of stay, patient functional status, quality of life / health status (e.g. SF-36). Indicator HbA1c, blood

• The security of the scheme is based on the number of possible latin squares containing the partial latin square defined by an unauthorized group of participants.. Rezny

Chaudhry and Seberry [4] developed secret sharing schemes based on critical sets of Room squares1. Both of these schemes are

The Δ f Hº can then be calculated empirically, either by an additivity scheme using group methods 2-32 or with a molecular mechanics force... Force fields have their origin

Drawing analysis particularly from the group's Sharing Map project, we explore how communal sharing initiatives like Share Sydney are constituting sharing practice and seeking to

different calculation methods are possible. Multiple solution schemes are necessary. Different strategies can be used. Openness of subtasks. Tasks with multiple solutions

(remembrance of what one has experienced) is not sealed off from other people's remembrances, from what Halbwachs called social or historical memory .31 The family too, has a

Le Corbusier on the Ville Radieuse: “In the Ford factory, everything is collaboration, unity of views, unity of purpose, a perfect convergence of the to- tality of gestures and

The use of QR codes in information security has been proposed for a variety of different purposes, such as for authenticating visual cryptography shares [22], e-voting

For grayscale images, we show that the perceived visual quality of the recovered image can be improved by using image filtering techniques prior to encrypting the secret image..