Python 3.7 implementation of the Shapley value for distributioning a total surplus to players in a game.

shapley_value.py

#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""
Shapley value (Python implementation)
-------------------------------------
@author: tommyod (https://github.com/tommyod)

A coalition of players cooperates, and obtains an overall gain from cooperation. 
Since some players may contribute more to the coalition than others, 
or may possess different bargaining power, what final distribution of 
generated surplus among the players should arise in any particular game? 

Phrased differently: how important is each player to the overall cooperation, 
and what payoff can he or she reasonably expect? 

The Shapley value provides one possible answer to this question. 
"""

import itertools
from scipy.special import comb as combinations


def powerset(iterable):
    "powerset([1,2,3]) --> () (1,) (2,) (3,) (1,2) (1,3) (2,3) (1,2,3)"
    # https://docs.python.org/3/library/itertools.html#itertools-recipes
    s = list(iterable)
    return itertools.chain.from_iterable(itertools.combinations(s, r) for r in range(len(s) + 1))


def shapley(players, characteristic_function):
    """Yield pairs of (player, shapley_value).

    This function implements the third equation for the Shapley Value
    from Wikipedia. The runtime is O(2**num_players).
        https://en.wikipedia.org/wiki/Shapley_value#Formal_definition

    Parameters
    ----------
    players : iterable
        An iterable consisting of hashable (int, str, ...) players.
    characteristic_function : callable
        A function taking a set of players as input and returning a value.

    Yields
    ------
    (player, shapley_value)
        Players and their shapley values in a tuple.
    """

    players = set(players)
    num_players = len(players)

    # Form all subsets of players and compute the characteristic function
    subsets = (frozenset(subset) for subset in powerset(players))
    cached_values = {subset: characteristic_function(subset) for subset in subsets}

    for player in players:
        shapley_value = 0

        # Create all subsets that do not have this player present
        subsets_wo_player = (frozenset(subset) for subset in powerset(players - set([player])))

        # Loop through each subset
        for subset_wo_player in subsets_wo_player:

            # Number of coalitions excluding 'player' of this size
            num_coalitions = combinations(N=num_players - 1, k=len(subset_wo_player))

            # Value of this coalition with the player and without the player
            value_with_player = cached_values[subset_wo_player.union(set([player]))]
            value_wo_player = cached_values[subset_wo_player]

            shapley_value += (value_with_player - value_wo_player) / num_coalitions

        # Yield result for this player
        shapley_value = shapley_value / num_players
        yield player, shapley_value


# =============================================================================
# TEST AGAINST EXAMPLES FROM LITTERATURE
# =============================================================================


if __name__ == "__main__":

    def test_against_wikipedia():
        def characteristic_function(coalition):
            # https://en.wikipedia.org/wiki/Shapley_value#Glove_game
            if coalition in set([frozenset([1, 3]), frozenset([2, 3]), frozenset([1, 2, 3])]):
                return 1
            else:
                return 0

        players = [1, 2, 3]
        shapley_values = dict(shapley(players, characteristic_function))

        # Verify the numbers from the Wikipedia example
        assert shapley_values[1] == shapley_values[2] == 1 / 6
        assert shapley_values[3] == 2 / 3

        # Shapley values must sum to the value of the grand coalition (all players)
        assert sum(shapley_values.values()) == characteristic_function(set(players))

    def test_against_narahari_ex_292():
        """Test against example 29.2 in the book 'Game theory and mechanism desin'
        by Narahari."""

        def characteristic_function(coalition):
            if coalition in set([frozenset([1, 2]), frozenset([1, 3]), frozenset([1, 2, 3])]):
                return 300
            else:
                return 0

        players = [1, 2, 3]
        shapley_values = dict(shapley(players, characteristic_function))

        # Verify the numbers
        assert shapley_values[1] == 200
        assert shapley_values[2] == 50
        assert shapley_values[3] == 50

        # Shapley values must sum to the value of the grand coalition (all players)
        assert sum(shapley_values.values()) == characteristic_function(set(players))

    def test_against_narahari_ex_293():
        """Test against example 29.3 in the book 'Game theory and mechanism desin'
        by Narahari."""

        def characteristic_function(coalition):
            if coalition == frozenset([1]):
                return 5
            elif coalition == frozenset([2]):
                return 9
            elif coalition == frozenset([3]):
                return 7
            elif coalition == frozenset([1, 2]):
                return 15
            elif coalition == frozenset([1, 3]):
                return 12
            elif coalition == frozenset([2, 3]):
                return 17
            elif coalition == frozenset([1, 2, 3]):
                return 23
            else:
                return 0

        players = [1, 2, 3]
        shapley_values = dict(shapley(players, characteristic_function))

        # Verify the numbers
        assert shapley_values[1] == 5.5
        assert shapley_values[2] == 10
        assert shapley_values[3] == 7.5

        # Shapley values must sum to the value of the grand coalition (all players)
        assert sum(shapley_values.values()) == characteristic_function(set(players))

    def test_against_narahari_ex_295():
        """Test against example 29.5 in the book 'Game theory and mechanism design'
        by Narahari. This is called the Apex Game."""

        def characteristic_function(coalition):
            if 1 in coalition and len(coalition) >= 2:
                return 1
            if len(coalition) >= 4:
                return 1
            return 0

        players = [1, 2, 3, 4, 5]
        shapley_values = dict(shapley(players, characteristic_function))

        # Verify the numbers
        epsilon = 1e-10
        assert abs(shapley_values[1] - 3 / 5) < epsilon
        for player in [2, 3, 4, 5]:
            assert abs(shapley_values[player] - 1 / 10) < epsilon

        # Shapley values must sum to the value of the grand coalition (all players)
        assert sum(shapley_values.values()) == characteristic_function(set(players))

    def test_against_narahari_ex_296():
        """Test against example 29.6 in the book 'Game theory and mechanism design'
        by Narahari. The problem was introduced in example 27.8."""

        def characteristic_function(coalition):
            if coalition == frozenset([1, 2, 3, 4]):
                return 100 - 35
            elif coalition == frozenset([1, 2, 4]):
                return 100 - 55
            elif coalition == frozenset([1, 3, 4]):
                return 100 - 60
            else:
                return 0

        players = [1, 2, 3, 4]
        shapley_values = dict(shapley(players, characteristic_function))

        # Verify the numbers
        # The solution given in the book is (20, 20, 5, 20), but this is WRONG
        # This is confirmed by both this implementation, and the implementation
        # found at http://shapleyvalue.com/index.php
        epsilon = 1e-10
        assert abs(shapley_values[1] - 23.333333333333) < epsilon
        assert abs(shapley_values[2] - 10) < epsilon
        assert abs(shapley_values[3] - 8.3333333333333) < epsilon
        assert abs(shapley_values[4] - 23.333333333333) < epsilon

        # Shapley values must sum to the value of the grand coalition (all players)
        assert sum(shapley_values.values()) == characteristic_function(set(players))

    def test_against_unanimity_game(num_players):
        def characteristic_function(coalition):
            if len(coalition) == num_players:
                return 1
            return 0

        players = list(range(num_players))
        shapley_values = dict(shapley(players, characteristic_function))

        epsilon = 1e-10
        for player in players:
            assert abs(shapley_values[player] - 1 / num_players) < epsilon

        # Shapley values must sum to the value of the grand coalition (all players)
        assert sum(shapley_values.values()) == characteristic_function(set(players))

    def test_against_multiagent_systems_1212():
        """Test against Example 12.1.2. in the book 'Multiagent Systems' by
        Yoav Shoham and Kevin Leyton-Brown. See page 390."""

        def characteristic_function(coalition):
            votes_per_party = {"A": 45, "B": 25, "C": 15, "D": 15}
            if sum(votes_per_party[party] for party in coalition) >= 51:
                return 100
            return 0

        players = list("ABCD")
        shapley_values = dict(shapley(players, characteristic_function))

        epsilon = 1e-10
        assert abs(shapley_values["A"] - 100 / 2) < epsilon
        assert abs(shapley_values["B"] - 100 / 6) < epsilon
        assert abs(shapley_values["C"] - 100 / 6) < epsilon
        assert abs(shapley_values["D"] - 100 / 6) < epsilon

        # Shapley values must sum to the value of the grand coalition (all players)
        assert abs(sum(shapley_values.values()) - characteristic_function(set(players))) < epsilon

    # Test against many examples
    test_against_wikipedia()
    test_against_narahari_ex_292()
    test_against_narahari_ex_293()
    test_against_narahari_ex_295()
    test_against_narahari_ex_296()
    for num_players in [1, 2, 3, 4, 5]:
        test_against_unanimity_game(num_players=num_players)
    test_against_multiagent_systems_1212()