我們研究了部分驗證的自動機制設計問題，其中每種類型隻能報告一組受限制的類型(而不是其他類型)，這是由主體有限的驗證能力引起的。我們證明硬度結果時，揭示原則不一定成立，以及類型有最低限度的不同偏好。根據這些硬度結果，我們關注設定中的真實機制，所有類型都對結果有相同的偏好，這是由應用，例如，戰略分類所驅動的。我們提出了一些算法和結構結果，包括一個尋找最優确定性真實機制的有效算法，這也意味着一個通過基于凸性的表征來尋找最優随機真實機制的更快算法。然後我們考慮一個更一般的設定，其中委托人的成本是配置設定給每種類型的結果組合的函數。特别地，我們将重點放在代價函數是子模的情況上，并在代價函數是可加性的經典情況下，基本上給出了我們所有的結果的推廣。我們的結果提供了一個相對完整的圖景自動機制設計部分驗證。
原文題目：Automated Mechanism Design for Classification with Partial Verification
原文：We study the problem of automated mechanism design with partial verification, where each type can (mis)report only a restricted set of types (rather than any other type), induced by the principal's limited verification power. We prove hardness results when the revelation principle does not necessarily hold, as well as when types have even minimally different preferences. In light of these hardness results, we focus on truthful mechanisms in the setting where all types share the same preference over outcomes, which is motivated by applications in, e.g., strategic classification. We present a number of algorithmic and structural results, including an efficient algorithm for finding optimal deterministic truthful mechanisms, which also implies a faster algorithm for finding optimal randomized truthful mechanisms via a characterization based on convexity. We then consider a more general setting, where the principal's cost is a function of the combination of outcomes assigned to each type. In particular, we focus on the case where the cost function is submodular, and give generalizations of essentially all our results in the classical setting where the cost function is additive. Our results provide a relatively complete picture for automated mechanism design with partial verification.
帶有部分驗證的自動分類機構設計.pdf