Bounds for the Nakamura number

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. More precisely, the computational problem to decide whether \(\nu ([q;w_1,\dots ,w_n])=2\) is NP-hard. A proof can be obtained by a reduction to the NP-hard partition problem. So, for integers \(w_1,\dots ,w_n\) we have to decide whether there exists a subset \(S\subseteq N\) such that \(\sum _{i\in S}w_i=\sum _{i\in N\backslash S} w_i\), where we use the abbreviation \(N=\{1,\dots ,n\}\). Consider the weighted game \([w(N)/2;w_1,\dots ,w_n]\). It has Nakamura number 2 if and only if a subset S with \(w(S)=w(N\backslash S)\) exists. Further complexity results for the Nakamura number can e.g. be found in Bartholdi et al. (1991) and Takamiya and Tanaka (2016).

The authors thank the anonymous referees and the associate editor for their careful reading of a preliminary version of this paper. Their constructive remarks were extremely useful to improve its presentation.

Authors and Affiliations

1. Department of Mathematics and Engineering, School of Manresa, Universitat Politècnica de Catalunya, Catalonia, Spain

   Josep Freixas

2. Department of Mathematics, Physics, and Computer Science, University of Bayreuth, 95440, Bayreuth, Germany

   Sascha Kurz

Corresponding author

Correspondence to Sascha Kurz.

Josep Freixas’s research is partially supported by funds from the spanish Ministry of Economy and Competitiveness (MINECO) and from the European Union (FEDER funds) under Grant MTM2015-66818-P (MINECO/FEDER).

Proof of Theorem 2

Proof

1. (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 \).

2. (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

for all \(1\le i\le q\), and

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

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.

Reprints and permissions