# Mechanism Design: second-price payment
###### tags: `writing`

機制設計的目的在於總和多個不同參與者的偏好，設計有效的誘因機制來達成特定目的。這篇文章會從一個機制設計者的視角來思考，我們要如何設計一個具有誘因匹配（Incentive Compatibility）的拍賣機制。

我們先從最簡單的開始。一場拍賣是由一個賣家和多個買家所組成，我們作為機制的設計者 (designer)，目的是要讓一件商品（ex. NFT）從賣家的手上轉移到認為這件商品最有價值的買家手上。

> Goal: Allocate the item to the player who values it highest.

在這場拍賣中，每個買家 $i$ 心中都對這件商品有一個估價 $w_i$，$w_i$ (willing-to-pay) 就是指買家願意花多少錢買這件商品。假設買家 $i$ 贏得了這場拍賣，他必須支付 $p$ (payment) 給賣家，然後他可以獲得的效用 $u$ (utility) 是：

$$u_i = w_i - p$$

如果買家輸了這場拍賣，那他就沒有獲得任何效用： $u_i = 0$。

## Challenge

1. 我們要如何知道買家心中對這件商品的真實估價是多少？
2. 我們要如何設計一個不會被策略性操縱 (strategically manipulated) 的機制？

為了解決上述問題，以下兩點留給 designer 自由發揮的空間：
1. 你可以決定要用什麼方式去得知買家的出價（ex. 舉手、寫在紙上）
2. 你可以決定這場拍賣的贏家應該支付多少錢給賣家（也就是效用函式裡面的 $p$ 可以自行定義）

## Analysis

第一個問題，我們要如何知道買家心中對這件商品的真實估價？

如果我們像常見的拍賣方式，買家從低價開始慢慢往上喊，或是像 NFT 交易平台 Opensea 是在限定時間內讓買家公開競標，這些從買家發送出來公開訊號 (signal)，是否可以代表買家心中對這件商品的真實價值呢？

答案是不行的，正在競標的買家會不斷丟出新的標價，只要他還想繼續競標，這些標價都不會是他的底線。假設一個情境是你今天很忙沒辦法到拍賣會上，你必須委託一個代理人幫你競標，你就會告訴那個代理人：「喊到 100 元就不喊了。」這個金額才是買家心中真實的估價，也是我們想知道的，但它通常是不能說的秘密。

因此，有沒有什麼方法可以得知每個買家的出價**底線**是多少？

我們這裡的解法是讓標價不公開，讓大家把自己心中對這件商品的估價寫在紙上，每個買家都不知道彼此的估價，秘密地把紙條傳給一個中立的第三方（ex. 拍賣官），由拍賣官打開每位買家的紙條，我們就能知道誰才是對這件商品估價最高的人了。

我們隱藏了買家們彼此的訊息，而且限制他只能出價一次，這麼一來就不會有從低價喊到高價的競標行為，大家都不知道彼此對這件商品的出價，所以也只好表達自己心中對這件商品的真實價值。

但是，這會不會有漏洞？

假如你是買家，其實你可以偷偷打聽別人的出價，知道他們對這件商品的估價是多少，他們也會打聽你對這件商品的估價是多少，於是，就變成一個很複雜的狀況，每個人都在思考別人在打什麼算盤，於是大家最後寫在紙條上的標價，都不是自己真實的估價。

作為機制的 designer，我們要如何設計誘因，讓買家願意寫出真實的估價，也就是說，買家只需要想這件東西對自己來說值多少，**不用管別人在想什麼**，然後把這個金額寫在紙上。

在設計誘因機制之前，我們最好先了解所謂的「誘因匹配」是什麼？

### Incentive Compatibility

在多數決投票中，當候選人有三個時，有可能會發生所謂的「策略性投票」。簡單來說，假如你喜歡 A 候選人，但是新聞上的民調顯示 A 的支持率非常低，與 B, C 差距懸殊，此時你知道 A 是不可能當選了，於是你投票給 C，因為如果未來的總統可能是 B 或 C 的話，你寧願 C 當選。此時，你並沒有按照自己心中真實的偏好去投票，而是進行策略性投票。

而當一個機制是可以被策略性操縱的時候，這個機制是不具有誘因匹配的 (incentive compatible)。

一個機制要能夠誘因匹配，它必須讓玩家沒有動機，或沒有好的理由，去做策略性操縱的行為 (strategic manipulation)，例如欺騙、說謊、隱瞞、假裝等。如果是在一場拍賣的場景，假設買家 $i$ 對某項商品的真實估價是 $w$，獲得的效用是 $u$，，如果今天他在機制中做了策略性操縱的行為，他沒有以心中真實的估價來出價，而是對商品標價為 $w'$，而他得到的效用會變成 $u'$，而一個具有誘因匹配的機制，必須符合的條件就會是：

$$u = w - p \geq w' -p = u'$$

也就是說，他沒有理由去欺騙、說謊、隱瞞、假裝，因為這些策略性操縱的行為不會給他帶來更多的好處。

回到我們的拍賣會場上，今天你是機制的 designer，你需要設計一個誘因匹配的機制，讓你的玩家追求自身利益最大化的同時，沒有理由去操縱。

### No payment

為了解決第一個問題我們已經讓買家都把估價寫在紙條上了，此時拍賣官只要一個個將紙條打開就能知道誰出價最高，然後他不需要付任何錢就能獲得商品。等等，那不就是比誰在紙條上寫得數字最大就贏了嗎？

當買家知道贏得拍賣不需要支付任何成本時，他就會有動機寫一個非常大的標價，而這標價明顯不可能是他心中真實的估價，顯然這個機制是可被操縱的，因為玩家可以誇大商品的價值，贏得商品後又不須付半毛錢。

因此，我們要讓買家不會有動機說謊，應該要有誘因讓買家誠實表達心中的估價。

### Pay your bid

顯然我們應該讓買家支付他自己的標價，這樣他就不會浮誇商品的價值，拍賣官才不會看到有人在紙條上寫 $\infty$。這個方法就是常見的拍賣方式，買家支付的價格等於自己的出價。

然而，如果拍賣的贏家最後支付的價格是他自己的標價 $w$，那麼他的效用函數 $u = w - w = 0$，他贏得了商品，卻沒有獲得任何效用，就跟他輸掉拍賣獲得的效用一樣都是 0。

因此，他就會有動機去作策略性的操縱，也就是說，他可以欺騙拍賣官，他的標價並不是他心中真實的估價，而是低於心中的估價，這樣他才有賺到的感覺。假設他操縱的標價為 $w'$，那他就會希望 $w' < w$，這樣他就有利可圖，他的效用函數 $u = w - w' \geq 0$，就能獲得淨效益。

那麼，如果你是這個想要策略性操作的買家，你要怎麼調整自己的標價讓自己贏得拍賣的同時，又能賺到最多？你知道要把標價調低於自己心中的估價，那麼又要調低多少？

假如你有一個機會，趁拍賣官去上廁所的時候偷偷把每個競標者的紙條打開來看！於是你就知道每個競標者的出價各是多少了，你發現你還有時間，可以修改自己那張紙條上的標價，那麼，你會把標價改成哪個數字？

## Second-price payment


哥倫比亞大學的經濟學家，也是 1996 年的諾貝爾經濟學獎講得主，William Vickrey (1914–1996) 於 1961 年發表論文 "Counterspeculation, Auctions, and Competitive Sealed Tenders" 提出了次價彌封拍賣 (Sealed-bid second-price auction)，如今也稱作維克里拍賣 (Vickrey auction)。

在維克里拍賣中，所有的出價都放在一個密封的信封裡，信封打開決定得標者時，出價最高者勝。但是得標者並不是支付自己的出價，而只須支付次高出價。這個機制是誘因匹配的，也就是說買家不會有動機去做策略性操縱的行為。

> Definition:
> Let the winner be the player $i$ with the highest declared value of $w_i$, and let $i$ pay the second highest declared bid $p* = \max_{j\ne i}{ w_j}$

接下來，我們來證明為什麼這個機制是不會被操縱的。

> Proposition:
> For every $w_1,...,w_n$ and every $w_i'$, Let $u_i$ be $i$'s utility if he bids $w_i$, and $u_i'$ if he bids $w_i'$. Then, $u_i \geq u_i'$.

### Proof

我們分別從 $i$ 贏了拍賣和輸掉拍賣，兩個角度下去分析：（以下策略性操縱的情境，可以想像成是買家 $i$ 有機會打開信封看到每個競標者的估價，而且可以偷偷改寫自己的標價。）

1. 假設今天 $i$ 會**贏**得這場拍賣，他的估價是 $w_i$，而他所需要支付的價格是次高估價 $p*$，那麼他的效用函數是 $u_i = w_i - p* \geq 0$。

- 如果 $i$ 試圖策略性操縱，而他改寫自己的標價 $w_i'$，且改寫的標價**大於**次高的標價 $w_i' > p*$，他還是會贏得拍賣，而他要支付的也還是次高估價 $p*$，因此他操縱後獲得的效用 $u_i'$ 跟沒有操縱的效用 $u_i$ 是沒變的， $u_i' = u_i$。
- 同上，如果他改寫自己的標價 $w_i'$，且改寫的標價**小於**次高的標價 $p*$， $w' \leq p*$，那麼他就會輸掉這場拍賣，因此操縱後的效用就是 0，會小於他沒有操縱的效用，$u_i' = 0 \leq u_i$。

2. 假設今天 $i$ 會**輸**掉這場拍賣，他獲得的效用 $u_i = 0$。而買家 $j$ 是這場拍賣的贏家，因此 $j$ 的估價會大於 $i$ 的估價 $w_j \geq w_i$。

- 如果 $i$ 試圖策略性操縱，他改寫自己的標價為 $w_i'$，且改寫的標價**小於** $j$ 的標價 $w_i' < w_j$，他依然會輸掉這場拍賣，因此不管有沒有操縱效用都是 0，$u_i' = u_i = 0$。
- 同上，如果他改寫自己的標價 $w_i'$，且改寫的標價**大於** $j$ 的標價， $w_i' \geq w_j$，那麼他就會贏得這場拍賣，而他需要支付的是次高估價也就是 $w_j$。但是，他雖然贏了拍賣，操縱後的效用卻是負的，$u_i' = w_i - w_j \leq 0$。為什麼？因為他改寫的標價高於自己心中對於那件商品的真實價值，明明覺得這件商品沒那麼好，為了贏得商品，標了比自己心中認為的還要高的價，當然贏了商品也不會開心囉！這種情況也稱作「贏家的詛咒」。

從上述兩個角度分析下的四個結果，我們可以得出操縱後的效用並不會比較好，也就是 $u_i \geq u_i'$，因此買家不會有動機且沒有理由進行策略性的操縱，這證明維克里拍賣是誘因匹配的。

## Real world

那麼，現實生活中的拍賣是什麼樣子呢？

我們舉 NFT 常見的拍賣方式，公開競標，價格從低慢慢往上喊，贏家支付的價格是自己的標價，而賣家看到喜歡的標價，可以隨時賣出。

假設今天買家 A 很喜歡這張 NFT，他告訴自己非得買下它。在競標的過程中，某個買家標了 2 ETH，於時 A 就標 3 ETH，接著有人標了 4 ETH、5 ETH、6 ETH...，因為 A 太想要這個 NFT 了，他就標了 10 ETH，然後，他看到下一個買家的標價還是 6 ETH。

此時，賣家無意間看到競標的過程，他很滿意地接受了 10 ETH 的出價，成交！

這場 NFT 的競標結果，出價最高的是買家 A 的 10 ETH，而次高出價是 6 ETH。買家 A 必須支付 10 ETH 給賣家，但事實上，買家如果不要那麼衝動，一次從 6 ETH 跳到 10 ETH，也許 6.1 ETH 就能買到 NFT。

但是在拍賣結束之前（賣家決定成交之前），**買家 A 不可能知道這場拍賣的次高出價會出到哪裡**。他不知道次高出價，因此花了比次高出價還要高出許多的價格買下 NFT。而賣家，可能 6 ETH 就打算賣掉 NFT，沒想到競標來到 10 ETH，賣家因此多賺了 4 ETH。

維克里拍賣在經濟學文獻中很常見，在現實生活中卻很稀少，為什麼呢？

在現實生活中，賣家通常是決定拍賣機制的人。賣家的目的是希望能用最高的價格賣出商品，因此，如果賣家可以選擇拍賣的機制，他沒有理由選擇次價拍賣，一個可以讓買家們競價炒作的機制可能才是賣家的選擇。

## Conclusion

這篇文章從一個 designer 的視角去看經濟學上著名的維克里拍賣，讓我們回頭看看，作為機制的設計者，我們的目標是：

> Allocate the item to the player who values it highest.

你會發現我們關注的是這件商品的「分配」，以及買家認為這件商品價值多少，而不是從賣家的立場去想一個可以賣出高價的機制。機制設計的 designer 思考的是一個誘因機制能夠把商品分配給認為它價值最高的人，而且，這個機制必須讓買家追求自己利益最大化的同時，不會有動機做出策略性的操縱，如欺騙、說謊、隱瞞、假裝。

我們知道一個好的誘因機制需要有些條件，我們可以不必限制玩家不能有操縱的行為，讓玩家有自由去追求自身的利益，也會有自由去進行策略性的操縱，但是他的操縱行為並不會給他帶來更多的好處，那就會是一個好的機制。

在一個好的機制底下，人們追求自身利益的同時，也為社會帶來最佳的資源分配。

## Reference
- [Algorithmic Game Theory: Chapter 9.3](https://www.cs.cmu.edu/~sandholm/cs15-892F13/algorithmic-game-theory.pdf)
- [思辨賽局 Chapter 10 - 拍賣、競標與競爭](https://www.books.com.tw/products/0010717630)
- [2020諾貝爾經濟學獎：拍賣理論再進化](https://talkecon.com/2020_nobel_prize/)

## 延伸閱讀
- [Why don’t we have a second-price auction for blockspace instead?](https://docs.google.com/presentation/d/1ADPiTVWEVQ8nBGLMRdx5GmSFdrrKi3OzsbyedOcVLWk/edit#slide=id.g141d1b1a5ae_0_123)
- [auction-zoo - A menagerie of auction mechanisms implemented in Solidity](https://github.com/a16z/auction-zoo?utm_source=substack&utm_medium=email#readme)
- [Cheap, Anonymous Vickrey Auctions on-chain: bids sent to uninitialized CREATE2 addresses, proof of concept](https://blog.aayushg.com/posts/vickrey/?utm_source=substack&utm_medium=email)