5D Library › 算法营销、多触点沙普利归因与获客漏斗的随机控制 · English

第二章 沙普利值与马尔可夫移除效应:精确的分配,不精确的问题

合作博弈中的沙普利值

沙普利(Shapley)1953 年为合作博弈提出了一种分配方案 (Shapley 1953)。设参与者集合为 NN,特征函数 v(S)v(S) 给出任一联盟 S⊆NS \subseteq N 能够创造的价值,v(⌀)=0v(\varnothing) = 0。参与者 ii 的沙普利值是他对所有可能的「加入顺序」的平均边际贡献:

ϕ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].

它是唯一同时满足四条公理的分配:效率(∑iϕi=v(N)\sum_i \phi_i = v(N))、对称(对所有联盟贡献相同的两人分得相同)、零贡献(对任何联盟都没有边际贡献的人分得零)与可加(两个博弈之和的分配等于分配之和)。机器学习中解释模型预测的 SHAP 方法也建立在同一定义上 (Lundberg and Lee 2017)。

把渠道看作参与者、把转化看作价值,就得到沙普利归因。邵(Shao)与李(Li)2011 年在 KDD 会议上提出了数据驱动的多触点归因,包括一个简单的概率模型 (Shao and Li 2011);达莱桑德罗(Dalessandro)、佩利希(Perlich)、施蒂特尔曼(Stitelman)与普罗沃斯特(Provost)2012 年明确地把渠道归因写成沙普利值,并指出邵与李的概率模型在「第二次以后的曝光边际效应可以忽略」等简化假设下、经过缩放后与沙普利值给出相同的份额 (Dalessandro et al. 2012)。

「精确」指的是什么

沙普利值对给定的 vv 是精确的。下面的程序先在一个三渠道的小博弈中演示这一点,再看 vv 换了定义之后发生什么。

推导

# 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)

A 部分的第一个博弈是可加的:每个渠道单独带来固定的转化,组合时简单相加,沙普利值就是各自的单独贡献(10、4、2)。第二个博弈中 a 与 b 只有在一起时才有作用:单独都是 0,合在一起是 12。沙普利值把这 12 平分给 a 与 b 各 6,c 仍得 2。这正是沙普利值处理协同的方式:交互效应在参与交互的成员之间平均分配。这是公理的推论,不是经验结论;另一种同样合理的规则(例如按单独贡献的比例分配)会给出完全不同的答案。

B 部分把沙普利值用在第一章的虚构用户上。做法与达莱桑德罗等人的写法一致:把「曝光集合恰好为 SS 的用户的转化率」当作 v(S)v(S)(减去从未曝光者的转化率),对每个用户把他的 v(S)−v(⌀)v(S) – v(\varnothing) 按沙普利值分给他看到的渠道,再汇总。有定向时,沙普利值的份额误差为 13.1 个百分点:搜索得 27.0%(真实 11.0%),社交得 32.3%(真实 51.2%),比末次点击好一些,但仍是同一量级;它记在广告名下的转化是 5,994 次,真实增量只有 3,636 次。把同一个世界改成完全不定向(每个渠道的曝光与意向无关),沙普利值的误差降到 2.0 个百分点,记在广告名下的转化几乎等于真实增量(3,160 对 3,160;在无选择、可加的模型中二者期望相等)。差别只在于数据中有没有选择偏差。

注

观测沙普利值继承了第一章的选择偏差。 用「曝光集合为 SS 的人的转化率」作 v(S)v(S),等于假设曝光集合是随机分配的。达莱桑德罗等人自己写明:要把这些参数解释为因果效应,需要没有未测量的混杂与正值性等条件,而广告的观测数据很可能违反这些条件;他们的实证部分也明确没有作严格的因果解释 (Dalessandro et al. 2012)。所以「沙普利值是精确的多触点归因」应改为:沙普利值精确地实现了一组分配公理;当 v(S)v(S) 由随机实验或已知的因果模型给出时,它分配的是因果增量;当 v(S)v(S) 由观测路径估计时,它分配的是相关性。

吸收马尔可夫链与移除效应

另一类方法把用户路径看作随机过程。安德尔(Anderl)、贝克尔(Becker)、冯·旺根海姆(von Wangenheim)与舒曼(Schumann)2016 年把路径建模为一阶与高阶马尔可夫游走,用来自不同行业、各至少有七个在线渠道的四个大型数据集比较了归因结果,发现它与末次点击等启发式规则差别很大,并识别出渠道的自我延续(carryover)与跨渠道溢出(spillover)效应 (Anderl et al. 2016)。

一阶版本的构造如下。状态是「开始」、各渠道、「转化」与「未转化」,后两者是吸收态。从路径数据估计转移概率,用吸收链的标准计算得到从「开始」出发最终被「转化」吸收的概率 PP(第 6 本已推导过吸收链的基本矩阵,这里不重复)。渠道 cc 的移除效应定义为

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

其中「移除」指凡是走到 cc 的路径都改为走向「未转化」。各渠道的移除效应之和通常不等于 1,实际使用时再按比例归一化。

推导

# 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%

A 部分在第一章的定向世界中,移除效应之和为 1.62,归一化后的份额误差为 13.7 个百分点,与观测沙普利值的 13.1 相近,但两者的错误方向不同:马尔可夫方法给展示最多(30.5%,真实 22.0%),因为展示覆盖面最广、在许多路径的开头;沙普利值给社交与搜索更多。

B 部分换一个不定向的世界,专门看协同。展示覆盖 80% 的用户但没有任何作用;社交与搜索各覆盖 30%,单独都没有作用,同时看到两者时转化概率提高 6 个百分点。约 1,080 次转化是广告造成的,全部来自社交与搜索的组合,所以真实增量应当在二者之间平分(各 50%),展示为零。沙普利值给社交 46.5%、搜索 57.7%、展示 −4.2%(抽样噪声,真值为零),接近真相。马尔可夫移除效应却把 51.1% 的功劳给了毫无作用的展示。原因在于移除的定义:展示出现在大多数路径上,把它「移除」等于截断了这些路径中所有后续的社交与搜索接触,于是一阶链把后面渠道的作用记到了前面这个高频渠道头上。图 1 并排画出了两个世界的结果。

左:第一章的定向世界中,真实增量份额与末次点击、观测沙普利值、马尔可夫移除效应的份额。右:一个不定向、只有社交与搜索协同起作用的世界中,三者的份额(示意参数,数据为模拟)。

证据

沙普利值在广告市场中的后果与修正。 伯曼(Berman)用博弈论模型分析了归因规则对广告主与发布商的激励:末次点击会过度激励广告曝光,常常使广告主利润下降;沙普利值归因比末次点击更能提高广告主的利润,代价是发布商的利润与分配效率,越精细的归因方法越压低市场价格 (Berman 2018)。辛加尔(Singal)、贝斯贝斯(Besbes)、德西尔(Desir)、戈亚尔(Goyal)与延加尔(Iyengar)为归因建立了公理框架,指出经典沙普利值在在线广告中有缺陷,提出「反事实调整的沙普利值」,并证明在一个用户沿漏斗作马尔可夫移动的模型中,它等于一种调整后的「唯一—均匀」归因 (Singal et al. 2022)。李(Li)与卡南(Kannan)则提出了一个考虑渠道间溢出与延续的归因模型,并以实地实验检验 (Li and Kannan 2014)。

两种方法的边界

两种方法都是对给定数据的确定性分配,各有自己的隐含反事实。沙普利值的反事实是「只开 SS 中的渠道时的转化」,它从曝光集合恰为 SS 的人身上估计;移除效应的反事实是「某渠道之后的路径全部中断」,它由一阶马尔可夫假设生成。前者在协同下的分配合乎公理,但在定向下继承选择偏差,并且要估计 2n2^n 个联盟的转化率,渠道多时许多联盟的样本很少;后者计算简单、能体现路径顺序,但在高覆盖、早出现的渠道上可能严重高估。两者都不能代替随机实验。合理的用法是:用随机持出实验校准少数主要渠道的增量,用沙普利值或马尔可夫方法在实验之间做描述性的记账,并在报表中写明它们分配的是相关性。

本章小结

沙普利值是唯一满足效率、对称、零贡献与可加四条公理的分配,在协同时把交互效应平分给参与者;它的含义完全取决于特征函数 v(S)v(S)。用观测路径估计 v(S)v(S) 时,它继承了定向投放的选择偏差:在第一章的虚构世界中,有定向时份额误差 13.1 个百分点,无定向时 2.0 个百分点。马尔可夫移除效应在同一世界中误差相近(13.7),但在一个只有两个渠道协同起作用的世界里,它把一半以上的功劳给了一个毫无作用的高覆盖渠道。作者框架中「精确的多触点归因」应限定为「精确的公理化分配」;归因的终点是增量实验,不是更精细的分配公式。

假说 · 尚未验证 · 移除效应偏向高覆盖的早期渠道

作者的假说(尚未确立): 在真实的多渠道数据中,一阶马尔可夫移除效应给予高覆盖、常出现在路径开头的渠道(如展示与信息流)的份额,高于同一渠道在随机持出实验中的增量份额,且高估幅度随该渠道的覆盖率上升而增大。什么样的结果能证明它是错的: 在事先登记的一组同时有马尔可夫归因与持出实验的渠道中(由独立研究者汇集),移除效应份额减去增量份额之差对覆盖率的回归斜率,其 95% 置信区间包含零或为负。

参考文献

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).