Computational complexity in the design of voting rules

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 to decide whether a given simple game is stable, or not.

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 reflect the distribution of “decision power” within the group specified in advance. For example, in a stockholders’ meeting, it is usually required that the larger the share one has, the bigger the “decision power” the one 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 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 be desirable for the group to have decision rules like the latter.

In this paper, we adopt the formulation in terms of simple games. A simple game represents a “power distribution” in the group in a very simple way: each subgroup is categorized as “powerful” or “not powerful.” Formally, a simple game is the list of the subgroups that are labeled “powerful.”

Provided that the power distribution is given by a simple game, let us consider the two requirements which we imposed on the voting rule in the above. To meet the first 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 effective oppositions given the power structure described by the simple game. To fulfill the second requirement, the core has to be nonempty for every combination of preferences that 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 game is 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 also in the special case in which the set of “powerful” subgroups consists only of “large” subgroups. Restricting “powerful” subgroups to “large” ones is natural 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 and sufficient condition for stability.

The significance of our results is that they cast a practical limit on the availability of stable voting rules. Our results suggest that there would be some cases in which the designer 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 from known results. Nonetheless, we consider our results important in that they answer some basic 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-completeness

For those not familiar with computational complexity, the following is only a brief and informal 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).

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 instance refers 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.”¹ Then we say that the problem belongs to the class $\mathbf{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 question is bounded by some fixed polynomial in the size of the instance (the length of the input).

We say that the problem belongs to the class $\mathbf{NP}$ if there is an algorithm that verifies the answer to the problem in polynomial time, that is, if there is a polynomial-time algorithm such that for any given instance, the answer to the question is “yes” if, and only if, there is a certain additional input, called a certificate, with which this algorithm outputs “yes.” Here the certificate has to be a polynomial length in the size of the instance.

It is straightforward that $\mathbf{P} \subset \mathbf{NP}$. At the present time, however, it is unknown whether $\mathbf{P} = \mathbf{NP}$, or not. This is one of the fundamental problems in computer science and mathematics. (See Cook (2000)). It is widely believed that $\mathbf{P} \not = \mathbf{NP}$.

Let $L_1$ and $L_2$ be problems. We say that $L_1$ is polynomial-time reducible to $L_2$ if

• (i) there exists a function f that transforms any instance x of $L _1$ into the instance f(x) of $L _2$ such that the answer to $L_1$ for the instance x is “yes” if, and only if, the answer to $L_2$ for the instance f(x) is “yes,” and

• (ii) the function f is embodied by a polynomial-time algorithm.

Intuitively, $L_2$ is at least as hard as $L_1$; if you can solve $L_2$, then you can also solve $L_1$ by transforming the instances of $L_1$ into those of $L_2$, and the transformation itself is not difficult. Denote this relation by $L_1 \le _p L_2$. Note that $\le _p$ is transitive.

A problem $L_1$ is called NP-hard if for any $L_2 \in \mathbf{NP}, L_2\le _p L_1$. Further, $L_1$ is called NP-complete if $L_1$ is NP-hard and $L_1 \in \mathbf{NP}$. Intuitively, a problem being NP-complete means 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 $L_1$ is NP-hard is reduction. This is done by the following steps:

• (i) Specify a known NP-complete problem $L_2$.

• (ii) Show $L_2 \le _p L_1$ by giving a concrete polynomial-time transformation.

To prove $L_1$ is NP-complete, we additionally show $L_1\in \mathbf {NP}$. We will utilize this method in the sequel.

Given a problem L, the complementary problem $\bar{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 $\exists x: p(x)$, then $\bar{L}$ asks if $\forall x, \lnot p(x)$. First, we note that if a problem L is NP-complete, then $\bar{L}$ is NP-hard since L is reducible to $\bar{L}$ (i.e., $L \le _p \bar{L}$) by flipping the output. Let $\mathbf{coNP}$ denote the set of problems L for which ${\bar{L}} \in \mathbf{NP}$. It holds true that $\mathbf{P} \subset \mathbf{coNP}$. It is an open problem whether $\mathbf{coNP}=\mathbf{NP}$ or not. In fact, this is related to the $\mathbf{P}=\mathbf{NP}$ problem: $\mathbf{coNP} \not = \mathbf{NP}$ implies $\mathbf{P}\not =\mathbf{NP}$. Further, if there exists an NP-complete problem L such that ${\bar{L}} \in \mathbf{NP}$, then $\mathbf{coNP}=\mathbf{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 $\mathbf{NP}$ or not.

2.2 Simple games

A simple game is a list ${\mathscr {G}}=(N, {\mathscr {W}}, \Omega )$. Here N is a nonempty finite set of individuals. A coalition is a nonempty subset of N. ${\mathscr {W}}$ is a nonempty class of coalitions. Any element of ${\mathscr {W}}$ is called a winning coalition. $\Omega$ is a nonempty finite set of alternatives.

A preference relation of individual $i \in N$ is an acyclic binary relation $\succ ^i$ on $\Omega$.² For $x,y \in \Omega$, $x \succ ^i y$ means “i strictly prefers x to y.” We denote a combination of preferences of all individuals $(\succ ^i)_{i \in N}$ by $\succ$.

Let a simple game and a combination of preferences $({\mathscr {G}}, \succ )$ be given. Let $x, y \in \Omega$. Then we say that x is blocked by S with y if

$$\begin{aligned} \forall i \in S,\ y \succ ^i x. \end{aligned}$$

The core of $({\mathscr {G}}, \succ )$ is the set of alternatives which are not blocked by any coalitions with any alternatives.

A simple game ${\mathscr {G}}$ is called stable if the core of $({\mathscr {G}}, \succ )$ is nonempty for any combination of preferences $\succ$. One of the fundamental questions in the theory of simple games is whether a given simple game is stable, or not. Nakamura (1979) gave the answer to this question by providing a necessary and sufficient condition for stability in terms of the “Nakamura number.”

Call a simple game ${\mathscr {G}}$ weak if $\bigcap {\mathscr {W}} \not = \emptyset$. Let ${\mathscr {G}}$ be a simple game which is not weak. Then the Nakamura number ${\mathscr {V}}({\mathscr {W}})$ of ${\mathscr {G}}$ is

$$\begin{aligned} {\mathscr {V}}({\mathscr {W}}) =\min \Bigl \{ \#\sigma \mid \emptyset {\not =} \sigma \subset {\mathscr {W}}, \ \bigcap \sigma = \emptyset \Bigr \}. \end{aligned}$$

We will utilize the following well-known theorem for proving our results.

Theorem 1

(Nakamura 1979) Let a simple game ${\mathscr {G}}=(N, {\mathscr {W}}, \Omega )$ be given. Then ${\mathscr {G}}$ is stable if, and only if, (i) ${\mathscr {G}}$ is weak, or (ii) $\#\Omega < {\mathscr {V}}({\mathscr {W}})$.

For a general and comprehensive analysis of the Nakamura number, consult Kumabe and Mihara (2008a).

3 Results

Let us define the problem that we will examine.

Name: UNSTABILITY.

Instance: A nonempty finite set N; A nonempty collection ${\mathscr {W}}=\{ W_{1} , \cdots ,W_{m} \}$ of nonempty subsets of N; A nonempty finite set $\Omega$.

Question: Is the simple game ${\mathscr {G}}=(N, {\mathscr {W}}, \Omega )$ not stable?

Note that the question in the above problem is asking whether the simple game is not stable, 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 think that STABILITY, rather than UNSTABILITY, is the natural question to ask. However, as we will see, here we cannot decide whether STABILITY belongs to $\mathbf{NP}$, or not, whereas we prove that UNSTABILITY is in $\mathbf{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, winning coalitions are restricted to “large” coalitions. Here, by a coalition being “large,” we mean that the number of individuals in the coalition is no less than the total population minus k (where k is a natural number given in advance) if the total population is more than k. 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 reduce the difficulty of the problem, as we will prove, this easier version is in fact as difficult as the original problem if $k \ge 3$. We refer to this easier version of the problem as k-UNSTABILITY, and its complementary problem as k-STABILITY. Let us define this problem formally. Let a natural number k be given.

Name: k-UNSTABILITY.

Instance: A nonempty finite set N; A nonempty collection ${\mathscr {W}}=\{ W_{1} , \cdots ,W_{m} \}$ of nonempty subsets of N with for all $i =1, \cdots , m, \#W_{i} \ge \#N-k$ if $\#N > k$; A nonempty finite set $\Omega$.

Question: Is the simple game ${\mathscr {G}}=(N, {\mathscr {W}}, \Omega )$ not stable?

Obviously, for any k, k-UNSTABILITY$\le _p$UNSTABILITY. Also, it is straightforward that if $k' \le k$, then $k'$-UNSTABILITY$\le _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 finite set S; A nonempty collection ${\mathscr {C}}=\{ C_{1} , \cdots ,C_{m} \}$ of subsets of S with for all $i=1, \cdots , m, \#C_{i} \le 3$; a natural number r with $r \le m$.

Question: Does there exist a collection ${\mathscr {D}}$ such that ${\mathscr {D}} \subset {\mathscr {C}}, \#{\mathscr {D}} \le r$, and $\bigcup {\mathscr {D}} = S$?

Let an instance $(S, {\mathscr {C}}, r)$ of 3-MINIMUM COVER be given. Let us construct an instance of 3-UNSTABILITY (i.e., a simple game) ${\mathscr {G}}=(N, {\mathscr {W}}, \Omega )$ as follows: Let $N:=S \cup \{ i^{\star } \}$ with $i ^{\star } \not \in S$. And let ${\mathscr {W}}:= \{N \setminus C \mid C \in {\mathscr {C}} \} \cup \{ S \}$ and $\Omega : =\{ 1,2, \cdots , r+1 \}$.

Note that N and all elements of ${\mathscr {W}}$ are nonempty since in defining N we have added $i^{\star }$ to S. Also note that for any $W \in {\mathscr {W}}$, it holds $i^{\star } \in W$ if, and only if, $W \ne S$. Clearly, if $\#N=\#S+1 >3$, then $\forall W \in {\mathscr {W}}, \ \#W \ge \#N-3$, i.e., ${\mathscr {W}}$ consists of “large” coalitions only. And we have the following relations:

$$\begin{aligned}&\displaystyle \bigcup {\mathscr {C}} = S \Leftrightarrow \bigcap {\mathscr {W}} = \emptyset ,&\end{aligned}$$

(1)

$$\begin{aligned}&\displaystyle \bigcup {\mathscr {C}} = S \Rightarrow \min \Bigl \{ \#{\mathscr {D}} \mid {\mathscr {D}} \subset {\mathscr {C}}, \quad \ \bigcup {\mathscr {D}} =S \Bigr \}+1 = {\mathscr {V}}({\mathscr {W}})&\end{aligned}$$

(2)

Suppose that the answer to 3-MINIMUM COVER for this instance is “yes.” Then we have $\bigcup {\mathscr {C}}=S$ and $\min \{ \#{\mathscr {D}} \mid {\mathscr {D}} \subset {\mathscr {C}}, \ \bigcup {\mathscr {D}} =S \}\le r$. This implies that the simple game constructed in the above is not weak by (1), and that ${\mathscr {V}}({\mathscr {W}}) \le r+1=\#\Omega$ by (2). Then by Theorem 1, the simple game is not stable so the answer to 3-UNSTABILITY for this instance 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 ${\mathscr {V}}({\mathscr {W}}) \le \#\Omega =r+1$. By (1) and (2), this implies $\bigcup {\mathscr {C}}=S$ and $\min \{ \#{\mathscr {D}} \mid {\mathscr {D}} \subset {\mathscr {C}}, \ \bigcup {\mathscr {D}} =S \}\le r$, that is, the answer to 3-MINIMUM COVER is “yes.” $\square$

Lemma 2

UNSTABILITY and k-UNSTABILITY with any k belong to $\mathbf NP$.

Proof

Because k-UNSTABILITY$\le _p$UNSTABILITY, it suffices to prove UNSTABILITY $\in \mathbf{NP}$. Let an instance $(N, {\mathscr {W}}, \Omega )$ of UNSTABILITY be given. Then by Theorem 1, the answer to the problem is “yes” for this instance if, and only if, there exists a class of coalitions $\sigma$ such that

$$\begin{aligned} \emptyset \not = \sigma \subset {\mathscr {W}}, \quad \ \bigcap \sigma = \emptyset \mathrm{\quad \ and\ } \quad \#\sigma \le \#\Omega . \end{aligned}$$

(3)

Then the class $\sigma$ constitutes the certificate. And the time taken to check whether $\sigma$ satisfies (3) grows only linearly. Thus it is checkable in polynomial time. $\square$

Remark 1

2-UNSTABILITY belongs to $\mathbf{P}$. This is because of the following two facts: (i) There is a polynomial time algorithm for solving “2-MINIMUM COVER,” the natural variant of 3-MINIMUM COVER, that is, the problem of checking if there is a cover of S in the family of subsets ${\mathscr {C}}$ of S with $\#C \le 2$ for all $C \in {\mathscr {C}}$. (See [SP5] in Garey and Johnson (1979)); (ii) 2-UNSTABILITY$\le _p 2$-MINIMUM COVER.

From Lemmas 1 and 2, we have the following conclusion.

Theorem 2

UNSTABILITY and k-UNSTABILITY with $k \ge 3$ are all NP-complete.

As mentioned in Sect. 2.1 (in the last paragraph), it is unknown if $\mathbf{coNP}=\mathbf{NP}$ or not. And if there exists some NP-complete problem whose complementary problem belongs to $\mathbf{NP}$, then $\mathbf{coNP}=\mathbf{NP}$. (Theorem 7.2 in Garey and Johnson (1979) p. 156). Thus it is not known if STABILITY belongs to $\mathbf{NP}$ or not. We have only the following.

Corollary 1

STABILITY and k-STABILITY with $k\ge 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” of coalitions; we define “large” coalitions as those which exceed in size some fixed proportion q of the total population. This formulation may be more natural than the one in k-UNSTABILITY. Let us formally define this problem. Let a number q with $0 \le q <1$ be given.

Name: QUOTAq-UNSTABILITY.

Instance: A nonempty finite set N; A nonempty collection ${\mathscr {W}}=\{ W_{1} , \cdots ,W_{m} \}$ of nonempty subsets of N with for all $i =1, \cdots , m, \#W_{i} \ge q\#N$; A nonempty finite set $\Omega$.

Question: Is the simple game ${\mathscr {G}}=(N, {\mathscr {W}}, \Omega )$ not stable?

Corollary 2

For any q with $0\le q <1$, QUOTA q -UNSTABILITY is NP-complete.

Proof

First, we prove UNSTABILITY$\le _p$QUOTAq-UNSTABILITY, which establishes the NP-hardness of QUOTAq-UNSTABILITY. Let an instance of UNSTABILITY ${\mathscr {G}} = (N, {\mathscr {W}}, \Omega )$ be given. Let us construct an instance of QUOTAq-UNSTABILITY ${\mathscr {G}}' = (N', {\mathscr {W'}}, \Omega ')$ as follows: Let M be a finite set disjoint with N such that $\#M \ge q (\#N+\#M)$. Let ${\mathscr {N}}$ be the set of coalitions $\{ N \cup (M \setminus \{ j \}) \mid j \in M \}$. Then let $N':=N \cup M, {\mathscr {W'}}:=\{ W \cup M \mid W \in {\mathscr {W}} \} \cup {\mathscr {N}}$ and $\Omega ' := \{1,2, \cdots , \#\Omega +\#M \}$.

Note that for any $W \in {\mathscr {W'}}$, $\#W \ge \#M$ thus $\#W \ge q \#N'$ i.e., ${\mathscr {W'}}$ satisfies the quota condition. ${\mathscr {N}}$ is constructed in the way that $\bigcap {\mathscr {N}}=N$ but the intersection of any proper subset ${\mathscr {N'}}$ of ${\mathscr {N}}$ contains not only N but also some elements of M. On the other hand, clearly, each element W in ${\mathscr {W}}$ corresponds to the element $W \cup M$ in ${\mathscr {W'}} \setminus {\mathscr {N}}$. Thus for any $\sigma \subset {\mathscr {W}}$, there is the natural counterpart $\sigma ' \subset {\mathscr {W'}} \setminus {\mathscr {N}}$, and it holds $\bigcap \sigma ' = \bigcap \sigma \cup M$. Thus $\bigcap \sigma = \emptyset$ if, and only if, $(\bigcap \sigma ' ) \cap (\bigcap {\mathscr {N}}) =\emptyset$. Note that $\#{\mathscr {N}}=\#M$. Therefore, if ${\mathscr {G}}$ and ${\mathscr {G}}'$ are not weak, then

$$\begin{aligned} {\mathscr {V}} ({\mathscr {W}}) +\#M = {\mathscr {V}} ({\mathscr {W'}}). \end{aligned}$$

(4)

Also, ${\mathscr {G}}$ is weak if, and only if, ${\mathscr {G}}'$ is weak,

Suppose that the answer to the UNSTABILITY instance is “yes.” That is, ${\mathscr {G}}$ is not stable, i.e., by Theorem 1, ${\mathscr {G}}$ is not weak and ${\mathscr {V}}({\mathscr {W}}) \le \#\Omega$. Then it is immediate that ${\mathscr {G}}'$ is not weak, and the relation (4) implies ${\mathscr {V}}({\mathscr {W'}}) \le \#\Omega '$. Thus ${\mathscr {G}}'$ is not stable, i.e., the answer 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, we have that the answer to the UNSTABILITY instance is “yes.”

Second, we show QUOTAq-UNSTABILITY $\in \mathbf{NP}$. This is immediate from QUOTAq-UNSTABILITY$\le _p$UNSTABILITY, and UNSTABILITY $\in \mathbf{NP}$ by Lemma 2. Therefore, we conclude that the problem is NP-complete. $\square$

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 is in 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 to determine whether a given game is such that the core is nonempty for every combination of preferences, not a given combination of preferences.

Remark 3

Bartholdi et al. (1991) is related to our work. Whereas our interest is in simple games, a general model, they study spatial voting games, a more specific model. They show that it is an NP-complete problem to check the unstability of 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 immediate from their result because their games have a different representation: In their problem of the unstability of q-weighted majority voting games, the instance of the problem is a list of 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 “effectivity function,” which is a generalization of the simple game, is a more elaborate expression of power distribution. The computational complexity of determining the unstability of effectivity functions was proved to be NP-complete by Mizutani et al. (1993) and Boros and Gurvich (2000). Similarly to the case in Remark 3, effectivity functions have a different representation from simple games thus their result has no direct relations to ours.