s2fieldsofstudy: Economics Mathematics

text:
On the Complexity of the Decisive Problem in Simple, Regular and Weighted Games

We study the computational complexity of an important property of simple, regular and weighted games, which is decisiveness. We show that this concept can naturally be represented in the context of hypergraph theory, and that decisiveness can be decided for simple games in quasi-polynomial time, and for regular and weighted games in polynomial time. The strongness condition poses the main difficulties, while properness reduces the complexity of the problem, especially if it is amplified by regularity. On the other hand, regularity also allows to specify the problem instances much more economically, implying a reconsideration of the corresponding complexity measure that, as we prove, has important structural as well as algorithmic consequences.

Introduction
Cooperative game theory is a branch of game theory where a subset X of players of an entirety A, forming a coalition, can achieve a common benefit. Unlike non-cooperative games, where each player is competing individually against the others, here the focus is cooperation. We shall concentrate on simple games that specify which subsets X of the collective A are winning coalitions; i.e. can impose their common will, if they have one. We will examine important properties that some simple games may have. Given all its minimal winning coalitions, we will ask if the given game is proper, strong, decisive, regular, linear, weighted, homogeneous or majority. So we will pose decision problems concerning simple games, and we will try to characterize the computational complexity of these decision problems.
In [4] the authors conjectured that given all the minimal winning coalitions of a simple game, the problem of deciding if this game is decisive -or self-dual-is coNP-complete. However, we will show that this decisive problem can be solved in quasi-polynomial time; that is, it can be solved by an algorithm which runs in a time bounded by a sub-exponential function, which is not necessarily polynomial. In [18] the authors proved that verifying that a game is weighted -or threshold [14] or a trade robust game [28]is in P . But in [4] the authors conjectured that deciding if a weighted game is decisive, is coNP-complete. We will prove that this conjecture is most probably wrong too (unless N P = P ), because this problem is also in P . Actually, the decisive problem is polynomial even for linear games [29] -also called complete games [2], ordered games [26], swap-robust games [29] or 2-monotone Boolean functions [30]-which are simple games whose players can be ordered forming a regular game [14] -also known as directed game [11]-; a class that includes weighted games.
Finally -going definitely beyond of what we already have stated in [25]-we shall drop the assumption that the given games are always specified by their minimal winning coalitions; and prove that regular games can be given in a more economic way so that if we now measure the computational time according to this smaller input size, the mentioned algorithm of [18] ceases to be polynomial. The corresponding decisive problem turns out be at least as complex as for simple games.
In the following section, we introduce hypergraphs to review the main basic definitions. In Section 3, we define the decisive problem and show that it is quasi-polynomial, using the well known result of [3]. In Section 4, we define regularity, weightedness and homogeneity, showing that one can recognize any of these properties in polynomial time; and moreover, if one of them holds, also decide decisiveness in time polynomial in the input size. In Section 5, we concentrate on regular games, proving that for such games the minimal winning coalitions yield, in fact, an inflated measure of the input size. In Section 6, we recapitulate considering more than proper games.
2 Hypergraphs and simple games Definition 1. Given a finite ground set A -and its power set P(A)a hypergraph defined over A is a family H ⊆ P(A) of hyperedges X ⊆ A.
We may represent hypergraphs H as incidence matrices, such that their rows represent the incidence vectors x : A → {0, 1} of the hyperedges X ∈ H. So, given a ∈ A, x(a) = 1 iff a ∈ X. The size of H, i.e., the amount of bits needed in order to write down the family of incidence vectors that characterize the hypergraph, is |A| · |H| ∈ N.
Shortly after mathematical hypergraph theory was consolidated [1], it was already used to analyze cooperative games [20], although corresponding complexity considerations are quite new.

Definition 3.
A simple game is a pair Γ := (A, W), where A is a finite set of players and W ⊆ P(A) is a family of winning coalitions, such that for all X ∈ W, X ⊆ Z implies Z ∈ W. So W is a hypergraph over A, with ν(W) = W. In other words, the Boolean function f : P(A) → {0, 1} determined by the hypergraph W -such that W = {X ⊆ A; f (A) = 1}-is monotone. Therefore we also say that simple games are monotone.
Then µ(W), the irredundant kernel of Γ , is the family of minimal winning coalitions; τ (W) is the blocker of W; and L := P(A)\W = {X ⊆ A; f (A) = 0} = ¬(τ (W)) is the set of losing coalitions. We do not demand ∅ ∈ L, so L can be void. The simple game (A, τ (W)) is called the dual game of (A, W). proper, if for all S ⊆ A, S ∈ W ⇒ A\S / ∈ W, i.e. W ⊆ τ (W), -strong, if for all S ⊆ A, S / ∈ W ⇒ A\S ∈ W, i.e. W ⊇ τ (W), and decisive, if it is both strong and proper, i.e. W = τ (W).

Decisiveness in simple games
In [29] we read: Properness rules out the possibility of disjoint winning coalitions, while strongness rules out the possibility of two losing coalitions whose union is A . . . Some authors who view simple games as models of voting systems have little interest in simple games that are not proper. Their argument is that disjoint winning coalitions can allow contradictory decisions to be made by the voting body. . . . A less vigorous argument is sometimes raised against games that are not strong, and thus, the argument goes, leave some issues unresolved. Ramamurthy (1990) refers to "the paralysis that may result from allowing a losing coalition to obstruct a decision." So, ideally, games should be decisive; and this is why this property interests us so much.
Proof. Just note that: Note that for any hypergraph H, ν(µ(H)) = ν(H) and τ (µ(H)) = τ (H). So let (H, K) be a pair of hypergraphs and Γ := (A, W) a simple game, then: In projective geometry, the Fano Plane is the smallest projective plane. It was introduced in simple game theory by [24] to define a subclass of simple games called finite projective games. Since then, it has been very much studied, due to it has special properties that make it a likely counterexample for different results -for instance, without going into details, it is the only non-partition game with the same number of minimal winning coalitions and players [26]-as well as a case in which some properties turn out to be the same -for instance, its reactive bargaining set coincides with its kernel [6].
It can be represented by a hypergraph H over A := {7, . . . , 1}, with seven evenly distributed hyperedges represented by the following incidence matrix. It is easy to check that µ(H) = H and prove that (H, H) is coherent. It is more difficult to prove the completeness of this pair -see the next Corollary 1-but in fact it is dual. So the game Γ := (A, ν(H)) is proper and strong; i.e. decisive. Given a simple game Γ := (A, W), since for any hypergraph H we have µ(ν(H)) = µ(H), we may assume that only µ(W) is extensively specified; that the rest of W is only implicitly defined by µ(W). Because given any Z ⊆ A, deciding if Z ∈ W can be done efficiently: Simply visit all X ∈ H, every time deciding X ⊆ Z; something that can be done in at most |A| units of computation time. So the amount of information needed to specify Γ is given by the size |A| · |µ(W)| of µ(W). This explains the following easy but important result: 3. decide decisiveness is quasi-polynomial; i.e. there exists a decision algorithm whose logarithm of the running time is polynomial in the logarithm of the input size.
Proof. The three statements rely on Lemma 2. Statement (1) follows because, as ν is a monotone operator, (H, H) is coherent iff ∀X, Z ∈ H, X ∩ Z = ∅, a condition that can be verified in polynomial time. Statement (2) follows because it has been proven many times [22] that the completeness of a pair of hypergraphs (H, K), poses a decision problem that is coNP-complete. Moreover, this not necessarily symmetric problem can polynomially be reduced to the symmetric one [3]. Statement (3) follows from a deep result, proving that duality of a pair of hypergraphs (H, K) can be decided in quasi-polynomial time, since there is a sub-exponential algorithm [3] whose logarithms of the running times can be bounded by a polynom of the logarithms of the sizes of the pairs.
Note that therefore the decisive problem is most probably not NP-hard, unless any NP-complete problem can be solved in quasi-polynomial time. But note also that the mentioned quasi-polynomial algorithm does not allow us to generate λ(H) := µ(τ (H)) in sub-exponential time, since |λ(H)| can not be quasi-polynomially bounded by |µ(H)|. To prove this statement, consider the following example: 4 Regular and weighted games Definition 6. Let ≤ denote a linear order on A which orders the players by increasing power. Given X ⊆ A, an increasing-shift on X, specified by a pair (a, b) ∈ A\X × X such that a > b, is an operation which returns Z := X\{b} ∪ {a}.
A simple game (A, W) is regular with respect to the given linear order [18,12] if for all X ∈ W, every increasing-shift returns an element of W; i.e. if replacing a member of a winning coalition X ∈ W by a more powerful one, always yields a winning coalition.
It is clear that a simple game (A, W) is regular iff ∀X ∈ µ(W) every increasing-shift returns an element of W. So, to decide the regularity of W, one can restrict the attention to H := µ(W), resulting that regularity can be decided in time polynomial in |H|. In fact, this recognition problem can be solved in linear time [12].
Regular games are -in a sense that we shall reconsider in Section 5-very tractable; i.e. there exist algorithms [19] that given H := |µ(W)|, generate λ(H) in linear time; and at the same time prove that |λ(H)| ≤ |A| · |H| + 1.
-if there exists a linear re-ordering of A, for which W becomes regular.
The linearity of W can also be decided in time polynomial in |µ(W)|; since if one identifies X ∈ µ(W), a ∈ A\X and b ∈ X with a > b and {a} ∪ X\{b} ∈ ν(H), then, to have a chance to obtain a regular re-ordering, the order a > b has to be reversed; definitively. And such definitive re-ordering can be executed at most n · (n − 1)/2 times, where n := |A| [12].
The Fano plane of Example 2 is clearly not regular, and by its symmetry, not linear.

Definition 8.
A weighted game is a simple game Γ := (A, W) that can be specified by a threshold criterion (q, p) -also known as weighted representation-where p : A → R + is a weight function and q ∈ R + a quota such that for all Z ⊆ A, Z ∈ W iff p(Z) ≥ q; where p(Z) := Σ{p(a); a ∈ Z}. Γ is homogeneous if it has a threshold criterion such that ∀X ∈ µ(W), p(X) = q.
It is well known that each weighted game has a canonical weighted representation. Weighted games were defined in 1944 by [16] and deeply studied in 1956 by [8], in the context of simple game theory. Since then they have been studied in many different contexts and under different names, like linearly separated truth function [13] -to contact and to rectify nets-, linearly separable switching function or threshold Boolean functions [7] -to separate circuits in switching circuit theory and analyse the threshold synthesis problem-, trade robustness [28] -for voting theory and trade exchangesor threshold hypergraphs [5,23] -to synchronize parallel processes. Homogeneous games were also first defined in [16], and they are one of the most studied subclasses of weighted games [26].
Weighted games clearly are simple (monotone) games, and one can always linearly re-order the elements of A such that p : A → R becomes monotone; i.e. for all a, b ∈ A with a < b, p(a) ≤ p(b). And then clearly the game W becomes regular. So all weighted games are linear. The converse, however, does not necessarily hold [29,14].
According to the well known duality of linear inequality systems: where 1 is the H-vector with all entries equal to 1, and H, H ′ are the H × A-incidence-matrices that represent H and ¬(H) respectively. In the next Section we will also prove that this game is decisive. The next result was proven in [18], but not for homogeneous games. Proof. The following procedure is efficient for both kind of games, since each Step can be accomplished in polynomial time: The first four were already commented above, and Steps 5 to 8 only demand the solution of a system of linear equalities and inequalities, which can also be found in polynomial time [10]. Note that in Step 8 the original restriction demands that for each loser Y ∈ J , p(Y ) < q; but this can equivalently be replaced by ∀Y ∈ J , p(Y ) ≤ q − 1, because multiplying a threshold criterion by a positive constant, returns a threshold criterion.
Next we will prove a similar result, but now regarding decisive games: Definition 9. A weighted game Γ := (A, W) is a sub-majority game, if it is strong; and it is a majority game, if it is decisive.
In [4] the authors conjecture that verifying majority games is coNP-complete. This conjecture is most probably false (unless P =N P ), because: Proof. Analogously to Theorem 1, the following Algorithm 2 is efficient to decide both kind of games. First note that by Definition 4, Γ is decisive iff τ (W) = W, so applying the operator µ on the expression we obtain λ(W) = µ(W), by Definition 2. In the same way, Γ is strong iff τ (W) ⊆ W iff λ(W) ⊆ µ(W). Moreover, it is easy to see that λ(µ(W)) = λ(W). Using these ideas, we test decisiveness or strongness on Steps 4-5, through the following questions: is λ(H) = H? or, respectively, is λ(H) ⊆ ν(H)? which are equivalent to the two conditions given above. Finally, the procedure to decide whether the game is also weighted or homogeneous is the same as the given by Algorithm 1.
It is known that up to eight players, all the simple games which are regular and decisive are also majority. This implies that Step 6 of Algorithm 2 is unnecessary in these cases, because the answer would always be "Yes". However, from nine players onwards, this is not always true. It is known that for |A| = 9 there are 319124 regular and decisive games [11], but only 175428 majority games [15].
As far as we know, explicit examples of regular games which are decisive but not weighted, as our Example 4, have not been indicated until now. However, another regular game that in fact meets these characteristics is given in [27].

Economic specification of regular games
The considerations that in the last section led from simple games to weighted ones, revealed the central importance of regular games. Mainly because to prove Theorem 1 and Theorem 2, we had to rely on the main result of [18], which, given the minimal winning coalitions µ(W) of a regular game Γ := (A, W), allows to generate the family of the irredundant transversal λ(W) in polynomial time, in function of the input size. But there is, as we will see, a much more economic way to determine regular games; one that will demand a reconsideration of the recalled polynomiallity results.
Since in what follows we restrict the attention to regular games, we may assume that A = {n, n − 1, . . . , 1}.
Definition 10. Given X ⊆ A, a left-shift on X is either an increasing-shift -see Definition 6-specified by a pair (a, b) ∈ A\X × X, such that a = b + 1; or, if 1 ∈ A\X, a replacement of X by X ∪ {1}.
Given X, Z ⊆ A we say that Z is a successor of X, if a left-shift performed on X yields Z; i.e. if there exist a ∈ A\X and b ∈ X ∪ {0}, such that a = b + 1 and Z := X\{b} ∪ {a}. So we can conceive a directed successor graph on the set of nodes P(A) such that, given X, Z ⊆ A, (X, Z) is an arrow of the graph, if Z is a successor of X.
We write X ⊆ ′ Z if, starting with X, there exists a sequence of left-shifts that produces Z. It is quite clear that a sequence of left-shifts starting with X can not re-produce X -unless the sequence is emptyso the successor graph is acyclic. The relation ⊆ ′ is the reflexive-and-transitive closure of that successor graph. So it is an order relation, that we shall call shift order.
Given X, Z ⊆ A, X ⊆ ′ Z iff for all a ∈ A, |{b ∈ X; b ≥ a}| ≤ |{b ∈ Z; b ≥ a}|; because if Z is a successor of X, then the stated inequalities evidently hold; and, the other way round, if the inequalities hold, then starting from X, one can always perform a sequence of left-shifts that preserve the inequalities to finally produce Z. So this shift relation can be decided in time polynomial in n. And it is also clear that, if X ⊆ Z, then X ⊆ ′ Z; i.e. that ⊆ ′ is a monotone variation of ⊆. And that for ⊆ ′ -as for ⊆complementation is antitone; i.e. if X ⊆ ′ Z, then A\Z ⊆ ′ A\X.
Note that, given a hypergraph W over A, (A, W) is a regular game iff ν ′ (W) = W. This is so because we always have ν ′ (W) ⊇ ν(W) ⊇ W. So ν ′ (W) = ν(W) = W is equivalent to ν ′ (W) ⊆ W. Hence regular games are ⊆ ′ -monotone games, as simple games are ⊆-monotone games.
Proof. The above mentioned monotone variation, together with the definition of H ′ , imply ν(W) ⊆ ν ′ (W) = ν ′ (H ′ ). So, to prove the first statement, it only remains to point out that regularity of (A, W) is equivalent to ν ′ (W) ⊆ ν(W). The second statement follows from the variation of Lemma 1 that one obtains replacing ⊆ by ⊆ ′ . Note that the given proof of Lemma 1 holds for any order relation on P(A) for which complementation is antitone.
Hence, to implicitly specify a regular game (A, W), it suffices to explicitly specify H ′ := µ ′ (W) ⊆ H := µ(W): Given any Z ⊆ A, one can decide Z ∈ W, simply visiting all X ∈ H ′ , every time deciding X ⊆ ′ Z.
Example 5. Consider the regular game of Example 4, specified over there by a hypergraph H. Its economic specification H ′ is the following; because all other X ∈ H are such that X ∈ ν ′ (H ′ ).
A 987654321 u H ′ 011011011 1 011100100 1 100011100 1 100100011 1 100101000 0 101000000 0 Until now we have assumed that not only simple games Γ := (A, W) but also, in particular, regular games, will be characterized by µ(W); and that therefore the time needed to decide questions concerning simple games, should be measured using the simple-measure κ(Γ ) := |A| · |µ(W)|; the size of µ(W). But if we limit the attention to the universe of regular games Γ := (A, W), since we now know that they can also be characterized by µ ′ (W), then it seems to be reasonable that the deciding times should be measured using the regular-measure κ ′ (Γ ) := |A| · |µ ′ (W)|; the size of µ ′ (W). One reason for this, is that the characterization in question turns out to be efficient, since for all Z ⊆ A, Z ∈ W can be decided in polynomial time in function of κ ′ (Γ ). Another reason is, that for all regular games Γ := (A, W), since But in our opinion this adaptation to the universe of regular games is moreover mandatory, because κ would yield an inflated measure for regular games, compared with κ ′ , since there exist sequences m . This opinion contradicts the one of the authors of [18]. They proved that there exists a polynom p : N → N, such that for all n ∈ N,κ(n)/κ ′ (n) ≤ p(n); whereκ(n) := max{κ((A, W)); |A| = n} and κ ′ (n) := max{κ ′ ((A, W)); |A| = n}. They even proved that the same would still hold, if κ ′ would be replaced by the size of any codification which is able to distinguish different regular games. And based on this result, they conclude that the simple-measure is a not-inflated measure.
This view, however, forces us to "scan" the universe of regular games partitioning it in "slices" with constant |A|. But one could as well "scan" it, partitioning it in "slices" of constant κ ′ (W). Then, redefiningκ,κ ′ accordingly, for any m ∈ N one would haveκ ′ (2m) = 2m. But since the above defined regular game Γ m is in the "slice" 2m,κ(2m) ≥ 2m · 2m m . Soκ(2m)/κ ′ (2m) can not be bounded by a polynom in m.
For all these reasons we adopt the regular-measure κ ′ ; with all its important consequences: Restricting the codomain to T (P(A)), T becomes bijective; i.e. an isomorphism. Proof.
The T -image of P(A) covers (only) the X ′ ∈ P(A ′ ) that for all a ∈ A, either satisfy 2a ∈ X ′ or (exclusive) 2a − 1 ∈ X ′ . So it is closed with respect to complementation. Let us now prove the last statement. We have ). And, given Z ′ ∈ P(A ′ )\T (P(A)), let a ∈ A be maximal such that either Then if the first holds, clearly Z a ⊆ ′ Z ′ ; and if the second one holds, A ′ \Z a ⊆ ′ Z ′ .

Conclusions
As we have seen, strongness poses the main question: Given W ⊆ P(A), is W ∪ ¬(W) = P(A)? If W is given explicitly, then obviously the question can be answered in time, that can polynomially be bounded by the size |A|·|W| of the given W. But if W is monotone, then W can implicitly be given by H := µ(W). So, if we restrict the attention to simple games (A, W), as we did, then the size of the problems instances is |A| · |H|. And evaluating according to that unit of measurement, the strongness problem becomes coNP-complete; unless we restrict the scope even more, to proper games, for which W ⊆ τ (H) holds. Then strongness can be decided in time that can be bounded by a sub-exponential function of the size of H. But the corresponding quasi-polynomial algorithms are definitely super-polynomial. To guaranty polynomiallity, it seems that one has to restrict the universe to instances W that are "morethan-proper". For example, if A = {n, . . . , 1} and for all considered instances ν ′ (H) ⊆ τ ′ (H) holds, then ν(H) ⊆ ν ′ (H) ⊆ τ ′ (H) ⊆ τ (H); so strongness ν(H) ⊇ τ (H) implies regularity. Hence, to decide strongness, one can first examine regularity and, if the answer is positive, decide the strongness of the regular game. All, of course, in time polynomial in |A| · |H|. In Section 4 we derived a similar result for weighted instances; which in fact are dually characterized by the, properness implying, "more than proper" condition of Lemma 3.
However, weighted instances W will often not be given stating explicitly H := µ(W). Usually they will be defined implicitly, explicitly giving only a corresponding threshold criterion (p, q). Then, measuring computational time according to the size of (p, q) -which of course is much smaller than |A| · |H|the strongness problem turns out to be coNP-complete; as is well known [4]. Again we could focus on a sub-universe: Suppose that A can be reordered such that A = {n, . . . , 1} and for all a ∈ A, p(a) = 2 a . Then there exists exactly one X ∈ W, such that p(X) := Σ{p(a); a ∈ A} is minimal. So, to implicitly give W, it suffices to explicitly exhibit this minimal winning coalition X ∈ W. The size of this X is |A|: very small. Nonetheless, strongness can be decided in time polynomial in that small size: Simply determine the maximal loser Y ⊆ A -the unique one, such that p(X) − 1 = p(Y )-and decide if A\Y ∈ W. These considerations show that restricting our strongness problem to "more than proper" sub-universes of simple games, sometimes, but not always, really reduces the problems complexity.
In Section 5 we proved that if instead of considering simple games we restrict the attention to the regular ones, it does not reduce the problems complexity; because regular games can implicitly be specified by codes that are much smaller than the ones needed to specify simple games. This turned out to be the reason why -in Section 5-the strongness decision problem for simple games could be polynomially reduced to its restriction to regular games. And the same holds if from the beginning we restrict the attention to proper games. These results have, as we indicated, algorithmic implications.
Beyond that, they are also of interest for structural game theoretical considerations [20,21]. Because our last Theorem 3 proves that one can extend the monomorphism T defined in Section 5, to define for every simple game Γ := (A, W) a regular game Γ ′ := T (Γ ) := (A ′ , T (W)), such that the amount of information needed to specify T (Γ ) is polynomial in the amount required by Γ . In this sense we may conclude that the class of regular, i.e. ⊆ ′ -monotone games, yields a structure that is at least as eloquent as the class of simple, i.e. ⊆-monotone games; because this classical Boolean structure can economically be interpreted in the here reconsidered regular structure.