Search

Abstract We introduce collective decision-making models associated with influence spread under the linear threshold model in social networks. We define the oblivious and the non-oblivious influence models. We also introduce the generalized opinion leader–follower model (gOLF) as an extension of the opinion leader–follower model (OLF) proposed by van den Brink et al. (2011). In our model we allow rules for the final decision different from the simple majority used in OLF. We show that gOLF models are non-oblivious influence models on a two-layered bipartite influence digraph. Together with OLF models, the satisfaction and the power measures were introduced and studied. We analyze the computational complexity of those measures for the decision models introduced in the paper. We show that the problem of computing the satisfaction or the power measure is #P-hard in all the introduced models even when the subjacent social network is a bipartite graph. Complementing this result, we provide two subfamilies of decision models in which both measures can be computed in polynomial time. We show that the collective decision functions are monotone and therefore they define an associated simple game. We relate the satisfaction and the power measures with the Rae index and the Banzhaf value of an associated simple game. This will allow the use of known approximation methods for computing the Banzhaf value, or the Rae index to their practical computation. [ABSTRACT FROM AUTHOR]

Simple games are abstract representations of voting systems and other group-decision procedures. A stable set —or von Neumann–Morgenstern solution—of a simple game represents a “standard of behavior” that satisfies certain internal and external stability properties. Compound simple games are built out of component games, which are, in turn, “players” of a quotient game. I describe a method to construct fair —or symmetry-preserving—stable sets of compound simple games from fair stable sets of their quotient and components. This method is closely related to the composition theorem of Shapley (1963c) , and contributes to the answer of a question that he formulated: What is the set G of simple games that admit a fair stable set? In particular, this method shows that the set G includes all simple games whose factors —or quotients in their “unique factorization” of Shapley (1967) —are in G , and suggests a path to characterize G . [ABSTRACT FROM AUTHOR]

We survey the results on representations of committees and constitutions by game forms that possess some kind of equilibrium strategies for each profile of preferences of the players. The survey is restricted to discrete models, that is, we deal with finitely many players and alternatives. No prior knowledge of social choice is assumed: As far as definitions are concerned, the paper is self-contained. Section 2 supplies the necessary general tools for the rest of the paper. Each definition is followed by a simple (but nontrivial) example. In Section 3 we give a complete account of representations of committees (proper and monotonic simple games), by exactly and strongly consistent social choice functions. We start with Peleg's representations of weak games, and then provide a complete and detailed account of Holzman's solution of the representation problem for simple games without veto players. In Section 4 we deal with representations of constitutions by game forms. Following Gärdenfors we model a constitution by a monotonic and superadditive effectivity function. We fully characterize the representations for three kinds of equilibrium: Nash equilibrium; acceptable equilibrium (Pareto optimal Nash equilibrium); and strong Nash equilibrium. We conclude in Section 5 with a report on two recent works on representations of constitutions under incomplete information. [ABSTRACT FROM AUTHOR]

We present an axiomatic characterization of the Owen-Shapley spatial power index for the case where issues are elements of two-dimensional space. This characterization employs a version of the transfer condition, which enables us to unravel a spatial game into spatial games connected to unanimity games. The other axioms include two conditions concerned particularly with the spatial positions of the players, besides spatial versions of anonymity and dummy. The last condition says that dummy players can be left out in a specific way without changing the power of the other players. We show that this condition can be weakened to requiring dummies to have zero power if we add a condition of positional continuity. We also show that the axioms in our characterization(s) are logically independent. [ABSTRACT FROM AUTHOR]

We describe a way of producing an -dimensional manifold starting with an Alexander self-dual simplicial complex on vertices (or, in another terminology, by a simple game with constant sum with players). The construction presents explicitly, by describing its regular cellulation. [ABSTRACT FROM AUTHOR]

This paper considers the computational complexity of the design of voting rules, which is formulated by simple games. We prove that it is an NP -complete problem to decide whether a given simple game is stable, or not. [ABSTRACT FROM AUTHOR]

Beimel, Tassa and Weinreb [SIAM J. Discrete Math. 22 (2008), 360-397] and Farràs and Padró [Lecture Notes in Comput. Sci. 5978, Springer, 2010, 219-236] partially characterised access structures of ideal weighted secret sharing schemes in terms of the operation of composition. They proved that any weighted ideal access structure is a composition of indecomposable ones. Farràs and Padró gave a list of seven classes of access structures - one unipartite, three bipartite and three tripartite - to which all weighted ideal indecomposable access structures may belong. In this paper we determine exactly which access structures from those classes are indecomposable. We also determine which compositions of indecomposable weighted access structures are again weighted and obtain an if-and-only-if characterisation of ideal weighted secret sharing schemes. We use game-theoretic techniques to achieve this. [ABSTRACT FROM AUTHOR]

Hierarchical simple games-both disjunctive and conjunctive-are natural generalizations of $$k$$ -out-of- $$n$$ games. They are ideal in the sense that they allow most efficient and secure secret sharing schemes to be defined on these games as access structures. Another important generalization of $$k$$ -out-of- $$n$$ games with origin in economics and politics are weighted and roughly weighted majority games. Weighted hierarchical games have been classified by Beimel et al. (SIAM J Discret Math 22(1):360-397, ) and Gvozdeva et al. (Math Soc Sci. doi:, ); it appeared that they cannot have more than two nontrivial levels in their hierarchy. In this paper we characterize roughly weighted hierarchical games and show that they cannot have more than three nontrivial levels. This shows that hierarchical games are rather far from weighted and even roughly weighted games, and hence provide an interesting set of examples for the theory of simple games. Our methods are purely game-theoretic. [ABSTRACT FROM AUTHOR]

In this paper, we characterize two power indices introduced in [1] using two different modifications of the monotonicity property first stated by [2]. The sets of properties are easily comparable among them and with previous characterizations of other power indices. [ABSTRACT FROM AUTHOR]

Gvozdeva et al. (Int J Game Theory, doi:, ) have introduced three hierarchies for simple games in order to measure the distance of a given simple game to the class of (roughly) weighted voting games. Their third class $${\mathcal {C}}_\alpha $$ consists of all simple games permitting a weighted representation such that each winning coalition has a weight of at least $$1$$ and each losing coalition a weight of at most $$\alpha $$ . For a given game the minimal possible value of $$\alpha $$ is called its critical threshold value. We continue the work on the critical threshold value, initiated by Gvozdeva et al., and contribute some new results on the possible values for a given number of voters as well as some general bounds for restricted subclasses of games. A strong relation between this concept and the cost of stability, i.e. the minimum amount of external payment to ensure stability in a coalitional game, is uncovered. [ABSTRACT FROM AUTHOR]

Several relationships between simple games and a particular type of solutions for cooperative games are studied in this paper. These solutions belong to the set of semivalues and they are related to a unique parameter that explicitly provides their weighting coefficients. Through the allocations offered by this family of solutions, so-called binomial semivalues, and also from their respective potentials, some characteristics of the simple games can be recovered. The paper analyzes the capacity of binomial semivalues to summarize the structure of simple games, and, moreover, a property of separation among simple games is given. [ABSTRACT FROM AUTHOR]

This paper contributes to the program of numerical characterization and classification of simple games outlined in the classic monograph of von Neumann and Morgenstern. We suggest three possible ways to classify simple games beyond the classes of weighted and roughly weighted games. To this end we introduce three hierarchies of games and prove some relationships between their classes. We prove that our hierarchies are true (i.e., infinite) hierarchies. In particular, they are strict in the sense that more of the key 'resource' (which may, for example, be the size or structure of the 'tie-breaking' region where the weights of the different coalitions are considered so close that we are allowed to specify either winningness or nonwinningness of the coalition) yields the flexibility to capture strictly more games. [ABSTRACT FROM AUTHOR]

The Isbell desirability relation (I), the Shapley-Shubik index (SS) and the Banzhaf-Coleman index (BC) are power theories that grasp the notion of individual influence in a yes-no voting rule. Also, a yes-no voting rule is often used as a tool for aggregating individual preferences over any given finite set of alternatives into a collective preference. In this second context, Diffo Lambo and Moulen (DM) have introduced a power relation which ranks the voters with respect to how ably they influence the collective preference. However, DM relies on the metric d that measures closeness between preference relations. Our concern in this work is: do I, SS, BC and DM agree when the same yes-no voting rule is the basis for collective decision making? We provide a concrete and intuitive class of metrics called locally generated (LG). We give a characterization of the LG metrics d for which I, SS, BC and DM agree on ranking the voters. [ABSTRACT FROM AUTHOR]

In games with a coalition structure, players organize themselves in coalitions that form a partition of the set of players. In games with a coalition configuration, the union of the coalitions is the whole set of players but the coalitions are not necessarily disjoint. We introduce two variations of the Public Good Index for games with a coalition configuration, provide axiomatic characterizations of them, and apply them to a real world example. [ABSTRACT FROM AUTHOR]

Abstract: 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. [Copyright &y& Elsevier]

Abstract: The collection of the coalitions b is balanced if the Shapley value of the simple game is 0. This observation makes us able to derive a class of simple games with the coincidence property, that is, the Shapley value and the nucleolus coincide. And then we use such a class of simple games as generators to construct coincidence regions, convex cones consisting of games with the coincidence property. We will first propose the SP region. Two sets of games satisfying the coincidence property are introduced. Both are SP regions. In fact, the SP regions do not cover all games satisfying the coincidence property even for 3-person case. To enlarge the class of games with the coincidence property, the ST regions are proposed. All 3-person games with the coincidence property can be classified into 4 ST regions. [Copyright &y& Elsevier]

Abstract: In this paper we give necessary and sufficient conditions for a simple game to have rough weights. We define two functions and 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. [ABSTRACT FROM AUTHOR]

This paper introduces two variations of the Public Good Index (Holler, 1982) for games with a priori unions. The first one stresses the public good property which suggests that all members of a winning coalition derive equal power. The second variation follows earlier work on the integration of a priori unions (Owen, 1977 and 1982) and refers to essential subsets of an a priori union when allocating power shares. Axiomatic characterizations of both indices are discussed. Numerical examples, one of them taken from a political setting, illustrate the new power indices presented in this paper. [ABSTRACT FROM AUTHOR]

Abstract: We study the structure of unstable local effectivity functions defined for players and alternatives. A stability index based on the notion of cycle is introduced. In the particular case of simple games, the stability index is closely related to the Nakamura Number. In general it may be any integer between 2 and . We prove that the stability index for maximal effectivity functions and for maximal local effectivity functions is either 2 or 3. [Copyright &y& Elsevier]

A previous work by Friedman et al. (Theory and Decision, 61:305–318, 2006) introduces the concept of a hierarchy of a simple voting game and characterizes which hierarchies, induced by the desirability relation, are achievable in linear games. In this paper, we consider the problem of determining all hierarchies, conserving the ordinal equivalence between the Shapley–Shubik and the Penrose–Banzhaf–Coleman power indices, achievable in simple games. It is proved that only four hierarchies are non-achievable in simple games. Moreover, it is also proved that all achievable hierarchies are already obtainable in the class of weakly linear games. Our results prove that given an arbitrary complete pre-ordering defined on a finite set with more than five elements, it is possible to construct a simple game such that the pre-ordering induced by the Shapley–Shubik and the Penrose–Banzhaf–Coleman power indices coincides with the given pre-ordering. [ABSTRACT FROM AUTHOR]

In a coalitional voting game, an alternative is said to be in the core when no majority is willing to replace it with another alternative. A social choice correspondence is a mapping which associates any profile of voters’ preferences with a non-empty subset of the set of alternatives, which is understood as the set of selected outcomes. We characterize the social choice correspondences which always select the core of a simple game for any profile of preferences. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]

This paper provides “ready-to-apply” procedures, based on generating functions, which allow to compute power indices in weighted majority games restricted by an a priori system of unions. We illustrate these methods by an application to the International Monetary Fund. We compare the empirical properties of the coalitional and traditional power indices keeping the game fixed or allowing for variations in its set of parameters. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]

Focuses on a generalized decisiveness index for simple games that is able to encompass both normative and strategic features of collective decision-making mechanisms in voting procedures. Overview of the x-decisiveness index; Analysis of the behavior of decisiveness index with regard to the basic forms of compounding simple games; Properties of the x-decisiveness index; Information on the Banzhaf x-index.

One assumption in the Shapley–Shubik power index is that there is no interaction nor influence among the voting members. This paper will apply the command structure of Shapley (1994) to model members'' interaction relations by simple games. An equilibrium authority distribution is then formulated by the power-in/power-out mechanism. It turns out to have much similarity to the invariant measure of a Markov chain and therefore some similar interpretations are followed for the new setting. In some sense, one''s authority distribution quantifies his general administrative power in the organization and his long-run influence on all members. We provide a few applications in conflict resolution, college and journal ranking, and organizational choice. [Copyright &y& Elsevier]