上一講利用 Myerson’s Lemma 闡述了給定在「好」的 allocation rule 下，該如何定價，使得 auction 具有 DSIC property; 而這講則要說明該如何 derive 出「好」的 allocation rule。
Knapsack Auction
上一講定義了 single-parameter environment ，其中的 allocation set $X$ 需滿足元素和 $ \leq k$ (in single-item, $k=1$)。這裡再將此推廣成更一般的形式。
- bidder $i$ has public size $w_i$ and private valuation $v_i$
- The allocation set $X$ contains 0-1 vectors subject to $\sum_{i=1}^n w_i \, x_i \leq W$
我們想要找的 allocation 需能最大化 social surplus
若想說明其具備 DSIC property，我們可以先證明該 allocation rule 為 monotone ，再利用 Myerson’s Lemma 得出其 payment rule
[Theorem]
$\underline{~Proof.}$
但目前為止看起來非常完美，但真是如此嗎？別忘了我們希望整個 mechanism 能在 POLY time 內結束，然而，尋找 max allocation 的問題(等價於找到 Knapsack problem 的最佳解)卻是一個 NPC …QQ，也就是說，對一般的 k-item auction 而言，不存在多項式時間的 mechanism。所以類似於在 approximation algorithm 所學的，我們的 objective 如以下。
Relax optimal surplus constraint as little as possible, subject to DSIC and POLY-time constraint
利用 Myerson’s Lemma，以下敘述也等價
Design POLY-time alg. and monotone allocation rule as close as possible to maximize the social surplus
至此，在 approximation alg. 中學到的當前 state-of-the-art 的演算法，可用於解決 AGT 的問題 (W/ 還不錯的 ratio )，但有件事情需要注意
The DSIC/monotone constraint that approx. mechanism should satisfy may cause additional surplus loss
因為我們需要保證 DSIC ，因此對某些 approx. algorithm ，我們可能需要犧牲 approx. ratio 去 maintain 這個性質。 (e.g black-box reduction)
以下定理證明用於 Knapsack problem 的 2-approx algorithm 所設計的 allocation rule 不會造成額外的 cost ，同時保持 monotone 的性質。
[Theorem] The greedy allocation rule for Knapsack auction is monotone
2-approx Algorithm: Sort bidders according to $ \frac{b_i}{w_i}$ in decending order
Choose bidders in that order until constranit DOESN’T satisfy, then pick $max(b_1 + b_2 + \cdots +b_i,$ $b\scriptstyle{i+1}$$)$For every bidder $i$, $\exists$ critical bid $b^{\star}$ (depending on its $w_i$ and $b\scriptstyle{-i}$) s.t $x_i$ jump from 0 to 1 。
It is easy to check that such allocation rule for arbitary bidder $i$ is monotone 0-1 curve 。