WEIGHTED SIMPLE GAMES AND THE TOPOLOGY OF SIMPLICIAL COMPLEXES ANASTASIA BROOKS FRANJO ˇSARˇCEVI C AND ISMAR VOLI C Abstract. We use simplicial complexes to model simple games as well as weighted voting games where

2025-05-06 0 0 435.39KB 27 页 10玖币

侵权投诉

WEIGHTED SIMPLE GAMES AND THE TOPOLOGY OF SIMPLICIAL COMPLEXES

ANASTASIA BROOKS, FRANJO ˇ

SARˇ

CEVI´

C, AND ISMAR VOLI´

Abstract. We use simplicial complexes to model simple games as well as weighted voting games where

certain coalitions are considered impossible. Topological characterizations of various ideas from simple

games are provided, as are the expressions for Banzhaf and Shapley-Shubik power indices for weighted

games. We calculate the indices in several examples of weighted voting games with unfeasible coalitions,

including the U.S. Electoral College and the Parliament of Bosnia-Herzegovina.

Contents

1. Introduction 1

2. Weighted voting games and power indices 3

2.1. Simple and weighted games 3

2.2. Banzhaf index 5

2.3. Shapley-Shubik index 6

3. Simplicial complexes 7

4. Simplicial complex models for simple games 10

5. Simplicial complex formulas for power indices of games with unfeasible coalitions 12

5.1. Power indices for weighted voting games 14

5.2. Banzhaf index for weighted games 14

5.3. Shapley-Shubik index for weighted games 18

6. Further work 21

References 24

1. Introduction

Simplicial complexes are a natural tool for modeling structures in which there exist interactions be-

tween objects. In recent years, the use of simplicial complexes to model such interactions has become

increasingly common in various ﬁelds, including in social sciences (and speciﬁcally in social choice the-

ory) where simplicial complexes have been use to model social communication and opinion dynamics

[HG21, IPBL19, WZLS20].

Modeling political structures with simplicial complexes, where the voters or agents are represented by

vertices and coalitions by simplices, has enabled the import of a number of topological concepts into the

picture [AK19, MV21]. In this paper, we will take this setup further by applying the simplicial complex

framework to simple games and the calculation of power indices for weighted voting games.

2020 Mathematics Subject Classiﬁcation. 91F10, 91B12, 05E45.

Key words and phrases. simple games, weighted voting games, feasible coalition, quantiﬁcation of power, power index,

Banzhaf index, Shapley-Shubik index, simplicial complex, U.N. Security Council, U.S. Electoral College, Bosnia-Herzegovina

Parliament.

Acknowledgements. The second author is grateful to the University of Seville and the University of Sarajevo where

parts of this paper were written. The third author would like to thank the Simons Foundation for its support. He is also

grateful to University of Sarajevo where parts of this paper were written. The authors also thank Ava Mock who worked

on this project in its early stages.

arXiv:2210.09771v3 [physics.soc-ph] 27 Mar 2025

2 ANASTASIA BROOKS, FRANJO ˇ

SARˇ

CEVI´

C, AND ISMAR VOLI´

Simple games correspond to simplicial complexes via the observation that the losing coalitions form a

complex. This is because of the requirement that any subset of a losing coalition is losing, which is

precisely the deﬁning property of a simplicial complex. This correspondence does not seem to have been

explored in the literature, and we hope our work initiates further investigation. A notable result in this

direction is Theorem 4.2 (and its consequence Corollary 4.3) which provides a topological characterization

of a certain type of a weighted voting game.

One of the reasons weighted voting games are an important class of simple games is that the theory of

quantiﬁcation of power, or power indices, can be applied to them. Power indices are the second way in

which we introduce topology into simple game theory. In general, these indices measure a voter’s ability

to change the outcome of a game. Two of the most classical indices are the Banzhaf index [Ban65] and

the Shapley-Shubik index [SS54].1However, in their most basic deﬁnition, neither of them can account

for certain nuances of real-life voting schemes. Both assume an equal likelihood of all coalitions being

formed, but reality suggests that some coalitions might be impossible.

The literature that builds such considerations into modiﬁcations of power indices is extensive, but none of

it uses our approach via simplicial complexes. Incorporating quarreling coalitions into theory goes back

to the 1970s [Kil74], with more recent work including that of Schmidtchen and Steunenberg [SS14] who

take institutional considerations into account and K´oczy [K´oc14] who incorporates voters’ preferences

and strategies (the starting point being the “paradox” that refusing to enter a coalition can increase a

voter’s power). Some of this theory is recounted in Section 7.5. of the classic book [FM98].

The situation when the communication between voters is limited goes back to Myerson [Mye77] who uses

graphs to encode which voters are in communication with one another. There is also a complementary

approach where voter incompatibilites are kept track of by a graph. Now an edge between two players

means that they can never be in a coalition together. Such games are sometimes called I-restricted

[Car91, GBnGJ93, Yak08]. Power indices for systems with such restrictions have also been studied

[JAM15] and use generating functions to compute them.

One point of view on our work is that we expand on the notion that a graph captures voter (in)compatibilities.

A graph is an example of a simplicial complex, but it is limited in that it only knows about relationships

between pairs of voters via its edges. If, for example, three voters are compatible, a graph cannot

capture this information. A simplicial complex, on the other hand, can, and this three-fold compatibility

would be represented by a triangle. Our formulas for the Banzhaf and Shapley-Shubik indices are thus

in a way generalizations of those for graph restricted weighted voting games.

Further situation where there is a gradation of cooperation between voters is done by Owen [Owe86],

and Borm, Owen, and Tijs [BOT92]. Owen [Owe77, Owe81] modiﬁes the power indices by introducing

non-equal probability assumptions for the coalitions. A further advance in that direction was made by

Edelman [Ede97], whose work was extended by Perlinger and Berg [Per00, BP00] and Mazurkiewicz and

Mercik [MM05]. Recent literature on these topics includes [MS18, dMLLBL20, Kur20]. In particular,

the authors of [MS18] give a modiﬁcation of the Banzhaf, Shapley-Shubik, and other power indices to

take into account the proﬁles of the political parties as the main factor for forming a winning coalition.

Aleskerov [Ale09] extends the Banzhaf index to incorporate the intensity of the voters’ desire to form

coalitions. Freixas [Fre20], building on work by [FZ03], extends the Banzhaf index to situations where

voters can choose from a ﬁnite set of ordered actions or approvals.

The simplicial complex model for cooperative games which tries to capture a more nuanced coalition

dynamic is fairly novel. The most relevant work is that of Martino [Mar21] who sets up the dictionary

between coalitions and simplices. Unfeasible coalitions are captured by the absence of simplices that

would have been spanned by the vertices representing those voters. This work generalizes the study of

1There are other power indices, such as Deegan-Packel and Public Good, but Banzhaf and Shapley-Shubik are the most

familiar.

WEIGHTED SIMPLE GAMES AND THE TOPOLOGY OF SIMPLICIAL COMPLEXES 3

matroid models of simple games [Bil00, BDJLL01, BDJLL02] as matroids are special cases of simplicial

complexes. Another appearance of simplicial complexes in simple games can be found in [GP16], where

the authors construct a combinatorial manifold associated to the simplicial complex modeling a simple

game. Elsewhere in cooperative game theory, simplicial complexes appear in the study of combinatorial

[FHN19a, FHN19b, FHN19c] and snowdrift games [XFZX22].

None of this work, however, uses the topology of simplicial complexes as a way to model simple games

or reinterpret power indices in the presence of unfeasible coalitions. The goal of this paper is to do so,

and in Section 4 we study the topology of simple games while in Section 5 we supply formulas for the

Banzhaf and Shapley-Shubik indices as a count of certain types of simplices.

A few examples of weighted games (UN Security Council, U.S. Electoral College, Bosnian-Herzegovinian

Parliament) are also provided. The calculation of the Banzhaf index for the U.S. Electoral College,

considering the blue and red wall states as single voters, is particularly revealing. The calculations were

performed using a Python code we wrote.2The code does not improve on existing computational tools

since it checks over all possible coalitions ﬁrst and then compares those against the unfeasible ones, but

it contains some potentially useful methods for ﬁltering coalitions. For the discussion of computational

complexity of calculating power indices, see [MM00].

Even though our formulas for the Banzhaf and Shapley-Shubik indices are new, they are largely just

straightforward consequences of the translation from the language of simple games to that of simplicial

complexes. Thus the results of this paper can be regarded as the beginning of the exploration of the

correspondence between these two seemingly unrelated ﬁelds. In this spirit, Section 6 oﬀers various

potential directions for further work, much of it based on recasting some standard constructions from

the topology and geometry of simplicial complexes in the language of simple games. Among other

things, we speculate that operations such as the wedge, cone, and suspension, as well as simplicial maps

between complexes and the homology of simplicial complexes can provide insight and be interpreted in

game-theoretic terms. The framework of category theory, imported from topology, may also prove to

be useful. Another possible extension is to the larger class of topological (and combinatorial) objects

called hypergraphs. An additional promising route is to improve our formulas by taking into account

that the probability of coalition formation may be non-binary.

2. Weighted voting games and power indices

In this section we will brieﬂy recall the basics of simple games, weighted voting games, and the Banzhaf

and Shapley-Shubik indices. This material and further details can be found in many standard references,

such as [FM98, FM05, LV08, Nap19, TP08, TZ99, Web88].

2.1. Simple and weighted games. Simple games model voting systems in which a binary choice is

presented, or an alternative is presented against the status quo (selecting one of two candidates, passing

a legislation, adopting a measure, convicting a suspect, etc.).

Deﬁnition 2.1. Asimple (voting) game on a ﬁnite set Nis a function

v:P(N)−→ {0,1},

where P(N)is the power set of N, satisfying:

(1) v(∅) = 0;

(2) v(N) = 1;

(3) If S⊆T⊆Nand v(S)=1, then v(T) = 1 (monotonicity).

2The code is available at https://tinyurl.com/y2ev5pyz.

4 ANASTASIA BROOKS, FRANJO ˇ

SARˇ

CEVI´

C, AND ISMAR VOLI´

We will typically write N={v1, v2, ..., vn}. Elements vi∈Nare called voters (or players or agents).

A subset Sof Nis called a coalition. If v(S)=1, then Sis a winning coalition. Otherwise it is a losing

coalition. A game is determined by its winning or its losing coalitions which we will denote by Wand

L, respectively.

Remark 2.2.A simple game can also be regarded as a hypergraph on N– which is by deﬁnition a

collection of subsets of N– whose hyperedges correspond to winning coalitions. In addition, we require

that all supersets of hyperedges are also in the hypergraph because of condition (3) above and that the

hypergraph contains Nitself as an edge because of condition (2) (which, incidentally, it will by (3) as

soon as the hypergraph is non-empty since Nis a superset of any hyperedge).

Aminimal winning coalition is a subset Ssuch that v(S) = 1 but the value of vrestricted to any proper

subset of Sis 0, namely Sis a winning coalition but all its subsets are losing coalitions. Monotonicity

implies that a simple game is determined by its minimal winning coalitions. Similarly, a maximal losing

coalition is one whose supersets are all winning. A game is also determined by its maximal losing

coalitions.

Here is some standard terminology associated to simple games. We will not go into any depth about

these deﬁnitions; suﬃce it to say that they are central to understanding simple games. Let Scdenote

the complement of S.

Deﬁnition 2.3.

•A simple game is proper if it satisﬁes: If Sis a winning coalition, then Scis not.

•A simple game is strong if it satisﬁes: If Sis a losing coalition, then Scis not.

•A simple game is constant sum if it is proper and strong.

•Voter viis a dummy if: For all S∈ W,S\ {vi} ∈ W.

•Voter viis a vetoer if: Whenever vi/∈S,S /∈ W.

•Voter viis a passer if: Whenever vi∈S,S∈ W.

•Voter viis a dictator if: S∈ W if and only if {vi} ∈ S.

•The dual game v∗of a game vhas the same voter set as vand winning coalitions whose

complements are losing coalitions of v.

A simple game can also be deﬁned on a subset Fof P(N). An element S∈ F is called a feasible

coalition. Otherwise it is unfeasible. The idea is that, in real-life applications, not all coalitions can

be formed; sometimes voters are not willing to align with some other voters for a particular issue at

hand, or even under any circumstances at all. Our simplicial complex model will capture precisely this

situation.

Suppose we have a weight function

w:N−→ R+.

The value wi=w(vi)is the weight of the voter vi,i= 1, ..., n. The heuristic is that voter vi’s

vote is “worth” wivotes, or carries wipoints. Also suppose given a real number 0< q ≤t, with

t=w1+· · · +wn, the total weight.

Deﬁnition 2.4. A simple game von Nis weighted if there exists a weight function won Nand, for

all S⊆N,

v(S)=1 ⇐⇒ w(S) = X

vi∈S

wi≥q.

This deﬁnition says that a coalition Sis winning precisely when the total number of votes in Sclears

the quota. The real-life analog is a collection of voters with potentially diﬀering weights – such as

members of a board of directors whose voting weight is commensurate with the amount of stock they

own or parties in a parliament which have diﬀerent numbers of representatives – forming a coalition and

WEIGHTED SIMPLE GAMES AND THE TOPOLOGY OF SIMPLICIAL COMPLEXES 5

voting the same way on the choice that is presented. The coalition wins, or imposes their preference,

if it contains enough votes to surpass the quota q, typically set as 1

2t<q≤t(the usual supermajority

condition). In this situation, Sand N\Scannot both be winning so the game is proper.

We will denote a weighted voting game on N={v1, v2, ..., vn}with weights wi,1≤i≤n, and quota

qby V(q;w1, ..., wn); this is a standard shorthand notation.

Not every simple game is weighted. The standard examples are that of the U.S. legislative system and

the procedure to amend the Canadian Constitution [Jim14, TZ99].

If all voters have the same weight, i.e. wi=mfor all 1≤i≤n, then we can set the weights at 1 and

scale the quota by m. This produces an isomorphic weighted system, namely the value of the map v

is the same on all subsets of Nbefore and after scaling. We can therefore assume that, for weighted

games where all weights are equal, those weights are in fact 1. We will denote such a weighted system

by V(q; 1, ..., 1) and call it symmetric (it is also known as q-out-of-nin the literature).

2.2. Banzhaf index. The theory of power indices arose from the simple observation that a voter’s

weight does not paint the entire picture in terms of that voter’s ability to inﬂuence outcomes. For

example, in the weighted game V(51; 49,49,2), all three voters appear the same number of times in

minimal winning coalitions so in an intuitive sense have the same importance.

Banzhaf index is one of the measures that tries to capture this discrepancy. It was deﬁned, in slightly

diﬀerent forms, by Penrose [Pen46] and Banzhaf [Ban65] (see also Coleman [Col71]). It is also sometimes

referred to as the Penrose-Banzhaf or Banzhaf-Coleman index.

Deﬁnition 2.5. A voter viis said to be critical for a coalition Sin a simple game vif Sis a winning

coalition but S\ {vi}is a losing coalition.

In case of a weighted system V(q;w1, ..., wn), this means that viis critical for Sif both these inequalities

hold: X

vj∈S

wj≥q;

vj∈S\{vi}

wj< q.

Deﬁnition 2.6. The absolute Banzhaf (power) index of the voter viin a simple game vis deﬁned to

(1) AB(vi) = 1

2n−1X

S⊆N\{vi}v(S∪ {vi})−v(S).

This index can be interpreted as the probability that voter viis critical assuming all coalitions are equally

likely. The absolute Banzhaf index has some pleasant formal properties and is in fact determined by

them.

One inconvenience with the absolute Banzhaf index is that its values do not add up to 1. This is why

it is sometimes convenient to use the relative or normalized Banzhaf index, given as

(2) B(vi) = AB(vi)

Pvi∈NAB(vi).

In other words, B(vi)is the number of times voter viis critical divided by the total number of times all

voters are critical; thus, if we denote by c(vi)the number of times voter viis critical and by c(V)the

total number of times all voters are critical, then the Banzhaf index can be written as

B(vi) = c(vi)

c(V).

文档加载中……请稍候！
如果长时间未打开，您也可以点击刷新试试。

下载文档到电脑，查找使用更方便

10 玖币 0人已下载

立即下载

摘要：

WEIGHTEDSIMPLEGAMESANDTHETOPOLOGYOFSIMPLICIALCOMPLEXESANASTASIABROOKS,FRANJOˇSARˇCEVI´C,ANDISMARVOLI´CAbstract.Weusesimplicialcomplexestomodelsimplegamesaswellasweightedvotinggameswherecertaincoalitionsareconsideredimpossible.Topologicalcharacterizationsofvariousideasfromsimplegamesareprovided,asare...

展开>> 收起<<

WEIGHTED SIMPLE GAMES AND THE TOPOLOGY OF SIMPLICIAL COMPLEXES ANASTASIA BROOKS FRANJO ˇSARˇCEVI C AND ISMAR VOLI C Abstract. We use simplicial complexes to model simple games as well as weighted voting games where.pdf

共27页,预览5页

还剩页未读，继续阅读

声明：本站为文档C2C交易模式，即用户上传的文档直接被用户下载，本站只是中间服务平台，本站所有文档下载所得的收益归上传人(含作者)所有。玖贝云文库仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私，请立即通知玖贝云文库，我们立即给予删除！

WEIGHTED SIMPLE GAMES AND THE TOPOLOGY OF SIMPLICIAL COMPLEXES ANASTASIA BROOKS FRANJO ˇSARˇCEVI C AND ISMAR VOLI C Abstract. We use simplicial complexes to model simple games as well as weighted voting games where

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

热门标签

举报选择: