Optimal collusion-resistant mechanisms with verification

摘要: Abstract We present the first general positive result on construction of collusion-resistant mechanisms, that is, mechanisms guarantee dominant strategies even when agents can form arbitrary coalitions and exchange compensations (sometimes referred to as transferable utilities or side payments ). This is a much stronger solution concept compared truthful group strategyproof only impossibility results were known for this type in “classical” model. describe with verification return optimal solutions wide class mechanism design problems (which includes utilitarian ones special case). Note every without must have an unbounded approximation factor and, general, cannot be obtained if we content ourselves (“non-collusion-resistant”) mechanisms. All these apply been extensively studied algorithmic literature like, instance, task scheduling inter-domain routing.