论文标题
森林的激励兼容选择机制
Incentive-Compatible Selection Mechanisms for Forests
论文作者
论文摘要
鉴于定向的森林图，概率\ emph {选择机制}是顶点集的概率分布。选择机制是\ emph {convient compative}（IC），如果分配给顶点的概率在我们改变其向外边缘（甚至删除）时不会改变。选择机制的质量是该机理分布下的预期后代与森林中最大后代之间的最差比率。在本文中，我们证明了4/5的上限和$ 1/\ ln16 \ ln16 \ of Yout.36 $的下限，用于任何IC选择机构的质量。下限是通过两种新型机制来实现的，并且是Babichenko等人的结果的显着改善。 （www '18）。第一个更简单的机制具有生成公平分布（即单调和比例）的不错功能。该机制的缺点是它不是精确的（即，概率可能少于1）。我们的第二个涉及的机制是确切但不公平的。我们还证明了一种既精确又公平并且具有积极质量的IC机制的不可能。
Given a directed forest-graph, a probabilistic \emph{selection mechanism} is a probability distribution over the vertex set. A selection mechanism is \emph{incentive-compatible} (IC), if the probability assigned to a vertex does not change when we alter its outgoing edge (or even remove it). The quality of a selection mechanism is the worst-case ratio between the expected progeny under the mechanism's distribution and the maximal progeny in the forest. In this paper we prove an upper bound of 4/5 and a lower bound of $ 1/\ln16\approx0.36 $ for the quality of any IC selection mechanism. The lower bound is achieved by two novel mechanisms and is a significant improvement to the results of Babichenko et al. (WWW '18). The first, simpler mechanism, has the nice feature of generating distributions which are fair (i.e., monotone and proportional). The downside of this mechanism is that it is not exact (i.e., the probabilities might sum-up to less than 1). Our second, more involved mechanism, is exact but not fair. We also prove an impossibility for an IC mechanism that is both exact and fair and has a positive quality.
