论文标题
机理设计及其应用中的刚性
Rigidity in Mechanism Design and its Applications
论文作者
论文摘要
我们介绍了拍卖设计中刚性的概念，并使用它来分析机理设计的一些基本方面。我们专注于单项拍卖，其中投标值的值是从某些（可能相关的）分发$ \ Mathcal f $中汲取的。令$ f $为$ \ mathcal f $的最佳机制的分配函数。非正式的情况下，$ s $是$ \ mathcal f $（线性的），如果对于每个机制$ m'$，则具有分配函数$ f'$ when $ f $ and $ f'$同意$ s $的最多$ x $ fractions $ s $的分配，预期的$ m'$的预期收入最多是$ x $ $ x $ $ x $ frataction the Buttractal Evenue的最佳收益。我们使用刚性来解释Cremer和McLean拍卖的单一成功。回想一下，如果分布遵守某个“完整排名”条件，Cremer和McLean拍卖的收入是最佳福利，但是如果这种情况不存在，则不知道Cremer和McLean的拍卖。请注意，Cremer和McLean拍卖的分配函数的Kolmogorov复杂性是对数的，而我们使用刚度表明，对于某些不遵守完整等级条件的分布，每种机制的分配功能的Kolmogorov复杂性几乎是线性线性的。假设个人合理性的不同概念，我们进一步研究了刚性。假设有前专业的合理性，如果有一个刚性集，那么最佳机制的结构很简单：最高价值``通常''的玩家赢得了该项目并贡献大部分收入。相比之下，假设临时个人合理性，则具有刚性集合$ s $的分布，其中最佳机制没有明显的分配模式（即，其Kolmogorov的复杂性很高）。我们的结果有助于解释为什么我们几乎没有希望在临时个人理性世界中发展良好，简单和通用的近似机制。
We introduce the notion of rigidity in auction design and use it to analyze some fundamental aspects of mechanism design. We focus on single-item auctions where the values of the bidders are drawn from some (possibly correlated) distribution $\mathcal F$. Let $f$ be the allocation function of an optimal mechanism for $\mathcal F$. Informally, $S$ is (linearly) rigid in $\mathcal F$ if for every mechanism $M'$ with an allocation function $f'$ where $f$ and $f'$ agree on the allocation of at most $x$-fraction of the instances of $S$, the expected revenue of $M'$ is at most an $x$ fraction of the optimal revenue. We use rigidity to explain the singular success of Cremer and McLean's auction. Recall that the revenue of Cremer and McLean's auction is the optimal welfare if the distribution obeys a certain ``full rank'' condition, but no analogous constructions are known if this condition does not hold. Note that the Kolmogorov complexity of the allocation function of Cremer and McLean's auction is logarithmic, whereas we use rigidity to show that for some distributions that do not obey the full rank condition, the Kolmogorov complexity of the allocation function of every mechanism that provides a constant approximation is almost linear. We further investigate rigidity assuming different notions of individual rationality. Assuming ex-post individual rationality, if there is a rigid set, the structure of the optimal mechanism is simple: the player with the highest value ``usually'' wins the item and contributes most of the revenue. In contrast, assuming interim individual rationality, there are distributions with a rigid set $S$ where the optimal mechanism has no obvious allocation pattern (i.e., its Kolmogorov complexity is high). Our results help explain why we have little hope of developing good, simple and generic approximation mechanisms in the interim individual rationality world.
