最優拍賣機制的數學原理

1. 背景

假設一個賣家有一些資源可以賣給能夠利用這些資源的若干個買家，但賣家並不清楚這資源對於這些買家具體的價值有多大、買家願意為其支付的費用是多少。這時對於賣家來說，設計一套合適的拍賣的方式可以最大化其期望收益。而拍賣是集體決定價格和分配的過程，賣家定義拍賣的規則和過程，買家提交出價，依據拍賣的規則和這些出價最終決定商品或資源在買家中的分配和每一買家應支付的價格。

拍賣機制，或稱競價機制，就是拍賣的規則和過程。賣家的核心問題是，設計一套能夠使得達成最大化收入，並能夠保證賣方與買方長期可持續發展的拍賣機制。Roger Myerson 對拍賣過程中涉及到的各方的期望收益進行了數學建模和描述，並將設計最優拍賣機制的問題轉化為一個數學上的優化問題。對於拍賣一件商品的問題，Myerson給出了這類優化問題的解，對應收入最優的拍賣機制。

Myerson的這套最優拍賣設計理論獲得了2007年的諾貝爾經濟學獎，這篇文章嘗試回顧和分析Myerson對於拍賣機制設計問題的數學描述和最優競價機制的推導。

2. 拍賣的數學描述

假設賣家要拍賣一個商品，共有$N$個買家參與，第$i$個買家對這件商品的價值的估計是 ，而這個 也是買家i願意為這件商品支付的最大的價格。

買家的 的具體取值對於賣家來說是不可知的，但賣家可以通過分析、揣摩來對其有一個大概的估計。這個估計在數學上可以描述為 取值的概率分布， 。其中 ， ， 在 上連續且 。這裡對於概率分布 的數學上的假設可以理解為，賣家認為買家$i$對商品價值估計值在區間 內，每個可能的取值 都有 的概率被取到，且這個概率不小於0，即每個取值都有可能被取到。

基於這個概率密度，賣家可以據其累積分布函數 來描述買家$i$的最大價值估計為$v_i$的概率。

假設買家的 之間是相互獨立的，那麼買家對商品的價值估計 服從概率分布 。對於任一買家i，其他買家的商品價值估計 服從概率分布 。

拍賣機制本質上是一套規則，根據參與競價的買家提交的出價來決定商品分配給哪一個勝出的買家，以及決定商品的價格。對於機制的設計，我們只考慮一類特殊的拍賣機制，「直接披露機制」（direct revelation mechanism）。在這類機制中，買家同時將出價秘密地提交給賣家，買家之間互相不知道出價信息，然後賣家直接決定商品分配給哪一個買家和每個買家應付的費用。

因此可以將拍賣機制在數學上描述為兩部分：一個是分配函數 ，根據出價組合 來得到商品被分配給每一個買家的概率，顯然有

(2.1)

另一個是計價函數 ，在前述分配加過下根據出價組合來得到每一買家應支付的費用。

這樣，買家i在拍賣機制 下參與競價且出價為其真實價值估計 時其收益期望是：

(2.2)

這個收益期望的數學描述有一個假設，買家是risk-neutral的，這樣其收益可以線性的描述為贏得拍賣而獲得的價值的期望減去其為此支付的成本。

而對於賣家來說，假設其保留商品不賣掉時商品對其價值為 ，那麼其在拍賣機制 下的收益期望為：

(2.3)

3. 最優拍賣機制

最優競價機制要解決的問題就是設計具體的 來最大化(2.3)。而買家是獨立且理性的，賣家無法干預買家是否參與競價和如何出價。因此這裡還有兩個假設需要滿足：一個是每個買家要有參與拍賣的意願，另一個是買家傾向於按照真實的價值估計來出價。因此需要在機制的設計中考慮這兩點，一是其收益期望(2.2)不應小於0，即

(3.1)

二是買家出價為其真實價值時所獲得的收益期望(2.2)最大。前者通過對機制 的約束可以滿足，後者則需要考慮在所有買家出價均為其真實價值時能夠達成一個Nash均衡。

假設買家$i$的真實價值估計是 ，而其提交的出價為 ，此時其收益期望為:

我們需要保證：

(3.2)

滿足約束(2.1) 取值非負且加和小於1，(3.1) 買家參與拍賣的收益期望非負，(3.2) 出價為真實價值是佔優策略，這樣的機製為可行的。最優機制的求解問題轉化為從可行的直接披露機制中找到使賣家收益最大的優化問題。

這裡只考慮了直接披露機制，而根據Myerson論文中的Lemma 1，任一可行的機制都有一個直接披露機制能夠產生與其相同的買家和賣家收益期望。所以只需要在直接披露機制中找到最優機制，就是所有可行機制中的最優值。

3.1 可行機制的充要條件

前述的可行機制的條件(2.1) (3.1) (32) 針對的是具體的物理意義，易於理解但不適合直接應用在最優機制的求解上。Myerson對其做了分析並給出了易於在優化問題中求解的條件的數學描述。

當買家i出價為 時其贏得拍賣的概率為

這時，其收益期望可以描述為：

那麼約束(3.2)，即出價為真實價值是收益最高的策略，等價於

(3.3)

這其中 是真實價值為 且按真實價值出價時的收益期望， 是真實價值為 且按真實價值出價時的收益期望。條件(3.3)可以理解為，如果買家出價並不是其真實的價值，那麼其通過不真實的出價而獲得的額外收益的期望 ，加上以 衡量物品的價值時其的收益期望，二者的和要小於其出價為真實價值時的收益期望。

對於式子（3.3），交換 和 後不等式仍然成立，將這兩個不等式合併，可以得到：

根據 和 二者的大小的情況，可以得出 滿足弱單調遞增的條件，即

(3.4)

這個條件的具體意義是說買家的出價越高則其贏得競價的概率越大。

同時，根據上述式子，對任意 ，有

又因為 是弱單調遞增的，它滿足Riemann integrable條件，那麼

（3.5）

此外，因為買家收益非負的限制（3.1），且因為(2.1)買家$i$的真實價值在區間 內每一處的概率都大於0，那麼真實價值為 也滿足這個限制，即

（3.6）

以上的推導，證明了當條件（3.1）和（3.3）成立時，條件（3.4）（3.5）（3.6）成立。

剩下的只需證明（3.4）（3.5）（3.6）成立時（3.1）（3.2）也成立，我們就得到了這組更簡單清晰易於數學實現的機制可行的充要條件。具體的推導如下。

因為（2.1） 在其定義域上處處大於0，那麼顯然 。同時因為條件（3.6），（3.5）等式右邊是兩個大於0的值，那麼等式左邊一定大於0，即（3.1）成立。

假設 ，根據（3.4）和（3.5）

同樣可以推出當 時，上述最終的不等式也成立。而這個不等式就是前述的條件（3.2）。

綜上，我們得到了一組在數學上較為簡潔且易於實現的條件，它們是一組直接披露機制可行的充分必要條件。

3.2 最優競價機制的求解

最優競價機制的求解就是在滿足上一節的（2.1）（3.4）（3.5）（3.6）條件約束下最大化賣家的收益期望（2.3）。對於目標值

(3.7)

其中

這裡 和 積分區域是一個等腰直角三角形，變換二者的積分順序可以得到

將這個結論代入到（3.7），得到

(3.8)

最優競價機制的求解問題，就是在滿足（2.1）（3.4）（3.5）（3.6）條件下，找到使（3.8）最大的機制函數二元組 。

而對於目標（3.8）來說，機制中的計價函數 只與第二項有關，這大大簡化了這個優化問題。因為（3.6）條件，那麼使（3.8）最大，需要

（3.9）

根據（3.9）來求解x的過程如下：

儘管這個數學的表達上是在 分布上的期望值為0，但我們需要在每一個確定了的 和 下，都使得（3.8）最大，那麼我們得到

（3.10）

這個 的解在滿足機制可行性條件下能夠最大化目標（3.8）。這樣在確定了分配 下，最優的計價 就得到了。最優機制的求解變成了如何得到最優的分配函數 。Myerson的文章中在此處給出了收益等效定理(the revenue-equivalence

theorem)：在一套可行的機制下，賣家的期望收益完全由分配 和買家在最低估值下的收益來決定的。這個目標可以描述為

（3.11）

3.3 常規狀態下的最優機制

在一些特定的條件下，我們可以直接求解出使（3.11）最優的 。這裡定義虛價值(virtual value，也可以根據virtual的本意翻譯做實質價值)：

因為 在 上連續且 ，所以 在 是有界且連續的。

當售賣的是不可分割的一件商品時，勝出買家的 ，其他買家的 。那麼此時一個最大化（3.11）的方案是，只需要 是 最大且非負i，並且這個機制方案需要滿足機制可行性的約束，尤其是對於分配的（3.4）條件。

這裡 越高，勝出的期望 越大，而由上述方案的定義可知， 越大對應 越大。因此，上述機制是最優機制的一個重要前提是： 關於 嚴格單調遞增。這個條件在Myerson的文章中稱為常規性假設(regularity assumption)。

在滿足常規性假設的分布上，最優的 即上述的virtual value非負的所有買家中virtual value最大者贏得拍賣。對應的計價函數的結果，根據（3.10），有：

其中當 時， 。當 時，上述等式右邊的第二項的積分區間有所不同。區間的下端點是分隔點在買家$i$是否勝出的節點上。假設virtual value第二高的買家為買家$k$，二者的virtual value相等時的買家$i$的出價為$reve{v}_i = phi^{-1}( phi(v_k) )$。這樣等式右邊變為：

這樣得到的 符合機制可行性的條件（2.1）（34）（3.5）（3.6），且最大化賣家收益（3.8）。

這套最優機制相當於使用 作為保留價，並在買家出價的virtual value空間上應用Vickery拍賣來分配和計價。 稱為hazard rate，其意義是當取值大於等於 為真時，取值為 的概率。而 是inverse hazard rate。

對於大多數分布函數$f(), F()$來說，常規性假設（ 嚴格單調遞增）都能夠滿足。對於極少數特殊的價值分布情況無法滿足常規性假設的，Myerson的文章也做了最優機制的推導，因為篇幅的限制，這裡不做深入分析。

Myerson的文章對單個商品多個買家的情況分析了對賣家來說受益最大的拍賣機制的設計。對於多個商品多個買家的拍賣機制，對賣家和每個買家的收益期望的數學描述變得非常複雜，難以簡單的formulate和求解，所以一般是給出一個更強的假設，並得到一個非最優的近似解。例如symmetric Nash equilibrium，locally envy-free等等假設是針對搜索廣告的展示機會的拍賣場景的，是generalized second price拍賣機制的基礎。GSP非常簡單直觀易行，但其本身並不是一個最優的拍賣機制。

推薦閱讀：