# Worst-case Bounds on Power vs. Proportion in Weighted Voting Games with
Application to False-name Manipulation

Yotam Gafni<EMAIL_ADDRESS>
Technion - Israel Institute of Technology
Haifa 32000 Israel Ron Lavi<EMAIL_ADDRESS>
Technion - Israel Institute of Technology
Haifa 32000 Israel
University of Bath, UK
Bath BA2 7AY, United Kingdom Moshe Tennenholtz<EMAIL_ADDRESS>
Technion - Israel Institute of Technology
Haifa 32000 Israel

###### Abstract

Weighted voting games apply to a wide variety of multi-agent settings. They
enable the formalization of power indices which quantify the coalitional power
of players. We take a novel approach to the study of the power of big vs.
small players in these games. We model small (big) players as having single
(multiple) votes. The aggregate relative power of big players is measured
w.r.t. their votes proportion. For this ratio, we show small constant worst-
case bounds for the Shapley-Shubik and the Deegan-Packel indices. In sharp
contrast, this ratio is unbounded for the Banzhaf index. As an application, we
define a false-name strategic normal form game where each big player may split
its votes between false identities, and study its various properties.
Together, our results provide foundations for the implications of players’
size, modeled as their ability to split, on their relative power.

##  1 Introduction

Weighted Voting Games (WVGs) are a class of cooperative games that naturally
appear in diverse settings, such as parliaments, councils, and firm
shareholders. In recent years, they were found to naturally appear in multi-
agent systems such as VCG auctions (?) and other online economic systems. WVGs
are defined by a set of players, their weights, and a threshold $T$. A set of
players forming a coalition must have an aggregate weight of at least $T$. It
is natural to ask: What is a player’s power to influence decisions, or,
alternatively, what is a player’s share of the benefit of forming a coalition?
This power measure does not necessarily comply with the player’s proportional
weight. For example, consider a WVG with a large threshold $T$, a big player
with weight $T-1$ and a small player with weight $1$. Despite the large
discrepancy in their weights, a consensus is required for any motion to pass,
suggesting they have equal power. This view of power considers a player’s
pivotal role as “king-maker”– “To the victors go the spoils”.

Due to this reason, cooperative game theory studies power indices to capture
the true effective power of players in WVGs. This literature views the power
index of a player as a numeric predictor of utility. The most prominent power
indices include the Shapley-Shubik index (?), which stems from the more
general Shapley value (?), and the Banzhaf index (?). Other power indices
emphasize different aspects of the power structure, such as the Deegan-Packel
index (?), which we also study. Our work lies in the intersection of three
strands of WVG literature:

#### Big vs. Small Players and Group Power.

We layout a WVG model with big vs. small players and study the power of big
players compared to their vote proportion, assuming that all player weights
are natural numbers and consider all players with weight larger than 1 as
“big” and all players with weight 1 “small”. The inequality in voting – “big
vs. small” – is a main drive for the study of power indices, going back to the
formation of the US electoral college. ? (?) points out that Luther Martin of
Maryland, a staunch anti-federalist and one of the US founding fathers,
analyzed the then-forming electoral college in a manner similar to the Banzhaf
index. In the compilation by ? (?), p. 50, Martin claims:

> The number of delegates ought not to be in exact proportion to the number of
> inhabitants, because the influence and power of those states whose delegates
> are numerous, will be greater [even relative to their proportion] when
> compared to the influence and power of the other states…

The contrast between big vs. small players exists not only in traditional
voting settings but also in modern contexts. For example, we see multiple
situations in which several small websites (where here “small” is in terms of
their number of users) aggregate their market power by forming a unified
service platform to compete with a big incumbent website. Similarly, we see an
aggregation of computational power (e.g., mining pools in Bitcoin, consortia
of cloud computing services). The other direction of a big player splitting
itself to multiple small identities also exists, even when such a split is
costly in terms of advertising and maintaining the brand, e.g., flight search
engines and web hosting services.

? (?) demonstrate that in the settings of one big player and many small
players, the power of the big player can be higher than its proportional
weight. They do not answer (nor ask) the question of how large this ratio can
be. They also do not analyze the opposite direction, of whether this ratio is
bounded below by some constant, possibly smaller than 1. As we explain below,
our results generalize and answer these questions. Beyond the case of one big
player and many small players, which we completely characterize, our model and
results extend in two aspects:

  * •

_Arbitrary number of big (and small) players_ \- We obtain results regarding
the power vs. proportion of any specific one big player and regarding the
aggregate power of big players. As the distinction between big and small
immediately suggests, the relative power of these groups now becomes the
focus. Examples for such groups are the top 1% wealthy people, the G7
countries, Bitcoin’s large miners. These settings typically involve a few big
players and many small players. ? (?) and ? (?) take this to an extreme by
considering so-called “oceanic games” where there are a few significant large
players and a continuum of small players. In contrast, our results are not
asymptotic and hold for any arbitrary number of big and small players.

  * •

_The Banzhaf and Deegan-Packel indices_ \- Since different power indices
structuring naturally encapsulates different aspects of strategic power, it is
important to compare the results of different indices given our model, and
more so as the Banzhaf index gives qualitatively different results than the
other indices.

#### Power vs. Proportion

Our main theoretical results, given in Sections 3-5, characterize the ratio
between the aggregate power of the big players and their aggregate
proportional weight for different power indices. Most previous literature
analyzes ways to adjust voters’ voting weights in order to equate voting power
to actual weight. An early suggestion by ? (?) is that, in the UN, states
should be assigned seats proportional to the square root of their population,
in order to achieve proportional representation for each citizen, worldwide,
regardless of her state. ? (?, ?) further suggest an improvement in the form
of the _double square root_ voting system, where on top of assigning seats
proportional to the square root, the voting threshold (quota) of the
representative body itself is determined so to optimize proportionality.

More recent attention to whether a good choice of the quota can attain
proportionality is found in the works of ? (?, ?, ?, ?) and ? (?). Theoretical
guarantees, experimental results, and probabilistic models are suggested, for
which this occurs. For example, these works collectively establish that under
some probabilistic assumptions, setting the threshold $T$ to be about 50% of
the total sum of weights results in power being equal to proportion with high
probability. In contrast, our worst-case analysis of this problem does not
depend on probabilistic assumptions that might not hold in reality, due to the
independence assumptions or specific properties of the distributions. We also
show examples, where the threshold is very close to 50%, and the power is far
from proportional. In addition, it may not be possible to tune the threshold
$T$ because of exogenous dictates (e.g., important parliament votes, where a
two-thirds majority is required) or because the model aims to capture some
underlying reality (e.g., over the Internet) that constrains $T$.

A third approach focuses on the probabilistic modelling of the WVG weights.
For example, ? (?) show that if player weights are sampled uniformly from the
unit simplex, the expected Shapley-Shubik power of a player relative to its
proportion goes to 1 with rapid convergence in the number of players. ? (?)
study a different model where the ratio of the Shapley-Shubik index to
proportional weight in infinite chains of game instances asymptotically
approaches 1. ? (?) follow up with an experimental analysis of a similar model
thus further verifying the previous conceptual conclusions.

#### False-name manipulation in WVG

As an application of our main results for power vs. proportion, we define in
Section 6 a false-name strategic normal-form game where each big player may
split its votes between false identities. Power indices in weighted voting
games have different aspects: They can either measure the level of _influence_
of the players over possible decisions, or they can measure what ? (?) call
the “P-power”: The ability to extract rent, in terms of monetary transfers for
their causes. In parliamentary politics, this may take the form of budget or
regulation dedicated to special interest groups. ? (?) emphasizes that a goal
of power indices measurement is to be a measure of how much “bribe” a player
can extract for her vote. This view is important to justify why false-name
attacks are interesting and effective in WVGs: While in terms of influence,
splitting into multiple players may not matter (as they still vote
ideologically as a bloc), in terms of rent extraction, this restructuring of
party landscape matters.

? (?) are the first to study power indices in the context of false-name
manipulation, showing upper and lower bounds on a player’s gain (or loss) from
splitting its votes into two parts, for the Shapley-Shubik and Banzhaf
indices. They also address a range of computational issues, among them the
decision problem of splitting into two equal parts, which is NP-hard for both
indices. ? (?) show that the decision problem of benefiting from splitting
into two equal parts to be in PP, and ? (?) show it is PP-complete for the
Shapley-Shubik index, PP-complete for the Banzhaf index with three equal
splits, and PP-hard for both indices with general splits.

Our results contribute to the above literature on false-name splits by
unifying it with the two previously mentioned aspects (‘big vs. small’ and
‘power vs. proportion’) and by generalizing on two additional fronts:

  * •

_General splits_ \- We consider splits into multiple identities, rather than
splits into two or three identities. ? (?) initiated work on this more general
problem, where they show some upper and lower bounds for the individual power
gain from general splits compared to the original power. These bounds assume
that only a single agent splits, whereas the bounds we provide hold under any
combination of strategic manipulations by the agents.

  * •

_Global bounds on manipulation_ \- By our results for the power vs. proportion
we extract useful global bounds on manipulation. Regularly power is compared
before and after splits. Since previous work shows the most basic questions in
regard to successful power manipulation to be computationally hard, developing
global performance bounds is important.

###  1.1 Overview of Main Results

  * •

Our main theoretical results, given in Sections 3-5, characterize the ratio
between the aggregate power of the big players and their aggregate
proportional weight. For the Shapley-Shubik index, this ratio is bounded by 2,
and this analysis is asymptotically tight. In contrast, for the Banzhaf index,
this ratio is unbounded. The Deegan-Packel index gives the same qualitative
result as the Shapley-Shubik index: For this index, we prove an upper bound of
$3$ for the ratio in the worst case and give an example where the ratio is
asymptotically at least 2.

We give additional examples showing that while these results hold for the
aggregate power of all big players, they do not hold for the power of any
individual player. In contrast to these upper bounds, we show that the power
to proportion ratio cannot be lower bounded by any positive number. Thus,
while the aggregate power of the big group cannot be much larger than its
proportion, it can certainly be much smaller.

  * •

As an application of these results, given in Section 2, Section 6 defines a
false-name strategic normal-form game where each big player may split its
votes between false identities. Subsection 6.1 characterizes the worst-case
effects of splits on the individual power of a strategic big player in the
false-name game. In the special case of one big player, if the big player
splits its vote tokens to $k$ false identities, each with a weight of 1, its
power will be equal to its proportional weight (since all power indices are
symmetric). By our results, this is never less than one-half of the power of
the optimal split for the Shapley-Shubik index. On the other hand, if the big
player decides not to split, in some cases its power is unboundedly small
relative to its proportional weight.

  * •

To generalize the above conclusion, derived for the case of one big player, to
the aggregate power of any number of big players and any possible set of
players’ split strategies, we give a combinatorial conjecture for the Shapley-
Shubik index. We support our conjecture by extensive experimentation. The
conjecture claims that the big players may lose at most half of their
aggregate power from any combination of splits. Overall the results can be
interpreted in the following way: As a whole, the big players are not set to
lose much from opening the voting game to false-name manipulations, while on
the other hand some notion of fairness can be guaranteed as they can not
exceed double their proportional size.

##  2 Preliminaries

Weighted Voting Games (WVGs), starting with weighted majority games (?, ?),
aim to capture a situation where several players need to form a coalition.
Each player has a weight, and a subset of players can form a coalition if
their sum of weights passes a certain threshold. In this paper, we make a
distinction between “big” versus “small” players, where small players have a
weight of one. Formally,

######  Definition 2.1.

(Adapted from ?) A weighted voting game is a tuple $\\{A,m,T\\}$ with

$\begin{split}&A=\\{a_{1},...,a_{r}\\},M=\overbrace{\\{1,...,1\\}}^{m},\quad
1\leq T\leq m+\sum\limits_{j=1}^{r}a_{j},\end{split}$

where $a_{1},...,a_{r},m,T\in\mathbb{N}$, there are $r$ “big players”, $m$
“small players” of weight 1, and a coalition threshold $T$.111There is some
loss of generality by fixing the parameters $a_{i},T$ to be exact multiples of
the weight of the small player. Our model can be slightly generalized as
follows: Let $s$ be some minimal weight corresponding to some operational or
regulatory minimal size of a venture, or to an electoral threshold for
parliaments. Any player with an integer weight $s\leq w<2s$ is termed “small”
as small players are the ones that cannot split. The model as presented
corresponds to the case $s=1$ for tractability and readability but we believe
that our results hold for the more general model as well. We give more details
in the discussion section. We at times denote the small players as
$1_{1},...1_{m}$. Note that $A$ is a multi-set. When we write
$A\setminus\\{i\\}$, for some weight $i$, at most one occurrence of $i$ is
removed from $A$.

A basic question in WVGs is how to split the gains from forming a coalition
among its members. One possible notion of fairness is to split gains in a way
that is approximately proportional to the weights of the coalition members.

######  Definition 2.2.

The proportional value of a weighted voting game is $\displaystyle
P(A,m,T)=\frac{\sum\limits_{j=1}^{r}a_{j}}{m+\sum\limits_{j=1}^{r}a_{j}}.$

However, reality tells us that many times the “power” of players is different
than their proportional weight. Well-established literature on power indices
formally studies this by looking at our setting as a cooperative game. For the
analysis we have the following value function $v(S)$ which describes whether a
subset of players $S\subseteq A\cup M$ is able to form a coalition:

$v(S)=\begin{cases}1&\sum\limits_{s\in S}s\geq T\\\ 0&otherwise.\end{cases}$

We next compare the aggregate power of the big players, using several three
well-known power indices, to their aggregate proportional weight.

##  3 The Shapley-Shubik Power Index

Define the ordered tuple $A+M=(a_{1},...,a_{r},1_{1},...,1_{m})$. Let
$S_{m+r}$ be the group of all permutations operating on $m+r$ objects. For
some $\sigma\in S_{m+r}$, $\sigma(A+M)$ is the ordered tuple which results by
applying the permutation $\sigma$ to $A+M$. We usually omit the term $A+M$
when it is clear from the context. Define
$\displaystyle\sigma|_{p},\bar{\sigma}|_{p}$ as the set of all players
(strictly, non-strictly) preceding player $p$ in permutation $\sigma(A+M)$.
The permutation pivotal player indicator function for a player $p$ is

$\displaystyle\mathbbm{1}_{p,\sigma}=v(\bar{\sigma}|_{p})-v(\sigma|_{p}).$

In words, the indicator $\mathbbm{1}_{p,\sigma}$ is equal to one if the
players preceding $p$ in the permutation $\sigma(A+M)$ do not form a coalition
and adding $p$ enables the coalition formation. In such a case, we say that
$p$ is pivotal for $\sigma$. Note that $\mathbbm{1}_{p,\sigma}\in\\{0,1\\}$
and that each permutation has exactly one pivotal player.

######  Definition 3.1.

(Adapted from ?) The Shapley-Shubik power index of a weighted voting game
(A,m,T) is

$\begin{split}&\phi_{p}(A,m,T)=\mathbb{E}_{\sigma\sim
UNI(S_{m+r})}[\mathbbm{1}_{p,\sigma}],\\\ \end{split}$

for a player $p$ (whether a big player $a_{i}$ or a small player $1_{i}$),
where UNI is the uniform distribution over a discrete set.

This definition is a special case of the Shapley value applied to WVGs. Three
well-known properties of this power index are:

  * •

Symmetry.  $a_{i}=a_{j}\rightarrow\phi_{a_{i}}(A,m,T)=\phi_{a_{j}}(A,m,T)$.
This implies that for any two small players $i,j$,
$\phi_{1_{i}}(A,m,T)=\phi_{1_{j}}(A,m,T)$. Thus, for simplicity, we sometimes
write $\phi_{1}(A,m,T)$.

  * •

Efficiency.  $\sum\limits_{j=1}^{r}\phi_{a_{j}}(A,m,T)+m\phi_{1}(A,m,T)=1$,
i.e., the sum of all players’ Shapley-Shubik indices is 1.

  * •

Non-Negativity.  The Shapley-Shubik index of any player $p$ is non-negative:
$\phi_{p}(A,m,T)\geq 0$.

######  Definition 3.2.

The Shapley-proportional ratios are the global supremum (infiumum) over all
weighted voting games

$\bar{R}_{\phi}\\!=\\!\sup_{A,m,T}\frac{\sum\limits_{j=1}^{r}\phi_{a_{j}}(A,m,T)}{P(A,m,T)},\underline{R}_{\phi}\\!=\\!\inf_{A,m,T}\frac{\sum\limits_{j=1}^{r}\phi_{a_{j}}(A,m,T)}{P(A,m,T)}.$

Note that $\underline{R}_{\phi}\geq 0$ because of non-negativity.

######  Example 3.1 ($\bar{R}_{\phi}$ is at least 2).

For some $k\geq 2$, consider $A=\\{k\\},m=k-1,T=k$. Then
$\phi_{a_{1}}(A,m,T)=1$, while $P(A,m,T)=\frac{1}{2}+\frac{1}{4k-2}$.

In fact, this asymptotic lower bound is tight:

######  Theorem 3.1.

$\bar{R}_{\phi}=2.$

To prove Theorem 3.1, we first show a recursive relation for the Shapley-
Shubik index.

######  Lemma 3.1.

The following recursion holds for $\phi_{1}$

$\begin{split}&\phi_{1}(A,m,T)=\begin{dcases}\frac{1}{m+r}&T=1\\\
\frac{1}{m+r}\bigg{(}\sum\limits_{\begin{subarray}{c}1\leq i\leq r\\\
a_{i}<T\end{subarray}}\phi_{1}(A\\!\setminus\\!\\{a_{i}\\},m,T-a_{i})+(m\\!-\\!1)\phi_{1}(A,m\\!-\\!1,T-1)\bigg{)}&T>1\end{dcases}\end{split}$

###### Proof.

Fix a small player for which we measure the expected number of permutations
where it is pivotal. The recursion is done by the conditional expectation on
the identity of the first player in the permutation. If $T=1$, then if and
only if our fixed player is first, is it pivotal, which happens in probability
$\frac{1}{m+r}$. For $T>1$, if the first player in the permutation is $a_{i}$
and $a_{i}\geq T$, then our fixed player is not pivotal. If it is some big
player with $a_{i}<T$, then the problem reduces to the WVG with parameters
$(A\setminus\\{a_{i}\\},m,T-a_{i})$. Similarly, if a small player different
than our fixed player is first (for which there are $m-1$ alternatives), the
problem reduces to the WVG with parameters $(A,m-1,T-1)$. If our fixed player
is first, it is not pivotal. All the above events are with a uniform
probability of $\frac{1}{m+r}$. ∎

We now show a sufficient condition to prove Theorem 3.1. Let $\displaystyle
r_{j}=\left|\\{i\\}_{1\leq i\leq r,a_{i}=j}\right|$, the amount of big players
with weight equal to $j$, and let $a=\max A$. We have by definition

$\begin{split}&r=\sum\limits_{j=2}^{a}r_{j},\quad\quad\sum\limits_{j=1}^{r}a_{j}=\sum\limits_{j=2}^{a}r_{j}\cdot
j.\end{split}$ (1)

######  Lemma 3.2.

$\bar{R}_{\phi}=2$, if for any WVG parameters $(A,m,T)$ it holds that

$\displaystyle\phi_{1}(A,m,T)\geq\frac{m-{\sum}\limits_{i=2}^{a}r_{i}\min(i,T)}{m\left(m+{\sum}\limits_{i=2}^{a}r_{i}\min(i,T)\right)}.$

###### Proof.

By Example 3.1, $\bar{R}_{\phi}\geq 2$. We thus show $\bar{R}_{\phi}\leq 2$.
By the premise of the lemma,

$\begin{split}&\phi_{1}(A,m,T)\geq\frac{m-{\sum}\limits_{i=2}^{a}r_{i}\min(i,T)}{m\left(m+{\sum}\limits_{i=2}^{a}r_{i}\min(i,T)\right)}\geq\\\
&\frac{m-{\sum}\limits_{i=2}^{a}r_{i}\cdot
i}{m\left(m+{\sum}\limits_{i=2}^{a}r_{i}\cdot i\right)}\stackrel{{\scriptstyle
Eq.~{}\ref{defHistograms}}}{{=}}\frac{m-{\sum}\limits_{j=1}^{r}a_{j}}{m\left(m+{\sum}\limits_{j=1}^{r}a_{j}\right)}.\end{split}$
(2)

Now,

$\begin{split}&\sum_{j=1}^{r}\phi_{a_{j}}(A,m,T)\stackrel{{\scriptstyle\text{efficiency
+ symmetry}}}{{=}}1-m\phi_{1}(A,m,T)\stackrel{{\scriptstyle
Eq.~{}\ref{strongerInduction}}}{{\leq}}\\\ &1-\frac{\displaystyle
m-\sum\limits_{j=1}^{r}a_{j}}{\displaystyle
m+\sum\limits_{j=1}^{r}a_{j}}=2\frac{\displaystyle\sum\limits_{j=1}^{r}a_{j}}{\displaystyle
m+\sum\limits_{j=1}^{r}a_{j}}=2P(A,m,T).\end{split}$ (3)

If we divide both sides by $P(A,m,T)$, and since this holds for any parameters
$(A,m,T)$, we get $\bar{R}_{\phi}\leq 2$.

∎

We now prove Theorem 3.1 by proving the sufficient condition of Lemma 3.2
holds by induction.

######  Lemma 3.3.

For any WVG $(A,m,T)$,

$\displaystyle\phi_{1}(A,m,T)\geq\frac{m-{\sum}\limits_{i=2}^{a}r_{i}\min(i,T)}{m\left(m+{\sum}\limits_{i=2}^{a}r_{i}\min(i,T)\right)}.$

###### Proof.

We prove the lemma by induction on the threshold value $T$. For $T=1$, we have
$\phi_{1}(A,m,T)=\frac{1}{m+r}\geq\frac{m-r}{m(m+r)}$, which satisfies the
condition of Eq. 2, since
${\sum}\limits_{i=2}^{a}r_{i}\min(i,T)={\sum}\limits_{i=2}^{a}r_{i}=r$. Now
take a threshold value $T$, and assume for all lower threshold values and any
$A,m$, the condition holds. We make several justified assumptions:

  * •

Recall that we denoted $a=\max A$, the largest weight of a big player. We
assume w.l.o.g. $a\leq T$. If it is strictly higher than $T$, consider the
game $A^{\prime}$ where all $a_{i}>T$ values are set to $T$. Then
$\phi_{1}(A,m,T)=\phi_{1}(A^{\prime},m,T)$ because these players are pivotal
iff they appear in the permutation without a preceding pivotal player, in both
cases. For $A^{\prime}$, $a^{\prime}=\max A^{\prime}=T,\displaystyle
r^{\prime}_{j}=\left|\\{i\\}_{1\leq i\leq r,a^{\prime}_{i}=j}\right|$, and

$\begin{split}&\sum\limits_{i=2}^{a^{\prime}}r^{\prime}_{i}\min(i,T)=\sum\limits_{i=2}^{T}r_{i}\min(i,T)+\sum\limits_{i=T+1}^{a}r_{i}T=\sum\limits_{i=2}^{a}r_{i}\min(i,T).\end{split}$

Thus, proving the induction assumption for $(A^{\prime},m,T)$ also proves it
for $(A,m,T)$.

  * •

We assume $m>{\sum}\limits_{j=1}^{r}a_{j}$. Otherwise, we have by the non-
negativity property of the Shapley-Shubik index,

$\begin{split}&m\phi_{1}(A,m,T)\geq
0\geq\frac{m\\!-\\!\sum\limits_{j=1}^{r}a_{j}}{m\\!+\\!\sum\limits_{j=1}^{r}a_{j}}\stackrel{{\scriptstyle(1)}}{{=}}\frac{m\\!-\\!{\sum}\limits_{i=2}^{a}r_{i}\min(i,T)}{m\\!+\\!{\sum}\limits_{i=2}^{a}r_{i}\min(i,T)},\end{split}$

where $(1)$ is since $a\leq T$, and therefore for $1\leq i\leq a,\min(i,T)=i$.

  * •

We assume $m\geq 2$, as otherwise, by the $m>{\sum}\limits_{j=1}^{r}a_{j}$
assumption, $A=\emptyset$ and $\phi_{1}(A,m,T)=\frac{1}{m}$, which is exactly
the required induction hypothesis in this case.

We now develop the induction step. We can write

$\displaystyle m\phi_{1}(A,m,T)\stackrel{{\scriptstyle
Lemma~{}\ref{recursionLemma}}}{{=}}$ (Induction Step) $\displaystyle
m\\!\cdot\\!\frac{\sum\limits_{\begin{subarray}{c}1\leq k\leq r\\\
a_{k}<T\end{subarray}}\phi_{1}(A\\!\setminus\\!\\{a_{k}\\},m,T\\!-\\!a_{k})\\!+\\!(m\\!-\\!1)\phi_{1}(A,m\\!-\\!1,T\\!-\\!1)}{m+r}=$
$\displaystyle
m\\!\cdot\\!\frac{(m\\!-\\!1)\overbrace{\phi_{1}(A,m\\!-\\!1,T\\!-\\!1)}^{Exp1}\\!+\\!\sum\limits_{i=2}^{T-1}r_{i}\overbrace{\phi_{1}(A\\!\setminus\\!\\{i\\},m,T\\!-\\!i)}^{Exp2}}{m+r}\stackrel{{\scriptstyle(1)}}{{\geq}}$
$\displaystyle\frac{1}{m+r}\cdot\bigg{(}m\cdot\frac{m-1-{\sum}\limits_{j=2}^{T}r_{j}\min(j,T-1)}{m-1+\displaystyle\sum\limits_{j=2}^{T}r_{j}\min(j,T-1)}+$
$\displaystyle{\sum\limits_{i=2}^{T-1}}r_{i}\\!\cdot\\!\frac{m\\!-\\!\big{(}{\sum}\limits_{2\leq
j\neq i\leq
T}r_{j}\min(j,T-i)\big{)}\\!-\\!(r_{i}\\!-\\!1)\min(i,T\\!-\\!i)}{m\\!+\\!\big{(}{\sum}\limits_{2\leq
j\neq i\leq
T}r_{j}\min(j,T\\!-\\!i)\big{)}\\!+\\!(r_{i}\\!-\\!1)\min(i,T\\!-\\!i)}\bigg{)}\stackrel{{\scriptstyle(2)}}{{\geq}}$
$\displaystyle\frac{m-\displaystyle\sum\limits_{j=1}^{r}a_{j}}{m+\displaystyle\sum\limits_{j=1}^{r}a_{j}}\stackrel{{\scriptstyle
Eq.~{}\ref{defHistograms}}}{{=}}\frac{m-{\sum}\limits_{j=2}^{a}r_{j}\cdot
j}{m+{\sum}\limits_{j=2}^{a}r_{j}\cdot
j}\stackrel{{\scriptstyle(3)}}{{=}}\frac{m-{\sum}\limits_{j=2}^{a}r_{j}\min(j,T)}{m+{\sum}\limits_{j=2}^{a}r_{j}\min(j,T)},$

where in $(1)$ we replace $Exp1$ and $Exp2$ by the induction hypothesis for
lower values of $T$. For $Exp2$, note that in the game
$(A\setminus\\{i\\},m,T-i)$, for any weight $2\leq j\neq i\leq T$, the number
of players with weight $j$ is $r_{j}$, but for the weight $i$ it is $r_{i}-1$.
In Lemma A.1 of the appendix we show $(2)$, and $(3)$ is since $a\leq T$. The
RHS is the inductive result required by Eq. (2). This completes the induction
step. ∎

We conclude the section by examining two more illustrative examples, and
providing an individual upper bound for a player’s Shapley-Shubik index.

The following example shows that $\underline{R}_{\phi}=0$.

######  Example 3.2.

For any $k\geq 2$, choose $A=\\{k\\},m=k,T=2k$. Then
$\phi_{a_{1}}(A,m,T)=\frac{1}{k+1}$ while $P(A,m,T)=\frac{1}{2}$.

In example 3.2, a big player has less power in terms of the Shapley-Shubik
index than its proportional weight. In the next example the opposite holds:

######  Example 3.3.

For a single player, it may hold that its individual power to proportional
weight ratio is unbounded: Consider $A=\\{2,k\\},m=1,T=k+3$. Then
$\phi_{a_{1}}(A,m,T)=\frac{1}{3}$ while
$\frac{a_{1}}{m+\sum\limits_{j=1}^{r}a_{j}}=\frac{2}{k+3}$.

Nevertheless, there does exist an upper bound on the Shapley-Shubik index of
any individual big player:

######  Theorem 3.2.

$\displaystyle\phi_{a_{i}}(A,m,T)\leq\frac{a_{i}}{m+r}.$

###### Proof.

Let $S_{n}$ be the set of all permutations over $n$ items and $\sigma(A)$ for
some ordered set $A$ and some $\sigma\in S_{n}$ is the ordered set after
applying $\sigma$. For $j\in\\{1,...,|A|\\}$ let $\sigma_{j}(A)$ be the
element in the $j$-th position of the ordered set $\sigma(A)$, and
$\sigma|_{-j}(A)$ be the ordered set of size $|A|-1$ obtained by omitting the
element in position $j$ of $\sigma(A)$.

Two ways to think about sampling permutations for the calculation of the
Shapley-Shubik index uniformly at random are the following: First, we can take
$S_{m+r}$, the set of all permutations that are possible to apply to $A+M$,
and sample $\sigma\sim UNI(S_{m+r})$. Equivalently, for a fixed player
$a_{i}$, we can choose its position in the permutation applied to $A+M$,
namely $1\leq j\leq m+r$, uniformly at random, and then sample a permutation
over all other players $\sigma^{\prime}\sim UNI(S_{m+r-1})$. We then denote
$\sigma^{*}_{a_{i}}(j,\sigma^{\prime})$ as the unique permutation that has
$\sigma_{a_{i}}^{*}|_{j}(A+M)=a_{i}$ and
$\sigma_{a_{i}}^{*}|_{-j}(A+M)=\sigma^{\prime}(A\setminus\\{a_{i}\\}+M)$. Also
recall $[m+r]$ is a short-hand notation for the set $\\{1,...,m+r\\}$. This
enables rewriting $\phi_{a_{i}}(A,m,T)$ in terms of total expectation:

$\begin{split}&\phi_{a_{i}}(A,m,T)=\mathbb{E}_{\sigma\sim
UNI(S_{m+r})}[\mathbbm{1}_{a_{i},\sigma}]=\\\ &\mathbb{E}_{\sigma^{\prime}\sim
UNI(S_{m+r-1})}\left[\mathbb{E}_{j\sim
UNI([m+r])}[\mathbbm{1}_{a_{i},\sigma^{*}_{a_{i}}(j,\sigma^{\prime})}\mid\sigma^{\prime}]\right]\stackrel{{\scriptstyle(1)}}{{\leq}}\\\
&\mathbb{E}_{\sigma^{\prime}\sim
UNI(S_{m+r-1})}\left[\frac{a_{i}}{m+r}\right]=\frac{a_{i}}{m+r}\ \
.\end{split}$

The transition in $(1)$ is by the following argument. Let
$\nu_{j}(\sigma^{\prime})$ be the sum of the first $j$ elements in
$\sigma^{\prime}$. By definition, $a_{i}$ is pivotal in
$\sigma^{*}_{a_{i}}(j,\sigma^{\prime})$ iff $\nu_{j}(\sigma^{\prime})<T$ and
$\nu_{j}(\sigma^{\prime})+a_{i}\geq T$. Each choice of $j$ determines a unique
integer value for $\nu_{j}(\sigma^{\prime})$. I.e., there are overall $a_{i}$
integer values that have the property that their sum is smaller than $T$ and
with the addition of $a_{i}$ their sum is at least $T$, namely
$T-1,...,T-a_{i}$. There are at most $a_{i}$ unique values of $j$ (and, as a
result, of $\nu_{j}(\sigma^{\prime})$) that would result in $j$ being pivotal
for $\sigma^{*}_{a_{i}}(j,\sigma^{\prime})$. This is out of the total of $m+r$
possible values for $j$, uniformly chosen. So for any $\sigma^{\prime}$ the
inner expectation is bounded by $\frac{a_{i}}{m+r}$. ∎

##  4 The Banzhaf Index

We show a contrary result for the Banzhaf index (?), where an asymptotic
example has an unbounded ratio of aggregate big players’ power over their
proportion.

######  Definition 4.1.

(See ?) Let $P(S)$ be the power set of $S$, and $UNI$ be the uniform
distribution over a discrete set. The Absolute Banzhaf index of a WVG is:

$\begin{split}&\beta^{\prime}_{a_{i}}(A,m,T)=\mathbb{E}_{S\sim
UNI(P(A\setminus\\{a_{i}\\}\cup M)}\left[v(S\cup\\{a_{i}\\})-v(S)\right]\\\
&\beta^{\prime}_{1}(A,m,T)=\mathbb{E}_{S\sim UNI(P(A\cup
M\setminus\\{1\\})}\left[v(S\cup\\{1\\})-v(S)\right].\end{split}$

The Normalized Banzhaf index is:

$\beta_{a_{i}}=\frac{\beta^{\prime}_{a_{i}}(A,m,T)}{\displaystyle\sum\limits_{j=1}^{r}\beta^{\prime}_{a_{j}}+m\beta^{\prime}_{1}(A,m,T)}.$

While the Shapley-Shubik index gives equal probabilities to all permutations
over players, the Banzhaf index gives equal probabilities to all subsets of
players. The normalization is needed to achieve the efficiency property, where
summation over the indices of all players sums up to exactly one. The absolute
Banzhaf indices may sum to less or more than 1. For an individual absolute
Banzhaf index, by definition

$\beta^{\prime}_{a_{i}}(A,m,T)\leq 1$ (4)

######  Definition 4.2.

The Banzhaf-proportional ratios are the global supremum over all WVGs

$\begin{split}&\bar{R}_{\beta^{\prime}}=\sup_{A,m,T}\frac{\displaystyle\sum\limits_{i=1}^{r}\beta^{\prime}_{a_{i}}(A,m,T)}{P(A,m,T)},\\\
\end{split}$

A similar definition holds for $\bar{R}_{\beta}$.

While the power of the big players cannot be much larger than their
proportional weight according to the Shapley-Shubik index, the Banzhaf index
gives a different result:

######  Theorem 4.1.

$\bar{R}_{\beta^{\prime}},\bar{R}_{\beta}$ are unbounded.

The proof of Theorem 4.1, given in Appendix 4.1, shows that the ratio in the
following example goes to infinity with $k$.

######  Example 4.1.

Consider $A=\\{2k\\},m=k^{1.5},T=\frac{2k+k^{1.5}}{2}$. Then for $k=1600$, we
have

$P(A,m,T)\\!=\\!\frac{3200}{3200\\!+\\!1600^{1.5}}\\!=\\!\frac{1}{21},\beta_{a_{1}}(A,m,T)\\!\approx\\!\beta^{\prime}_{a_{1}}(A,m,T)\\!\approx\\!1.\\\
$

The intuition for the calculation is as follows. Since there is only one big
player, and all other players have a weight of one, only the size of the
subset of other players matters for the index. Choosing a subset $S$ of small
identical players with uniform probability is like letting each small player
participate in the chosen subset with probability $\frac{1}{2}$ (a Bernoulli
trial). So, the size of the subset is sampled from the Binomial distribution
with parameters $B(m,\frac{1}{2})$. Measure concentration properties of the
symmetric binomial distribution around its mean imply that with high
probability the size of the sampled set is close enough to $\frac{m}{2}$ so
that the big player in the example is pivotal. Details of this calculation can
be directly extracted from the argument in the proof of Theorem 4.1. The
normalized Banzhaf index is for these parameters is:

$\begin{split}&\beta_{a_{1}}(A,m,T)\\!\approx\\!\frac{0.999999}{0.999999\\!+\\!1600^{1.5}\cdot
3.52795*10^{-33}}\\!\approx\\!1.\end{split}$

This yields $21$ for both the ratio of absolute Banzhaf to proportion and
normalized Banzhaf to proportion. Notice that this example also serves as a
counter-example for a possible adaptation of Theorem 3.2 to the Banzhaf index,
as we have $\beta_{a_{1}}(A,m,T)\approx
1>\frac{3200}{64001}=\frac{a_{1}}{m+r}$.

Example 4.1 is in the spirit of Section b of ? (?) and the asymptotic results
analysed in Section 7 of ? (?). As far as we know, the exact bound that we
derive along with its formal analysis are new.

Theorem 7 of ? (?) states that if a single player splits her votes between
exactly two identities, its power as measured by the Banzhaf index cannot
increase by a factor larger than 2. In contrast, Theorem 4.1 above shows that,
with general splits, a player might end up decreasing its power by an
unbounded factor. This paints an overall non-favorable picture for false-name
manipulations as measured by the Banzhaf index.

##  5 The Deegan-Packel Index

######  Definition 5.1.

An all-pivotal set in a WVG is a set $S$ such that for any player $s\in S$,
$v(S)-v(S\setminus s)=1$. Let the set of all-pivotal subsets be $AP$. The
Deegan-Packel index is:

$\rho_{a_{i}}(A,m,T)=\mathbb{E}_{S\sim
UNI(AP)}\left[\frac{\mathbbm{1}_{a_{i}\in S}}{|S|}\right],$

where $UNI$ is the uniform disribution over a discrete set.

Thus, the Deegan-Packel index is similar to the Banzhaf index but takes into
account only the all-pivotal subsets that are, in a sense, the minimal
coalitions. It also considers the size of the coalition, so participation in a
large coalition results in less “power” than being a part of a small
coalition. One can verify that this index is efficient, i.e., the sum of
indices of all players is always exactly one.

######  Definition 5.2.

The Deegan-Packel-proportional ratio is the global supremum over all WVGs

$\begin{split}&\bar{R}_{\rho}=\displaystyle\sup_{A,m,T}\frac{\sum\limits_{i=1}^{r}\rho_{a_{i}}(A,m,T)}{P(A,m,T)}.\end{split}$

######  Example 5.1.

$\bar{R}_{\rho}\geq 2$: Let $\displaystyle A=\\{k\\},m=k-1,T=k$. Then
$\displaystyle\rho_{a_{1}}(A,m,T)=1$, while $P(A,m,T)=\frac{k}{2k-1}$.

######  Theorem 5.1.

$\bar{R}_{\rho}\leq 3$.

The theorem follows from lemmas given in Appendices D,E. It exploits
properties of the all-pivotal coalition in two threshold regimes: If the
threshold is high, we show that enough small players must participate in an
all-pivotal coalition, making the relative power of the big players in such a
coalition small. If the threshold is low, we are able to use algebraic
manipulations over binomials to derive the bound.

Regarding the power of each individual player, the following example shows
that Theorem 3.2 can not be adapted for the Deegan-Packel index.

######  Example 5.2.

There exists $\\{A,m,T\\}$ such that $\rho_{a_{1}}(A,m,T)>\frac{a_{1}}{m+r}$.

Consider $A=\\{99,\overbrace{101,...,101}^{1000}\\},m=100,T=101$. Any all-
pivotal coalition $S$ with $a_{i}\in S$ for $i\geq 2$ is a singleton. Any
coalition $S$ with $\forall i\geq 2,a_{i}\not\in S$ must include $a_{1}$,
otherwise the coalition does not reach the threshold $T$. For a coalition $S$
with $a_{1}\in S$, $\forall i\geq 2,a_{i}\not\in S$ to be all-pivotal it must
include exactly two small players. There are thus $\binom{m}{2}=4950$ all-
pivotal coalitions that do not include any $a_{i}$ with $i\geq 2$, and $5950$
all-pivotal coalitions overall. We conclude that
$\rho_{a_{1}}(A,m,T)=\frac{4950}{5950}\frac{1}{3}>\frac{99}{1101}=\frac{a_{1}}{m+r}$.
This example can be generalized with
$A=\\{k-1,\overbrace{k+1,...,k+1}^{k^{1.5}}\\},m=k,T=k+1$, and yield
$\rho_{a_{1}}(A,m,T)=\frac{\binom{k}{2}}{\binom{k}{2}+k^{1.5}}\frac{1}{3}\approx\frac{1}{3}$,
$\frac{a_{1}}{m+r}=\frac{k-1}{k^{1.5}+k+1}\approx\frac{1}{\sqrt{k}}$ for large
enough values of $k$. Thus, not only is $\rho_{a_{1}}(A,m,T)$ not upper
bounded by $\frac{a_{1}}{m+r}$, but it can supersede it by an arbitrary
multiple.

##  6 A Power Index False-name Game

In this section, we consider a framework general to all power indices under
the possibility of votes split by big players in the voting game. Our
discussion focuses on the Shapley-Shubik power index, where we give a
conjecture with empirical results. We begin with a notation. Given a natural
number $a$, define the integer partitions of $a$ as

$Partitions(a)=\bigcup_{i=1}^{a}\left\\{\\{b_{1},...,b_{i}\\}\bigg{|}\sum\limits_{j=1}^{i}b_{j}=a,\forall_{j=1}^{i}b_{j}\in\mathbb{N}\right\\}$

In words, the partitions of $a$ are all the different multi-sets of natural
numbers such that their sum is $a$. Note that we allow several big players to
split into multiple identities each, which is stronger than many other
incentive analyses of false-name attack where only one strategic player is
considered.

######  Definition 6.1 (The false-name weighted voting game for a power index
$\alpha\in\\{\phi,\beta,\rho\\}$).

Let $\\{A,m,T\\}$ be a WVG. We define a non-cooperative game with $|A|$
strategic players (which are the big players in the WVG). The strategy space
of each strategic player is $Partitions(a_{i})$. Given strategies
$s_{i}=\\{b_{i}^{1},...,b_{i}^{c_{i}}\\}$ for $1\leq i\leq r$, let
$B=\\{b_{1}^{1},...,b_{1}^{c_{1}},...,b_{r}^{1},...,b_{r}^{c_{r}}\\}$. The
payoff for player $i$ is

$u_{i}^{\alpha}(s_{1},...,s_{r})=\sum\limits_{j=1}^{c_{i}}\alpha_{b_{i}^{j}}(B,m,T).$

Let $c=\sum\limits_{i=1}^{r}c_{i}$ stand for the total number of elements in
$B$.

We wish to understand how the option to split (submit false-name bids) changes
the power of the strategic players. The previous section sheds light on this
question:

######  Theorem 6.1.

When $\alpha\in\\{\phi,\rho\\}$ (the Shapley-Shubik and Deegan-Packel
indices), then for any tuple of strategies $s_{1},...,s_{r}$,

$\sum\limits_{i=1}^{r}u_{i}^{\alpha}(s_{1},...,s_{r})\leq\bar{R}_{\alpha}P(A,m,T).$

In particular, this happens in any mixed or pure Nash or correlated
equilibrium of the game.

Recall that $\bar{R}_{\phi}=2,\bar{R}_{\rho}\leq 3$ (by Theorems 3.1,5.1
respectively). Note that by Theorem 4.1, this theorem can not hold with any
finite bound for the Banzhaf index.

###### Proof.

Given $B_{s_{1},...,s_{r}}$ as the set of big players in the WVG after the
application of the splitting strategies, we have

$\displaystyle\sum\limits_{i=1}^{r}\sum\limits_{j=1}^{c_{i}}\alpha_{b_{i}^{j}}(B_{s_{1},...,s_{r}},m,T)\leq\bar{R}_{\alpha}\frac{\sum\limits_{i=1}^{r}\sum\limits_{j=1}^{c_{i}}b_{i}^{j}}{m+\sum\limits_{i=1}^{r}\sum\limits_{j=1}^{c_{i}}b_{i}^{j}}=\bar{R}_{\alpha}\frac{\sum\limits_{j=1}^{r}a_{j}}{m+\sum\limits_{j=1}^{r}a_{j}}.$

∎

Thus, strategically splitting vote weights using false-name manipulations
cannot increase the overall Shapley-Shubik power of the big players to be more
than double their proportional weight. On the other hand, we conjecture that
such strategic manipulations cannot harm their overall Shapley-Shubik power
too much:

######  Conjecture 6.1.

For the Shapley-Shubik index $\phi$ with any weighted voting game
$\\{A,m,T\\}$ and a choice of strategies resulting in a corresponding weighted
voting game $\\{B,m,T\\}$, it holds that

$\displaystyle\sum\limits_{i=1}^{r}\phi_{a_{i}}(A,m,T)\leq
2\sum\limits_{i=1}^{r}\sum\limits_{j=1}^{c_{i}}\phi_{b_{i}^{j}}(B,m,T).$

######  Remark 6.1.

  * •

Section 6.2 gives empirical results supporting the conjecture, obtained from
an exhaustive search over small WVGs.

  * •

Theorem 3.1 is a special case of the conjecture, where each player $i$’s
strategy choice is $\overbrace{\\{1,...,1\\}}^{a_{i}}$.

  * •

Theorem 6 of ? (?) states that a single player that splits her votes to
exactly two identities cannot decrease its Shapley-Shubik index by more than a
factor of $\frac{n+1}{2}$. Our conjecture gives a much stronger bound for the
aggregate power of big players: The worst decrease of aggregate power, caused
by any combination of splits, is by a constant factor of 2.

Combining Theorem 6.1 and Conjecture 6.1 yields:

######  Corollary 6.1.

For all strategies $s_{1},...,s_{r}$ in the Shapley false-name WVG
$\\{A,m,T\\}$, if Conjecture 6.1 holds,

$\frac{1}{2}\sum\limits_{i=1}^{r}\phi_{a_{i}}(A,m,T)\leq\sum\limits_{i=1}^{r}u_{i}^{\phi}(s_{1},...,s_{r})\leq
2P(A,m,T).$

Our conclusions regarding the Shapley-Shubik power index are therefore the
following: false-name attacks can unboundedly increase the aggregate Shapley-
Shubik power index of the big players, e.g., by splitting to singletons
(Example 3.2). However, no attack can increase the power to more than twice
the power resulting from the simple attack of splitting to singletons (Theorem
6.1). False-name attacks can also decrease the Shapley-Shubik index (Example
3.1). However, we believe, as expressed in Conjecture 6.1, that no false-name
attack can decrease the aggregate Shapley-Shubik power to be less than one-
half of the original power.

Example 4.1 shows that an adaptation of Conjecture 6.1 does not hold for the
Banzhaf index. For the Deegan-Packel index, even though Theorem 5.1 holds
(similar to the Shapley-Shubik index case, and unlike the Banzhaf index case),
an analogue of the conjecture fails to hold, as demonstrated in the following
example:

######  Example 6.1.

Consider $A=\\{16\\},B=\\{8,8\\},m=16,T=17$. For the WVG $(A,m,T)$ there are
$16$ all-pivotal coalitions, all consisting of $a_{1}$ and some single small
player, and so $\rho_{a_{1}}(A,m,T)=\frac{1}{2}$. For the WVG $(B,m,T)$, there
are $16$ all-pivotal coalitions that include both $b_{1},b_{2}$. There are
$\binom{16}{9}=11440$ all-pivotal coalitions with only $b_{1}$ (out of the big
players), and the same amount with only $b_{2}$. There are no coalitions with
no big players. Overall we have

$\rho_{b_{1}}(B,m,T)+\rho_{b_{2}}(B,m,T)=2\rho_{b_{1}}(B,m,T)=2\frac{16\cdot\frac{1}{3}+11440\cdot\frac{1}{10}}{22896}\approx
0.1004,$

and so the ratio between the aggregate power of the big players before and
after the split is approximately 5, larger than $\bar{R}_{\rho}\leq 3$. The
example can further be generalized with $A=\\{2k\\},B=\\{k,k\\},m=2k,T=2k+1$.
Then
$\rho_{a_{1}}(A,m,T)=\frac{1}{2},\rho_{b_{1}}(B,m,T)+\rho_{b_{2}}(B,m,T)=2\frac{2k\cdot\frac{1}{3}+\binom{2k}{k+1}\cdot\frac{1}{k+2}}{2\binom{2k}{k+1}+2k}\leq\frac{k+\binom{2k}{k+1}\cdot\frac{1}{k+2}}{\binom{2k}{k+1}+k}\stackrel{{\scriptstyle
k\leq\binom{2k}{k+1}\cdot\frac{1}{k+2}}}{{\leq}}\frac{2}{k+2}$ for large
enough $k$.

###  6.1 The Worst-case Effects of False-name Manipulation for a Single Player

While the total utility of the big players is conjectured to not lose much by
splits, a single player may multiplicatively lose arbitrarily much in B
compared to A. This is evident by Example 3.3, but we give two additional
examples that do not require all players to fully split. In the first example,
the player that chooses not to split loses by this choice. In the second
example, the player that chooses to split loses by this choice.

######  Example 6.2.

Consider
$A=\\{k,k,k\\},B=\\{k,\overbrace{1,...,1}^{k},\overbrace{1,...,1}^{k}\\},m=k,T=4k$.
Then

$\begin{split}&\phi_{a_{1}}(A,m,T)=\frac{1}{k+3}\qquad\phi_{b_{1}^{1}}(B,m,T)=\frac{1}{3k+1}.\end{split}$

Thus, with $k\geq 6$, the ratio is higher than 2. The example can be
generalized to exceed any bound $r$, with
$A=\overbrace{\\{k,...,k\\}}^{r+1},B=\\{k,\overbrace{\overbrace{1,...,1}^{k},...,\overbrace{1,...,1}^{k}}^{r}\\},m=k,T=(r+2)k.$

######  Example 6.3.

Consider $A=\\{k,k\\},B=\\{\overbrace{1,...,1}^{k},k\\},m=0,T=k+1$. Then

$\begin{split}&\phi_{a_{1}}(A,m,T)=\frac{1}{2}\qquad\sum\limits_{j=1}^{a_{1}}\phi_{b_{1}^{j}}(B,m,T)=\frac{1}{k+1}.\end{split}$

The basic upper bound on the power of a single big player that Theorem 3.2
yields, continues to hold under the possibility of splits, and it decreases as
the number of splits increases:

######  Corollary 6.2.

For a player $i$, and any strategy choice $s_{1},...,s_{r}$ of the players, it
holds that:

$\begin{split}&\bm{u_{i}^{\phi}(s_{1},...,s_{r})}=\sum\limits_{j=1}^{c_{i}}\phi_{b_{i}^{j}}(B,m,T)\stackrel{{\scriptstyle
THM~{}\ref{lemmaBasicUpperbound}}}{{\leq}}\\\
&\sum\limits_{j=1}^{c_{i}}\frac{b_{i}^{j}}{m+\sum\limits_{k=1}^{r}c_{k}}\leq\sum\limits_{j=1}^{c_{i}}\frac{b_{i}^{j}}{m+r+(c_{i}-1)}=\\\
&\bm{\frac{a_{i}}{m+r+(c_{i}-1)}}.\end{split}$

Note that we derive this corollary only for the Shapley-Shubik index, as
examples 4.1 and 5.2 serve as counter-examples for the Banzhaf and Deegan-
Packel indices respectively.

######  Corollary 6.3.

When $\alpha\in\\{\phi,\rho\\}$, then in any setting with a single big player
$a_{1}$, $m$ small players, and any threshold $T$, the big player has a
strategy that guarantees a fraction of at least $1/\bar{R}_{\alpha}$ of the
power of its best possible strategy. In particular, this is the “full split”
strategy.

###### Proof.

An immediate application of Theorem 6.1 yields that for any strategy $s_{1}$,

$u_{1}^{\phi}(s_{1})\leq\bar{R}_{\alpha}P(A,m,T).$

Thus, the proportional value for the big player is at least
$1/\bar{R}_{\alpha}$ as good as the best possible strategy. By the symmetry
property of the Shapley-Shubik index,
$s_{1}=\overbrace{\\{1,...,1\\}}^{a_{1}}$ (“full split”) guarantees the
proportional value. ∎

It is important to note that not every strategy guarantees this ratio, as
demonstrated by Example 3.1. In the example, a player choosing not to split
(or split into large pieces) will achieve much less than her optimal strategy.

###  6.2 Experimental Results

To support Conjecture 6.1, we ran an exhaustive validation over all WVGs with
$m<25,\sum\limits_{j=1}^{r}a_{j}<25$. The python code can be found at
github.com/yotam-gafni/shapley_fairness_result. A total of $5,833,920$ WVGs
were checked against all valid sub-partitions of them, resulting in a total of
$1,246,727,916$ valid pairs being compared. The maximal ratio attained was
$1.958333^{\prime}$. The minimal ratio attained was $0.08$. The exhaustive
search consists of two parts. First, using dynamic programming over a dual
recursion to that of Lemma 3.1 (see Appendix G), we built a full recursion
table of all Shapley-Shubik indices for the WVGs in the range. Then, for each
WVG we considered all valid partition strategy sets $B$.

While the maximal ratio over all instances of the experimental analysis was
close to $2$, in most instances the ratio was much closer to 1. Figure 1 shows
a histogram of the number of cases (on the y-axis) for different possible
ratios between 0 and 2 (on the x-axis). As can be seen from the figure, the
ratio is concentrated around 1.

$0$$0.5$$1$$1.5$$2$$0$$0.2$$0.4$RatioInstance percent - Exhaustive search

Figure 1: Ratio of big players’ power before and after splits

##  7 Discussion and Future Directions

Many questions remain open. We find Conjecture 6.1 hard to prove even in
limited settings. For example, consider the WVG $\\{B,m,T\\}$ where
$m<T<\sum_{i=1}^{|B|}b_{i}$, i.e., the overall weights of the small players
are less than the threshold, which itself is less than the overall weights of
the big players. In this case, it is possible to show that if we take
$A=\\{\sum_{i=1}^{|B|}b_{i}\\}$, i.e., a single big player, then that player
has a Shapley-Shubik index of 1 in the WVG $\\{A,m,T\\}$. The conjecture’s
inequality in that case then states that the sum of Shapley-Shubik indices of
the big players in $B$ is larger or equal to $\frac{1}{2}$. This reads as a
very clean combinatorial problem: If we draw a permutation at random over a
multi-set of integers $m\times\\{1\\}\cup B$, with
$m<T<\sum_{i=1}^{|B|}b_{i}$, then the probability that the pivotal player
(crossing the threshold $T$) is “big” is higher than the probability that it
is “small”. This can be even simplified further if we assume all big players
are of identical size $k$.

The model itself could be generalized so that the threshold value $T$ and big
players’ values $A$ are not a multiple of the small players value, or into
some other idea of looser distinctions between big and small players. For
example, the Israeli Parliament currently has a minimal threshold of $3$ seats
for a party to enter parliament. Thus, prior to elections, it does not make
sense for a bloc to split into parties with less than at least $3$ seats each
(as indicated by polls). Therefore, maintaining our notion that “small” blocs
are these that can not split, any player $a$ with size $3\leq a<6$ is
considered small. Any other player is considered big. Since not all small
players now must have the same size, we no longer parameterize them by the
number $m$, but by the multi-set $M$ of small players. As for $T$, consider
that the threshold to pass a basic law in the Israeli Parliament is an
absolute majority of $61$. This is not a multiple of $s=3$, unlike the case of
$s=1$ we consider throughout the paper. As a concrete example, consider a WVG
with weights $A=\\{8,7\\},M=\\{5,3\\},T=10$. Then,
$P(A,M,T)=\frac{8+7}{8+7+5+3}=\frac{15}{23},\sum_{j=1}^{2}\phi_{a_{j}}(A,M,T)=\frac{2}{3}$,
and so $\frac{\sum_{j=1}^{2}\phi_{a_{j}}(A,M,T)}{P(A,M,T)}=\frac{46}{45}\leq
2$. As we can see, the claim of Theorem 3.1 is still meaningful (with
appropriate adjustments) in these settings. In order to test it, we ran an
exhaustive validation over all WVGs with
$\sum_{j=1}^{r}a_{j}<\sum_{j=1}^{|M|}m_{j}<25$. We find that over this
set,222We remind the reader that if
$\sum_{j=1}^{r}a_{j}\geq\sum_{j=1}^{|M|}m_{j}$, then
$P(A,M,T)\geq\frac{1}{2}$, and so the ratio must be at most $2$. For this
reason we forgo exact calculation for these WVGs.  indeed $\bar{R}_{\phi}\leq
2$. A total of $90,141$ WVGs were checked. The maximal ratio attained was
$\approx 1.8585$, for the instance
$A=\\{22\\},M=\overbrace{\\{3,...,3\\}}^{8},T=22$. The minimal ratio attained
was $\approx 0.22705$, for the instance
$A=\\{23\\},M=\overbrace{\\{3,...,3\\}}^{8},T=47$. We derived similar results
for every $2\leq s\leq 11$, which is the relevant range of interest for the
WVGs examined. The results are summarized in Table 1 (ratios are given
approximately).

s | # Instances | Max ratio | Min ratio
---|---|---|---
2 | $161,737$ | $1.88628$ | $0.15719$
3 | $90,141$ | $1.8585$ | $0.22705$
4 | $46,262$ | $1.83673$ | $0.291925$
5 | $23,386$ | $1.8666$ | $0.40869$
6 | $12,691$ | $1.88888$ | $0.40869$
7 | $8,075$ | $1.8095$ | $0.510869$
8 | $5,310$ | $1.8088$ | $0.510869$
9 | $2,642$ | $1.5555$ | $0.681159$
10 | $1,021$ | $1.46666$ | $0.681159$
11 | $231$ | $1.3939$ | $0.681159$
Table 1: Aggregate big players’ power vs. proportion ratios with varying
“small” definition

Other interesting extensions for the work can be deriving tight bounds for the
Deegan-Packel index, and exploring similar results for other power indices in
common use, such as these of ? (?), ? (?), and ? (?). Generalizing our results
to a larger class of cooperative games is also interesting.

## Acknowledgements

A preliminary version of this paper has appeared in the proceedings of the
30th International Joint Conference on Artificial Intelligence (IJCAI-21), and
was presented at the 8th International Workshop on Computational Social Choice
(COMSOC-2021). We thank all anonymous reviewers for their helpful comments.

Yotam Gafni and Moshe Tennenholtz were supported by the European Research
Council (ERC) under the European Union’s Horizon 2020 research and innovation
programme (Grant No. 740435).

Ron Lavi was partially supported by the ISF-NSFC joint research program (grant
No. 2560/17).

##  A Proof of Step (2) in the Induction Step Equation, Used in the Proof of
Lemma 3.3

######  Lemma A.1.

$\begin{split}&\frac{m}{m+r}\cdot\frac{m-1-{\sum}\limits_{j=2}^{T}r_{j}\min(j,T-1)}{m-1+\displaystyle\sum\limits_{j=2}^{T}r_{j}\min(j,T-1)}+\\\
&{{{\sum\limits_{i=2}^{T-1}}}}\frac{r_{i}}{m+r}\cdot\frac{m-\left({\sum}\limits_{2\leq
j\neq i\leq
T}r_{j}\min(j,T-i)\right)-(r_{i}-1)\min(i,T-i)}{m+\left({\sum}\limits_{2\leq
j\neq i\leq
T}r_{j}\min(j,T-i)\right)+(r_{i}-1)\min(i,T-i)}\geq\frac{m-\displaystyle\sum\limits_{j=1}^{r}a_{j}}{m+\displaystyle\sum\limits_{j=1}^{r}a_{j}}\end{split}$

###### Proof.

We define (within the following equations), $G^{-}(A,m,T,i),G^{+}(A,m,T,i)$
for shorter notations. Observe that for any weight $2\leq i\leq T-1$,

$\begin{split}&G^{-}(A,m,T,i)\stackrel{{\scriptstyle
def.}}{{=}}m-\left(\sum\limits_{2\leq j\neq i\leq
T}r_{j}\min(j,T-i)\right)-(r_{i}-1)\min(i,T-i)\geq\\\
&m-\left(\sum\limits_{2\leq j\neq i\leq T-1}r_{j}\cdot
j\right)-r_{T}\cdot(T-1)-(r_{i}-1)i=m-\sum\limits_{j=2}^{T}r_{j}\cdot
j+r_{T}+i=m-\sum\limits_{j=1}^{r}a_{j}+r_{T}+i,\end{split}$

and similarly,

$\begin{gathered}G^{+}(A,m,T,i)\stackrel{{\scriptstyle
def.}}{{=}}m+\left(\sum\limits_{2\leq j\neq i\leq
T}r_{j}\min(j,T-i)\right)+(r_{i}-1)\min(i,T-i)\leq
m+\sum\limits_{j=1}^{r}a_{j}-r_{T}-i,\\\
\sum\limits_{j=2}^{T}r_{j}\min(j,T-1)=\sum\limits_{j=1}^{r}a_{j}-r_{T}.\end{gathered}$

By making the relevant substitutions to the LHS of the lemma’s claim, we thus
have,

$\begin{split}&\frac{m}{m+r}\cdot\frac{m-1-\displaystyle\sum\limits_{j=2}^{T}r_{j}\min(j,T-1)}{m-1+\displaystyle\sum\limits_{j=2}^{T}r_{j}\min(j,T-1)}+{{{\sum\limits_{i=2}^{T-1}}}}\frac{r_{i}}{m+r}\cdot\frac{G^{-}(A,m,T,i)}{G^{+}(A,m,T,i)}\geq\\\
&\frac{m}{m+r}\cdot\frac{m-\displaystyle\sum\limits_{j=1}^{r}a_{j}+r_{T}-1}{m+\displaystyle\sum\limits_{j=1}^{r}a_{i}-r_{T}-1}+{{{\sum\limits_{i=2}^{T-1}}}}\frac{r_{i}}{m+r}\cdot\frac{m-\displaystyle\sum\limits_{j=1}^{r}a_{i}+r_{T}+i}{m+\displaystyle\sum\limits_{j=1}^{r}a_{i}-r_{T}-i}.\end{split}$
(5)

For the case where $r_{T}=1$ we further have

$\begin{split}&\frac{m}{m+r}\cdot\frac{m-\sum\limits_{j=1}^{r}a_{j}+r_{T}-1}{m+\sum\limits_{j=1}^{r}a_{j}-r_{T}-1}+\sum\limits_{i=2}^{T-1}\frac{r_{i}}{m+r}\cdot\frac{m-\sum\limits_{j=1}^{r}a_{j}+r_{T}+i}{m+\sum\limits_{j=1}^{r}a_{j}-r_{T}-i}=\\\
&\frac{m}{m+r}\cdot\frac{m-\sum\limits_{j=1}^{r}a_{j}}{m+\sum\limits_{j=1}^{r}a_{j}-2}+\sum\limits_{i=2}^{T-1}\frac{r_{i}}{m+r}\cdot\frac{m-\sum\limits_{j=1}^{r}a_{j}+i+1}{m+\sum\limits_{j=1}^{r}a_{j}-i-1}\stackrel{{\scriptstyle(1)}}{{\geq}}\\\
&\frac{m+1}{m+r}\cdot\frac{m-\sum\limits_{j=1}^{r}a_{j}}{m+\sum\limits_{j=1}^{r}a_{j}}+\sum\limits_{i=2}^{T-1}\frac{r_{i}}{m+r}\cdot\frac{m-\sum\limits_{j=1}^{r}a_{j}}{m+\sum\limits_{j=1}^{r}a_{j}}=\\\
&\frac{m+\sum\limits_{i=2}^{T-1}r_{i}+r_{T}}{m+r}\cdot\frac{m-\sum\limits_{j=1}^{r}a_{j}}{m+\sum\limits_{j=1}^{r}a_{j}}=\frac{m-\sum\limits_{j=1}^{r}a_{j}}{m+\sum\limits_{j=1}^{r}a_{j}},\end{split}$
(6)

where for $(1)$ note that by arithmetics,
$\displaystyle\frac{m}{m+\sum\limits_{j=1}^{r}a_{j}-2}\geq\frac{m+1}{m+\sum\limits_{j=1}^{r}a_{j}}$.

We next treat the case where $r_{T}\neq 1$.

$\begin{split}&\frac{m}{m+r}\cdot\frac{m-\sum\limits_{j=1}^{r}a_{j}+r_{T}-1}{m+\sum\limits_{j=1}^{r}a_{i}-r_{T}-1}+\sum\limits_{i=2}^{T-1}\frac{r_{i}}{m+r}\cdot\frac{m-\sum\limits_{j=1}^{r}a_{j}+r_{T}+i}{m\sum\limits_{j=1}^{r}a_{j}-r_{T}-i}\stackrel{{\scriptstyle(1)}}{{\geq}}\\\
&\frac{m-\sum\limits_{j=1}^{r}a_{j}}{m+\sum\limits_{j=1}^{r}a_{j}-r_{T}}+\frac{(\sum\limits_{j=1}^{r}a_{j}+r-r_{T})r_{T}}{(m+r)(m+\sum\limits_{j=1}^{r}a_{j}-r_{T})}-\frac{2mr_{T}T}{(m+r)(m+\sum\limits_{j=1}^{r}a_{j}-r_{T}-1)(m+\sum\limits_{j=1}^{r}a_{j}-r_{T})}\stackrel{{\scriptstyle(2)}}{{\geq}}\\\
&\frac{m-\sum\limits_{j=1}^{r}a_{j}}{m+\sum\limits_{j=1}^{r}a_{j}}\end{split}$
(7)

We develop (1) in Appendix B. We prove (2) by examining two cases, based on
the value of $r_{T}$.

  1. 1.

If $r_{T}=0$, it is immediate by assignment.

  2. 2.

If $r_{T}\geq 2$, we have

$\begin{split}&\overbrace{\sum\limits_{j=1}^{r}a_{j}+r-r_{T}}^{Exp1}\geq
r_{T}\cdot
T+r-r_{T}\geq\overbrace{2T}^{Exp2},\qquad\overbrace{m+\sum\limits_{j=1}^{r}a_{j}-r_{T}-1}^{Exp3}\geq
m+r_{T}T-r_{T}-1\geq\overbrace{m}^{Exp4}\end{split}$

which allows us to replace $Exp1$ with $Exp2$, cancel $Exp3$ and $Exp4$ with
each other, and arrive at

$\begin{split}&\frac{m-\sum\limits_{j=1}^{r}a_{j}}{m+\sum\limits_{j=1}^{r}a_{j}-r_{T}}+\frac{\overbrace{(\sum\limits_{j=1}^{r}a_{j}+r-r_{T})}^{Exp1}r_{T}}{(m+r)(m+\sum\limits_{j=1}^{r}a_{j}-r_{T})}-\frac{2\overbrace{m}^{Exp4}r_{T}T}{(m+r)\underbrace{(m+\sum\limits_{j=1}^{r}a_{j}-r_{T}-1)}_{Exp3}(m+\sum\limits_{j=1}^{r}a_{j}-r_{T})}\geq\\\
&\frac{m-\sum\limits_{j=1}^{r}a_{j}}{m+\sum\limits_{j=1}^{r}a_{j}-r_{T}}+\frac{\overbrace{2T}^{Exp2}r_{T}}{(m+r)(m+\sum\limits_{j=1}^{r}a_{j}-r_{T})}-\frac{2r_{T}T}{(m+r)(m+\sum\limits_{j=1}^{r}a_{j}-r_{T})}=\\\
&\frac{m-\sum\limits_{j=1}^{r}a_{j}}{m+\sum\limits_{j=1}^{r}a_{j}-r_{T}}\geq\frac{m-\sum\limits_{j=1}^{r}a_{j}}{m+\sum\limits_{j=1}^{r}a_{j}}.\end{split}$

∎

##  B Expansion of the Steps to Derive (1) in Eq. 7

A note on notation - before each equality/inequality, we mark the expressions
that are to be manipulated in the subsequent step. We note that these
expressions are not related to the next ones after the equality/inequality
sign. For example, $Exp1$ and $Exp2$ are central to transformation $(1)$, but
they are unrelated to $Exp3$ and $Exp4$, which are marked because they are
central to transformation $(2)$. After giving the full chain of inequalities,
we explain each transformation.

$\displaystyle\frac{m}{m+r}\cdot\overbrace{\frac{m-\sum\limits_{j=1}^{r}a_{j}+r_{T}-1}{m+\sum\limits_{j=1}^{r}a_{j}-r_{T}-1}}^{Exp1}+\sum\limits_{i=2}^{T-1}\frac{r_{i}}{m+r}\cdot\overbrace{\frac{m-\sum\limits_{j=1}^{r}a_{j}+r_{T}+i}{m+\sum\limits_{j=1}^{r}a_{j}-r_{T}-i}}^{Exp2}\stackrel{{\scriptstyle(1)}}{{=}}$
$\displaystyle\frac{m}{m+r}\cdot\left(\frac{m-\sum\limits_{j=1}^{r}a_{j}+r_{T}}{m+\sum\limits_{j=1}^{r}a_{j}-r_{T}}+\frac{\overbrace{2r_{T}}^{Exp3}-2\sum\limits_{j=1}^{r}a_{j}}{(m+\sum\limits_{j=1}^{r}a_{j}-r_{T}-1)(m+\sum\limits_{j=1}^{r}a_{j}-r_{T})}\right)+$
$\displaystyle\frac{1}{m+r}\sum\limits_{i=2}^{T-1}r_{i}\left(\frac{m-\sum\limits_{j=1}^{r}a_{j}+r_{T}}{m+\sum\limits_{j=1}^{r}a_{j}-r_{T}}+\frac{2mi}{\underbrace{(m+\sum\limits_{j=1}^{r}a_{j}-r_{T}-i)}_{Exp4}(m+\sum\limits_{j=1}^{r}a_{j}-r_{T})}\right)\stackrel{{\scriptstyle(2)}}{{\geq}}$
$\displaystyle\frac{m}{m+r}\cdot\left(\overbrace{\frac{m-\sum\limits_{j=1}^{r}a_{j}+r_{T}}{m+\sum\limits_{j=1}^{r}a_{j}-r_{T}}}^{Exp5}-\frac{2\sum\limits_{j=1}^{r}a_{j}}{(m+\sum\limits_{j=1}^{r}a_{j}-r_{T}-1)(m+\sum\limits_{j=1}^{r}a_{j}-r_{T})}\right)+$
$\displaystyle\frac{1}{m+r}\sum\limits_{i=2}^{T-1}r_{i}\left(\overbrace{\frac{m-\sum\limits_{j=1}^{r}a_{j}+r_{T}}{m+\sum\limits_{j=1}^{r}a_{j}-r_{T}}}^{Exp5}+\frac{2mi}{(m+\sum\limits_{j=1}^{r}a_{j}-r_{T}-1)(m+\sum\limits_{j=1}^{r}a_{j}-r_{T})}\right)\stackrel{{\scriptstyle(3)}}{{=}}$
$\displaystyle\overbrace{\frac{m+\sum\limits_{i=2}^{T-1}r_{i}}{m+r}}^{Exp6}\cdot\frac{m\\!-\\!\sum\limits_{j=1}^{r}a_{j}\\!+\\!r_{T}}{m\\!+\\!\sum\limits_{j=1}^{r}a_{j}\\!-\\!r_{T}}+\frac{\overbrace{2m\sum\limits_{i=2}^{T-1}r_{i}\cdot
i-2m\sum\limits_{j=1}^{r}a_{j}}^{Exp7}}{(m\\!+\\!r)(m\\!+\\!\sum\limits_{j=1}^{r}a_{j}-r_{T}-1)(m+\sum\limits_{j=1}^{r}a_{j}-r_{T})}\stackrel{{\scriptstyle(4)}}{{=}}$
$\displaystyle\overbrace{\left(1\\!-\\!\frac{r_{T}}{m+r}\right)\cdot\frac{m\\!-\\!\sum\limits_{j=1}^{r}a_{j}\\!+\\!r_{T}}{m\\!+\\!\sum\limits_{j=1}^{r}a_{j}\\!-\\!r_{T}}}^{Exp8}-\frac{2mr_{T}T}{(m\\!+\\!r)(m\\!+\\!\sum\limits_{j=1}^{r}a_{j}-r_{T}-1)(m+\sum\limits_{j=1}^{r}a_{j}-r_{T})}\stackrel{{\scriptstyle(5)}}{{=}}$
$\displaystyle\frac{m-\sum\limits_{j=1}^{r}a_{j}}{m+\sum\limits_{j=1}^{r}a_{j}-r_{T}}+\frac{(\sum\limits_{j=1}^{r}a_{j}+r-r_{T})r_{T}}{(m+r)(m+\sum\limits_{j=1}^{r}a_{j}-r_{T})}-$
$\displaystyle\frac{2mr_{T}T}{(m+r)(m+\sum\limits_{j=1}^{r}a_{j}-r_{T}-1)(m+\sum\limits_{j=1}^{r}a_{j}-r_{T})}.$

Hence we arrive at the desired expression. We state in words the changes
introduced in each step:

  1. 1.

We transform $Exp1$ by performing

$\displaystyle\frac{m-\sum\limits_{j=1}^{r}a_{j}+r_{T}-1}{m+\sum\limits_{j=1}^{r}a_{j}-r_{T}-1}=\frac{m-\sum\limits_{j=1}^{r}a_{j}+r_{T}-1}{m+\sum\limits_{j=1}^{r}a_{j}-r_{T}-1}\cdot\frac{m+\sum\limits_{j=1}^{r}a_{j}-r_{T}-1+1}{m+\sum\limits_{j=1}^{r}a_{j}-r_{T}}=$
$\displaystyle\frac{m-\sum\limits_{j=1}^{r}a_{j}+r_{T}-1}{m+\sum\limits_{j=1}^{r}a_{j}-r_{T}-1}\cdot\left(\frac{m+\sum\limits_{j=1}^{r}a_{j}-r_{T}-1}{m+\sum\limits_{j=1}^{r}a_{j}-r_{T}}+\frac{1}{m+\sum\limits_{j=1}^{r}a_{j}-r_{T}}\right)=$
$\displaystyle\frac{m-\sum\limits_{j=1}^{r}a_{j}+r_{T}-1}{m+\sum\limits_{j=1}^{r}a_{j}-r_{T}}+\frac{m-\sum\limits_{j=1}^{r}a_{j}+r_{T}-1}{(m+\sum\limits_{j=1}^{r}a_{j}-r_{T}-1)(m+\sum\limits_{j=1}^{r}a_{j}-r_{T})}=$
$\displaystyle\frac{m-\sum\limits_{j=1}^{r}a_{j}+r_{T}}{m+\sum\limits_{j=1}^{r}a_{j}-r_{T}}+\frac{(m-\sum\limits_{j=1}^{r}a_{j}+r_{T}-1)-(m+\sum\limits_{j=1}^{r}a_{j}-r_{T}-1)}{(m+\sum\limits_{j=1}^{r}a_{j}-r_{T}-1)(m+\sum\limits_{j=1}^{r}a_{j}-r_{T})}=$
$\displaystyle\frac{m-\sum\limits_{j=1}^{r}a_{j}+r_{T}}{m+\sum\limits_{j=1}^{r}a_{j}-r_{T}}+\frac{2r_{T}-2\sum\limits_{j=1}^{r}a_{j}}{(m+\sum\limits_{j=1}^{r}a_{j}-r_{T}-1)(m+\sum\limits_{j=1}^{r}a_{j}-r_{T})}$

A similar transformation is applied to $Exp2$.

  2. 2.

We omit $Exp3$. We substitute $Exp4$, which is
$(m+\sum\limits_{j=1}^{r}a_{j}-r_{T}-i)$, with
$(m+\sum\limits_{j=1}^{r}a_{j}-r_{T}-1)$.

  3. 3.

We gather the terms multiplying $Exp5$ (which is
$\frac{m-\sum\limits_{j=1}^{r}a_{j}+r_{T}}{m+\sum\limits_{j=1}^{r}a_{j}-r_{T}}$)
as the first summand, and all other terms as the second summand.

  4. 4.

Since $r=\sum\limits_{j=2}^{T}r_{j}$, we can rewrite $Exp6$ as
$\displaystyle\frac{m+\sum\limits_{i=2}^{T-1}r_{i}}{m+r}=\frac{m+r-r_{T}}{m+r}=1-\frac{r_{T}}{m+r}$.

Since $\sum\limits_{j=1}^{r}a_{j}=\sum\limits_{i=2}^{T}r_{i}\cdot i$, we can
rewrite $Exp7$

$2m\sum\limits_{i=2}^{T-1}r_{i}\cdot
i-2m\sum\limits_{j=1}^{r}a_{j}=2m\sum\limits_{i=2}^{T-1}r_{i}\cdot
i-2m\sum\limits_{j=2}^{T}r_{j}\cdot j=-2mr_{T}\cdot T.$

  5. 5.

We rewrite $Exp8$

$\begin{split}&\left(1-\frac{r_{T}}{m+r}\right)\cdot\frac{m-\sum\limits_{j=1}^{r}a_{j}+r_{T}}{m+\sum\limits_{j=1}^{r}a_{j}-r_{T}}=\\\
&\frac{m-\sum\limits_{j=1}^{r}a_{j}}{m+\sum\limits_{j=1}^{r}a_{j}-r_{T}}\left(1-\frac{r_{T}}{m+r}\right)+\frac{r_{T}}{m+\sum\limits_{j=1}^{r}a_{j}-r_{T}}\cdot\frac{m+r-r_{T}}{m+r}=\\\
&\frac{m-\sum\limits_{j=1}^{r}a_{j}}{m+\sum\limits_{j=1}^{r}a_{j}-r_{T}}-\frac{r_{T}}{m+r}\cdot\frac{m-\sum\limits_{j=1}^{r}a_{j}}{m+\sum\limits_{j=1}^{r}a_{j}-r_{T}}+\frac{r_{T}}{m+\sum\limits_{j=1}^{r}a_{j}-r_{T}}\cdot\frac{m+r-r_{T}}{m+r}=\\\
&\frac{m-\sum\limits_{j=1}^{r}a_{j}}{m+\sum\limits_{j=1}^{r}a_{j}-r_{T}}+\frac{r_{T}(\sum\limits_{j=1}^{r}a_{j}+r-r_{T})}{(m+r)(m+\sum\limits_{j=1}^{r}a_{j}-r_{T})}.\end{split}$

##  C Proof of Theorem 4.1

###### Proof.

Choose $k=(2n_{k})^{2}$ for some natural number $n_{k}$, so $k=4,16,36,...$.
This choice maintains the property that the weighted voting game parameters
and all binomial coefficients’ arguments throughout the proof are natural
numbers. Consider $\displaystyle A=\\{2k\\},m=k^{1.5},T=\frac{2k+k^{1.5}}{2}$.
Then $P(A,m,T)=\frac{2k}{2k+k^{1.5}}\in o(1)$ and

$v(S\cup\\{a_{1}\\})-v(S)=\begin{cases}1&\frac{k^{1.5}}{2}-k\leq|S|<\frac{k^{1.5}}{2}+k\\\
0&otherwise.\end{cases}$

The absolute Banzhaf index gives an equal probability to each subset in
$P((A\setminus\\{a_{1}\\})\cup M)=P(M)$. There are $2^{k^{1.5}}$ subsets, and
by the above, each one of those adds one to the index iff it has $i$ small
players as specified above. Thus,

$\begin{split}&\beta^{\prime}_{a_{1}}(A,m,T)={\sum}\limits_{\begin{subarray}{c}S\in
P(M)\\\
\frac{k^{1.5}}{2}-k\leq|S|<\frac{k^{1.5}}{2}+k\end{subarray}}\frac{1}{2^{k^{1.5}}}=\frac{1}{2^{k^{1.5}}}{\sum\limits_{i=\frac{k^{1.5}}{2}-k}^{\frac{k^{1.5}}{2}+k-1}}\binom{k^{1.5}}{i}\geq\\\
&Pr_{X\sim B(k^{1.5},\frac{1}{2})}\left[|X-\frac{k^{1.5}}{2}|<k\right]=\\\
&1-Pr_{X\sim
B(k^{1.5},\frac{1}{2})}\left[|\frac{X}{k^{1.5}}-\frac{1}{2}|\geq\frac{1}{\sqrt{k}}\right],\end{split}$
(8)

where $B(n,p)$ is the binomial distribution with $n$ players and success
probability $p$.

We cite a Chernoff-type inequality (By Theorem 1 of ?), for $\displaystyle
X\sim B(n,p),c>0$:

$Pr_{X\sim B(n,p)}\left[|\frac{X}{n}-p|\geq c\right]<2e^{-2nc^{2}}$ (9)

If we choose $n=k^{1.5},p=\frac{1}{2},c=\frac{1}{\sqrt{k}}$, we get

$Pr_{X\sim
B(k^{1.5},\frac{1}{2})}\left[|\frac{X}{k^{1.5}}-\frac{1}{2}|\geq\frac{1}{\sqrt{k}}\right]<2e^{-2\sqrt{k}}\leq
0.05$ (10)

So Eq. 8 and Eq. 10 yield

$\beta^{\prime}_{a_{1}}(A,m,T)\geq 0.95.$ (11)

This concludes the argument for the absolute Banzhaf index. For the normalized
Banzhaf index, we first need to bound the small player’s absolute Banzhaf
index. Notice that for a fixed small player to be pivotal, the sum of subset
$S$ elements needs to be exactly $T-1=\frac{k^{1.5}}{2}+k-1$. This means that
either $a_{1}\in S$ and there are $\frac{k^{1.5}}{2}-k-1$ small players (other
than our one fixed small player) in the subset, or $a_{1}\not\in S$ and there
are $\frac{k^{1.5}}{2}+k-1$ other small players in the subset. Thus,

$\begin{split}&\beta^{\prime}_{1}(A,m,T)=Pr[a_{1}\in
S]\frac{1}{2^{m-1}}\binom{m-1}{\frac{k^{1.5}}{2}-k-1}+\\\ &Pr[a_{1}\not\in
S]\frac{1}{2^{m-1}}\binom{m-1}{\frac{k^{1.5}}{2}+k-1}=\\\
&\frac{1}{2^{k^{1.5}}}\left[\binom{k^{1.5}-1}{\frac{k^{1.5}}{2}+k-1}+\binom{k^{1.5}-1}{\frac{k^{1.5}}{2}-k-1}\right]=\\\
&\frac{1}{2^{k^{1.5}}}\left[\binom{k^{1.5}-1}{\frac{k^{1.5}}{2}+k-1}+\binom{k^{1.5}-1}{\frac{k^{1.5}}{2}+k}\right]\stackrel{{\scriptstyle(1)}}{{=}}\\\
&\frac{1}{2^{k^{1.5}}}\binom{k^{1.5}}{\frac{k^{1.5}}{2}+k}\leq Pr_{X\sim
B(k^{1.5},\frac{1}{2})}\left[|X-\frac{k^{1.5}}{2}|\geq k\right]=\\\ &Pr_{X\sim
B(k^{1.5},\frac{1}{2})}\left[|\frac{X}{k^{1.5}}-\frac{1}{2}|\geq\frac{1}{\sqrt{k}}\right]\stackrel{{\scriptstyle
Eq.\ref{OurChernoff}}}{{<}}2e^{-2\sqrt{k}},\end{split}$ (12)

where $(1)$ is by Pascal identity. So for the normalized Banzhaf index, we can
write

$\displaystyle\beta_{a_{1}}(A,m,T)=\frac{\beta^{\prime}_{a_{1}}}{k^{1.5}\beta^{\prime}_{1}(A,m,T)+\beta^{\prime}_{a_{1}}}\stackrel{{\scriptstyle
Eq.~{}\ref{eqBanzhafIndividualUpperBound}+\ref{bigPlayerAbsBanzhafLowerBound}+\ref{smallPlayerAbsBanzhafBound}}}{{\geq}}\frac{0.95}{2k^{1.5}e^{-2\sqrt{k}}+1}\geq
0.7$ ∎

##  D Proof of Theorem 5.1 for the High Threshold Regime

######  Lemma D.1.

If for some $A,m,T$,
$\displaystyle\frac{\displaystyle\sum\limits_{i=1}^{r}\rho_{a_{i}}(A,m,T)}{P(A,m,T)}>3$,
then $T<\frac{m}{2}$ and $\displaystyle\sum\limits_{j=1}^{r}a_{j}<m$.

###### Proof.

By the lemma’s premise, for some $A,m,T$ values,

$\frac{\displaystyle\sum\limits_{i=1}^{r}\rho_{a_{i}}(A,m,T)}{P(A,m,T)}>3.$
(13)

First, note that we must have $\sum\limits_{j=1}^{r}a_{j}<\frac{m}{2}.$
Otherwise,

$3P(A,m,T)\\!=\\!3\frac{\sum\limits_{j=1}^{r}a_{j}}{m\\!+\\!\sum\limits_{j=1}^{r}a_{j}}\\!\geq\\!{\frac{3\cdot\frac{m}{2}}{m\\!+\\!\frac{m}{2}}}\\!\stackrel{{\scriptstyle
eff.}}{{\geq}}\\!\sum\limits_{i=1}^{r}\rho_{a_{i}}(A,m,T),$

and dividing both sides by $P(A,m,T)$ contradicts Eq. 13.

Recall that $AP$ is the set of all-pivotal player subsets. Let $l=\min_{S\in
AP}\left|S\setminus A\right|$, the least amount of small player participants
in an all-pivotal subset $S$. We use the notation $x^{+}=\max(x,0)$. It can be
directly checked that it must hold that
$l=(T-\sum\limits_{j=1}^{r}a_{j})^{+}$. Now,

$\begin{split}&\sum\limits_{i=1}^{r}\rho_{a_{i}}(A,m,T)={{\sum\limits_{i=1}^{r}}}\mathbb{E}_{S\sim
UNI(AP)}\left[\frac{\mathbbm{1}_{a_{i}\in S}}{|S|}\right]=\\\
&\mathbb{E}_{S\sim
UNI(AP)}\left[\sum\limits_{i=1}^{r}\frac{\mathbbm{1}_{a_{i}\in
S}}{|S|}\right]\stackrel{{\scriptstyle(1)}}{{\leq}}\mathbb{E}_{S\sim
UNI(AP)}\left[\frac{|S\cap A|}{l+|S\cap A|}\right]\leq\\\ &\mathbb{E}_{S\sim
UNI(AP)}\left[\frac{r}{l+r}\right]\leq\frac{r}{l+r}=\frac{r}{(T-\displaystyle\sum\limits_{j=1}^{r}a_{j})^{+}+r},\\\
\end{split}$ (14)

where (1) is since for the numerator, we have
$\sum_{i=1}^{r}\mathbbm{1}_{{a_{i}}\in S}=|S\cap A|$. Also, for any all-
pivotal set $S$, $l\leq|S\setminus A|$ by its definition, and so for the
denominator we have $l+|S\cap A|\leq|S\setminus A|+|S\cap A|=|S|$. We thus
have

$\frac{r}{(T-\displaystyle\sum\limits_{j=1}^{r}a_{j})^{+}+r}\stackrel{{\scriptstyle
Eq.~{}\ref{lemmaPrior}+\ref{upperBoundDPEq}}}{{>}}3\frac{\displaystyle\sum\limits_{j=1}^{r}a_{j}}{m+\displaystyle\sum\limits_{j=1}^{r}a_{j}}.$
(15)

Finally, we consider two cases.

  1. 1.

If $\displaystyle T-\sum\limits_{j=1}^{r}a_{j}<0$, we have $\displaystyle
T<\sum\limits_{j=1}^{r}a_{j}<\frac{m}{2}$.

  2. 2.

If $\displaystyle T-\sum\limits_{j=1}^{r}a_{j}\geq 0$, we can make the
substitution $(T-\sum_{j=1}^{r}a_{j})^{+}=T-\sum_{j=1}^{r}a_{j}$. We can also
write $\sum_{j=1}^{r}a_{j}=\frac{m}{\theta}$ for some $\theta>2$. We can then
rearrange Eq. 15 and have

$\begin{split}&T<\frac{r(m+\sum\limits_{j=1}^{r}a_{j})}{3\sum\limits_{j=1}^{r}a_{j}}+\sum\limits_{j=1}^{r}a_{j}-r\leq\frac{r(\theta-2)}{3}+\frac{m}{\theta}\stackrel{{\scriptstyle(1)}}{{\leq}}\\\
&\frac{m(\theta-2)}{6\theta}+\frac{m}{\theta}<\frac{m}{2}\end{split}$

where (1) is since $\displaystyle
r\leq\frac{\sum_{j=1}^{r}a_{j}}{2}=\frac{m}{2\theta}$ (the big players are of
size at least 2).

∎

##  E Proof of Theorem 5.1 for the Low Threshold Regime

######  Lemma E.1.

For any $A,m,T$ with $T<\frac{m}{2}$ and $\sum\limits_{j=1}^{r}a_{j}<m$,

$\displaystyle\frac{\sum\limits_{i=1}^{r}\rho_{a_{i}}(A,m,T)}{P(A,m,T)}\leq
2.$

###### Proof.

Let $a=\max A$ and $r_{2},...,r_{a}$ the number of players with weights
$2,...,a$ respectively. For some all-pivotal set $S\in AP$, let
$i_{j}(S)=|\\{i\\}_{a_{i}=j,a_{i}\in S}|$ be the number of elements of size
$j$ in $S$. Let $APT=\\{(i_{2}(S),...,i_{a}(S))\\}_{S\in AP}$ be the set of
all unique tuples $(i_{2}(S),...,i_{a}(S))$ such that there is some $S\in AP$
with these size-counts values. Recall the notation $\displaystyle
x^{+}=\max(x,0)$. For any tuple $I=(i_{2},...,i_{a})\in APT$, there are
$(\prod\limits_{j=2}^{a}\binom{r_{j}}{i_{j}})\binom{m}{(T-\sum\limits_{j=2}^{a}j\cdot
i_{j})^{+}}$ all-pivotal sets $S$ in $AP$ such that
$(i_{2}(S),...,i_{a}(S))=I$. This yields overall

$|AP|=\sum\limits_{I\in
APT}\big{(}\prod\limits_{j=2}^{a}\binom{r_{j}}{i_{j}}\big{)}\binom{m}{(T-\sum\limits_{j=2}^{a}j\cdot
i_{j})^{+}}.$

Also for any $S\in AP$ and its corresponding $I\in APT$, it holds that

$|S\cap A|=\sum\limits_{j=2}^{a}i_{j},|S|=(T-\sum\limits_{j=2}^{a}j\cdot
i_{j})^{+}+\sum\limits_{j=2}^{a}i_{j}.$

We can write the sum

$\begin{split}&\sum\limits_{i=1}^{r}\rho_{a_{i}}(A,m,T)=\sum\limits_{i=1}^{r}\mathbb{E}_{S\sim
UNI(AP)}\left[\frac{\mathbbm{1}_{a_{i}\in
S}}{|S|}\right]=\frac{1}{|AP|}\sum\limits_{S\in AP}\frac{|S\cap A|}{|S|}=\\\
&\frac{\sum\limits_{I\in
APT}\big{(}\prod\limits_{j=2}^{a}\binom{r_{j}}{i_{j}}\big{)}\binom{m}{(T-\sum\limits_{j=2}^{a}j\cdot
i_{j})^{+}}\frac{\sum\limits_{j=2}^{a}i_{j}}{(T-\sum\limits_{j=2}^{a}j\cdot
i_{j})^{+}+\sum\limits_{j=2}^{a}i_{j}}}{\sum\limits_{I\in
APT}\big{(}\prod\limits_{j=2}^{a}\binom{r_{j}}{i_{j}}\big{)}\binom{m}{(T-\sum\limits_{j=2}^{a}j\cdot
i_{j})^{+}}}.\end{split}$ (16)

Claim F.1 of the appendix shows that if $T<\frac{m}{2}$, then

$\begin{split}&\sum\limits_{I\in
APT}\big{(}\prod\limits_{j=2}^{a}\binom{r_{j}}{i_{j}}\big{)}\binom{m}{(T-\sum\limits_{j=2}^{a}j\cdot
i_{j})^{+}}\frac{\sum\limits_{j=2}^{a}i_{j}}{(T-\sum\limits_{j=2}^{a}j\cdot
i_{j})^{+}+\sum\limits_{j=2}^{a}i_{j}}\leq\\\
&\frac{r}{m+1}\sum\limits_{\begin{subarray}{c}I\in APT\\\
\sum\limits_{j=2}^{a}j\cdot
i_{j}<T\end{subarray}}\big{(}\prod\limits_{j=2}^{a}\binom{r_{j}}{i_{j}}\big{)}\binom{m+1}{(T-\sum\limits_{j=2}^{a}j\cdot
i_{j}-2)^{+}+1}.\end{split}$

Then, Claim F.2 of the appendix states that for any $I\in APT$ with
$\sum\limits_{j=2}^{a}j\cdot i_{j}<T<\frac{m}{2}$, it holds that
$\displaystyle\binom{m+1}{(T-\sum\limits_{j=2}^{a}j\cdot i_{j}-2)^{+}+1}\leq
2\binom{m}{(T-\sum\limits_{j=2}^{a}j\cdot i_{j})^{+}}$. By the two claims and
Eq. 16, we have

$\begin{split}&\sum\limits_{i=1}^{r}\rho_{a_{i}}(A,m,T)\stackrel{{\scriptstyle(Eq.~{}\ref{DP_Ineq1})}}{{=}}\frac{\sum\limits_{I\in
APT}\big{(}\prod\limits_{j=2}^{a}\binom{r_{j}}{i_{j}}\big{)}\binom{m}{(T-\sum\limits_{j=2}^{a}j\cdot
i_{j})^{+}}\frac{\sum\limits_{j=2}^{a}i_{j}}{(T-\sum\limits_{j=2}^{a}j\cdot
i_{j})^{+}+\sum\limits_{j=2}^{a}i_{j}}}{\sum\limits_{I\in
APT}\big{(}\prod\limits_{j=2}^{a}\binom{r_{j}}{i_{j}}\big{)}\binom{m}{(T-\sum\limits_{j=2}^{a}j\cdot
i_{j})^{+}}}\stackrel{{\scriptstyle(\ref{nominatorInequalities})}}{{\leq}}\\\
&\frac{r}{m+1}\cdot\frac{1}{\sum\limits_{I\in
APT}\big{(}\prod\limits_{j=2}^{a}\binom{r_{j}}{i_{j}}\big{)}\binom{m}{(T-\sum\limits_{j=2}^{a}j\cdot
i_{j})^{+}}}\sum\limits_{\begin{subarray}{c}I\in APT\\\
\sum\limits_{j=2}^{a}j\cdot
i_{j}<T\end{subarray}}\big{(}\prod\limits_{j=2}^{a}\binom{r_{j}}{i_{j}}\big{)}\binom{m+1}{(T-\sum\limits_{j=2}^{a}j\cdot
i_{j}-2)^{+}+1}\stackrel{{\scriptstyle(\ref{nomDenomRatio})}}{{\leq}}\\\
&2\frac{r}{m+1}\cdot\frac{1}{\sum\limits_{I\in
APT}\big{(}\prod\limits_{j=2}^{a}\binom{r_{j}}{i_{j}}\big{)}\binom{m}{(T-\sum\limits_{j=2}^{a}j\cdot
i_{j})^{+}}}\sum\limits_{\begin{subarray}{c}I\in APT\\\
\sum\limits_{j=2}^{a}j\cdot
i_{j}<T\end{subarray}}\big{(}\prod\limits_{j=2}^{a}\binom{r_{j}}{i_{j}}\big{)}\binom{m}{(T-\sum\limits_{j=2}^{a}j\cdot
i_{j})^{+}}\leq 2\frac{r}{m+1}\end{split}$

We can then follow up with

$\begin{split}&\sum\limits_{i=1}^{r}\rho_{a_{i}}(A,m,T)\leq
2\frac{r}{m+1}=\frac{m+\sum\limits_{j=1}^{r}a_{j}}{m+1}\cdot\frac{2r}{m+\sum\limits_{j=1}^{r}a_{j}}\leq
2\cdot\frac{\sum\limits_{j=1}^{r}a_{j}}{m+\sum\limits_{j=1}^{r}a_{j}}=2P(A,m,T),\end{split}$

with the inequality going from the first to second line due to
$\displaystyle\sum\limits_{j=1}^{r}a_{j}<m$ (from the lemma assumptions) and
$\displaystyle r\leq\frac{\sum\limits_{j=1}^{r}a_{j}}{2}$ (big players are at
least of size 2). ∎

##  F Technical Claims for the Deegan-Packel Upper Bound

######  Claim F.1.

If $T<\frac{m}{2}$, then

$\begin{split}&\sum\limits_{I\in
APT}\bigg{(}\prod\limits_{j=2}^{a}\binom{r_{j}}{i_{j}}\bigg{)}\binom{m}{(T-\sum\limits_{j=2}^{a}j\cdot
i_{j})^{+}}\frac{\sum\limits_{j=2}^{a}i_{j}}{(T-\sum\limits_{j=2}^{a}j\cdot
i_{j})^{+}+\sum\limits_{j=2}^{a}i_{j}}\leq\\\
&\frac{r}{m+1}\sum\limits_{\begin{subarray}{c}I\in APT\\\
\sum\limits_{j=2}^{a}j\cdot
i_{j}<T\end{subarray}}\bigg{(}\prod\limits_{j=2}^{a}\binom{r_{j}}{i_{j}}\bigg{)}\binom{m+1}{(T-\sum\limits_{j=2}^{a}j\cdot
i_{j}-2)^{+}+1}.\end{split}$

###### Proof.

We begin with the following inequalities:

$\begin{split}&\sum\limits_{I\in
APT}\bigg{(}\prod\limits_{j=2}^{a}\binom{r_{j}}{i_{j}}\bigg{)}\binom{m}{(T-\sum\limits_{j=2}^{a}j\cdot
i_{j})^{+}}\frac{\sum\limits_{j=2}^{a}i_{j}}{(T-\sum\limits_{j=2}^{a}j\cdot
i_{j})^{+}+\sum\limits_{j=2}^{a}i_{j}}\stackrel{{\scriptstyle(1)}}{{=}}\\\
&\sum\limits_{\begin{subarray}{c}I\in APT\\\ \sum\limits_{j=2}^{a}i_{j}\geq
1\end{subarray}}\bigg{(}\prod\limits_{j=2}^{a}\binom{r_{j}}{i_{j}}\bigg{)}\binom{m}{(T-\sum\limits_{j=2}^{a}j\cdot
i_{j})^{+}}\frac{\sum\limits_{j=2}^{a}i_{j}}{(T-\sum\limits_{j=2}^{a}j\cdot
i_{j})^{+}+\sum\limits_{j=2}^{a}i_{j}}\stackrel{{\scriptstyle(2)}}{{\leq}}\\\
&\sum\limits_{\begin{subarray}{c}I\in APT\\\ \sum\limits_{j=2}^{a}i_{j}\geq
1\end{subarray}}\bigg{(}\prod\limits_{j=2}^{a}\binom{r_{j}}{i_{j}}\bigg{)}\binom{m}{(T-\sum\limits_{j=2}^{a}j\cdot
i_{j})^{+}}\frac{\sum\limits_{j=2}^{a}i_{j}}{(T-\sum\limits_{j=2}^{a}j\cdot
i_{j})^{+}+1},\end{split}$ (17)

where the transitions hold due to that:

  1. 1.

Any all-pivotal size-counts tuple $I\in APT$ with
$\sum\limits_{j=2}^{a}i_{j}=0$ (and there is exactly one like that, which
corresponds to the case where the all-pivotal set is comprised only of small
players), will not contribute to the sum due to the
$\sum\limits_{j=2}^{a}i_{j}$ expression in the numerator of the summand.

  2. 2.

Since we only sum over $I\in APT$ with $\sum_{j=2}^{a}i_{j}\geq 1$, this
condition is true for all summands, and so we can replace this expression in
the inequality with 1 and draw the inequality.

Now notice that for each element $I$, we can rewrite

$\begin{split}&\bigg{(}\prod\limits_{j=2}^{a}\binom{r_{j}}{i_{j}}\bigg{)}\binom{m}{(T-\sum\limits_{j=2}^{a}j\cdot
i_{j})^{+}}\frac{\sum\limits_{j=2}^{a}i_{j}}{(T-\sum\limits_{j=2}^{a}j\cdot
i_{j})^{+}+1}\stackrel{{\scriptstyle(1)}}{{=}}\\\ &\sum\limits_{2\leq k\leq
a}\bigg{(}\prod\limits_{j=2}^{a}\binom{r_{j}}{i_{j}}\bigg{)}\binom{m}{(T-\sum\limits_{j=2}^{a}j\cdot
i_{j})^{+}}\frac{i_{k}}{(T-\sum\limits_{j=2}^{a}j\cdot
i_{j})^{+}+1}\stackrel{{\scriptstyle(2)}}{{=}}\\\
&\sum\limits_{\begin{subarray}{c}2\leq k\leq a\\\ i_{k}\neq
0\end{subarray}}\binom{r_{k}}{i_{k}}i_{k}\bigg{(}\prod\limits_{2\leq j\neq
k\leq a}\binom{r_{j}}{i_{j}}\bigg{)}\binom{m}{(T-\sum\limits_{2\leq j\neq
k\leq a}j\cdot i_{j}-k\cdot i_{k})^{+}}\frac{1}{(T-\sum\limits_{2\leq j\neq
k\leq a}j\cdot i_{j}-ki_{k})^{+}+1}\stackrel{{\scriptstyle(3)}}{{=}}\\\
&\sum\limits_{\begin{subarray}{c}2\leq k\leq a\\\ i_{k}\neq
0\end{subarray}}\binom{r_{k}-1}{i_{k}-1}r_{k}\bigg{(}\prod\limits_{2\leq j\neq
k\leq a}\binom{r_{j}}{i_{j}}\bigg{)}\binom{m+1}{(T-\sum\limits_{2\leq j\neq
k\leq a}j\cdot i_{j}-k\cdot i_{k})^{+}+1}\frac{1}{m+1},\end{split}$ (18)

with transitions due to:

  1. 1.

Moving summation outside.

  2. 2.

All summands with $i_{k}=0$ don’t contribute to the sum, so we can limit the
summation to $k$ values with $i_{k}\neq 0$. We can also isolate the $k$ terms
in all the products and sub-sums of the summands.

  3. 3.

In general for $a\geq b\geq 1$, it holds that $\binom{a-1}{b-1}\cdot
a=\binom{a}{b}b$, by just moving terms in and out the binomial coefficient. We
use this identity twice.

Now we may continue with

$\displaystyle\sum\limits_{\begin{subarray}{c}I\in APT\\\
\sum\limits_{j=2}^{a}i_{j}\geq
1\end{subarray}}\bigg{(}\prod\limits_{j=2}^{a}\binom{r_{j}}{i_{j}}\bigg{)}\binom{m}{(T-\sum\limits_{j=2}^{a}j\cdot
i_{j})^{+}}\frac{\sum\limits_{j=2}^{a}i_{j}}{(T-\sum\limits_{j=2}^{a}j\cdot
i_{j})^{+}+1}\stackrel{{\scriptstyle(Eq.~{}\ref{elementWiseEquations})}}{{=}}$
$\displaystyle\sum\limits_{\begin{subarray}{c}I\in APT\\\
\sum\limits_{j=2}^{a}i_{j}\geq
1\end{subarray}}\sum\limits_{\begin{subarray}{c}2\leq k\leq a\\\ i_{k}\neq
0\end{subarray}}\binom{r_{k}-1}{i_{k}-1}r_{k}\bigg{(}\prod\limits_{2\leq j\neq
k\leq a}\binom{r_{j}}{i_{j}}\bigg{)}\binom{m+1}{(T-\sum\limits_{2\leq j\neq
k\leq a}j\cdot i_{j}-k\cdot
i_{k})^{+}+1}\frac{1}{m+1}\stackrel{{\scriptstyle(1)}}{{=}}$
$\displaystyle\sum\limits_{k=2}^{a}\sum\limits_{l_{k}=1}^{r_{k}}\sum\limits_{\begin{subarray}{c}I\in
APT\\\
i_{k}=l_{k}\end{subarray}}\binom{r_{k}-1}{i_{k}-1}r_{k}\bigg{(}\prod\limits_{2\leq
j\neq k\leq a}\binom{r_{j}}{i_{j}}\bigg{)}\binom{m+1}{(T-\sum\limits_{2\leq
j\neq k\leq a}j\cdot i_{j}-k\cdot
i_{k})^{+}+1}\frac{1}{m+1}\stackrel{{\scriptstyle(2)}}{{=}}$
$\displaystyle\frac{1}{m+1}\sum\limits_{k=2}^{a}r_{k}\sum\limits_{l_{k}=0}^{r_{k}-1}\sum\limits_{\begin{subarray}{c}I\in
APT\\\
i_{k}=l_{k}+1\end{subarray}}\binom{r_{k}-1}{l_{k}}\bigg{(}\prod\limits_{2\leq
j\neq k\leq a}\binom{r_{j}}{i_{j}}\bigg{)}\binom{m+1}{(T-\sum\limits_{2\leq
j\neq k\leq a}j\cdot i_{j}-k\cdot
l_{k}-k)^{+}+1}\stackrel{{\scriptstyle(3)}}{{\leq}}$
$\displaystyle\frac{1}{m+1}\sum\limits_{k=2}^{a}r_{k}\sum\limits_{l_{k}=0}^{r_{k}-1}\sum\limits_{\begin{subarray}{c}I\in
APT\\\
i_{k}=l_{k}+1\end{subarray}}\binom{r_{k}}{l_{k}}\bigg{(}\prod\limits_{2\leq
j\neq k\leq a}\binom{r_{j}}{i_{j}}\bigg{)}\binom{m+1}{(T-\sum\limits_{2\leq
j\neq k\leq a}j\cdot i_{j}-k\cdot
l_{k}-k)^{+}+1}\stackrel{{\scriptstyle(4)}}{{\leq}}$
$\displaystyle\frac{1}{m+1}\sum\limits_{k=2}^{a}r_{k}\sum\limits_{l_{k}=0}^{r_{k}-1}\sum\limits_{\begin{subarray}{c}I\in
APT\\\
i_{k}=l_{k}+1\end{subarray}}\binom{r_{k}}{l_{k}}\bigg{(}\prod\limits_{2\leq
j\neq k\leq a}\binom{r_{j}}{i_{j}}\bigg{)}\binom{m+1}{(T-\sum\limits_{2\leq
j\neq k\leq a}j\cdot i_{j}-k\cdot
l_{k}-2)^{+}+1}\stackrel{{\scriptstyle(5)}}{{=}}$
$\displaystyle\frac{1}{m+1}\sum\limits_{k=2}^{a}r_{k}\sum\limits_{\begin{subarray}{c}I\in
APT\\\ \sum\limits_{j=2}^{a}j\cdot
i_{j}<T\end{subarray}}\binom{r_{k}}{i_{k}}\bigg{(}\prod\limits_{2\leq j\neq
k\leq a}\binom{r_{j}}{i_{j}}\bigg{)}\binom{m+1}{(T-\sum\limits_{2\leq j\neq
k\leq a}j\cdot i_{j}-k\cdot i_{k}-2)^{+}+1}\stackrel{{\scriptstyle(6)}}{{=}}$
$\displaystyle\frac{1}{m+1}\sum\limits_{k=2}^{a}r_{k}\sum\limits_{\begin{subarray}{c}I\in
APT\\\ \sum\limits_{j=2}^{a}j\cdot
i_{j}<T\end{subarray}}\bigg{(}\prod\limits_{j=2}^{a}\binom{r_{j}}{i_{j}}\bigg{)}\binom{m+1}{(T-\sum\limits_{j=2}^{a}j\cdot
i_{j}-2)^{+}+1}\stackrel{{\scriptstyle(7)}}{{=}}$
$\displaystyle\frac{r}{m+1}\sum\limits_{\begin{subarray}{c}I\in APT\\\
\sum\limits_{j=2}^{a}j\cdot
i_{j}<T\end{subarray}}\bigg{(}\prod\limits_{j=2}^{a}\binom{r_{j}}{i_{j}}\bigg{)}\binom{m+1}{(T-\sum\limits_{j=2}^{a}j\cdot
i_{j}-2)^{+}+1}.$

with the transitions due to:

  1. 1.

First, notice the summands do not change. We switch the order of summation,
and separate the iteration over sets in $APT$, to first consider all possible
non-zero values of $i_{k}$, namely $l_{k}$ between 1 and $r_{k}$.

  2. 2.

We move the $\frac{1}{m+1}$ expression outside of all sums since it’s not
dependent on any sum parameter. We move the $r_{k}$ expression to the first
sum since it only depends on $k$. We move $l_{k}$ to run from 0 to $r_{k}-1$
instead of $1$ to $r_{k}$, and we make the substitution $i_{k}=l_{k}+1$ in the
summand.

  3. 3.

Binomial coefficients are monotone increasing in the first argument, and so
$\binom{r_{k}-1}{l_{k}}\leq\binom{r_{k}}{l_{k}}$ for each summand.

  4. 4.

For a binomial coefficient $\binom{a}{b}$ with $b<\frac{a}{2}$, it is monotone
increasing in the second argument. Since $T<\frac{m}{2}$, it holds in our
case, and since $k\geq 2$, the second argument indeed non-decreasing by the
substitution $k\rightarrow 2$.

  5. 5.

Whenever $0\leq l_{k}\leq r_{k}-1$ and $I\in APT$ has $i_{k}=l_{k}+1$, we have
$\displaystyle\sum\limits_{2\leq j\neq k\leq a}j\cdot i_{j}+k\cdot
i_{k}=\sum\limits_{2\leq j\neq k\leq a}j\cdot i_{j}+k\cdot l_{k}+k<T+k$,
otherwise some player of size $k$ would not be pivotal, and $I$ corresponds to
an all-pivotal set. This is equivalent to $\displaystyle\sum\limits_{2\leq
j\neq k\leq a}j\cdot i_{j}+k\cdot l_{k}<T$, so if we sum over all elements
$I\in APT$ that have $\displaystyle\sum\limits_{j=2}^{a}j\cdot i_{j}<T$
(Notice that for ease of notation we make the substitution $l_{k}=i_{k}$, we
make the same substitution in the summand - it is ok since $i_{k}=l_{k}+1$ is
not in our summation assumptions anymore).

  6. 6.

Isolating the $k$ element in the sub-sums and products is no longer required.

  7. 7.

By definition $\displaystyle r=\sum\limits_{k=2}^{a}r_{k}$.

∎

######  Claim F.2.

For any $I\in APT$ with $\sum\limits_{j=2}^{a}j\cdot i_{j}<T<\frac{m}{2}$, it
holds that $\binom{m+1}{(T-\sum\limits_{j=2}^{a}j\cdot i_{j}-2)^{+}+1}\leq
2\binom{m}{(T-\sum\limits_{j=2}^{a}j\cdot i_{j})^{+}}$.

###### Proof.

Let $I\in APT$ be some tuple of all-pivotal size-counts, with
$\sum\limits_{j=2}^{a}j\cdot i_{j}<T$.

We separate to two cases:

  1. 1.

If $\sum\limits_{j=2}^{a}j\cdot i_{j}=T-1$, then

$\binom{m+1}{(T-\sum\limits_{j=2}^{a}j\cdot
i_{j}-2)^{+}+1}=\binom{m+1}{1}=m+1\leq
2m=2\binom{m}{1}=2\binom{m}{(T-\sum\limits_{j=2}^{a}j\cdot i_{j})^{+}}.$

  2. 2.

If $\sum\limits_{j=2}^{a}j\cdot i_{j}<T-1$, then by our assumption
$T<\frac{m}{2}$ and so

$T-\sum\limits_{j=2}^{a}j\cdot i_{j}\leq m+1-(T-\sum\limits_{j=2}^{a}j\cdot
i_{j})$ (19)

which we can follow with

$\begin{split}&\frac{\displaystyle\binom{m+1}{T-\sum\limits_{j=2}^{a}j\cdot
i_{j}-1}}{\displaystyle\binom{m}{T-\sum\limits_{j=2}^{a}j\cdot
i_{j}}}=\frac{\displaystyle(m+1)(T-\sum\limits_{j=2}^{a}j\cdot
i_{j})}{\displaystyle(m-T+\sum\limits_{j=2}^{a}j\cdot
i_{j}+1)(m-T+\sum\limits_{j=2}^{a}j\cdot
i_{j}+2)}\stackrel{{\scriptstyle(Eq.~{}\ref{simpleInequalityForClaim})}}{{\leq}}\\\
&\frac{m+1}{m-T+\displaystyle\sum\limits_{j=2}^{a}j\cdot
i_{j}+2}\leq\frac{m+1}{\frac{m+1}{2}}=2.\end{split}$ (20)

Thus

$\begin{split}&\binom{m+1}{(T-\sum\limits_{j=2}^{a}j\cdot
i_{j}-2)^{+}+1}=\binom{m+1}{T-\sum\limits_{j=2}^{a}j\cdot
i_{j}-1}\stackrel{{\scriptstyle(Eq.~{}\ref{mainTechnicalTransitionForClaim})}}{{\leq}}2\binom{m}{T-\sum\limits_{j=2}^{a}j\cdot
i_{j}}=2\binom{m}{(T-\sum\limits_{j=2}^{a}j\cdot i_{j})^{+}}.\end{split}$

∎

##  G Second Recursion Lemma and Duality

######  Lemma G.1.

The following recursion holds for $\phi_{1}$

$\begin{split}&\phi_{1}(A,m,T)=\\\
&\begin{dcases}\frac{1}{m+r}&T=m+\sum\limits_{j=1}^{r}a_{j}\\\
\frac{1}{m+r}(\sum\limits_{\begin{subarray}{c}1\leq i\leq r\\\
m+\sum\limits_{1\leq j\neq i\leq r}a_{j}\geq
T\end{subarray}}\phi_{1}(A\\!\setminus\\!\\{a_{i}\\},m,T)+(m\\!-\\!1)\phi_{1}(A,m\\!-\\!1,T))&T<m+\sum\limits_{j=1}^{r}a_{j}\end{dcases}.\end{split}$

###### Proof.

Fix some small player, for which we measure the expected number of
permutations where it is pivotal. The recursion is done by conditional
expectation on the identity of the last player in the permutation. If
$T=m+\sum\limits_{j=1}^{r}a_{j}$, then if and only if our fixed player is
last, is it pivotal, which happens in probability $\frac{1}{m+r}$. For
$T<m+\sum\limits_{j=1}^{r}a_{j}$, if the last player in the permutation is
$a_{i}$ and $m+\sum\limits_{1\leq j\neq i\leq r}a_{j}<T$, then our fixed
player is not pivotal. If it is some big player $i$ with $m+\sum\limits_{1\leq
j\neq i\leq r}a_{j}\geq T$, then the problem reduces to the weighted voting
game with parameters $(A\setminus\\{a_{i}\\},m,T)$. Similarly if a small
player different than our fixed player is last (for which there are $m-1$
alternatives), the parameters are $(A,m-1,T)$. If our fixed player is last, it
will not be pivotal. All above events are with a uniform probability of
$\frac{1}{m+r}$. ∎

Remark.  The recursions in Lemma 3.1 and Lemma G.1 are dual and can be
obtained from one another using the following lemma:

######  Lemma G.2.

The following duality holds for $\Phi$

$\Phi_{1}(A,m,T)=\Phi_{1}(A,m,m+\sum\limits_{j=1}^{r}a_{j}-T+1).$

The proof of this lemma is simple and therefore omitted. Essentially, the
lemma follows since for every permutation, one may iterate over the set of
players to pass the threshold ’from the left’ or ’from the right’.

## References

  * Aziz, Bachrach, Elkind, and Paterson Aziz, H., Bachrach, Y., Elkind, E., and Paterson, M. (2011).  False-name manipulations in weighted voting games.  Journal of Artificial Intelligence Research, 40, 57–93.
  * Bachrach, Filmus, Oren, and Zick Bachrach, Y., Filmus, Y., Oren, J., and Zick, Y. (2016a).  Analyzing power in weighted voting games with super-increasing weights.  In Gairing, M., and Savani, R. (Eds.), Algorithmic Game Theory, pp. 169–181, Berlin, Heidelberg. Springer Berlin Heidelberg.
  * Bachrach, Filmus, Oren, and Zick Bachrach, Y., Filmus, Y., Oren, J., and Zick, Y. (2016b).  A characterization of voting power for discrete weight distributions.  In Proceedings of the 25th International Joint Conference on Artificial Intelligence, p. 74–80. AAAI Press.
  * Bachrach, Zadimoghaddam, and Key Bachrach, Y., Zadimoghaddam, M., and Key, P. (2011).  A cooperative approach to collusion in auctions.  SIGecom Exch., 10(1), 17–22.
  * Banzhaf III Banzhaf III, J. F. (1964).  Weighted voting doesn’t work: A mathematical analysis.  Rutgers L. Rev., 19, 317.
  * Chang, Chua, and Machover Chang, P.-L., Chua, V., and Machover, M. (2006).  L.S. Penrose’s limit theorem: Tests by simulation.  Mathematical Social Sciences, 51, 90–106.
  * Coleman Coleman, J. S. (1971).  Control of collectivities and the power of a collectivity to act.  In Liebermann, B. (Ed.), Social Choice, Monographs and texts in the behavioral sciences, pp. 269–300. Gordon and Breach.
  * Deegan and Packel Deegan, J., and Packel, E. (1978).  A new index of power for simple n-person games.  International Journal of Game Theory, 7, 113–123.
  * Dubey and Shapley Dubey, P., and Shapley, L. S. (1979).  Mathematical properties of the Banzhaf power index.  Mathematics of Operations Research, 4(2), 99–131.
  * Faliszewski and Hemaspaandra Faliszewski, P., and Hemaspaandra, L. (2009).  The complexity of power-index comparison.  Theoretical Computer Science, 410(1), 101 – 107.
  * Felsenthal and Machover Felsenthal, D. S., and Machover, M. (2005).  Voting power measurement: a story of misreinvention.  Social Choice and Welfare, 25(2), 485–506.
  * Holler and Packel Holler, M. J., and Packel, E. W. (1983).  Power, luck and the right index.  Zeitschrift für Nationalökonomie / Journal of Economics, 43(1), 21–29.
  * Jelnov and Tauman Jelnov, A., and Tauman, Y. (2014).  Voting power and proportional representation of voters.  International Journal of Game Theory, 43(4), 747–766.
  * Johnston Johnston, R. J. (1978).  On the measurement of power: Some reactions to laver.  Environment and Planning A, 10(8), 907–914.
  * Lasisi and Allan Lasisi, R. O., and Allan, V. H. (2017).  False-name manipulation in weighted voting games: Empirical and theoretical analysis.  Computational Intelligence, 33(3), 478–506.
  * Lindner and Machover Lindner, I., and Machover, M. (2004).  L.S. Penrose’s limit theorem: Proof of some special cases.  Mathematical Social Sciences, 47, 37–49.
  * Milnor and Shapley Milnor, J. W., and Shapley, L. S. (1978).  Values of large games ii: Oceanic games.  Mathematics of Operations Research, 3(4), 290–307.
  * Morgenstern and Von Neumann Morgenstern, O., and Von Neumann, J. (1953).  Theory of games and economic behavior.  Princeton university press.
  * Neyman Neyman, A. (1981).  Singular games have asymptotic values.  Mathematics of Operations Research, 6(2), 205–212.
  * Okamoto Okamoto, M. (1959).  Some inequalities relating to the partial sum of binomial probabilities.  Annals of the Institute of Statistical Mathematics, 10, 29–35.
  * Oren, Filmus, Zick, and Bachrach Oren, J., Filmus, Y., Zick, Y., and Bachrach, Y. (2014).  Power distribution in randomized weighted voting: the effects of the quota.  https://arxiv.org/abs/1408.0442.
  * Penrose Penrose, L. S. (1946).  The elementary statistics of majority voting.  Journal of the Royal Statistical Society, 109(1), 53–57.
  * Rey and Rothe Rey, A., and Rothe, J. (2014).  False-name manipulation in weighted voting games is hard for probabilistic polynomial time.  The Journal of Artificial Intelligence Research, 50(1), 573–601.
  * Riker Riker, W. H. (1986).  The first power index.  Social Choice and Welfare, 3, 293–295.
  * Shapley Shapley, L. S. (1952).  A value for n-person games.  Tech. rep., Rand Corp Santa Monica CA.
  * Shapley Shapley, L. S. (1962).  Simple games: an outline of the descriptive theory.  Behavioral Science, 7(1), 59–66.
  * Shapley and Shubik Shapley, L. S., and Shubik, M. (1954).  A method for evaluating the distribution of power in a committee system.  American political science review, 48(3), 787–792.
  * Storing Storing, H. J. (2008).  The complete anti-federalist, Vol. 2.  University of Chicago Press.
  * Słomczyński and Zyczkowski Słomczyński, W., and Zyczkowski, K. (2006).  Penrose voting system and optimal quota.  Acta Physica Polonica B, 37, 3133–3143.
  * Słomczyński and Życzkowski Słomczyński, W., and Życzkowski, K. (2007).  From a toy model to the double square root voting system.  Homo Oeconomicus, 24(3-4), 381–399.
  * Winter Winter, E. (2002).  Chapter 53 The Shapley value..  Vol. 3 of Handbook of Game Theory with Economic Applications, pp. 2025 – 2054. Elsevier.
  * Young Young, H. P. (1978).  Power, prices, and incomes in voting systems.  Mathematical Programming, 14(1), 129–148.
  * Zick Zick, Y. (2013).  On random quotas and proportional representation in weighted voting games.  In Proceedings of the 23rd International Joint Conference on Artificial Intelligence, pp. 432–439.
  * Zick, Skopalik, and Elkind Zick, Y., Skopalik, A., and Elkind, E. (2011).  The Shapley value as a function of the quota in weighted voting games.  In Proceedings of the 22nd International Joint Conference on Artificial Intelligence, pp. 490–496.