5D Library › Algorithmic Marketing, Multi-Touch Shapley Attribution and Stochastic Control of Acquisition Funnels · 中文

Chapter 2 Shapley Values and Markov Removal Effects: Exact Allocations of an Inexact Question

The Shapley value of a cooperative game

In 1953 Shapley proposed a way of dividing the value of a cooperative game (Shapley 1953). Let the set of players be NN, and let the characteristic function v(S)v(S) give the value any coalition S⊆NS \subseteq N can create, with v(⌀)=0v(\varnothing) = 0. Player ii’s Shapley value is his marginal contribution averaged over all possible orders of joining:

ϕi(v)=∑S⊆N\{i}|S|!(n−|S|−1)!n![v(S∪{i})−v(S)].\phi_i(v) = \sum_{S \subseteq N \setminus \{i\}} \frac{|S|!\,(n – |S| – 1)!}{n!}\,\bigl[v(S \cup \{i\}) – v(S)\bigr].

It is the only allocation satisfying four axioms at once: efficiency (∑iϕi=v(N)\sum_i \phi_i = v(N)), symmetry (two players who contribute the same to every coalition get the same), null player (a player who adds nothing to any coalition gets nothing) and additivity (the allocation of a sum of games is the sum of the allocations). The SHAP method for explaining machine-learning predictions rests on the same definition (Lundberg and Lee 2017).

Treating channels as players and conversions as value gives Shapley attribution. Shao and Li proposed data-driven multi-touch attribution models at KDD in 2011, including a simple probabilistic model (Shao and Li 2011); Dalessandro, Perlich, Stitelman and Provost in 2012 wrote channel attribution explicitly as a Shapley value, and showed that, under simplifying assumptions such as negligible marginal effects of exposures beyond the second, Shao and Li’s probabilistic model gives, after rescaling, the same shares as the Shapley value (Dalessandro et al. 2012).

What “exact” means

The Shapley value is exact for a given vv. The program first shows this in a small three-channel game, then looks at what happens when vv is defined differently.

Calculation

# Shapley values for channel attribution. Part A: a three-channel game, showing that
# the answer depends on how v(S) is defined. Part B: the observational Shapley rule on
# the fictional journeys of p01, where v(S) = conversion rate of users whose exposure
# set is exactly S (estimated from the paths), credited per user relative to v(empty).
# With targeting (selection on intent) it inherits the bias; without, it is exact.
import itertools, math, random

# --- helpers repeated from earlier programs, so that this one runs on its own ---
CH = "SFDE"
P_HIGH = 0.20
EXPO = {"S": (0.60, 0.10), "F": (0.35, 0.30), "D": (0.50, 0.50), "E": (0.60, 0.15)}
BASE = (0.08, 0.005)                                   # (high intent, low intent)
LIFT = {"S": 0.010, "F": 0.030, "D": 0.008, "E": 0.012}
WHEN = {"S": (0.6, 1.0), "F": (0.0, 0.7), "D": (0.0, 0.5), "E": (0.2, 1.0)}

def user(rng, sel=1.0):
    """One journey: (intent, channels in time order, converted)."""
    hi = rng.random() < P_HIGH
    touches = []
    for c in CH:
        p_hi, p_lo = EXPO[c]
        p = p_lo + sel * (p_hi - p_lo) if hi else p_lo   # sel = 0: no selection
        if rng.random() < p:
            touches.append((rng.uniform(*WHEN[c]), c))
    path = [c for _, c in sorted(touches)]
    p_conv = BASE[0 if hi else 1] + sum(LIFT[c] for c in path)
    return hi, path, rng.random() < p_conv

def truth(n, sel=1.0):
    """Expected incremental conversions per channel (exact, from the model)."""
    out = {}
    for c in CH:
        p_hi, p_lo = EXPO[c]
        expo = P_HIGH * (p_lo + sel * (p_hi - p_lo)) + (1 - P_HIGH) * p_lo
        out[c] = n * expo * LIFT[c]
    return out

def shares(d):
    tot = sum(d.values())
    return {c: d[c] / tot for c in CH}
# --- end of repeated helpers ---

def shapley(players, v):
    n, phi = len(players), {}
    for i in players:
        rest, s = [p for p in players if p != i], 0.0
        for k in range(n):
            w = math.factorial(k) * math.factorial(n - k - 1) / math.factorial(n)
            for T in itertools.combinations(rest, k):
                s += w * (v(frozenset(T) | {i}) - v(frozenset(T)))
        phi[i] = s
    return phi

def observational(data):
    """Total credit per channel: each user with exposure set S gets the Shapley
    split of v(S) - v(empty) over the members of S, v = empirical rate by exact set."""
    cnt, conv = {}, {}
    for _, path, c in data:
        S = frozenset(path); cnt[S] = cnt.get(S, 0) + 1; conv[S] = conv.get(S, 0) + c
    rate = {S: conv[S] / cnt[S] for S in cnt}
    v = lambda T: rate.get(T, 0.0) - rate[frozenset()]
    credit = {c: 0.0 for c in CH}
    for S, m in cnt.items():
        if S:
            for c, x in shapley(sorted(S), v).items():
                credit[c] += m * x
    return credit

if __name__ == "__main__":
    print("A. three channels; v = conversions per 1,000 users exposed")
    games = {"additive": {"": 0, "a": 10, "b": 4, "c": 2, "ab": 14, "ac": 12, "bc": 6,
                          "abc": 16},
             "a and b only work together": {"": 0, "a": 0, "b": 0, "c": 2, "ab": 12,
                                            "ac": 2, "bc": 2, "abc": 14}}
    for name, g in games.items():
        v = lambda T, g=g: g["".join(sorted(T))]
        phi = shapley(["a", "b", "c"], v)
        print(f"   {name:28s} " + "  ".join(f"{k} {x:5.2f}" for k, x in phi.items())
              + f"  (sum {sum(phi.values()):.0f} = v(abc))")
    print("B. observational Shapley on the fictional journeys of p01 (share of credit)")
    names = {"S": "Search", "F": "Social", "D": "Display", "E": "Email"}
    res = []
    for sel in (1.0, 0.0):
        rng = random.Random(2026)
        data = [user(rng, sel) for _ in range(200_000)]
        cr, tr = observational(data), truth(200_000, sel)
        res.append((shares(cr), shares(tr), sum(cr.values()), sum(tr.values())))
    print("               targeted (selection on intent)    untargeted")
    print("   channel        Shapley      truth            Shapley      truth")
    for c in CH:
        print(f"   {names[c]:8s}       {res[0][0][c]:6.1%}     {res[0][1][c]:6.1%}"
              f"            {res[1][0][c]:6.1%}     {res[1][1][c]:6.1%}")
    mae = [sum(abs(r[0][c] - r[1][c]) for c in CH) / len(CH) for r in res]
    print(f"   mean abs. error  {mae[0]:5.1%}                          {mae[1]:5.1%}")
    print(f"   conversions credited to ads {res[0][2]:,.0f} (true {res[0][3]:,.0f});"
          f" untargeted {res[1][2]:,.0f} (true {res[1][3]:,.0f})")
# A. three channels; v = conversions per 1,000 users exposed
#    additive                     a 10.00  b  4.00  c  2.00  (sum 16 = v(abc))
#    a and b only work together   a  6.00  b  6.00  c  2.00  (sum 14 = v(abc))
# B. observational Shapley on the fictional journeys of p01 (share of credit)
#                targeted (selection on intent)    untargeted
#    channel        Shapley      truth            Shapley      truth
#    Search          27.0%      11.0%              6.2%       6.3%
#    Social          32.3%      51.2%             56.7%      57.0%
#    Display         14.7%      22.0%             29.4%      25.3%
#    Email           26.0%      15.8%              7.7%      11.4%
#    mean abs. error  13.1%                           2.0%
#    conversions credited to ads 5,994 (true 3,636); untargeted 3,160 (true 3,160)

In part A, the first game is additive: each channel brings a fixed number of conversions on its own and the numbers simply add in combination, so the Shapley values are the individual contributions (10, 4, 2). In the second game a and b work only together: alone each is worth 0, together 12. The Shapley value splits the 12 equally, 6 each to a and b, and c still gets 2. This is how the Shapley value treats synergy: an interaction effect is divided equally among the members of the interaction. That is a consequence of the axioms, not an empirical finding; another equally reasonable rule (for example, splitting in proportion to individual contributions) would give a completely different answer.

Part B applies the Shapley value to the fictional users of Chapter 1, in the manner of Dalessandro and co-authors: the conversion rate of users whose exposure set is exactly SS is taken as v(S)v(S) (minus the rate of those never exposed), each user’s v(S)−v(⌀)v(S) – v(\varnothing) is divided among the channels he saw by the Shapley value, and the results are summed. With targeting, the Shapley shares are off by 13.1 percentage points: search gets 27.0 % (true 11.0 %), social 32.3 % (true 51.2 %) — better than last click, but of the same order; it credits 5,994 conversions to ads when the true incrementality is 3,636. When the same world is made untargeted (exposure to each channel unrelated to intent), the Shapley error falls to 2.0 points, and the conversions it credits to ads almost equal the true incrementality (3,160 against 3,160; in a model without selection and with additive lifts the two are equal in expectation). The only difference is whether the data contain selection bias.

Note

Observational Shapley values inherit the selection bias of Chapter 1. Taking “the conversion rate of people with exposure set SS” as v(S)v(S) amounts to assuming that exposure sets are randomly assigned. Dalessandro and co-authors themselves state that interpreting such parameters as causal effects requires conditions such as no unmeasured confounding and positivity, which observational advertising data are likely to violate, and their empirical section explicitly makes no strict causal interpretation (Dalessandro et al. 2012). “Shapley values are exact multi-touch attribution” should therefore read: the Shapley value implements a set of allocation axioms exactly; when v(S)v(S) comes from randomised experiments or a known causal model, it allocates causal increments; when v(S)v(S) is estimated from observed paths, it allocates correlation.

Absorbing Markov chains and the removal effect

Another family of methods treats user paths as a stochastic process. Anderl, Becker, von Wangenheim and Schumann (2016) modelled paths as first- and higher-order Markov walks and compared attribution results on four large datasets from different industries, each with at least seven online channels; they found results very different from heuristics such as last click, and identified channel-specific carryover and cross-channel spillover effects (Anderl et al. 2016).

The first-order version is built as follows. The states are “start”, the channels, “conversion” and “null”, the last two absorbing. Transition probabilities are estimated from the path data, and the standard absorbing-chain computation gives the probability PP that a walk from “start” is eventually absorbed in “conversion” (Book 6 derived the fundamental matrix of an absorbing chain, which is not repeated here). The removal effect of channel cc is

REc=1−P(without c)P,\mathrm{RE}_c = 1 – \frac{P(\text{without } c)}{P},

where “removing” a channel sends every path that reaches it to “null”. The removal effects usually do not sum to 1 and are normalised in practice.

Calculation

# First-order Markov attribution (Anderl et al. 2016): states start, channels,
# conversion, null; P(conv) from the absorbing chain; removal effect of channel c =
# 1 - P(conv | c removed) / P(conv), where "removed" sends every visit to c to null.
# Shares = removal effects normalised to 1. Compared with exact-set Shapley on (A) the
# journeys of p01 and (B) a fictional untargeted world with a Social x Search synergy
# and a high-reach Display channel that does nothing.
import itertools, math, random

# --- helpers repeated from earlier programs, so that this one runs on its own ---
CH = "SFDE"
P_HIGH = 0.20
EXPO = {"S": (0.60, 0.10), "F": (0.35, 0.30), "D": (0.50, 0.50), "E": (0.60, 0.15)}
BASE = (0.08, 0.005)                                   # (high intent, low intent)
LIFT = {"S": 0.010, "F": 0.030, "D": 0.008, "E": 0.012}
WHEN = {"S": (0.6, 1.0), "F": (0.0, 0.7), "D": (0.0, 0.5), "E": (0.2, 1.0)}

def user(rng, sel=1.0):
    """One journey: (intent, channels in time order, converted)."""
    hi = rng.random() < P_HIGH
    touches = []
    for c in CH:
        p_hi, p_lo = EXPO[c]
        p = p_lo + sel * (p_hi - p_lo) if hi else p_lo   # sel = 0: no selection
        if rng.random() < p:
            touches.append((rng.uniform(*WHEN[c]), c))
    path = [c for _, c in sorted(touches)]
    p_conv = BASE[0 if hi else 1] + sum(LIFT[c] for c in path)
    return hi, path, rng.random() < p_conv

def truth(n, sel=1.0):
    """Expected incremental conversions per channel (exact, from the model)."""
    out = {}
    for c in CH:
        p_hi, p_lo = EXPO[c]
        expo = P_HIGH * (p_lo + sel * (p_hi - p_lo)) + (1 - P_HIGH) * p_lo
        out[c] = n * expo * LIFT[c]
    return out

def shares(d):
    tot = sum(d.values())
    return {c: d[c] / tot for c in CH}

def shapley(players, v):
    n, phi = len(players), {}
    for i in players:
        rest, s = [p for p in players if p != i], 0.0
        for k in range(n):
            w = math.factorial(k) * math.factorial(n - k - 1) / math.factorial(n)
            for T in itertools.combinations(rest, k):
                s += w * (v(frozenset(T) | {i}) - v(frozenset(T)))
        phi[i] = s
    return phi

def observational(data):
    """Total credit per channel: each user with exposure set S gets the Shapley
    split of v(S) - v(empty) over the members of S, v = empirical rate by exact set."""
    cnt, conv = {}, {}
    for _, path, c in data:
        S = frozenset(path); cnt[S] = cnt.get(S, 0) + 1; conv[S] = conv.get(S, 0) + c
    rate = {S: conv[S] / cnt[S] for S in cnt}
    v = lambda T: rate.get(T, 0.0) - rate[frozenset()]
    credit = {c: 0.0 for c in CH}
    for S, m in cnt.items():
        if S:
            for c, x in shapley(sorted(S), v).items():
                credit[c] += m * x
    return credit
# --- end of repeated helpers ---

def chain(data):
    cnt = {}
    for _, path, conv in data:
        seq = ["start"] + list(path) + ["conv" if conv else "null"]
        for a, b in zip(seq, seq[1:]):
            row = cnt.setdefault(a, {}); row[b] = row.get(b, 0) + 1
    return {a: {b: k / sum(r.values()) for b, k in r.items()} for a, r in cnt.items()}

def p_conv(P, removed=None):
    val = {s: 0.0 for s in P}; val["conv"], val["null"] = 1.0, 0.0
    for _ in range(200):                         # value iteration on transient states
        for s in P:
            val[s] = 0.0 if s == removed else sum(p * val[b] for b, p in P[s].items())
    return val["start"]

def removal(data, chans):
    P = chain(data); base = p_conv(P)
    re = {c: 1 - p_conv(P, c) / base for c in chans}
    return re, {c: re[c] / sum(re.values()) for c in chans}

def synergy_user(rng):
    seen = [c for c, p in (("D", 0.80), ("F", 0.30), ("S", 0.30)) if rng.random() < p]
    order = {"D": rng.random() * 0.5, "F": rng.random() * 0.7,
             "S": 0.5 + rng.random() / 2}
    path = sorted(seen, key=order.get)
    p = 0.02 + (0.06 if "F" in seen and "S" in seen else 0.0)
    return None, path, rng.random() < p

if __name__ == "__main__":
    names = {"S": "Search", "F": "Social", "D": "Display", "E": "Email"}
    rng = random.Random(2026); data = [user(rng) for _ in range(200_000)]
    re, sh = removal(data, "SFDE"); sp, st = shares(observational(data)), shares(
        truth(200_000))
    print("A. journeys of p01 (targeted)  removal effect  Markov share  Shapley  truth")
    for c in "SFDE":
        print(f"   {names[c]:8s}                       {re[c]:6.1%}       {sh[c]:6.1%}"
              f"   {sp[c]:6.1%}  {st[c]:6.1%}")
    print(f"   sum of removal effects {sum(re.values()):.2f} (they need not add to 1)")
    mm = sum(abs(sh[c] - st[c]) for c in "SFDE") / 4
    ms = sum(abs(sp[c] - st[c]) for c in "SFDE") / 4
    print(f"   mean absolute error of shares: Markov {mm:.1%}, Shapley {ms:.1%}")
    rng = random.Random(7); data = [synergy_user(rng) for _ in range(200_000)]
    re, sh = removal(data, "DFS"); sp = shares(observational(data))
    conv = sum(d[2] for d in data)
    inc = 200_000 * 0.30 * 0.30 * 0.06
    print(f"B. synergy world: {conv:,} conversions, about {inc:,.0f} caused by ads"
          f" (all by Social x Search)")
    print("   channel   removal effect   Markov share   Shapley share")
    for c in "DFS":
        print(f"   {names[c]:8s}      {re[c]:6.1%}         {sh[c]:6.1%}"
              f"         {sp[c]:6.1%}")
# A. journeys of p01 (targeted)  removal effect  Markov share  Shapley  truth
#    Search                          38.9%        23.9%    27.0%   11.0%
#    Social                          38.6%        23.8%    32.3%   51.2%
#    Display                         49.5%        30.5%    14.7%   22.0%
#    Email                           35.4%        21.8%    26.0%   15.8%
#    sum of removal effects 1.62 (they need not add to 1)
#    mean absolute error of shares: Markov 13.7%, Shapley 13.1%
# B. synergy world: 5,021 conversions, about 1,080 caused by ads (all by Social x Search)
#    channel   removal effect   Markov share   Shapley share
#    Display        75.4%          51.1%          -4.2%
#    Social         28.9%          19.6%          46.5%
#    Search         43.3%          29.3%          57.7%

In part A, in the targeted world of Chapter 1, the removal effects sum to 1.62, and the normalised shares are off by 13.7 points, close to the 13.1 of observational Shapley; but the errors go in different directions: the Markov method gives most to display (30.5 %, true 22.0 %), because display has the widest reach and opens many paths, while Shapley gives more to social and search.

Part B uses an untargeted world built to isolate synergy. Display reaches 80 % of users and does nothing; social and search each reach 30 %, do nothing alone, and together raise the conversion probability by 6 points. About 1,080 conversions are caused by ads, all by the social–search combination, so the true incremental credit should be split equally between them (50 % each) with zero for display. Shapley gives social 46.5 %, search 57.7 % and display −4.2 % (sampling noise around a true zero), close to the truth. The Markov removal effect gives 51.1 % of the credit to display, which does nothing at all. The reason lies in the definition of removal: display is on most paths, so “removing” it cuts off every later social and search touch on those paths, and the first-order chain credits a frequent early channel with the work of the channels that follow it. Figure 1 shows both worlds side by side.

Left: in the targeted world of Chapter 1, the true incremental shares and the shares given by last click, observational Shapley and the Markov removal effect. Right: in an untargeted world in which only the social–search combination works, the shares given by the three (illustrative parameters, simulated data).

Evidence

Consequences and corrections of Shapley values in ad markets. Berman used a game-theoretic model to analyse how attribution rules shape incentives for advertisers and publishers: last click over-incentivises ad exposures and often lowers advertisers’ profits; Shapley attribution raises advertiser profits relative to last click, at the expense of publisher profits and allocation efficiency, and more sophisticated attribution lowers market prices (Berman 2018). Singal, Besbes, Desir, Goyal and Iyengar built an axiomatic framework for attribution, showed where the classical Shapley value falls short in online advertising, proposed the “counterfactual adjusted Shapley value”, and proved that in a model in which users move through the funnel as a Markov chain it equals an adjusted “unique-uniform” attribution (Singal et al. 2022). Li and Kannan proposed an attribution model with carryover and spillover between channels and tested it with a field experiment (Li and Kannan 2014).

The boundaries of the two methods

Both methods are deterministic allocations of given data, each with its own implicit counterfactual. The Shapley counterfactual is “conversions with only the channels in SS switched on”, estimated from people whose exposure set is exactly SS; the removal-effect counterfactual is “every path after the channel is cut off”, generated by the first-order Markov assumption. The former allocates synergy according to its axioms but inherits selection bias under targeting, and requires conversion rates for 2n2^n coalitions, many of which have few users when there are many channels; the latter is simple to compute and reflects path order, but can badly overstate wide-reach, early channels. Neither can replace a randomised experiment. A sensible use is to calibrate the incrementality of the main channels with randomised holdouts, to use Shapley or Markov methods for descriptive bookkeeping between experiments, and to state in reports that they allocate correlation.

Summary

The Shapley value is the only allocation satisfying efficiency, symmetry, null player and additivity, and under synergy it splits the interaction effect equally among participants; its meaning depends entirely on the characteristic function v(S)v(S). When v(S)v(S) is estimated from observed paths, it inherits the selection bias of targeted delivery: in the fictional world of Chapter 1, its share error is 13.1 points with targeting and 2.0 points without. The Markov removal effect has a similar error in that world (13.7), but in a world in which only two channels work together it gives more than half the credit to a wide-reach channel that does nothing. “Exact multi-touch attribution” in the author’s framework should be qualified as “exact axiomatic allocation”; the end point of attribution is the incrementality experiment, not a more refined allocation formula.

Hypothesis · not established · Removal effects favour wide-reach early channels

The author’s hypothesis (not established): in real multichannel data, the share the first-order Markov removal effect gives to wide-reach channels that often open paths (such as display and feeds) is higher than the same channel’s incremental share in randomised holdouts, and the overstatement grows with the channel’s reach. What result would show it to be wrong: in a pre-registered collection (assembled by independent researchers) of channels with both Markov attribution and holdout experiments, the 95 % confidence interval for the slope of “removal-effect share minus incremental share” on reach contains zero or is negative.

References

Anderl, Eva, Ingo Becker, Florian von Wangenheim, and Jan Hendrik Schumann. 2016. “Mapping the Customer Journey: Lessons Learned from Graph-Based Online Attribution Modeling.” International Journal of Research in Marketing 33 (3): 457–74. https://doi.org/10.1016/j.ijresmar.2016.03.001.
Berman, Ron. 2018. “Beyond the Last Touch: Attribution in Online Advertising.” Marketing Science 37 (5): 771–92. https://doi.org/10.1287/mksc.2018.1104.
Dalessandro, Brian, Claudia Perlich, Ori Stitelman, and Foster Provost. 2012. “Causally Motivated Attribution for Online Advertising.” Proceedings of the Sixth International Workshop on Data Mining for Online Advertising and Internet Economy (ADKDD ’12). https://doi.org/10.1145/2351356.2351363.
Li, Hongshuang (Alice), and P. K. Kannan. 2014. “Attributing Conversions in a Multichannel Online Marketing Environment: An Empirical Model and a Field Experiment.” Journal of Marketing Research 51 (1): 40–56.
Lundberg, Scott M., and Su-In Lee. 2017. “A Unified Approach to Interpreting Model Predictions.” Advances in Neural Information Processing Systems 30 (NIPS 2017), 4765–74.
Shao, Xuhui, and Lexin Li. 2011. “Data-Driven Multi-Touch Attribution Models.” Proceedings of the 17th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD ’11), 258–64.
Shapley, Lloyd S. 1953. “A Value for n-Person Games.” In Contributions to the Theory of Games, Volume II, edited by Harold W. Kuhn and Albert W. Tucker. Annals of Mathematics Studies 28. Princeton University Press.
Singal, Raghav, Omar Besbes, Antoine Desir, Vineet Goyal, and Garud Iyengar. 2022. “Shapley Meets Uniform: An Axiomatic Framework for Attribution in Online Advertising.” Management Science 68 (10): 7457–79. https://doi.org/10.1287/mnsc.2021.4263.

Fan, Y. (2026). Algorithmic Marketing, Multi-Touch Shapley Attribution and Stochastic Control of Acquisition Funnels: From Thompson Sampling Bandits and Absorbing Markov Chains to BG/NBD Customer Lifetime Value, Read Beside the Strategic Dispositions of the Sunzi [算法营销、多触点沙普利归因与获客漏斗的随机控制] (Version 1.0.0). 5D Library. https://doi.org/10.5281/zenodo.23836264 · Licensed under Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International (CC BY-NC-ND 4.0).