The power of verification for one-parameter agents

摘要: We initiate the study of mechanisms with verification for one-parameter agents. give an algorithmic characterization such and show that they are provably better than without verification, i.e., those previously considered in literature. These results obtained a number optimization problems motivated by Internet recently studied mechanism design The can be regarded as alternative approach to existing techniques truthful mechanisms. construction reduces algorithm satisfying certain ''monotonicity'' conditions which, case much less stringent. In other words, makes easier more efficient (both computationally terms approximability).