game_theory_attribution.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Data-Driven Marketing Attribution"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Game theory and the Shapley value\n",
    "\n",
    "The Shapley value is a concept taken from cooperative game theory. In a game of multiple players that can work together (form coalitions) to increase the likelihood of a desired outcome (payoff), the Shapley value provides a way to fairly divide the payoff between the players.\n",
    "\n",
    "Essentially, the Shapley value is a measure of a player's average marginal contribution to each coalition. Taking into consideration that players can join coalitions at different points in time (order), and have varying degrees of influence (worth). Its based on the assumption that each ordering has the same probability of occurring, thus players are awarded by their contribution to all permutations.\n",
    "\n",
    "In the context of marketing analytics, campaign channels are the players of the game, and the various ways in which the channels interact with accounts throughout the buyer journey form the coalitions. Cooperative game theory and the Shapley value provide a stable way to measure channel influence and fairly divide the credit for sales conversions between the channels, based on their individual contribution to the total payoff.\n",
    "\n",
    "Marketing benefits:\n",
    "* Deeper insight into channel performance\n",
    "* Fair division of credit, based on measured contribution\n",
    "* Ability to optimise channel spend and influence sales results\n",
    "* Shapley value is a widely used, and Nobel prize winning, solution"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### The characteristic function\n",
    "\n",
    "A game is defined by a set of players ***<sup>N</sup>*** and a characteristic function ***<sup>v</sup>***. Every subset of players is called a coalition ***<sup>S</sup>***, and the characteristic function ***<sup>v(S)</sup>*** assigns a value to each coalition to signify it's worth. A coalition's worth represents the payoff that it can generate when it's players work together.\n",
    "\n",
    "Options for defining the characteristic function for marketing include:\n",
    "* Total revenue generated by each coalition\n",
    "* Total number of sales conversions generated by each coalition\n",
    "* Conversion ratio of each coalition (conversions / opportunities)\n",
    "* Conditional probability of conversion - i.e. likelihood of converting given a set of channels (Naive Bayes)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Conversion ratio example\n",
    "\n",
    "Let’s walk through an example. Say that your company converted 100 opportunities at the end of a fiscal quarter. During that period, the marketing department advertised to the associated accounts using three channels:\n",
    "\n",
    "N = {Facebook, Google, LinkedIn}\n",
    "\n",
    "All 100 accounts were touched by one or more of the channels throughout their buyer journeys. In other words, the channels worked together by forming coalitions to increase the likelihood of opportunity conversion.\n",
    "\n",
    "The table below lists all possible channel coalitions and their conversion ratios:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<div>\n",
       "<style scoped>\n",
       "    .dataframe tbody tr th:only-of-type {\n",
       "        vertical-align: middle;\n",
       "    }\n",
       "\n",
       "    .dataframe tbody tr th {\n",
       "        vertical-align: top;\n",
       "    }\n",
       "\n",
       "    .dataframe thead th {\n",
       "        text-align: right;\n",
       "    }\n",
       "</style>\n",
       "<table border=\"1\" class=\"dataframe\">\n",
       "  <thead>\n",
       "    <tr style=\"text-align: right;\">\n",
       "      <th></th>\n",
       "      <th>Coalition</th>\n",
       "      <th>Ratio</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>S1</th>\n",
       "      <td>Facebook</td>\n",
       "      <td>0.18</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>S2</th>\n",
       "      <td>Google</td>\n",
       "      <td>0.04</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>S3</th>\n",
       "      <td>LinkedIn</td>\n",
       "      <td>0.08</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>S4</th>\n",
       "      <td>Facebook+Google</td>\n",
       "      <td>0.10</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>S5</th>\n",
       "      <td>Facebook+LinkedIn</td>\n",
       "      <td>0.26</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>S6</th>\n",
       "      <td>Google+LinkedIn</td>\n",
       "      <td>0.07</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>S7</th>\n",
       "      <td>Facebook+Google+LinkedIn</td>\n",
       "      <td>0.27</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "                   Coalition  Ratio\n",
       "S1                  Facebook   0.18\n",
       "S2                    Google   0.04\n",
       "S3                  LinkedIn   0.08\n",
       "S4           Facebook+Google   0.10\n",
       "S5         Facebook+LinkedIn   0.26\n",
       "S6           Google+LinkedIn   0.07\n",
       "S7  Facebook+Google+LinkedIn   0.27"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "import numpy as np\n",
    "import pandas as pd\n",
    "from itertools import combinations\n",
    "\n",
    "def subsets(S):\n",
    "    '''Returns all possible subsets of the given set'''\n",
    "    s = []\n",
    "    for i in range(1, len(S)+1):\n",
    "        s.extend(map(list, combinations(S, i)))\n",
    "    return list(map('+'.join, s))\n",
    "\n",
    "N = sorted({'Facebook', 'Google', 'LinkedIn'})\n",
    "\n",
    "coalitions = subsets(N)\n",
    "coalitions_lbl = ['S{}'.format(i) for i in range(1, len(coalitions)+1)]\n",
    "\n",
    "# The coalition 'Facebook+Google' (S4) resulted in 10 conversions from 100 opportunities,\n",
    "# so has a conversion ratio of 10/100 = 0.1 (10%)\n",
    "IR = np.array([0.18, 0.04, 0.08, 0.1, 0.26, 0.07, 0.27])\n",
    "\n",
    "pd.options.display.float_format = '{:,.2f}'.format\n",
    "pd.DataFrame({\n",
    "    'Coalition': coalitions,\n",
    "    'Ratio': IR\n",
    "}, dtype=np.float64, index=coalitions_lbl)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<div>\n",
       "<style scoped>\n",
       "    .dataframe tbody tr th:only-of-type {\n",
       "        vertical-align: middle;\n",
       "    }\n",
       "\n",
       "    .dataframe tbody tr th {\n",
       "        vertical-align: top;\n",
       "    }\n",
       "\n",
       "    .dataframe thead th {\n",
       "        text-align: right;\n",
       "    }\n",
       "</style>\n",
       "<table border=\"1\" class=\"dataframe\">\n",
       "  <thead>\n",
       "    <tr style=\"text-align: right;\">\n",
       "      <th></th>\n",
       "      <th>Facebook</th>\n",
       "      <th>Google</th>\n",
       "      <th>LinkedIn</th>\n",
       "      <th>Facebook+Google</th>\n",
       "      <th>Facebook+LinkedIn</th>\n",
       "      <th>Google+LinkedIn</th>\n",
       "      <th>Facebook+Google+LinkedIn</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>Facebook</th>\n",
       "      <td>1</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>Google</th>\n",
       "      <td>0</td>\n",
       "      <td>1</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>LinkedIn</th>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>1</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>Facebook+Google</th>\n",
       "      <td>1</td>\n",
       "      <td>1</td>\n",
       "      <td>0</td>\n",
       "      <td>1</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>Facebook+LinkedIn</th>\n",
       "      <td>1</td>\n",
       "      <td>0</td>\n",
       "      <td>1</td>\n",
       "      <td>0</td>\n",
       "      <td>1</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>Google+LinkedIn</th>\n",
       "      <td>0</td>\n",
       "      <td>1</td>\n",
       "      <td>1</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>1</td>\n",
       "      <td>0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>Facebook+Google+LinkedIn</th>\n",
       "      <td>1</td>\n",
       "      <td>1</td>\n",
       "      <td>1</td>\n",
       "      <td>1</td>\n",
       "      <td>1</td>\n",
       "      <td>1</td>\n",
       "      <td>1</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "                          Facebook  Google  LinkedIn  Facebook+Google  \\\n",
       "Facebook                         1       0         0                0   \n",
       "Google                           0       1         0                0   \n",
       "LinkedIn                         0       0         1                0   \n",
       "Facebook+Google                  1       1         0                1   \n",
       "Facebook+LinkedIn                1       0         1                0   \n",
       "Google+LinkedIn                  0       1         1                0   \n",
       "Facebook+Google+LinkedIn         1       1         1                1   \n",
       "\n",
       "                          Facebook+LinkedIn  Google+LinkedIn  \\\n",
       "Facebook                                  0                0   \n",
       "Google                                    0                0   \n",
       "LinkedIn                                  0                0   \n",
       "Facebook+Google                           0                0   \n",
       "Facebook+LinkedIn                         1                0   \n",
       "Google+LinkedIn                           0                1   \n",
       "Facebook+Google+LinkedIn                  1                1   \n",
       "\n",
       "                          Facebook+Google+LinkedIn  \n",
       "Facebook                                         0  \n",
       "Google                                           0  \n",
       "LinkedIn                                         0  \n",
       "Facebook+Google                                  0  \n",
       "Facebook+LinkedIn                                0  \n",
       "Google+LinkedIn                                  0  \n",
       "Facebook+Google+LinkedIn                         1  "
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# B is binary squared matrix that represents coalition membership.\n",
    "# For example, coalition Facebook+LinkedIn (S5) includes members:\n",
    "# - Facebook (S1)\n",
    "# - LinkedIn (S3)\n",
    "# - Facebook+LinkedIn (S5)\n",
    "# Resulting in the coefficients: [1,0,1,0,1,0,0]\n",
    "\n",
    "d = 2**len(N)-1\n",
    "B = np.matrix(np.zeros((d, d)))\n",
    "\n",
    "for i in range(0, d):\n",
    "    A = coalitions[i]\n",
    "    S = subsets(A.split('+'))\n",
    "    coef = [1 if c in S else 0 for c in coalitions]\n",
    "    B[i] = coef\n",
    "\n",
    "pd.options.display.float_format = '{:,.0f}'.format\n",
    "pd.DataFrame(data=B, index=coalitions, columns=coalitions)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The **worth** of each coalition is determined by the characteristic function. In this example, the worth is represented as the sum of conversion ratios of each channel in a coalition:\n",
    "\n",
    "* Coalition S5 = Facebook+LinkedIn\n",
    "* v(S5) = Facebook (S1) + LinkedIn (S3) + Facebook+LinkedIn (S5)\n",
    "* v(S5) = 0.18 + 0.08 + 0.26\n",
    "* v(S5) = 0.52\n",
    "\n",
    "The coalition containing all players is known as the grand coalition ***<sup>v(N)</sup>***. The grand coalition's worth should be equal to the total payoff."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<div>\n",
       "<style scoped>\n",
       "    .dataframe tbody tr th:only-of-type {\n",
       "        vertical-align: middle;\n",
       "    }\n",
       "\n",
       "    .dataframe tbody tr th {\n",
       "        vertical-align: top;\n",
       "    }\n",
       "\n",
       "    .dataframe thead th {\n",
       "        text-align: right;\n",
       "    }\n",
       "</style>\n",
       "<table border=\"1\" class=\"dataframe\">\n",
       "  <thead>\n",
       "    <tr style=\"text-align: right;\">\n",
       "      <th></th>\n",
       "      <th>Coalition</th>\n",
       "      <th>Worth</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>v(S1)</th>\n",
       "      <td>Facebook</td>\n",
       "      <td>0.18</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>v(S2)</th>\n",
       "      <td>Google</td>\n",
       "      <td>0.04</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>v(S3)</th>\n",
       "      <td>LinkedIn</td>\n",
       "      <td>0.08</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>v(S4)</th>\n",
       "      <td>Facebook+Google</td>\n",
       "      <td>0.32</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>v(S5)</th>\n",
       "      <td>Facebook+LinkedIn</td>\n",
       "      <td>0.52</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>v(S6)</th>\n",
       "      <td>Google+LinkedIn</td>\n",
       "      <td>0.19</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>v(S7)</th>\n",
       "      <td>Facebook+Google+LinkedIn</td>\n",
       "      <td>1.00</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "                      Coalition  Worth\n",
       "v(S1)                  Facebook   0.18\n",
       "v(S2)                    Google   0.04\n",
       "v(S3)                  LinkedIn   0.08\n",
       "v(S4)           Facebook+Google   0.32\n",
       "v(S5)         Facebook+LinkedIn   0.52\n",
       "v(S6)           Google+LinkedIn   0.19\n",
       "v(S7)  Facebook+Google+LinkedIn   1.00"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# The product of the matrices coalition membership and coalition ratios\n",
    "# is the coalition worth - the result of the characteristic function 'v(S)'\n",
    "\n",
    "vS = np.dot(B, IR)\n",
    "vS = np.squeeze(np.asarray(vS))\n",
    "\n",
    "vSx = ['v({})'.format(lbl) for lbl in coalitions_lbl]\n",
    "pd.options.display.float_format = '{:,.2f}'.format\n",
    "pd.DataFrame({\n",
    "    'Coalition': coalitions,\n",
    "    'Worth': vS\n",
    "}, index=vSx)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Calculating the Shapley values\n",
    "\n",
    "Now that we know the worth of each coalition, the Shapley values can be calculated by taking the average of each channels marginal contribution to the game, accounting for all possible orderings. Specifically, the Shapley value gives us a way to distribute the worth of the grand coalition (total payoff) between the three channels.\n",
    "\n",
    "Facebook's Shapley value:\n",
    "\n",
    "| Order v(N)                  | Marginal contribution |\n",
    "| --------------------------- | --------------------- |\n",
    "| 1. Facebook+Google+LinkedIn | v(S1) = 0.18          |\n",
    "| 2. Facebook+LinkedIn+Google | v(S1) = 0.18          |\n",
    "| 3. Google+Facebook+LinkedIn | v(S4) - v(S2) = 0.28  |\n",
    "| 4. Google+LinkedIn+Facebook | v(S7) - v(S6) = 0.81  |\n",
    "| 5. LinkedIn+Facebook+Google | v(S5) - v(S3) = 0.44  |\n",
    "| 6. LinkedIn+Google+Facebook | v(S7) - v(S6) = 0.81  |\n",
    "| **Average contribution**    | 0.45                  |\n",
    "\n",
    "* In orders 1 and 2, Facebook is first to arrive so it receives its full contribution\n",
    "* In order 3, Facebook arrives after Google so its marginal contribution is the coalition containing both channels ***<sup>v(S4)</sup>*** <br>minus the coalition without Facebook ***<sup>v(S2)</sup>***\n",
    "* In orders 4 and 6, Facebook is last to arrive so its marginal contribution is the coalition containing all channels ***<sup>v(S7)</sup>*** <br>minus the coalition without Facebook ***<sup>v(S6)</sup>***\n",
    "* In order 5, Facebook arrives after LinkedIn so its marginal contribution is the coalition containing both channels ***<sup>v(S5)</sup>*** <br>minus the coalition without Facebook ***<sup>v(S3)</sup>***\n",
    "\n",
    "The Shapley values for all channels:\n",
    "\n",
    "| Order                       | Facebook              | Google                | LinkedIn              |\n",
    "| --------------------------- | --------------------- | --------------------- | --------------------- |\n",
    "| 1. Facebook+Google+LinkedIn | v(S1) = 0.18          | v(S4) - v(S1) = 0.14  | v(S7) - v(S4) = 0.68  |\n",
    "| 2. Facebook+LinkedIn+Google | v(S1) = 0.18          | v(S7) - v(S5) = 0.48  | v(S5) - v(S1) = 0.34  |\n",
    "| 3. Google+Facebook+LinkedIn | v(S4) - v(S2) = 0.28  | v(S2) = 0.04          | v(S7) - v(S4) = 0.68  |\n",
    "| 4. Google+LinkedIn+Facebook | v(S7) - v(S6) = 0.81  | v(S2) = 0.04          | v(S6) - v(S2) = 0.15  |\n",
    "| 5. LinkedIn+Facebook+Google | v(S5) - v(S3) = 0.44  | v(S7) - v(S5) = 0.48  | v(S3) = 0.08          |\n",
    "| 6. LinkedIn+Google+Facebook | v(S7) - v(S6) = 0.81  | v(S6) - v(S3) = 0.11  | v(S3) = 0.08          |\n",
    "| **Average contribution**    | 0.45                  | 0.215                 | 0.335                 |"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [],
   "source": [
    "from collections import defaultdict\n",
    "from math import factorial\n",
    "\n",
    "# Calculate the Shapley values - the average value of each channel's marginal contribution\n",
    "# to the grand coalition, taking into account all possible orderings.\n",
    "\n",
    "shapley = defaultdict(int)\n",
    "n = len(N)\n",
    "\n",
    "for i in N:\n",
    "    for A in coalitions:\n",
    "        S = A.split('+')\n",
    "        if i not in S:\n",
    "            k = len(S) # Cardinality of set |S|\n",
    "            Si = S\n",
    "            Si.append(i)\n",
    "            Si = '+'.join(sorted(Si))\n",
    "            # Weight = |S|!(n-|S|-1)!/n!\n",
    "            weight = (factorial(k) * factorial(n-k-1)) / factorial(n)\n",
    "            # Marginal contribution = v(S U {i})-v(S)\n",
    "            contrib = vS[coalitions.index(Si)] - vS[coalitions.index(A)]            \n",
    "            shapley[i] += weight * contrib\n",
    "    shapley[i] += vS[coalitions.index(i)]/n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<div>\n",
       "<style scoped>\n",
       "    .dataframe tbody tr th:only-of-type {\n",
       "        vertical-align: middle;\n",
       "    }\n",
       "\n",
       "    .dataframe tbody tr th {\n",
       "        vertical-align: top;\n",
       "    }\n",
       "\n",
       "    .dataframe thead th {\n",
       "        text-align: right;\n",
       "    }\n",
       "</style>\n",
       "<table border=\"1\" class=\"dataframe\">\n",
       "  <thead>\n",
       "    <tr style=\"text-align: right;\">\n",
       "      <th></th>\n",
       "      <th>Shapley value</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>Facebook</th>\n",
       "      <td>0.450</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>Google</th>\n",
       "      <td>0.215</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>LinkedIn</th>\n",
       "      <td>0.335</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "          Shapley value\n",
       "Facebook          0.450\n",
       "Google            0.215\n",
       "LinkedIn          0.335"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "pd.options.display.float_format = '{:,.3f}'.format\n",
    "pd.DataFrame({\n",
    "    'Shapley value': list(shapley.values())\n",
    "}, index=list(shapley.keys()))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.5"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}