3.5 Calculating Power- Shapley-Shubik Power Index

The Shapley-Shubik power index was introduced in 1954 by economists Lloyd Shapley and Martin Shubik, and provides a different approach for calculating power.

# Math in Society 3.5 -- Shapley-Shubik: sequential coalitions and pivotal players
# Order matters now. In <P3, P2, P4, P1> the players joined in that order, and the
# PIVOTAL player is the one whose arrival first pushes the running total to quota.
from itertools import permutations
from math import factorial

def pivotal(order, q, w):
    run = 0
    for i in order:
        run += w[i]
        if run >= q:
            return i
    return None

# Trace one sequential coalition by hand, the way the book does.
q, w = 8, [6, 4, 3, 2]
order = (2, 1, 3, 0)                       # <P3, P2, P4, P1>.  EDIT this order.
print(f"[{q}: {', '.join(map(str, w))}]   tracing <"
      + ", ".join(f"P{i+1}" for i in order) + ">")
run = 0
for i in order:
    run += w[i]
    print(f"   P{i+1} joins, weight {w[i]:>2}   running total {run:>3}"
          f"   {'WINNING' if run >= q else 'not winning yet'}")
print(f"   -> P{pivotal(order, q, w)+1} is the pivotal player\n")

def shapley(q, w, show=False, names=None):
    n = len(w)
    names = names or [f"P{i+1}" for i in range(n)]
    assert n <= 8, "n! sequential coalitions -- keep this to 8 players or fewer"
    total = factorial(n)
    print(f"[{q}: {', '.join(map(str, w))}]   {total} sequential coalitions")
    counts = [0] * n
    for order in permutations(range(n)):
        p = pivotal(order, q, w)
        counts[p] += 1
        if show:
            print("   <" + ", ".join(f"[{names[i]}]" if i == p else names[i]
                                     for i in order) + ">")
    for i in range(n):
        print(f"   {names[i]:<8} pivotal in {counts[i]:>4} of them"
              f"   ->  {counts[i]}/{total} = {counts[i]/total:6.1%}")
    print()
    return counts

# All 3! = 6 sequential coalitions, pivotal player in [brackets]
shapley(6, [4, 3, 2], show=True)
shapley(36, [20, 17, 15])
shapley(8, [6, 3, 2])                       # EDIT: your own [q: w1, w2, ...]

print("A voting system with 7 players has 7! = 5040 sequential coalitions, and")
print("10 players has 3,628,800. This is why the Electoral College power index has")
print("to be estimated rather than counted.")
print("Try it: compare shapley(8, [6, 3, 2]) above with the Banzhaf answer for the")
print("same system, 60% / 20% / 20%. Two reasonable definitions of power, two")
print("different numbers for the same three players.")

In situations like political alliances, the order in which players join an alliance could be considered the most important consideration. In particular, if a proposal is introduced, the player that joins the coalition and allows it to reach quota might be considered the most essential. The Shapley-Shubik power index counts how likely a player is to be pivotal. What does it mean for a player to be pivotal?

First, we need to change our approach to coalitions. Previously, the coalition $open brace P sub 1, P sub 2 close brace$ and $open brace P sub 2, P sub 1 close brace$ would be considered equivalent, since they contain the same players. We now need to consider the order in which players join the coalition. For that, we will consider sequential coalitions – coalitions that contain all the players in which the order players are listed reflect the order they joined the coalition. For example, the sequential coalition

$less than P sub 2, P sub 1, P sub 3 greater than$ would mean that $P sub 2$ joined the coalition first, then $P sub 1$ , and finally $P sub 3$ . The angle brackets < > are used instead of curly brackets to distinguish sequential coalitions.

Example 1

In the weighted voting system $open bracket 8: 6, 4, 3, 2 close bracket$ , which player is pivotal in the sequential coalition $less than P sub 3, P sub 2, P sub 4, P sub 1 greater than$ ?

Show solution

The sequential coalition shows the order in which players joined the coalition. Consider the running totals as each player joins:

$\begin{matrix} P_{3} & Total weight: 3 & Not winning \\ P_{3}, P_{2} & Total weight: 3 + 4 = 7 & Not winning \\ P_{3}, P_{2}, P_{4} & Total weight: 3 + 4 + 2 = 9 & Winning \\ R_{2}, P_{3}, P_{4}, P_{1} & Total weight: 3 + 4 + 2 + 6 = 15 & Winning \end{matrix}$

Since the coalition becomes winning when $P sub 4$ joins, $P sub 4$ is the pivotal player in this coalition.

How many sequential coalitions should we expect to have? If there are N players in the voting system, then there are $N$ possibilities for the first player in the coalition, $N – 1$ possibilities for the second player in the coalition, and so on. Combining these possibilities, the total number of coalitions would be: $N (N - 1) (N - 2) (N - 3) \dots (3) (2) (1)$ . This calculation is called a factorial, and is notated $N!$ The number of sequential coalitions with $N$ players is $N!$

As you can see, computing the Shapley-Shubik power index by hand would be very difficult for voting systems that are not very small.

# Math in Society 3.5 -- Enter [q: w1, w2, ...] and get BOTH power indices
# Banzhaf counts how often a player is CRITICAL in a winning coalition.
# Shapley-Shubik counts how often a player is PIVOTAL in a sequential coalition.
from itertools import combinations, permutations
from math import factorial

def power(q, w, names=None, label=""):
    n = len(w)
    names = names or [f"P{i+1}" for i in range(n)]
    assert n <= 8, "n! grows fast -- keep this to 8 players or fewer"
    total_w = sum(w)

    critical, winning = [0] * n, 0
    for k in range(1, n + 1):
        for c in combinations(range(n), k):
            weight = sum(w[i] for i in c)
            if weight < q:
                continue
            winning += 1
            for i in c:
                if weight - w[i] < q:
                    critical[i] += 1

    pivot = [0] * n
    for order in permutations(range(n)):
        run = 0
        for i in order:
            run += w[i]
            if run >= q:
                pivot[i] += 1
                break

    tc, tp = sum(critical), factorial(n)
    print(f"{label}[{q}: {', '.join(map(str, w))}]"
          f"   {winning} winning coalitions, {tp} sequential coalitions")
    print(f"   {'player':<19}{'weight':>7}{'weight %':>10}"
          f"{'critical':>10}{'Banzhaf':>10}{'pivotal':>9}{'Shapley':>10}")
    for i in range(n):
        print(f"   {names[i]:<19}{w[i]:>7}{w[i]/total_w:>10.1%}"
              f"{critical[i]:>10}{critical[i]/tc:>10.1%}"
              f"{pivot[i]:>9}{pivot[i]/tp:>10.1%}")
    print()

power(65, [47, 46, 17, 16, 2], label="Scottish Parliament 2009  ",
      names=["Scottish Nat.", "Labour", "Conservative", "Lib Democrat", "Green"])
power(51, [30, 25, 25, 20], label="Four shareholders  ",
      names=["Mr Smith", "Mr Garcia", "Mrs Hughes", "Mrs Lee"])
power(6, [4, 3, 2])
power(36, [20, 17, 16, 3])          # EDIT: any quota and weight list you like

print("The two indices usually agree on the ranking and disagree on the numbers,")
print("because they answer different questions: 'how often could I break this")
print("coalition?' versus 'how often would I be the one who completes it?'")
print("Try it: Mrs Lee owns 20% of the company but holds only 8.3% of the power.")
print("Change the shareholders' quota from 51 to 61 and re-run: no two owners can")
print("pass anything, any three can, and all four end up with exactly 25% power.")
print("The small shareholder gains everything the largest one loses.")

Example 3

Consider the weighted voting system $open bracket 6: 4, 3, 2 close bracket$ . We will list all the sequential coalitions and identify the pivotal player. We will have 3! = 6 sequential coalitions. The coalitions are listed, and the pivotal player is underlined.

$less than P sub 1, P bar sub 2, P sub 3 greater than less than P sub 1, P bar sub 3, P sub 2 greater than less than P sub 2, P bar sub 1, P sub 3 greater than; less than P sub 2, P sub 3, P bar sub 1 greater than less than P sub 3, P sub 2, P bar sub 1 greater than less than P sub 3, P bar sub 1, P sub 2 greater than$

Show solution

$P sub 1$ is pivotal 4 times, $P sub 2$ is pivotal 1 time, and $P sub 3$ is pivotal 1 time.

Player	Times pivotal	Power index
$P sub 1$	4	$4 / 6 equals 66.7 %$
$P sub 2$	1	$1 / 6 equals 16.7 %$
$P sub 3$	1	$1 / 6 equals 16.7 %$

For comparison, the Banzhaf power index for the same weighted voting system would be $P sub 1: 60 %, P sub 2: 20 %, P sub 3: 20 %$ . While the Banzhaf power index and Shapley-Shubik power index are usually not terribly different, the two different approaches usually produce somewhat different results.

Your Turn

Try it Now 4

Find the Shapley-Shubik power index for the weighted voting system $open bracket 36: 20, 17, 15 close bracket$ .

Answer

Listing all sequential coalitions and identifying the pivotal player:

$less than P sub 1, P bar sub 2, P sub 3 greater than, less than P sub 1, P sub 3, P bar sub 2 greater than, less than P sub 2, P bar sub 1, P sub 3 greater than; less than P sub 2, P sub 3, P bar sub 1 greater than, less than P sub 3, P sub 2, P bar sub 1 greater than, less than P sub 3, P sub 1, P bar sub 2 greater than$

$P sub 1$ is pivotal 3 times, $P sub 2$ is pivotal 3 times, and $P sub 3$ is pivotal 0 times.

Player	Times pivotal	Power index
$P sub 1$	3	$3 / 6 equals 50 %$
$P sub 2$	3	$3 / 6 equals 50 %$
$P sub 3$	0	$0 / 6 equals 0 %$

Adapted from Math in Society by David Lippman, hosted on LibreTexts (math.libretexts.org) and licensed under CC BY-SA 3.0. Changes were made. License: CC-BY-SA-3.0.