Who to Trust for Truthfully Maximizing Welfare

摘要: We introduce a general approach based on \emph{selective verification} and obtain approximate mechanisms without money for maximizing the social welfare in domain of utilitarian voting. Having good allocation mind, mechanism with verification selects few critical agents detects, using oracle, whether they have reported truthfully. If yes, produces desired allocation. Otherwise, ignores any misreports proceeds remaining agents. randomized truthful (or almost truthful) that verify only $O(\ln m / \epsilon)$ agents, where $m$ is number outcomes, independently total are $(1-\epsilon)$-approximate welfare. also show constant approximation ratio needs to $\Omega(\log m)$ A remarkable property our \emph{robustness}, namely their outcome depends reports