A Note on Asymmetric Power Index for Voting Games

Presentation on theme: "A Note on Asymmetric Power Index for Voting Games"— Presentation transcript:

1 A Note on Asymmetric Power Index for Voting Games
University of Tokyo Tomomi Matsui University of Tokyo Yoshikata Uehara

2 v: 2N →R: characteristic function (N,v): characteristic function game
voting game N={1,2,…,n}: set of players v: 2N →R: characteristic function (N,v): characteristic function game voting game v: 2N →{0,1} (simple game), ∀S⊆∀T⊆N, v（S）≦v（T）. game for analyzing (political) voting system

3 coalition: subset of players
voting game coalition: subset of players (empty set is also called a coalition, here) winning coalition: v(S)=1 losing coalition: v(S)=0 W: family of all the winning coalitions L: family of all the losing coalitions (clearly W ∪ L = 2N ) voting game: G=(N,W): (players, winning coalitions) ∀S⊆∀T∈W, S∈W.

4 power index: quantitative measure of power for players of voting game
(symmetric) power index Shapley-Shubik (1953,1954) Banzhaf (1965) Deegan-Packel (1978) defined only by the characteristic function Political voting system: each voter has his/her own ideology ⇒ non-symmetry among voters

5 Rabinowitz-MacDonald (1986) Ono-Muto (1997)
asymmetric index asymmetric index Shapley-Owen (1971) Rapoport-Golan (1985) Israeli Knesset Frank-Shapley (1981) U. S. Supreme Court Rabinowitz-MacDonald (1986) U. S. Presidential Elections Ono-Muto (1997) House of Councilors in Japan introduce ideology (profile) space, each player has a position in ideology space,

6 main result: asymmetric index for voting game
(1) without the definition of ideology space, (2) use the profile of issue distribution directly, (3) generalization of Shapley-Shubik index, and Deegan-Packel index, (4) axiomatic characterization.

7 profile of issue distribution
characterize each issue by the coalition consists of players (parties) who agree with the issue issue distribution = probability distribution defined on winning coalitions (losing coalition = rejected issue = issue blocked by complement coalition = (winning) complement coalition) Assumption: v(S)+v(N-S) ≧１ profile: p:W →[0,1] satisfying {∑p(S)｜S∈W}=1

8 G[E]=(N,W[E]) sub-game: W[E]={F ⊆N｜F∩E ∈W} φ[G’]：N→[0,1]：
new index E: winning coalition G[E]=(N,W[E]) sub-game: W[E]={F ⊆N｜F∩E ∈W} φ[G’]：N→[0,1]： Shapley-Shubik index of a voting game G’ φ[E]： N→[0,1]： Shapley-Shubik index of the sub-game G[E] new index: η(G,p)={∑p(E) φ[E] ｜E∈W} G=(N,W) : sub-game, p:W →[0,1] : profile

9 explanation from game theoretical point of view
new index: η(G,p)={∑p(E) φ[E] ｜E∈W} G[E]=(N,W[E]) : sub-game, p:W →[0,1] : profile φ[E] :Shapley-Shubik index of sub-game = imputation corresponding to Shapley value ∑p(E) φ[E] = ∑(probability) (imputation) = (expectation of imputations w.r.t. Shapley value and issue distribution)

10 η(G,p)={∑p(E) φ[E] ｜E∈W} Shapley-Shubik index:
special case new index: η(G,p)={∑p(E) φ[E] ｜E∈W} Shapley-Shubik index: profile p(F )=1 iff F =N Deegan-Packel index: profile p(F)=1/|Wmin| iff F is a minimal winning coalition Wmin : family of minimal winning coalitions (p(F)= 0 (otherwise) )

11 Analysis of House of Councilors in Japan

12 House of Councilors in Japan
6 (non-minor) parties Liberal Democratic Party (LDP): 109 Social Democratic Party (SDPJ): 74 Komeito (Komei): 21 Japan Communist Party (JCP): 14 Democratic Socialist Party (DSP): 10 Rengo: 12 total: 240

13 profile of issue distribution
characterize issues by the coalition (8 issues) House of Councilors in Japan （ ） party： LDP SDPJ Komei JCP DSP Rengo ：number seats： Y Y Y N Y Y ： 85 Y N N N N N ： 18 Y N N N Y N ： 9 Y N Y N Y Y ： 6 N Y Y Y Y Y ： 6 Y N Y N Y N ： 5 Y N Y Y Y Y ： 3 Y Y Y N Y N ： 1 profiles of non-unanimous votes

14 weighted majority game
players: N ={1,2,…,n} weighted majority game: [q; w1,w2,…,wn] q: quota, wi: voting weight (seats) of player (party) i coalition S is winning ⇔ {∑ wi| i ∈S}≧q Assumption: (1/2) (w1+w2+・･･＋wn )<q≦ (w1+w2+・･･＋wn )

15 profile of issue distribution
sub-games profile of issue distribution party： LDP SDPJ Komei JCP DSP Rengo ： number seats： Y Y Y N Y Y ： 85 (winning) Y N N N N N ： 18 (loosing) Y N ・ ・ ・ ・ ・ ・ Y N ： 9 (loosing) ・ ・ ・ ・ ・ ・ generate sub-games （121=quota） [ 121; 109, 74, , 0, , 12 ] [ 121; 0, 74, , 14, , 12 ] [ 121; 0, 74, ・ ・ ・ ・ ・ ・ 0, 12 ]

16 calculation of indices
generated sub-games （121=quota） party： LDP SDPJ Komei JCP DSP Rengo ： number seats： [ 121; 109, 74, , 0, , 12 ] 85 [ 121; 0, 74, , 14, , 12 ] 18 [ 121; 0, 74, ・ ・ ・ ・ ・ ・ 0, 12 ] ・ ・ ・ ・ ・ ・ Shapley-Shubik index of each sub-game （issue total=133） ( )×(85/133） ( )×(18/133） ( ・ ・ ・ ・ ・ ・ )×( 9/133) ＋ ・ ・ ・ ・ ・ ・ ( )

17 comparison with other indices
party： LDP SDPJ Komei JCP DSP Rengo seats: S-S ： Bz ： D-P ： S-O1： S-O2： O-M1: O-M2: O-M3: O-M4: O-M5: M-U :

18 Axiom1 [∀F， v(F)=v(F+i)] → η(G,p)i = 0
Axiom2 [i,j ∈E, [∀F， v(F+i ｰ j)=v(Fｰ i+j)]] → η(G,pE)i = η(G,pE) j Axiom3 ∀ E, η(G1, pE)+η(G2, pE) =η(G1 ∧G2, pE)+η(G1 ∨ G2, pE) Axiom4 sum total of indices =1 Axiom5 (0≦∀λ≦1), η(G, λp+(1‐λ)p’) =λη(G1, p)+ (1‐λ) η(G, p’) Axiom6 ∀ E, η(G, pE) =η(G [E ], pE)

19 index： (η(G,p)1, η(G,p)2,...,η(G,p)n)
Axiom (1) G=(N,v): voting game profile p : index： (η(G,p)1, η(G,p)2,...,η(G,p)n) Axiom1 [∀F， v(F) = v(F+i)] → η(G,p)i = 0 （dummy player) Axiom2 [i,j ∈E , [∀F， v(F+i ｰ j)=v(Fｰ i+j)]] → η(G,pE)i = η(G,pE) j simple profile pE : [pE(F) =1 ⇔F=E ] (symmetric player and simple profile)

20 Axiom2 (symmetric players and simple profile)
Axiom1 (dummy player) Axiom2 (symmetric players and simple profile) Axiom3 ∀ E ∈W, η(G1, pE)+η(G2, pE) =η(G1 ∧G2, pE)+η(G1 ∨ G2, pE) (additivity of games with simple profile) simple profile pE : [pE(F) =1 ⇔F=E ] Axiom4 sum total of indices =1 Axiom5 (0≦∀λ≦1), η(G, λp+(1‐λ)p’) =λη(G1, p)+ (1‐λ) η(G, p’) (linearity with respect to the profile)

21 Axiom2 (symmetric players and simple profile)
Axiom1 (dummy player) Axiom2 (symmetric players and simple profile) Axiom3 (additivity of games with simple profile) Axiom4 sum total of indices =1 Axiom5 (linearity with respect to the profile) Axiom6 ∀ E∈W,η(G, pE) =η(G [E ], pE) (indices of simple profile game = indices of simple profile sub-game restricted to the corresponding coalition = outsiders do not have any power) simple profile pE : [pE(F) =1 ⇔F=E ]

22 Axiom1 [∀F， v(F)=v(F+i)] → η(G,p)i = 0
Axiom2 [i,j ∈E, [∀F， v(F+i ｰ j)=v(Fｰ i+j)]] → η(G,pE)i = η(G,pE) j Axiom3 ∀ E, η(G1, pE)+η(G2, pE) =η(G1 ∧G2, pE)+η(G1 ∨ G2, pE) Axiom4 sum total of indices =1 Axiom5 (0≦∀λ≦1), η(G, λp+(1‐λ)p’) =λη(G1, p)+ (1‐λ) η(G, p’) Axiom6 ∀ E, η(G, pE) =η(G [E ], pE) Theorem: ηindex is characterized by the above axioms

23 propose asymmetric index without definition of ideology space
Conclusion propose asymmetric index without definition of ideology space generalization of S-S index and D-P index analyze House of Councilors in Japan our index is similar to O-M index axiomatic characterization of our index axioms for S-S index +（Axiom5）linearity on profile +（Axiom6）index for the case of simple profile Axiom5 (0≦∀λ≦1), η(G, λp+(1‐λ)p’) =λη(G1, p)+ (1‐λ) η(G, p’) Axiom6 ∀ E, η(G, pE) =η(G [E ], pE)

24 END

25 各政党を点(n次元ベクトル）として配置する. 投票行動の近い政党は近い位置にある.
イデオロギー空間 イデオロギー空間： n次元ユークリッド空間. 各政党を点(n次元ベクトル）として配置する. 方法は後に述べる. 投票行動の近い政党は近い位置にある. 議案ベクトル(Rabinowitz-Macdonald)： 議案は1つの方向として与えられる. O A党 D党 B党 C党 議案 j に賛成 議案 j に反対

26 議案ベクトルに沿った順に提携が形成される. {C}, {C,B}, {C,B,D},{C,B,D,A} 敗北→ 敗北→ 勝利 → 勝利
ピヴォット 議案ベクトルに沿った順に提携が形成される. {C}, {C,B}, {C,B,D},{C,B,D,A} 敗北→ 敗北→ 勝利 → 勝利 D:ピヴォット ピヴォット：敗北から勝利に変化させた政党 O A党 D党 B党 C党 議案 j に賛成 議案 j に反対

27 (Rabinowitz-Macdonald) （1）投票行動表を用いて 政党をイデオロギー空間中に配置する (2) 議案ベクトルを
非対称投票力指数の計算 非対称投票力指数の計算法 (Rabinowitz-Macdonald) （1）投票行動表を用いて 政党をイデオロギー空間中に配置する (2) 議案ベクトルを 適当な方法で確率的に発生させる (3) 政党i の指数＝政党i がピヴォットとなる確率 を計算する

28 Rabinowitz-Macdonald：因子分析を用いる Ono-Muto ：数量化III類を用いる
政党の配置と議案ベクトルの発生 (1) 投票行動表を用いて 政党をイデオロギー空間中に配置する Rabinowitz-Macdonald：因子分析を用いる Ono-Muto ：数量化III類を用いる (2) 議案ベクトル（または点）の発生 Shapley：各方向が等確率で発生する Rabinowitz-Macdonald：投票行動表の議案もイデオロギー空間中に方向として配置, 過去の議案の非負結合ベクトルを等確率で発生 Ono-Muto：投票行動表の議案もイデオロギー空間中に点として配置, 過去の議案数に比例して発生

29 (1) 既往の方法：投票行動表から各政党のイデオロギー空間での配置を構築
研究の動機 既往の方法： 投票行動表 → イデオロギー空間 →指数 本発表の方法： 投票行動表 → → → 指数 (1) 既往の方法：投票行動表から各政党のイデオロギー空間での配置を構築 (2) A党とB党が同じ投票行動を示す議案が多い→A,B党は似たイデオロギーを持つ→指数 (3) 各議案の発生比率→各提携の発生確率 →(非対称)投票力指数

30 Y Y Y N Y Y ： 85 (勝利) Y N N N N N ： 18 (敗北)
新しい指数(1) 投票行動表 政党： 自民 社会 公明 共産 民社 連合 ： 議案数 議席： Y Y Y N Y Y ： 85 (勝利) Y N N N N N ： 18 (敗北) Y N ・ ・ ・ ・ ・ ・ Y N ： 9 (敗北) ・ ・ ・ ・ ・ ・ 重み付き多数決ゲームを生成 （121=割当数） [ 121; 109, 74, , 0, , 12 ] [ 121; 0, 74, , 14, , 12 ] [ 121; 0, 74, ・ ・ ・ ・ ・ ・ 0, 12 ]

31 Shapley-Shubik 指数を計算 （総議案数=133） (.75 .083 .083 0 0 .083)×(85/133）
新しい指数(2) 重み付き多数決ゲームを生成 政党： 自民 社会 公明 共産 民社 連合 ： 議案数 議席： [ 121; 109, 74, , 0, , 12 ] 85 [ 121; 0, 74, , 14, , 12 ] 18 [ 121; 0, 74, ・ ・ ・ ・ ・ ・ 0, 12 ] ・ ・ ・ ・ ・ ・ Shapley-Shubik 指数を計算 （総議案数=133） ( )×(85/133） ( )×(18/133） ( ・ ・ ・ ・ ・ ・ )×( 9/133) ＋ ・ ・ ・ ・ ・ ・ ( )

32 他の指数との比較 指数 ： 自民 社会 公明 共産 民社 連合 S-S ： Bz ： D-P ： S-O1： S-O2： O-M1: O-M2: O-M3: O-M4: O-M5: M-U :

33 他の指数を特殊ケースとして含む Shapley-Shubik 指数 投票行動表 政党： A B C D E F ：議案数
他の指数との関係 他の指数を特殊ケースとして含む Shapley-Shubik 指数 投票行動表 政党： A B C D E F ：議案数 議案： Y Y Y Y Y Y ： 1 Deegan-Packel 指数 政党 ： A B C D E F ：議案数 議案1： Y Y N Y Y Y ： 1 議案2： Y Y Y N Y Y ： 全ての 議案3： Y Y Y Y N N ： 極小勝利提携 ･ ･ ･ ･ ･ ･

34 公理1 [∀F， v(F)=v(F+i)] → η(G,p)i = 0
公理系(0) 公理1 [∀F， v(F)=v(F+i)] → η(G,p)i = 0 公理2 [i,j ∈E, [∀F， v(F+i ｰ j)=v(Fｰ i+j)]] → η(G,pE)i = η(G,pE) j 公理3 ∀ E, η(G1, pE)+η(G2, pE) =η(G1 ∧G2, pE)+η(G1 ∨ G2, pE) 公理4 指数の総和=1 公理5 (0≦∀λ≦1), η(G, λp+(1‐λ)p’) =λη(G1, p)+ (1‐λ) η(G, p’) 公理6 ∀ E, η(G, pE) =η(G [E ], pE)

35 G=[q；w1, w2,..., wn]： wi ：i の票数, q ：割当数 プロフィール p :各勝利提携の発生確率
公理系(1) データ： G=[q；w1, w2,..., wn]： wi ：i の票数, q ：割当数 v : 特性関数 プロフィール p :各勝利提携の発生確率 (発生確率の総和は1） 指数： (η(G,p)1, η(G,p)2,...,η(G,p)n) 公理1 [∀F， v(F) = v(F+i)] → η(G,p)i = 0 公理2 [i,j ∈E, [∀F， v(F+i ｰ j)=v(Fｰ i+j)]] → η(G,pE)i = η(G,pE) j 単純プロフィール pE :勝利提携Eの発生確率=1 公理3 ・ ・ ・ ・

36 単純プロフィール pE :勝利提携Eの発生確率=1 公理1 [∀F， v(F)=v(F+i)] → η(G,p)i = 0
公理系(2) 単純プロフィール pE :勝利提携Eの発生確率=1 公理1 [∀F， v(F)=v(F+i)] → η(G,p)i = 0 公理2 [i,j ∈E, [∀F， v(F+i ｰ j)=v(Fｰ i+j)]] → η(G,pE)i = η(G,pE) j 公理3 ∀ E, η(G1, pE)+η(G2, pE) =η(G1 ∧G2, pE)+η(G1 ∨ G2, pE) 公理4 指数の総和=1 公理5 (0≦∀λ≦1), η(G, λp+(1‐λ)p’) =λη(G1, p)+ (1‐λ) η(G, p’) 公理6 ･ ･ ･ ･

37 公理1 [∀F， v(F)=v(F+i)] → η(G,p)i = 0
公理系(3) 公理1 [∀F， v(F)=v(F+i)] → η(G,p)i = 0 公理2 [i,j ∈E, [∀F， v(F+i ｰ j)=v(Fｰ i+j)]] → η(G,pE)i = η(G,pE) j 公理3 ∀ E, η(G1, pE)+η(G2, pE) =η(G1 ∧G2, pE)+η(G1 ∨ G2, pE) 公理4 指数の総和=1 公理5 (0≦∀λ≦1), η(G, λp+(1‐λ)p’) =λη(G1, p)+ (1‐λ) η(G, p’) 公理6 ∀ E, η(G, pE) =η(G [E ], pE) v’：G [E ]の特性関数, v’（F)=1 ⇔ v(F∩E)=1

38 定理：提案した指数は, 公理1～6で特徴付けられる. 公理1 [∀F， v(F)=v(F+i)] → η(G,p)i = 0
公理系(4) 公理1 [∀F， v(F)=v(F+i)] → η(G,p)i = 0 公理2 [i,j ∈E, [∀F， v(F+i ｰ j)=v(Fｰ i+j)]] → η(G,pE)i = η(G,pE) j 公理3 ∀ E, η(G1, pE)+η(G2, pE) =η(G1 ∧G2, pE)+η(G1 ∨ G2, pE) 公理4 指数の総和=1 公理5 (0≦∀λ≦1), η(G, λp+(1‐λ)p’) =λη(G1, p)+ (1‐λ) η(G, p’) 公理6 ∀ E, η(G, pE) =η(G [E ], pE) 定理：提案した指数は, 公理1～6で特徴付けられる.

39 S-S指数, D-P指数 を特殊ケースとして含む 参議院のデータを用いた他の指数との比較 O-M指数と近い数値が得られた
まとめ 新たな指数の提案 イデオロギー空間の導入が不要 S-S指数, D-P指数 を特殊ケースとして含む 参議院のデータを用いた他の指数との比較 O-M指数と近い数値が得られた （議案ベクトルの発生が偏っている場合に有効） 指数を特徴付ける公理系の証明 S-S指数の公理系 +（公理5）プロフィｰルに関する線形性 +（公理6）単純プロフィールを持つ際の仮定 公理5 (0≦∀λ≦1), η(G, λp+(1‐λ)p’) =λη(G, p)+ (1‐λ) η(G, p’) 公理6 ∀ E, η(G, pE) =η(G [E ], pE)

40 おわり

41 他の指数との比較 指数 ： 自民 社会 公明 共産 民社 連合 S-S ： Bz ： D-P ： S-O1： S-O2： O-M1: O-M2: O-M3: O-M4: O-M5: M-U :