近似最優機制設計與啟示原理

文章摘要“具有子模組估值的真實組合拍賣的不可能結果”（Dobzinski，Vondrak，2016 年）指出

算法機制設計中一個長期存在的懸而未決的問題是，是否存在用於組合拍賣的計算有效的真實機制，其性能保證接近那些可能的結果，而不考慮真實性。在本文中，我們否定地回答了這個問題：真實性的要求會極大地影響機制實現組合拍賣的良好近似比的能力。

我的問題是——鑑於啟示原則說我們可以在機制設計中限制我們對直接啟示 IC 機制的關注，如何通過限制近似最優的搜尋（即收益最大化) 機製到 IC 的機制？

如果我理解正確，這裡有兩個問題。

首先，為什麼計算效率高的 IC 直接機制相對於最優 IC 直接機製表現不佳？天真的答案很簡單，就是最優機制真的很複雜。這篇論文似乎仔細討論了這一點。

其次，為什麼有計算上有效的直接機制可以很好地逼近最優 IC 直接機制但不能成為 IC？在不太熟悉算法機制設計的情況下，我懷疑這是因為直接機制的類別（IC 與否）比 IC 直接機制的類別大得多。特別是，如果不需要 IC，但假設代理人仍然如實報告，則可以誘導任何結果分佈。

請注意，啟示原則的 WLOG 必須按以下方式理解。‘‘採用任意機制，並在該機制的其中一個平衡中分配結果。存在一種 IC 直接機制，它在真實報告的情況下對結果產生相同的分佈。’’ 啟示原則並沒有聲稱通過適當選擇的 IC 直接機制可以實現對結果的每個分佈——這僅適用於那些分佈已經由某種間接機制的某種平衡引起。從這個意義上說，將注意力限制在 IC 直接機制上會造成損失，因為某些結果分佈根本就不是均衡的一部分。

引用自：https://economics.stackexchange.com/questions/35953