API Docs#

class shapleyrouting.rideshare.RideShare(num_players, distances)#

Bases: object

APPROO1(num, Distances)#

Compute 2D approximation for Shapley values.

This algorithm is designed based on the Appro-O(1) algorithm for Shapley value approximation by Dan C. Popescu and Philip Kilby.

The approximation equation is as follows for a given location k:

\[\phi^{(1)}_k=s_{kk}-Sc(S_{1,k},...,S_{k-1,k},S_{k+1,k},...,S_{n,k})\]

This equation uses the equations for shared distance between two locations, i and j, with respect to starting location.

\[s_{ij} = d_{0i}+d_{0j}-d_{ij}\]

It also uses the Shared Contribution function. Please note in the equation below that the vector y is equivalent to the input vector x sorted in descending order.

\[Sc(x_1,x_2,...,x_k)=\sum\limits_{i=1}^{k} \frac{y_i}{i(i+1)}\]
Parameters:

  • num (int) – Number of players.

  • Distances (list) – 2D list of distances.

Returns:

appro – List of approximated shapley values.

Return type:

list

Examples

>>> num = 9
>>> Distances = [
    [0, 2, 9, 7, 7, 7, 6, 7, 1, 7],
    [2, 0, 5, 9, 9, 8, 9, 1, 7, 6],
    [9, 5, 0, 9, 6, 5, 7, 4, 7, 1],
    [7, 9, 9, 0, 1, 2, 8, 7, 1, 5],
    [7, 9, 6, 1, 0, 5, 5, 5, 8, 8],
    [7, 8, 5, 2, 5, 0, 1, 8, 2, 5],
    [6, 9, 7, 8, 5, 1, 0, 1, 6, 1],
    [7, 1, 4, 7, 5, 8, 1, 0, 1, 2],
    [1, 7, 7, 1, 8, 2, 6, 1, 0, 4],
    [7, 6, 1, 5, 8, 5, 1, 2, 4, 0]
    ]
>>> APPROO1(num, Distances)
[-1.3249999999999993,
5.001190476190477,
2.994047619047622,
3.05952380952381,
2.8861111111111093,
2.2075396825396822,
2.908333333333333,
-3.362698412698413,
2.4940476190476204]
SHAPO(num, Distances)#

Compute ride sharing Shapley values.

Parameters:

  • num (int) – Number of players.

  • Distances (list) – 2D list of distances.

Returns:

shapo – List of shapley values.

Return type:

list

Examples

>>> num = 2
>>> Distances = [[0, 1, 2], [1, 0, 3], [2, 3, 0]]
>>> SHAPO(num, Distances)
[2.0, 4.0]
cost_samples(subsets, costs)#

Compute Shapley values for ride sharing given cost samples.

This algorithm is designed based on the cost sharing algorithm based on cost samples, written by Eric Balkanski, Umar Syed, and Sergei Vassilvitskii.

Given a set of \(m\) samples, \((S_1, C(S_1)), (S_2, C(S_2)), ..., (S_m, C(S_m))\), from distribution \(\mathcal{D}\), where \(S_i\) represents a subset of players and \(C(S_i)\) represents the cost of the subset of players, the approximate share of the player \(i\), denoted by \(\tilde{\Phi^\mathcal{D}_i}\) is given by:

\[\tilde{\phi^\mathcal{D}_i} = \frac{1}{m} \sum\limits_{S_j : i \in S_j} \frac{C(S_j)}{|S_j|}\]
Parameters:

  • subsets (numpy.ndarray) – 2D boolean array of size mxn, where m is the number of subsets of players and n is the number of players. Each boolean entry indicates whether or not the player was included in that subset.

  • costs (numpy.ndarray) – 1D array of length m indicating the total costs incurred by each subset.

Examples

>>> import numpy as np
>>> subsets = np.array([
...     [True, False, False],
...     [False, True, True],
...     [True, True, False],
... ], dtype=bool)
>>> costs = np.array([10, 5, 8], dtype=np.float64)
>>> cost_samples(subsets, costs)
array([4.66666667, 2.16666667, 0.83333333])
fit()#