Bounds for the Nakamura number

Abstract

The Nakamura number is an appropriate invariant of a simple game to study the existence of social equilibria and the possibility of cycles. For symmetric (quota) games its number can be obtained by an easy formula. For some subclasses of simple games the corresponding Nakamura number has also been characterized. However, in general, not much is known about lower and upper bounds depending on invariants of simple, complete or weighted games. Here, we survey such results and highlight connections with other game theoretic concepts.

1 Introduction

Consider a committee with a finite set N of committee members. Suppose that a subset S of the committee members, is in favor of variant A of a certain proposal, while all others, i.e., those in $N\backslash S$, are in favor of variant B. If the committee’s decision rule is such that both S and $N\backslash S$ can change the status quo, then we may end up in an infinite chain of status quo changes between variant A and variant B—a very unpleasant and unstable situation. In the context of simple games the described situation can be prevented easily. Here, a simple game is a mapping from the set of subsets of committee members, called coalitions, into $\{0,1\}$, where “1” means to accept a proposal and “0” to defeat it. In the latter case we call the coalition winning. In order to ensure “stability”, one just has to restrict the allowed class of voting systems to proper simple games, i.e., each two winning coalitions have at least one common player. As a generalization, the Nakamura number of a simple game is the smallest number k such that there exist k winning coalitions with empty intersection, see Sect. 2 for more details. So, a simple game is proper if and only if its Nakamura number is at least 3. Indeed, the Nakamura number turned out to be an appropriate invariant of a simple game to study the existence of social equilibria and the possibility of cycles in a more general setting, see Schofield (1984). As the author remarks, individual convex preferences are insufficient to guarantee convex social preferences. If, however, the Nakamura number of the used decision rule is large enough, with respect to the dimension of the involved policy space, then convex individual preferences guarantee convex social preferences. Having this relation at hand, a stability result of Greenberg (1979) on q-majority games boils down to the computation of the Nakamura number for these games. The original result of Nakamura (1979) gives a necessary and sufficient condition for the non-emptiness of the core of a simple game obtained from individual preferences. Further stability results in terms of the Nakamura number are e.g. given by Le Breton and Salles (1990). A generalization to coalition structures can be found in Deb et al. (1996). For other notions of stability and acyclicity we refer e.g. to Martin (1998), Schwartz (2001) and Truchon (1996). Unifications of related theorems have been presented by Saari (2014). Complexity results for the computation of the Nakamura number can e.g. be found in Bartholdi et al. (1991) and Takamiya and Tanaka (2016). There is a loose connection to the capacity of a committee, see Holzman (1986) and Peleg (2008).

Here we study lower and upper bounds for the Nakamura number of different types of voting games. The mentioned q-majority games, see Greenberg (1979), consist of n symmetric players and are therefore also called symmetric (quota) games. The quota q is the number of necessary players for a coalition to pass a proposal, i.e., coalitions with at least q members are winning. For those games the Nakamura number was analytically determined to be $\left\lceil \frac{n}{n-q}\right\rceil$ by Ferejohn and Grether (1974) and Peleg (1978). For $n=5$ and $q=3$ the Nakamura number is given by 3, i.e., every two winning coalitions intersect in at least one player and e.g. the winning coalitions $\{1,2,3\}$, $\{3,4,5\}$, and $\{1,2,4,5\}$ have an empty intersection. The Nakamura number for two-stage voting games, has been determined by Peleg (1987).

Kumabe and Mihara (2008) studied the 32 combinations of five properties of simple games. In each of the cases the authors determined the generic Nakamura number or the best possible lower bound if several values can be attained. As a generalization of simple games with more than two alternatives, the so-called (j, k)-simple games have been introduced, see e.g. Freixas and Zwicker (2003). The notion of the Nakamura number and a first set of stability results for (j, 2)-simple games have been transfered by Tchantcho et al. (2010).

The remaining part of the paper is organized as follows. In Sect. 2 we state the necessary preliminaries. Integer linear programming formulations for theexact computation of the Nakamura number are presented in Sect. 3. Bounds for the Nakamura number of weighted games, generalizing the result of Ferejohn and Grether (1974) and Peleg (1978), are studied in Sect. 4. The more general class of simple games is treated in Sect. 5. The maximum possible Nakamura number within specialsubclasses of simple games is the topic of Sect. 6. Further relation of the Nakamura number to other concepts of cooperative game theory are discussed in Sect. 7. In this context the one-dimensional cutting stock problem is treated in Sect. 7.1. We close with a conclusion in Sect. 8.

2 Preliminaries

A pair $(N,v)$ is called simple game if N is a finite set, $v:2^N\rightarrow \{0,1\}$ satisfies $v(\emptyset )=0$, $v(N)=1$, and $v(S)\le v(T)$ for all $S\subseteq T\subseteq N$. The subsets of N are called coalitions and N is called the grand coalition. By $n=|N|$ we denote the number of players in N. If $v(S)=1$, we call S a winning coalition and a losing coalition otherwise. By $\mathcal {W}$ we denote the set of winning coalitions and by $\mathcal {L}$ the set of losing coalitions. If S is a winning coalition such that each proper subset is losing we call S a minimal winning coalition. Similarly, if T is a losing coalition such that each proper superset is winning, we call T a maximal losing coalition. By $\mathcal {W}^m$ we denote the set of minimal winning coalitions and by $\mathcal {L}^M$ we denote the set of maximal losing coalitions. We remark that each of the sets $\mathcal {W}$, $\mathcal {L}$, $\mathcal {W}^m$ or $\mathcal {L}^M$ uniquely characterizes a simple game. Instead of $(N,v)$ we also write $(N,\mathcal {W})$ for a simple game.

Example 1

A k-out-of-n game is a simple game $(N,\mathcal {W})$ with $N=\{1,\dots ,n\}$ and $\mathcal {W}=\{S\subseteq N\,:\, |S|\ge k\}$. For $k=2$ and $n=3$ coalition $\{1,2,3\}$ is winning but not minimal winning. Similarly, coalition $\emptyset$ is losing but not maximal losing.

A simple game $(N,\mathcal {W})$ is called proper if the complement $N\backslash S$ of any winning coalition $S\in \mathcal {W}$ is losing. It is called strong if the complement $N\backslash T$ of any losing coalition T is winning. A simple game that is both proper and strong is called constant-sum (or self-dual or decisive). An example of a constant-sum simple game is given by the 2-out-of-3 game.

A simple game $(N,v)$ is weighted if there exists a quota$q>0$ and weights$w_i\ge 0$ for all $1\le i\le n$ such that $v(S)=1$ if and only if $w(S)=\sum _{i\in S} w_i\ge q$ for all $S\subseteq N$. As notation we use $[q;w_1,\dots ,w_n]$ for a weighted game. For some examples we need many players with the same weight. To this end we write $\left[ q;{w_1}^{\{a_1\}},\dots ,{w_k}^{\{a_k\}}\right]$ for a weighted game with $a_i$ players of weight $w_i$ for $1\le i\le k$. A weighted representation of k-out-of-n games is given by $\left[ k;{1}^{\{n\}}\right]$ or $[k;1,\dots ,1]$ with n times weight 1. We remark that weighted representations are far from being unique. In any case there exist some special weighted representations. By $\left[ \hat{q};\hat{w}_1,\dots ,\hat{w}_n\right]$ we denote a weighted representation, where all weights and the quota are integers. Instead of specializing to integers we can also normalize the weights to sum to one. By $\left[ q';w'_1,\dots ,w'_n\right]$ we denote a weighted normalized representation with $q'\in (0,1]$ and $w'(N):=\sum _{i\in N} w'_i=1$. For the existence of a normalized representation we remark that not all weights can be equal to zero, since $\emptyset$ is a losing coalition.

There exists a relaxation of the notion of a weighted game. A simple game $(N,\mathcal {W})$ is $\alpha$-roughly weighted if there exist non-negative weights $w_1,\dots ,w_n$ such that each winning coalition S has a weight w(S) of at least 1 and each losing coalition T has a weight of at most $\alpha$. Weighted games are exactly those that permit an $\alpha <1$. 1-roughly weighted games are also called roughly weighted games in the literature.

Let $(N,v)$ be a simple game. A player $i\in N$ such that $i\in S$ for all winning coalitions S is called a vetoer. Each player $i\in N$ that is not contained in any minimal winning coalition is called a null player. If $\{i\}$ is a winning coalition, we call player ipasser. If $\{i\}$ is the unique minimal winning coalition, then we call player i a dictator. Note that a dictator is the strongest form of being both a passer and a vetoer. Obviously, there can be at most one dictator.

Next we consider notation that is beneficial for simple games with many equivalent players. Let $(N,v)$ be a simple game. We write $i\sqsupset j$ (or $j \sqsubset i$) for two agents $i,j\in N$ if we have $v(\{i\}\cup S\backslash \{j\})\ge v(S)$ for all $\{j\}\subseteq S\subseteq N\backslash \{i\}$ and we abbreviate $i\sqsupset j$, $j\sqsupset i$ by $i\square j$. Two players $i,j\in N$ with $i\square j$ are called equivalent. The relation $\square$ partitions the set of players N into equivalence classes$N_1,\dots ,N_t$. For [4; 5, 4, 2, 2, 0] we have $N_1=\{1,2\}$, $N_2=\{3,4\}$, and $N_3=\{5\}$. Obviously, players having the same weight are contained in the same equivalence class, while the converse is not necessarily true. But there always exists a different weighted representation of the same game such that the players of each equivalence class have the same weight, i.e., [2; 2, 2, 1, 1, 0] in our example. The simple games with a unique equivalence class of players are exactly the k-out-of-n games, see Example 1. They are also called symmetric (quota) games or q-majority games.

The set of winning or minimal winning coalitions can be quite numerous. Based on the equivalence classes of players we can state a more compact description if there are some equivalent players. Let $(N,\mathcal {W})$ be a simple game with equivalence classes $N_1,\dots ,N_t$. A coalition vector is a vector $c=(c_1,\dots ,c_t)\in \mathbb {N}_{\ge 0}^t$ with $0\le c_i\le \left| N_i\right|$ for all $1\le i\le t$. The coalition vector of a coalition S is given by $\left( \left| S\cap N_1\right| ,\dots ,\left| S\cap N_t\right| \right)$. A coalition vector is called winning if the corresponding coalitions are winning and losing otherwise. If the corresponding coalitions are minimal winning or maximal losing the coalition vector itself is called minimal winning or maximal losing. The number of equivalence classes of players is denoted by t throughout.

Example 2

For the weighted game [7; 3, 3, 3, 1, 1, 1], with two types of players, the minimal winning coalitions are given by $\{1,2,3\}$, $\{1,2,4\}$, $\{1,2,5\}$, $\{1,2,6\}$, $\{1,3,4\}$, $\{1,3,5\}$, $\{1,3,6\}$, $\{2,3,4\}$, $\{2,3,5\}$, and $\{2,3,6\}$. The minimal winning (coalition) vectors are given by (3, 0) and (2, 1), where $N_1=\{1,2,3\}$ and $N_2=\{4,5,6\}$.

In between weighted games and simple games there is the important subclass of complete simple games. A simple game $(N,\mathcal {W})$ is called complete if the binary relation $\sqsupset$ is a total preorder, i.e., $i\sqsupset i$ for all $i\in N$, $i\sqsupset j$ or $j\sqsupset i$ for all $i,j\in N$, and $i\sqsupset j$, $j\sqsupset h$ implies $i\sqsupset h$ for all $i,j,h\in N$. All weighted games are obviously complete since $w_i\ge w_j$ implies $i\sqsupset j$. For two non-equivalent players we write $i\boxtimes j$. A coalition S of a complete simple game is called shift-minimal winning if S is minimal winning and $S\backslash \{i\}\cup \{j\}$ is losing for all $i\in S$ and $j\in N\backslash S$ with $i\sqsupset j$ and $i\boxtimes j$. Similarly, S is called shift-maximal losing if S is maximal losing and $S\backslash \{i\}\cup \{j\}$ is winning for all $i\in S$ and $j\in N\backslash S$ with $j\sqsupset i$ and $i\boxtimes j$. The intuition is that the players are ordered by $\sqsupset$ according to their “importance”. A shift-minimal winning coalition is a winning coalition where no player can be removed and no player can be replaced by a strictly “weaker” player without turning the coalition into a losing one. In [7; 3, 3, 3, 1, 1, 1], see Example 2, the coalitions $\{1,2,4\}$ and $\{1,3,5\}$ are shift-minimal winning while coalition $\{1,2,3\}$ is minimal winning but not shift-minimal winning. Of course the notion of coalition vectors can also be used for complete simple games. In a complete simple game we always assume $i\sqsupset j$ for all $i\in N_a$ and $l\in N_b$ with $a<b$, i.e., the equivalence classes are numbered with decreasing importance. For two vectors $u,v\in \mathbb {N}_{\ge 0}^t$ we write $u\preceq v$ if $\sum _{j=1}^i u_j\le \sum _{j=1}^i v_j$ for all $1\le i\le t$. We call $\preceq$ the shift-relation. If neither $u\preceq v$ nor $v\preceq u$, we write $u\bowtie v$. We call a winning coalition vector ushift-minimal winning if all coalition vectors $v\preceq u$, $v\ne u$ ($v\prec u$ for short) are losing. Similarly, we call a losing vector ushift-maximal losing if all coalition vectors $u\prec v$ are winning. Of course, coalitions corresponding to a shift-minimal winning vector are shift-minimal winning.

For [7; 3, 3, 3, 1, 1, 1], see Example 2, the vector (2, 1) is shift-minimal winning and (3, 0) is not shift-minimal winning, since one player of type 1 can be shifted to be of type 2 without losing the property of being a winning vector. Complete simple games are uniquely characterized by their count vector $\tilde{n}=(\left| N_1\right| ,\dots ,\left| N_t\right| )$ and their matrix $\tilde{M}$ of shift-minimal winning vectors, see Carreras and Freixas (1996) for a corresponding characterization theorem. In Example 2 we have $\tilde{n}=(3,3)$, $\tilde{M}=\begin{pmatrix}2&1\end{pmatrix}$. The corresponding matrix of shift-maximal losing vectors is given by $\tilde{L}=\begin{pmatrix}2&{}0\\ 1&{}3\end{pmatrix}$. By $\tilde{m}_1,\dots ,\tilde{m}_r$ we denote the shift-minimal winning vectors, i.e., the rows of $\tilde{M}$.

Definition 1

Given a simple game $(N,\mathcal {W})$ its Nakamura number, cf. Nakamura (1979), $\nu (N,\mathcal {W})$ is given by the minimum number of winning coalitions whoseintersection is empty. If the intersection of all winning coalitions is non-empty we set $\nu (N,\mathcal {W})=\infty$.

It is well-known that there exist $\nu (N,\mathcal {W})$ minimal winning coalitions with empty intersection if $\nu (N,\mathcal {W})\ne \infty$ (just remove some players from the winning coalitions to make them minimal winning.)

We state a few well-known and easy observations:

Proposition 1

Let $(N,\mathcal {W})$ be a simple game.

• (a) If player i is a null player, then $\nu (N,\mathcal {W})=\nu (N\backslash \{i\},\mathcal {W}')$, where $\mathcal {W}'=\{ S\in \mathcal {W}$$:\, S\subseteq N\backslash \{i\}\}$.

• (b) We have $\nu (N,\mathcal {W})=\infty$ if and only if $(N,\mathcal {W})$ contains at least one vetoer.

• (c) If $(N,\mathcal {W})$ contains no vetoer, then $2\le \nu (N,\mathcal {W})\le n$.

• (d) If $(N,\mathcal {W})$ contains a passer that is not a dictator, then $\nu (N,\mathcal {W})=2$.

• (e) If $(N,\mathcal {W})$ contains no vetoer but d null players, then $\nu (N,\mathcal {W})$ is upper bounded by $\min \left( \left| \mathcal {W}^m\right| ,n-d\right)$.

• (f) If $(N,\mathcal {W})$ contains no vetoer, then $\nu (N,\mathcal {W})\le \left| \cap _{i=1}^k S_i\right| +k$ for any k winning coalitions $S_i$.

So, when determining $\nu (N,\mathcal {W})$, we may always assume that $(N,\mathcal {W})$ does not contain any vetoer, null player, passer, or dictator. Also the simple games with $\nu (N,\mathcal {W})=2$ can be completely characterized. Directly from the definition we conclude, see also Kumabe and Mihara (2008):

Proposition 2

Let $(N,\mathcal {W})$ be a simple game without vetoers.

• (a) We have $\nu (N,\mathcal {W})=2$ if and only if $(N,\mathcal {W})$ is non-proper.

• (b) If $(N,\mathcal {W})$ is constant-sum, then $\nu (N,\mathcal {W})=3$.

• (c) If $\nu (N,\mathcal {W})>3$, then $(N,\mathcal {W})$ is proper and non-strong.

For part (b) we can start from any minimal winning coalition S and any player $i\in S$. Then, S, $N\backslash S\cup \{i\}$, and $N\backslash \{i\}$ are winning coalitions with empty intersection.

The Nakamura number for symmetric games, i.e., k-out-of-n games, see Example 1, is well known, see e.g. Ferejohn and Grether (1974) and Nakamura (1979), Peleg (1978):

$$\begin{aligned} \nu ([\hat{q},1,\dots ,1])=\left\lceil \frac{n}{n-\hat{q}}\right\rceil =\left\lceil \frac{1}{1-q'}\right\rceil , \end{aligned}$$

(1)

where we formally set $\frac{n}{0}=\infty$.

The exact Nakamura number of a compound simple game, i.e., simple games arising in a two-stage voting game, has been determined in Peleg (1987), see also Keiding (1984).

Each simple game can be written as the intersection or union of a finite number r of weighted games. The minimum possible number r is called dimension or co-dimension, respectively, see e.g. Freixas and Marciniak (2009). Since for two simple games $(N,\mathcal {W}_1)$, $(N,\mathcal {W}_2)$ with $\mathcal {W}_1\subseteq \mathcal {W}_2$ we obviously have $\nu (N,\mathcal {W}_1)\ge \nu (N,\mathcal {W}_2)$ and the intersection or union of simple games with the same grand coalition is also a simple game, we can formulate:

Proposition 3

Let r be a positive integer and $(N,\mathcal {W}_i)$ be simple games for $1\le i\le r$.

• (a) If $\mathcal {W}=\cap _{1\le i\le r} \mathcal {W}_i$, then $\nu (N,\mathcal {W})\ge \nu (N,\mathcal {W}_i)$ for all $1\le i\le r$.

• (b) If $\mathcal {W}=\cup _{1\le i\le r} \mathcal {W}_i$, then $\nu (N,\mathcal {W})\le \nu (N,\mathcal {W}_i)$ for all $1\le i\le r$.

3 Integer linear programming formulations

The determination of the Nakamura number of a simple or weighted game is a hard computational problem.¹ This justifies the use of integer linear programming (ILP) formulations.

Lemma 1

For each simple game $(N,\mathcal {W})$ and $\mathcal {X}=\mathcal {W}$ or $\mathcal {X}=\mathcal {W}^m$ the corresponding Nakamura number $\nu (N,\mathcal {W})$ is given as the optimal target value of:

$$\begin{aligned}&\min r\\&\sum _{S\in \mathcal {X}} x_S = r \\&\sum _{S\in \mathcal {X}\,:\,i\in S} x_S \le r-1\quad \forall i\in N\\&x_S \in \{0,1\}\quad \forall S\in \mathcal {X} \end{aligned}$$

Proof

In the ILP formulation we consider r minimal winning coalitions $\{S\in \mathcal {X}\,:\,x_S=1\}$. They have an empty intersection iff each player $i\in N$ is contained in at most $r-1$ of them. The Nakamura number $\nu (N,\mathcal {W})$ is of course given by the minimum possible value for r. $\square$

Using the concept of coalition vectors the ILP from Lemma 1 can be condensed:

Lemma 2

Let $(N,\mathcal {W})$ be a simple game without vetoers and $N_1,\dots ,N_t$ be itsdecomposition into equivalence classes. Using the abbreviations $n_j=\left| N_j\right|$ for all $1\le j\le t$ and $V\subseteq \mathbb {N}_{\ge 0}^t$ for the set of minimal winning coalition vectors, the Nakamura number of $(N,\mathcal {W})$ is given as the optimal target value of:

$$\begin{aligned}&\min \sum _{v\in V} x_v\\&\sum _{v=(v_1,\dots ,v_t)\in V} (n_j-v_j)\cdot x_v \ge n_j\quad \forall 1\le j\le t\\&x_v \in \mathbb {Z}_{\ge 0}\quad \forall v\in V \end{aligned}$$

Proof

First we show that each collection $S_1,\dots ,S_r$ of minimal winning coalitions with empty intersection can be mapped onto a feasible, not necessarily optimal, solution of the above ILP with target value r.

Each minimal winning coalition $S_i$ has a minimal winning coalition vector $v_i$. We set $x_v$ to the number of times vector v is the corresponding winning coalition vector. So the $x_v$ are non-negative integers and the target value clearly coincides with r. The term $\left| N_j\right| -\left| S_i\backslash N_j\right|$ counts the number of players of type j which are missing in coalition $S_i$. Since every player has to be dropped at least once from a winning coalition, we have $\sum _{i=1}^r n_j-\left| S_i\backslash N_j\right| \ge n_j$ for all $1\le j\le t$. The number on the left hand side is also counted by

$$\begin{aligned} \sum _{v=(v_1,\dots ,v_t)\in V} \left( n_j-v_j\right) \cdot x_v, \end{aligned}$$

so that all inequalities are satisfied.

For the other direction we choose r vectors $v^1,\dots ,v^r\in V$ such that $\sum _{i=1}^r v^i=\sum _{v\in V} x_v\cdot v$, i.e., we take $x_v$ copies of vector v for each $v\in V$, where $r=\sum _{v\in V} x_v$. In order to construct corresponding minimal winning coalitions $S_1,\dots ,S_r$, wedecompose those desired coalitions according to the equivalence classes of players: $S^i=\cup S_j^i$ with $S_j^i\subseteq N_j$ for all $1\le j\le t$.

For an arbitrary fix index $1\le j\le t$ we start with $R_0=N_j$ and recursively construct the sets $S_j^i$ as follows: Starting from $i=1$ we set $S_j^i=N_j\backslash R_{i-1}$ and $R_i=\emptyset$ if $\left| R_{i-1}\right| <n_j-v^i_j$. Otherwise we choose a subset $U\subseteq R_{i-1}$ of cardinality $n_j-v^i_j$ and set $S_j^i=N_j\backslash U$ and $R_i=R_{i-1}\backslash U$. For each $1\le i\le r$ we have $N_j\backslash \cap _{1\le h\le i} S_j^i=N_j\backslash R_i$.

By construction, the coalition vector of $S_i$ is component-wise larger or equal to $v^i$, i.e., the $S^i$ are winning coalitions. Since $\sum _{i=1}^r\left( n_j-v_j^i\right) \ge n_j$, we have $R_i=\emptyset$ in all cases, i.e., the intersection of the $S_i$ is empty. $\square$

Example 3

Consider the weighted game [4; 2, 2, 1, 1, 1, 1] with equivalence classes $N_1=\{1,2\}$, $N_2=\{3,4,5,6\}$ and minimal winning coalition vectors (2, 0), (1, 2), and (0, 4). The corresponding ILP reads:

$$\begin{aligned}&\min x_{(2,0)}+x_{(1,2)}+x_{(0,4)}\\&0\cdot x_{(2,0)}+1\cdot x_{(1,2)}+2\cdot x_{(0,4)} \ge 2\\&4\cdot x_{(2,0)}+2\cdot x_{(1,2)}+0\cdot x_{(0,4)} \ge 4\\&x_{(2,0)},x_{(1,2)},x_{(0,4)}\in \mathbb {Z}_{\ge 0} \end{aligned}$$

Solutions with the optimal target value of 2 are given by $x_{(2,0)}=1$, $x_{(1,2)}=0$, $x_{(0,4)}=1$ and $x_{(2,0)}=0$, $x_{(1,2)}=2$, $x_{(0,4)}=0$. For the first solution we have $v^1=(2,0)$ and $v^2=(0,4)$ so that $S_1^1=\{1,2\}$, $S_1^2=\emptyset$, $S_2^1=\emptyset$ and $S_2^2=\{3,4,5,6\}$, where we have always chosen the players with the smallest index. For the second solution we have $v^1=(1,2)$ and $v^2=(1,2)$ so that $S_1^1=\{1\}$, $S_1^2=\{2\}$, $S_2^1=\{3,4\}$, and $S_2^2=\{5,6\}$.

Next, we specialize to complete simple games. Note that while we can assume that there exists a list of $\nu (N,\mathcal {W})$ minimal winning coalitions with empty intersection, there does not need to exist a list of $\nu (N,\mathcal {W})$ shift-minimal winning coalitions with empty intersection (for a given complete simple game $(N,\mathcal {W})$).

Example 4

Consider the complete simple game uniquely characterized by $\tilde{n}=(5,5)$ and $\tilde{M}=\begin{pmatrix}2&3\end{pmatrix}$. Here we need three copies of the coalition vector (2, 3) since $2\cdot (\tilde{n}-(2,3))=(6,4)\not \ge (5,5)=\tilde{n}$ but $3\cdot (\tilde{n}-(2,3))\ge \tilde{n}$. On the other hand the Nakamura number is indeed 2, as one can choose the two minimal winning vectors (2, 3) and (3, 2), where the latter is a shifted version of (2, 3).

As further notation, we write $v=\sum (u)\in \mathbb {N}_{\ge 0}^t$ for $v_i=\sum _{j=1}^i u_j$ for all $1\le i\le t$, where $u\in \mathbb {N}_{\ge 0}^t$. Let $v\in \mathbb {N}_{\ge 0}^t$ be a minimal winning vector of a complete simple game $(N,\mathcal {W})$. Directly from definition we conclude that if $v\preceq u$, then u is also a winning vector and $\sum (v)\le \sum (u)$.

Fig. 1

The Hasse diagram of the vectors with counting vector (1, 2, 1)

Lemma 3

For each complete simple game, uniquely characterized by $\tilde{n}$ and $\tilde{M}$, without vetoers and equivalence classes $N_1,\dots , N_t$ the corresponding Nakamura number $\nu (N,\mathcal {W})$ is given as the optimal target value of

$$\begin{aligned}&\min \sum _{i=1}^r x_i\\&\sum _{i=1}^r \left( o_j-p_j^i\right) \cdot x_i\ge o_j \quad \forall 1\le j\le t\\&x_i\in \mathbb {Z}_{\ge 0}\quad \forall 1\le i\le r, \end{aligned}$$

where $o:=\left( o_1,\dots ,o_t\right) =\sum (\tilde{n})$, $p^i:=\left( p_1^i,\dots ,p_t^i\right) =\sum (\tilde{m}_i)$, and $n_j=\left| N_j\right|$.

Proof

Consider a list of minimal winning vectors $v^1,\dots ,v^r$ corresponding to an optimal solution of the ILP of Lemma 2. We aim to construct a solution of the present ILP. To this end, consider an arbitrary mapping $\tau$ from the set of minimal winning vectors into the set of shift-minimal winning vectors, such that $\tau (u)\preceq u$ for all minimal winning vectors u. We choose the $x_i$’s as the number of occurrences of $\tilde{m}_i=\tau (v^j)$ for all $1\le j\le j$. Thus, the $x_i$ are non-negative numbers, which sum to the Nakamura number of the given complete game. Since $\tau (v^i)\preceq v^i$ we have $\sum (\tau (v^i))\le \sum (v^i)$. Thus $\sum (\tilde{n})-\sum (\tau (v^i))\ge \sum (\tilde{n})-\sum (v^i)$, so that all inequalities are satisfied.

For the other direction let $x_i$ be a solution of the present ILP. Choosing $x_i$ copies of shift-minimal winning vector $\tilde{m}_i$ we obtain a list of shift-minimal winning vectors $v^1_0,\dots ,v^r_0$ satisfying $\sum _{i=1}^r\sum (\tilde{n})-\sum (v^i_0)\ge \sum (\tilde{n})$. Starting with $j=1$ we iterate: As long we do not have $\sum _{i=1}^r\tilde{n}-v^i_j\ge \tilde{n}$, we choose an index $1\le h\le t$, where the hth component of $\sum _{i=1}^r\tilde{n}-v^i_j$ is smaller than $\tilde{n}_h$. Since $\sum _{i=1}^r\sum (\tilde{n})-\sum (v^i_j)\ge \sum (\tilde{n})$ we have $h\ge 2$ and the $(h-1)$th component of $\sum _{i=1}^r\sum (\tilde{n})-\sum (v^i_j)$ is at least one larger than the $(h-1)$th component of $\sum (\tilde{n})$. Thus, there exists a vector $v_j^{i'}$ where we can shift one player from class h to a class with index lower or equal than $h-1$ to obtain a new minimal winning vector $v_{j+1}^{i'}$. All other vectors remain unchanged.

We can easily check, that the new list of minimal winning vectors also satisfies $\sum _{i=1}^r\sum (\tilde{n})-\sum (v^i_{j+1})\ge \sum (\tilde{n})$. The process must terminate since $\sum _{i=1}^r\sum (\tilde{n})-\sum (v^i_{j})$ decreases one unit in a component in each iteration. Thus, finally we end up with a list of minimal winning vectors satisfying $\sum _{i=1}^r\tilde{n}-v^i_j\ge \tilde{n}$. $\square$

In Fig. 1 we have depicted the Hasse diagram of the shift-relation for coalition vectors for $\tilde{n}=(1,2,1)$. If we consider the complete simple game with shift-minimal winning vectors (1, 0, 1) and (0, 2, 0), then for the minimal winning vector (1, 1, 0) we have two possibilities for $\tau$.

We remark that the complexity result in Footnote 1 prompts the existence of hard instances for the ILP formulations of Lemmas 2 and 3.

Example 5

Consider the complete simple game uniquely characterized by $\tilde{n}=(10,10)$ and $\tilde{M}=\begin{pmatrix}7&8\end{pmatrix}$. An optimal solution of the corresponding ILP is given by $x_1=4$. I.e. initially we have $v_0^1=(7,8)$, $v_0^2=(7,8)$, $v_0^3=(7,8)$, and $v_0^4=(7,8)$. We have $\sum _{i=1}^r\sum (\tilde{n})-\sum (v^i_0)=(12,20)\ge (10,20)=\sum (\tilde{n})$ and $\sum _{i=1}^r\tilde{n}-v^i_0=(12,8)\not \ge (10,10)=\tilde{n}$. Here the second component, with value 8, is too small. Thus the first component must be at least 1 too large, and indeed $12>10$. We can shift one player from class 2 to class 1. We may choose $v_1^1=(8,7)$, $v_1^2=(7,8)$, $v_1^3=(7,8)$, and $v_1^4=(7,8)$, so that $\sum _{i=1}^r\sum (\tilde{n})-\sum (v^1_0)=(11,20)\ge (10,20)=\sum (\tilde{n})$ and $\sum _{i=1}^r\tilde{n}-v^i_0=(11,9)\not \ge (10,10)=\tilde{n}$. Finally we may shift one player in $v_1^1$ again or in any of the three other vectors to obtain $v_2'=v_2^2=(7,8)$ and $v_2^3=v_2^4=(8,7)$.

4 Bounds for weighted games

Having the classical result of the determination of the Nakamura number of symmetric games, see Eq. (1), in mind, we provide bounds for general weighted games:

Theorem 1

For each weighted game we have

$$\begin{aligned} \left\lceil \frac{1}{1-q'}\right\rceil= & {} \left\lceil \frac{w(N)}{w(N)-q}\right\rceil \le \nu ([q;w_1,\dots ,w_n])\nonumber \\\le & {} \left\lceil \frac{\hat{w}(N)}{\hat{w}(N)-\hat{q}-\hat{\omega }+1}\right\rceil \le \left\lceil \frac{1}{1-q'-\omega '}\right\rceil , \end{aligned}$$

(2)

where $\hat{\omega }=\max _i \hat{w}_i$ and $\omega '=\max _i w'_i$.

Proof

For the lower bound we set $r=\nu (N,\mathcal {W})$ and choose r winning coalitions $S_1,\dots ,S_r$ with empty intersection. With $I_0:=N$ we recursively set $I_i:=I_{i-1}\cap S_i$ for $1\le i\le r$. By induction we prove $w(I_i)\ge w(N)-i\cdot (w(N)-q)$ for all $0\le i\le r$. The statement is true for $I_0$ by definition. For $i\ge 1$ we have $w(I_{i-1})\ge w(N)-(i-1)\cdot (w(N)-q)$. Since $w(S_i)\ge q$ we have $w(I_{i-1}\cap S_i)\ge w(I_{i-1}) -(w(N)-q)=w(N)-i\cdot (w(N)-q)$. Thus we have $\nu ([q;w_1,\dots ,w_n])\ge \left\lceil \frac{w(N)}{w(N)-q}\right\rceil$.

For the upper bound we start with $R_0=N$ and recursively construct winning coalitions $S_i$ by setting $S_i=N\backslash R_{i-1}$ and adding players from $R_{i-1}$ to $S_i$ until $\hat{w}(S_i)\ge \hat{q}$. By construction we have that $S_i$ is a winning coalition with $\hat{w}(S_i)\le \hat{q}+\hat{\omega }-1$. With this we set $R_i=R_{i-1}\cap S_i$ and get

$$\begin{aligned} \hat{w}(R_i)\le \max \left( 0,\hat{w}(N)-i\cdot \left( \hat{w}(N)-\hat{q}-\hat{\omega }+1\right) \right) . \end{aligned}$$

Since $\hat{w}(R_i)=0$ implies that $R_i$ can contain only null players of weight zero, we may replace $S_1$ by $S_1\cup R_i$, so that we obtain the stated upper bound. $\square$

Note that for symmetric games (2) is equivalent to (1), i.e., Theorem 1 can be seen as a generalization of the classical result of Nakamura (1979). We remark that one can use the freedom in choosing the representation of a weighted game to eventually improve the lower bound from Theorem 1. For the representation [2; 1, 1, 1] we obtain $\nu ([2;1,1,1])\ge \left\lceil \frac{3}{3-2}\right\rceil =3$. Since the same game is also represented by $[1+\varepsilon ;1,1,1]$ for all $0<\varepsilon \le \frac{1}{2}$, we could also deduce $\nu ([2;1,1,1])\ge \left\lceil \frac{3}{3-1-\varepsilon }\right\rceil =2$, which is a worse bound. The tightest possible bound is attained if the relative quota is maximized, see Section 7. The greedy type approach of the second part of the proof of Theorem 1 can be improved so that it yields better upper bounds for many instances. Starting from N, we iteratively remove the heaviest possible player in $R_{i-1}$ from $S_i$ such that $\hat{w}(S_i)\ge \hat{q}$ until no player can be removed anymore. However, the following example shows that the lower and the upper bound can still differ by a constant factor.

Example 6

For a positive integer k, consider a weighted game [q; w] with 2k players of weight 5, 6k players of weight 2, and quota $q=22k-11$. The greedy algorithm described above chooses the removal of two players of weight 5 in the first k rounds. Then it removes five (or the remaining number of) players of weight 2 in the next $\left\lceil \frac{6k}{5}\right\rceil$ rounds, so that $2k\le \nu ([q;w])\le k+\left\lceil \frac{6k}{5}\right\rceil$. Removing 2k times one player of weight 5 and three players of weight 2 gives indeed $\nu ([q;w])=2k$.

In the special case of $\hat{w}_i\le 1$, i.e. $\hat{w}_i\in \{0,1\}$, for all $1\le i\le n$, the bounds of Theorem 1 coincide, which is equivalent to the null player extension of Eq. (1). In general we are interested in large classes of instances where the lower bound of Theorem 1 is tight. Promising candidates are weighted representations where all minimal winning coalitions have the same weight equaling the quota. Those representations are called homogeneous representations and the corresponding games are called, whenever such a representation exists, homogeneous games. However, the lower bound is not tight in general for homogeneous representations, as shown by the following example.

Example 7

The weighted game $(N,\mathcal {W})=\left[ 90;{9}^{\{10\}},{2}^{\{4\}},{1}^{\{2\}}\right]$, with ten players of weight 9, four players of weight 2, and two players of weight 1, is homogeneous since all minimal winning coalitions have weight 90. The lower bound of Theorem 1 gives $\nu (N,\mathcal {W})\ge \left\lceil \frac{100}{100-90}\right\rceil =10$. In order to determine the exact Nakamura number of this game we study its minimal winning coalitions. To this end let S be a minimal winning coalition. If S contains a player of weight 2, then it has to contain all players of weight 2, one player of weight 1, and nine players of weight 9. If S contains a player of weight 1, then the other player of weight 1 is not contained and S has to contain all players of weight 2 and nine players of weight 9. If S contains neither a player of weight 1 nor a player of weight 2, then S consists of all players of weight 9. Now we are ready to prove that the Nakamura number of $(N,\mathcal {W})$ equals 11. Let $S_1,\dots ,S_r$ be a minimal collection of minimal winning coalitions whose intersection is empty. Clearly all coalitions are pairwise different. Since there has to be a coalition where not all players of weight 2 are present, one coalition, say $S_1$, has to consist of all players of weight 9. Since each minimal winning coalition contains at least nine players of weight 9, we need 10 further coalitions $S_i$, where each of the players of weight 9 is missing once. Thus $\nu (N,\mathcal {W})\ge 11$ and indeed one can easily state a collection of 11 minimal winning coalitions with empty intersection.

Note that in Example 7 the used integral weights are as small as possible, i.e., $\sum _i w_i$ is minimal, so that one also speaks of a minimum sum (integer) representation, see e.g. Kurz (2012). Example 7 can further be generalized by choosing an integer $k\ge 3$ and considering the weighted game

$$\begin{aligned} (N,\mathcal {W}):=\left[ k(k+1);{k}^{\{k+1\}},{2}^{\{l\}},{1}^{\{k+1-2l\}}\right] , \end{aligned}$$

where $1\le l\le \lfloor k/2\rfloor$ is arbitrary. The lower bound from Theorem 1 gives $\nu (N,\mathcal {W})\ge k+1$, while $\nu (N,\mathcal {W})=k+2$.

However, homogeneous games seem to go into the right direction and we can obtain large classes of tight instances by “homogenizing” an initial weighted game. It is well known that one can homogenize each weighted game, given by an integer representation, by adding a sufficiently large number of players of weight 1 keeping the relative quota “constant”. Other possibilities are to consider replicas, i.e., each of the initial players is divided into k equal players all having the initial weight, where we also assume a “constant” relative quota. If no players of weight 1 are present, then the game eventually does not become homogeneous, even if the replication factor k is large. But indeed the authors of Kurz et al. (2014) have recently shown that for the case of a suitably large replication factor k the nucleolus coincides with the relative weights of the players, i.e., the lower bounds of Theorem 4, see Sect. 7, and Theorem 1 coincide. Both transformations from the literature, eventually homogenizing an initial weighted game, lead to weighted games where the lower bound of Theorem 1 gives the exact value of $\nu (N,\mathcal {W})$:

Theorem 2

Let $w_1\ge \cdots \ge w_n\ge 1$ be (not necessarily pairwise) coprime integer weights with sum $\varOmega =\sum _{i=1}^n w_i$ and $\overline{q}\in (0,1)$ be a rational number.

• (a) For each positive integer r we consider the game

  $$\begin{aligned} \chi =\left[ \overline{q}\cdot (\varOmega +r);w_1,\dots ,w_n,{1}^{\{r\}}\right] , \end{aligned}$$

  with r players of weight 1. If $r\ge \max \left( \varOmega ,\frac{2+w_1}{1-\overline{q}}\right)$ we have $\nu (\chi )=\left\lceil \frac{1}{1-q^r}\right\rceil$, where $q^r=\frac{\left\lceil \overline{q}(\varOmega +r)\right\rceil }{\varOmega +r}$.

• (b) For each positive integer r we consider the game

  $$\begin{aligned} \chi =\left[ \overline{q}\cdot (\varOmega \cdot r);{w_1}^{\{r\}},\dots ,{w_n}^{\{r\}}\right] , \end{aligned}$$

  where each player is replicated r times. If r is sufficiently large, we have $\nu (\chi )=\left\lceil \frac{1}{1-q^r}\right\rceil$, where $q^r=\frac{\left\lceil \overline{q}(\varOmega \cdot r)\right\rceil }{\varOmega \cdot r}$.

The proof is a bit involved and postponed to Sect. A in the Appendix.

4.1 $\mathbf {\alpha }$-Roughly weighted games

Now we want to transfer Theorem 1 to $\alpha$-roughly weighted games. Instead of a quota q separating between winning and losing coalitions we have the two thresholds 1 and $\alpha$, i.e., coalitions with a weight smaller than 1 are losing and coalitions with a weight larger than $\alpha$ are winning. Those two thresholds 1 and $\alpha$ play the role of the quota q in the lower and upper bound of Theorem 1, respectively:

Proposition 4

Let $(N,\mathcal {W})$ be an $\alpha$-roughly weighted simple game with representation $(w_1,\dots ,w_n)$ satisfying $\alpha +\omega >w(N)$, where $\omega =\max \{w_i\mid i\in N\}$. Then, $\left\lceil \frac{w(N)}{w(N)-1}\right\rceil \le \nu (N,\mathcal {W})\le \left\lceil \frac{w(N)}{w(N)-\alpha -\omega }\right\rceil$.

Proof

Since each winning coalition has a weight of at least 1, the proof of the lower bound of Theorem 1 also applies here. The proof of the upper bound can be slightly adjusted. In order to construct winning coalitions $S_i$ with empty intersection we set $S_i=N\backslash R_{i-1}$ and add players from $R_{i-1}$ until $S_i$ becomes a winning coalition. We remark $w(S_i)\le \alpha +\omega$ so that we can conclude the proposed statement. $\square$

Of course an $\alpha$-roughly weighted game is $\alpha '$-roughly weighted for all $\alpha '\ge \alpha$. The minimum possible value of $\alpha$ such that a given simple game is $\alpha$-roughly weighted is called critical threshold value in Freixas and Kurz (2014a). Taking the critical threshold value gives the tightest upper bound. A larger value of $\alpha$ means less information on whether coalitions are losing or winning. Thus, it is quite natural that the lower and the upper bound of Proposition 4 diverge if $\alpha$ increases.

5 Bounds for simple and complete simple games

Most simple games are not weighted. An example is given as follows:

Example 8

Let $v=(N,\mathcal {W})$ be a game with equivalence classes $N_1=\{1,2\}$, $N_2=\{3,4\}$ uniquely characterized by the single minimal winning coalition vector (1, 1). One can think of a family with two kids and two parents planing their weekend excursion. A proposal is accepted if at least one member of each of the two equivalence classes agrees.

So, in Example 8, and all other non-weighted games, the bounds from Theorem 1 cannot be applied directly. However, each simple game is $\alpha$-roughly weighted for a suitable $\alpha$, so that we have the bounds of Proposition 4 at hand. The corresponding critical threshold value is given by $\alpha =1$, which is attained by weights of $\tfrac{1}{2}$ for all four players. Thus, Proposition 4 gives $2\le \nu (N,\mathcal {W})\le 4$. In general, the minimal possible $\alpha$ can be proportional to n, i.e., fairly large. Moreover, the determination of the critical threshold value is a computational hard problem, see Hof et al. (2018).

As mentioned in Sect. 2, another representation of simple games is given by the intersection or union of weighted games. For Example 8 we have $(N,\mathcal {W})=[1;1,1,0,0]\cap [1;0,0,1,1]$ and $(N,\mathcal {W})=[3;2,0,1,1]\cup [3;0,2,1,1]$. Indeed, the dimension and codimension of $(N,\mathcal {W})$ is 2. With this, Proposition 3 gives $2\le \nu (N,\mathcal {W})\le \infty$. The weak upper bound is due to the fact that the involved weighted games contain a vetoer. We remark that the computational problem ofdetermining the dimension or codimension of a given simple game is hard ingeneral, see e.g. Deǐneko and Woeginger (2006) and Kurz and Napel (2016).

For simple games we do not have a relative quota $q'$, which is the most essential parameter in the bounds of Theorem 1. However, in Sect. 7 we present a slightly more involved substitute. Prior to that, we consider bounds for the cardinalities of minimal winning coalitions as parameters and slightly adjust the proof of Theorem 1. If both parameters coincide we obtain an equation comprising Eq. (1).

Theorem 3

Let m be the minimum and M be the maximum cardinality of aminimal winning coalition of a simple game $(N,\mathcal {W})$. Then, $\left\lceil \frac{n}{n-m}\right\rceil \le \nu (N,\mathcal {W})\le 1+\left\lceil \frac{m}{n-M}\right\rceil \le \left\lceil \frac{n}{n-M}\right\rceil$.

Proof

For the lower bound, we set $r=\nu (N,\mathcal {W})$ and choose r winning coalitions $S_1,\dots ,S_r$ with empty intersection. Starting with $I_0:=N$, we recursively set $I_i:=I_{i-1}\cap S_i$ for $1\le i\le r$. By induction we prove $\left| I_i\right| \ge n-i\cdot (n-m)$ for all $0\le i\le r$. The statement is true for $I_0$ by definition. For $i\ge 1$ we have $\left| I_{i-1}\right| \ge n-(i-1)\cdot (n-m)$. Since $\left| S_i\right| \ge m$ we have $\left| I_{i-1}\cap S_i\right| \ge \left| I_{i-1}\right| -(n-m)\ge n-i\cdot (n-m)$. Thus we have $\nu (N,\mathcal {W})\ge \left\lceil \frac{n}{n-m}\right\rceil$, where we set $\frac{n}{0}=\infty$ and remark that this can happen only, if N is the unique winning coalition, i.e., all players are vetoers.

If $M=n$, we obtain the trivial bound $\nu (N,\mathcal {W})\le \infty$ so that we assume $M\le n-1$. We recursively define $I_i:=I_{i-1}\cap S_i$ for $1\le i\le r$ and set $I_0=N$. In order to construct a winning coalition $S_i$ we determine $U=N\backslash \{I_{i-1}\}$ and choose a $\max \left( 0,M-\left| U\right| \right)$-element subset V of $I_{i-1}$. With this we set $S_i=U\cup V$. If $\left| S_i\right| > M$, we remove some arbitrary elements so that $\left| S_i\right| =M$, i.e.  all coalitions $S_i$ have cardinality exactly M and thus are winning for all $i\ge 1$. By induction we prove $\left| I_i\right| \ge \max \left( 0,n-i\cdot (n-M)\right)$, so that the stated weaker upper bound follows. For the stronger version we choose $S_1$ as a winning coalition of cardinality m. $\square$

We remark that Theorem 3 gives $\nu (N,\mathcal {W})=2$ for the simple game from Example 8.

Next we aim at bounds for the Nakamura number of complete simple games. To this end, we start by considering complete simple games with a unique shift-minimal winning vector.

Proposition 5

The Nakamura number of a complete simple game without vetoers, uniquely characterized by $\tilde{n}=(n_1,\dots ,n_t)$ and $\tilde{M}=\begin{pmatrix}m_{1}^1&\dots&m_t^1\end{pmatrix}$, is given by

$$\begin{aligned} \max _{1\le i\le t} \left\lceil \frac{\sum _{j=1}^i n_j}{\sum _{j=1}^i n_j-m_j^1}\right\rceil \le \max _{1\le i\le t} \left\lceil \frac{\sum _{j=1}^i n_j}{i}\right\rceil \le \max (2,n-2t+3). \end{aligned}$$

Proof

We utilize the ILP in Lemma 3. In our situation it has only one variable $x_1$. The minimal integer satisfying the inequality number i is given by $\left\lceil \frac{\sum _{j=1}^i n_j}{\sum _{j=1}^i n_j-m_j^1}\right\rceil$.

Next we consider the first upper bound just involving the cardinalities of theequivalence classes. Since the complete simple game has no vetoers we have $m_1^1\le n_1-1$. Due to the type conditions in the parameterization theorem of complete simple games, we have $1\le m_j^1\le n_j-1$ and $n_j\ge 2$ for all $2\le j\le t-1$. If $t\ge 2$ then we additionally have $0\le m_t^1\le n_t-1$ and $n_t\ge 1$. Thus we have $\sum _{j=1}^i n_j-m_j^1\ge i$ and conclude the proposed upper bound.

By shifting one player from $N_i$ to $N_{i-1}$ the upper bound $\max _{1\le i\le t} \left\lceil \frac{\sum _{j=1}^i n_j}{i}\right\rceil$ does not decrease. Thus the minimum is attained at $n_t=1$, and $n_i=2$ for all $2\le i\le t-1$, which gives the second upper bound only depending on the number of players and equivalence classes. $\square$

Corollary 1

Let $(N,\mathcal {W})$ be a complete simple game with t types of players. If $(n_1-1,\dots ,n_t-1)$ is a winning vector, then we have

$$\begin{aligned} \nu (N,\mathcal {W})\le \max _{1\le i\le t} \left\lceil \frac{\sum _{j=1}^i n_j}{i}\right\rceil \le n-t+1. \end{aligned}$$

Proof

Proceeding as in the proof of Proposition 5 yields the first bound. The second bound follows from

$$\begin{aligned} \frac{n_1+\dots +n_i}{i}\le \frac{n-t+i}{i}=\frac{n-t}{i}+1\le n-t+1. \end{aligned}$$

$\square$

Using Proposition 5 as a heuristic, i.e., using just a single shift-minimal winning vector, we obtain:

Corollary 2

The Nakamura number of a complete simple game uniquely characterized by $\tilde{n}=(n_1,\dots ,n_t)$ and $\tilde{M}=(m^1,\dots ,m^r)^T$, where $m^i=(m^i_1,\dots ,m^i_t)$, is upper bounded by

$$\begin{aligned} \max _{1\le i\le t} \left\lceil \frac{\sum _{j=1}^i n_j}{\sum _{j=1}^i n_j-m_j^i}\right\rceil \end{aligned}$$

for all $1\le i\le r$.

We remark that we cannot apply Corollary 2 to the game of Example 8 since it is not complete.

For further bounds for the Nakamura number of simple games we refer to Theorem 4 and Proposition 9 in Sect. 7.

5.1 Enumeration results

In order to get a first idea of the distribution of the attained Nakamura numbers we consider the class of complete simple games with a unique shift-minimal winning vector, see Tables 1 and 2, as well as their subclass of weighted games, see Table 3.

Table 1 Complete simple games with a unique shift-minimal winning vector per Nakamura number—1

We have chosen these subclasses since they allow to exhaustively generate all corresponding games for moderate sizes of the number of players n, which is not the case for many other subclasses of simple games. Additionally, the corresponding Nakamura numbers can be evaluated easily applying Proposition 5.

Table 2 Complete simple games with a unique shift-minimal winning vector per Nakamura number—2

Table 3 Weighted games with a unique shift-minimal winning vector per Nakamura number

One might say that being non-weighted increases the probability for a complete simple game with a unique shift-minimal winning vector to have a low Nakamura number.

Tables 1, 2, and 3 suggest:

Conjecture 1

$$\begin{aligned} a_{\mathcal {C}}(n,\nu )= 2^{n-\nu -1}\quad \text { for }\left\lceil (n+2)/2\right\rceil \le \nu \le n-1 \end{aligned}$$

and

$$\begin{aligned} a_{\mathcal {T}}(n,\nu )=n-\nu \quad \text { for }\left\lceil (n+2)/2\right\rceil \le \nu \le n-1, \end{aligned}$$

where $a_{\mathcal {C}}(n,\nu )$ and $a_{\mathcal {T}}(n,\nu )$ denote the number of complete simple and weighted games with minimum ($r=1$) consisting of n players and having Nakamura number $\nu$.

6 Maximum Nakamura numbers within subclasses of simple games

In this section we consider the “worst case”, i.e., the maximum possible Nakamura number within a given class of games. Clearly, $(N,\mathcal {W})=[n-1;1,\dots ,1]$ attains the maximum $\nu (N,\mathcal {W})=n$ in the class of simple or weighted games with $n\ge 1$ players. However, all players of this example are equivalent, which is rather untypical for a simple game. Thus, it is quite natural to ask for the maximum possible Nakamura number if the number of players and the number of equivalence classes is given.

By $\mathcal {S}$ we denote the set of simple games, by $\mathcal {C}$ we denote the set of complete simple games, and by $\mathcal {T}$ we denote the set of weighted games.

Definition 2

${\text {Nak}}^{\mathcal {X}}(n,t)$ is the maximum Nakamura number of a game without vetoers with $n\ge 2$ players and $t\le n$ equivalence classes in $\mathcal {X}$, where $\mathcal {X}\in \{\mathcal {S},\mathcal {C},\mathcal {T}\}$.

Clearly, we have

$$\begin{aligned} 2\le {\text {Nak}}^{\mathcal {T}}(n,t)\le {\text {Nak}}^{\mathcal {C}}(n,t)\le {\text {Nak}}^{\mathcal {S}}(n,t)\le n, \end{aligned}$$

if the corresponding set of games is non-empty. Before giving exact formulas for small t, we characterize all simple games with $\nu (N,\mathcal {W})\ge n-1$:

Lemma 4

Let $(N,\mathcal {W})$ be a simple game. If $\nu (N,\mathcal {W})=n$, then $(N,\mathcal {W})=[n-1;1,\dots ,1]$ and $n\ge 2$. If $\nu (N,\mathcal {W})=n-1$, then $(N,\mathcal {W})$ is of one of thefollowing types:

• (1) $(N,\mathcal {W})=\left[ 2n-4;{2}^{\{n-2\}},{1}^{\{2\}}\right]$, $t=2$, for all $n\ge 3$;

• (2) $(N,\mathcal {W})=\left[ 1;{1}^{\{3\}}\right]$, $t=1$, for $n=3$;

• (3) $(N,\mathcal {W})=\left[ 2n-5;{2}^{\{n-3\}},{1}^{\{3\}}\right]$, $t=2$, for all $n\ge 4$;

• (4) $(N,\mathcal {W})=\left[ n-1;{1}^{\{n-1\}},{0}^{\{1\}}\right]$, $t=2$, for all $n\ge 3$;

• (5) $(N,\mathcal {W})=\left[ 5n-2k-9;{5}^{\{n-k-1\}},{3}^{\{k\}},{1}^{\{1\}}\right]$, $t=3$, for all $n\ge 4$ ($2\le k\le n-2$).

Proof

Let us start with the case $\nu (N,\mathcal {W})=n$. Due to part (b) and (f) of Proposition 1 all minimal winning coalitions have cardinality $n-1$. Part (e) gives that there are no null players, i.e., all players are contained in some minimal winning coalition.

Now let $\nu (N,\mathcal {W})=n-1$. Again, due to part (b) and part (f) of Proposition 1 all minimal winning coalitions have either cardinality $n-2$ or $n-1$. So, we can describe the game as a graph by taking N as the set of vertices and by taking edge $\{i,j\}$ if and only if $N\backslash \{i,j\}$ is a winning coalition. Again by using Proposition 1(f) we conclude that each two edges need to have a vertex in common. Thus, our graph consists of isolated vertices and either a triangle or a star. To be more precise, we consider the following cases:

• only isolated vertices, which gives $\nu (N,\mathcal {W})=n$;

• a single edge: this does not correspond to a simple game since the empty coalition has to be losing;

• a single edge and at least one isolated vertex: this is case (1);

• a triangle: this is case (2);

• a triangle and at least one isolated vertex: this is case (3);

• a star (with at least three vertices) and no isolated vertex: this is case (4);

• a star (with at least three vertices) and at least one isolated vertex: this is case (5).

$\square$

Proposition 6

For $1\le t\le 4$ equivalence classes of $n\ge t+1$ players we have

$$\begin{aligned} {\text {Nak}}^{\mathcal {T}}(n,t)={\text {Nak}}^{\mathcal {C}}(n,t) ={\text {Nak}}^{\mathcal {S}}(n,t)= \left\{ \begin{array}{rcl}n&{}:&{}t=1,\\ n-1&{}:&{}t=2,3,\\ n-2&{}:&{}t=4.\end{array}\right. \end{aligned}$$

Proof

Due to Lemma 4 it remains to give an example for each case. For $t=1$ and $t=2$ we have $\left[ n-1;{1}^{\{n\}}\right]$ and $\left[ n-2;{1}^{\{n-1\}},{0}^{\{1\}}\right]$, respectively.

For $t=3$, consider the example $\left[ 5n-2k-9;{5}^{\{n-k-1\}},{3}^{\{k\}},{1}^{\{1\}}\right]$, where $k\ge 2$ and $n-k-1\ge 1$, i.e., $n\ge k+2$ and $n\ge 4$, with $n-k-1$ players of weight 5, k players of weight 3, and one player of weight 1 – this is indeed the minimum integer representation, so that we really have 3 types of players (this may also be checked directly).

Let S be a minimal winning coalition. If a player of weight 5 is missing in S, then all players of weight 3 and the player of weight 1 belong to S. Thus, we need $n-k-1$ such versions in order to get an empty intersection of winning coalitions. If a player of weight 3 is missing, then all of the remaining players of weight 3 and all players of weight 5 have to be present, so that we need k such versions. Thus, the game has Nakamura number $n-1$ for all $n\ge 4$ (if k is chosen properly).

For $t=4$, we append a null player to the example for $t=3$, which is possible for $n\ge 5$ players. $\square$

We remark that each simple game $(N,\mathcal {W})$ with $n=t\le 2$ players contains a vetoer, so that $\nu (N,\mathcal {W})=\infty$, see Proposition 1(b). Note that there exists no simple game with $n\le 3$ players and 3 types. Moreover, there exists no weighted game with 4 types and $n\le 4$ players.

By computing the maximum possible Nakamura number for some small parameters n and t, we have some evidence for:

Conjecture 2

If n is sufficiently large, then we have $n-t+1\le {\text {Nak}}^{\mathcal {T}}(n,t)\le n-t+2$, where $t\in \mathbb {N}_{>0}$.

We leave it as an open problem to determine ${\text {Nak}}^{\mathcal {T}}(n,t)$, ${\text {Nak}}^{\mathcal {C}}(n,t)$, and ${\text {Nak}}^{\mathcal {S}}(n,t)$ for $t>4$. The section is concluded by two constructions of parametric classes of simple games providing lower bounds for ${\text {Nak}}^{\mathcal {S}}(n,t)$.

Proposition 7

For $n\ge t\ge 6$ we have ${\text {Nak}}^{\mathcal {S}}(n,t)\ge n-\left\lfloor \frac{t-1}{2}\right\rfloor$.

Proof

Consider a simple game with t types of players given by the following list of minimal winning vectors:

$$\begin{aligned} (n_1-1,n_2,\dots ,n_t)\\ (n_1,n_2-1,n_3-1,n_4,\dots ,n_t)\\ (n_1,n_2,n_3-1,n_4-1,n_5,\dots ,n_t)\\ \vdots \\ (n_1,n_2,\dots ,n_{t-2},n_{t-1}-1,n_t-1)\\ (n_1,n_2-1,n_3,\dots ,n_{t-1},n_t-1), \end{aligned}$$

i.e., if a player of class 1 is missing, then all other players have to be present in a winning coalition, no two players of the same type can be missing in a winning coalition, and at most two players can be missing in a winning vector, if they come from neighbored classes (where the classes $2,3,\dots ,t$ are arranged on a circle).

At first we check that this game has in fact t types. Obviously class 1 is different from the other ones. Let $i<j$ be two indices in $\{2,3,\dots ,t\}$ and $x^{\{a,b\}}=(x_1,\dots ,x_t)$, where $x_h=n_h-1$ if $h\in \{a,b\}$ and $x_h=n_h$ otherwise. Choose some index $c\in \{2,\dots ,t\}\backslash \{i,j\}$ as follows. If $i=2$, then let $c\in \{3,t\}$ and $c\in \{i-1,i+1\}$ otherwise. We can further ensure that $c\notin \{j-1,j+1\}$ and $(c,j)\ne (2,t)$. With this $x^{\{i,c\}}$ is a winning vector and $x^{\{j,c\}}$ is a losing vector. Thus, the classes i and j have to be different.

With respect to the Nakamura number we remark that we have to choose $n_1$coalitions of the form $(n_1-1,n_2,\dots ,n_t)$. All other coalitions exclude 2 players, so that we need $\left\lceil \frac{n_2+\dots +n_t}{2}\right\rceil$ of these. Taking $n_2=\dots =n_t=1$ gives the proposed bound. $\square$

Proposition 8

Let $k\ge 3$ be an integer. For $2k+1\le t\le k+2^k$ and $n\ge t$ we have ${\text {Nak}}^{\mathcal {S}}(n,t)\ge n-k$.

Proof

Let V be an arbitrary k-element subset of N. Let $U_1,\dots ,U_{t-k}$ be distinct subsets of V including all k one-element subsets and the empty subset. For each $1\le i\le t-k$ we choose a distinct player $v_i$ in $N\backslash V$. We define the game by specifying the set of winning coalitions as follows: The grand coalition and all coalitions of cardinality $n-1$ are winning. Coalition $N\backslash V$ and all of its supersets are winning. Additionally the following coalitions of cardinality $n-2$ are winning: For all $1\le i\le t-k$ and all $u\in U_i$ the coalition $N\backslash \{v_i,u\}$ is winning.

We can now check that the k players in V are of k different types, where each equivalence class contains exactly one player (this is due to the 1-element subsets $U_i$ of V). Players $v_i$ also form their own equivalence class, consisting of exactly one player—except for the case of $U_i=\emptyset$, where all remaining players from $N\backslash V$ are pooled. Thus, we have $2k+1\le t\le k+2^k$ types of players.

Suppose we are given a list $S_1,\dots ,S_l$ of winning coalitions with empty intersection, then $\left| N\backslash (S_i\backslash V)\right| =1$, i.e., every winning coalition can miss at most one player from $N\backslash V$. Thus, the Nakamura number is at least $n-k$. $\square$

7 Relations for the Nakamura number

As we have already remarked, the lower bound of Theorem 1 can be strengthened if we maximize the quota, i.e., if we solve

$$\begin{aligned}&\max q\\&w(S) \ge q\quad \forall S\in \mathcal {W}\\&w(T) < q\quad \forall T\in \mathcal {L}\\&w(N) = 1\\&w_i \ge 0\quad \forall 1\le i\le n \end{aligned}$$

Since the losing coalitions were not used in the proof of the lower bound inTheorem 1, we consider the linear program

$$\begin{aligned}&\max q \\&w(S) \ge q\quad \forall S\in \mathcal {W}\\&w(N) = 1\\&w_i \ge 0\quad \forall 1\le i\le n, \end{aligned}$$

which has the same set of optimal solutions, except for the target value, as

$$\begin{aligned}&\min 1-q\\&w(S) \ge q\quad \forall S\in \mathcal {W}\\&w(N) = 1\\&w_i \ge 0\quad \forall 1\le i\le n. \end{aligned}$$

Note that $(N,\mathcal {W})$ does not need to be weighted. Here the optimal value $1-q$ is also called the minimum maximum excess $e^\star$, which arises in the determination of the nucleolus.

Dividing the target function by $q>0$ and replacing $w_i=w_i'q$, which is a monotone transform, we obtain that the set of the optimal solutions of the previous LP is the same as the one of:

$$\begin{aligned}&\min \frac{1-q}{q}=\frac{1}{q}-1\\&w'(S) \ge 1\quad \forall S\in \mathcal {W}\\&w'(N) = \frac{1}{q}\\&w'_i \ge 0\quad \forall 1\le i\le n, \end{aligned}$$

If we now set $\varDelta :=\frac{1}{q}-1$ and add $\varDelta \ge 0$, we obtain the definition of the price of stability for games where the grand coalition is winning, see e.g. Bachrach et al. (2009). Thus, we have:

Theorem 4

Let $(N,\mathcal {W})$ be a simple game.

• (a) We have $\nu (N,\mathcal {W})\ge \left\lceil \frac{1}{e^\star }\right\rceil$ for the minimum maximum excess $e^\star$ of $(N,\mathcal {W})$.

• (b) We have $\nu (N,\mathcal {W})\ge \left\lceil \frac{1+\varDelta }{\varDelta }\right\rceil =\left\lceil \frac{1}{1-q}\right\rceil$ for the price of stability $\varDelta$ of $(N,\mathcal {W})$.

Note that in part (b) we formally obtain the same lower bound as in Theorem 1, while there is of course no notion of a quota q in a simple game. We remark that we have $e^\star =0$ or $\varDelta =\frac{e^\star }{1-e^\star }=0$ if and only if $(N,\mathcal {W})$ contains a vetoer. In general, the Nakamura number is large if the price of stability is low. It seems that Theorem 4 is the tightest and most applicable lower bound that we have at hand for the Nakamura number of a simple game. An interesting question is to study under what conditions it attains the exact value.

7.1 The Nakamura number and the one-dimensional cutting stock problem

Finally we would like to mention another relation between the Nakamura number of a weighted game and a famous optimization problem—the one-dimensional cutting stock problem. Here, one-dimensional objects like e.g. paper reels or wooden rods, all having length $L\in \mathbb {R}_{>0}$ should be cut into pieces of lengths $l_1,\dots ,l_m$ in order to satisfy the corresponding order demands $b_1,\dots ,b_m\in \mathbb {Z}_{>0}$. The minimization of waste is the famous 1CSP. By possible duplicating some lengths $l_i$, we can assume $b_i=1$ for all $1\le i\le m$, while this transformation can increase the value of m. Using the abbreviations $l=(l_1,\dots ,l_m)^T$ we denote an instance of 1CSP by $E=(m,L,l)$. The classical ILP formulation for the cutting stock problem by Gilmore and Gomory is based on so-called cutting patterns, see Gilmore and Gomory (1961). We call a pattern $a\in \{0,1\}^m$ feasible (for E) if $l^{\top }a\le L$. By P(E) we denote the set of all patterns that are feasible for E. Given a set of patterns $P=\{a^1,\dots ,a^r\}$ (of E), let A(P) denote the concatenation of the pattern vectors $a^i$. With this we can define

$$\begin{aligned} z_B(P,m):= & {} \sum _{i=1}^{r} x_i \rightarrow \min \; \text { subject to } \; A(P)x = \mathbf {1}, \; x \in \{0,1\}^{r}\quad \text {and}\\ z_C(P,m):= & {} \sum _{i=1}^{r} x_i \rightarrow \min \; \text { subject to } \; A(P)x = \mathbf {1}, \; x \in [0,1]^{r}. \end{aligned}$$

Choosing $P=P(E)$ we obtain the mentioned ILP formulation for 1CSP of Gilmore and Gomory (1961) and its continuous relaxation. Obviously we have $z_B(P(E),m)\ge \left\lceil z_C(P(E),m)\right\rceil$. In cases of equality one speaks of an IRUP (integer round-up property) instance—a concept introduced for general linear minimization problems in Baum and Trotter (1981). In practice almost all instances have the IRUP. Indeed, the authors of Scheithauer and Terno (1995) have conjectured that $z_B(P(E),m)\le \left\lceil z_C(P(E),m)\right\rceil +1$—called the MIRUP property (modified integer round-up property), which is one of the most important theoretical issues about 1CSP, see also Eisenbrand et al. (2013).

There is a strong relation between the 1CSP instances and weighted games, see Kartak et al. (2015). For each weighted games there exists an 1CSP instance where the feasible patterns correspond to the losing coalitions. For the other direction the feasible patterns of a 1CSP instance correspond to the losing coalitions of a weighted game if the all-one vector is non-feasible. In our context, we can utilize upper bounds for $z_B$ in at least two ways.

Lemma 5

Let $(N,\mathcal {W})$ be a strong simple game on n players, then $\nu (N,\mathcal {W})\le z_B(\overline{\mathcal {L}},n)$, where $\overline{\mathcal {L}}$ denotes the incidence vectors corresponding to the losingcoalitions $\mathcal {L}=2^N\backslash \mathcal {W}\subseteq 2^N$.

Proof

The value $z_B(\overline{\mathcal {L}},n)$ corresponds to the minimal number of losing coalitions that partition the set N, which is the same as the minimum number of (maximal) losing coalitions that cover the grand coalition N. Let $L_1,\dots ,L_r$ denote a list of losing coalitions, where $r=z_B(\overline{\mathcal {L}},n)$. Since the game $(N,\mathcal {W})$ is strong thecoalitions $N\backslash L_1,\dots ,N\backslash L_r$ are winning and have an empty intersection, so that $\nu (N,\mathcal {W})\le z_B(\overline{\mathcal {L}},n)$. $\square$

As the assumption of a strong simple game (without vetoers) implies $\nu (N,\mathcal {W})\in \{2,3\}$, the applicability is quite limited. This is not the case for the second, more direct, connection.

Proposition 9

For a simple game $(N,\mathcal {W})$ on n players we have $\nu (N,\mathcal {W})=z_B(\mathbf {1}-\overline{\mathcal {W}},n)$, where $\overline{\mathcal {W}}$ denotes the incidence vectors corresponding to the winningcoalitions and $\mathbf {1}$ is the vector with n ones.

Proof

Let $r=z_B(\mathbf {1}-\overline{\mathcal {W}},n)$ and $x_1,\dots , x_r$ corresponding incidence vectors. Then the sets $S_i$ corresponding to the incidence vectors $\mathbf {1}-x_i$ are winning and have empty intersection. If otherwise, $S_1,\dots , S_r$ are winning coalitions with empty intersection, then we can enlarge the coalitions to $T_1,\dots , T_r$ such that the intersection remains empty but every player is missing in exactly one of the $T_i$. Since the $T_i$ are winning coalitions by construction, $\mathbf {1}$ minus the incidence vector of $T_i$ gives r vectors that are feasible for $z_B(\mathbf {1}-\overline{\mathcal {W}},n)$. $\square$

Example 9

For an integer $k\ge 2$ consider the weighted game $v=\left[ 16k-20;{9}^{\{k\}},{7}^{\{k\}}\right]$. We can easily check that all coalitions of size $2k-2$ are winning while all coalitions of size $2k-3$ are losing, so that $v=[2k-2;1^{2k}]$ and $\nu (v)=k$. The lower bound of Theorem 1 only gives $\nu (v)\ge \left\lceil \frac{4k}{5}\right\rceil$. The feasible incidence vectors in $z_B(\mathbf {1}-\overline{\mathcal {W}},n)$ are those that contain at most two 1s, so that even $z_C(\mathbf {1}-\overline{\mathcal {W}},n)$ gives a tight upper bound.

Of course the advantage of the incidence vectors is that no explicit weights are involved, while the lower bound of Theorem 1 depends on the weighted representation. We remark that $z_B(\mathbf {1}-\overline{\mathcal {W}},n)\ge \left\lceil \frac{1}{1-q'}\right\rceil$ for any normalized representation $(q',w')$ of $(N,\mathcal {W})$.

We can also use 1CSP instances without the IRUP property to construct weighted games where the lower bound of Theorem 1 is never tight for any weightedrepresentation. Let $L=155$ be the length of the material to be cut and

$$\begin{aligned}l=(9,12,12,16,16,46,46,54,69,77, 102)\end{aligned}$$

be the lengths of the requested final pieces. Taking $\sum _{i=1}^{11} l_i -L=304$ as quota gives the weighted game $v=[304;9,12,12,16,16,46,46,54,69,77,102]$. Theorem 1 gives $\nu (v)\ge 3$ while $\nu (v)=4$.

Conjecture 3

For any weighted game $(N,\mathcal {W})$ on n players we have $\nu (N,\mathcal {W})\le \left\lfloor z_C(\mathbf {1}-\overline{\mathcal {W}},n)\right\rfloor +1$.

8 Conclusion

The Nakamura number measures the degree of rationality of preference aggregation rules such as simple games in the voting context. It indicates the extent to which the aggregation rule can yield well defined choices. If the number of alternatives to choose from is less than this number, then the rule in question will identify “best” alternatives. The larger the Nakamura number of a rule, the greater the number of alternatives the rule can rationally deal with. This paper provides new results on: the computation of the Nakamura number, lower and upper bounds for it or the maximum achievable Nakamura number for subclasses of simple games and parameters as the number of players and the number of equivalent types of them. We highlight the results found in the classes of weighted, complete, and $\alpha$-roughly weighted simple games. In addition, some enumerations for some classes of games with a given Nakamura number are obtained.

Further relations of the Nakamura number to other concepts of cooperative game theory like the price of stability of a simple game or the one-dimensional cutting stock problem are provided.

As future research, it would be interesting to study the truth of Conjectures 1 and 2 or finding new results on the Nakamura number for other interesting subclasses of simple games, as for example, weakly complete simple games. However, the main open question is to determine further classes where the lower bound of Theorem 1 is tight and to come up with tighter upper bounds. As suggested by the associate editor, the study of the probability distribution of the Nakamura number for simple games and subclasses thereof is an interesting research problem.

Proof of Theorem 2

Proof

• (a) At first we remark that the proposed exact value coincides with the lower bound from Theorem 1. Next we observe

  $$\begin{aligned} q^r=\frac{\left\lceil \overline{q}(\varOmega +r)\right\rceil }{\varOmega +r} \le \frac{1+\overline{q}(\varOmega +r)}{\varOmega +r}= \overline{q}+\frac{1}{\varOmega +r}\le \overline{q}+\frac{1}{r}. \end{aligned}$$

  Consider the following greedy way of constructing the list $S_1,\dots ,S_k$ of winning coalitions with empty intersection. Starting with $i=1$ and $h=1$ we choose an index $h\le g\le n$ such that $U_i=\{h,h+1,\dots ,g\}$ has a weight of at most $(1-q^r)(\varOmega +r)$ and either $g=n$ or $U_i\cup \{g+1\}$ has a weight larger than $(1-q^r)(\varOmega +r)$. Given $U_i$ we set $S_i=\{1,\dots ,n+r\}\backslash U_i$, $h=g+1$, and increase i by one. If $(1-q^r)(\varOmega +r)\ge w_i$ for all $1\le i\le n$, then no player in $\{1,\dots ,n\}$ has a too large weight to be dropped in this manner. Since we assume the weights to be ordered, it suffices to check the proposed inequality for $w_1$. To this end we consider

  $$\begin{aligned}&(1-q^r)(\varOmega +r)\ge \left( 1-\overline{q}-\frac{1}{r}\right) \cdot (\varOmega +r)\\&\quad = (1-\overline{q})\varOmega -1-\frac{\varOmega }{r} +(1-\overline{q})r\ge (1-\overline{q})r-2, \end{aligned}$$

  where we have used $r\ge \varOmega$. Since $r\ge \frac{2+w_1}{1-\overline{q}}\ge \frac{2+w_i}{1-\overline{q}}$ the requested inequality is satisfied.

  So far the winning coalitions $S_i$ can have weights larger than $q^r(\varOmega +r)$ and their intersection is given by the players of weight 1, i.e. by $\{n+1,\dots ,n+r\}$. For all $1\le i<k$ let $h_i$ be the player with the smallest index in $U_i$, which is indeed one of the heaviest players in this subset. With this we conclude $w(S_i)\le q^r(\varOmega +r)+w_{h_i}-1$ since otherwise another player from $U_{i+1}$ could have been added. In order to lower the weights of the $S_i$ to $q^r(\varOmega +r)$ we remove $w(S_i)-\left( q^r(\varOmega +r)\right) )$ players of $S_i$ for all $1\le i\le k$, starting from player $n+1$ and removing each player exactly once. Since $\sum _{i=1}^{k-1} w_{h_i}\le \varOmega \le r$ this is indeed possible. Now we remove the remaining, if any, players of weight 1 from $S_k$ until they reach weight $q^r(\varOmega +r)$ and eventually start new coalitions $S_i=\{1,\dots ,n+r\}$ removing players of weight 1. Finally we end up with $r+l$ winning coalitions with empty intersection, where the coalitions $1\le i\le k+l-1$ have weight exactly $q^r(\varOmega +r)$ and the sets $\{1,\dots ,n+r\}\backslash S_i$ do contain only players of weight 1 for $i\ge r+1$. Since each player is dropped exactly once the Nakamura number of the game equals $k+l=\left\lceil \frac{1}{1-q^r}\right\rceil$.

• (b) We write $\overline{q}=\frac{p}{q}$ with positive comprime integers p, q. If $p\ne q-1$, then

  $$\begin{aligned} \left\lceil \frac{1}{1-\overline{q}}\right\rceil =\left\lceil \frac{q}{q-p}\right\rceil >\frac{1}{1-\overline{q}}, \end{aligned}$$

  i.e., we always round up. Obviously $\lim _{r\rightarrow \infty } q^r=\overline{q}$ (and $q^r\ge \overline{q}$). Since also

  $$\begin{aligned} \lim _{r\rightarrow \infty } \frac{w(N^r)}{w(N^r)-q^r w(N^r)-w_1+1}= \lim _{r\rightarrow \infty } \frac{w(N^r)}{w(N^r)-q^r w(N^r)}=\frac{1}{1-\overline{q}}, \end{aligned}$$

  we can apply the upper bound of Theorem 1 to deduce that the lower bound is attained with equality for sufficiently large replication factors r.

  In the remaining part we assume $p=q-1$, i.e., $1-\overline{q}=\frac{1}{q}$. If $\varOmega \cdot r$ is not divisible by q, i.e. $q^r>\overline{q}$, we can apply a similar argument as before, so that we restrict ourselves to the case $q|\varOmega \cdot r$, i.e. $\overline{q}=q^r$. Here we have to show that the Nakamura number exactly equals q (in the previous case it equals $q+1$). This is possible if we can partition the grand coalition N into q subsets $U_1,\dots ,U_q$ all having a weight of exactly $\frac{\varOmega \cdot r}{q}$. (The list of winning coalitions with empty intersection is then given by $S_i=N\backslash U_i$ for $1\le i\le q$.) This boils down to a purely theoretical question of number theory, which is solved in the next lemma.

$\square$

Lemma 6

Let $g\ge 2$ and $w_1,\dots ,w_n$ be positive integers with $\sum \limits _{i=1}^n w_i=\varOmega$ and greatest common divisor 1.

There exists an integer K such that for all $k\ge K$, where $\frac{k\cdot \varOmega }{q}\in \mathbb {N}$, there exist non-negative integers $u_j^i$ with

$$\begin{aligned} \sum _{j=1}^n u_j^i\cdot w_j=\frac{k\cdot \varOmega }{q}, \end{aligned}$$

for all $1\le i\le q$, and

$$\begin{aligned} \sum _{i=1}^q u_j^i=k, \end{aligned}$$

for all $1\le j\le n$.

Proof

For $k=1$, setting $u_j^i=\frac{1}{q}$ is an inner point of the polyhedron

$$\begin{aligned} P=\left\{ u_j^i\in \mathbb {R}_{\ge 0}\mid \sum _{j=1}^n u_j^i\cdot w_j=\frac{\varOmega }{q}\,\forall 1\le i\le q \text { and } \sum _{i=1}^q u_j^i=1\,\forall 1\le j\le n\right\} , \end{aligned}$$

so that is has non-zero volume.

For general $k\in \mathbb {N}_{>0}$ we are looking for lattice points in the dilation $k\cdot P$. If q is a divisor of $k\cdot \varOmega$, then $\mathbb {Z}^{nq}\cap k\cdot P$ is a lattice of maximal rank in the affine space spanned by $k\cdot P$. Let $k_0$ the minimal positive integer such that q divides $k_0\cdot \varOmega$. Using Erhart Theory one can count the number of lattice points in the parametric rational polytope in $m\cdot k_0\cdot P$, where $m\in \mathbb {N}_{>0}$, see e.g. Beck and Robins (2007). To be more precise, the number of (integer) lattice points in $m\cdot k_0\cdot P$ grows asymptotically as $m^d {\text {vol}}_d(k_0 P)$, where d is the dimension of the affine space A spanned by $k_0\cdot P$ and ${\text {vol}}_d (k_0 P)$ is the (normalized)

volume of $k_0\cdot P$ within A. Due to the existence of an inner point we have ${\text {vol}}_d (k_0 P)>0$, so that the number of integer solutions is at least 1 for $m\gg 0$. $\square$

There is a relation between the problem of Lemma 6 and the Frobenius number, which asks for the largest integer which can not be expressed as a non-negative integer linear combination of the $w_i$. Recently this type of problem occurs in the context on minimum sum integer representations, see Freixas and Kurz (2014b). According to the Frobenius theorem every sufficiently large number can be expressed as such a sum. Here we ask for several such representations which are balanced, i.e., each coin is taken equally often.