# Design of Blockchain-based Travel Rule Compliance System

Chaehyeon Lee1, Changhoon Kang1, Wonseok Choi1, Jehoon Lee1,
Myunghun Cha2, Jongsoo Woo3, and James Won-Ki Hong1  1Department of Computer
Science and Engineering, POSTECH, Korea
2Coinone, Seoul, Korea
3Graduate School of Information Technology, POSTECH, Korea

###### Abstract

In accordance with the guidelines of the Financial Action Task Force (FATF),
Virtual Asset Service Providers (VASPs) should comply with a ‘travel rule’,
which requires them to exchange originator’s and beneficiary’s personal
information when transferring virtual assets. In this paper, we propose a
novel blockchain-based travel rule compliance system that supports fully-
decentralized data exchange. The proposed system uses a permissioned
blockchain, and thereby eliminates the possibility of leakage of personal
information to third parties or even to travel rule service providers, and
ensures that travel rule data can be managed securely.

###### Index Terms:

FATF, Decentralized Travel Rule Compliance System, Blockchain, Recommendation
16, Virtual Asset Service Provider

††publicationid: pubid: 978-1-6654-9538-7/22/$31.00 ©2022 IEEE

##  I Introduction

The use of virtual assets for illegal purposes has increased, so, Financial
Action Task Force (FATF) proposed guidelines to prevent money laundering and
financing of terrorism [1, 2, 3]. The guidelines include travel rule guidance
that aims to have virtual asset service providers (VASP) fulfill their Anti-
Money Laundering/Combating the Financing of Terrorism (AML/CFT) obligations
[4]. The travel rule guidance is provided in Recommendation 16 and is intended
to restrict terrorists and criminals from moving funds freely by virtual asset
transfers [5]. To this end, the travel rule requires VASPs to share
identifying information regarding originator (sender of virtual assets) and
beneficiary (receiver of virtual assets). FATF updated the travel rule
guidelines in October 2021 [6]. In response to FATF’s guidelines, each country
is preparing laws on virtual assets and VASP to comply with FATF regulations.

In this paper, we propose a novel travel rule compliance system that uses
blockchain to comply with the travel rule [7]. In our proposed system,
authentication and data exchange between VASPs are performed in a peer-to-peer
(P2P) way by using blockchain, so that travel rule data can be exchanged
without third-party intermediaries and unnecessary data exposure. Thus, our
system is completely decentralized and secure.

##  II Related Work

Various companies around the world are developing travel rule compliance
systems to comply with the guidelines stipulated by FATF (see Table I). These
guidelines have no restrictions on the development of travel rule compliance
systems. Most systems [8, 9, 10, 11, 12] use a central server for
authentication or even data-exchange. This may cause a single point of failure
and a serious leakage of personal information. To overcome this, blockchain
technology can be applied to travel rule solutions. With the use of blockchain
technology, it is more efficient than the use of traditional methods to
exchange information, and has advantages in various aspects such as cost and
storage place management.

OpenVASP [13] uses Ethereum and does not require authentication processes by
third parties. However, blockchain is only used during the process of
authenticating the identity; the messaging protocol is used separately from
the blockchain in the actual data-exchange process, i.e., OpenVASP only
partially uses blockchain.

TABLE I: Comparison of Existing Travel Rule Solutions

Service | Company | Decentralized | Blockchain-based | Authentication | Communication | Open-sourced
---|---|---|---|---|---|---
TRISA[8] | CipherTrace | O | X | Certificate Authority | SSL/TLS | O
Sygna Bridge[9] | CoolBitX | X | X | Sygna Bridge Server | SSL/TLS | X
OpenVASP[13] | Bitocin Suisse | O | O | Ethereum Smart Contract | Whisper, WAKU, etc., | O
VerifyVASP[10] | Lambda256 | X | X | Join VerifyVASP Alliance | HTTPS | X
Transact ID[11] | Netki | O | X | Certificate | HTTPS | O
TRP[12] | ING Group | O | X | Direct, Certificate Authority | RESTful API, HTTP | O

##  III Design

Our blockchain-based travel rule compliance system has some advantages. First,
thanks to the principle of blockchain, third-party intervention is not
required. In some of the existing solutions, the exchange of travel rule data
between the VASPs is brokered by a third party, such as the solution-
provider’s central server. In this case, the customer’s personal information
held by the exchange may be unnecessarily exposed, and each exchange bears the
risk of exposing such personal information. However, by using blockchain,
transaction parties can exchange data in a P2P manner, and thereby prevent
unwanted exposure from irrelevant third parties.

Travel rule data can be directly exchanged between the two VASPs, and the
swapped data can be retained by each to follow decentralization. However, in
this case, if one party arbitrarily modifies or deletes data, a discrepancy
occurs between the data maintained by the two VASPs. This discrepancy
complicates the task of determining which data are genuine and which are not.
In contrast, in a blockchain, data cannot be modified or deleted without the
consent of the parties involved in the transaction. Even if a VASP succeeds in
maliciously modifying the data, the deed cannot be hidden, because all records
of data changes remain transparent on the blockchain. Therefore, the travel
rule solution that uses blockchain enables secure management of personal
information.

The architecture of our travel rule compliance system (see Fig. 1) takes the
form of a permissioned blockchain network to allow only authenticated VASPs to
use the system to exchange personal information with counterpart VASPs. A VASP
authentication node verifies the identity of the VASP that wants to
participate in the network and grants the authority. Authenticated VASPs must
operate a single individual node, and must store the data generated in the
process of exchanging personal information to comply with the travel rule in
its own distributed ledger. Each VASP node retrieves travel rule related data
from the connected backend.

Figure 1: Blockchain-based Travel Rule Compliance System Architecture

To satisfy the travel rule recently specified in Korean law [14], the travel
rule data exchange process is conducted in two steps. When originator at VASP
1 is trying to send virtual asset to beneficiary at VASP 2, the first step is
to provide the essential personal information, which includes the name and
virtual asset address of originator and beneficiary. After essential personal
information is exchanged, virtual assets are transferred, then the personal
and transaction data are stored. The second step is to provide additional
information. If a previously-executed transfer is determined to be suspicious,
VASP 2 can request the real name confirmation information of the originator.
This information can be resident registration number, passport number, or
alien registration number.

###  III-A Step 1 - Provision of Essential Information

When a customer of VASP 1 requests virtual asset transfer with beneficiary’s
virtual asset address, the VASP 1 backend confirms the customer’s request and
delivers the originator’s and beneficiary’s virtual asset addresses to the
VASP 1 blockchain node. VASP 1 delivers it to VASP 2, then VASP 2 checks
whether the originator information is normal. If the originator information
does not contain abnormality, then the VASP 2 node brings in the beneficiary’s
personal information from the backend and transmits it to VASP 1. When the
exchange of the originator’s and beneficiary’s personal information is
complete, VASP 1 executes virtual asset remittance and sends transaction
information including transaction ID to VASP 2. After confirming the
transaction information, VASP 2 informs VASP 1 whether the transaction is
normal or not, and if it is normal, confirms the transfer. When a response is
received from the VASP 2 node, travel rule data including personal information
and transaction information of the originator/beneficiary are recorded in the
blockchain ledger by the VASP 1 node.

###  III-B Step 2 - Provision of Additional Information

The beneficiary VASP may ask the originator VASP to provide the originator’s
real name confirmation information when fulfilling obligations under the laws,
such as Suspicious Transaction Report (STR) [6]. When suspicious circumstances
are found in the transaction executed by Step 1, VASP 2 requests the
originator’s additional information from VASP 1 by considering the information
exchanged in the first step. VASP 1 retrieves the originator’s real name
information from the backend and delivers it to VASP 2.

##  IV Concluding Remarks

In this paper, we have presented the design of a blockchain-based travel rule
compliance system to comply with the FATF’s guidance. This allows VASPs to
exchange travel rule data in a P2P manner for each transaction. Shared
personal information data can be stored and managed securely without unneeded
exposure. In future work, we plan to implement this system using Corda
enterprise distributed ledger system [15]. We also plan to link our system
with existing [8, 9, 10, 11, 12, 13] travel rule compliance systems. They are
diverse, and the travel rule cannot be applied using a single protocol in the
virtual-asset market. This makes expanding our system by integrating with
other travel rule systems important.

## Acknowledgments

This work was supported by CODE and the MSIT(Ministry of Science and ICT),
Korea, under the ITRC(Information Technology Research Center) support
program(IITP-2022-2017-0-01633) supervised by the IITP(Institute for
Information & Communications Technology Planning & Evaluation).

## References

  * [1] FATF.  Outcomes fatf plenary, 16-21 june 2019.  Available at https://www.fatf-gafi.org/publications/fatfgeneral/documents/outcomes-plenary-june-2019.html, 2021\.  Accessed: 2021-09-07.
  * [2] FATF.  Improving global aml/cft compliance: On-going process - 21 june 2019.  Available at https://www.fatf-gafi.org/publications/high-risk-and-other-monitored-jurisdictions/documents/fatf-compliance-june-2019.html, 2021\.  Accessed: 2021-09-07.
  * [3] FATF.  Public statement on virtual assets and related providers.  Available at http://www.fatf-gafi.org/publications/fatfrecommendations/documents/public-statement-virtual-assets.html, 2021\.  Accessed: 2021-09-07.
  * [4] FATF.  Guidance for a risk-based approach to virtual assets and virtual asset service providers.  Available at https://www.fatf-gafi.org/publications/fatfrecommendations/documents/guidance-rba-virtual-assets.html, 2021\.  Accessed: 2021-09-07.
  * [5] FATF.  The fatf recommendations.  Available at https://www.fatf-gafi.org/publications/fatfrecommendations/documents/fatf-recommendations.html, 2021\.  Accessed: 2021-09-07.
  * [6] FATF.  Outcomes fatf plenary, 19-21 october 2021.  Available at http://www.fatf-gafi.org/publications/fatfgeneral/documents/outcomes-fatf-plenary-october-2021.html, 2021\.  Accessed: 2021-11-01.
  * [7] Marc Pilkington.  Blockchain technology: principles and applications.  In Research handbook on digital transformations. Edward Elgar Publishing, 2016.
  * [8] Dave Jevans, Thomas Hardjono, Jelle Vink, Frank Steegmans, John Jefferies, and Aanchal Malhotra.  Travel rule information sharing architecture for virtual asset service providers.  TRISA, Version, 7, 2020.
  * [9] Sygna.  Technical document.  Available at https://developers.sygna.io/docs/api-doc, 2020.  Accessed: 2021-09-14.
  * [10] Lambda256.  Verifyvasp documentation.  Available at https://docs.verifyvasp.com/.  Accessed: 2021-09-14.
  * [11] NETKI.  Trancactid.  Available at https://netki.com/transactid/.  Accessed: 2021-11-12.
  * [12] TRP.  Trp.  Available at https://www.travelruleprotocol.org/.  Accessed: 2021-11-12.
  * [13] David Riegelnig and Bitcoin Suisse.  Openvasp: An open protocol to implement fatf’s travel rule for virtual assets, 2019.
  * [14] Enforcement decree of the act on reporting and use of certain financial transaction information.  Available at https://www.law.go.kr/.  Accessed: 2021-09-07.
  * [15] Corda.  Corda open source 4.8.  Available at https://docs.r3.com/en/platform/corda/4.8/open-source.html.  Accessed: 2021-10-08.


# Quantification of power and the geometry of simplicial complexes

Anastasia Brooks  Department of Mathematics, Wellesley College, Wellesley, MA
<EMAIL_ADDRESS>,  Franjo Šarčević  Department of Mathematics, University
of Sarajevo, Bosnia and Herzegovina<EMAIL_ADDRESS>pmf.unsa.ba/franjos and  Ismar Volić  Department of Mathematics, Wellesley
College, Wellesley, MA<EMAIL_ADDRESS>ivolic.wellesley.edu

###### Abstract.

We use simplicial complexes to model voting systems where certain coalitions
are considered unlikely or impossible. We express the Banzhaf and Shapley-
Shubik power indices in terms of such voting systems. We show how unweighted
and weighted Banzhaf and Shapley-Shubik power indices can be computed by
formulas which count certain types of simplices. We also provide several
examples and supply the code for calculating these indices in Python.

###### Key words and phrases:

weighted voting, coalition, quantification of power, power index, Banzhaf
index, Shapley-Shubik index, simplicial complex

###### 2020 Mathematics Subject Classification:

91F10, 91B12, 05E45

Acknowledgements. The second author is grateful to University of Seville 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.

###### Contents

  1. 1 Introduction
  2. 2 Preliminaries
    1. 2.1 Banzhaf power index
    2. 2.2 Shapley-Shubik power index
    3. 2.3 Simplicial complexes
  3. 3 Computing power indices with simplicial complexes
    1. 3.1 Modeling voting systems with simplicial complexes
    2. 3.2 Unweighted Banzhaf power index
    3. 3.3 Unweighted Shapley-Shubik power index
    4. 3.4 Weighted Banzhaf power index
    5. 3.5 Weighted Shapley-Shubik power index
  4. 4 Index calculators
    1. 4.1 Banzhaf index calculator
    2. 4.2 Shapley-Shubik index calculator
  5. 5 Directions for further research

##  1\. Introduction

Simplicial complexes are a natural tool for modeling structures in which there
exist interactions between objects; the objects can be represented by vertices
and their interaction by a simplex. In recent years, the use of simplicial
complexes to model such interactions has become increasingly common in various
fields, including in social sciences – and specifically in social choice
theory – where simplicial complexes have been use to model social
communication and opinion dynamics [HG21, IPBL19, WZLS20].

Modeling the political structures with simplicial complexes, where the voters
or agents are represented by the vertices and coalitions by the simplices,
enables us to bring 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 the problem of quantification of power and the
calculation of power indices.

There are two classical ways of quantifying the probability that a particular
voter will change the outcome of an election. The Banzhaf power index [Ban65]
and the Shapley-Shubik power index [SS54] offer two measurements of the power
of a voter based on their ability to affect the outcome of an election, though
both indices are unable to account for certain nuances of real-life voting
schemes. Both systems assume the equal likelihood of all voting coalitions,
but reality suggests that some coalitions are more likely than others, while
some are perhaps entirely improbable. Owen [Owe77, Owe81] modified these
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 modification of the Banzhaf, Shapley-
Shubik, and other power indices to take into account the profiles of the
political parties as the main factor for forming a winning coalition. They
considering the power indices in a few empirical cases.

Another avenue of investigation in the field of power indices is _election
inversion_ [Mil12], a phenomenon that can occur in any two-tiered electoral
system, for example under the U.S. Electoral College. This is the situation
when a win in the popular vote does not translate into the electoral (or
parliamentary) win, as has happened, for example, in the 2016 U.S.
presidential elections. In [dMLLBL20], the authors give an asymptotic
evaluation of the probability of an election inversion in a toy symmetric
version of the U.S. presidential electoral system, assuming that the votes are
drawn from a Shapley-Shubik probability model.

Finally, [Kur20] discusses approximation results between weights and the
Banzhaf power index in a weighted game, providing some parametric examples
that give necessary conditions for the existence of limit results for the
Banzhaf power index. The author also formulates a conjecture regarding weights
and the Shapley-Shubik index.

Our paper takes what appears to be a new approach to power indices. A voting
scheme is modeled by a simplicial complex where voters are represented by
vertices and $k$-simplices represent possible coalitions of size $k+1$.
Improbable or impossible coalitions are captured by the absence of simplices
that would have been spanned by the vertices representing those voters. The
topology and geometry of such a simplicial complex offer new insights into the
relationships between voters, particularly in larger voting systems.

The main part of the paper is Section 3. After modeling voting systems with
simplicial complexes, we first study and provide formulas for the unweighted
Banzhaf power index and the unweighted Shapley-Shubik power index in terms of
simplicial complexes. Then we study the weighted Banzhaf index and express it
by a formula counting certain types of simplices. A few examples (UN Security
Council, U.S. Electoral College, Bosnian-Herzegovinian Parliament) are also
provided. We do the same with the Shapley-Shubik index.

The Banzhaf and Shapley-Shubik indices in the examples are obtained using a
Python code we wrote for calculating them. Section 4 provides some details and
samples from the code. Finally, we offer potential directions for further
research. One of the most promising routes is to improve our formulas by
taking into account that the probability of coalition formation may be non-
binary, which is of course closer to reality.

##  2\. Preliminaries

In this section we will briefly recall the basics of power indices and
simplicial complexes that are relevant to this paper.

###  2.1. Banzhaf power index

The Banzhaf power index was defined, in slightly different forms, by multiple
mathematicians over the $20^{\text{th}}$ century (Penrose [Pen46], Banzhaf
[Ban65], Coleman [Col71]). It is also referred to as the Penrose-Banzhaf or
Banzhaf-Coleman index. This index measures the number of times a voter is
critical as a share of all the instances when any voter is critical. For
details, see the book [RU16].

Consider the weighted voting system

$V(q;w_{1},...,w_{n})$

of $n$ voters in a yes/no voting situation (selecting one of two candidates,
passing a legislation, adopting a measure, convicting a suspect, etc.). Here
$w_{i}$ is the _weight_ of the voter $v_{i}$, for $i=1,...,n$, so voter
$v_{i}$’s vote is in some sense ”worth” $w_{i}$ votes, or carries $w_{i}$
points. At least $q$ votes are required for a win; this positive integer is
called the _quota_. The quota is typically set as

$\frac{1}{2}t<q\leq t,$

where $t=w_{1}+\cdots+w_{n}$ is the total number of votes. This is the usual
_supermajority_ condition, with $q=t$ being the special case of _unanimity_.

Any subset $U=\\{v_{j_{1}},...,v_{j_{k}}\\}\subset V=\\{v_{1},...,v_{n}\\}$ of
the set of voters is called a coalition. We assume all the voters in a
coalition $U$ vote the same way.

######  Definition 2.1.

In a weighted voting system $V(q;w_{1},...,w_{n})$, a subset of the voters
$U=\\{v_{j_{1}},...,v_{j_{k}}\\}$ is a _winning coalition_ if

$w_{j_{1}}+\cdots+w_{j_{k}}\geq q.$

It is clear that there cannot be two disjoint winning coalitions $U$ and $Z$,
because otherwise the sum of votes in $U$ and $Z$ would exceed $t$.

If a coalition is not winning, it is said to be _losing_.

######  Definition 2.2.

A voter is said to be _critical_ if it is a member of a winning coalition that
would become losing coalition without its vote; that is, for some
$l\in\\{1,...,k\\}$, a member $v_{j_{l}}$ of a winning coalition
$\\{v_{j_{1}},...,v_{j_{k}}\\}$ is critical if

$w_{j_{1}}+\cdots+w_{j_{k}}-w_{j_{l}}<q.$

######  Definition 2.3.

For a voter $v_{i}$, the _Banzhaf power index_ is defined to be the number

$B(v_{i})=\frac{c(v_{i})}{c(V)},$

where $c(v_{i})$ is the number of times voter $v_{i}$ is critical, and $c(V)$
is the total number of times all voters are critical, i.e.
$c(V)=c(v_{1})+\cdots+c(v_{n}).$

In other words $B(v_{i})$ captures the probability that a voter $v_{i}$ will
change the outcome of a vote by joining coalitions.

It should be clear that $B(v_{1})+\cdots+B(v_{n})=1$.

######  Example 2.4.

Take the voting system $V(q=8;w_{1}=1,w_{2}=2,w_{3}=3,w_{4}=4,w_{5}=5)$ of
five voters $\\{v_{1},v_{2},v_{3},v_{4},v_{5}\\}$. There are $12$ winning
coalitions, including the coalition $\\{v_{1},v_{2},v_{3},v_{4}\\}$. This is a
winning coalition because $1+2+3+4=10\geq 8$. In this coalition, only $v_{3}$
and $v_{4}$ are critical, because without either of their votes the coalition
would not pass, but $v_{1}$ and $v_{2}$ could each be removed and the
coalition would still be winning. Out of the $12$ winning coalitions, there
are $26$ instances when a voter is critical. Voter $v_{1}$ is critical $2$
times, namely in the winning coalitions $\\{v_{1},v_{2},v_{5}\\}$ and
$\\{v_{1},v_{3},v_{4}\\}$, so $c(v_{1})=2$. We also have $c(v_{2})=2$ because
$v_{2}$ is critical only in the winning coalitions $\\{v_{1},v_{2},v_{5}\\}$
and $\\{v_{2},v_{3},v_{4}\\}$. Similarly, $c(v_{3})=6,c(v_{4})=6$, and
$c(v_{5})=10$. Thus the Banzhaf indices for this voting system are

$B(v_{1})=B(v_{2})=\frac{2}{26},\ \ B(v_{3})=B(v_{4})=\frac{6}{26},\ \
B(v_{5})=\frac{10}{26}.$

###  2.2. Shapley-Shubik power index

While for the Banzhaf power index the order in which voters join a coalition
does not matter, i.e. the coalitions are just subsets of the set of voters,
the Shapley-Shubik power index, introduced by Shapley and Shubik in 1954
[SS54] takes the order in which voters enter a coalition into account. This is
natural since, in real-life situations, voters often decide whether to join a
coalition based on who is already in it (think political parties in a
parliament). Voting power is then measured by how often a voter flips a
coalition from losing to winning at the moment they join.

######  Definition 2.5.

A _maximal sequential coalition_ or an _ordered coalition_ of $n$ voters
$\\{v_{1},...,v_{n}\\}$ is any bijection
$\sigma:\\{v_{1},...,v_{n}\\}\rightarrow\\{v_{1},...,v_{n}\\}$, that is, any
permutation $[v_{\sigma(1)},...,v_{\sigma(n)}]$ of the set
$\\{v_{1},...,v_{n}\\}$.

######  Definition 2.6.

A voter is said to be _pivotal_ if the ordered coalition is not winning before
the voter joined and it is winning after the voter joined the coalition; that
is, a voter $v_{l}$ is pivotal in the ordered coalition
$[v_{\sigma(1)},...,v_{\sigma(n)}]$ if $l=\sigma(k)$ for some
$k\in\\{1,...,n\\}$ and

$\text{(a) }w_{\sigma(1)}+\cdots+w_{\sigma(k-1)}<q,$ $\text{(b)
}w_{\sigma(1)}+\cdots+w_{\sigma(k)}\geq q.$

######  Definition 2.7.

For a voter $v_{i}$ in a voting system $V(q;w_{1},...,w_{n})$, the _Shapley-
Shubik power index_ is defined to be the number

$SS(v_{i})=\frac{p(v_{i})}{p(V)},$

where $p(v_{i})$ is the number of times voter $v_{i}$ is pivotal, and $p(V)$
is the number of times all voters are pivotal.

Since every winning coalition has a pivotal voter, the count of all pivotal
voters is the count of all maximal sequential coalitions, hence $p(V)=n!.$ So
the Shapley-Shubik index can be rewritten as

$SS(v_{i})=\frac{p(v_{i})}{n!}.$

It should again be clear that $SS(v_{1})+\cdots+SS(v_{n})=1$.

######  Example 2.8.

Take the same voting system $V(8;1,2,3,4,5)$ as in Example 2.4. Taking order
into account, there are $5!=120$ winning coalitions. Using the brackets $[-]$
to denote sequential coalitions, two of the winning ones are
$A=[v_{5},v_{1},v_{2},v_{4},v_{3}]$ and $B=[v_{1},v_{3},v_{2},v_{4},v_{5}]$.
In the sequential coalition $A$, $v_{2}$ is the pivotal voter, because $v_{5}$
and $v_{1}$ together do not have enough voting power, but $v_{2}$ is the one
that tips the coalition into victory by its vote. Similarly, in the sequential
coalition $B$, $v_{4}$ is the pivotal voter. We find that all sequential
coalitions with $v_{1}$ as pivotal are $[v_{2},v_{5},v_{1},v_{4},v_{3}]$,
$[v_{2},v_{5},v_{1},v_{3},v_{4}]$, $[v_{5},v_{2},v_{1},v_{3},v_{4}]$,
$[v_{5},v_{2},v_{1},v_{4},v_{3}]$, $[v_{3},v_{4},v_{1},v_{2},v_{5}]$,
$[v_{3},v_{4},v_{1},v_{5},v_{2}]$, $[v_{4},v_{3},v_{1},v_{2},v_{5}]$,
$[v_{4},v_{3},v_{1},v_{5},v_{2}]$. Hence, $p(v_{1})=8$. Similarly,
$p(v_{2})=8$, $p(v_{3})=p(v_{4})=28$, $p(v_{5})=48$. Therefore, the Shapley-
Shubik indices for this voting system are

$SS(v_{1})=SS(v_{2})=\frac{8}{120},\ \ SS(v_{3})=SS(v_{4})=\frac{28}{120},\ \
SS(v_{5})=\frac{48}{120}.$

Comparing this with Example 2.4, we see that the Shapley-Shubik indices for
the voters $v_{1}$ and $v_{2}$ are slightly less than the corresponding
Banzhaf indices, and the Shapley-Shubik indices for the voters
$v_{3},v_{4},v_{5}$ are slightly greater than the corresponding Banzhaf
indices.

###  2.3. Simplicial complexes

This subsection provides the basic information about finite simplicial
complexes that we will use in the subsequent section to represent voting
systems and develop new formulas for power indices. Standard material about
simplicial complexes can be found in many topology textbooks, such as [FP09],
[Mat03], [Spa95]. A self-contained exposition sufficient for understanding how
political structures relate to simplicial complexes can be found in [MV21].

######  Definition 2.9.

A _finite abstract simplicial complex_ is the ordered pair $K=(V,\Delta)$ that
consists of a finite set $V$ and a set $\Delta$ of subsets of $V$ such that
(1) Elements of $V$ are in $\Delta$;
(2) If $\sigma\in\Delta$ and $\eta\subset\sigma$, then $\eta\in\Delta$.

Roughly speaking, $K$ is a family of sets that is closed under taking subsets.
Elements of $V$ are called vertices of $K$, and elements of $\Delta$ are
called simplices of $K$.

To simplify notation, we usually identify $K$ with $\Delta$.

If we associate geometry to a given abstract simplicial complex – turning $K$
into a topological space $||K||$ called the _geometric realization_ (or the
_polyhedron_) of $K$ – we get a _geometric simplicial complex_ , a structure
that can be visualized by points, line segments, triangles, tetrahedra, and
their higher-dimensional generalizations. Each point represents a vertex and a
(generalized) tetrahedron spanned by some subsets of the vertices represents a
simplex. When we say simplicial complex, it is this geometric representation
we will be referring to.

######  Example 2.10.

An example of a simplicial complex on the vertex set
$V=\\{v_{1},v_{2},v_{3},v_{4},v_{5},v_{6},v_{7}\\}$ is

$K=\\{\\{v_{1}\\},\\{v_{2}\\},\\{v_{3}\\},\\{v_{4}\\},\\{v_{5}\\},\\{v_{6}\\},\\{v_{7}\\},\\{v_{1},v_{2}\\},\\{v_{1},v_{3}\\},$
$\hskip
22.1931pt\\{v_{2},v_{3}\\},\\{v_{2},v_{4}\\},\\{v_{2},v_{5}\\},\\{v_{4},v_{5}\\},\\{v_{5},v_{6}\\},\\{v_{1},v_{2},v_{3}\\}\\}.$

The geometric realization of $K$ is given in Figure 1.

On the other hand, the collections

$K^{\prime}=\\{\\{v_{1}\\},\\{v_{2}\\},\\{v_{3}\\},\\{v_{4}\\},\\{v_{5}\\},\\{v_{6}\\},\\{v_{7}\\},\\{v_{1},v_{2}\\},\\{v_{1},v_{3}\\},\\{v_{1},v_{2},v_{3}\\}\\}$

and

$K^{\prime\prime}=\\{\\{v_{1}\\},\\{v_{2}\\},\\{v_{3}\\},\\{v_{4}\\},\\{v_{5}\\},\\{v_{6}\\},\\{v_{1},v_{2}\\},\\{v_{1},v_{3}\\},$
$\hskip
50.64586pt\\{v_{2},v_{3}\\},\\{v_{2},v_{4}\\},\\{v_{2},v_{5}\\},\\{v_{4},v_{5}\\},\\{v_{5},v_{6}\\},\\{v_{1},v_{2},v_{3}\\}\\}$

are not simplicial complexes on $V$.

$v_{1}$$v_{2}$$v_{3}$$v_{1}$$v_{2}$$v_{5}$$v_{2}$$v_{4}$$v_{5}$$v_{4}$$v_{5}$$v_{6}$$v_{7}$
Figure 1. The geometric realization of the simplicial complex from Example
2.10

######  Definition 2.11.

  * •

A simplicial complex $L=(V^{\prime},\Delta^{\prime})$ is a _subcomplex_ of a
simplicial complex $K=(V,\Delta)$ if $V^{\prime}\subset V$ and
$\Delta^{\prime}\subset\Delta$.

  * •

Let $K=(V,\Delta)$ be a simplicial complex. We call $\sigma\in\Delta$ a _$d$
-simplex_ of $K$ if $\sigma$ contains exactly $d+1$ vertices, i.e.
$|\sigma|=d+1$.

  * •

If $\sigma$ is a simplex of $K$, then any subset $\eta$ of $\sigma$ is called
a _face_ of $\sigma$.

  * •

If $\sigma$ is a simplex of $K$, the _dimension_ of $\sigma$ is

$\dim\sigma=|\sigma|-1.$

  * •

The _dimension of the complex_ $K$ is defined to be the maximal dimension of
its simplices, that is

$\dim K=\max\\{\dim\sigma:\sigma\in\Delta\\}.$

If $\dim K=n$, we say $K$ is an _$n$ -complex_.

  * •

A simplex $\sigma$ in $K$ is called a _maximal simplex_ or a _facet_ if
$\sigma$ is not a face of any other simplex of $K$. It follows that $\Delta$
is the set of all non-empty subsets of the maximal simplices of $K$.

  * •

Let $K^{d}$ be the collection of all $e$-simplices of $K$ along with their
faces, for all $0\leq e\leq d$. Then $K^{d}$ is called the _$d$ -skeleton_ of
$K$. Note that $K^{l}\subset K^{m}$ for $l\leq m$.

  * •

The _star_ of a simplex $\sigma$ is defined to be the set

$\text{st}(\sigma)=\\{\tau\in\Delta:\sigma\subset\tau\\}.$

Here we are most interested in the special case $\sigma=\\{v\\}$ for a vertex
$v$, so $\text{st}(v)$ is the set of all simplices in $K$ that contain $v$ as
a vertex.

  * •

The action of removing the set $\text{st}(v)$ from the complex $K$ is called
the _deletion_ of $v$. The subcomplex $K\setminus\text{st}(v)$ is denoted by
$K\setminus v$.

######  Example 2.12.

Let $K$ be the simplicial complex from Example 2.10, with the geometric
realization presented in Figure 1.

  * •

Each vertex $\\{v_{i}\\}$, $i=1,...,7$, is $0$-simplex of $K$.
The line segments
$\\{v_{1},v_{2}\\},\\{v_{1},v_{3}\\},\\{v_{2},v_{3}\\},\\{v_{2},v_{4}\\},\\{v_{2},v_{5}\\},\\{v_{4},v_{5}\\},\\{v_{5},v_{6}\\}$
are $1$-simplices of $K$.
$K$ has one $2$-simplex, a triangle $\\{v_{1},v_{2},v_{3}\\}$.

  * •

The dimension of $K$ is $2$.

  * •

The simplices $\\{v_{1},v_{2}\\},\\{v_{1},v_{3}\\},\\{v_{2},v_{3}\\}$ are
faces of the simplex $\\{v_{1},v_{2},v_{3}\\}$.

  * •

The simplices $\\{v_{1},v_{2},v_{3}\\}$,
$\\{v_{2},v_{4}\\},\\{v_{2},v_{5}\\},\\{v_{4},v_{5}\\},\\{v_{5},v_{6}\\}$ and
$\\{v_{7}\\}$ are maximal simplices of $K$. The simplices
$\\{v_{1},v_{2}\\},\\{v_{1},v_{3}\\},\\{v_{2},v_{3}\\}$ are not maximal.

  * •

$K^{0}=\\{\\{v_{1}\\},\\{v_{2}\\},\\{v_{3}\\},\\{v_{4}\\},\\{v_{5}\\},\\{v_{6}\\},\\{v_{7}\\}\\}.$
$K^{1}=K^{0}\cup\\{\\{v_{1},v_{2}\\},\\{v_{1},v_{3}\\},\\{v_{2},v_{3}\\},\\{v_{2},v_{4}\\},\\{v_{2},v_{5}\\},\\{v_{4},v_{5}\\},\\{v_{5},v_{6}\\}\\}.$
$K^{2}=K^{1}\cup\\{\\{v_{1},v_{2},v_{3}\\}\\}.$

  * •

$\text{st}(v_{2})=\\{\\{v_{2}\\},\\{v_{1},v_{2}\\},\\{v_{2},v_{3}\\},\\{v_{2},v_{4}\\},\\{v_{2},v_{5}\\},\\{v_{1},v_{2},v_{3}\\}\\}$.
$K\setminus
v_{2}=\\{\\{v_{1}\\},\\{v_{3}\\},\\{v_{4}\\},\\{v_{5}\\},\\{v_{6}\\},\\{v_{7}\\},\\{v_{1},v_{3}\\},\\{v_{4},v_{5}\\},\\{v_{5},v_{6}\\}\\}$.

##  3\. Computing power indices with simplicial complexes

This is the main section of the paper. We show how to make use of simplicial
complexes in modelling voting systems where some of the coalitions are not
possible and calculating the Banzhaf and the Shapley-Shubik power indices for
such systems.

###  3.1. Modeling voting systems with simplicial complexes

The traditional Banzhaf and Shapley-Shubik indices both assume equal
likelihood of all possible coalitions. However, this may not provide the most
accurate representation of the power of each voter. Here we model voting
systems which contain forbidden coalitions, that is, the coalitions that may
be extremely unlikely or impossible to form.

Consider first the traditional voting system in which no coalition is assumed
forbidden. Let $V=V(q;w_{1},...,w_{n})$ be the weighted voting system
consisting of voters $v_{1},...,v_{n}$. Then we can represent $V$ as the
simplicial complex $K$ such that the vertices of $K$ represent each individual
voter and the simplices of $K$ represent each face of the maximal simplex
$\\{v_{1},...,v_{n}\\}$. In other words, $K$ is the standard $(n-1)$-simplex.
For example, the voting system $V$ consisting of voters $v_{1},...,v_{7}$ such
that no coalition is forbidden can be represented as the simplicial complex
$K$ whose simplices are all non-empty subsets of the set of voters, i.e.

$K=\mathcal{P}_{0}(\\{v_{1},...,v_{7}\\}).$

Here, for a set $A$, $\mathcal{P}_{0}(A)$ denotes the set of all non-empty
subsets of $A$.

In full generality, the situation with forbidden coalitions can be described
as follows. Start with a full $(n-1)$-simplex. Since then there are subsets of
voters which are not allowed, this geometrically means that we remove certain
faces from the full simplex. This leaves a simplicial complex which has a
simplex for every coalition that is allowed. This means that there could be
various subsets, not even disjoint, where voters do not talk to each other.

Now suppose, more specifically, that there exists a subset of $j$ voters such
that no two of them would ever be in a coalition. Relabel the voters so that
this subset is indexed as $\\{v_{1},...,v_{j}\\}$. In other words, any
coalition containing two voters from $\\{v_{1},...,v_{j}\\}$ is forbidden. We
can represent this as the simplicial complex $K$ with vertices representing
the voters in $V$, and each simplex of $K$ represents a feasible, i.e. not
forbidden, coalition in $V$. Notice that no two vertices in
$\\{v_{1},...,v_{j}\\}$ can be contained in the same simplex, that is, they
are not connected by an edge in the geometric realization of $K$. Then the
maximal simplices are formed by joining $v_{i}$, $1\leq i\leq j$, to the set
$\\{v_{j+1},...,v_{n}\\}$. This way, we have that $K$ has $j$ maximal
simplices and the dimension of those simplices is $n-j$.

The following example describes also another “forbidden” situation.

######  Example 3.1.

Let $V$ be the voting system consisting of voters $v_{1},...,v_{7}$ such that
a voter in $\\{v_{1},v_{2},v_{3}\\}$ could never be in a coalition with a
voter in $\\{v_{5},v_{6},v_{7}\\}$. This means that certain subsets of the set
$\\{v_{1},...,v_{7}\\}$ are not allowed, such as $\\{v_{3},v_{5}\\}$,
$\\{v_{1},v_{3},v_{7}\\}$, $\\{v_{1},v_{4},v_{5}\\}$, and
$\\{v_{2},v_{5},v_{6}\\}$. Therefore we remove all such simplices from the
full $6$-simplex. On the other hand, the elements of $\\{v_{1},v_{2},v_{3}\\}$
and $\\{v_{5},v_{6},v_{7}\\}$ can be in a coalition with any other element of
those sets, and $v_{4}$ is open to being in a coalition with anyone. The
system $V$ can thus be represented as the simplicial complex $K$ given by

$K=\mathcal{P}_{0}(\\{v_{1},v_{2},v_{3},v_{4}\\})\cup\mathcal{P}_{0}(\\{v_{4},v_{5},v_{6},v_{7}\\}).$

The geometric realization of $K$ is the union of two tetrahedra
$\\{v_{1},v_{2},v_{3},v_{4}\\}$ and $\\{v_{4},v_{5},v_{6},v_{7}\\}$ with the
common vertex $v_{4}$; in other words, as a wedge sum of these two tetrahedra
with $v_{4}$ as the wedge point.

######  Example 3.2.

The president of the United States of America is not elected directly by
popular vote, but through a process called Electoral College. Each of the 50
states, along with Washington, D.C., gets a certain number of electors, which
depends on its population according to the last census. The number of electors
determined on the basis of 2020 Census will be applied to the 2024 and 2028
presidential elections. The smallest number of electors is 3 (for Alaska,
Delaware, North Dakota, South Dakota, Vermont, and D.C.), and the highest
number is 54 (for California). The total number of electors is 538, and a
candidate needs at least 270 votes in the College to win the election.

Therefore, the Electoral College of the United States can be represented as
the weighted voting system

$\displaystyle
V(270;54,40,30,28,19,19,17,16,16,15,14,13,12,11,11,11,11,10,10,10,$
$\displaystyle
10,10,9,9,8,8,8,7,7,6,6,6,6,6,6,5,5,4,4,4,4,4,4,4,3,3,3,3,3,3,3).$

The states are often divided into three groups: ”blue wall” states, ”red wall”
states, and swing states. There is no real concensus on what the blue, red,
and swing states are, as this depends on the criteria used (usually along the
lines of how many elections of what kind have been won by which party in each
state). We take one of the possibilities here, but the analysis and
calculations can easily be modified for any of them. Namely, we think of the
Electoral College as partitioned into the following 18 ”blue wall,” 21 ”red
wall,” and 12 swing states:

Blue: California, Colorado, Connecticut, Delaware, Hawaii, Illinois, Maryland,
Massachusetts, Nevada, New Jersey, New Mexico, New York, Oregon, Rhode Island,
Vermont, Virginia, Washington, and D.C.

Red: Alabama, Alaska, Arkansas, Idaho, Indiana, Kansas, Kentucky, Louisiana,
Mississippi, Missouri, Montana, Nebraska, North Dakota, Oklahoma, South
Carolina, South Dakota, Tennessee, Texas, Utah, West Virginia, and Wyoming.

Swing: Arizona, Florida, Georgia, Iowa, Maine, Michigan, Minnesota, New
Hampshire, North Carolina, Ohio, Pennsylvania, and Wisconsin.

In all states except Nebraska and Maine, the electors are assigned according
to the ”winner takes all” principle. Nebraska and Maine allocate elctoral
votes districtwise, which means that there is potential for each of those
states to not vote entirely blue or red, but we will ignore this possiblity
since it is not of significant relevance for the calculations.

A U.S. presidential election typically comes down to a vote between one
Republican candidate and one Democratic candidate. It follows that a “red
wall” state is unlikely to be in the same coalition as a “blue wall” state and
consideration of such improbable coalitions when counting pivotal and critical
voters may lead to inaccuracies. Reorder the states so that the first $18$
states are blue, and the next $21$ states are red. Hence we will represent the
Electoral College as the simplicial complex $K$ given by

$K=\mathcal{P}_{0}(\\{v_{1},...,v_{18},v_{40},...,v_{51}\\})\cup\mathcal{P}_{0}(\\{v_{19},...,v_{39},v_{40},...,v_{51}\\})$

where the vertices corresponding to the “blue wall” states are
{$v_{1}$,…,$v_{18}$}, the vertices corresponding to the “red wall” states are
{$v_{19}$,…,$v_{39}$}, and the vertices corresponding to the swing states are
{$v_{40}$,…,$v_{51}$}. The simplices
$\\{v_{1},...,v_{18},v_{40},...,v_{51}\\}$ and
$\\{v_{19},...,v_{39},v_{40},...,v_{51}\\}$ are maximal in $K$.

###  3.2. Unweighted Banzhaf power index

We say a voting system $V(q;w_{1},...,w_{n})$ is _unweighted_ if $w_{i}=1$ for
all $i=1,...,n$.

Define the reduced $d$-skeleton $\widetilde{K}^{d}$ of a simplicial complex
$K$ as the set $K^{d}\setminus K^{d-1}$, where $K^{d}$ is the $d$-skeleton.
Note that $\widetilde{K}^{d}$ is just a subset, not necessarily a subcomplex
of $K$.

For a subset $K^{\prime}\subset K$, let $|K^{\prime}|$ denote the cardinality
of $K^{\prime}$, i.e. the number of elements in $K^{\prime}$.

Let $V(q;1,...,1)$ be an unweighted voting system with voters
$v_{1},...,v_{n}$ and quota $q$, where

$\frac{n}{2}<q\leq n.$

######  Proposition 3.3.

The Banzhaf power index $B_{u}(v_{i})$ for a voter $v_{i}$ in the unweighted
system $V(q;1,...,1)$ is given by

$B_{u}(v_{i})=\frac{|\text{st}(v_{i})\cap\widetilde{K}^{q-1}|}{q\cdot|\widetilde{K}^{q-1}|}.$

###### Proof.

We can represent $V$ as the simplicial complex $K$ whose simplices are all
possible coalitions in $V$. Then a critical coalition in $V$ must contain
exactly $q$ voters, that is, critical coalitions can be represented as the set
of all simplices in $K$ containing exactly $q$ voters, i.e. as the reduced
$(q-1)$-skeleton $\widetilde{K}^{q-1}$. Hence the denominator of the Banzhaf
power index is

$q\cdot|\widetilde{K}^{q-1}|.$

The numerator of the Banzhaf power index of a voter $v_{i}$ is the number of
coalitions in which $v_{i}$ is critical. The set of all such coalitions is the
set of simplices in $\widetilde{K}^{q-1}$ which contain $v_{i}$; in other
words, this is the set of simplices in $K$ which contain $v_{i}$ as a vertex
and which are contained in $\widetilde{K}^{q-1}$. This means that the number
of coalitions in which $v_{i}$ is critical is

$|\text{st}(v_{i})\cap\widetilde{K}^{q-1}|.$

Therefore, the Banzhaf power index $B_{u}(v_{i})$ is given by

$B_{u}(v_{i})=\frac{|\text{st}(v_{i})\cap\widetilde{K}^{q-1}|}{q\cdot|\widetilde{K}^{q-1}|}.$

∎

######  Example 3.4.

Let $V$ be an unweighted voting system represented as the simplicial complex
from Example 2.10, with quota (a) $q=2$, (b) $q=3$.

In the case (a), the reduced $1$-skeleton $\widetilde{K}^{1}$ is the set

$\\{\\{v_{1},v_{2}\\},\\{v_{1},v_{3}\\},\\{v_{2},v_{3}\\},\\{v_{2},v_{4}\\},\\{v_{2},v_{5}\\},\\{v_{4},v_{5}\\},\\{v_{5},v_{6}\\}\\}.$

Further, we have $c(v_{1})=|\text{st}(v_{1})\cap\widetilde{K}^{1}|=2$,
$c(v_{2})=4$, $c(v_{3})=2$, $c(v_{4})=2$, $c(v_{5})=3$, $c(v_{6})=1$,
$c(v_{7})=0$. The denominator for the Banzhaf index is

$c(v)=\sum_{i=1}^{7}c(v_{i})=q\cdot|\widetilde{K}^{1}|=14.$

Therefore, the unweighted Banzhaf indices are

$B_{u}(v_{1})=\frac{2}{14},B_{u}(v_{2})=\frac{4}{14},B_{u}(v_{3})=\frac{2}{14},B_{u}(v_{4})=\frac{2}{14},B_{u}(v_{5})=\frac{3}{14},B_{u}(v_{6})=\frac{1}{14},B_{u}(v_{7})=0.$

In the case (b), $\widetilde{K}^{2}=\\{\\{v_{1},v_{2},v_{3}\\}\\}$,
$c(v_{1})=|\text{st}(v_{1})\cap\widetilde{K}^{2}|=1$, $c(v_{2})=c(v_{3})=1$,
$c(v_{i})=0$ for $4\leq i\leq 7$, $c(V)=q\cdot|\widetilde{K}^{2}|=3$, and the
unweighted Banzhaf indices are

$B_{u}(v_{1})=B_{u}(v_{2})=B_{u}(v_{3})=\frac{1}{3},B_{u}(v_{i})=0\text{ for
}4\leq i\leq 7.$

###  3.3. Unweighted Shapley-Shubik power index

Let $V=V(q;1,...,1)$ be an unweighted voting system with voters
$v_{1},...,v_{n}$. Let $K$ be the simplicial complex that represents $V$, as
in Section 3.2. Recall that the denominator of the Shapley-Shubik power index
is the number of all maximal winning sequential coalitions and take into
account that some coalitions may be forbidden. It follows that in order for a
coalition to be winning, it must have at least $q$ voters. Hence we can
represent the maximal winning coalition as the set of all maximal simplices in
$K$ that contain $q$ or more vertices.

Denote by $M_{j}$ the set of all maximal simplices with $j+1$ vertices and by
$|M_{j}|$ its cardinality. Let $d=\dim K$.

######  Proposition 3.5.

The Shapley-Shubik power index $SS_{u}(v_{i})$ for a voter $v_{i}$ in the
unweighted voting system $V(q;1,...,1)$ is given by

$SS_{u}(v_{i})=\frac{\sum_{j=q-1}^{d}|M_{j}\cap\text{st}(v_{i})|\cdot
j!}{\sum_{j=q-1}^{d}|M_{j}|\cdot(j+1)!}.$

###### Proof.

The number of all maximal winning coalitions is given by

$\sum_{j=q-1}^{d}|M_{j}|.$

To compute the number of all winning sequential coalitions, we have to
consider every possible order in which voters join a maximal winning
coalition. Since each $m\in M_{j}$ has $j+1$ vertices, the number of all
winning sequential coalitions is obtained by multiplying the above expression
by $(j+1)!$. Thus the denominator of the Shapley-Shubik index is given by

$\sum_{j=q-1}^{d}|M_{j}|\cdot(j+1)!.$

Recall also that the numerator of the Shapley-Shubik power index for a voter
$v_{i}$ is the number of times $v_{i}$ is pivotal. In the unweighted voting
system, $p(v_{i})$ is the number of times $v_{i}$ is the $q^{\text{th}}$ voter
to join a maximal coalition. This is given by the number of maximal simplices
in $K$ with $q$ or more vertices that contain $v_{i}$. When $v_{i}$ is pivotal
it is fixed in the $q^{\text{th}}$ sequential position of a maximal coalition,
while the order in which the other voters join may vary. Thus the numerator of
the Shapley-Shubik index of $v_{i}$ is given by

$\sum_{j=q-1}^{d}|M_{j}\cap\text{st}(v_{i})|\cdot j!.$

Therefore, the Shapley-Shubik power index $SS_{u}(v_{i})$ is given by

$SS_{u}(v_{i})=\frac{\sum_{j=q-1}^{d}|M_{j}\cap\text{st}(v_{i})|\cdot
j!}{\sum_{j=q-1}^{d}|M_{j}|\cdot(j+1)!}.$

∎

######  Example 3.6.

Let $V$ be an unweighted voting system represented as the simplicial complex
from Example 2.10, with quota (a) $q=2$, (b) $q=3$. Note that the dimension of
the complex is $d=2$.

In the case (a),

$M_{1}=\\{\\{v_{1},v_{2}\\},\\{v_{1},v_{3}\\},\\{v_{2},v_{3}\\},\\{v_{2},v_{4}\\},\\{v_{2},v_{5}\\},\\{v_{4},v_{5}\\},\\{v_{5},v_{6}\\}\\},$

and

$M_{2}=\\{\\{v_{1},v_{2},v_{3}\\}\\}.$

The Shapley-Shubik power index for the voter $v_{1}$ is

$SS_{u}(v_{1})=\frac{\sum_{j=1}^{2}|M_{j}\cap\text{st}(v_{1})|\cdot
j!}{\sum_{j=1}^{2}|M_{j}|\cdot(j+1)!}=\frac{2\cdot 1!+1\cdot 2!}{7\cdot
2!+1\cdot 3!}=\frac{4}{20},$

and, similarly,

$SS_{u}(v_{2})=\frac{6}{20},SS_{u}(v_{3})=\frac{4}{20},SS_{u}(v_{4})=\frac{2}{20},SS_{u}(v_{5})=\frac{3}{20},SS_{u}(v_{6})=\frac{1}{20},SS_{u}(v_{7})=0.$

In the case (b), the only relevant are $2$-simplices, i.e. the set
$M_{2}=\\{\\{v_{1},v_{2},v_{3}\\}\\}$. The Shapley-Shubik indices are

$\displaystyle SS_{u}(v_{1})=\frac{|M_{2}\cap\text{st}(v_{1})|\cdot
2!}{|M_{2}|\cdot 3!}=\frac{1\cdot 2!}{1\cdot 3!}$ $\displaystyle=\frac{1}{3};$
$\displaystyle SS_{u}(v_{2})=SS_{u}(v_{3})$ $\displaystyle=\frac{1}{3};$
$\displaystyle SS_{u}(v_{i})$ $\displaystyle=0,\ \text{ for }4\leq i\leq 7.$

###  3.4. Weighted Banzhaf power index

We will demonstrate how the language of simplicial complexes enables us to
develop a formula for the Banzhaf power index of a voter in a weighted voting
system such that certain coalitions may be unlikely to form.

Let $V=V(q;w_{1},...,w_{n})$ be a weighted voting system with voters
$v_{1},...,v_{n}$, represented by the simplicial complex $K$ whose vertices
are the voters in $V$ and the set of simplices represents the set of all
possible coalitions in $V$, as before. We find that the numerator $c(v_{i})$
for the Banzhaf power index of a voter $v_{i}$ can be given by

$c(v_{i})=\sum_{j=0}^{d}|\\{s\in C_{j}^{v_{i}}\cap\text{st}(v_{i}):W_{s}\geq
q\\}|,$

where $d=\dim K$, $W_{s}$ is the sum of the weights of the vertices of $s$,
and $C_{j}^{v_{i}}$ is the set of all $j$-simplices in $K$ such that no
element in $C_{j}^{v_{i}}\setminus
v_{i}=C_{j}^{v_{i}}\setminus\text{st}(v_{i})$ reaches the quota. We get the
denominator by summing up all $c(v_{i})$’s.

Thus we proved the following

######  Proposition 3.7.

The Banzhaf power index for a voter $v_{i}$ in a weighted voting system
$V(q;w_{1},...,w_{n})$ is given by

$B(v_{i})=\frac{\sum_{j=0}^{d}|\\{s\in
C_{j}^{v_{i}}\cap\text{st}(v_{i}):W_{s}\geq
q\\}|}{\sum_{i=1}^{n}\sum_{j=0}^{d}|\\{s\in
C_{j}^{v_{i}}\cap\text{st}(v_{i}):W_{s}\geq q\\}|}.$

####  3.4.1. UN Security Council example

The United Nations Security Council has $15$ members, divided into two subsets
we will call PM and NPM, where PM consists of $5$ permanent members (United
States, United Kingdom, China, Russia, and France) and NPM consists of $10$
non-permanent members from the rest of the UN. For a resolution to pass in the
security council, it needs the support of all $5$ permanent members and at
least $4$ non-permanent members. This situation can be modelled as the
weighted voting system

$V(39;7,7,7,7,7,1,1,1,1,1,1,1,1,1,1).$

The Banzhaf index of any of the countries is easy to calculate and can readily
be found in the literature. For each permanent member, Banzhaf index is
$\approx 0.1669$; and for each non-permanent member, Banzhaf index is $\approx
0.0165$. Using our modified index, we can investigate how the power would
shift if certain members decided not to vote together, i.e. to not be in the
same coalition.

In one case, denoted “PM vs NPM,” if a non-permanent member (say NPM1) refuses
to vote with a permanent member, we can see that the power would shift. The
PMs have slightly less power ($\approx 0.1582$), and the NPMs have slightly
more power ($\approx 0.0232$), except for the NPM1, who now has no power.

In the case “NPM vs NPM” of two non-permanent members not voting together, say
NPM1 and NPM2, the PMs still have less power ($\approx 0.1610$) than they
originally did, and the NPMs still have slightly more power ($\approx 0.0206$)
than they originally did, except for the two quarelling NPMs who now have less
power ($\approx 0.0150$). See Figure 2.

Figure 2. Banzhaf power indices for the UN Security Council

####  3.4.2. Electoral College example

Take the Electoral College voting system from Example 3.2. We consolidate the
solid ”red wall” and ”blue wall” states into two variables called red and
blue, respectively, that hold the collective weights of those states. These
two agents, combined with the twelve identified swing states, make for a
computationally feasible example. The calculation will thus provide the power
of each swing as well as the powers of the blue and red states collectively.

The blue states have the total of 214 electoral votes, so that is their voting
weight. The red states combine to 166 electoral votes.

The twelve swing states have the following numbers of electoral votes: Arizona
– 11, Florida – 30, Georgia – 16, Iowa – 6, Maine – 4, Michigan – 15,
Minnesota – 10, New Hampshire – 4, North Carolina – 16, Ohio – 17,
Pennsylvania – 19, Wisconsin – 10.

The weighted voting system in question is therefore

$V(270;214,166,30,19,17,16,16,15,11,10,10,6,4,4).$

Table 1 contains the calculations (rounded to four decimals) of the Banzhaf
index for the swing states and the Banzhaf indices for the red wall and blue
wall states taken collectively, where the coalition [Blue States, Red States]
is forbidden. Note the surprising result that Florida in fact has more Banzhaf
power than the red wall states combined. This curiousity is corrected in the
Shapley-Shubik index.

State | Banzhaf index
---|---
Blue States | 0.3092
Red States | 0.0685
Florida | 0.1172
Pennsylvania | 0.0745
Ohio | 0.0669
Georgia | 0.0637
North Carolina | 0.0637
Michigan | 0.0594
Arizona | 0.0439
Minnesota | 0.0402
Wisconsin | 0.0402
Iowa | 0.0225
Maine | 0.0149
New Hampshire | 0.0149
Table 1. Forbidden Banzhaf power indices for the states in the U.S. Electoral
College

####  3.4.3. Bosnian-Herzegovinian parliament example

Another system we want to analyze using the modified Banzhaf index is the
parliament of Bosnia and Herzegovina. The political system in Bosnia and
Herzegovina is an incredibly complicated apparatus of nationalist and ethnic
parties that have varying allegiances and feuds within the country. After the
2018 Bosnian-Herzegovinian general election, there were 14 parties represented
within the House of Representatives which has 42 seats, ranging from 1 to 9
members per party. Counting each party with one voter with the weight of
however many seats they have in the Parliament, we can model this with a
weighted voting system $V(22;9,6,5,5,3,3,2,2,2,1,1,1,1,1)$. It is important to
point out that this is a simplified model, for the reasons that require an
extensive explanation of the Bosnian-Herzegovinian political system. A good
reference for this is [BGM21].

There is again a simplicial complex associated to this voting system in which
every party is one vertex and the edges between them show party alliances. One
can run the standard Banzhaf index or run it with a list of forbidden pairs of
voters, giving a more accurate representation of each party’s power.

To make things simpler for running the calculations, we only consider the
forbidden voting pairs of parties with 2 or more votes in parliament.111We use
the abbreviations for the names of the political parties. The full names can
be found at
https://www.izbori.ba/rezultati_izbora?resId=25&langId=1#/2/0/0/0/0/0. The
forbidden pairs are [SDA, SDP], [HDZ, SDP], [SDA, NS], [HDZ, NS], [SDP, SDS],
[NS, SDS], [SDP, SNSD], [NS, SNSD], [SNSD, SDS], and [SNSD, PDP].

The original Banzhaf indices (with no forbidden pairs) and forbidden Banzhaf
indices (with forbidden pairs) are given in Table 2 and also presented in
Figure 3. We can see that the power indices for some parties increase after
taking into account forbidden pairs, which means that those parties are more
likely to be a part of the winning coalition. This is also empirically
confirmed: The actual (as in 2022) government is made of SDA (forbidden
Banzhaf index $0.2543$), HDZ (forbidden index $0.1938$), DF (forbidden index
$0.1014$), and SNSD (forbidden index $0.0818$). On the other hand, the
decision of SDP that it will not be a part of any coalition with nationalist
parties (SDA, HDZ, SNSD, SDS) caused the decrease of the power index from
$0.1152$ to $0$. The same was with NS. In other words, SDP and NS cannot
theoretically be a part of the ruling coalition.

Party | Original Banzhaf Index | Forbidden Banzhaf index
---|---|---
SDA | 0.2441 | 0.2543
HDZ | 0.1152 | 0.1938
SDP | 0.1152 | 0.0000
DF | 0.0687 | 0.1014
SBB | 0.0452 | 0.0682
NS | 0.0452 | 0.0000
NB | 0.0226 | 0.0338
PDA | 0.0226 | 0.0338
A-SDA | 0.0226 | 0.0338
SNSD | 0.1397 | 0.0818
SDS | 0.0687 | 0.0794
PDP | 0.0452 | 0.0552
DNS | 0.0226 | 0.0338
SP | 0.0226 | 0.0338
Table 2. Original and forbidden Banzhaf power indices in the House of
Representatives of Bosnia and Herzegovina Figure 3. Original and forbidden
Banzhaf power indices in the House of Representatives of Bosnia and
Herzegovina

###  3.5. Weighted Shapley-Shubik power index

Let $V=V(q;w_{1},...,w_{n})$ be a weighted voting system with voters
$v_{1},...,v_{n}$, represented by the $d$-dimensional simplicial complex $K$
whose vertices are voters and simplices are possible coalitions. Let $M_{j}$
again denote the set of all maximal simplices in $K$ with $j+1$ vertices. For
a simplex $s$, $W_{s}$ denotes the sum of the weights of the vertices of $s$.

######  Theorem 3.8.

Let $\\{f_{1},...,f_{m}\\}$ be the set of all maximal simplices that contain
$v_{i}$. For a maximal simplex $f_{k}$, let $P_{j}^{f_{k},v_{i}}$ be the set
of all $j$-dimensional faces of $f_{k}$ such that for an arbitrary $\varphi\in
P_{j}^{f_{k},v_{i}}$ no $(j-1)$-dimensional face of $\varphi$ in
$\text{st}(v_{i})$ reaches the quota, and let $n_{f_{k}}$ denote the number of
vertices in $f_{k}$. Then the Shapley-Shubik power index for a voter $v_{i}\in
V$ is given by

$SS(v_{i})=\frac{\sum_{k=1}^{m}\sum_{j=0}^{n_{f_{k}}-1}|\\{s\in
P_{j}^{f_{k},v_{i}}\cap\text{st}(v_{i}):W_{s}\geq q\\}|\cdot
j!\cdot(n_{f_{k}}-(j+1))!}{\sum_{j=0}^{d}|\\{s\in M_{j}:W_{s}\geq
q\\}|\cdot(j+1)!}.$

###### Proof.

We can represent the maximal winning coalitions as the set of all maximal
simplices in $K$ that contain vertices whose weights sum up to $q$ or greater.
So the number of maximal winning coalitions is given by

$\sum_{j=0}^{d}|\\{s\in M_{j}:W_{s}\geq q\\}|.$

The denominator for the Shapley-Shubik power index, being the number of all
maximal sequential coalitions, is then given by

$\sum_{j=0}^{d}|\\{s\in M_{j}:W_{s}\geq q\\}|\cdot(j+1)!.$

The numerator for the Shapley-Shubik power index of a voter $v_{i}$ in $V$ is
the number of times $v_{i}$ is pivotal. Since the Shapley-Shubik index only
considers maximal winning coalitions, in order to compute the index we can
break down our simplicial complex $K$ into its maximal simplices and work
through each maximal simplex separately.

Note that for each maximal simplex $f=\\{v_{j_{1}},...,v_{j_{n_{f}}}\\}$,
where $n_{f}$ is the number of vertices in $f$, a voter $v_{i}\in f$ is
pivotal if the following is satisfied:

i) $i=j_{k}$ for a $k\in\\{1,...,n_{f}\\};$

ii) the total weight of the face $\\{v_{j_{1}},...,v_{j_{k}-1}\\}$ does not
reach the quota, i.e.

$w_{j_{1}}+\cdots+w_{j_{k}-1}<q;$

ii) the total weight of the face $\\{v_{j_{1}},...,v_{j_{k}}\\}$ reaches the
quota, i.e.

$w_{j_{1}}+\cdots+w_{j_{k}}\geq q.$

Hence we must only count the faces of $f$ containing $v_{i}$ that have weight
greater or equal to $q$, but would have weight less than $q$ if we removed
$v_{i}$. So the number of times $v_{i}$ is pivotal in a maximal sequential
coalition $f$ can be given by

$\sum_{j=0}^{n_{f}-1}|\\{s\in P_{j}^{f,v_{i}}\cap\text{st}(v_{i}):W_{s}\geq
q\\}|\cdot j!\cdot(n_{f}-(j+1))!.$

where $P_{j}^{f,v_{i}}$ is the set of all $j$-dimensional faces of the maximal
simplex $f$ such that for an arbitrary $\varphi\in P_{j}^{f,v_{i}}$, no
$(j-1)$-dimensional face of $\varphi$ in $\text{st}(v_{i})$ reaches the quota.
We multiply by $j!$ and $(n_{f}-(j+1))!$ to count the number of orders in
which voters join a coalition before and after $v_{i}$.

To get the total number of times $v_{i}$ is pivotal in $V$, we evaluate the
above expression for each maximal simplex that contains $v_{i}$ and take the
sum of the resulting value. Thus, if $\\{f_{1},...,f_{m}\\}$ is the set of all
maximal simplices that contain $v_{i}$, the numerator for the Shapley-Shubik
power index of $v_{i}$ equals

$\sum_{k=1}^{m}\sum_{j=0}^{n_{f_{k}}-1}|\\{s\in
P_{j}^{f_{k},v_{i}}\cap\text{st}(v_{i}):W_{s}\geq q\\}|\cdot
j!\cdot(n_{f_{k}}-(j+1))!.$

Therefore, the Shapley-Shubik power index for a voter $v_{i}$ is given by

$SS(v_{i})=\frac{\sum_{k=1}^{m}\sum_{j=0}^{n_{f_{k}}-1}|\\{s\in
P_{j}^{f_{k},v_{i}}\cap\text{st}(v_{i}):W_{s}\geq q\\}|\cdot
j!\cdot(n_{f_{k}}-(j+1))!}{\sum_{j=0}^{d}|\\{s\in M_{j}:W_{s}\geq
q\\}|\cdot(j+1)!}.$

∎

####  3.5.1. UN Security Council example

Consider the United Nations Security Council (the details are explained in
Example 3.4.1). With the Shapley-Shubik power index, the permanent members
have considerably more power than the non-permanent members; unrestricted,
each PM has $19.6\%$ of the voting power while each NPM has $0.19\%$ of the
voting power. As we consider two cases, one where a PM and NPM1 are
quarelling, and the other where NPM1 and NPM2 are quarelling, the power
shifts, but only by about a fifth of a percent. See Figure 4.

Figure 4. Shapley-Shubik power indices for the UN Security Council

####  3.5.2. Electoral College example

Following the Electoral College from Example 3.2, we calculated the values of
the swing states’ Shapley-Shubik indices using the same technique from 3.4.2.
Because the Shapley-Shubik index takes into account permutations, this
computation was especially taxing because the computer would have had to run
through $31!+32!$, or $2.71\cdot 10^{35}$, maximal sequential coalitions. By
consolidating the red and blue states, we made the problem into a manageable
solution while reflecting a more realistic situation. The resulting Shapley-
Shubik indices can be found in Table 3.

State | Shapley-Shubik index
---|---
Blue States | 0.3173
Red States | 0.1799
Florida | 0.1074
Pennsylvania | 0.0595
Ohio | 0.0524
Georgia | 0.0502
North Carolina | 0.0502
Michigan | 0.0468
Arizona | 0.0346
Minnesota | 0.0319
Wisconsin | 0.0319
Iowa | 0.0168
Maine | 0.0105
New Hampshire | 0.0105
Table 3. Forbidden Shapley-Shubik power indices for the states in the U.S.
Electoral College

####  3.5.3. Bosnian-Herzegovinian parliament example

Consider the voting system from Example 3.4.3. Because there are so many
quarrelling parties, the number of winning permutations is considerably less
than the original index, so the voting power shifts a lot too. Original
Shapley-Shubik indices (with no forbidden pairs) and forbidden Shapley-Shubik
indices (with forbidden pairs as in 3.4.3) are given in Table 4 and also
presented in Figure 5. We notice a similar pattern as with the Banzhaf
indices, which was commented on in Example 3.4.3.

Party | Original Shapley-Shubik index | Forbidden Shapley-Shubik index
---|---|---
SDA | 0.2439 | 0.3940
HDZ | 0.1178 | 0.1816
SDP | 0.1178 | 0.0000
DF | 0.0675 | 0.0905
SBB | 0.0441 | 0.0560
NS | 0.0441 | 0.0000
NB | 0.0217 | 0.0255
PDA | 0.0217 | 0.0255
A-SDA | 0.0217 | 0.0255
SNSD | 0.1450 | 0.0155
SDS | 0.0675 | 0.0832
PDP | 0.0441 | 0.0516
DNS | 0.0217 | 0.0255
SP | 0.0217 | 0.0255
Table 4. Original and forbidden Shapley-Shubik power indices in the House of
Representatives of Bosnia and Herzegovina Figure 5. Original and forbidden
Shapley-Shubik power indices in the House of Representatives of Bosnia and
Herzegovina

##  4\. Index calculators

This section contains some of the Python code to calculate the Banzhaf and the
Shapley-Shubik power index.

###  4.1. Banzhaf index calculator

The calculator method for the Bazhaf power index does the standard
computations given a list of all allowed, winning coalitions, then returns a
dictionary with each voter’s index.

The method takes three arguments: coalitions is a list of allowed coalitions,
weights is a dictionary of voters and their weights, and quota is the quota
needed to pass a vote.

def banzhafCalculator(coalitionsList, weights, quota):

voterList = weights.keys ()

numerators = {}

banzhafDict = {}

for voter in voterList:

numerators[voter] = 0

for coalition in coalitionsList:

coalWeight = coalitionWeight(coalition, weights)

for voter in coalition:

if (coalWeight - weights[voter]) $<$ quota:

numerators[voter] += 1

denominator = 0

for voter in voterList:

denominator += numerators[voter]

if denominator is 0:

return ”No Critical Voters”

for voter in voterList:

banzhafDict[voter] = numerators[voter]/denominator

return banzhafDict

Because our modification of the index is not in how it specifically counts
critical voters, but how it counts whole coalitions, most of the coding came
in the form of methods building up and filtering out the possible coalitions
to find every possible allowed, winning coalition. We broke it into three
methods, allSubsets which breaks down every list into every combination,
removeForbiddens which takes in pairs of forbidden voters and returns all
allowed coalitions, and winningCoalitions which returns all winning
coalitions.

def winningCoalitions(coalitionsList, weights, quota):

winnings = [ ]

for coalition in coalitionsList:

coalWeight = coalitionWeight(coalition, weights)

if coalWeight $>$= quota:

winnings.append(coalition)

return winnings

def removeForbiddens(voterSets, forbiddens):

returnableCoalitions = [ ]

allowed = 0

for voterSet in voterSets:

allowed = 0

for forbid in forbiddens:

if forbid[0] in voterSet and forbid[1] in voterSet:

allowed = 1

if allowed is 0:

returnableCoalitions.append(voterSet)

return returnableCoalitions

def allSubsets(coalition):

return list(chain.from_iterable(combinations(coalition, r)

for r in range(len(coalition)+1)))

###  4.2. Shapley-Shubik index calculator

The Shapley-Shubik calculator was a bit more involved than the Banzhaf
calculator, but used much of the same base. Taking into account permutations
made computations much slower to run the same processes.

def shapleyShubikCalculator(coalitions, weights, quota):

numDict = {}

voters = weights.keys()

for voter in voters:

numDict[voter] = 0

perms = [ ]

for coal in coalitions:

coalPerms = list(permutations(coal))

for p in coalPerms:

perms.append(p)

for perm in perms:

coalWeight = 0

winFlag = False

for voter in perm:

if (coalWeight + weights[voter] $>$= quota and (not winFlag)):

numDict[voter] += 1

winFlat = True

else:

coalWeight += weight[voter]

denom = 0

for voter in numDict:

denom += numDict[voter]

ssDict = {}

for voter in numDict:

ssDict[voter] = numDict[voter] / denom

return ssDict

The one extra helper method we had to add was maximumCoalitions because the
Shapley-Shubik index counts maximal coalitions.

def maximumCoalitions(coalitionsList):

maxCoalitions = [ ]

for coalition in coalitionsList:

maxCoalitions.append(coalition)

for coalition in coalitionsList:

for i in range(len(coalitionsList)):

if len(coalition) $<$ len(coalitionsList[ i ]):

counter = 0

for voter in coalition:

if voter in coalitionsList[i]:

counter +=1

if counter $>$= len(coalition) and coalition in maxCoalitions:

maxCoalitions.remove(coalition)

return maxCoalitions

##  5\. Directions for further research

As discussed in [AMS18], the traditional method for assigning weights to a
voter may not accurately represent the power of a member in a voting system
because it does not consider the diplomatic influence of the member. The
authors use an association matrix to quantify the “persuasive power” of a
voter and use the entries of that matrix to improve the Banzhaf power index.
We have developed formulas to calculate power indices in a voting system such
that certain coalitions may be forbidden, but reality suggests that the
probability of coalition formation may not always be binary. One reason for
this is that a group of voters may agree on some issues, but not on others. In
future work, we want to pursue this line of reasoning, but rather than
considering the “persuasive power” of a voter, we plan to consider the
probability that a voter will join a coalition. One should be able to
integrate this probability into the formulas developed in Section 3 without
too much trouble. Here is a rough idea.

Let $V=V(q;w_{1},...,w_{n})$ be a weighted voting system with voters
$v_{1},v_{2},...,v_{n}$. Let the $n\times n$ matrix $A$ have entries $a_{ij}$
such that $a_{ij}\in[0,1]$ is the probability that $v_{i}$ will form a
coalition with $v_{j}$, for $i,j\in\\{1,...n\\}$. Let
$C=\\{v_{j_{1}},...,v_{j_{k}}\\}$ be a coalition in $V$ such that $v_{i}\notin
C$. Let the $n\times 1$ matrix $\Omega$ have entries $\omega_{i,C}$ such that
$\omega_{i,C}$ is the probability that $v_{i}$ will join coalition $C$. We
define $\omega_{i,C}$ to be the average of all $a_{ij_{m}}$ for
$j_{m}\in\\{1,...k\\}$, that is,

$\omega_{i,C}=\frac{\sum_{m=1}^{k}a_{ij_{m}}}{k},$

where $k=|C|$. Using this set up, one should be able to develop a formula for
the improved Banzhaf power index of a voter $v_{i}$ in a weighted voting
system in terms of the probabilities $\omega_{i,C}$ for suitably defined $C$’s
via simplices. In a similar manner, one can improve the Shapley-Shubik power
index formulas.

Instead of using probabilities, vertices representing agents might have
“agreement matrices” attached to them. These would indicate which issues the
agents agree or disagree on. The entries might even reflect the levels of
agreement, i.e. they might take values in the real numbers rather than in the
set $\\{0,1\\}$. This setup is reminiscent of a _sheaf_. It is plausible that
sheaf-theoretic techniques (such as the Laplacian of sheaf cohomology) could
be used to define entirely new power indices that would capture much more of
the political dynamics between voters or political parties.

There are also other indices besides the Banzhaf and Shapley-Shubik, and they
all measure voting power slightly differently. One of interest is the Deegan-
Packel index [DP78], which is similar to the Shapley-Shubik index, however it
only considers minimal coalitions, those just big enough to pass a quota,
whereas Shapley-Shubik considers only maximal coalitions. There is much merit
to this index because often coalitions do not need to expend the extra energy
to get more votes than necessary, so this index warrants looking at minimal
coalitions and using our simplicial complex model to adjust it. Papers like
[Soh20] and [KC20] do something similar.

## References

  * [AK19] Joseph M. Abdou and Hans Keiding.  A qualitative theory of conflict resolution and political compromise.  Math. Social Sci., 98:15–25, 2019.
  * [AMS18] Krishna V. Acharya, Himadri Mukherjee, and Jajati Keshari Sahoo.  Approximation of Banzhaf indices and its application to voting games.  arXiv. 10.48550/ARXIV.1801.08029, 2018.
  * [Ban65] J. F. Banzhaf.  Weighted voting doesn’t work: A mathematical analysis.  Rutgers Law Review, 19(2):317–343, 1965.
  * [BGM21] Damir Banović, Saša Gavrić, and Mariña Mariño.  Political System of Bosnia and Herzegovina. Institutions, Actors, Processes.  Springer Cham, 2021.
  * [BP00] Sven Berg and Thommy Perlinger.  Connected coalitions, Pólya sequences and voting power indices.  Homo Oecon., 16:391–403, 2000.
  * [Col71] James Samuel Coleman.  Control of collectivities and the power of a collectivity to act.  in B. Lieberman (ed.) Social Choice, 269-298, 1971.
  * [dMLLBL20] Olivier de Mouzon, Thibault Laurent, Michel Le Breton, and Dominique Lepelley.  The theoretical Shapley-Shubik probability of an election inversion in a toy symmetric version of the US presidential electoral system.  Soc. Choice Welfare, 54(2-3):363–395, 2020.
  * [DP78] J. Deegan and E. W. Packel.  A new index of power for simple $n$-person games.  Internat. J. Game Theory, 7(2):113–123, 1978.
  * [Ede97] Paul H. Edelman.  A note on voting.  Math. Soc. Sci., 34(1):37–50, 1997.
  * [FP09] Davide L. Ferrario and Renzo A. Piccinini.  Strutture simpliciali in topologia, volume 50 of Quad. Unione Mat. Ital. Bologna: Pitagora Editrice, 2009.
  * [HG21] Jakob Hansen and Robert Ghrist.  Opinion dynamics on discourse sheaves.  SIAM J. Appl. Math., 81(5):2033–2060, 2021.
  * [IPBL19] Iacopo Iacopini, Giovanni Petri, Alain Barrat, and Vito Latora.  Simplicial models of social contagion.  Nat. Commun., 10:2485, 2019.
  * [KC20] Anna Khmelnitskaya and Michela Chessa.  Weighted and Restricted Deegan-Packel Power Indices.  Post-Print halshs-03042933, HAL, October 2020.
  * [Kur20] Sascha Kurz.  A note on limit results for the Penrose-Banzhaf index.  Theory Decis., 88(2):191–203, 2020.
  * [Mat03] Jiří Matoušek.  Using the Borsuk-Ulam theorem. Lectures on topological methods in combinatorics and geometry. Written in cooperation with Anders Björner and Günter M. Ziegler.  Universitext. Berlin: Springer, 2003.
  * [Mil12] Nicholas R. Miller.  Election Inversions by the U.S. Electoral College.  In Dan S. Felsenthal and Moshé Machover, editors, Electoral Systems: Paradoxes, Assumptions, and Procedures, pages 93–127. Springer, Berlin - Heidelberg, 2012.
  * [MM05] Mariusz Mazurkiewicz and Jacek W. Mercik.  Modified Shapley-Shubik power index for parliamentary coalitions.  Operations Research and Decisions, 15(2):43–52, 2005.
  * [MS18] Tomislav Marošević and Ivan Soldo.  Modified indices of political power: a case study of a few parliaments.  CEJOR, Cent. Eur. J. Oper. Res., 26(3):645–657, 2018.
  * [MV21] Andrea Mock and Ismar Volić.  Political structures and the topology of simplicial complexes.  Math. Social Sci., 114:39–57, 2021.
  * [Owe77] Guillermo Owen.  Values of games with a priori unions.  Math. Econ. Game Theory, Essays in Honor of O. Morgenstern, Lect. Notes Econ. Math. Syst. 141, 76-88 (1977), 1977\.
  * [Owe81] Guillermo Owen.  Modification of the Banzhaf-Coleman index for games with a priori unions.  Power, Voting, and Voting Power, 232-238 (1981), 1981.
  * [Pen46] L. S. Penrose.  The elementary statistics of majority voting.  J. R. Stat. Soc., 109(1):53–57, 1946.
  * [Per00] Thommy Perlinger.  Voting power in an ideological spectrum. The Markov-Pólya index.  Math. Soc. Sci., 40(2):215–226, 2000.
  * [RU16] E.A. Robinson and D.H. Ullman.  The Mathematics of Politics, Second Edition.  CRC Press, 2016.
  * [Soh20] Arnold Soh.  Deegan-Packel & Johnston spatial power indices and characterizations.  SSRN Electronic Journal, 01 2020.
  * [Spa95] Edwin H. Spanier.  Algebraic topology.  Berlin: Springer-Verlag, 1995.
  * [SS54] L. S. Shapley and Martin Shubik.  A method for evaluating the distribution of power in a committee system.  American Political Science Review, 48(3):787–792, 1954.
  * [WZLS20] Dong Wang, Yi Zhao, Hui Leng, and Michael Small.  A social communication model based on simplicial complexes.  Phys. Lett. A, 384(35):126895, 6, 2020.


# Multi-Instance Pose Networks: Rethinking Top-Down Pose Estimation

##  1 Multi-Instance Modulation Block (MIMB) Code

##  2 Implementation Details

##  3 Diminishing Returns with $\mathbf{N=3,4}$

##  4 Additional Results on COCO, CrowdPose and OCHuman

###  4.1 Additional results on COCO

###  4.2 Additional results on CrowdPose

###  4.3 Additional results on OCHuman

###  4.4 Robustness to Bounding Box Confidence

##  5 Individual Instance Performance

##  6 Ablation: MIMB

##  7 OCPose Dataset

##  8 Qualitative Results