Hostname: page-component-cd9895bd7-q99xh Total loading time: 0 Render date: 2024-12-26T19:17:29.034Z Has data issue: false hasContentIssue false
  • English
  • Français

On the Size of Winning Coalitions*

Published online by Cambridge University Press:  01 August 2014

Kenneth A. Shepsle
Kenneth A. Shepsle*
Affiliation:
Washington University, St. Louis
Get access Rights & Permissions [Opens in a new window]

Abstract

A recent note by Robert Butterworth is critical of William Riker's size principle on several important grounds. There is, however, an important omission in his analysis which this present essay aims to correct. The author goes on to tie assertions about coalition structure in n-person zero-sum games to a solution theory for such games. In the appendix to this essay the general five-person game, of which Butterworth's game is a special case, is considered in some detail. The effect, with one reasonable solution theory, is a favorable appraisal of the size principle.

Type
Articles
Information
American Political Science Review , Volume 68 , Issue 2 , June 1974 , pp. 505 - 518
Copyright
Copyright © American Political Science Association 1974

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

Footnotes

*

The author would like to acknowledge the helpful criticisms of an earlier draft of this paper by Steven Brams and William Riker, as well as those of several anonymous referees. Although considerably revised, this current version may still have failed to accommodate all of their remarks. The critics, therefore, are not responsible for what is contained herein. Financial support by the National Science Foundation, under Grant GS-33053, is also appreciatively acknowledged.

References

1 Butterworth, Robert, “A Research Note on the Size of Winning Coalitions,” American Political Science Review, 65 (09, 1971), 741–745 CrossRefGoogle Scholar.

2 von Neumann, John and Morgenstern, Oskar, The Theory of Games and Economic Behavior, science edition (New York: John Wiley, 1964)Google Scholar.

3 Aumann, Robert and Maschler, Michael, “The Bargaining Set for Cooperative Games,” in Advances in Game Theory, ed. Dresher, Melvin, Shapley, L. S., and Tucker, A. W. (Princeton: Princeton University Press, 1964), pp. 443–476 Google Scholar.

4 Riker, William H., The Theory of Political Coalitions (New Haven: Yale University Press, 1962), p. 32 Google Scholar.

5 Riker, William H., “A New Proof of the Size Principle,” in Mathematical Applications in Political Science, II, ed. Bernd, Joseph L. (Dallas: Southern Methodist University Press, 1966), pp. 167–174 Google Scholar. For the moment, technical definitions and notation are avoided. Thus, the definition of the characteristic function will remain vague until a more formal analysis is employed. Suffice it to say that the characteristic function of a game specifies the worth or value of a coalition.

6 Butterworth, , “A Research Note,” p. 744 Google Scholar.

7 Not all games are adequately represented by a characteristic function. In Competition, Welfare, and the Theory of Games (unpublished manuscript), L. S. Shapley and Martin Shubik suggest a number of deficiencies in a characteristic function representation to which the interested reader is referred. For additional formal considerations see Rosenthal, Robert W., “Cooperative Games in Effectiveness Form,” Journal of Economic Theory, 5 (08, 1972), 88–101 CrossRefGoogle Scholar, and Wilson, Robert, “Stable Coalition Proposals in Majority-Rule Voting,” Journal of Economic Theory, 3 (09, 1971), 254–271 CrossRefGoogle Scholar. Throughout I shall focus exclusively on games in characteristic function form—what Shapley and Subik call c-games.

8 It is clear that many political games are not symmetric. In a legislature, for example, a majority coalition that does not contain a majority of members on a relevant committee and/or subcommittee is usually not winning. The status of a coalition, in this case, does depend on the labels or roles which identify its members.

9 It is, of course, the case that players a, b, …, e may be permuted among the payoffs for each coalition size. There are 10 three-member coalitions and four-member coalitions.

10 Butterworth, , “A Research Note,” p. 742 Google Scholar.

11 Riker, it seems, is very close to making this observation when he notes the tension of a coalition that receives more than it is objectively worth. See Riker, William H., “Comment on Butterworth, ‘A Research Note on the Size of Winning Coalitions,’” American Political Science Review, 65 (09, 1971), 745–747 CrossRefGoogle Scholar.

13 An excellent, readable discussion of solution theory is found in Shapley and Shubik, Competition, Welfare, and the Theory of Games. Other important treatments include Aumann, Robert, “A Survey of Cooperative Games Without Sidepayments,” in Essays in Mathematical Economics in Honor of Oskar Morgenstern, ed. Shubik, Martin (Princeton: Princeton University Press, 1967), pp. 3–27 CrossRefGoogle Scholar; Aumann and Maschler, “The Bargaining Set”; Gelbaum, B. R., “Symmetric Zero-Sum n-Person Games,” in Contributions to the Theory of Games, IV, ed. Tucker, A. W. and Luce, R. D. (Princeton: Princeton University Press, 1959), pp. 95–109 Google Scholar; Luce, R. Duncan and Raiffa, Howard, Games and Decisions (New York: John Wiley, 1957)Google Scholar; Shapley, L. S., “Simple Games: An Outline of the Descriptive Theory,” Behavioral Science, 7 (01, 1962), 59–66 Google Scholar; Shapley, L. S., “Solutions of Compound Simple Games,” in Advances in Game Theory, ed. Dresher, Melvin, Shapley, L. S. and Tucker, A. W. (Princeton: Princeton University Press, 1964), pp. 267–306 Google Scholar; Shapley, L. S., “Compound Simple Games, III1,” RM-5438-PR (Santa Monica: RAND Corporation, 1967)Google Scholar; Vickrey, William, “Self-Policing Properties of Certain Imputation Sets,” in Contribution to the Theory of Games, IV, ed. Tucker, A. W. and Luce, R. D. (Princeton: Princeton University Press, 1959), pp. 213–246 Google Scholar; Wilson, Robert, “A Class of Solutions for Voting Games,” Working Paper #156, Stanford Business School, 1968 Google Scholar; and Robert Wilson, “Stable Coalition Proposals.” Of course, von Neumann and Morgenstern, The Theory of Games, is an historically important primary source. It might also be added that Shapley has contributed a very large number of significant results, only a small number of which are cited here.

14 In a zero-sum game, for example, a coalition C does determine the payoff for C, namely — v(C), but it cannot affect the way in which the i∈C′ distribute — v(C) among themselves.

15 Recall note 12 above. Riker sought to bypass altogether the notion of solution as an “acceptable” distribution of gains and losses, instead focusing exclusively on coalition structures.

16 Technical note: These conditions apply to the case of transferable utility. An analogous set of conditions exists for the nontransferable case. See Aumann, “A Survey of Cooperative Games.”

17 Much of this section follows Wilson, Robert, “A Game-Theoretic Analysis of Social Choice,” in Social Choice, ed. Lieberman, Bernhardt (New York: Gordon and Breach, 1971), pp. 393–407 Google Scholar, Wilson, “Stable Coalition Proposals,” and Shapley and Shubik, Competition, Welfare, and the Theory of Games, although there have been some notational changes.

18 For a generalization of effectiveness that does not rely on the characteristic function, see Rosenthal, “Cooperative Games,” and Wilson, “Stable Coalition Proposals.”

19 Throughout I shall assume that xRiy means xiRiyi . Player i, that is, evaluates the imputations x and y solely according to his own payoffs.

20 Other core-like solution concepts have been examined in the game theory literature. The ϵ-core, for example, is the set of imputations in which every coalition C receives within an ϵ of its value:

If the costs of coalition formation and negotiation exceed ϵ, then the elements of the ϵ-core may be quite stable, even if some coalitions receive less than their value. Moreover, the e-core always exists for some ϵ. Of course, the ϵ-core and the core are identical for ϵ = 0.

21 It should be noted that one buys more than existence when imputations are joined to the core to produce V. The core lacks external stability (see (4.1) below) so that there may be some difficulty in getting into the core, even when it exists. That is, although the core contains imputations that are themselves undominated, elements of the core do not necessarily dominate imputations outside the core. Thus, from an initial point outside the core, an imputation in the core may be “unreachable” by the process of dominance. Some strands of exchange theory are concerned with the additional structure required to insure that final allocations of economic goods lie in the core of the economy. The interested reader should consult the excellent presentation in Newman, Peter, The Theory of Exchange (Englewood Cliffs: Prentice-Hall, 1965), esp. chap. 5Google Scholar.

22 See Lucas, William F., “The Proof That a Game May Not Have a Solution,” Transactions of the American Mathematical Society, 137 (03, 1969), 219–229 CrossRefGoogle Scholar.

23 In the Appendix some general results by Gelbaum are employed. See Gelbaum, “Symmetric, Zero-Sum, n-Person Games.” The reader may also wish to consult von Neumann, and Morgenstern, , Theory of Games and Economic Behavior, pp. 330–338 Google Scholar.

24 It is of historical interest to note that an earlier version of the MPG principle, applied to a slightly different class of games, appears in the work of Vickrey. See his “Self-Policing Properties” and especially his Lemma 6 which applies to constant-sum simple games.

25 Inequality (5.2) bears a slight resemblance to Aumann and Maschler's notion of a coalitionally rational payoff configuration (c.r.p.c). In their early work on the bargaining set, however, they require (5.2) not only for extant coalitions, but also for subsets of extant coalitions:

(5.2′)

for all

That is, they additionally “assume that a coalition will not form if some of its members can obtain more by themselves forming a permissible coalition (emphasis added).” See Aumann and Maschler, “The Bargaining Set,” p. 445. Wilson, too, assumes (5.2′) by restricting consideration to MWC's. See Robert Wilson, “Stable Coalition Proposals.” In more recent work on the bargaining set, this condition is relaxed. The reader may consult Davis, Morton and Maschler, Michael, “Existence of Stable Payoff Configurations for Cooperative Games,” in Essays in Mathematical Economics in Honor of Oskar Morgenstern, ed. Shubik, Martin (Princeton: Princeton University Press, 1967), pp. 39–52 CrossRefGoogle Scholar; and Peleg, Bazalel, “Existence Theorem for the Bargaining Set M i 4),” in Essays in Mathematical Economics, ed. Shubik, , pp. 53–56 Google Scholar.

26 Riker, , Theory of Political Coalitions, pp. 102–103 Google Scholar.

27 See, for example, Luce and Raiffa, Games and Decisions, chap. 9.

28 The demonstration to follow has been heavily influenced by the literature on the bargaining set. However, inasmuch as there are several important differences between my analysis and those listed above (one of which is alluded to in note 25), existence results pertaining to the bargaining set may not apply here. In this paper I do not examine existence problems.

29 Recall the distinction made in note 25 between an a.p.c. and a c.r.p.c. The former is defined by (5.2), the latter by (5.2′).

30 The collection of efficacious payoff configurations is very similar to the bargaining set. Indeed, the “objection” and “counterobjection” terms come directly from that literature. There is, however, an important difference (in addition to the one mentioned in note 25). In the bargaining set literature, the objector s and the objectee t must belong to the same Kt ∈K. This requirement is not imposed here.

31 By 25− l mean slightly less than 25, and similarly for —20+. Also y is an undetermined parameter in the closed interval [–20, –10].

32 It must be assumed throughout that payoffs are completely divisible.

33 On quota games, see Shapley, L. S., “Quota Solutions to n-Person Games,” in Contributions to the Theory of Games, II, ed. Kuhn, H. W. and Tucker, A. W. (Princeton: Princeton University Press, 1953), pp. 343–359 Google Scholar. On (n, k) -majority games, see Bott, Raoul, “Symmetric Solutions to Majority Games,” in Contributions to the Theory of Games, II, ed., Kuhn, A. W. and Tucker, A. W. (Princeton: Princeton University Press, 1953), pp. 319–329 Google Scholar, and Gillies, D. B., “Discriminatory and Bargaining Solutions to a Class of Symmetric n-Person Games,” in Contributions to the Theory of Games, II, ed. Kuhn, H. W. and Tucker, A. W. (Princeton: Princeton University Press, 1953), pp. 325–342 Google Scholar. On symmetric, zero-sum games, see Gelbaum, “Symmetric, Zero-Sum, n-Person Games.”

34 In addition to the articles cited in note 25, the reader may consult Maschler, Michael, “Stable Payoff Configurations for Quota Games,” in Advances in Game Theory, ed. Dresher, Melvin, Shapley, L. S., and Tucker, A. W. (Princeton: Princeton University Press, 1964), pp. 477–500 Google Scholar. As well, Wilson's important work on the relationship between stable sets (when they exist) and bargaining sets of various kinds (“Stable Coalition Proposals”) is especially enlightening. In this 1971 paper, Wilson provides several subtle criticisms of the bargaining set as originally formulated by Aumann and Maschler and charts some interesting directions for accommodating these criticisms.

35 For example, little interest has been expressed in the question of coalition structure in non—zero-sum games (although Riker's work is often criticized for his zero-sum assumption). A natural starting place is a consideration of the class of simple games—games in which a coalition is either winning or losing depending on whether its size exceeds some minimal number, k:

See the work of Shapley and von Neumann and Morgenstern cited above for expositions on this class of games.

36 Theory of Games and Economic Behavior, pp. 330–338.

37 Gelbaum, “Symmetric, Zero-Sum, n-Person Games,” pp. 96–100.

38 See Riker, Theory of Political Coalitions, Appendix I. Notice that in case (d) above, the characteristic function may be positively sloped with the size principle still obtaining.

Submit a response

Comments

No Comments have been published for this article.