我们研究了部分验证的自动机制设计问题，其中每种类型只能报告一组受限制的类型(而不是其他类型)，这是由主体有限的验证能力引起的。我们证明硬度结果时，揭示原则不一定成立，以及类型有最低限度的不同偏好。根据这些硬度结果，我们关注设置中的真实机制，所有类型都对结果有相同的偏好，这是由应用，例如，战略分类所驱动的。我们提出了一些算法和结构结果，包括一个寻找最优确定性真实机制的有效算法，这也意味着一个通过基于凸性的表征来寻找最优随机真实机制的更快算法。然后我们考虑一个更一般的设置，其中委托人的成本是分配给每种类型的结果组合的函数。特别地，我们将重点放在代价函数是子模的情况上，并在代价函数是可加性的经典情况下，基本上给出了我们所有的结果的推广。我们的结果提供了一个相对完整的图景自动机制设计部分验证。
原文题目：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