貝葉斯最優機制

貝葉斯最優機制（英語：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))}$