On the complexity of achieving proportional representation (Q2426957): Difference between revisions

\textit{R. J. Chamberlin} and \textit{P. N. Courant} [Am. Polit. Sci. Rev. 77, 718--733 (1983)] and \textit{B. L. Monroe} [Am. Polit. Sci. Rev. 89, 925--940 (1995)] introduced voting systems that can be used to select an assembly of representatives of a set of voters. Though different, these systems share the fundamental properties that each voter is represented by a member of the assembly, and that there is no pre-determined grouping of voters into subsets that will have common representatives. (For instance, assemblies that have seats pre-assigned to particular geographic areas are not considered.) In the present paper the authors consider the problem of determining which candidates have won election into the assembly under these systems; they prove that the problem is computationally tractable if the size of the assembly is fixed, and intractable otherwise.