Binary games in constitutional form and collective choice

In this paper, we define the notion of binary game in constitutional form. For this game, we define a core and give a necessary and sufficient condition for a game to be stable.We define a representation of a collective choice rule by a binary game in constitutional form and characterize those collective choice rules which are representable.We finally introduce the notion of c-social decision function and characterize, as an application of our theorem on stability of binary constitutional games, the collective choice rules which are c-social decision functions.Our representation of a collective choice rule by a binary game in constitutional form is an obvious improvement of the classical representation by a simple game.     

A minimum dimensional class of simple games

This paper provides several extensions of the notion of dimension of a simple game and proves the existence of a minimum subclass of weighted games with the property that every simple game can be expressed as their intersection. Some further generalizations lead to the new concept of codimension which is obtained by considering the union instead of the intersection as the basic operation.     

On the vertices of the -additive core

The core of a game v on N, which is the set of additive games φ dominating v such that φ(N)=v(N), is a central notion in cooperative game theory, decision making and in combinatorics, where it is related to submodular functions, matroids and the greedy algorithm. In many cases however, the core is empty, and alternative solutions have to be found. We define the k-additive core by replacing additive games by k-additive games in the definition of the core, where k-additive games are those games whose Möbius transform vanishes for subsets of more than k elements. For a sufficiently high value of k, the k-additive core is nonempty, and is a convex closed polyhedron. Our aim is to establish results similar to the classical results of Shapley and Ichiishi on the core of convex games (corresponds to Edmonds’ theorem for the greedy algorithm), which characterize the vertices of the core.     

Weighted and roughly weighted simple games

In this paper we give necessary and sufficient conditions for a simple game to have rough weights. We define two functions f(n) and g(n) that measure the deviation of a simple game from a weighted majority game and roughly weighted majority game, respectively. We formulate known results in terms of lower and upper bounds for these functions and improve those bounds. We also investigate rough weightedness of simple games with a small number of players.     

Representations of simple games by social choice functions

We investigate possible constructions of choice procedures (social choice functions) for committees (simple games). The notion of a capacity of a committee is derived from our construction. We determine the capacity of strong, symmetric and weak simple games. We also provide an upper bound on the capacity of a simple game without veto players.     

Different ways to represent weighted majority games

It is well known that every simple game is the intersection of weighted majority games. the aim of this paper is to gather together various ways of expressing weighted majority games and, for each game of this type, to give the simplest way to define it. Normalized representations, the parameters of a simple game and the characteristic invariants of a complete game merit special attention. Research partially supported by projects PR9509 of the Polytechnic University of Catalonia and PB96-0493 of DGES     

Necessary and sufficient conditions forl-stability of games in constitutional form

This paper is devoted to the notion of game in constitutional form. For this game, we define three notions of cores: theo-core, thei-core and thej-core. For each core, we give a necessary and sufficient condition for a game to be stable. We finally prove that these theorems generalize Nakamura's theorems for stability of a simple game and Keiding's theorems for stability of an effectivity function.     

On the existence of a minimum integer representation for?weighted voting systems

A basic problem in the theory of simple games and other fields is to study whether a simple game (Boolean function) is weighted (linearly separable). A second related problem consists in studying whether a weighted game has a minimum integer realization. In this paper we simultaneously analyze both problems by using linear programming. For less than 9 voters, we find that there are 154 weighted games without minimum integer realization, but all of them have minimum normalized realization. Isbell in 1958 was the first to find a weighted game without a minimum normalized realization, he needed to consider 12 voters to construct a game with such a property. The main result of this work proves the existence of weighted games with this property with less than 12 voters. This research was partially supported by Grant MTM 2006-06064 of “Ministerio de Ciencia y Tecnología y el Fondo Europeo de Desarrollo Regional” and SGRC 2005-00651 of “Generalitat de Catalunya”, and by the Spanish “Ministerio de Ciencia y Tecnología” programmes ALINEX (TIN2005-05446 and TIN2006-11345).     

Simple games and weighted games: A theoretical and computational viewpoint

It is a well-known result in the theory of simple games that a game is weighted if and only if it is trade robust. In this paper we propose a variant of trade robustness, that we call invariant-trade robustness, which is enough to determine whether a simple game is weighted. To test whether a simple game is invariant-trade robust we do not need to consider all winning coalitions; a reduced subset of minimal winning coalitions is enough.We make a comparison between the two methods (trade robustness and invariant-trade robustness) to check whether a simple game is weighted. We also provide by means of algorithms a full classification using both methods, for simple games with less than 8 voters according to the maximum level of (invariant-)trade robustness they achieve.     

Banzhaf Measures for Games with Several Levels of Approval in the Input and Output

An axiomatic characterization of ‘a Banzhaf score’ notion is provided for a class of games called (j,k) simple games with a numeric measure associated to the output set, i.e., games with n players, j ordered qualitative alternatives in the input level and k possible ordered quantitative alternatives in the output. Three Banzhaf measures are also introduced which can be used to determine a player's ‘a priori’ value in such a game. We illustrate by means of several real world examples how to compute these measures. Research partially supported by Grant BFM 2003-01314 of the Science and Technology Spanish Ministry and the European Regional Development Fund.     

The desirability relation of simple games

We prove some properties of simple games with a complete desirability relation, and investigate the relationships between the desirability of a simple game G and that of some simple games that are derived from G. We also provide an example of a proper simple game that has a complete and acyclic desirability relation but is not a weighted majority game.     

Heights of simple games

We consider simple games which are constructed as iterated weighted majority games. It turns out that every proper simple game can be obtained in this way. The minimal number of iterations necessary to obtain a given game is called the height of this game. We investigate the behaviour ofh (n), the maximal height of a simple game withn players.     

Nonsymmetric values under Hart-Mass-Colell consistency

Let f be a single valued solution for cooperative TU games that satisfies inessential game property, efficiency, Hart Mas-Colell consistency and for two person games is strictly monotonic and individually unbounded. Then there exists a family of strictly increasing functions associated with players that completely determines f. For two person games, both players have equal differences between their functions at the solution point and at the values of characteristic function of their singletons. This solution for two person games is uniquely extended to n person games due to consistency and efficiency. The extension uses the potential with respect to the family of functions and generalizes potentials introduced by Hart and Mas Colell [6]. The weighted Shapley values, the proportional value described by Ortmann [11], and new values generated by power functions are among these solutions. The author is grateful to anonymous referee and Associate Editor for their comments and suggestions.     

Minimal and locally minimal games and game forms

By Shapley’s (1964) theorem, a matrix game has a saddle point whenever each of its 2×2 subgames has one. In other words, all minimal saddle point free (SP-free) matrices are of size 2×2. We strengthen this result and show that all locally minimal SP-free matrices also are of size 2×2. In other words, if A is a SP-free matrix in which a saddle point appears after deleting an arbitrary row or column then A is of size 2×2. Furthermore, we generalize this result and characterize the locally minimal Nash equilibrium free (NE-free) bimatrix games.Let us recall that a two-person game form is Nash-solvable if and only if it is tight [V. Gurvich, Solution of positional games in pure strategies, USSR Comput. Math. and Math. Phys. 15 (2) (1975) 74-87]. We show that all (locally) minimal non-tight game forms are of size 2×2. In contrast, it seems difficult to characterize the locally minimal tight game forms (while all minimal ones are just trivial); we only obtain some necessary and some sufficient conditions. We also recall an example from cooperative game theory: a maximal stable effectivity function that is not self-dual and not convex.     

Nash and strongly consistent two-player game forms

A two-player game form is Nash-consistent if and only if it is tight (Gurvich). Therefore Nash-consistency of two-player game forms depends only on the effectivity structure. This fact is no longer true for strong consistency. In this paper we introduce a new object called the joint effectivity structure and define the exact joint effectivity set. These notions are similar though more sophisticated than the usual effectivity functions. We prove that a two-player game form is strongly consistent if and only if it is tight and jointly exact. Joint exactness is a property of the exact joint effectivity set which basically requires that the joint exact effectivity set coincides with the classical effectivity function. As a corollary we have a characterization of two-player strongly implementable social choice correspondences.     

Atomic weights and the combinatorial game of bipass

We define an all-small ruleset, bipass, within the framework of normal play combinatorial games. A game is played on finite strips of black and white stones. Stones of different colors are swapped provided they do not bypass one of their own kind. We find a simple surjective function from the strips to integer atomic weights (Berlekamp, Conway and Guy 1982) that measures the number of units in all-small games. This result provides explicit winning strategies for many games, and in cases where it does not, it gives narrow bounds for the canonical form game values. We find game values for some parametrized families of games, including an infinite number of strips of value ?, and we prove that the game value ?2 does not appear as a disjunctive sum of bipass. Lastly, we define the notion of atomic weight tameness, and prove that optimal misére play bipass resembles optimal normal play.     

A convex representation of totally balanced games

We analyze the least increment function, a convex function of n variables associated to an n-person cooperative game. Another convex representation of cooperative games, the indirect function, has previously been studied. At every point the least increment function is greater than or equal to the indirect function, and both functions coincide in the case of convex games, but an example shows that they do not necessarily coincide if the game is totally balanced but not convex. We prove that the least increment function of a game contains all the information of the game if and only if the game is totally balanced. We also give necessary and sufficient conditions for a function to be the least increment function of a game as well as an expression for the core of a game in terms of its least increment function.     

Representation of finite games as network congestion games

Weighted network congestion games are a natural model for interactions involving finitely many non-identical users of network resources, such as road segments or communication links. However, in spite of their special form, these games are not fundamentally special: every finite game can be represented as a weighted network congestion game. The same is true for the class of (unweighted) network congestion games with player-specific costs, in which the players differ in their cost functions rather than their weights. The intersection of the two classes consists of the unweighted network congestion games. These games are special: a finite game can be represented in this form if and only if it is an exact potential game.     

On the design of voting games

By focusing on the protectionist tendency found in the design of voting games, a thorough analysis is provided for the role of blocking coalitions in a simple game. We characterize those blocking families that univocally determine the game, and show that otherwise at least three games share a given nonempty blocking family, also giving an upper bound for the number of such games. Some examples illustrate the application of these ideas to political science.     

Semivalues as power indices

A restricted notion of semivalue as a power index, i.e. as a value on the lattice of simple games, is axiomatically introduced by using the symmetry, positivity and dummy player standard properties together with the transfer property. The main theorem, that parallels the existing statement for semivalues on general cooperative games, provides a combinatorial definition of each semivalue on simple games in terms of weighting coefficients, and shows the crucial role of the transfer property in this class of games. A similar characterization is also given that refers to unanimity coefficients, which describe the action of the semivalue on unanimity games. We then combine the notion of induced semivalue on lower cardinalities with regularity and obtain a series of characteristic properties of regular semivalues on simple games, that concern null and nonnull players, subgames, quotients, and weighted majority games.