博弈论在零售业务中的应用

在零售业的供应链管理中，我们经常会遇到一些资源分配问题，例如商品的供需平衡，销售利润分摊，运输成本分摊等。常见的分配方式有平均分配和按权重(比例)分配。在某些应用场景下，我们需要保证分配方案的"公平性"，那么如何科学地定义公平性，又如何计算公平的分配方案? 本文从合作博弈论的角度思考如何解决这些实际问题。

合作博弈

考虑这样的的销售场景：商家从它的供应商采购商品，顾客在线下单之后，商品会通过承运商(例如顺丰)把商品送达顾客手中。在这个销售过程中，供应商，电商平台和承运商三方合作从而获得销售利润。那么我们如何"公平地"把利润分配给三方?

合作博弈论关注的核心问题就是如何对合作产生的利润(或成本)用科学的方式进行分配。用二元组 $\langle N, v \rangle$ 表示合作博弈 (Cooperative Game)，其中记号 $N, v$ 的解释如下：

• $N={1, 2, \ldots, n}$ – 参与博弈的局中人 (Player) 的集合
• $S\subseteq N$ – 局中人集合的任意子集称为联盟 (Coalition)
• $v: 2^N \rightarrow \mathbb{R}$ – 联盟的效用函数，$v(S)$ 可以及理解为联盟 $S$ 合作产生的总收益。

问题如下：给定$\langle N, v \rangle$，如何把总收益$v(N)$公平地分配给每个局中人?

不同应用场景对公平性的定义可能是不同的。因此，合作博弈论的一个核心问题就是，研究不同分配策略的性质。通过这种性质来解释公平性。

分配策略

为方面描述，我们先引入如下记号：

• $x=(x_1, x_2, \ldots, x_n)$ – 分配向量 (Allocation Vector), 局中人 $i$ 得到的收益为 $x_i$
• $x(S)$ – 联盟 $S$ 分配到的收益之和，即 $x(S) = \sum_{i\in S}x_i$

下面我们介绍一些分配策略.

Core

Core 是分配向量的集合。$x\in$core 必须满足如下条件：

1. $x(N) = v(N)$
2. $x(S) \geq v(S), \forall S\subseteq N$。

说明

1. 条件 1 保证所有的收益都被分配了。
2. 如果任意一个联盟 $S\subset N$ 想要独立门户，即，不跟其他人 ($N\backslash S$) 合作，那么条件 2 保证 $S$ 得到的总收益不会超过他们当前分配到的收益之和。换句话说。条件 2 保证联盟 $S$ 没有动机独立门户，即不合作不会赚得更多。
3. core 有可能是空集。如果非空，它包含的分配向量一般不是唯一的。

Kernel¹

Kernel 也是分配向量的集合，它从谈判的角度来定义公平性。考虑两个局中人 $i$，$j$，给定分配向量$x$，定义

$$s_{ij}(x) = \max_{S}\set{v(S) - x(S) \mid i\in S, j\not\in S, S\subseteq N}$$

站在局中人 $i$ 的角度来看，如果他不愿意跟 $j$ 合作，最多能额外获得的收益即为 $s_{ij}(x)$。因此，我们可以把 $s_{ij}(x)$ 理解为 $i$ 对 $j$ 的谈判能力。如果 $s_{ij}(x) > s_{ji}(x)$，则说明 $i$ 相对 $j$ 有可能在谈判上有优势。

$x\in$ kernel必须满足如下条件:

1. $x(N) = v(N)$
2. $x_i \geq v({i})$, $\forall i\in N$
3. 如果$s_{ij}(x) > s_{ji}(x)$, 那么$x_j = v({j})$, $\forall i,j \in N, i\neq j$

说明

1. 条件 2 确保局中人 $i$ 分配到的收益比自己"单干"不会少。
2. 把满足条件 1 和条件 2 的分配向量称为 imputation。
3. 条件 3 说如果 $i$ 对 $j$ 谈判有优势，那么 $j$ 对 $i$ 的谈判是免疫的 (因为 $j$ 分配到的收益等于自己单干的收益，$j$ 即使不合作也没有损失)。简而言之，条件 3 确保任意两个不同的局中人 $i$ 和 $j$ 在谈判地位上是平等的。
4. Kernel非空。

Nucleolus²

Nucleolus 与前面的概念有所区别，它是分配向量 (不是集合)。我们先给出一些记号：

• $e(S) = v(S) - x(S)$, $\forall S\subseteq N$ – 代表联盟 $S$ 不合作能额外获得的收益
• $\theta(x) = (e(S))_{S\in 2^N}$ – 是 $e(S)$ 构成的向量。设 $\theta(x)$ 的分量按照从大到小的顺序排列。

考虑两个分配向量 $x$, $y$，我们说 “$x$ 按词典序 (lexicographically) 比 $y$ 小”，当存在下标 $k$ 使得$\theta_k(x) < \theta_k(y)$ 且 $\theta_i(x) = \theta_i(y)$，$\forall i < k$。

Nucleolus 是按字典序最小的 imputation (满足kernel的条件1和条件2)。

说明

1. Nucleolus的定义比较抽象。它分配的思想是这样的，它考虑了所有的分配结果，选了一个让贫穷的局中人最大化的结果。
2. nucleolus $\in$ kernel。
3. 如果 core 非空, 则 nucleolus $\in$ core。

Shapley Value³

它的计算公式为:

$$x_i =\sum_{S\subseteq N\backslash {i}}\frac{|S|!(|N|-|S|-1)!}{|N|!}\left(v(S\cup{i})-v(S)\right), \quad \forall i\in N.$$

说明

1. 给定联盟 $S$，局中人 $i$ 相对 $S$ 的边际贡献为 $v(S\cup{i}) - v(S)$。
2. 如果随机分配联盟，那么 $\frac{|S|!(|N|-|S|-1)!}{|N|!}$ 是 $i$ 落入集合 $S$ 的概率。
3. 综上所述，$x_i$ 为局中人 $i$ 边际贡献的期望。

应用

下面列举几个在电商业务中的应用案例。

需求分配

假设有 $n$ 个仓库，它们对同一个商品的需求分别为 $d_1, d_2, \ldots, d_n$。当前该商品的采购入库总量为 $E$。当$E<d_1+d_2 + \ldots + d_n$时，该如何分配需求?

如果按比例分配, 当其中某个仓库 $A$ 的需求非常大时，它分到大量商品，而另外的仓库B可能只分到极少商品。这样一来 $A$ 仓库可以销售较长时间，相反 $B$ 仓库可能很快就发生缺货。长此以往，仓库 $B$ 由于需求总量少，可能长期无法满足，因而一直缺货状态。

其他的分配方式，可以参考 《破产问题》。

车辆装车

考虑把 $n$ 种商品运输到一个仓库中，每种商品的单位体积分别是 $v_1, v_2, \ldots, v_n$，商品的运输量分别是 $s_1, s_2, \ldots, s_n$。当前车辆可运输的总体积为 $E$。当 $E < \sum_{i=1}^n v_is_i$ 时，我们该如何分配商品的运输量?

令 $d_i=v_is_i$，这个问题就转化成上面的需求分配问题了。

成本分摊

设客户购买了三件商品，其售价如下表所示。

并使用了一张满 150 减 20 的优惠券，因此他实际支付的订单费用是 180 元(不考虑运费)。那么平摊到每个商品的购买成本是多少?

为了凑够优惠券的条件，实际上只需要购买帽子和手套即可。所以毛巾对凑单的实际贡献是 0。从这个角度来看，毛巾不应该享受优惠，它的购买成本应该按原价 20 计算比较合理。因此，按比例分配不太合适。为了公平起见，可以试试 Shapley Value。

促销活动评估

考虑如下的场景：某电商在同一天上线多个促销活动。促销活动的集合记为 $N={1,2,\ldots, n}$。每个促销活动对应了一些商品(同一个商品允许参加多个活动)。对任意活动的组合 $S\subseteq N$，我们可以计算其参加活动商品的总销量 $v(S)$。因此，$v(N)$ 表示当天所有活动商品的总销量。请问如何计算每个活动 $i$ 带来的销量 $x_i$?

参考文献