How hard is it to control a group?
作者:Yongjie Yang, Dinko Dimitrov
摘要
We consider group identification models in which the aggregation of individual opinions concerning who is qualified in a given society determines the set of socially qualified persons. In this setting, we study the extent to which social qualification can be changed when societies expand, shrink, or partition themselves. The answers we provide are with respect to the computational complexity of the corresponding control problems and fully cover the class of consent aggregation rules introduced by Samet and Schmeidler (J Econ Theory, 110(2):213–233, 2003) as well as procedural rules for group identification. We obtain both polynomial-time solvability results and NP-hardness results. In addition, we also study these problems from the parameterized complexity perspective, and obtain some fixed-parameter tractability results.
论文关键词:Group identification, Consent rules, Procedural rules, Computational complexity, Parameterized complexity, Control
论文评审过程:
论文官网地址:https://doi.org/10.1007/s10458-018-9392-1