Simple Games Versus Weighted Voting Games

Abstract

A simple game (N, v) is given by a set N of n players and a partition of $2^N$ into a set $\mathcal {L}$ of losing coalitions L with value $v(L)=0$ that is closed under taking subsets and a set $\mathcal {W}$ of winning coalitions W with $v(W)=1$. Simple games with $\alpha = \min _{p\ge 0}\max _{W\in \mathcal{W},L\in \mathcal{L}} \frac{p(L)}{p(W)}<1$ are exactly the weighted voting games. Freixas and Kurz (IJGT, 2014) conjectured that $\alpha \le \frac{1}{4}n$ for every simple game (N, v). We confirm this conjecture for two complementary cases, namely when all minimal winning coalitions have size 3 and when no minimal winning coalition has size 3. As a general bound we prove that $\alpha \le \frac{2}{7}n$ for every simple game (N, v). For complete simple games, Freixas and Kurz conjectured that $\alpha =O(\sqrt{n})$. We prove this conjecture up to a $\ln n$ factor. We also prove that for graphic simple games, that is, simple games in which every minimal winning coalition has size 2, computing $\alpha$ is NP-hard, but polynomial-time solvable if the underlying graph is bipartite. Moreover, we show that for every graphic simple game, deciding if $\alpha <a$ is polynomial-time solvable for every fixed $a>0$.

These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

1 Introduction

Cooperative Game Theory provides a mathematical framework for capturing situations where subsets of agents may form a coalition in order to obtain some collective profit or share some collective cost. Formally, a cooperative game (with transferable utilities) consists of a pair (N, v), where N is a set of n agents called players and $v: 2^N\rightarrow {\mathbb R}_+$ is a value function that satisfies $v(\emptyset ) = 0$. In our context, the value v(S) of a coalition $S\subseteq N$ represents the profit for S if all players in S choose to collaborate with (only) each other. The central problem in cooperative game theory is to allocate the total profit v(N) of the grand coalition N to the individual players $i \in N$ in a “fair” way. To this end various solution concepts such as the core, Shapley value or nucleolus have been designed; see [24] for an overview. For example, core solutions try to allocate the total profit such that every coalition $S \subseteq N$ gets at least v(S). This is of course not always possible, e.g., the core might be empty. This leads to related questions like: “How much do we need to spend in total if we want to give at least v(S) to each coalition $S \subseteq N$?” In the specific case of simple games (cf. below) where v takes only values 0 and 1, classifying coalitions into “losing” and “winning” coalitions resp., one may also ask: “How much do we have to give in the worst case to a losing coalition if we want to give at least $v(S)=1$ to each winning coalition?”

As mentioned above, we study simple games. Simple games form a classical class of games, which are well studied; see also the book of Taylor and Zwicker [29]. The notion of being simple means that every coalition either has some equal amount of power or no power at all. Formally, a cooperative game (N, v) is simple if v is a monotone 0–1 function with $v(\emptyset )=0$ and $v(N)=1$, so $v(S)\in \{0,1\}$ for all $S\subseteq N$ and $v(S)\le v(T)$ whenever $S\subseteq T$. In other words, if v is simple, then there is a set $\mathcal {W} \subseteq 2^N$ of winning coalitions W that have value $v(W)=1$ and a set $\mathcal {L} \subseteq 2^N$of losing coalitions L that have value $v(L)=0$. Note that $N\in \mathcal{W}$, $\emptyset \in \mathcal{L}$ and $\mathcal{W}\cup \mathcal{L}=2^N$. The monotonicity of v implies that subsets of losing coalitions are losing and supersets of winning coalitions are winning. A winning coalition W is minimal if every proper subset of W is losing, and a losing coalition L is maximal if every proper superset of L is winning.

A simple game is a weighted voting game if there exists a payoff vector $p \in {\mathbb R}_+^n$ such that a coalition S is winning if $p(S)\ge 1$ and losing if $p(S)<1$. Weighted voting games are also known as weighted majority games and form one of the most popular classes of simple games.

However, it is easy to construct simple games that are not weighted voting games. We give an example below, but in fact there are many important simple games that are not weighted voting games, and the relationship between weighted voting games and simple games is not yet fully understood. Therefore, Gvozdeva, Hemaspaandra, and Slinko [16] introduced a parameter $\alpha$, called the critical threshold value, to measure the “distance” of a simple game to the class of weighted voting games:

$$\begin{aligned} \alpha ~= ~\alpha (N,v)~=\min _{p \ge 0}~ \max _{W,L}~ \frac{p(L)}{p(W)}, \end{aligned}$$

(1)

where the maximum is taken over all winning coalitions in $\mathcal{W}$ and all losing coalitions in $\mathcal{L}$. A simple game (N, v) is a weighted voting game if and only if $\alpha <1$. This follows from observing that each optimal solution p of (1) can be scaled to satisfy $p(W)\ge 1$ for all winning coalitions W.

A concrete example of a simple game (N, v) that is not a weighted voting game and that has in fact a large value of $\alpha$ was given in [12]:

Example

Let $N=\{1, \dots , n\}$ for some even integer $n\ge 4$, and let the minimal winning coalitions be the pairs $\{1,2\}, \{2,3\}, \dots \{n-1, n\}, \{n,1\}$. Consider any payoff $p\ge 0$ satisfying $p(W) \ge 1$ for every winning coalition W. Then $p_i+p_{i+1}\ge 1$ for $i=1,\ldots ,n$ (where $n+1=1$). This means that $p(N)\ge \frac{1}{2}n$. Then, for at least one of $L=\{2,4,6,\dots , n\}$ and $L=\{1,3,5, \dots , n-1\}$, we have $p(L)\ge \frac{1}{4}n$, showing that $\alpha \ge \frac{1}{4}n$. On the other hand, it is easily seen that $p \equiv \frac{1}{2}$ satisfies $p(W) \ge 1$ for all winning coalitions and $p(L) \le \frac{1}{4}n$ for all losing coalitions, showing that $\alpha \le \frac{1}{4}n$. Thus $\alpha =\frac{1}{4}n$.

This example led the authors of [12] to the following conjecture:

Conjecture 1 [12]. For every simple game (N, v), it holds that $\alpha \le \frac{1}{4}n$.

Our Results. In Sect. 2 we prove that Conjecture 1 holds for the case where all minimal winning coalitions have size 3 and for its complementary case where no minimal winning collection has size 3. We were not able to prove Conjecture 1 for all simple games. However, in Sect. 3 we show that $\alpha \le \frac{2}{7}n \approx 0.2858 n$.

In Sect. 4 we consider a subclass of simple games based on a natural desirability order [25]. A simple game (N, v) is complete if the players can be ordered by a complete, transitive ordering $\succeq$, say, $1 \succeq 2 \succeq \dots \succeq n$, indicating that higher ranked players have more “power” than lower ranked players. More precisely, $i \succeq j$ means that $v(S\cup i) \ge v(S \cup j)$ for any coalition $S \subseteq N\backslash \{i,j\}$. The class of complete simple games properly contains all weighted voting games [14]. For complete simple games, we show an asymptotically lower bound on $\alpha$, namely $\alpha =O(\sqrt{n}\ln n)$. This bound matches, up to a $\ln n$ factor, the lower bound of $\Omega (\sqrt{n})$ in [12] (conjectured to be tight in [12]). Intuitively, complete simple games are much closer to weighted voting games than arbitrary simple games. So, from this perspective, our result seems to support the hypothesis that $\alpha$ is indeed a sensible measure for the distance to weighted voting games.

In Sect. 5 we discuss some algorithmic and complexity issues. We focus on instances where all minimal winning coalitions have size 2. We say that such simple games are graphic, as they can conveniently be described by a graph $G=(N,E)$ with vertex set N and edge set $E~=~\{ij~|~\{i,j\}~ \text {is winning} \}$. For graphic simple games we show that computing $\alpha$ is NP-hard in general, but polynomial-time solvable if the underlying graph $G=(N,E)$ is bipartite, or if $\alpha$ is known to be small (less than a fixed number a).

Related Work. Due to their practical applications in voting systems, computer operating systems and model resource allocation (see e.g. [3, 7]), structural and computational complexity aspects for solution concepts for weighted voting games have been thoroughly investigated [9, 10, 13, 16].

Another way to measure the distance of a simple game to the class of weighted voting games is to use the dimension of a simple game [28], which is the smallest number of weighted voting games whose intersection equals a given simple game. However, computing the dimension of a simple game is NP-hard [8], and the largest dimension of a simple game with n players is $2^{n-o(n)}$ [21]. Moreover, $\alpha$ may be arbitrarily large for simple games with dimension larger than 1. Hence there is no direct relation between the two distance measures. Gvozdeva, Hemaspaandra, and Slinko [16] introduced two other distance parameters as well. One measures the power balance between small and large coalitions. The other one allows multiple thresholds instead of threshold 1 only.

For graphic simple games, it is natural to take the number of players n as the input size for answering complexity questions, but in general simple games may have different representations. For instance, one can list all minimal winning coalitions or all maximal losing coalitions. Under these two representations the problem of deciding if $\alpha < 1$, that is, if a given simple game is a weighted voting game, is also polynomial-time solvable. This follows from results of [17, 23], as shown in [13]. The latter paper also showed that the same result holds if the representation is given by listing all winning coalitions or all losing coalitions.

As mentioned, a crucial case in our study is when the simple game is graphic, that is, defined on some graph $G=(N,E)$. In the corresponding matching game a coalition $S \subseteq N$ has value v(S) equal to the maximum size of a matching in the subgraph of G induced by S. One of the most prominent solution concepts is the core of a game, defined by $core(N,v) := \{p \in {\mathbb R}^n ~|~ p(N)=v(N), ~p(S) \ge v(S)~ \forall S \subseteq N\}$. Matching games are not simple games. Yet their core constraints are readily seen to simplify to $p\ge 0$ and $p_i+p_j \ge 1$ for all $ij \in E$. Classical solution concepts, such as the core and core-related ones like least core, nucleolus or nucleon are well studied for matching games, see, for example, [4, 5, 11, 19, 20, 27]. However, for graphic simple games we aim to bound p(L) over all losing coalitions, subject to $p \ge 0$, $p_i+p_j \ge 1$ for all $ij \in E$, whereas for matching games with an empty core we wish to bound p(N), subject to $p \ge 0$, $p_i+p_j \ge 1$ for all $ij \in E$. Nevertheless, basic tools from matching theory like the Gallai-Edmonds decomposition play a role in both cases.

2 Two Complementary Cases

We will treat the following two “complementary” cases: when all winning coalitions have size equal to 3, and when no winning coalition has size equal to 3. First observe that winning coalitions of size 1 do not cause any problems. If $\{i\}$ is a winning coalition of size 1, we satisfy it by setting $p_i=1$. Since no losing coalition L contains i, we may remove i from the game and solve (1) with respect to the resulting subgame. A similar argument applies if some $i \in N$ is not contained in any minimal winning coalition. We then simply define $p_i=0$ and remove i from the game. Thus, we may assume without loss of generality that all minimal winning coalitions have size at least 2 and that they cover all of N.

We first investigate the case where all minimal winning coalitions have size exactly 2. This case (which is a crucial case in our study) can conveniently be translated to a graph-theoretic problem. Let $G=(N,E)$ be the graph with vertex set N whose edges are exactly the minimal winning coalitions of size 2 in our game (N, v). Our assumption that N is completely covered by minimal winning coalitions means that G has no isolated vertices. Losing coalitions correspond to independent sets of vertices $L\subseteq N$. Then the min max problem (1) becomes

$$\begin{aligned} \alpha ~:=~\alpha _G ~:=~ \min _p ~ \max _L ~ p(L), \end{aligned}$$

(2)

where the minimum is taken over all feasible pay-off vectors p, that is, $p\in {\mathbb R}_+^n$ with $p_i+p_j \ge 1$ for every $ij\in E$, and the maximum is taken over all independent sets $L\subseteq N$.

We first consider the case where $G=(A \cup B, E)$ is bipartite. To explain the basic idea, we introduce the following concept (illustrated in Fig. 1).

Fig. 1.

A well-spread bipartite graph.

Definition

Let $G=(A \cup B,E)$ be a bipartite graph of order $n = |A|+|B|$ without isolated notes and assume without loss of generality that $|A| \le |B|$. Let $\lambda \le \frac{1}{2}$ such that $|A|=\lambda n$ (and $|B|=(1-\lambda )n$). We say that G is well-spread with parameter $\lambda$ if for all $S\subseteq A$ we have

$$\frac{|S|}{|N(S)|} ~\le ~\frac{|A|}{|B|} ~=~ \frac{\lambda }{1-\lambda }.$$

(Here, as usual, $N(S) \subseteq B$ denotes the set of neighbors of S in B.)

Examples of well-spread bipartite graphs are biregular graphs or biregular graphs minus an edge. Note that if G is well-spread with parameter $\lambda \le \frac{1}{2}$, then Hall’s condition $|N(S)| \ge |S|$ for all $S \subseteq A$ is satisfied, implying that A can be completely matched to B (see, for example, [22]). The following lemma is the key observation.

Lemma 1

Let $G=(A\cup B,E)$ be well-spread with parameter $\lambda \le \frac{1}{2}$. Then $p\equiv \lambda$ on B and $p \equiv 1-\lambda$ on A yields $\alpha _G \le \frac{1}{4}n$.

Proof

Assume $L\subseteq N$ is an independent set. Let $\rho \le 1$ such that $|L \cap A| =\rho \lambda n$. Since G is well-spread, we get $|N(L\cap A)| \ge \rho (1- \lambda )n$, so that $|L \cap B| \le (1-\rho )(1-\lambda )n$. Thus $p(L)=|L\cap A|(1-\lambda )+|L\cap B|\lambda \le \rho \lambda n (1-\lambda ) + (1-\rho )(1-\lambda ) n \lambda \le \rho \frac{1}{4}n+(1-\rho )\frac{1}{4}n \le \frac{1}{4}n$.    $\square$

In general, when $G=(A \cup B,E)$ is not well-spread, we seek to decompose G into well-spread induced subgraphs $G_i=(A_i \cup B_i, E_i)$ with $A= \bigcup A_i$ and $B=\bigcup B_i$. Of course, this can only work if $G=(A \cup B,E)$ is such that A can be matched to B in G.

Proposition 1

Let $G=(A \cup B,E)$ be a bipartite graph without isolated vertices and assume that A can be matched into B. Then G decomposes into well-spread induced subgraphs $G_i=(A_i \cup B_i, E_i)$, with $A= \bigcup A_i$ and $B=\bigcup B_i$ in such a way that for all i, j with $i<j$, $\lambda _i \ge \lambda _j$ and no edges join $A_i$ to $B_j$.

Proof

Let $S \subseteq A$ maximize |S| / |N(S). Set $A_1:=S$ and $B_1:=N(S)$. Let $G'$ be the subgraph of G induced by $A\backslash A_1$ and $B':= B \backslash B_1$. Then $G'$ satisfies the assumption of the Proposition. Indeed, if $A'$ cannot be matched into $B'$ in $G'$, then there must be some $S'\subseteq A'$ with $|S'| > |N'(S')|$, where $N'(S')=N(S')\backslash B_1$ is the neighborhood of $S'$ in $G'$. But then $|S \cup S'| =|S|+|S'|$ and $|N(S\cup S')|\le |N(S)|+|N'(S)|$ shows that S cannot maximize |S| / |N(S)|, a contradiction. Thus, by induction, we may assume that $G'$ decomposes in the desired way into well-spread subgraphs $G_2, \dots , G_k$ with parameters $\lambda _2 \ge \dots \ge \lambda _k$. The claim then follows by observing that (i) no edges join $B_1$ to $A'$; and (ii) $\lambda _1 \ge \lambda _2$ (otherwise $S \cup A_2$ would contradict the choice of S maximizing |S| / |N(S)|).    $\square$

We combine the last two results.

Corollary 1

For every bipartite graph $G=(A\cup B,E)$ of order n satisfying the assumption of Proposition 1, there exists a payoff vector $p\ge 0$ such that $p_i+p_j \ge 1$ for $ij\in E$ and $p(L)\le \frac{1}{4}n$ for any independent set $L \subseteq A \cup B$. In addition, p can be chosen so as to satisfy $p \ge \frac{1}{2}$ on A.

Proof

The result follows immediately from Lemma 1 and Proposition 1. Note that if p is chosen as $p\equiv 1-\lambda _i$ on $A_i$, then it holds that $p \ge \frac{1}{2}$ indeed.    $\square$

As we will see, the assumption of Proposition 1 is not really restrictive for our purposes. A (connected) component C of a graph G is even (odd) if C has an even (odd) number of vertices. A graph $G=(N,E)$ is factor-critical if for every vertex $v\in V(G)$, the graph $G-v$ has a perfect matching. We recall the well-known Gallai–Edmonds Theorem (see [22]) for characterizing the structure of maximum matchings in G; see also Fig. 2. There exists a (unique) subset $A\subseteq N$, called a Tutte set, such that (i) every even component of $G-A$ has a perfect matching; (ii) every odd component of $G-A$ is factor-critical; and (iii) every maximum matching in G is the union of a perfect matching in each even component, a nearly perfect matching in each odd component and a matching that matches A (completely) to the odd components.

Fig. 2.

Tutte set A splitting G into even and odd components (possibly single nodes).

We are now ready to derive our first main result.¹

Theorem 1

Let $G=(N,E)$ be a graph of order n. Then $\alpha _G \le \frac{1}{4}n.$

Proof

Let $A\subseteq N$ be a Tutte set. Contract each odd component in $G-A$ to a single vertex and let B denote the resulting set of vertices. The subgraph $\bar{G}$ induced by $A \cup B$ then satisfies the assumption of Corollary 1. Let $\bar{p} \in {\mathbb R}^{|A|+|B|}$ be the corresponding payoff vector. We define $p \in \mathbb {R}^n$ by setting $p_i=\bar{p}_i$ for every vertex $i \in A$ and every vertex i that corresponds to an odd component of size 1 in $G-A$. All other vertices get $p_j=\frac{1}{2}$.

It is straightforward to check that $p \ge 0$ and $p_i+p_j \ge 1$. Indeed, it holds that $\bar{p} \ge \frac{1}{2}$ everywhere except on B, so the only critical edges ij have $i \in A$ and j a singleton odd component. But in this case $p_i+p_j =\bar{p}_i+\bar{p}_j \ge 1$. Thus we are left to prove that for every independent set $L \subseteq N$, $p(L) \le \frac{1}{4}n$. Let $B_0$ denote the set of singleton odd components $i \in B$, $L_0 := (L \cap A) \cup (L\cap B_0)$ and $n_0 := |A|+|B|$. Clearly, $L_0$ is an independent set in the bipartite graph $\bar{G}$, and $p\equiv \bar{p}$ on $L_0$. We thus conclude that $p(L_0) \le \frac{1}{4}n_0$.

Next let us analyze $L\cap C$ where $C \subseteq N\backslash A$ is an even component. As C is perfectly matchable, L contains at most |C| / 2 vertices of C. So $p(L\cap C) \le \frac{1}{4}|C|$. A similar argument applies to the odd components. Let C be an odd component in $G-A$ of size at least 3. Then certainly L cannot contain all vertices of C, so there exists some $i \in C\backslash L$. Since C is factor-critical, $C\backslash i$ is perfectly matchable, implying that L can contain at most half of $C\backslash i$. Thus $|L \cap C| \le (|C|-1)/2$ and $p(L\cap C) \le (|C|-1)/4$.

Summarizing, $n-n_0 = |N| - (|A|+|B|)$ is the sum over all |C|, where C is an even component plus the sum over all $|C|-1$ where C is an odd component, and $p(L \backslash L_0)$ is at most a $\frac{1}{4}$ fraction of this, finishing the proof.    $\square$

We note that both decompositions that we use to define the payoff p can be computed efficiently. For the Edmonds–Gallai decomposition, this is a well-known fact (see, for example, [22]). For the decomposition into well-spread subgraphs, this follows from the observation that deciding whether $\max _S \frac{|S|}{|N(S)|} \le r$ is equivalent to $\min _S r|N(S)|-|S| \ge 0$, which amounts to minimizing the submodular function $f(S)=r|N(S)|-|S|$; see, for example, [26] for a strongly polynomial-time algorithm.

We now deal with the more general case where there are, in addition, minimal winning coalitions of size 4 or larger. First recall how the payoff p that we proposed in Corollary 1 works. For a bipartite graph $G=(A\cup B,E)$ that is split into well-spread subgraphs $G_i=(A_i \cup B_i, E_i)$ with parameter $\lambda _i$, we let $p \equiv \lambda _i$ on $B_i$. So for $\lambda _i < \frac{1}{4}$, p may be infeasible, that is, we may encounter winning coalitions W of size 4 or larger with $p(W) <1$. This problem can easily be remedied by raising p a bit on each $B_i$ and decreasing it accordingly on $A_i$. Indeed, the standard $(\lambda , 1-\lambda )$ allocation rule proposed in Lemma 1 is based on the simple fact that $\lambda (1-\lambda ) \le \frac{1}{4}$, which gives us some flexibility for modification in the case where $\lambda$ is small. More precisely, defining the payoff to be $p :\equiv \frac{1}{4(1-\lambda )} > \frac{1}{4}$ on B and $1-p <\frac{3}{4}$ on A for a bipartite graph $(G=(A \cup B,E)$, well-spread with parameter $\lambda$, would work as well and thus solve the problem. Indeed, the unique independent set L that maximizes p(L) is $L=B$ in this case, which gives $p(L)=p(B)=|B|/(4(1-\lambda ))= \frac{1}{4}n$.

There is one thing that needs to be taken care of. Namely, in Proposition 1 we assumed that $G=(A \cup B, E)$ has no isolated vertices, an assumption that can be made without loss of generality if we only have 2-element winning coalitions. Now we may have isolated vertices that are part of winning coalitions of size 4 or larger. But this does not cause any problems either. We simply assign $p:= \frac{1}{4}$ to these isolated vertices to ensure that indeed all winning coalitions W have $p(W) \ge 1$. Formally, this can also be seen as an extension of our decomposition: if $G=(A \cup B, E)$ contains isolated vertices, then they are all contained in B (once we assume that A can be completely matched into B). So the set of isolated vertices can be seen as a “degenerate” well-spread final subgraph $(A_k \cup B_k, E_k)$ with $A_k= \emptyset$ and parameter $\lambda _k=0$. Our proposed payoff $p \equiv \frac{1}{4(1-\lambda _k)}$ would then indeed assign $p= \frac{1}{4}$ to all isolated vertices.

It remains to observe that when we pass to general graphs, no further problems arise. Indeed, all that happens is that vertices in even and odd components get payoffs $p=\frac{1}{2}$ which certainly does no harm to the feasibility of p. Thus we have proved the following result.

Corollary 2

Let (N, v) be a simple game with no minimal winning coalition of size 3. Then $\alpha (N,v) \le \frac{1}{4}n$.  

We end this section with the complementary case where all minimal winning coalitions have size 3.

Proposition 2

Let (N, v) be a simple game with all minimal winning coalitions of size 3. Then $\alpha (N,v) \le \frac{1}{4}n$.

Proof

We try $p :\equiv \frac{1}{3}$, which is certainly feasible. If this yields $\max p(L) \le \frac{1}{4}n$, then we are done. Otherwise, there exists a losing coalition $L \subseteq N$ with $p(L) = \frac{1}{3}|L| > \frac{1}{4}n$, or equivalently, $|L|>\frac{3}{4}n$. In this case we use an alternative payoff $\tilde{p}$ given by $\tilde{p}\equiv 1$ on $N\backslash L$ and $\tilde{p} \equiv 0$ on L. Since $|N\setminus L| < \frac{1}{4}n$, this ensures $\tilde{p}(\tilde{L}) <\frac{1}{4}n$ for any losing coalition $\tilde{L}$. On the other hand, $\tilde{p}$ is feasible, since a winning coalition W cannot be completely contained in L, that is, there exists a player $i \in W$ with $\tilde{p}_i=1$ and hence $\tilde{p}(W) \ge 1$.    $\square$

We note that Proposition 2 is a pure existence result. To compute $\tilde{p}$ it requires to solve a maximum independent set problem in 3-uniform hypergraphs, which is NP-hard. This can be seen from a reduction from the maximum independent set problem in graphs, which is well known to be NP-hard (see [15]). Given a graph $G=(V,E)$, construct a 3-uniform hypergraph $\bar{G}$ as follows. Add $n=|V|$ new vertices labeled $1, \dots , n$ and extend each edge $e=ij \in E$ to n edges $\{i,j,1\}, \dots , \{i,j,n\}$ in $\bar{G}$. It is readily seen that a maximum independent set of vertices in $\bar{G}$ (that is, a set of vertices that does not contain any hyperedge) consists of the n new vertices plus a maximum independent set in G.

3 Minimal Winning Coalitions of Arbitrary Size

In this section we try to combine the ideas for the two complementary cases to derive an upper bound $\alpha \le \frac{2}{7}$ for the general case. The payoffs p that we consider will all satisfy $p \ge \frac{1}{4}$ so that only winning coalitions of size 2 and 3 are of interest. The basic idea is to start with a bipartite graph $(A\cup B, E)$ representing the size 2 winning coalitions and a payoff satisfying all these. Standard payoffs that we use satisfy $p \ge \frac{1}{4}$ on B and $p \ge \frac{1}{2}$ on A. Hence we have to worry only about 3-element winning coalitions contained in B. We seek to satisfy these by raising the payoff of some vertices in B without spending too much in total.

More precisely, consider a bipartite graph $G=(A \cup B, E)$ representing the winning coalitions of size 2. As before, we assume that A can be completely matched into B, so that our decomposition into well-spread subgraphs $G_i=(A_i \cup B_i, E_i)$ applies (with possibly the last subgraph $G_k=(A_k \cup B_k, E_k)$ having $A_k=\emptyset$ and $B_k$ consisting of isolated points, as explained at the end of the previous section). Recall the payoff $\bar{\lambda }_i :\equiv \frac{1}{4(1-\lambda _i)}$ on $B_i$ and $1-\bar{\lambda }_i$ on $A_i$ defined for the proof of Corollary 2. We first consider the following payoff $\bar{p} :\equiv 1-\bar{\lambda }_i$ on $A_i$ and $\bar{p} :\equiv \bar{\lambda }_i$ on $B_i$ for $\lambda _i \ge \frac{1}{4}$, so $\bar{\lambda }_i \ge \frac{1}{3}$. For subgraphs with $\lambda _i < \frac{1}{4}$ (including possibly a final $\lambda _k=0$) we define $\bar{p} \equiv \frac{2}{3}$ on $A_i$ and $\bar{p} \equiv \frac{1}{3}$ on $B_i$. Thus it holds that $\bar{p} \ge \frac{1}{3}$ everywhere, in particular, $\bar{p}$ is feasible with respect to all winning coalitions of size at least 3.

Let $\bar{L}$ be a losing coalition with maximum $\bar{p}(L)$. We define an alternative payoff $\tilde{p}$ as follows: For $\lambda _i \ge \frac{1}{4}$ we set $\tilde{p} :\equiv 1- \bar{\lambda }_i$ on $A_i$,  $\tilde{p} :\equiv \bar{\lambda }_i$ on $B\cap \bar{L}$ and $\tilde{p}:\equiv \frac{1}{2}$ on $B_i\backslash \bar{L}$. For $\lambda _i <\frac{1}{4}$ we set $\tilde{p} :\equiv \frac{3}{4}$ on $A_i$,  $\tilde{p} :\equiv \frac{1}{4}$ on $B_i \cap \bar{L}$ and $\tilde{p} :\equiv \frac{1}{2}$ on $B_i \backslash \bar{L}$. Clearly, both $\bar{p}$ and $\tilde{p}$ are feasible. We claim that a suitable combination of these two yields the desired upper bound (proof omitted) yielding Theorem 2.

Lemma 2

For $p:=\frac{3}{7}\bar{p}+\frac{4}{7}\tilde{p}$ we get $\alpha = \max _L ~p(L) \le \frac{2}{7}n$.

Theorem 2

For every simple game (N, v), $\alpha (N,v)\le \frac{2}{7}n$.

4 Complete Simple Games

Intuitively, the class of complete simple games is “closer” to weighted voting games than general simple games. The next result quantifies this expectation.

Theorem 3

A complete simple game (N, v) has $\alpha \le \sqrt{n}\ln n$.

Proof

Let $N=\{1,\dots ,n\}$ be the set of players and assume without loss of generality that $1\succeq 2\succeq \dots \succeq n$. Let $k \in N$ be the largest number such that $\{k, \dots , n\}$ is winning. For $i=1, \dots , k$, let $s_i$ denote the smallest size of a winning coalition in $\{i, \dots , n\}$. Define $p_i:= 1/s_i$ for $i=1, \dots , k$ and $p_i:=p_k$ for $i=k+1,\dots ,n$. Thus, obviously, $p_1 \ge \dots \ge p_k = \dots = p_n$.

Consider a winning coalition $W\subseteq N$ and let i be the first player in W (with respect to $\succeq$). If $|W| \le \sqrt{n}$, then $s_i \le |W| \le \sqrt{n}$ and hence $p(W) \ge p_i = \frac{1}{s_i} \ge \frac{1}{\sqrt{n}}$. On the other hand, if $|W| > \sqrt{n}$, then $p(W) > \sqrt{n}p_k \ge \sqrt{n}\frac{1}{n} =\frac{1}{\sqrt{n}}$.

For a losing coalition $L \subseteq N$, we conclude that $|L \cap \{1, \dots , i\}| \le s_i-1$ (otherwise L would dominate the winning coalition of size $s_i$ in $\{i, \dots ,n\}$). So p(L) is bounded by $\max \sum _{i=1}^{k} x_i\frac{1}{s_i} ~~\text {subject to}~~ \sum _{j=1}^{i}x_j \le s_i-1,~ i=1, \dots , k$. The optimal solution of this maximization problem is $x_1=s_1-1, x_i=s_i-s_{i-1} ~\text {for}~ 2 \le i \le k$. Hence $p(L) \le (s_1-1)\frac{1}{s_1} + (s_2-s_1)\frac{1}{s_2} + \dots + (s_k-s_{k-1})\frac{1}{s_k} \le \frac{1}{2} + \dots + \frac{1}{s_k} \le \ln n$. Summarizing, we obtain $p(L)/p(W) \le \sqrt{n} \ln n$.    $\square$

In [12] it is conjectured that $\alpha = O(\sqrt{n})$ holds for complete simple games. In the same paper a lower bound of order $\sqrt{n}$ is given, as well as specific subclasses of complete simple games for which $\alpha =O(\sqrt{n})$ can be proven.

5 Algorithmic Aspects

A fundamental question concerns the complexity of our original problem (1). For general simple games this depends on how the game in question is given, and we refer to Sect. 1 for a discussion. Here we concentrate on the graphic” case.

Proposition 3

Computing $\alpha _G$ for bipartite graphs G can be done in polynomial time.

Proof

Let $P \subseteq {\mathbb R}^n$ Be the set of feasible payoffs (satisfying $p \ge 0$ and $p_i+p_j \ge 1$ for $ij \in E$). For $\alpha \in {\mathbb R}$, let $P_\alpha := \{p\in P ~|~ p(L) \le \alpha ~\text {for all independent}~ L \subseteq N\}$. Thus $\alpha _G = \min \{\alpha ~|~P_\alpha \ne \emptyset \}$. The separation problem for $P_\alpha$ (for any given $\alpha$) is efficiently solvable. Given $p\in {\mathbb R}^n$, we can check feasibility and whether $\max \{p(L) ~| ~L \subseteq N \text {~independent} \} \le \alpha$ by solving a corresponding maximum weight independent set problem in the bipartite graph G. Thus we can, for any given $\alpha \in {\mathbb R}$, apply the ellipsoid method to either compute some $p \in P_\alpha$ or conclude that $P_\alpha =\emptyset$. Binary search then exhibits the minimum value for which $P_\alpha$ is non-empty; binary search works indeed in polynomial time as the optimal $\alpha$ has size polynomially bounded in n, which follows from observing that

$$\begin{aligned} \alpha = \min \{a ~|~ p_i+p_j \ge 1~ ~\forall ij \in E,~ p(L)-a \le 0 ~ ~\forall L \subseteq N \text {~independent}, p \ge 0\} \end{aligned}$$

(3)

can be computed by solving a linear system of n constraints defining an optimal basic solution of the above linear program.    $\square$

The proof of Proposition 3 also applies to other classes of graphs, such as claw-free graphs (see [6]) in which finding a weighted maximum independent set is polynomial-time solvable. In general, the problem is NP-hard.

Proposition 4

Computing $\alpha _G$ for arbitrary graphs G is NP-hard.

Proof

Let $G'=(N',E')$ and $G''=(N'',E'')$ be two disjoint copies of a graph $G=(N,E)$ with independence number k. For each $i'\in N'$ and $j''\in N''$ add an edge $i'j''$ if and only if $i=j$ or $ij \in E$ and call the resulting graph $G^*= (N^*, E^*)$. We claim that $\alpha _{G^*} = k/2$ (thus computing $\alpha _{G^*}$ is as difficult as computing k).

First note that the independent sets in $G^*$ are exactly the sets $L^* \subseteq N^*$ that arise from an independent set $L \subseteq N$ in G by splitting L into two complementary sets $L_1$ and $L_2$ and defining $L^*:= L_1'\cup L_2''$. Hence, $p\equiv \frac{1}{2}$ on $N^*$ yields $\max p(L^*) = k/2$ where the maximum is taken over all independent sets $L^* \subseteq N^*$ in $G^*$. This shows that $\alpha _{G^*} \le k/2$.

Conversely, let $p^*$ be any feasible payoff in $G^*$, that is, $p^* \ge 0$ and $p^*_i+p^*_j \ge 1$ for all $ij \in E^*$. Let $L \subseteq N$ be a maximum independent set of size k in G and construct $L^*$ by including for each $i \in L$ either $i'$ or $i''$ in $L^*$, whichever has p-value at least $\frac{1}{2}$. Then, by construction, $L^*$ is an independent set in $G^*$ with $p^*(L^*) \ge k/2$, showing that $\alpha _{G^*} \ge k/2$.    $\square$

Summarizing, for graphic simple games, computing $\alpha _G$ is as least as hard as computing the size of a maximum independent in G. For our last result we assume that a is a fixed integer, that is, a is not part of the input.

Proposition 5

For every fixed $a > 0$, it is possible to decide if $\alpha _G \le a$ in polynomial time for an arbitrary graph $G=(N,E)$.

Proof

Let $k= 2\lceil a+\epsilon \rceil$ for some $\epsilon >0$. By brute-force, we can check in $O(n^{2k})$ time if N contains 2k vertices $\{u_1,\ldots ,u_k\}\cup \{v_1,\ldots ,v_k\}$ that induce k disjoint copies of $P_2$, that is, paths $P_i=u_iv_i$ of length 2 for $i=1,\ldots ,k$ with no edges joining any two of these paths. If so, then the condition $p(u_i)+p(v_i)\ge 1$ implies that one of $u_i,v_i$, say $u_i$, must receive a payoff $p(u_i)\ge \frac{1}{2}$, and hence $U=\{u_1,\ldots ,u_k\}$ has $p(U)\ge k/2 > a$. As U is an independent set, $\alpha (G)>a$.

Now assume that G does not contain k disjoint copies of $P_2$ as an induced subgraph, that is, G is $kP_2$-free. For every $s\ge 1$, the number of maximal independent sets in a $sP_2$-free graphs is $n^{O(s)}$ due to a result of Balas and Yu [2]. Tsukiyama, Ide, Ariyoshi, and Shirakawa [30] show how to enumerate all maximal independent sets of a graph G on n vertices and m edges using time O(nm) per independent set. Hence we can find all maximal independent sets of G and thus solve, in polynomial time, the linear program (3). Then it remains to check if the solution found satisfies $\alpha \le a$.    $\square$

6 Conclusions

After our paper appeared, Kanstantsin Pashkovich [1] found a proof of Conjecture 1. Hence it remains to tighten the upper bound for complete simple games to $O(\sqrt{n})$. In order to classify simple games, many more subclasses of simple games have been identified in the literature. Besides the two open problems, no optimal bounds for $\alpha$ are known for other subclasses of simple games, such as strong, proper, or constant-sum games, that is, where $v(S)+v(N\backslash S)\ge 1$, $v(S)+v(N\backslash S)\le 1$, or $v(S)+v(N\backslash S)= 1$ for all $S\subseteq N$, respectively.