An axiomatic characterization of the potential decisiveness index

AN AXIOMATIC CHARACTERIZATION OF THE POTENTIAL DECISIVENESS INDEX Josep Freixas and Montserrat Pons∗ November 6, 2013 Abstract Let us consider that somebody is extremely interested in increasing the probability of a proposal to be approved by a certain committee and let us assume that for achieving this goal he/she is prepared to pay off one member of the committee. In a situation like this one, and assuming that vote-buying is allowed and free of stigma, which voter should be offered a bribe? The potential decisiveness index for simple games, which measures the effect that ensuring one positive vote produces in the probability to pass the issue at hand, is a good tool to get the answer. An axiomatic characterization of this index is given in this paper, and its relation to other classical power indices is showed. Key words: Game theory, Potential decisiveness index; a measure for bribes; axiomatization; standard power indices; relationship among several measures. Math. Subj. Class. (2000): 91A12, 91A40, 91A80, 91B12. JEL Classification Numbers: C71, D71. ∗“Departament de Matem`atica Aplicada III i Escola Polit`ecnica Superior d’Enginyeria de Manresa (Universitat Polit`ecnica de Catalunya).” Spain. Research partially supported by “Ministerio de Econom´ıa y Competitividad proyecto MTM2012-34426/FEDER” and “Govern de la Generalitat de Catalunya SGR 2009–1029”. E-mails: [email protected], [email protected] 1 Introduction Assume that a proposal has to be submitted to a finite set of voters, that each voter has an independent a priori probability of voting in favor of the proposal and that some voting rules are established for deciding if the proposal will either be accepted or rejected after the votes are cast. Suppose now that an external influence is able to increase till 1 the probability of a voter for accepting the proposal. Of course, if this happens, and this voter has even a small influence in the final result, the probability for the proposal being approved will increase. The amount of this increasing effect is obviously not the same for all of the voters. It depends on how crucial is his/her vote and it also depends on his/her initial probability to vote for the proposal. A new index Ω for measuring potential decisiveness of voters in this context was introduced in [22], and it was proved that ensuring the favorable vote of the voter with maximum Ω–measure is the way to obtain the greatest increment in the probability of getting the proposal approved. Example 1.1 Assume that a jury has to take a decision on a case. For purposes of the example, we will suppose there are 4 jurors, one of whom is the president of the jury. Each juror will vote for either conviction or acquittal and the outcome of the vote will be the majority decision of the jury. Because ties are possible, these will be resolved by the casting vote of the president, i.e., the president plays the role of tiebreaker in the jury. Assume further that an external person, who is very interested in the verdict of the trial, estimates that the president will vote for acquittal with probability 1−p, while the other 3 jurors will vote for acquittal with an equal probability p. If the outsider considers the possibility of bribing one of the jurors to ensure his/her vote for acquittal with probability 1, which one of the jurors would he/she rather select to be offered the bribe: the president or any of the other three jurors? Some results in [23] allow us to select a list of voters to be persuaded, given any particular ranking of their predictions, and this procedure, which can be easily implemented in a computer, can be applied in an analogous way to select a list of voters to be bribed, i.e. voters with maximum value for the Ω–measure. We refer to these two papers for more examples about the applicability of the Ω–measure. 2 The usual model for a voting scenario like the one described is a simple game, that is to say, a pair (N, W), where N={1,2, . . . , n}denotes the set of voters, and Wis the set of winning coalitions, i.e., sets of voters whose favorable vote ensures the acceptation of the proposal. Subsets of Nthat are not in Ware called losing coalitions, and it is assumed that: 1) ∅is losing; 2) subsets of losing coalitions are again losing (monotonicity). It is assumed that W =∅, so that Nis always a winning coalition. A winning coalition is minimal if each proper subset is a losing coalition. The set of minimal winning coalitions is usually denoted by Wm, and, because of monotonicity, it completely determines the game. Given S⊆N,S=∅, the S–unanimity game (N, US) is the game which has Sas the unique minimal winning coalition. If S=Nthe game (N, UN) is just called the unanimity game. A voter i∈Nis null in (N, W) if idoes not belong to any minimal winning coalition, and it is a vetoer if it belongs to all of them. It is clear that in the S–unanimity game (N, US) all voters in N\Sare null and all voters in Sare vetoers. Classically, the only elements which are taken into account to define the power of a particular voter iare the set Nof all voters and the voting rule, defined by the set Wof winning coalitions. The definitions of power indices try to reflect different aspects of power. Most of them rely on the idea of measuring decisiveness (see [33] [29], [34], [5], [14] or [15] among others), but other aspects like success have also been used ([31], [18], [9], [7], [8], [35], [24]). There exist another approach, which we call the contextual approach, that takes into account, to measure the power of a voter i, not only the elements Nand Wbut also a probability distribution pover the vote configurations that can emerge. This contextual framework was introduced, as far as we know, by Laruelle and Valenciano ([26]), although some authors had already considered this kind of power indices before, with different probability distributions ([18], [35]). When independence of voter’s votes is assumed then the probability distribution pover the vote configurations is completely determined by the probabilities vector p= (p1, . . . , pn)∈[0,1]n, where piis the a priori probability of each voter ifor voting in favor of the proposal. Either in the classical approach or in the contextual one, a power index can also be defined by a set of properties which uniquely characterize it. This has been done for most of the classical indices, in particular the first axiomatization of the Shapley–Shubik index on simple games was given in [17] and the first one for the Banzhaf index in [18] (different alternative axiomatizations have been proposed, see 3 for example [32], [19]). In the contextual approach, a decisiveness index, which extends the Banzhaf index, was proposed in [18] and axiomatized in [10], different success indices were introduced in [26] and axiomatized in [2], and the potential decisiveness index was introduced in [22] and an axiomatization for it is presented in this work. The paper is organized as follows. In Section 2 the definition and the motivation of the potential decisiveness are recalled. An axiomatic characterization for this measure is established in Section 3, and the independence of the axioms is proved. Section 4 is devoted to relate this index with the classical Banzhaf and Shapley– Shubik indices, and Section 5 summarizes the contents of the paper and points out some future questions to work on. 2 The Ωmeasure of potential decisiveness Let (N, W) be a simple game, where N={1,2, . . . , n}denotes the set of voters (we assume that n≥2) and Wis the set of winning coalitions. Assume that each voter’s vote is independent of the others’ and let pibe the a priori probability of voter i for voting in favor of the proposal. Our contextual model is a triple (N, W,p), where (N, W) is the simple game and p= (p1, . . . , pn)∈[0,1]nis the probabilities vector. In [10] and [11], this triple is called assessed simple game and we also use this nomenclature in this paper. The set of all assessed simple games is denoted by ASG. Under the assumption of independence of voter’s votes, the probability for a proposal being accepted in (N, W,p) is given by f(N, W,p) = ∑ S∈W ∏ i∈S pi∏ i/∈S (1 −pi).(1) The function fis the multilinear extension (MLE) of the simple game (N, W) which was introduced by Owen in [28] in the general context of cooperative games. The MLE of a simple game is a polynomial function. Thus, it is continuous in its domain [0,1]nand differentiable in (0,1)n. It verifies two types of monotonicity properties: •f(N, W,p)≤f(N, W′,p) if W ⊆ W′, 4 •f(N, W,p)≤f(N, W,p′) if p≤p′(componentwise). We will use f(p) instead of f(N, W,p) whenever there is no possible misunderstanding. The increment on the probability f(p) due to an increment ∆pion piis: ∆if(p) = f(p+ ∆i(p)) −f(p) = fi(p)∆pi(2) where ∆i(p) = (0, . . . , 0,∆pi,0, . . . , 0), and fistands for the partial derivative of f with respect to the component i, which is non-negative. Note that ∆if(p) depends on fi(p) but also on the values ∆pithat is possible to achieve. Indeed, it is obvious that if pi= 1 no increase of this probability is possible, while if pi= 0 we can think of an increase ∆pi= 1. So the potential decisiveness importance of a voter idepends on two factors: the rate of change fi(p) and the a priori probability pi. This is the motivation given in [22] for defining the index Ω in the following way: Definition 2.1 The potential decisiveness index Ω is the map that assigns to every (N, W,p)∈ASG a vector Ω(N, W,p)∈[0,1]ndefined by: Ωi(N, W,p) = (1 −pi)fi(p). The function Ω is, for any fixed game (N, W), a continuous function on [0,1]n, differentiable of any order in its interior (0,1)n. From (2) it is clear that Ωi(N, W,p) = f(1i,p)−f(p), where f(1i,p) denotes the value of fon the vector (1i,p) obtained from pby replacing piwith 1. Thus, this index gives precisely the increment of f(p) obtained by only changing the i–component of pfrom pito 1. Corollary 3.3 in [22] shows that 0 ≤Ωi(N, W,p)≤1, where 0 is only achieved for null voters or for any other voter with pi= 1 (i.e., pure yes–voters), whereas 1 is only achieved for a dictator being a pure no-voter (i.e., Wm={{i}} and pi= 0). As the difference f(1i,p)−f(p) or, equivalently, Ωi(N, W,p) equals the increase of probability for the issue at hand to be passed when only voter ichanges his/her vote from pito 1, Ω is the most natural measure, from the probabilistic point of view, for bribes or vote buying in the context of assessed simple games, when the alleged briber is interested in approving the proposal. Once stated that this observation in terms of probability is the main support to this measure, we additionally propose in this paper a first axiomatic characterization for it. Thus, from the results of this 5 paper, the index Ω has support from both approaches, probabilistic and axiomatic. Needless to say that finding other axiomatizations for Ω is an open issue. This twofold characterization is a natural procedure for the justification of well known power indices in simple games. For instance, either the Banzhaf or the two Coleman’s power indices admit several axiomatic characterizations but also a probabilistic interpretation, see e.g. [27]. We also refer the interested reader to [22] and [23] for additional theoretical information about Ω, which, as far as we know, is the only tool expressly introduced to measure the potential decisiveness of voters in the context of assessed simple games. Note that if the alleged briber was interested in defeating the proposal (instead of approving it) then the difference f(p)−f(0i,p) would be the appropriate measure because it gives the increase of probability, in absolute value, for the issue at hand to be defeated when only voter ichanges his/her vote from pito 0. In this last expression, f(0i,p) denotes the value of fon the vector (0i,p) obtained from pby replacing piwith 0. This measure for assessed simple games is somehow analogous to Ω because, by applying (2) with ∆i(p) = (0, . . . , 0,−pi,0, . . . , 0), we obtain f(p)− f(0i,p) = pifi(p). Before continuing with the axiomatic characterization let us return to Example 1.1. Example 2.2 (Example 1.1 revisited) For the voting system in Example 1.1, we have N={1,2,3,4}, where 1denotes the president, W={{1,2},{1,3},{1,4},{1,2,3},{1,2,4},{1,3,4},{2,3,4},{1,2,3,4}}.1 For this game, expression (1) gives: f(p) = p1p2+p1p3+p1p4−p1p2p3−p1p2p4−p1p3p4+p2p3p4. Thus, the partial derivatives are: f1(p) = p2+p3+p4−p2p3−p2p4−p3p4, f2(p) = p1−p1p3−p1p4+p3p4, f3(p) = p1−p1p2−p1p4+p2p4, f4(p) = p1−p1p2−p1p3+p2p3. Let us consider now the particular value of p= (1 −p, p, p, p)for some 0<p<1. For this probability vector we have: f1(p) = 3p(1 −p)and f2(p) = f3(p) = f4(p) = 1This game can also be represented by the weighted game with representation [3; 2,1,1,1]. 6 1−3p+3p2.Thus, we can compare the potential decisiveness index of the president, i.e., player 1, with the potential decisiveness index of any other juror. Without loss of generality we take player 4: Ω1(N, W,p) = (1 −p1)f1(p)=3p2(1 −p), Ω4(N, W,p) = (1 −p4)f4(p)=1−4p+ 6p2−3p3. Thus, Ω1(N, W,p)−Ω4(N, W,p) = −3p2+ 4p−1and Ω1(N, W,p)−Ω4(N, W,p)>0⇔p∈(1/3,1), Ω1(N, W,p)−Ω4(N, W,p)<0⇔p∈(0,1/3). Hence, according to the potential decisiveness index, the president of the juror is the best candidate to be bribed in (N, W,p)if p > 1/3, while for p < 1/3any other juror should be chosen as a candidate to be bribed. Note also that the maximum difference in the interval (1/3,1) is achieved for p= 2/3. We remark that computing the MLE of a simple game is a complex task when the number of variables involved is high. Some bounds are obtained in [20], and various computation methods can be found, in another context, in [6] and [25]. From now on we restrict our work in proving some properties for the Ω measure, and in giving an axiomatic characterization of it. 3 Axiomatic characterization of the Ωmeasure In this section we establish some mathematical properties of the Ω measure and use them to give an axiomatic characterization of it. These properties are consequence of some characteristics of the MLE of a simple game that we collect in the following lemma. The first part will be used in the axiomatization of this index, while the second part is basic for establishing the relationship of the Ω measure with the Shapley-Shubik index. Lemma 3.1 Let (N, W,p)be an assessed simple game and f(N, W,p)its MLE as defined in (1). (a) If (N, f W,p)is another assessed simple game, then f(N, W ∪ f W,p) + f(N, W ∩ f W,p) = f(N, W,p) + f(N, f W,p). 7 (b) If π:N→Nis a permutation on N, then f(N, π(W),p) = f(N, W, π(p)), where π(W) = {π(S)|S∈ W} and, π(p) = (pπ(1), . . . , pπ(n)). Proof: (a) For any subset Aof 2Nwe define f(N, A,p) = ∑ S∈A ∏ i∈S pi∏ i/∈S (1 −pi). If (N, A) is a simple game then fis its MLE as defined in (1). It is also clear that if {W1,W2}is a partition of Wthen f(N, W,p) = f(N, W1,p) + f(N, W2,p). Thus, f(N, W ∪ f W,p) = f(N, W \ f W,p) + f(N, f W \ W,p) + f(N, W ∩ f W,p) =f(N, W,p)−f(N, W ∩ f W,p)+f(N, f W,p)−f(N, W ∩ f W,p)+f(N, W ∩ f W,p) =f(N, W,p) + f(N, f W,p)−f(N, W ∩ f W,p). (b) From (1) we can write f(N, π(W),p) = ∑ S∈π(W)∏ k∈S pk∏ k/∈S (1 −pk) = ∑ π−1(S)∈W ∏ k∈S pk∏ k/∈S (1 −pk) =∑ S∈W ∏ k∈π(S) pk∏ k/∈π(S) (1 −pk) = ∑ S∈W ∏ π−1(k)∈S pk∏ π−1(k)/∈S (1 −pk) =f(N, W, π(p))  In the following theorem, four basic properties of the potential decisiveness index Ω are established. We will prove later that these axioms completely characterize this index. In the following definition we introduce some new concepts needed to enounce the theorem. Definition 3.2 Let i∈Nand N−i=N\ {i}. The new game (N−i,W−i) is defined by S∈ W−iif and only if S⊆N−iand S∪ {i} ∈ W The game (N−i,W−i) is the reduced game of (N, W) determined by N\ {i}as defined in [36]. The notation we use is borrowed from [10]. 8 Theorem 3.3 Let (N, W,p)∈ASG and Ωbe the potential decisiveness index. (A1) Null voter property: If jis null in (N, W) then Ωj(N, W,p) = 0. (A2) External null voter property. If jis null in (N, W) then Ωi(N, W,p) = Ωi(N−j,W−j,p−j) for any i∈N(i=j), where the jth component of phas been deleted in p−j. (A3) Transfer property: If (N, f W)is another simple game, then Ω(N, W ∪ f W,p) + Ω(N, W ∩ f W,p) = Ω(N, W,p) + Ω(N, f W,p). (A4) Unanimity property: If (N, UN) is the unanimity game then Ωi(N, UN,p) = (1 −pi)∏ k∈N k=i pk for all i∈N. Proof: We start by proving that if jis null in (N, W), then f(N, W,p) = f(N−j,W−j,p−j). If jis null in (N, W) then it can not belong to any minimal winning coalition, so that S∈ W and j∈Simplies that S\ {j} ∈ W. Thus, we can write: f(N, W,p) = ∑ S∈W j /∈S∏ k∈S pk∏ k/∈S (1 −pk) + ∑ S∈W j∈S∏ k∈S pk∏ k/∈S (1 −pk) = (1 −pj)∑ S∈W j /∈S∏ k∈S pk∏ k/∈S k=j (1 −pk) + pj∑ S∈W j /∈S∏ k∈S pk∏ k/∈S k=j (1 −pk) =∑ S∈W j /∈S∏ k∈S pk∏ k/∈S k=j (1 −pk) = ∑ S∈W−j∏ k∈S pk∏ k/∈S (1 −pk) =f(N−j,W−j,p−j). (3) (A1) If jis null in (N, W) then, from (3), it is clear that pjdoes not appear in the expression of f(N, W,p) so that its corresponding partial derivative fj(N, W,p) = 0. Thus Ωj(N, W,p) = 0. (A2) If jis null in (N, W), then, from (3), f(N, W,p) = f(N−j,W−j,p−j), and therefore their respective partial derivatives with respect to any component i=j coincide. Thus, Ωi(N, W,p) = Ωi(N−j,W−j,p−j) for any i=j. 9 [7] B. Barry. Is it better to be powerfull or lucky? part i. Political Studies, pages 183–194, 1980. [8] B. Barry. Is it better to be powerfull or lucky? part ii. Political Studies, pages 338–352, 1980. [9] S.J. Brams and M. Lake. Power and satisfaction in a representative democracy. In P. Ordeshook, editor, Game Theory and Political Science, pages 529–562. New York University Press, 1978. [10] F. Carreras. α-Decisiveness in simple games. Theory and Decision, 56:77–91, 2004. [11] F. Carreras. A decisiveness index for simple games. European Journal of Operational Research, 163:370–387, 2005. [12] F. Carreras and J. Freixas. Some theoretical reasons for using regular semivalues. In H. De Swart, editor, Logic, Game Theory and Social Choice. Proceedings of the International Conference, LGS, pages 140–154, Tilburg, the Netherlands, 1999. [13] F. Carreras and J. Freixas. Semivalue versatility and applications. Annals of Operations Research, 109:341–356, 2002. [14] J.S. Coleman. Control of collectivities and the power of a collectivity to act. In B. Lieberman, editor, Social Choice, pages 269–300. Gordon and Breach, New York, USA, 1971. [15] J.S. Coleman. Combinatorics: Individual Interests and Collective Action: selected Essays. Cambridge University Press, 1986. [16] L. Diffo Lambo and J. Moulen. Ordinal equivalence of power notions in voting games. Theory and Decision, 53:313–325, 2002. [17] P. Dubey. On the uniqueness of the Shapley value. American Political Science Review, 4:131–139, 1975. [18] P. Dubey and L.S. Shapley. Mathematical properties of the Banzhaf power index. Mathematics of Operations Research, 4:99–131, 1979. 16 [19] V. Feltkamp. Alternative axiomatic characterizations of the Shapley and the Banzhaf values. International Journal of Game Theory, 24:179–186, 1995. [20] J. Freixas. Bounds for the owen’s multilinear extension. Journal of Applied Probability, 44:852–864, 2007. [21] J. Freixas. On ordinal equivalence of the Shapley and Banzhaf values for cooperative games. International Journal of Game Theory, 39:513–527, 2010. [22] J. Freixas and M. Pons. Two measures of circumstantial power: influences and bribes. Homo Oeconomicus, 22:569–588, 2005. [23] J. Freixas and M. Pons. Circumstantial power: optimal persuadable voters. European Journal of Operational Research, 186:1114–1126, 2008. [24] T. K¨oning and T. Br¨auninger. The inclusiveness of European decision rules. Canadian Journal of Theoretical Politics, 10:125–142, 1998. [25] W. Kuo and M.J. Zuo. Optimal Reliability Modeling: Principles and Applications. Wiley, New York, 2003. [26] A. Laruelle and F. Valenciano. Assessing success and decisiveness in voting situations. Social Choice and Welfare, 24:171–197, 2005. [27] A. Laruelle and F. Valenciano. Voting and Collective Decision–Making. Cambridge University Press, 2008. [28] G. Owen. Multilinear extensions of games. Management Science, 18:64–79, 1972. [29] L.S. Penrose. The elementary statistics of majority voting. Journal of the Royal Statistical Society, 109:53–57, 1946. [30] R. Pongou, B. Tchantcho, and L. Diffo Lambo. Political influence in multichoice institutions: cyclicity, anonymity and transitivity. Theory and Decision, 70:157–178, 2011. [31] D. Rae. Decision rules and individual values in constitutional choice. American Political Science Review, 63:40–56, 1969. 17 [32] A.E. Roth. Introduction to the Shapley value. In A.E. Roth, editor, The Shapley value. Essays in Honor of L.S. Shapley, pages 1–27. Cambridge University Press, 1988. [33] L.S. Shapley. A value for n-person games. In A.W. Tucker and H.W. Kuhn, editors, Contributions to the theory of games II, pages 307–317. Princeton University Press, Princeton, USA, 1953. [34] L.S. Shapley and M. Shubik. A method for evaluating the distribution of power in a committee system. American Political Science Review, 48:787–792, 1954. [35] P.D. Straffin, M.D. Davis, and S.J. Brams. Power and satisfaction in an ideologically divided voting body. In M.J. Holler, editor, Power, voting and voting power, pages 239–253. Physica Verlag, W¨urzburg–Wien, 1982. [36] A.D. Taylor and W.S. Zwicker. Simple games: desirability relations, trading, and pseudoweightings. Princeton University Press, New Jersey, USA, 1999. [37] B. Tchantcho, L. Diffo Lambo, R. Pongou, and B. Mbama Engoulou. Voters’ power in voting games with abstention: Influence relation and ordinal equivalence of power theories. Games and Economic Behavior, 64:335–350, 2008. 18