查看“︁贝叶斯最优机制”︁的源代码

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

这种机制的实际应用是卖家向他的潜在客户出售商品，这些卖家希望通过这种机制实现利益最大化。最优的价格取决于每个买家愿意为每件商品支付的金额。卖家不知道买家愿意出价的具体值，但他假设这些出价属于某个已知的概率分布。贝叶斯最优机制一词有如下意涵：<ref name=agt>{{cite book
 | last1 = Vazirani | first1 = Vijay V. | author1-link = Vijay Vazirani
 | last2 = Nisan | first2 = Noam | author2-link = Noam Nisan
 | last3 = Roughgarden | first3 = Tim  | author3-link = Tim Roughgarden
 | last4 = Tardos | first4 = Éva | author4-link = Éva Tardos
 | isbn = 0-521-87282-0
 | location = Cambridge, UK
 | publisher = Cambridge University Press
 | title = Algorithmic Game Theory
 | url = http://www.cs.cmu.edu/~sandholm/cs15-892F13/algorithmic-game-theory.pdf
 | year = 2007
 | chapter = {{{chapter|}}}
}}</ref>{{rp|335–338}}

*'''贝叶斯'''的意思是卖家已经知道买家出价的概率分布。
*'''最优'''意味着我们想要使拍卖商的预期收益最大化，在这种情况下，预期收入大于买家估值的预期。
*'''机制'''意味着我们想要设计规则来定义一个真实的机制，在这个机制中，每个参与者都有报告其真实估价的动机。
==举例==
假定有一件待售商品和两个潜在买家，他们的出价为[[独立同分布]]，均为在[0,1]区间的连续均匀分布。

维克里拍卖是一种真实机制，其预期利润为1/3，但是这并非最优结果。如果我们设置保留价格为1/2，则预期利润为5/12，为最优解。<ref>{{cite web |author1=Sergio Parreiras |title=Expected revenue obtained by the Vickery auction with reserve price 1/2 |url=https://math.stackexchange.com/questions/845869/expected-revenue-obtained-by-the-vickery-auction-with-reserve-price-1-2 |website=stackexchange |access-date=2021-12-15 |archive-date=2021-12-15 |archive-url=https://web.archive.org/web/20211215045512/https://math.stackexchange.com/questions/845869/expected-revenue-obtained-by-the-vickery-auction-with-reserve-price-1-2 }}</ref>
== 标记法 ==
我们假设参与者具有单参数效用函数，例如单个物品拍卖的情况。每个参与者<math>i</math>都有一个值<math>v_i</math>，它表示参与者的“得标值”（例如，参与者对物品的估价）。我们并不知道这些<math>v_i</math>值具体是多少，但我们知道每一个<math>v_i</math>都符合[[独立同分布]]。我们用符号<math>F_i</math>表示[[累积分布函数]]：
:<math>F_i(z) = \Pr[v_i<z]</math>
再用<math>f_i</math>表示[[概率密度函数]]：
:<math>f_i(z) = F_i'(z)</math>

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

分配的盈余可以定义为：
:<math>S(x) = \sum_i x_i\cdot v_i - c(x)</math>
即向竞拍者收取的费用减去对拍卖商产生的成本。

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

但是这个机制是无法实现的，因为在这种机制下，竞标者有动机低报估价<math>v_i</math>以图支付更少的价钱。不过这个问题可以通过梅尔森机制来解决。
== 梅尔森机制 ==
[[罗杰·梅尔森]]为具有单参数效用函数的参与者设计了贝叶斯最优机制，该机制的关键技巧是使用虚拟估值。对于每个竞拍者<math>i</math>，定义其虚拟估值为：
:<math>w_i(v_i) = v_i - \frac{1-F_i(v_i)}{f_i(v_i)}</math>
请注意，虚拟估值通常小于实际估值，甚至有事还有出现可能虚拟估值为负而实际估值为正的现象。

对于分配方式<math>x</math>，定义'''虚拟盈余'''为：
:<math>S^*(x) = \sum_i x_i\cdot w_i(v_i) - c(x)</math>
请注意，虚拟盈余也是小于实际盈余。
梅尔森的一个关键定理表示:<ref name=agt/>{{rp|336}}<ref name=myerson81>{{cite journal|doi = 10.1287/moor.6.1.58|title = Optimal Auction Design|journal = Mathematics of Operations Research|volume = 6|pages = 58|year = 1981|last1 = Myerson|first1 = Roger B.}}</ref>
:::'''任何真实机制的预期利润等于它的预期虚拟盈余。'''
（期望值代替了参与人估价的随机性。）

这个定理提出了以下机制：
:要求每个竞拍者<math>i</math>给出估价<math>v_i</math>
:根据竞拍者的回应和已知的概率分布函数<math>F_i,f_i</math>来计算<math>w_i</math>
:计算使虚拟盈余<math>S^*(x)</math>最大化时的分配方式<math>x</math>。

为了完成对该机制的描述，我们最后应该算出每个获胜的竞拍者需要支付的钱。一种计算方法是使用[[VCG机制]]计算虚拟估值<math>w_i</math>。VCG机制可以求出一个使虚拟盈余最大化的分配方式和一个价格向量。由于价格向量对应于虚拟估值，因此我们必须将其转换回实估值。所以这个机制的最后一步是：
*每个得标的竞拍者<math>i</math>需要支付<math>p_i = w_i^{-1}(p'_i)</math>的钱，其中<math>p'_i</math>是由VCG机制决定的。
=== 真实性 ===
当分配规则满足弱[[单调性]]，即分配函数在竞拍者估价中弱递增时，梅尔森机制是真实的。VCG分配规则在估值中确实是弱递增的，但我们将其用于虚拟估值而不是实际估值。
=== 单个商品拍卖 ===
假设我们想出售单一商品，并且我们知道所有竞拍者的估值符合相同的概率分布，函数为 <math>F,f</math>。然后，所有竞标者都具有相同的虚拟估值函数<math>w</math>。假设这个函数是弱递增的。在这种情况下，VCG机制简化为[[維克里拍賣]]，也就是将物品分配给估价最大（出价最高）的竞拍者。但是梅尔森的机制使用VCG和虚拟估值，这导致最终结果可能是负的。因此，在梅尔森机制中，这一问题简化为了'''带有保留价格的维克里拍卖'''。该机制将商品分配给估价最高的竞拍者，但前提是它的虚拟估价至少为0。这意味着梅尔森机制的保留价格恰好为:
:<math>w^{-1}(0)</math>
因此，如果我们知道概率分布函数<math>F,f</math>，我们可以计算函数<math>w</math>，并从中找到最优的保留价格。
=== 数字商品拍卖 ===
在数字商品拍卖中，我们有无限的相同物品供应，而每个竞拍者最多购买一件物品。竞拍者对物品的估价遵从相同的概率分布，分布函数为<math>F,f</math>，虚拟估价函数为<math>w</math>。VCG机制将数字商品分配给每个具有非负虚拟价值的竞标者，并收取最小的得标价格，即：
:<math>w^{-1}(0)</math>
这正好等于最优销售价格，也就是在估价分配的情况下，使卖方利润的[[期望值]]最大化的价格：
:<math>\arg\max_z {z\cdot (1-F(z))}</math>

==参考文献==
{{reflist}}

[[Category:机制设计]]