5D Library › 算法营销、多触点沙普利归因与获客漏斗的随机控制 · English
第二章 沙普利值与马尔可夫移除效应:精确的分配,不精确的问题
合作博弈中的沙普利值
沙普利(Shapley)1953 年为合作博弈提出了一种分配方案 (Shapley 1953)。设参与者集合为 ,特征函数 给出任一联盟 能够创造的价值,。参与者 的沙普利值是他对所有可能的「加入顺序」的平均边际贡献:
它是唯一同时满足四条公理的分配:效率()、对称(对所有联盟贡献相同的两人分得相同)、零贡献(对任何联盟都没有边际贡献的人分得零)与可加(两个博弈之和的分配等于分配之和)。机器学习中解释模型预测的 SHAP 方法也建立在同一定义上 (Lundberg and Lee 2017)。
把渠道看作参与者、把转化看作价值,就得到沙普利归因。邵(Shao)与李(Li)2011 年在 KDD 会议上提出了数据驱动的多触点归因,包括一个简单的概率模型 (Shao and Li 2011);达莱桑德罗(Dalessandro)、佩利希(Perlich)、施蒂特尔曼(Stitelman)与普罗沃斯特(Provost)2012 年明确地把渠道归因写成沙普利值,并指出邵与李的概率模型在「第二次以后的曝光边际效应可以忽略」等简化假设下、经过缩放后与沙普利值给出相同的份额 (Dalessandro et al. 2012)。
「精确」指的是什么
沙普利值对给定的 是精确的。下面的程序先在一个三渠道的小博弈中演示这一点,再看 换了定义之后发生什么。
推导
# 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 部分把沙普利值用在第一章的虚构用户上。做法与达莱桑德罗等人的写法一致:把「曝光集合恰好为 的用户的转化率」当作 (减去从未曝光者的转化率),对每个用户把他的 按沙普利值分给他看到的渠道,再汇总。有定向时,沙普利值的份额误差为 13.1 个百分点:搜索得 27.0%(真实 11.0%),社交得 32.3%(真实 51.2%),比末次点击好一些,但仍是同一量级;它记在广告名下的转化是 5,994 次,真实增量只有 3,636 次。把同一个世界改成完全不定向(每个渠道的曝光与意向无关),沙普利值的误差降到 2.0 个百分点,记在广告名下的转化几乎等于真实增量(3,160 对 3,160;在无选择、可加的模型中二者期望相等)。差别只在于数据中有没有选择偏差。
注
观测沙普利值继承了第一章的选择偏差。 用「曝光集合为 的人的转化率」作 ,等于假设曝光集合是随机分配的。达莱桑德罗等人自己写明:要把这些参数解释为因果效应,需要没有未测量的混杂与正值性等条件,而广告的观测数据很可能违反这些条件;他们的实证部分也明确没有作严格的因果解释 (Dalessandro et al. 2012)。所以「沙普利值是精确的多触点归因」应改为:沙普利值精确地实现了一组分配公理;当 由随机实验或已知的因果模型给出时,它分配的是因果增量;当 由观测路径估计时,它分配的是相关性。
吸收马尔可夫链与移除效应
另一类方法把用户路径看作随机过程。安德尔(Anderl)、贝克尔(Becker)、冯·旺根海姆(von Wangenheim)与舒曼(Schumann)2016 年把路径建模为一阶与高阶马尔可夫游走,用来自不同行业、各至少有七个在线渠道的四个大型数据集比较了归因结果,发现它与末次点击等启发式规则差别很大,并识别出渠道的自我延续(carryover)与跨渠道溢出(spillover)效应 (Anderl et al. 2016)。
一阶版本的构造如下。状态是「开始」、各渠道、「转化」与「未转化」,后两者是吸收态。从路径数据估计转移概率,用吸收链的标准计算得到从「开始」出发最终被「转化」吸收的概率 (第 6 本已推导过吸收链的基本矩阵,这里不重复)。渠道 的移除效应定义为
其中「移除」指凡是走到 的路径都改为走向「未转化」。各渠道的移除效应之和通常不等于 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)。
两种方法的边界
两种方法都是对给定数据的确定性分配,各有自己的隐含反事实。沙普利值的反事实是「只开 中的渠道时的转化」,它从曝光集合恰为 的人身上估计;移除效应的反事实是「某渠道之后的路径全部中断」,它由一阶马尔可夫假设生成。前者在协同下的分配合乎公理,但在定向下继承选择偏差,并且要估计 个联盟的转化率,渠道多时许多联盟的样本很少;后者计算简单、能体现路径顺序,但在高覆盖、早出现的渠道上可能严重高估。两者都不能代替随机实验。合理的用法是:用随机持出实验校准少数主要渠道的增量,用沙普利值或马尔可夫方法在实验之间做描述性的记账,并在报表中写明它们分配的是相关性。
本章小结
沙普利值是唯一满足效率、对称、零贡献与可加四条公理的分配,在协同时把交互效应平分给参与者;它的含义完全取决于特征函数 。用观测路径估计 时,它继承了定向投放的选择偏差:在第一章的虚构世界中,有定向时份额误差 13.1 个百分点,无定向时 2.0 个百分点。马尔可夫移除效应在同一世界中误差相近(13.7),但在一个只有两个渠道协同起作用的世界里,它把一半以上的功劳给了一个毫无作用的高覆盖渠道。作者框架中「精确的多触点归因」应限定为「精确的公理化分配」;归因的终点是增量实验,不是更精细的分配公式。
假说 · 尚未验证 · 移除效应偏向高覆盖的早期渠道
作者的假说(尚未确立): 在真实的多渠道数据中,一阶马尔可夫移除效应给予高覆盖、常出现在路径开头的渠道(如展示与信息流)的份额,高于同一渠道在随机持出实验中的增量份额,且高估幅度随该渠道的覆盖率上升而增大。什么样的结果能证明它是错的: 在事先登记的一组同时有马尔可夫归因与持出实验的渠道中(由独立研究者汇集),移除效应份额减去增量份额之差对覆盖率的回归斜率,其 95% 置信区间包含零或为负。
参考文献
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).