Computational complexity in the design of voting rules
Koji TAKAMIYA∗

Akira TANAKA†

Faculty of Economics,

Graduate School of

Niigata University

Information Science and Technology,
Hokkaido University

December 14, 2013

Abstract
This paper considers the computational complexity of the design of voting rules,
which is formulated by simple games. We prove that it is an NP-complete problem todecide whether a given simple game is stable, or not.
JEL Classification— C71, D71.
Keywords— computational complexity, NP-completeness, simple game, core, stability, Nakamura number.

1

Introduction

1.1

Motivation

This paper considers the design of voting rules from the viewpoint of computational complexity. In many real-life organizations, people have to design some rules to make collective
decisions. In designing such a rule, the designer has to check beforehand whether the designed rule works properly. For example, the designer has to check whether the rule
outputs an appropriate decision for every possible input. However, such checking may be
a computationally daunting task. In this paper, we examine such computational problems
in the case where the voting setting is formulated by the familiar concept of simple games(Nakamura 1975). In discussing the “hardness” of computation, we utilize the well-known
concept of NP-hardness from computational complexity theory.
Consider a group of people who want to set up a voting rule for their own use. Then
there are at least two requirements that the group would want to impose on the rule.
First, the group would want the rule to properly reﬂect the distribution of “decision
power” within the group speciﬁed in advance. For example, in a stockholders’ meeting, it
is usually required that the larger the share one has, the bigger the “decision power” theone is given. This may be embodied as the number of votes distributed proportional to
the share.
Second, the group would want the rule to work for any conceivable case, that is, for
any combination of preferences of the members of the group. For example, the simple∗

Corresponding author. Faculty of Economics, Niigata University. 8050 2-no-cho Ikarashi Nishi-ku
Niigata Japan, 950-2181. E-mail: takamiya@econ.niigata-u.ac.jp.
†
Division of Computer Science, Graduate School of Information Science and Technology, Hokkaido
University. Kita14 Nishi9 Sapporo Japan, 060-0814. E-mail: takira@main.ist.hokudai.ac.jp.

1majority rule can always output winners for any votes (though there can be ties). On
the contrary, the Condorcet winner rule does not always output winners. It would not bedesirable for the group to have decision rules like the latter.
In this paper, we adopt the formulation in terms of simple games. A simple gamerepresents a “power distribution” in the group in a very simple way: Each subgroup iscategorized as “powerful” or “not powerful.” Formally, a simple game is the list of thesubgroups that are labeled “powerful.”
Provided that the power distribution is given by a simple game, let us consider thetwo requirements which we imposed on the voting rule in the above. To meet the ﬁrst
requirement, we require the voting rule to be a subcorrespondence of the core of the simple
game. The core is the set of alternatives which cannot be blocked by any “powerful”
subgroups. That is to say, the core is those alternatives which do not confront with any
eﬀective oppositions given the power structure described by the simple game. To fulﬁll
the second requirement, the core has to be nonempty for every combination of preferencesthat the members of the group may have. If the core of a simple game has this property,
then the simple game is called stable. Therefore, our question in designing a voting rule
is summed up to whether the underlying simple game is stable, or not.

1.2

Results

From the discussion in the above, it is essential to check whether any given simple gameis stable, or not. The question we ask in this paper is how computationally complex
this checking is. We prove that it is an NP-complete problem to decide whether a given
simple game is stable or unstable. In fact, we prove that the problem is NP-complete not
only in the general case but in the special case in which the set of “powerful” subgroups
consists only of “large” subgroups. Restricting “powerful” subgroups to “large” ones isnatural because in many real-life situations, power is assigned only to “large” subgroups.
In our proofs, we utilize the result proved by Nakamura (1979) that gives a necessary andsuﬃcient condition for stability.
The signiﬁcance of our results is that they cast a practical limit on the availabilityof stable voting rules. Our results suggest that there would be some cases in which thedesigner of the voting rule cannot check the performance of the rule in a practical sense.
This fact restricts those simple games which are available for practical use.
We note that our proofs are mathematically trivial: They follow immediately fromknown results. Nonetheless, we consider our results important in that they answer somebasic questions regarding computational aspects of voting theory. We believe that our
results are worth reporting to the readers in voting theory, rather than those in computational complexity theory.

2

Preliminaries

2.1

NP-completenessFor those not familiar with computational complexity, the following is only a brief andinformal description of NP-completeness. For detailed exposition, Garey and Johnson(1979) is a classical reference. A newer and concise presentation is Chapter 2 of Arora
and Barak (2009).
2

A decision problem (problem, henceforth) is a problem which is to be answered in“yes” or “no.” A problem consists of the descriptions of(i) instance, which is the free parameters of the problem, and(ii) question, which is to be answered in “yes” or “no.”The answer to the question depends on the values of the free parameters. An instancerefers to one set of values of these parameters.
Consider a problem. We say that an algorithm solves this problem if (i) the algorithm
outputs “yes” if, and only if, the input is an instance for which the answer to the problem
is “yes,” and (ii) otherwise the algorithm outputs “no.”1 Then we say that the problem
belongs to the class P if there is an algorithm that solves the problem in polynomial time,that is, the maximum time (the maximum number of steps) taken to answer the questionis bounded by some ﬁxed polynomial in the size of the instance (the length of the input).
We say that the problem belongs to the class NP if there is an algorithm that verifies
the answer to the problem in polynomial time, that is, if there is a polynomial-timealgorithm such that for any given instance, the answer to the question is “yes” if, andonly if, there is a certain additional input, called a certificate, with which this algorithm
outputs “yes.” Here the certiﬁcate has to be a polynomial length in the size of the instance.
It is straightforward that P ⊂ NP. At the present time, however, it is unknown
whether P = NP, or not. This is one of the fundamental problems in computer scienceand mathematics. (See Cook (2000).) It is widely believed that P ̸= NP.
Let L1 and L2 be problems. We say that L1 is polynomial-time reducible to L2 if(i) there exists a function f that transforms any instance x of L1 into the instance f (x)of L2 such that the answer to L1 for the instance x is “yes” if, and only if, the answer
to L2 for the instance f (x) is “yes,” and(ii) the function f is embodied by a polynomial-time algorithm.
Intuitively, L2 is at least as hard as L1 ; if you can solve L2 , then you can also solve L1
by transforming the instances of L1 into those of L2 , and the transformation itself is not
diﬃcult. Denote this relation by L1 ≤p L2 . Note that ≤p is transitive.
A problem L1 is called NP-hard if for any L2 ∈ NP, L2 ≤p L1 . Further, L1 is called
NP-complete if L1 is NP-hard and L1 ∈ NP. Intuitively, a problem being NP-completemeans that the problem is one of the “hardest” among all NP problems. A problem being
NP-hard means that it is at least as hard as NP-complete problems.
There are numerous problems which are known to be NP-complete. One method
which is often used in proving a certain problem L1 is NP-hard is reduction. This is doneby the following steps:(i) Specify a known NP-complete problem L2 .
(ii) Show L2 ≤p L1 by giving a concrete polynomial-time transformation.
To prove L1 is NP-complete, we additionally show L1 ∈ NP. We will utilize this methodin the sequel.
1

In this paper, by the term “algorithm,” we mean “deterministic algorithm.” That is, we exclude suchalgorithms which utilize randomness. We are not going into the formal deﬁnitions of these concepts here.

3Given a problem L, the complementary problem L̄ of L is the problem which has
the same free parameters but has the opposite question to L. That is, if L asks if ∃x : p(x),then L̄ asks if ∀x, ¬p(x). First, we note that if a problem L is NP-complete, then L̄ is
NP-hard since L is reducible to L̄ (i.e. L ≤p L̄) by ﬂipping the output. Let coNP denotethe set of problems L for which L̄ ∈ NP. It holds true that P ⊂ coNP. It is an open
problem whether coNP = NP or not. In fact, this is related to the P = NP problem:
coNP ̸= NP implies P ̸= NP. Further, if there exists an NP-complete problem L
such that L̄ ∈ NP, then coNP = NP. (Theorem 7.2 in Garey and Johnson (1979) p.
156.) Thus if a problem is NP-complete, then it is not known whether its complementary
problem belongs to NP or not.

2.2

Simple games

A simple game is a list G = (N, W , Ω). Here N is a nonempty ﬁnite set of individuals.
A coalition is a nonempty subset of N . W is a nonempty class of coalitions. Any elementof W is called a winning coalition. Ω is a nonempty ﬁnite set of alternatives.
A preference relation of individual i ∈ N is an acyclic binary relation ≻i on Ω.2 For
x, y ∈ Ω, x ≻i y means “i strictly prefers x to y.” We denote a combination of preferencesof all individuals (≻i )i∈N by ≻.
Let a simple game and a combination of preferences (G , ≻) be given. Let x, y ∈ Ω.
Then we say that x is blocked by S with y if∀i ∈ S, y ≻i x.
The core of (G , ≻) is the set of alternatives which are not blocked by any coalitions withany alternatives.
A simple game G is called stable if the core of (G , ≻) is nonempty for any combinationof preferences ≻. One of the fundamental questions in the theory of simple games iswhether a given simple game is stable, or not. Nakamura (1979) gave the answer to thisquestion by providing a necessary and suﬃcient condition for stability in terms of the“Nakamura number.”∩Call a simple game G weak if W ̸= ∅. Let G be a simple game which is not weak.
Then the Nakamura number V (W ) of G is{}∩
V (W ) = min #σ | ∅̸=σ ⊂ W ,σ=∅ .
We will utilize the following well-known theorem for proving our results.
Theorem 1 (Nakamura, 1979) Let a simple game G = (N, W , Ω) be given. Then G isstable if, and only if, (i) G is weak, or (ii) #Ω < V (W ).
For a general and comprehensive analysis of the Nakamura number, consult Kumabeand Mihara (2008a).

A binary relation ≻i on Ω is called acyclic if for any natural number m, any m elements x1 , x2 , · · · , xmof Ω, if x2 ≻i x1 , x3 ≻i x2 , · · · and xm ≻i xm−1 , then x1 ̸≻i xm .
2

4

3

Results

Let us deﬁne the problem that we will examine.
Name: UNSTABILITY.
Instance: A nonempty ﬁnite set N ; A nonempty collection W = {W1 , · · · , Wm }of nonempty subsets of N ; A nonempty ﬁnite set Ω.
Question: Is the simple game G = (N, W , Ω) not stable?
Note that the question in the above problem is asking whether the simple game is notstable, that is, the answer is “yes” if, and only if, the simple game is not stable. Let us
refer to the complementary problem of UNSTABILITY as STABILITY. One may thinkthat STABILITY, rather than UNSTABILITY, is the natural question to ask. However,as we will see, here we cannot decide whether STABILITY belongs to NP, or not, whereas
we prove that UNSTABILITY is in NP (see just below Theorem 2).
Although UNSTABILITY is our primary problem, we consider an easier version of
UNSTABILITY so that we will obtain stronger results. In this easier version, winningcoalitions are restricted to “large” coalitions. Here, by a coalition being “large,” we meanthat the number of individuals in the coalition is no less than the total population minusk (where k is a natural number given in advance) if the total population is more thank. This restriction is natural because in many real-life situations, power is assigned only
to subgroups larger than a particular size. Although this restriction may seem to reducethe diﬃculty of the problem, as we will prove, this easier version is in fact as diﬃcult
as the original problem if k ≥ 3. We refer to this easier version of the problem as kUNSTABILITY, and its complementary problem as k-STABILITY. Let us deﬁne thisproblem formally. Let a natural number k be given.
Name: k-UNSTABILITY.
Instance: A nonempty ﬁnite set N ; A nonempty collection W = {W1 , · · · , Wm }of nonempty subsets of N with for all i = 1, · · · , m, #Wi ≥ #N −k if #N > k;A nonempty ﬁnite set Ω.
Question: Is the simple game G = (N, W , Ω) not stable?
Obviously, for any k, k-UNSTABILITY≤p UNSTABILITY. Also, it is straightforwardthat if k ′ ≤ k, then k ′ -UNSTABILITY≤p k-UNSTABILITY.
In the following, we prove that 3-UNSTABILITY is NP-complete.
Lemma 1 3-UNSTABILITY is NP-hard.
Proof. The proof is done by reduction from the following known NP-complete problem([SP5] in Garey and Johnson (1979)).
Name: 3-MINIMUM COVER.
Instance: A ﬁnite set S; A nonempty collection C = {C1 , · · · , Cm } of subsets
of S with for all i = 1, · · · , m, #Ci ≤ 3; a natural number r with r ≤ m.
Question: Does there exist a collection D such that D ⊂ C , #D ≤ r, and∪
D = S?
Let an instance (S, C , r) of 3-MINIMUM COVER be given. Let us construct an
instance of 3-UNSTABILITY (i.e. a simple game) G = (N, W , Ω) as follows: Let N :=S ∪ {i⋆ } with i⋆ ̸∈ S. And let W := {N \ C | C ∈ C } ∪ {S} and Ω := {1, 2, · · · , r + 1}.
5Note that N and all elements of W are nonempty since in deﬁning N we have addedi⋆ to S. Also note that for any W ∈ W , it holds i⋆ ∈ W if, and only if, W ̸= S. Clearly, if#N = #S + 1 > 3, then ∀W ∈ W , #W ≥ #N − 3, i.e. W consists of “large” coalitions
only. And we have the following relations:
∪
∩
C =S⇔
W = ∅,(1){}∪∪
C = S ⇒ min #D | D ⊂ C ,D = S + 1 = V (W )(2)
Suppose that the answer to 3-MINIMUM COVER for this instance is “yes.” Then we∪∪
have C = S and min{#D | D ⊂ C ,D = S} ≤ r. This implies that the simple game
constructed in the above is not weak by (1), and that V (W ) ≤ r + 1 = #Ω by (2). Thenby Theorem 1, the simple game is not stable so the answer to 3-UNSTABILITY for thisinstance is “yes.”
Suppose that the answer to 3-UNSTABILITY is “yes,” i.e. the constructed simple
game is not stable. Then by Theorem 1, it follows that the simple game is not weak and∪that V (W ) ≤ #Ω = r + 1. By (1) and (2), this implies C = S and min{#D | D ⊂∪C , D = S} ≤ r, that is, the answer to 3-MINIMUM COVER is “yes.” 2
Lemma 2 UNSTABILITY and k-UNSTABILITY with any k belong to NP.
Proof. Because k-UNSTABILITY≤p UNSTABILITY, it suﬃces to prove UNSTABILITY∈
NP. Let an instance (N, W , Ω) of UNSTABILITY be given. Then by Theorem 1, theanswer to the problem is “yes” for this instance if, and only if, there exists a class of
coalitions σ such that∩∅ ̸= σ ⊂ W ,σ = ∅ and #σ ≤ #Ω.
(3)
Then the class σ constitutes the certiﬁcate. And the time taken to check whether σsatisﬁes (3) grows only linearly. Thus it is checkable in polynomial time. 2
Remark 1 2-UNSTABILITY belongs to P. This is because of the following two facts:(i) There is a polynomial time algorithm for solving “2-MINIMUM COVER,” the naturalvariant of 3-MINIMUM COVER, that is, the problem of checking if there is a cover of
S in the family of subsets C of S with #C ≤ 2 for all C ∈ C . (See [SP5] in Garey andJohnson (1979)); (ii) 2-UNSTABILITY≤p 2-MINIMUM COVER.
From Lemmas 1 and 2, we have the following conclusion.
Theorem 2 UNSTABILITY and k-UNSTABILITY with k ≥ 3 are all NP-complete.
As mentioned in Sec. 2.1 (in the last paragraph), it is unknown if coNP = NP or not.
And if there exists some NP-complete problem whose complementary problem belongs to
NP, then coNP = NP. (Theorem 7.2 in Garey and Johnson (1979) p. 156). Thus it is
not known if STABILITY belongs to NP or not. We have only the following.
Corollary 1 STABILITY and k-STABILITY with k ≥ 3 are all NP-hard.
Recall that in k-UNSTABILITY (and k-STABILITY) we have restricted winning coalitions to “large” coalitions. Now let us consider an alternative formulation of “largeness”

6

of coalitions; we deﬁne “large” coalitions as those which exceed in size some ﬁxed proportion q of the total population. This formulation may be more natural than the one in
k-UNSTABILITY. Let us formally deﬁne this problem. Let a number q with 0 ≤ q < 1
be given.
Name: QUOTAq-UNSTABILITY.
Instance: A nonempty ﬁnite set N ; A nonempty collection W = {W1 , · · · , Wm }of nonempty subsets of N with for all i = 1, · · · , m, #Wi ≥ q#N ; A nonempty
ﬁnite set Ω.
Question: Is the simple game G = (N, W , Ω) not stable?
Corollary 2 For any q with 0 ≤ q < 1, QUOTAq-UNSTABILITY is NP-complete.
Proof. First, we prove UNSTABILITY≤p QUOTAq-UNSTABILITY, which establishes
the NP-hardness of QUOTAq-UNSTABILITY. Let an instance of UNSTABILITY G =(N, W , Ω) be given. Let us construct an instance of QUOTAq-UNSTABILITY G ′ =(N ′ , W ′ , Ω′ ) as follows: Let M be a ﬁnite set disjoint with N such that #M ≥ q(#N +#M ). Let N be the set of coalitions {N ∪ (M \ {j}) | j ∈ M }. Then let N ′ := N ∪ M ,W ′ := {W ∪ M | W ∈ W } ∪ N and Ω′ := {1, 2, · · · , #Ω + #M }.
Note that for any W ∈ W ′ , #W ≥ #M thus #W ≥ q#N ′ i.e. W ′ satisﬁes the quota∩
condition. N is constructed in the way that N = N but the intersection of any proper
subset N ′ of N contains not only N but some elements of M . On the other hand, clearly,
each element W in W corresponds to the element W ∪M in W ′ \N . Thus for any σ ⊂ W ,∩∩∩there is the natural counterpart σ ′ ⊂ W ′ \ N , and it holds σ ′ = σ ∪ M . Thus σ = ∅∩∩if, and only if, ( σ ′ ) ∩ ( N ) = ∅. Note that #N = #M . Therefore, if G and G ′ arenot weak, thenV (W ) + #M = V (W ′ ).

(4)Also, G is weak if, and only if, G ′ is weak,Suppose that the answer to the UNSTABILITY instance is “yes.” That is, G is notstable, i.e. by Theorem 1, G is not weak and V (W ) ≤ #Ω. Then it is immediate that G ′is not weak, and the relation (4) implies V (W ′ ) ≤ #Ω′ . Thus G ′ is not stable, i.e. theanswer to the QUOTAq-UNSTABILITY instance is “yes.” Next, suppose that the answer
to the QUOTAq-UNSTABILITY instance is “yes.” Then similarly to the above case, wehave that the answer to the UNSTABILITY instance is “yes.”
Second, we show QUOTAq-UNSTABILITY ∈ NP. This is immediate from QUOTAqUNSTABILITY≤p UNSTABILITY, and UNSTABILITY ∈ NP by Lemma 2. Therefore,
we conclude that the problem is NP-complete. 2

4

Related studies

Remark 2 Many works examine those computational problems which arise in various
models of coalitional games when preferences are given. For example, some studies consider
the problem of determining whether the core is nonempty, or whether a given outcome isin the core (e.g. Conitzer and Sandholm 2006, Kumabe and Mihara 2008b). The present
work should be carefully distinguished from this type of research. Our problems ask todetermine whether a given game is such that the core is nonempty for every combinationof preferences, not a given combination of preferences.
7Remark 3 Bartholdi, Narasimhan and Tovey (1991) is related to our work. Whereas
our interest is in simple games, a general model, they study spatial voting games, a more
speciﬁc model. They show that it is an NP-complete problem to check the unstabilityof q-weighted majority voting games. This class of voting games is a subclass of simple
games. However, the NP-hardness of UNSTABILITY, one of our results, is not immediatefrom their result because their games have a diﬀerent representation: In their problem of
the unstability of q-weighted majority voting games, the instance of the problem is a listof weights assigned to individuals and the quota q. The size of these data grows only in
linear order as the number of individuals gets larger. On the other hand, in our problem
UNSTABILITY, the instance is the list of winning coalitions, which grows exponentially.
Remark 4 One may object that the simple game is too simple a representation of power
distribution. The “eﬀectivity function,” which is a generalization of the simple game,is a more elaborate expression of power distribution. The computational complexity ofdetermining the unstability of eﬀectivity functions was proved to be NP-complete by
Mizutani, Hiraide and Nishino (1993) and Boros and Gurvich (2000). Similarly to thecase in Remark 3, eﬀectivity functions have a diﬀerent representation from simple games
thus their result has no direct relations to ours.
Acknowledgments The authors are grateful to H Reiju Mihara, Takuma Wakayama, Akira Yamada and Kazuyuki Yamauchi for useful comments, and also thank the participants of the seminar
at Sapporo University. This research is partially supported by Grant-in-Aid for Scientiﬁc Researchof the Ministry of Education, Culture, Sports, Science and Technology of Japan No.23730188. Allerrors are our own responsibility.

References[1] Abdou JM (2010): The structure of unstable power mechanisms, Economic Theory 50: 389–
415.
[2] Arora S, Barak B (2009): Computational Complexity: A Modern Approach, Cambridge University Press.
[3] Aziz H, Paterson M, Leech D (2007): Eﬃcient algorithm for designing weighted voting games,
INMIC 2007, Proceedings of the IEEE Computer Society, 11th IEEE International Multitopic
Conference.
[4] Bartholdi III JJ, Narasimhan LS, Tovey CA (1991): Recognizing majority-rule equilibrium inspatial voting game, Social Choice and Welfare 8: 183–97.
[5] Conitzer V, Sandholm T (2006): Complexity of constructing solutions in the core based onsynergies among coalitions, Artificial Intelligence 170: 607–19.
[6] Boros E, Gurvich V (2000): Stable eﬀectivity functions and perfect graphs, Mathematical
Social Sciences 39: 175–94.
[7] Cook S (2000): The P versus NP problem, Clay Mathematics Institute. available at http://www.claymath.org/millennium/P vs NP/Official Problem Description.pdf[8] Garey MR, Johnson DS (1979): Computers and Intractability: A Guide to the Theory of
NP-completeness, WH Freeman, New York.
[9] Kumabe M, Mihara HR (2008a): The Nakamura numbers for computable simple games, Social
Choice and Welfare, 31: 621–40.

8[10] Kumabe M, Mihara HR (2008b): Computability of simple games: a characterization andapplication to the core, Journal of Mathematical Economics, 44: 348–66.
[11] Mizutani M, Hiraide Y, Nishino H (1993): Computational complexity to verify the unstabilityof eﬀectivity function, International Journal of Game Theory 22: 225–39.
[12] Nakamura K (1975): The core of a simple game with ordinal preferences, International Journalof Game Theory 4: 95–104.
[13] Nakamura K (1979): The vetoer in a simple game with ordinal preferences, International
Journal of Game Theory 8: 55–61.
[14] Razaﬁmahatolotra D (2009): Une contribution à la théorie du pouvoir :Négociation et Stabilité, PhD dissertation, Université Paris 1.

9

Conflits —