Mathematical structures of simple voting games

We address simple voting games (SVGs) as mathematical objects in their own right, and study structures made up of these objects, rather than focusing on SVGs primarily as co-operative games. To this end it is convenient to employ the conceptual framework and language of category theory. This enables us to uncover the underlying unity of the basic operations involving SVGs.     

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.     

On the Cores of cooperative games and the stability of the Weber set

In this paper conditions are given guaranteeing that the Core equals the D-core (the set of unDominated imputations). Under these conditions, we prove the non-emptiness of the intersection of the Weber set with the imputation set. This intersection has a special stability property: it is externally stable. As a consequence we can give a new characterization (th. 3.2) for the convexity of a cooperative game in terms of its stability (von Neumann-Morgenstern solutions) using the Weber set.     

The bargaining set of four-person balanced games

It is well known that in three-person transferable-utility cooperative games the bargaining set ℳⁱ ₁ and the core coincide for any coalition structure, provided the latter solution is not empty. In contrast, five-person totally-balanced games are discussed in the literature in which the bargaining set ℳⁱ ₁ (for the grand coalition) is larger then the core. This paper answers the equivalence question in the remaining four-person case. We prove that in any four-person game and for arbitrary coalition structure, whenever the core is not empty, it coincides with the bargaining set ℳⁱ ₁. Our discussion employs a generalization of balancedness to games with coalition structures. Received: August 2001/Revised version: April 2002     

The reactive bargaining set of some flow games and of superadditive simple games

We prove that the reactive bargaining set coincides with the core of simple flow games, and it essentially coincides with the kernel of simple superadditive games.     

The kernel and bargaining set for convex games

It is shown that for convex games the bargaining set? ₁ ⁽ⁱ⁾ (for the grand coalition) coincides with the core. Moreover, it is proved that the kernel (for the grand coalition) of convex games consists of a unique point which coincides with the nucleolus of the game.     

The reactive bargaining set for cooperative games

We introduce a new bargaining set for cooperative games in characteristic function form, and investigate its structure and properties. We prove that the new bargaining set is not empty. In fact, we show that it contains the kernel and is contained in the classical bargaining set ${\mathcal{M}^i_1}$ , and we further prove that it consists of the unique symmetric vector for the class of simple majority games.     

A class of power indices for voting games

A class of power indices is discussed which includes not only the usual power indices but also the class of semivalues and the indices introduced byDeegan/Packel [1978]. Sufficient conditions for members of this class to be symmetric, support-independent, and self-dual are given. We then discuss various conditions under which members of this class coincide with the ShapleyShubik and Banzhaf indices.     

A core of voting games with improved foresight

This paper considers voting situations in which the vote takes place iteratively. If a coalition replaces the status quo a with a contestant b, then b becomes the new status quo, and the vote goes on until a candidate is reached that no winning coalition is willing to replace. It is well known that the core, that is, the set of undominated alternatives, may be empty. To alleviate this problem, Rubinstein [Rubinstein, A., 1980. Stability of decision systems under majority rule. Journal of Economic Theory 23, 150–159] assumes that voters look forward one vote before deciding to replace an alternative by a new one. They will not do so if the new status quo is going to be replaced by a third that is less interesting than the first. The stability set, that is, the set of undominated alternatives under this behavior, is always non-empty when preferences are strict. However, this is not necessarily the case when voters’ indifference is allowed. Le Breton and Salles [Le Breton, M., Salles, M., 1990. The stability set of voting games: Classification and generecity results. International Journal of Game Theory 19, 111–127], Li [Li, S., 1993. Stability of voting games. Social Choice and Welfare 10, 51–56] and Martin [Martin, M., 1998. Quota games and stability set of order d. Economic Letters 59, 145–151] extend the sophistication of the voters by having them look d votes forward along the iterative process. For d sufficiently large, the resulting set of undominated alternatives is always non-empty even if indifference is allowed. We show that it may be unduly large. Next, by assuming that other voters along a chain of votes are also rational, that is, they also look forward to make sure that the votes taking place later on will not lead to a worst issue for them, we are able to reduce the size of this set while insuring its non-emptiness. Finally, we show that a vote with sufficient foresight satisfies a no-regret property, contrarily to the classical core and the stability set.     

The core and the bargaining set in glove-market games

In a glove-market game, the worth of a coalition is defined as the minimum, over all commodities in the market, of the total quantity that the coalition owns of each commodity. We identify a subclass of these games for which the core and the bargaining set coincide with the set of competitive equilibrium outcomes. We present examples showing that these solution concepts differ outside that subclass. We also illustrate a peculiar behavior of the bargaining set with respect to replication of a glove-market. These examples provide a simple economic setting in which the merits of the various solution concepts may be discussed and compared.Correspondence with Michael Maschler is gratefully acknowledged.This authors work was partly done while visiting the Department of Mathematics, Massachusetts Institute of Technology. Research supported by the Fund for the Promotion of Research at the Technion.     

The core and the Weber set for bicooperative games

This paper studies two classical solution concepts for the structure of bicooperative games. First, we define the core and the Weber set of a bicooperative game and prove that the core is always contained in the Weber set. Next, we introduce a special class of bicooperative games, the so-called bisupermodular games, and show that these games are the only ones in which the core and the Weber set coincide.      

The intermediate set and limiting superdifferential for coalitional games: between the core and the Weber set

We introduce the intermediate set as an interpolating solution concept between the core and the Weber set of a coalitional game. The new solution is defined as the limiting superdifferential of the Lovász extension and thus it completes the hierarchy of variational objects used to represent the core (Fréchet superdifferential) and the Weber set (Clarke superdifferential). It is shown that the intermediate set is a non-convex solution containing the Pareto optimal payoff vectors that depend on some chain of coalitions and marginal coalitional contributions with respect to the chain. A detailed comparison between the intermediate set and other set-valued solutions is provided. We compute the exact form of intermediate set for all games and provide its simplified characterization for the simple games and the glove game.     

Two hardness results for core stability in hedonic coalition formation games

We establish NP-completeness of two problems on core stable coalitions in hedonic games. In the first problem every player has only two acceptable coalitions in his preference list, and in the second problem the preference structures arise from the distances in an underlying metric space.     

A further result on the core of voting games

LetN be a set of individuals,A a closed bounded interval ofRe. Using a former result ofNakamura, it is shown that if every individual inN has a quasi-concave utility function overA, then a proper simple game has a non-empty core which is a convex set. In particular, the majority core is explicitly characterized. When every individual inN has a strictly quasi-concave utility function overA, then it is shown that the local core in a proper simple game is precisely the core.     

A note on hierarchies in weighted voting games and partitions

Weighted voting games (WVGs) model situations where voters, possibly controlling different numbers of votes, vote yes or no on a proposition. A proposition passes if and only if the number of yes votes meets or exceeds a quota \(q\). Each winning coalition is a partition of an integer greater than or equal to \(q\), with parts taken from the set of all weights for that game. Results about WVGs are here interpreted as results about partitions.     

The reactive bargaining set: Structure, dynamics and extension to NTU games

The reactive bargaining set (Granot [1994]) is the set of outcomes for which no justified objection exists. Here, in a justified objection the objector first watches how the target tries to act (if he has such an option), and then reacts by making a profit and ruining the target's attempt to maintain his share. In this paper we explore properties of the reactive bargaining set, set up the system of inequalities that defines it, and construct a dynamic system in the sense of Stearns' transfer scheme that leads the players to this set. We also extend the definition of the reactive bargaining set toNTU games in a way that keeps it nonempty. To shed light on its nature and its relative ease of computation, we compute the reactive bargaining set for games that played important role in the game theory literature.     

The core and the Weber set of games on augmenting systems

This paper deals with cooperative games in which only certain coalitions are allowed to form. There have been previous models developed to confront the problem of unallowable coalitions. Games restricted by a communication graph were introduced by Myerson and Owen. In their model, the feasible coalitions are those that induce connected subgraphs. Another type of model is introduced in Gilles, Owen and van den Brink. In their model, the possibilities of coalition formation are determined by the positions of the players in a so-called permission structure. Faigle proposed a general model for cooperative games defined on lattice structures. In this paper, the restrictions to the cooperation are given by a combinatorial structure called augmenting system which generalizes antimatroid structure and the system of connected subgraphs of a graph. In this framework, the core and the Weber set of games on augmenting systems are introduced and it is proved that monotone convex games have a non-empty core. Moreover, we obtain a characterization of the convexity of these games in terms of the core of the game and the Weber set of the extended game.     

Monotonicity of power in weighted voting games with restricted communication

Indices that evaluate the distribution of power in simple games are commonly required to be monotonic in voting weights when the game represents a voting body such as a shareholder meeting, parliament, etc. The standard notions of local or global monotonicity are bound to be violated, however, if cooperation is restricted to coalitions that are connected by a communication graph. This paper proposes new monotonicity concepts for power in games with communication structure and investigates the monotonicity properties of the Myerson value, the restricted Banzhaf value, the position value, and the average tree solution.