Analyzing Power in Weighted Voting Games with Super-Increasing Weights

Abstract

Weighted voting games (WVGs) are a class of cooperative games that capture settings of group decision making in various domains, such as parliaments or committees. Earlier work has revealed that the effective decision making power, or influence of agents in WVGs is not necessarily proportional to their weight. This gave rise to measures of influence for WVGs. However, recent work in the algorithmic game theory community have shown that computing agent voting power is computationally intractable. In an effort to characterize WVG instances for which polynomial-time computation of voting power is possible, several classes of WVGs have been proposed and analyzed in the literature. One of the most prominent of these are super increasing weight sequences. Recent papers show that when agent weights are super-increasing, it is possible to compute the agents’ voting power (as measured by the Shapley value) in polynomial-time. We provide the first set of explicit closed-form formulas for the Shapley value for super-increasing sequences. We bound the effects of changes to the quota, and relate the behavior of voting power to a novel function. This set of results constitutes a complete characterization of the Shapley value in weighted voting games, and answers a number of open questions presented in previous work.

1 Introduction

Weighted voting games (WVGs) are a class of cooperative games, commonly used to model large group decision making systems, such as parliaments. Alternatively, one can think of each player as controlling some resource, with winning coalitions being ones that have sufficient resources in order to complete a task. One of the main challenges in the WVG setting is the measurement of player influence, or power. It is a well known fact that one’s ability to affect decisions may not necessarily be proportional to one’s weight. As an intuitive example, consider a parliament with three parties, A, B and C: A and B both have 50 seats, while C has 20 (a government must control a majority of the house, i.e., have at least 60 votes). If one equates voting power with weight, then A and B are significantly more powerful than C; a government can be formed by any two coalitions, and no single party can form a government on its own. Based on this observation, it can be reasonably argued that all parties have equal electoral power. Formal measures of voting influence, such as the Shapley value, aim to capture exactly these effects, providing a formal measure of player influence in WVGs. The Shapley value is considered by many to be a particularly appealing method of measuring voting power, as it satisfies several desired properties. However, it is well-known that computing the Shapley value in WVGs is computationally intractable [1]. This has naturally led to works identifying classes of WVGs for which computing voting influence is computationally tractable. In particular, an interesting sufficient condition on weights has been identified, which, if satisfied, guarantees the polynomial-time computability of the Shapley value. More formally, polynomial-time computability of the Shapley value is guaranteed if player weights are known to be super-increasing: a sequence of weights $w_1,\dots ,w_n$ is said to be super-increasing if $w_i > \sum _{j = i+1}^n w_j$ for all $i \in \{1,\dots ,n-1\}$.

1.1 Our Contributions

We provide a complete characterization of the Shapley values in a game where weights form a super-increasing sequence (Sect. 3). We provide a closed-form formula for the Shapley value when weights are super-increasing (extending techniques and observations on such games discussed in earlier work [2–4]). This formula is derived by exploiting an interesting relation between general super-increasing sequences, and the WVG obtained when weights are exponents of 2. We show several implications of our analysis to the results by [2, 4], as well as a relation to a curious fractal function (Fig. 1). We significantly improve our understanding of this function, showing its various analytical properties, and its relation to Shapley values in WVGs with super-increasing weights. On a technical level, we employ several non-trivial combinatorial techniques, as well as surprising insights on the bit representation of fractions.

1.2 Related Work

Our work generalizes several results appearing in [2–4] with respect to WVGs with weights that are powers of 2. We use the Shapley value [5, 6] to measure voting power; this follows the extensive literature in mathematical economics and, more recently, the AI community (see [7, Chap. 4] and [8] for a literature review), on measuring influence in cooperative games. The computational complexity of computing the Shapley value is a well-studied problem, with several works on either establishing its intractability [1, 9, 10], approximating it [11–13], or computing it exactly for some class of cooperative game [14–20], using it to measure importance and assign gains or costs [21–26] or analyzing its behavior in the face of various types of uncertainty [27–31] (this list is by no means exhaustive, for a comprehensive review see [7, 8]).

2 Preliminaries

We generally refer to vectors as lowercase, boldface letters and sets as uppercase letters. Given a positive integer m we denote $[m] = \{1,\dots ,m\}$. A weighted voting game (WVG) is given by a set of agents $N = \{1,\dots ,n\}$, a non-negative weight vector $\mathrm {w} = (w_1,\dots ,w_n)$, where $w_i$ is the weight of player $i \in N$ (and we let $\mathrm {w}$ denote the length-n weight vector), and a quota (or threshold) q. Thus, we refer to a WVG over N as the tuple $\langle \mathrm {w};q\rangle$. Unless otherwise specified, we assume that $w_1\ge \dots \ge w_n$. For a subset of agents $S \subseteq N$ (also referred to as a coalition), we define $w(S) = \sum _{i \in S} w_i$.

A coalition $S \subseteq N$ is called winning (has a value $v(S) = 1$) if $w(S) \ge q$ and is called losing (has a value $v(S) = 0$) otherwise. To define the Shapley value, we require the following notation. Given a coalition $S \subseteq N$ and some $i \in N{\setminus } S$, we let the marginal contribution of i to S be $m_i(S) = v(S\cup \{i\}) - v(S)$; for WVGs, $m_i(S) \in \{0,1\}$, and $m_i(S) = 1$ iff $w(S) < q$ but $w(S) + w_i \ge q$. If $m_i(S) = 1$ we say that i is pivotal for S. Given a permutation $\sigma :N\rightarrow N$, we let $P_i(\sigma ) = \{j \in N \mid \sigma (i) > \sigma (j)\}$ be the set of i’s predecessors in $\sigma$. By letting $m_i(\sigma ) = m_i(P_i(\sigma ))$, we have that $m_i(\sigma ) = 1$ iff i is pivotal for its predecessors in $\sigma$, in which case we simply say that i is pivotal for $\sigma$. Let ${{\mathrm{Sym}}}_{n}$ be the set of all permutations of N. The Shapley value of player i is the probability that i is pivotal for a randomly selected permutation $\sigma \in {{\mathrm{Sym}}}_{n}$: $\varphi _i(\mathrm {w};q) = \frac{1}{n!}\sum _{\sigma \in {{\mathrm{Sym}}}_{n}}m_i(\sigma )$. For $i \in N$, we write $\varphi _i(q)$ whenever $\mathrm {w}$ is clear from the context, and assume that $q \in (0,w(N)]$ (as otherwise $\varphi _i(\mathrm {w}; q) = 0$).

3 A Formula for the Shapley Value Under Super-Increasing Sequences

Given a vector of weights $\mathrm {w} = (w_1,\dots ,w_n)$, we say that $\mathrm {w}$ is super-increasing (SI) if $w_i > \sum _{j=i+1}^n w_j$ for all $i \in \{1,\dots ,n-1\}$. We henceforth assume that $\mathrm {w}$ is a super-increasing sequence.¹

In Lemma 2, we show that computing the Shapley value for SI weight sequences is essentially equivalent to doing so for the sequence $\mathrm {\beta }= (2^{n-1},2^{n-2},\dots ,1)$ (for a subset $S \subseteq N$, recall that $\beta (S) = \sum _{i \in S} 2^{n-i}$). Given an integer value $q \in (0,2^n - 1=\beta (N)]$, we note that there exists a unique subset $S_q\subseteq N$ such that $\beta (S_q) = q$. Given an SI vector $\mathrm {w}$, not every number q in the range (0, w(N)] can be written as a sum of members of $\{w_1,\ldots ,w_n\}$; however, there are certain naturally defined intervals that partition (0, w(N)].

We begin by proving the following two simple lemmas (the proof of Lemma 1 is omitted due to space constraints).

Lemma 1

Let $\mathrm {w}$ be an SI weight vector. For every $S,T \subseteq N$, $\beta (S) < \beta (T)$ if and only if $w(S) < w(T)$.

For a non-empty set of agents $S \subseteq N$, we let $S^- \subseteq N$ be the unique subset of agents satisfying $\beta (S^-) = \beta (S) - 1$. For example, assuming $n = 4$, if $S = \{1,3,4\}$, then $\beta (S) = 2^{4-1} + 2^{4-3} + 2^{4-4} = 2^3 + 2^1 + 2^0 = 11$; thus $S^- = \{1,3\}$ since $\beta (\{1,3\}) = 2^{4-1} + 2^{4-3} = 2^3 + 2^1 = 10$. Lemma 1 shows that for every quota $q \in (0,w(N)]$ there exists a unique set $A(q)\subseteq N$ such that q is in $(w(A(q)^-),w(A(q))]$. Whenever we write $A(q) = \{a_0,\ldots ,a_r\}$, we will always assume that $a_0< \dots < a_r$.

Lemma 2

Given an SI vector $\mathrm {w}$, then for every $i \in N$ and $q \in (0,w(N)]$, $\varphi _i(\mathrm {w};q) = \varphi _i(\mathrm {\beta };\beta (A(q)))$.

Proof

Recall that $P_i(\sigma )$ is the set of agents appearing before agent i in a given permutation $\sigma \in {{\mathrm{Sym}}}_{n}$. The Shapley value $\varphi _i(\mathrm {w};q)$ is the probability that $w(P_i(\sigma )) \in [q-w_i,q)$, or equivalently, that $q \in (w(P_i(\sigma )),w(P_i(\sigma ))+w_i]$. The intervals $(w(C^-),w(C)]$ partition (0, w(N)]; thus q is in $(w(P_i(\sigma )),w(P_i(\sigma ))+w_i]$ if and only if $w(P_i(\sigma )) \le w(A(q)^-)$ and $w(A(q)) \le w(P_i(\sigma ) \cup \{i\})$. Lemma 1 shows that this is equivalent to checking whether $\beta (P_i(\sigma )) \le \beta (A(q)^-)$ and $\beta (A(q)) \le \beta (P_i(\sigma ) \cup \{i\})$. Now, note that $\beta (A(q)^-) = \beta (A(q))-1$, so the above condition simply states that i is pivotal for $\sigma$ under $\mathrm {\beta }$ when the quota is $\beta (A(q))$.

Lemma 2 implies that for any SI $\mathrm {w}$, computing $\varphi _i(\mathrm {w};q)$ only requires finding $A(q)$; this can be done using Algorithm 1. This is a straightforward greedy algorithm, whose proof of correctness is omitted due to space constraints.

We now present our main result, a closed form formula for the Shapley values in the super-increasing case. The resulting Shapley values are illustrated in Fig. 1.

Theorem 1

Given an SI vector $\mathrm {w}$ and a threshold q, let $A(q) = \{a_0,\ldots ,a_r\}$.

If $i \notin A(q)$ then:

$$\varphi _i(\mathrm {w};q) = \sum _{\begin{array}{c} t \in \{0,\ldots ,r\}:\\ a_t > i \end{array}} \frac{1}{a_t\left( {\begin{array}{c}a_t-1\\ t\end{array}}\right) }.$$

If $i \in A(q)$, say $i = a_s$, then:

$$\varphi _i(\mathrm {w};q) = \frac{1}{a_s\left( {\begin{array}{c}a_s-1\\ s\end{array}}\right) } - \sum _{t >s} \frac{1}{a_t\left( {\begin{array}{c}a_t-1\\ t-1\end{array}}\right) }.$$

Proof

We present here the case where $i \notin A(q)$; the case where $i \in A(q)$ is similar, and its proof is omitted due to space constraints. Lemma 2 shows that $\varphi _i(\mathrm {w};q) = \varphi _i(\mathrm {\beta };\beta (A(q)))$, where $\mathrm {\beta }= 2^{n-1},\ldots ,1$. Therefore we can assume w.l.o.g. that $\mathrm {w} = \mathrm {\beta }$ and that the threshold is $q^* = \sum _{j \in A(q)} 2^{n-j}$.

Recall that $\varphi _i(\mathrm {w};q)$ is the probability that $w(P_i(\sigma )) \in [q-w_i,q)$, where $\sigma$ is chosen randomly from ${{\mathrm{Sym}}}_{n}$, and $P_i(\sigma )$ is the set of predecessors of i in $\sigma$. The idea of the proof is to consider the maximal $\tau \in \{1,\ldots ,r+1\}$ such that $a_t \in P_i(\sigma )$ for all $t < \tau$. We will show that when $i \notin A(q)$, each possible value of $\tau$ corresponds to one summand in the expression for $\varphi _i(\mathrm {w};q)$.

Suppose that i is pivotal for $\sigma$. We start by showing that $\tau \le r$, ruling out the case $\tau = r+1$. If $\tau = r+1$ then by definition $\beta (P_i(\sigma )) \ge \sum _{j \in A(q)} 2^{n-j} = q^*$, contradicting the assumption $\beta (P_i(\sigma )) < q^*$. Thus $\tau \le r$, and so $a_\tau$ is well-defined. We claim that if $k \in P_i(\sigma )$ for some agent $k < a_\tau$ then $k \in A(q)$. Indeed, otherwise:

$$\begin{aligned} \beta (P_i(\sigma )) \ge&\sum _{t=0}^{\tau -1} 2^{n-a_t} + 2^{n-k} \ge \sum _{t=0}^{\tau -1} 2^{n-a_t} + 2^{n-a_\tau +1} \\ \ge&\sum _{t=0}^{\tau -1} 2^{n-a_t} + \sum _{j=a_\tau }^n 2^{n-j} \ge \beta (A(q))=q^*, \end{aligned}$$

again contradicting $\beta (P_i(\sigma )) < q^*$; thus, if $k \in P_i(\sigma ){\setminus } A(q)$, then $k> a_\tau$.

Furthermore, we claim that $a_\tau \ge i$. Otherwise:

$$\begin{aligned} \beta (P_i(\sigma )) \le&\sum _{t=0}^{\tau -1} 2^{n-a_t} + \sum _{j=a_\tau +1}^n 2^{n-j} - 2^{n-i}\\ <&\sum _{t=0}^{\tau } 2^{n-a_t} - 2^{n-i} \le q^* - w_i, \end{aligned}$$

contradicting the assumption $w(P_i(\sigma )) \ge q^* - w_i$.

Summarizing, we have that if i is pivotal for $\sigma$, then $\tau \le r$, $a_{\tau } \ge i$ and

$$\begin{aligned} P_i(\sigma ) \cap \{1,\ldots ,a_{\tau }\} = \{a_0,\ldots ,a_{\tau -1}\}. \end{aligned}$$

(1)

Denote this event $E_\tau$, and call a $\tau \le r$ satisfying $a_\tau \ge i$ legal.

Recall that $i \notin A(q)$; we have shown above that if i is pivotal for $\sigma$ then $E_\tau$ occurs for some legal $\tau$. We claim that the converse is also true; that is, if there exists some legal $\tau$ such that (1) holds with respect to $\sigma$, then i is pivotal for $\sigma$. Indeed, given $E_\tau$ defined with respect to a permutation $\sigma$, and for some legal $\tau$, the weight of $P_i(\sigma )$ can be bounded as follows.

$$ \sum _{t=0}^{\tau -1} 2^{n-a_t} \le \beta (P_i(\sigma )) \le \sum _{t=0}^{\tau -1} 2^{n-a_t} + \sum _{j=a_{\tau }+1}^n 2^{n-j} < \sum _{t=0}^{\tau } 2^{n-a_t}, $$

where the last expression is at most $q^*$. The second inequality follows from the definition of $\tau$. As $i < a_\tau$, the lower bound satisfies:

$$ \sum _{t=0}^{\tau -1} 2^{n-a_t} \ge q^* - \sum _{j=a_\tau }^n 2^{n-j} > q^* - 2^{n-a_\tau +1} \ge q^* - 2^{n-i}, $$

It remains to calculate $\Pr [E_\tau ]$. The event $E_\tau$ states that the restriction of $\sigma$ to $\{1,\ldots ,a_\tau \}$ consists of the elements $\{a_0,\ldots ,a_{\tau -1}\}$ in some order, followed by i (recall that $i \le a_\tau$). For each of the $\tau !$ possible orders, the probability of this is $1/a_\tau \cdots (a_\tau -\tau ) = (a_\tau -\tau -1)!/a_\tau !$, and so

$$\begin{aligned} \Pr [E_\tau ] = \frac{\tau !(a_\tau -\tau -1)!}{a_\tau !} = \frac{1}{a_\tau \left( {\begin{array}{c}a_\tau -1\\ \tau \end{array}}\right) }. \end{aligned}$$

(2)

Summing over all legal $\tau$, we obtain the formula in the statement of the theorem. This completes the proof in the case $i \notin A(q)$.

Example 1

Consider a 10 agent game where $w_i = 2^{n -i}$. Let us compute the Shapley value of agent 7 when the quota is $q = 27$. We can write $q = 16 + 8 + 2 +1 = w_6 + w_7 + w_9 + w_{10}$, hence $A(q) = \{a_0 = 6,a_1 = 7,a_2 = 9,a_3 = 10\}$. Since agent 7 is in $A(q)$, it must be the case that: $\varphi _7(27) = \frac{1}{7\left( {\begin{array}{c}6\\ 1\end{array}}\right) } - \frac{1}{9\left( {\begin{array}{c}8\\ 1\end{array}}\right) } - \frac{1}{10\left( {\begin{array}{c}9\\ 2\end{array}}\right) } \approx 0.007143.$

Fig. 1.

Examples Shapley values corresponding to super-increasing sequences.

4 Shapley Values Under Super-Increasing Weights

Zuckerman et al. [4] prove a nice property of super-increasing sets (Lemma 19):

Theorem 2

(given in[4]). Suppose that $n \ge 3$; if the weights $\mathrm {w}$ are SI, then for every quota $q \in (0,w(N)]$, either $\varphi _n(q) = \varphi _{n-1}(q)$ or $\varphi _{n-1}(q) = \varphi _{n-2}(q)$.

We generalize this result using Theorem 1, showing how to determine in which cases $\varphi _i(q) = \varphi _{i+1}(q)$. We prove Lemma 4 using a combinatorial identity.

Lemma 3

Let p, t be integers satisfying $p > t \ge 1$. Then

$$\begin{aligned} \frac{1}{p\left( {\begin{array}{c}p-1\\ t\end{array}}\right) } + \frac{1}{p\left( {\begin{array}{c}p-1\\ t-1\end{array}}\right) } = \frac{1}{(p-1)\left( {\begin{array}{c}p-2\\ t-1\end{array}}\right) }. \end{aligned}$$

Lemma 4

Given a quota $q \in (0,w(N)]$, let $A(q) = \{a_0,\ldots ,a_r\}$. Given some $i \in N{\setminus }\{n\}$, (a) if $i,i+1 \in A(q)$ or $i,i+1 \notin A(q)$ then $\varphi _i(q) = \varphi _{i+1}(q)$; (b) if $i \notin A(q)$ and $i+1\in A(q)$ then $\varphi _i(q) \ge \varphi _{i+1}(q)$, with equality if and only if $i+1 = a_r$; (c) if $i \in A(q)$ and $i+1\notin A(q)$ then $\varphi _i(q) > \varphi _{i+1}(q)$.

Proof

We write $A(q) = \{a_1,\dots ,a_r\}$. Let us assume that neither i nor $i+1$ are in $A(q)$; the other cases are similar and their proof is omitted due to space constraints. For every $t \in \{0,\dots ,r\}$, $a_t > i$ if and only $a_t > i+1$. Employing the formula used in Theorem 1, we have that

$$\begin{aligned} \varphi _i(q)&= \sum _{\begin{array}{c} t \in \{0,\ldots ,r\}:\\ a_t> i \end{array}} \frac{1}{a_t\left( {\begin{array}{c}a_t-1\\ t\end{array}}\right) } \\&= \sum _{\begin{array}{c} t \in \{0,\ldots ,r\}:\\ a_t > i+1 \end{array}} \frac{1}{a_t\left( {\begin{array}{c}a_t-1\\ t\end{array}}\right) } = \varphi _{i+1}(q). \end{aligned}$$

Next, if $i,i+1 \in A(q)$ then there is some s such that $i = a_s$ and $i+1 = a_{s+1}$, so:

$$\begin{aligned} \varphi _i(q) =&\frac{1}{a_s\left( {\begin{array}{c}a_s - 1\\ s\end{array}}\right) } - \sum _{\begin{array}{c} t \in \{0,\dots ,r\}:\\ a_t> i \end{array}}\frac{1}{a_t\left( {\begin{array}{c}a_t-1\\ t-1\end{array}}\right) } \\ =&\frac{1}{a_s\left( {\begin{array}{c}a_s - 1\\ s\end{array}}\right) } - \frac{1}{a_{s+1}\left( {\begin{array}{c}a_{s+1}-1\\ s\end{array}}\right) } - \sum _{\begin{array}{c} t \in \{0,\dots ,r\}:\\ a_t> i+1 \end{array}}\frac{1}{a_t\left( {\begin{array}{c}a_t-1\\ t-1\end{array}}\right) }\\ =&\frac{1}{a_s\left( {\begin{array}{c}a_s - 1\\ s\end{array}}\right) } - \frac{1}{(a_s+1)\left( {\begin{array}{c}a_s\\ s\end{array}}\right) } - \sum _{\begin{array}{c} t \in \{0,\dots ,r\}:\\ a_t > i+1 \end{array}}\frac{1}{a_t\left( {\begin{array}{c}a_t-1\\ t-1\end{array}}\right) } \end{aligned}$$

According to Lemma 3 this equals:

$$\begin{aligned} \frac{1}{(a_s+1)\left( {\begin{array}{c}a_s\\ s+1\end{array}}\right) } - \sum _{\begin{array}{c} t \in \{0,\dots ,r\}:\\ a_t> i+1 \end{array}}\frac{1}{a_t\left( {\begin{array}{c}a_t-1\\ t-1\end{array}}\right) }= \frac{1}{(a_{s+1})\left( {\begin{array}{c}a_{s+1}-1\\ s+1\end{array}}\right) } - \sum _{\begin{array}{c} t \in \{0,\dots ,r\}:\\ a_t > i+1 \end{array}}\frac{1}{a_t\left( {\begin{array}{c}a_t-1\\ t-1\end{array}}\right) } = \varphi _{i+1}(q), \end{aligned}$$

where the last equality uses Theorem 1.

Next, we show that Lemma 4 generalizes Theorem 2. We can, in fact, show the following stronger corollary (proof omitted).

Corollary 1

Let $\mathrm {w}$ be a vector of super-increasing weights. Let $A(q) = \{a_0,\dots ,a_r\}$. Then for all $i \ge a_r$, either $\varphi _i(q) = \varphi _{i-1}(q)$, or $\varphi _{i-1}(q) = \varphi _{i-2}(q)$.

Invoking Corollary 1 with $i = n$ gives Theorem 2.

Another interesting implication of Corollary 1 is the following. Suppose that $A(q) = \{a_0,\dots ,a_r\}$, then for all $i,j > a_r$, $\varphi _i(q) = \varphi _j(q)$.

It is often desirable that WVGs exhibit separability: if two players have different weights, then they should have different voting power. [4] show that separability is not attainable under SI weights; Corollary 1 implies that some quotas offer more separability than others: if $A(q)$ does not consist of low-weight agents, then low-weight agents are not separable under q. For example, if weights are exponents of 2 and $q = \ell 2^{n - m}$, where $\ell$ is an odd number, then $\varphi _{n-m+1} = \dots = \varphi _{n}(q)$. Our results allow us to bound the difference in voting power that one may achieve by changing the quota under SI weights. Recall that given a set $S \subseteq N$, $S^-$ is the set for which $\beta (S) = \beta (S^-) +1$. As the Shapley values are constant in the interval $(w(S^-),w(S)]$, in order to analyze the behavior of $\varphi _i(q)$, one needs only determine the rate of increase or decrease at quotas of the form w(S) for $S \subseteq N$. These are given by the following lemma.

Lemma 5

For every $S \subseteq N$, and any $i \in N$, if $i \notin S^-$ then $\varphi _i(w(S^-)) < \varphi _i(w(S))$. If $i \in S^-$ then $\varphi _i(w(S^-)) > \varphi _i(w(S))$.

Moreover, $|\varphi _i(w(S)) - \varphi _i(w(S^-))| = \frac{1}{n}$ if one of the following holds: (a) $S = \{n\}$; (b) $i < n$ and $S = \{1,\ldots ,i\}$ or $S = \{i,n\}$; or (c) $i = n$ and $S = \{n-1\}$. Otherwise, $|\varphi _i(w(S)) - \varphi _i(w(S^-))| \le \frac{1}{n(n-1)}$.

Proof

Given a non-empty set $S \subseteq N$, we define $\varphi _+ = \varphi _i(w(S))$ and $\varphi _- = \varphi _i(w(S^-))$. Let $S = \{a_0,\ldots ,a_r\}$. We have $S^- = \{a_0,\ldots ,a_{r-1},a_r+1,\ldots ,n\}$.

Suppose first that $i > a_r$, and let s be the index of i in the sequence $S^-$. According to Theorem 1, $\varphi _+ = 0$ and

$$ \varphi _- = \frac{1}{i\left( {\begin{array}{c}i-1\\ s\end{array}}\right) } - \sum _{\ell =1}^{n-i} \frac{1}{(i+\ell )\left( {\begin{array}{c}i+\ell -1\\ s+\ell -1\end{array}}\right) } = \frac{1}{n\left( {\begin{array}{c}n-1\\ s+n-i\end{array}}\right) }; $$

thus $\varphi _- > \varphi _+$. Furthermore, $|\varphi _+ - \varphi _-| \le \frac{1}{n(n-1)}$, unless $s+n-i \in \{0,n-1\}$. If $s+n-i = 0$ then $s = 0$ and $i = n$, implying $S^- = \{n\}$ and so $S = \{n-1\}$. If $s+n-i = n-1$ then $s = i-1$ and so $S^- = \{1,\ldots ,n\}$, which is impossible. The cases where $i = a_r$ and $i < a_r$ are similarly analyzed, and provide the complete case analysis; we omit the details due to space constraints.

5 The Limiting Behavior of the Shapley Value Under Super-Increasing Weights

Given a super-increasing sequence $w_1,\ldots ,w_n$ (where again, $w_1> w_2> \dots > w_n$) and some $m \in N$, let us write $\mathrm {w}|_m$ for $(w_1,\dots ,w_m)$ and [m] for $\{1,\dots ,m\}$. We write $\varphi _i(\mathrm {w}|_m;q)$ for the Shapley value of agent $i \in [m]$ in the weighted voting game in which the set of agents is [m], the weights are $\mathrm {w}|_m$, and the quota is q. We also write $A|_m(q)$ for the set $S \subseteq [m]$ such that $q \in (w|_m(S^-),w|_m(S)]$.

The following lemma (proof omitted) relates $\varphi _i(\mathrm {w};q)$ and $\varphi _i(\mathrm {w}|_m;q)$.

Lemma 6

Let $m \in N$ and $i \in [m]$, and let $q \in (0,w([m])]$. Then

$$\varphi _i(\mathrm {w}|_m;q) = \varphi _i(\mathrm {w};w(A|_m(q))). $$

Therefore the plot of $\varphi _i(\mathrm {w}|_m;q)$ (as a function of q) can be readily obtained from that of $\varphi _i(\mathrm {w};q)$. This suggests looking at the limiting case of an infinite super-increasing sequence $(w_i)_{i=1}^\infty$, which is a sequence satisfying $w_i > 0$ and $w_i \ge \sum _{j=i+1}^\infty w_j$ for all $i \ge 1$. In this section we make some normalizing assumptions that will be useful. Just like in the preceding subsections, we assume that weights are arranged in decreasing order; furthermore, we assume that $w_1 = \frac{1}{2}$. This is no loss of generality: it is an easy exercise to see that given a weight vector $\mathrm {w}$ and some positive constant $\alpha$, $\varphi _i(\mathrm {w};q) = \varphi _i(\alpha \mathrm {w};\alpha q)$. Thus, instead of the weight vector $(2^{n-1},2^{n-2},\dots ,1)$, we now have $(\frac{1}{2},\frac{1}{4},\dots ,\frac{1}{2^{n-1}})$. The super-increasing condition implies that the infinite sequence sums to some value $w(\infty ) \le 1$. Lemma 6 suggests how to define $\varphi _i(q)$ in this case. For $q \in (0,w(\infty ))$ and $i \ge 1$, define: $\varphi ^{(\infty )}_i(q) = \lim _{n\rightarrow \infty } \varphi _i(\mathrm {w}|_n;q).$

We show that the limit exists by providing an explicit formula for it, as given in the main result of this section, Theorem 3. Under this definition, Lemma 6 easily extends to the case $n = \infty$ (proof omitted):

Lemma 7

Let $m \ge 1$ be an integer, let $i \in [m]$, and let $q \in (0,w([m])]$. Then $\varphi _i(\mathrm {w}|_m;q) = \varphi ^{(\infty )}_i(w(A|_m(q)))$.

Below, we consider possibly infinite subsets $S = \{a_0,\ldots ,a_r\}$ of the positive integers, ordered in increasing order; when $r = \infty$, the subset is infinite. Also, the notation $\{a,\ldots ,\infty \}$ (or $\{a,\ldots ,r\}$ when $r=\infty$) means all integers larger than or equal to a.

Given a finite sequence of integers $S = \{a_0,\dots ,a_r\}$, such that $a_0<a_1< \dots <a_r$, we define $S^-$ to be $\{a_0,\dots ,a_{r-1}\}\cup \{a_{r+1},\dots ,\infty \}$; note the analogy to the finite case: when we had a finite sequence of agents N, $S^-$ was the maximal weight set such that $w(S^-) < w(S)$. This is also the case for $S^-$ as defined above. For a (possibly infinite) subset S of the positive integers, define $\beta _\infty (S) = \sum _{i \in S} 2^{-i}.$ First, we show an analog of Lemma 1 (proof omitted).

Lemma 8

Suppose $S,T\subseteq \mathbb {N}$ are two subsets of the positive integers. Then $\beta _\infty (S) \le \beta _\infty (T)$ if and only if $w(S) \le w(T)$. Further, if $\beta _\infty (S) < \beta _\infty (T)$ then $w(S) < w(T)$.

There is a subtlety involved here: unlike the finite case explored in Lemma 1, we can have $\beta _\infty (S) = \beta _\infty (T)$ for $S \ne T$. This is because dyadic rationals (numbers of the form $\frac{a}{2^b}$ for some positive integer a) have two different binary expansions. For example, $\frac{1}{2} = (0.1000\ldots )_2 = (0.0111\ldots )_2$. The lemma states (in this case) that $w(\{1\}) \ge w(\{2,3,4,\ldots \})$, but there need not be equality.

Next, we use the fact that any real $r \in (0,1)$ has a binary expansion with infinitely many 0s (alternatively, a set $S_r$ such that $\beta _\infty (S_r) =\sum _{n \in S_r}2^{-n}= r$ and there are infinitely many $n \notin S_r$), and a binary expansion with infinitely many 1s (alternatively, a set $T_r$ such that $\beta _\infty (T_r) = \sum _{n \in T}2^{-n} = r$ and there are infinitely many $n \in T_r$). If r is not dyadic, then it has a unique binary expansion which has infinitely many 0s and 1s. If r is dyadic, say $r=\frac{1}{2}$, then it has one expansion $(0.1000\ldots )_2$ with infinitely many 0s and another expansion $(0.0111\ldots )_2$ with infinitely many 1s. The following lemma describes the analog of the intervals $(w(S^-),w(S)]$ in the infinite case.

Lemma 9

Let $q \in (0,w(\infty ))$. There exists a non-empty subset S of the positive integers such that either $q = w(S)$ or $S=\{a_0,\ldots ,a_r\}$ is finite and $q \in (w(S^-),w(S)]$.

Proof

Since $q < w(\infty )$, there exists some finite m such that $q \le w([m])$. For any $n \ge m$, let $A|_n = A|_n(q)$. Let $Q|_n$ be the subset of [n] preceding $A|_n$, and let $R|_n$ be the subset of $[n+1]$ preceding $A|_n$; here “preceding” is in the sense of $X \mapsto X^-$. The interval $(w(Q|_n),w(A|_n)]$ splits into $(w(Q|_n),w(R|_n)] \cup (w(R|_n),w(A|_n)]$, and so $A|_{n+1} \in \{R|_n,A|_n\}$. Also $\beta _\infty (A|_{n+1}) \le \beta _\infty (A|_n)$, with equality only if $A|_{n+1} = A|_n$. We consider two cases. The first case is when for some integer M, for all $n \ge M$ we have $A|_n = A= \{a_0,\ldots ,a_r\}$. In that case for all $n \ge M$ $\sum _{t=0}^{r-1} w_{a_t} + \sum _{t=a_r+1}^n w_t < q \le \sum _{t=0}^r w_{a_t}$, and taking the limit $n \rightarrow \infty$ we obtain $q \in (w(A^-),w(A)]$. The other case is when $A|_n$ never stabilizes. The sequence $\beta _\infty (A|_n)$ is monotonically decreasing, and reaches a limit b satisfying $b < \beta _\infty (A|_n)$ for all n. Since $w(A|_m) \in (w(Q|_n),w(A|_n)]$ for all integers $m \ge n \ge 1$, Lemma 8 implies that $b \in [\beta _\infty (Q|_n),\beta _\infty (A|_n))$.

Let L be a subset such that $b = \beta _\infty (L)$ and there are infinitely many $i \notin L$, and define $L|_n = L \cap [n]$. We have $b \in [\beta _\infty (L|_n),\beta _\infty (L|_n) + 2^{-n})$. Thus $Q|_n = L|_n$, and so $q > w(Q|_n) = w(L|_n)$. Taking the limit $n \rightarrow \infty$, we deduce that $q \ge w(L)$. If $n \notin L$ then $A|_n = Q|_n \cup \{n\}$, and so $q \le w(A|_n) = w(L|_n) + w_n$. There are infinitely many such n, so taking the limit $n \rightarrow \infty$ we conclude that $q \le w(L)$ and so $q = w(L)$.

We can now give an explicit formula for $\varphi ^{(\infty )}_i$. We extend our notation to accommodate the notions given in Lemma 9. The proof of Theorem 3 is similar in spirit to the proof of Theorem 1, with one important subtlety: given some $q \in (0,w(\infty ))$, we write $A(q)\subseteq \mathbb {N}$ to be an infinite set S such that $q = w(S)$, or the finite set S for which $q \in (w(S^-),w(S)]$. In the first case there may be more than one set S such that $q = w(S)$; Theorem 3 holds for any of the possible representations of q using $\mathrm {w}$.

Theorem 3

Let $q \in (0,w(\infty ))$ and let i be a positive integer. Let $A(q) = \{a_0,\dots ,a_r\}$ be the set defined in Lemma 9. Then:

• (a) the limit $\varphi ^{(\infty )}_i(q) = \lim _{n\rightarrow \infty } \varphi _i(\mathrm {w}|_n;q)$ exists.

• (b) if $i \notin A(q)$ then

  $$\varphi ^{(\infty )}_i(q) = \sum _{\begin{array}{c} t \in \{0,\ldots ,r\}:\\ a_t > i \end{array}} \frac{1}{a_t\left( {\begin{array}{c}a_t-1\\ t\end{array}}\right) }.$$

  If $i \in A(q)$, say $i = a_s$, then

  $$ \varphi ^{(\infty )}_i(q) = \frac{1}{a_s\left( {\begin{array}{c}a_s-1\\ s\end{array}}\right) } - \sum _{\begin{array}{c} t \in \{0,\ldots ,r\}:\\ a_t > i \end{array}} \frac{1}{a_t\left( {\begin{array}{c}a_t-1\\ t-1\end{array}}\right) }.$$

We conclude by stating that the limiting functions $\varphi _i^{(\infty )}$ are continuous; the proof is omitted due to space constraints.

Theorem 4

Let i be a positive integer. The function $\varphi ^{(\infty )}_i$ is continuous on $(0,w(\infty ))$, and $\lim _{q \rightarrow 0} \varphi ^{(\infty )}_i(q) = \lim _{q \rightarrow w(\infty )} \varphi ^{(\infty )}_i(q) = 0.$

Summarizing, we can extend the functions $\varphi _i(\mathrm {w}|_n;q)$ to a continuous function $\varphi _i^{(\infty )}$ which agrees with $\varphi _i(\mathrm {w}|_n;q)$ on the points w(S) for $S \subseteq \{1,\ldots ,n\}$.

When $w_i = 2^{-i}$ the plot of $\varphi ^{(\infty )}$ has no flat areas, but when $w_i = d^{-i}$ for $d > 2$, the limiting function is constant on intervals $(w(S^-),w(S)]$. This is reflected in Fig. 1. These flat areas highlight a curious phenomenon. When $w_1 > \sum _{j=2}^\infty w_j$, we have $w(\{2,3,\ldots ,\infty \}) < w(\{1\})$, which corresponds to the strict inequality $0.0111\ldots < 0.1$ in binary, or $0.4999\ldots < 0.5$ in decimal. The infinitesimal difference is expanded to an interval $(w(\{1\}^-),w(\{1\})]$ of non-zero width $w_1 - \sum _{j=2}^\infty w_j$. When $w_i > \sum _{j=i+1}^\infty w_j$ for all i, this phenomenon happens around every dyadic number.

6 Conclusions and Future Work

In this paper we present a series of novel results characterizing the behavior of the Shapley value in WVGs when weights are super-increasing. We derive an explicit formula for the Shapley value in this case, and use it to gain several insights, bounding the gain in value as the quota changes, and explaining our results via the behavior of an interesting fractal function. While our technical results are interesting on their own, they offer some instructive insights on the study of WVGs in the AI lens. For example, our combinatorial techniques can inform the study of annexation and merging in WVGs [32–35], as well as other AI domains such as combinatorial auctions and boolean threshold logic.