Complexity Consideration on the Existence of Strategy-proof Social Choice Functions
Complexity Consideration on the Existence of Strategy-proof Social Choice Functions
复制标题
DOI：
--
复制
发表时间：
--
期刊：
影响因子：
--
通讯作者：
Koji Takamiya
中科院分区：
文献类型：
--
作者：
Koji Takamiya
社会选择理论家早就认识到，在私人物品经济的模型中，防策略性有时与个人理性加帕累托效率不相容，而且证明这种不相容通常或多或少是“困难的”。在本文中，我们研究这个“困难”的计算复杂性的观点。我们建立了一个简单的私人物品交换模型，其中代理人在消费约束下引进和交易不可分割的物品。我们考虑的计算问题是，对于给定的经济规范，是否存在一个社会选择函数，它是防策略的，个体理性的和帕累托效率的。我们证明了（i）这是一个NP -困难问题，并指出，然而，（ii）问题变得计算平凡，如果我们放弃这三个属性的社会选择函数。
Social choice theorists have long recognized that in models of private goods economies, strategy-proofness is sometimes incompatible with individual rationality plus Pareto efficiency, and that it is usually more or less “difficult” to prove this incompatibility. In this paper we examine this “difficulty” from the viewpoint of computational complexity. We set up a simple model of private goods exchange where agents bring in and trade indivisible objects under consumption constraints. We consider the computational problem of deciding whether for a given specification of the economy, there exists a social choice function which is strategy-proof, individually rational and Pareto efficient. We prove that (i) this is an NP -hard problem, and point out, however, that (ii) the problem becomes computationally trivial if we drop one of these three properties of the social choice function.