Weighted multiple majority games with unions: Generating functions and applications to the European Union

An a priori system of unions or coalition structure is a partition of a finite set of players into disjoint coalitions which have made a prior commitment to cooperate in playing a game. This paper provides “ready-to-apply” procedures based on generating functions that are easily implementable to compute coalitional power indices in weighted multiple majority games. As an application of the proposed procedures, we calculate and compare coalitional power indices under the decision rules prescribed by the Treaty of Nice and the new rules proposed by the Council of the European Union.     

Directed and weighted majority games

In this paper we deal with several classes of simple games; the first class is the one of ordered simple games (i.e. they admit of a complete desirability relation). The second class consists of all zero-sum games in the first one.First of all we introduce a natural partial order on both classes respectively and prove that this order relation admits a rank function. Also the first class turns out to be a rank symmetric lattice. These order relations induce fast algorithms to generate both classes of ordered games.Next we focus on the class of weighted majority games withn persons, which can be mapped onto the class of weighted majority zero-sum games withn+1 persons.To this end, we use in addition methods of linear programming, styling them for the special structure of ordered games. Thus, finally, we obtain algorithms, by combiningLP-methods and the partial order relation structure. These fast algorithms serve to test any ordered game for the weighted majority property. They provide a (frequently minimal) representation in case the answer to the test is affirmative.     

Weighted search games

In this paper we shall deal with search games in which the strategic situation is developed on a lattice. The main characteristic of these games is that the points in each column of the lattice have a specific associated weight which directly affects the payoff function. Thus, the points in different columns represent points of different strategic value. We solve three different types of games. The first involves search, ambush and mixed situations, the second is a search and inspection game and the last is related to the accumulative games.     

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     

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.     

Weighted values and the core in NTU games

Monderer et al. (Int J Game Theory 21(1):27–39, 1992) proved that the core is included in the set of the weighted Shapley values in TU games. The purpose of this paper is to extend this result to NTU games. We first show that the core is included in the closure of the positively weighted egalitarian solutions introduced by Kalai and Samet (Econometrica 53(2):307–327, 1985). Next, we show that the weighted version of the Shapley NTU value by Shapley (La Decision, aggregation et dynamique des ordres de preference, Editions du Centre National de la Recherche Scientifique, Paris, pp 251–263, 1969) does not always include the core. These results indicate that, in view of the relationship to the core, the egalitarian solution is a more desirable extension of the weighted Shapley value to NTU games. As a byproduct of our approach, we also clarify the relationship between the core and marginal contributions in NTU games. We show that, if the attainable payoff for the grand coalition is represented as a closed-half space, then any element of the core is attainable as the expected value of marginal contributions.     

Weak topology and infinite matrix games

This paper approaches infinite matrix games through the weak topology on the players' sets of strategies. A new class of semi-infinite and infinite matrix games is defined, and it is proved that these games always have a value and optimal strategies for each player. Using these games it is proved that some other important classes of infinite matrix game also have values. Received April 1996/Revised version June 1997/Final version September 1997     

Weighted matrix means and symmetrization procedures

Here we prove the convergence of the Ando–Li–Mathias and Bini–Meini–Poloni procedures for matrix means. Actually it is proved here that for a two-variable function which maps pairs of positive definite matrices to a positive definite matrix and is not greater than the square mean of two positive definite matrices, the Ando–Li–Mathias and Bini–Meini–Poloni procedure converges. In order to be able to set up the Bini–Meini–Poloni procedure, a weighted two-variable matrix mean is also needed. Therefore a definition of a two-variable weighted matrix mean corresponding to every symmetric matrix mean is also given. It is also shown here that most of the properties considered by Ando, Li and Mathias for the n-variable geometric mean hold for all of these n-variable maps that we obtain by this two limiting process for all two-variable matrix means. As a consequence it also follows that the Bini–Meini–Poloni procedure converges cubically for every matrix mean.     

Weighted allocation rules for standard fixed tree games

In this paper we consider standard fixed tree games, for which each vertex unequal to the root is inhabited by exactly one player. We present two weighted allocation rules, the weighted down-home allocation and the weighted neighbour-home allocation, both inspired by the painting story in Maschler et al. (1995) . We show, in a constructive way, that the core equals both the set of weighted down-home allocations and the set of weighted neighbour allocations. Since every weighted down-home allocation specifies a weighted Shapley value (Kalai and Samet (1988)) in a natural way, and vice versa, our results provide an alternative proof of the fact that the core of a standard fixed tree game equals the set of weighted Shapley values. The class of weighted neighbour allocations is a generalization of the nucleolus, in the sense that the latter is in this class as the special member where players have all equal weights.     

Numerical solution of special matrix games

A method is proposed for solving large-sized matrix games (zero-sum games) of special form for which there is a fast algorithm of searching for the best pure strategy of a player given any mixed strategy of the opponent. Examples of problems leading to such games are given. The method proposed is numerically compared with the Brown-Robinson iterative method.     

Ellipsoid projection method in matrix games

A problem of calculating a solution of a zero-sum matrix game is considered in the paper The problem of search of a solution is reduced to a constrained convex minimization problem for which an ellipsoid projection algorithm is used. The algorithm generates an ?-optimal solution of the game in a polynomial time     

Weighted Banzhaf power and interaction indexes through weighted approximations of games

The Banzhaf power index was introduced in cooperative game theory to measure the real power of players in a game. The Banzhaf interaction index was then proposed to measure the interaction degree inside coalitions of players. It was shown that the power and interaction indexes can be obtained as solutions of a standard least squares approximation problem for pseudo-Boolean functions. Considering certain weighted versions of this approximation problem, we define a class of weighted interaction indexes that generalize the Banzhaf interaction index. We show that these indexes define a subclass of the family of probabilistic interaction indexes and study their most important properties. Finally, we give an interpretation of the Banzhaf and Shapley interaction indexes as centers of mass of this subclass of interaction indexes.     

二元Boolean矩阵的加权Moore-Penrose逆

主要研究了二元Boolean矩阵A的加权Moore-Penrose逆的存在性问题,给出了二元Boolean矩阵A的加权Moore-Penrose逆存在的一些充分必要条件,并讨论了加权Moore-Penrose逆存在时的若干等价刻画及惟一性问题.     

Analyzing games by Boolean matrix iteration

Finite win-draw-lose games with perfect information are studied, using a Boolean formulation with the intention of computational realization. The interdependence of the sets of winning strategies is expressed by means of Boolean matrix equations. Their solutions which describe the winning positions can be obtained by matrix iteration. In the case of last-player-winning games this method shows the existence of two kernels of a bipartite graph which are distinguished in the sense that they bound all other possible kernels. For some chess endings with three and four men all positions are completely analyzed.     

Weighted values for non-atomic games: an axiomatic approach

Weighted values of non-atomic games were introduced by Hart and Monderer. These values have been studied by using three approaches: the potential, the asymptotic and the random order approach. In this study we analyze the axiomatic approach for one class of weight functions: the set of players is partitioned into a finite number of types, with each type having different weight.