A new binary relation to compare viability of winning coalitions and its interrelationships to desirability relation and blockability relation

This paper aims to propose a new type of binary relations, called the viability relation, defined on the set of all coalitions in a simple game for a comparison of coalition influence, and to investigate its properties, especially its interrelationships to the desirability relation and the blockability relation. The viability relation is defined to compare coalitions based on their robustness over deviation of their members for complementing the inability of the desirability relation and the blockability relation to make a distinguishable comparison among winning coalitions. It is verified in this paper that the viability relation on a simple game is always transitive and is complete if and only if the simple game is S-unanimous for a coalition S. Examples show that there are no general inclusion relations among the desirability relation, the blockability relation and the viability relation. It is also verified that the viability relation and the blockability relation are complementary to each other. Specifically, the blockability relation between two coalitions is equivalent to the inversed viability relation between the complements of the two coalitions.     

Characterization of coalitionally ordered games

Summary In the sequel we will derive sufficient and necessary conditions for the existence of certain numeric representations of simple games. In § 2 the above mentioned representation is given by a so called, coalitionally ordered function, i.e. a numeric function representing the desirability of each coalition in the class of all coalitions. Simple games which possess a c.o.f are called coalitionally ordered games. Sufficient and necessary criteria are given for a simple game to be a c.o.g. Analogously weighted majority games are characterized in § 3. The criteria to be presented are linked by properties of the desirability relation of a simple game. The concept of a desirability relation was introduced by Peleg 1978.

---

Zusammenfassung Im folgenden werden wir hinreichende und notwendige Bedingungen zur Existenz von gewissen numerischen Darstellungen einfacher Spiele (simple games) herleiten. Diese oben genannte Darstellung wird in § 2 durch eine sogenannte coalitionally ordered function, gegeben, wobei wir darunter eine numerische Funktion verstehen, die die Desirability, jeder Koalition innerhalb der Klasse aller Koalitionen beschreibt. Einfache Spiele, die eine c.o.f besitzen, werden coalitionally ordered games genannt. Es werden hinreichende und notwendige Bedingungen dafür genannt, daß ein einfaches Spiel ein c.o.g ist. Analog werden gewichtete Abstimmungsspiele (weighted majority games) in § 3 charakterisiert. Die angegebenen Kriterien werden mit Eigenschaften der sogenannten desirability relation eines einfachen Spieles in Verbindung gebracht. Das Konzept einer desirability relation wurde von Peleg 1978 verwendet.

     

A relation-algebraic approach to simple games

Simple games are a powerful tool to analyze decision-making and coalition formation in social and political life. In this paper, we present relation-algebraic models of simple games and develop relational specifications for solving some basic problems of them. In particular, we test certain fundamental properties of simple games and compute specific players and coalitions. We also apply relation algebra to determine power indices. This leads to relation-algebraic specifications, which can be evaluated with the help of the BDD-based tool Rel View after a simple translation into the tool’s programming language. In order to demonstrate the visualization facilities of Rel View we consider an example of the Catalonian Parliament after the 2003 election.     

Fundamentals of simple games from a viewpoint of blockability relations

This paper shows some elementary facts on simple games with respect to blockability relations. It is verified in this paper that fundamental concepts on simple games as null players, dictators, veto players, and so on can be expressed in terms of blockability relations. More, some new concepts as “conflict-free” and so on, are introduced from the viewpoint of blockability relations into the framework of simple games.     

The Shapley–Shubik index for simple games with multiple alternatives

When analyzing mathematically decision mechanisms ruled by voting it is sometimes convenient to include abstention as a possible alternative for the voters. In classical simple games, abstention, if considered, is formally equivalent to voting against the proposal. Simple games with alternatives are useful to study voting systems where abstention does not favour any of the options. In this work, we axiomatically characterize the Shapley–Shubik index for simple games with alternatives and apply it to an example taken from real life. This work has been partially supported by Grant MTM 2006–06064 of the Education and Science Spanish Ministry and the European Regional Development Fund, and Grant SGR 2005–00651 of the Catalonia Government.     

On the use of binary decision diagrams for solving problems on simple games

Simple games are yes/no cooperative games which arise in many practical applications. Recently, we have used reduced ordered binary decision diagrams and quasi-reduced ordered binary decision diagrams (abbreviated as Robdds and Qobdds, respectively) for the representation of simple games and for the computation of some power indices. In the present paper, we continue this work. We show how further important computational problems on simple games can be solved using Qobdds, viz. the identification of some key players, the computation of the desirability relation on individuals, the test whether a simple game is proper and strong, respectively, and the computation of Qobdd-representations for the sets of all minimal winning coalitions, all shift-minimal winning coalitions and all blocking coalitions, respectively. Applications of these solutions include the computation of recent power indices based on shift-minimal winning coalitions and the test for linear separability of a directed simple 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.     

Dimension of complete simple games with minimum

Weighted majority games have the property that players are totally ordered by the desirability relation (introduced by Isbell in [J.R. Isbell, A class of majority games, Quarterly Journal of Mathematics, 7 (1956) 183–187]) because weights induce it. Games for which this relation is total are called complete simple games. Taylor and Zwicker proved in [A.D. Taylor, W.S. Zwicker, Weighted voting, multicameral representation, and power, Games and Economic Behavior 5 (1993) 170–181] that every simple game (or monotonic finite hypergraph) can be represented by an intersection of weighted majority games and consider the dimension of a game as the needed minimum number of them to get it. They provide the existence of non-complete simple games of every dimension and left open the problem for complete simple games.     

Fuzzy matrix games via a fuzzy relation approach

A generalized model for a two person zero sum matrix game with fuzzy goals and fuzzy payoffs via fuzzy relation approach is introduced, and it is shown to be equivalent to two semi-infinite optimization problems. Further, in certain special cases, it is observed that the two semi-infinite optimization problems reduce to (finite) linear programming problems which are dual to each other either in the fuzzy sense or in the crisp sense.     

Bilinear spaces over a fixed field are simple unstable

We study the model theory of vector spaces with a bilinear form over a fixed field. For finite fields this can be, and has been, done in the classical framework of full first-order logic. For infinite fields we need different logical frameworks. First we take a category-theoretic approach, which requires very little set-up. We show that linear independence forms a simple unstable independence relation. With some more work we then show that we can also work in the framework of positive logic, which is much more powerful than the category-theoretic approach and much closer to the classical framework of full first-order logic. We fully characterise the existentially closed models of the arising positive theory. Using the independence relation from before we conclude that the theory is simple unstable, in the sense that dividing has local character but there are many distinct types. We also provide positive version of what is commonly known as the Ryll-Nardzewski theorem for ω-categorical theories in full first-order logic, from which we conclude that bilinear spaces over a countable field are ω-categorical.     

Optimization of generalized desirability functions under model uncertainty

Desirability functions are increasingly used in multi-criteria decision-making which we support by modern optimization. It is necessary to formulate desirability functions to obtain a generalized version with a piecewise max type-structure for optimizing them in different areas of mathematics, operational research, management science and engineering by nonsmooth optimization approaches. This optimization problem needs to be robustified as regression models employed by the desirability functions are typically built under lack of knowledge about the underlying model. In this paper, we contribute to the theory of desirability functions by our robustification approach. We present how generalized semi-infinite programming and disjunctive optimization can be used for this purpose. We show our findings on a numerical example. The robustification of the optimization problem eventually aims at variance reduction in the optimal solutions.     

Closedness under reduced games

We will introduce the notation of the generalized reduced game to unify the representations for maximal subclasses of the classes of essential games (superadditive games and convex games) that are closed under reduction in the sense of Sobolev (1975), Hart and Mas-Colell (1989), and Moulin (1985), respectively.     

The Shapley value for bicooperative games

The aim of the present paper is to study a one-point solution concept for bicooperative games. For these games introduced by Bilbao (Cooperative Games on Combinatorial Structures, 2000) , we define a one-point solution called the Shapley value, since this value can be interpreted in a similar way to the classical Shapley value for cooperative games. The main result of the paper is an axiomatic characterization of this value.     

Various characterizations of convex fuzzy games

This note enlarges the literature on convex fuzzy games with new characterizing properties of such games besides the increasing average marginal return property, namely: the monotonicity of the first partial derivatives, the directional convexity and forC ²-functions the non-negativity of the second order partial derivatives.     

The nucleon of cooperative games and an algorithm for matching games

Thenucleon is introduced as a new allocation concept for non-negative cooperativen-person transferable utility games. The nucleon may be viewed as the multiplicative analogue of Schmeidler’s nucleolus. It is shown that the nucleon of (not necessarily bipartite) matching games can be computed in polynomial time.     

On computational complexity of membership test in flow games and linear production games

Let Γ≡(N,v) be a cooperative game with the player set N and characteristic function v: 2^N→R. An imputation of the game is in the core if no subset of players could gain advantage by splitting from the grand coalition of all players. It is well known that, for the flow game (and equivalently, for the linear production game), the core is always non-empty and a solution in the core can be found in polynomial time. In this paper, we show that, given an imputation x, it is NP-complete to decide x is not a member of the core, for the flow game. And because of the specific reduction we constructed, the result also holds for the linear production game. Received: October 2000/Final version: March 2002     

The Myerson value for directed graph games

A directed graph game consists of a cooperative game with transferable utility and a digraph which describes limited cooperation and the dominance relation among the players. Under the assumption that only coalitions of strongly connected players are able to fully cooperate, we introduce the digraph-restricted game in which a non-strongly connected coalition can only realize the sum of the worths of its strong components. The Myerson value for directed graph games is defined as the Shapley value of the digraph-restricted game. We establish axiomatic characterizations of the Myerson value for directed graph games by strong component efficiency and either fairness or bi-fairness.     

The simple geometry of perfect information games

Perfect information games have a particularly simple structure of equilibria in the associated normal form. For generic such games each of the finitely many connected components of Nash equilibria is contractible. For every perfect information game there is a unique connected and contractible component of subgame perfect equilibria. Finally, the graph of the subgame perfect equilibrium correspondence, after a very mild deformation, looks like the space of perfect information extensive form games.