In the design of incentive compatible mechanisms, a common approach is to enforce incentive compatibility as constraints in programs that optimize over feasible mechanisms. Such constraints are often imposed on sparsified representations of the type spaces, such as their discretizations or samples, in order for the program to be manageable. In this work, we explore limitations of this approach, by studying whether all dominant strategy incentive compatible mechanisms on a set $T$ of discrete types can be extended to the convex hull of $T$. Dobzinski, Fu and Kleinberg (2015) answered the question affirmatively for all settings where types are single dimensional. It is not difficult to show that the same holds when the set of feasible outcomes is downward closed. In this work we show that the question has a negative answer for certain non-downward-closed settings with multi-dimensional types. This result should call for caution in the use of the said approach to enforcing incentive compatibility beyond single-dimensional preferences and downward closed feasible outcomes.
翻译:在设计奖励兼容机制时,一个共同的方法是将激励兼容性作为最佳利用可行机制的方案的制约因素,这些制约因素往往施加于类型空间的封闭性表示,例如其离散性或样本,以使方案易于管理;在这项工作中,我们探讨这一方法的局限性,研究是否可以将一套离散型美元的所有主要战略鼓励兼容机制扩大到离散型美元这一固定壳体。Dobzinski、Fu和Kleinberg(2015年)肯定地回答了所有类型为单一维度的设置的问题。在一组可行结果向下关闭时,不难证明同样的情况。在这项工作中,我们表明这一问题对于某些多维型非自上而下封闭的环境有一个否定的答案。因此,应当谨慎使用上述方法在单维偏好和向下封闭式可行结果之外强制执行激励兼容性。