Algorithmic Game Theory - Lecture2

Mechanism Design Basics

Algorithmic Game Theory
Game Theory / Algorithm / Open Course / Stanford

Lecture1 提到了我們需要透由好的 mechanism，使得 agent 與 designer 的 incentive 彼此 aligned。這講從最簡單的 Single-item Auction 開始，探討該如何設計合理的 mechanism。

Single-Item Auction

1 seller wants to sell 1 good.

There are n strategic bidders want to buy the good with their own preferences (unknown to the seller).

在討論之前，我們先以簡單的 model 來描述 bidder 的行為。

Let valuation $v_i$: bidder i's max willingness-to-pay for the item

定義 quasilinear utility model $U$ 如以下

\[ U = \left\{ \begin{array}{ll} 0, \text{if not win} \\ v_i - p, \text{if wins at price} ~p \end{array} \right. \]

而 bidder 的 objective is to maximize $U$

Sealed-Bid Auction

對 designer 而言，需要設計適合的機制。而這裡所謂適合，即是能獲得整體最大收益(包括 seller 和 bidder)

而Sealed-Bid Auction 有以下幾個步驟:

  1. Each bidder $i$ privately communicates a bid $b_i$ to the seller

  2. The seller decide who can get the good

  3. The seller decide the selling price

(2) 很直觀來想，就是給出價最高的 bidder (more selection rule will come later)， 這裡主要討論 (3), eBay的作法是以下的 second-price auction (得標者付第二高價的 bid 即可)。

Second-Price (Vickery) Auction

  1. [strong incentive guarantees] It is dominant-strategy incentive-compatible (DSIC)

  2. [computational efficiency] The auction can be implemented in $\mathbf{POLY}$ time (indeed, we want it to be linear)

  3. [strong performance guarantees] If bidder report truthfully, then the auction maximizes the social surplus

\[ \sum\limits_{i=1}^n \mathbb{1}[\text{bidder i wins}],

\text{subject to } \sum\limits_{i=1}^n \mathbb{1}[\text{bidder i wins}] \lneq 1

]

回顧 Lecture1，可以發現最一開始講到的 3 個部份一一對應 XD

從 bidder 的觀點來看， DSIC property，保證了誠實是最佳策略 (無論其他的 bidder 如何報價)，因此對 seller 來說，只要組成是完全理性的 bidder，便可預測其行為 (這裡先忽略 collusion 或非理性的情況 :p)。

Claim

Every bidder has a dominant strategy: set its bid $b_i = v_i$, and guaranteed to have utility $\gneq 0$.

考慮 bidder i, let $B = max_{j \neq i}b_j$

\[ \text{payoff of bidder i} = \left\{ \begin{array}{ll} v_i - B, \text{if} ~b_i > B \\ 0, \text{otherwise} \end{array} \right. \]

若為了拿到 good，而高報 bid (i.e $b_i > v_i$)，有以下 cases:

  1. $B < v_i$ or $B > b_i$，與誠實報的 payoff 相同。

  2. $v_i < B < b_i$， bidder 會贏得 good ，但 payoff 是負的☹，而誠實報的 payoff 為0 (然後輸掉)，故會選擇誠實。

同理，低報 bid 比不上誠實報 (直覺來想就是，低報可能使原先會贏的拍賣，到最後反而將商品拱手讓人 :p)

對那些沒拿到 good 的人， $U = 0$; 而贏家 (imply $v \gneq B$) 的 utility $~U = v -B \gneq 0 ~\blacksquare$

3 個 property的 (3) 可簡單地用 greedy 常見的方法證明，而 (2) 對seller而言只要簡單的掃過一遍 bid vector就可決定誰贏得 auction 及成交價格，複雜度為 $\mathcal{O}(n)$

思考

另一種可能的定價方式為 first-price auction，在這個情況下， winner 需付自己所喊的價碼，所以其傾向於會低報(誠實報保證了 payoff 為 0)，但問題是該低報多少，又跟其他 bidder 有關… (留著之後來想XD)

 
comments powered by Disqus