贝叶斯最优机制

贝叶斯最优机制（英語：Bayesian-optimal mechanism，BOM）是一种拍卖机制，这种机制的设计者不知道参与者的出价具体是多少，但是知道这些参与者的出价是一个随机变量和这些随机变量的概率分布。

这种机制的实际应用是卖家向他的潜在客户出售商品，这些卖家希望通过这种机制实现利益最大化。最优的价格取决于每个买家愿意为每件商品支付的金额。卖家不知道买家愿意出价的具体值，但他假设这些出价属于某个已知的概率分布。贝叶斯最优机制一词有如下意涵：

• 贝叶斯的意思是卖家已经知道买家出价的概率分布。
• 最优意味着我们想要使拍卖商的预期收益最大化，在这种情况下，预期收入大于买家估值的预期。
• 机制意味着我们想要设计规则来定义一个真实的机制，在这个机制中，每个参与者都有报告其真实估价的动机。

举例

假定有一件待售商品和两个潜在买家，他们的出价为独立同分布，均为在[0,1]区间的连续均匀分布。

维克里拍卖是一种真实机制，其预期利润为1/3，但是这并非最优结果。如果我们设置保留价格为1/2，则预期利润为5/12，为最优解。

标记法

我们假设参与者具有单参数效用函数，例如单个物品拍卖的情况。每个参与者$i$都有一个值$v_{i}$，它表示参与者的“得标值”（例如，参与者对物品的估价）。我们并不知道这些$v_{i}$值具体是多少，但我们知道每一个$v_{i}$都符合独立同分布。我们用符号$F_{i}$表示累积分布函数：

$F_{i}(z)=\Pr[v_{i}<z]$

再用$f_{i}$表示概率密度函数：

$f_{i}(z)=F_{i}'(z)$

接下来，我们用向量$x$表示分配方式，如果参与者$i$得标，则$x_{i}=1$，反之$x_{i}=0$。分配方式$x$对拍卖师产生的成本可表示为$c(x)$。

分配的盈余可以定义为：

$S(x)=\sum _{i}x_{i}\cdot v_{i}-c(x)$

即向竞拍者收取的费用减去对拍卖商产生的成本。

分配的盈余意味着最大可能的利润。如果每个竞拍者$i$最终支付$v_{i}$，那么拍卖商的利润是盈余$S(x)$，这意味着拍卖商把所有的盈余收归自己所有，竞拍者的效用为0。

但是这个机制是无法实现的，因为在这种机制下，竞标者有动机低报估价$v_{i}$以图支付更少的价钱。不过这个问题可以通过梅尔森机制来解决。

梅尔森机制

罗杰·梅尔森为具有单参数效用函数的参与者设计了贝叶斯最优机制，该机制的关键技巧是使用虚拟估值。对于每个竞拍者$i$，定义其虚拟估值为：

$w_{i}(v_{i})=v_{i}-{\frac {1-F_{i}(v_{i})}{f_{i}(v_{i})}}$

请注意，虚拟估值通常小于实际估值，甚至有事还有出现可能虚拟估值为负而实际估值为正的现象。

对于分配方式$x$，定义虚拟盈余为：

$S^{*}(x)=\sum _{i}x_{i}\cdot w_{i}(v_{i})-c(x)$

请注意，虚拟盈余也是小于实际盈余。 梅尔森的一个关键定理表示:

任何真实机制的预期利润等于它的预期虚拟盈余。

（期望值代替了参与人估价的随机性。）

这个定理提出了以下机制：

要求每个竞拍者$i$给出估价$v_{i}$

根据竞拍者的回应和已知的概率分布函数$F_{i},f_{i}$来计算$w_{i}$

计算使虚拟盈余$S^{*}(x)$最大化时的分配方式$x$。

为了完成对该机制的描述，我们最后应该算出每个获胜的竞拍者需要支付的钱。一种计算方法是使用VCG机制计算虚拟估值$w_{i}$。VCG机制可以求出一个使虚拟盈余最大化的分配方式和一个价格向量。由于价格向量对应于虚拟估值，因此我们必须将其转换回实估值。所以这个机制的最后一步是：

• 每个得标的竞拍者$i$需要支付$p_{i}=w_{i}^{-1}(p'_{i})$的钱，其中$p'_{i}$是由VCG机制决定的。

真实性

当分配规则满足弱单调性，即分配函数在竞拍者估价中弱递增时，梅尔森机制是真实的。VCG分配规则在估值中确实是弱递增的，但我们将其用于虚拟估值而不是实际估值。

单个商品拍卖

假设我们想出售单一商品，并且我们知道所有竞拍者的估值符合相同的概率分布，函数为 $F,f$。然后，所有竞标者都具有相同的虚拟估值函数$w$。假设这个函数是弱递增的。在这种情况下，VCG机制简化为維克里拍賣，也就是将物品分配给估价最大（出价最高）的竞拍者。但是梅尔森的机制使用VCG和虚拟估值，这导致最终结果可能是负的。因此，在梅尔森机制中，这一问题简化为了带有保留价格的维克里拍卖。该机制将商品分配给估价最高的竞拍者，但前提是它的虚拟估价至少为0。这意味着梅尔森机制的保留价格恰好为:

$w^{-1}(0)$

因此，如果我们知道概率分布函数$F,f$，我们可以计算函数$w$，并从中找到最优的保留价格。

数字商品拍卖

在数字商品拍卖中，我们有无限的相同物品供应，而每个竞拍者最多购买一件物品。竞拍者对物品的估价遵从相同的概率分布，分布函数为$F,f$，虚拟估价函数为$w$。VCG机制将数字商品分配给每个具有非负虚拟价值的竞标者，并收取最小的得标价格，即：

$w^{-1}(0)$

这正好等于最优销售价格，也就是在估价分配的情况下，使卖方利润的期望值最大化的价格：

$\arg \max _{z}{z\cdot (1-F(z))}$