Keywords

These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

1 Introduction

In several decisional situations the result is simply in favor or against a proposal, with no intermediate position, so that they are often referred to as 0-1 decision problems, where 1 means that the proposal is accepted and 0 that it is rejected. Accordingly, the decision-makers express their preferences to be favorable or not to the proposal. The most common of these situations take place in Parliamentary voting sessions, board of directors decisions and so on. An important question is how to evaluate the influence of each member on the final decision, especially when the members are not equivalent, for instance because they are political parties with different numbers of seats in the Parliament or stakeholders endowed with different stock shares. This analysis may be performed, inter alia, by using power indices.

A simple representation of decisional situations is through a weighted majority situation \([q; w_1,w_2,...,w_n]\), where given a set \(N = \{1, 2, ..., n\}\) of decision-makers, \(w_i\) is the weight of agent \(i \in N\), e.g. the number of seats of a party or the stock share of a stakeholder, and \(q\) is the majority quota; the interpretation is that a subset \(S \subseteq N\) of decision-makers is able to pass a proposal if and only if \(\sum _{i \in S} w_i \ge q\). It is possible to associate a weighted majority game \((N,v)\) defined as:

$$\begin{aligned} v(S) = \left\{ {\begin{array}{cc} 1\quad&\qquad{{\text{ if}} \sum \nolimits _{{i \in S}} {w _{i} \ge {{q}}} } \\ 0\quad&{{ \text{ otherwise}}} \\ \end{array} } \right.,\quad S \subseteq N \end{aligned}$$

A coalition \(S \subseteq N\) is called winning if \(v(S) = 1\) and losing if \(v(S) = 0\).

We start shortly surveying the literature on power indices. The large number of existing power indices depends on the matter that each emphasizes different features of the problem, making it particularly suitable for specific situations.

The first indices (see Penrose 1946; Shapley and Shubik 1954; Banzhaf 1965; Coleman 1971) are based on the ability of a decision-maker to switch the result of the voting from rejection to approval by joining a set of other decision-makers that are in favor of the proposal. More precisely, the indices of Penrose, Banzhaf and Coleman tally the switches w.r.t. the possible coalitions, while in the Shapley-Shubik index also the order agents form a coalition plays a role.

In 1977 two important contributions strongly modified the prevailing power indices, introducing the element of possible relations among the agents. Myerson (1977) proposed to use an undirected graph, called communication structure, in order to represent the relationships among the decision-makers and determining the Shapley value of a suitably restricted game. Owen (1977) introduced the a priori unions, or coalition structures, that account for existing agreements, not necessarily binding, among some decision-makers. The relationship among the power indices, mainly Shapley-Shubik and Banzhaf, in the original game and in the restricted game á la Myerson was studied in Owen (1986), with particular attention to those situations in which the underlying graph is a tree.

Recently, in Khmelnitskaya (2007) the communication structures by Myerson and the coalition structures by Owen were combined to define a new index.

In the following years, several new indices were introduced for better representation of other situations. Deegan and Packel (1978) defined a new index that considers only the minimal winning coalitions, i.e. those coalitions in which each agent is critical, in the sense that the coalition becomes losing when s/he leaves; Johnston (1978) used a similar model but he considered the quasi-minimal winning coalitions, i.e. those coalitions in which at least one agent is critical. Both indices are based on the idea of dividing the unitary power among the minimal or quasi-minimal winning coalitions, respectively; then the power assigned to each coalition is equally shared among the critical agents in it. We may say that they suppose that a very large coalition, in which no agent is critical, has no possibility to form, as the “cake should be divided among too many agents”.

Holler (1982) introduced the Public Good index, supposing that the worth of a coalition is a public good, so the members of the winning decisive sets, i.e. the minimal winning coalitions, have to enjoy the same value. The result is that the power of an agent is proportional to the number of minimal winning coalitions s/he belongs to.

Another important contribution was due to Kalai and Samet (1987). They introduced the idea of adding a weight to the elements characterizing each agent, besides her/his ability of switching the result; Haeringer (1999) combined the idea of the weights by Kalai and Samet with the idea of communication structure.

In 1989 Winter extended the idea of a priori unions by Owen by requiring that the different unions may join only according to a predefined scheme, that he called levels structure, and introduced the levels structure value.

In the following years, some papers dealt with situations in which only some coalitions are feasible, not only for communication reasons but also for possible incompatibilities among the agents; two main research fields are related to the permission structures and to special structures of the feasible coalitions. In the first group we mention the papers by Gilles et al. (1992), Van den Brink and Gilles (1996) and Van den Brink (1997). In the second group we cite the papers by Bilbao et al. (1998) and by Bilbao and Edelman (2000) that consider the Banzhaf index and the Shapley value on convex geometries, respectively and the papers by Algaba et al. (2003, 2004) that study the Shapley value and the Banzhaf value on antimatroids, respectively. We refer to the paper by Katsev (2010) for a survey on values for games with restricted cooperation.

Fragnelli et al. (2009) introduced a new family of power indices, called FP, that account the issue of contiguity in a monodimensional voting space; the indices in this family require to select a set of contiguous winning coalitions among which the unitary power is divided accounting the probability that each coalition form, then the power of each coalition is shared among its parties according to their relevance in the coalition. The idea of contiguity was extended to the idea of connectedness in a possibly multidimensional voting space by Chessa and Fragnelli (2011). In both cases, non-contiguous and non-connected coalitions are ignored. The idea of monodimensionality of the voting space was already considered in Amer and Carreras (2001).

We refer to the papers for the formal definitions of the indices and for further details.

In this note, we concentrate on the concept of incompatible agents. Communication structures provide a very powerful tool for representing incompatibilities, but it is necessary to carefully analyze them in order to decide which structure is more suitable in a given majority situation, in which the agents are not available to form any (theoretically) possible coalition.

2 Communication Structures and Incompatible Agents

In Myerson (1977) considers a situation in which communication is represented by using an undirected graph whose vertices correspond to the agents and the edges connect pairs of agents that are compatible (or may communicate). In the restricted game introduced by Myerson, a coalition is feasible and its worth is “effective” if the vertices associated to its players are connected, otherwise the worth of the coalition is the sum of the worths of the subcoalitions in the partition in connected components induced by the communication graph.

It is possible to raise some questions about this approach in a weighted majority situation setting; for doing so, let us consider the following example.

Example 1

Let \(N = \{1,2,3,4\}\) be the set of parties of the weighted majority situation \([51; 35, 30, 25, 10]\); the winning coalitions are \(\{1,2\}\), \(\{1,3\}\), \(\{2,3\}\), \(\{1,2,3\}\), \(\{1,2,4\}\), \(\{1,3,4\}\), \(\{2,3,4\}\), \(\{1,2,3,4\}\) and suppose that the communication structure is represented by the graph \(G\) in the following figure:

Player \(4\) is not connected and therefore will not be in a feasible coalition with one of the other players; also players \(1\) and \(3\) are not directly connected. In the restricted game \((N,v_G)\) induced by the graph \(G\), the winning coalitions reduce to \(\{1,2\}\), \(\{2,3\}\), \(\{1,2,3\}\), \(\{1,2,4\}\), \(\{2,3,4\}\), \(\{1,2,3,4\}\); for instance, \(v_{G}(\{1,3\}) = v(\{1\}) + v(\{3\}) = 0\) while \(v_{G}(\{1,2,4\}) = v(\{1,2\}) + v(\{4\}) = 1\).

We may provide some comments.

  1. (i)

    The games \(v\) and \(v_G\) are monotonic; in fact, \(v_G(\{1,2\}) = 1\) and \(v_G(\{1,2,4\}) = 1\), even if the second coalition is not feasible, being not connected.

  2. (ii)

    Dealing with infeasible coalitions, we may have some problems for computing indices based on the marginal contributions or swings. Let us consider the weighted majority situation \([51; 24, 25, 51]\) in which coalitions have to be contiguous, so the feasible winning coalitions are \(\{3\}\), \(\{2,3\}\), \(\{1,2,3\}\) and party \(3\) should have all the power. On the other hand the infeasible coalition \(\{1,3\}\) needs some comments. If we assign it value \(0\), we face the situation in which party \(1\) enters the winning coalition \(\{3\}\) generating the losing coalition \(\{1,3\}\), i.e. party \(1\) has a negative marginal contribution or a negative swing; moreover, party \(2\) results to be critical for coalition \(\{1,2,3\}\), so it has a positive marginal contribution or a positive swing. A possible solution is to account only the marginal contributions and the swings that involve pairs of feasible coalitions, including losing ones, and to modify the definition of the indices accordingly. Of course, this problem does not show up with those indices, like Deegan-Packel, Johnston and Holler, which do not compare pairs of coalitions.

  3. (iii)

    In Example 1, the graph \(G\) indicates that coalitions \(\{1,2\}\), \(\{2,3\}\), \(\{1,2,3\}\) are feasible while coalition \(\{1,3\}\) is infeasible. Now, let us suppose that parties \(1\) and \(3\) are both available for forming a two-party majority with party \(2\) but they never want to stay in the same coalition, so that also coalition \(\{1,2,3\}\) is infeasible; the previous approach does not enable us to represent this situation.

  4. (iv)

    Referring to the previous point, we can modify the definition of feasibility saying that a coalition is feasible if the corresponding subgraph is complete (clique). In this way the graph \(G\) represents the situation in which coalitions \(\{1,2\}\), \(\{2,3\}\) are feasible and coalitions \(\{1,3\}\), \(\{1,2,3\}\) are infeasible. If we want to represent a situation in which coalition \(\{1,2,3\}\) is feasible, we may consider the graph \(G^{\prime }\), where an edge between parties \(1\) and \(3\) is added:Unfortunately, the new graph \(G^{\prime }\) indicates that parties \(1\) and \(3\) accept forming a majority also without party \(2\). The problem cannot be solved neither introducing oriented arcs instead of unoriented edges.

  5. (v)

    Supposing that a suitable tool for representing all the feasible coalitions, and no more, is available, all these coalitions are usually considered equivalent, so another interesting question arises: how to evaluate the probability that a coalition forms? Having in mind the work by Calvo et al. (1999), we may associate to edge \((i,j), i,j \in N\) a real number \(0 \le p_{ij} \le 1\) that can be viewed as the probability that the two parties \(i\) and \(j\) enter the same coalition, so we have to find a method for computing the probability \(p_S\) of each feasible coalition \(S \subseteq N\).

A simple idea is to define \(p_S\) as the product of the weights of the edges of the subgraph associated to \(S\). We may remark that this method requires assuming that the events that two parties join are independent. Then, we may observe that \(S \subset T\) implies \(p_S \ge p_T\); if we account only minimal winning coalitions, \(T\) is not minimal and then it is excluded. In the other situations, it is equivalent to the hypothesis that a larger coalition has a larger cost so its probability decreases. But also in this case, we may raise a question. For instance, if we compute \(p_{\{1,2,3\}}\) referring to the graph \(G\) it is given by \(p_{12} p_{23}\) that is greater than or equal to \(p_{12} p_{23} p_{13}\) that is the value obtained referring to the graph \(G^{\prime }\). On the other hand, it is reasonable to expect a larger probability when we refer to the graph \(G^{\prime }\) where the three parties have stronger connections. This situation may be solved by imposing a complete graph, i.e. all pairs of nodes are connected by an arc. This approach was introduced by Calvo et al. (1999) for introducing the probabilistic extension of the Myerson value. They suppose that all pairs of agents may join according to a probability of direct communication that can be viewed as a degree of cooperation. The probability that a coalition of agents forms when a probabilistic communication graph is assigned is the product of the probabilities of the edges in the graph times the probability that the other edges of the subgraph associated to the coalition are not used. Finally, they define a restricted game in which the value of each coalition is the sum over all the subgraphs defined on the vertices associated to the coalition itself of the product of the probabilities that the coalition forms with each communication subgraph times the value of the coalition in the restricted game á la Myerson in that subgraph. Another approach is to define the probability of a coalition as the sum of the probabilities of the edges of the corresponding subgraph. Again, we may remark that it corresponds to require that the events that two parties enter the same coalition are disjoint, otherwise the resulting probability could be larger than 1. Finally, we remark that the probability to form for the different coalitions cannot be based on the same hypotheses whatever the parties entering the coalitions and that the parties in a coalition may influence the probability of the entrance of a new party. For instance, a left party will enter a right parties coalition with a low probability, but the probability increases if the coalition includes center parties and increases more if the resulting coalition is contiguous.

3 Concluding Remarks

Summarizing, we may say that, in our opinion, a good way to deal with incompatible agents is to use a graph to represent compatibilities among pairs of agents; then a set of feasible coalitions (or “relevant” coalitions) can be identified as a subset of all the connected coalitions; finally, a probability is assigned to each feasible coalition, referring to opinions of a panel of experts, or to the majorities formed in the past. This approach does not require the estimation of the probabilities of all the pairs of agents (for instance, see Remark 5.3 in Calvo et al. 1999, and does not need any hypothesis for adding or multiplying the probabilities of the pairs for assigning the probabilities of the coalitions.

We may also notice that this idea fits very well the requirements of the FP indices for contiguous/connected coalitions (see Fragnelli et al. 2009; Chessa and Fragnelli 2011) we can define the weights of the coalitions as their normalized probabilities, and the weights of the parties in each coalition as their percentages of seats in that coalition.

As we said in the previous section, another interesting open problem is the modification of indices based on marginal contributions and swings when some coalitions are infeasible.