In cooperative game theory and social choice theory, the Nakamura number measures the degree of rationality of preference aggregation rules (collective decision rules), such as voting rules. It is an indicator of the extent to which an aggregation rule can yield well-defined choices.

  • If the number of alternatives (candidates; options) to choose from is less than this number, then the rule in question will identify "best" alternatives without any problem.

In contrast,

  • if the number of alternatives is greater than or equal to this number, the rule will fail to identify "best" alternatives for some pattern of voting (i.e., for some profile (tuple) of individual preferences), because a voting paradox will arise (a cycle generated such as alternative socially preferred to alternative , to , and to ).

The larger the Nakamura number a rule has, the greater the number of alternatives the rule can rationally deal with. For example, since (except in the case of four individuals (voters)) the Nakamura number of majority rule is three, the rule can deal with up to two alternatives rationally (without causing a paradox). The number is named after Kenjiro Nakamura [ja] (1947–1979), a Japanese game theorist who proved the above fact that the rationality of collective choice critically depends on the number of alternatives.[1]

Overview

edit

To introduce a precise definition of the Nakamura number, we give an example of a "game" (underlying the rule in question) to which a Nakamura number will be assigned. Suppose the set of individuals consists of individuals 1, 2, 3, 4, and 5. Behind majority rule is the following collection of ("decisive") coalitions (subsets of individuals) having at least three members:

{ {1,2,3}, {1,2,4}, {1,2,5}, {1,3,4}, {1,3,5}, {1,4,5}, {2,3,4}, {2,3,5}, {2,4,5}, {3,4,5}, {1,2,3,4}, {1,2,3,5}, {1,2,4,5}, {1,3,4,5}, {2,3,4,5}, {1,2,3,4,5} }

A Nakamura number can be assigned to such collections, which we call simple games. More precisely, a simple game is just an arbitrary collection of coalitions; the coalitions belonging to the collection are said to be winning; the others losing. If all the (at least three, in the example above) members of a winning coalition prefer alternative x to alternative y, then the society (of five individuals, in the example above) will adopt the same ranking (social preference).

The Nakamura number of a simple game is defined as the minimum number of winning coalitions with empty intersection. (By intersecting this number of winning coalitions, one can sometimes obtain an empty set. But by intersecting less than this number, one can never obtain an empty set.) The Nakamura number of the simple game above is three, for example, since the intersection of any two winning coalitions contains at least one individual but the intersection of the following three winning coalitions is empty:  ,  ,  .

Nakamura's theorem (1979[2]) gives the following necessary (also sufficient if the set of alternatives is finite) condition for a simple game to have a nonempty "core" (the set of socially "best" alternatives) for all profiles of individual preferences: the number of alternatives is less than the Nakamura number of the simple game. Here, the core of a simple game with respect to the profile of preferences is the set of all alternatives   such that there is no alternative   that every individual in a winning coalition prefers to  ; that is, the set of maximal elements of the social preference. For the majority game example above, the theorem implies that the core will be empty (no alternative will be deemed "best") for some profile, if there are three or more alternatives.

Variants of Nakamura's theorem exist that provide a condition for the core to be nonempty (i) for all profiles of acyclic preferences; (ii) for all profiles of transitive preferences; and (iii) for all profiles of linear orders. There is a different kind of variant (Kumabe and Mihara, 2011[3]), which dispenses with acyclicity, the weak requirement of rationality. The variant gives a condition for the core to be nonempty for all profiles of preferences that have maximal elements.

For ranking alternatives, there is a very well known result called "Arrow's impossibility theorem" in social choice theory, which points out the difficulty for a group of individuals in ranking three or more alternatives. For choosing from a set of alternatives (instead of ranking them), Nakamura's theorem is more relevant.[5] An interesting question is how large the Nakamura number can be. It has been shown that for a (finite or) algorithmically computable simple game that has no veto player (an individual that belongs to every winning coalition) to have a Nakamura number greater than three, the game has to be non-strong.[6] This means that there is a losing (i.e., not winning) coalition whose complement is also losing. This in turn implies that nonemptyness of the core is assured for a set of three or more alternatives only if the core may contain several alternatives that cannot be strictly ranked.[8]

Framework

edit

Let   be a (finite or infinite) nonempty set of individuals. The subsets of   are called coalitions. A simple game (voting game) is a collection   of coalitions. (Equivalently, it is a coalitional game that assigns either 1 or 0 to each coalition.) We assume that   is nonempty and does not contain an empty set. The coalitions belonging to   are winning; the others are losing. A simple game   is monotonic if   and   imply  . It is proper if   implies  . It is strong if   implies  . A veto player (vetoer) is an individual that belongs to all winning coalitions. A simple game is nonweak if it has no veto player. It is finite if there is a finite set (called a carrier)   such that for all coalitions  , we have   iff  .

Let   be a (finite or infinite) set of alternatives, whose cardinal number (the number of elements)   is at least two. A (strict) preference is an asymmetric relation   on  : if   (read "  is preferred to  "), then  . We say that a preference   is acyclic (does not contain cycles) if for any finite number of alternatives  , whenever  ,  ,…,  , we have  . Note that acyclic relations are asymmetric, hence preferences.

A profile is a list   of individual preferences  . Here   means that individual   prefers alternative   to   at profile  .

A simple game with ordinal preferences is a pair   consisting of a simple game   and a profile  . Given  , a dominance (social preference) relation   is defined on   by   if and only if there is a winning coalition   satisfying   for all  . The core   of   is the set of alternatives undominated by   (the set of maximal elements of   with respect to  ):

  if and only if there is no   such that  .

Definition and examples

edit

The Nakamura number   of a simple game   is the size (cardinal number) of the smallest collection of winning coalitions with empty intersection:[9]

 

if   (no veto player);[2] otherwise,   (greater than any cardinal number).

it is easy to prove that if   is a simple game without a veto player, then  .

Examples for finitely many individuals ( ) (see Austen-Smith and Banks (1999), Lemma 3.2[4]). Let   be a simple game that is monotonic and proper.

  • If   is strong and without a veto player, then  .
  • If   is the majority game (i.e., a coalition is winning if and only if it consists of more than half of individuals), then   if  ;   if  .
  • If   is a  -rule (i.e., a coalition is winning if and only if it consists of at least   individuals) with  , then  , where   is the smallest integer greater than or equal to  .

Examples for at most countably many individuals ( ). Kumabe and Mihara (2008) comprehensively study the restrictions that various properties (monotonicity, properness, strongness, nonweakness, and finiteness) for simple games impose on their Nakamura number (the Table "Possible Nakamura Numbers" below summarizes the results). In particular, they show that an algorithmically computable simple game [10] without a veto player has a Nakamura number greater than 3 only if it is proper and nonstrong.[6]

Possible Nakamura Numbers[11]
Type Finite games Infinite games
1111 3 3
1110 +∞ none
1101 ≥3 ≥3
1100 +∞ +∞
1011 2 2
1010 none none
1001 2 2
1000 none none
0111 2 2
0110 none none
0101 ≥2 ≥2
0100 +∞ +∞
0011 2 2
0010 none none
0001 2 2
0000 none none

Nakamura's theorem for acyclic preferences

edit

Nakamura's theorem (Nakamura, 1979, Theorems 2.3 and 2.5[2]). Let   be a simple game. Then the core   is nonempty for all profiles   of acyclic preferences if and only if   is finite and  .

Remarks

  • Nakamura's theorem is often cited in the following form, without reference to the core (e.g., Austen-Smith and Banks, 1999, Theorem 3.2[4]): The dominance relation   is acyclic for all profiles   of acyclic preferences if and only if   for all finite   (Nakamura 1979, Theorem 3.1[2]).
  • The statement of the theorem remains valid if we replace "for all profiles   of acyclic preferences" by "for all profiles   of negatively transitive preferences" or by "for all profiles   of linearly ordered (i.e., transitive and total) preferences".[12]
  • The theorem can be extended to  -simple games. Here, the collection   of coalitions is an arbitrary Boolean algebra of subsets of  , such as the  -algebra of Lebesgue measurable sets. A  -simple game is a subcollection of  . Profiles are suitably restricted to measurable ones: a profile   is measurable if for all  , we have  .[3]

A variant of Nakamura's theorem for preferences that may contain cycles

edit

In this section, we discard the usual assumption of acyclic preferences. Instead, we restrict preferences to those having a maximal element on a given agenda (opportunity set that a group of individuals are confronted with), a subset of some underlying set of alternatives. (This weak restriction on preferences might be of some interest from the viewpoint of behavioral economics.) Accordingly, it is appropriate to think of   as an agenda here. An alternative   is a maximal element with respect to   (i.e.,   has a maximal element  ) if there is no   such that  . If a preference is acyclic over the underlying set of alternatives, then it has a maximal element on every finite subset  .

We introduce a strengthening of the core before stating the variant of Nakamura's theorem. An alternative   can be in the core   even if there is a winning coalition of individuals   that are "dissatisfied" with   (i.e., each   prefers some   to  ). The following solution excludes such an  :[3]

An alternative   is in the core   without majority dissatisfaction if there is no winning coalition   such that for all  ,   is non-maximal (there exists some   satisfying  ).

It is easy to prove that   depends only on the set of maximal elements of each individual and is included in the union of such sets. Moreover, for each profile  , we have  .

A variant of Nakamura's theorem (Kumabe and Mihara, 2011, Theorem 2[3]). Let   be a simple game. Then the following three statements are equivalent:

  1.  ;
  2. the core   without majority dissatisfaction is nonempty for all profiles   of preferences that have a maximal element;
  3. the core   is nonempty for all profiles   of preferences that have a maximal element.

Remarks

  • Unlike Nakamura's original theorem,   being finite is not a necessary condition for   or   to be nonempty for all profiles  . Even if an agenda   has infinitely many alternatives, there is an element in the cores for appropriate profiles, as long as the inequality   is satisfied.
  • The statement of the theorem remains valid if we replace "for all profiles   of preferences that have a maximal element" in statements 2 and 3 by "for all profiles   of preferences that have exactly one maximal element" or "for all profiles   of linearly ordered preferences that have a maximal element" (Kumabe and Mihara, 2011, Proposition 1).
  • Like Nakamura's theorem for acyclic preferences, this theorem can be extended to  -simple games. The theorem can be extended even further (1 and 2 are equivalent; they imply 3) to collections   of winning sets by extending the notion of the Nakamura number.[13]

See also

edit

Notes

edit
  1. ^ Suzuki, Mitsuo (1981). Game theory and social choice: Selected papers of Kenjiro Nakamura. Keiso Shuppan. Nakamura received Doctor's degree in Social Engineering in 1975 from Tokyo Institute of Technology.
  2. ^ a b c d Nakamura, K. (1979). "The vetoers in a simple game with ordinal preferences". International Journal of Game Theory. 8: 55–61. doi:10.1007/BF01763051. S2CID 120709873.
  3. ^ a b c d Kumabe, M.; Mihara, H. R. (2011). "Preference aggregation theory without acyclicity: the core without majority dissatisfaction" (PDF). Games and Economic Behavior. 72: 187–201. arXiv:1107.0431. doi:10.1016/j.geb.2010.06.008. S2CID 6685306.
  4. ^ a b c d Austen-Smith, David; Banks, Jeffrey S. (1999). Positive political theory I: Collective preference. Ann Arbor: University of Michigan Press. ISBN 978-0-472-08721-1.
  5. ^ Nakamura's original theorem is directly relevant to the class of simple preference aggregation rules, the rules completely described by their family of decisive (winning) coalitions. (Given an aggregation rule, a coalition   is decisive if whenever every individual in   prefers   to  , then so does the society.) Austen-Smith and Banks (1999),[4] a textbook on social choice theory that emphasizes the role of the Nakamura number, extends the Nakamura number to the wider (and empirically important) class of neutral (i.e., the labeling of alternatives does not matter) and monotonic (if   is socially preferred to  , then increasing the support for   over   preserves this social preference) aggregation rules (Theorem 3.3), and obtain a theorem (Theorem 3.4) similar to Nakamua's.
  6. ^ a b Kumabe, M.; Mihara, H. R. (2008). "The Nakamura numbers for computable simple games". Social Choice and Welfare. 31 (4): 621. arXiv:1107.0439. doi:10.1007/s00355-008-0300-5. S2CID 8106333.
  7. ^ Kirman, A.; Sondermann, D. (1972). "Arrow's theorem, many agents, and invisible dictators". Journal of Economic Theory. 5 (2): 267–277. doi:10.1016/0022-0531(72)90106-8.
  8. ^ There exist monotonic, proper, strong simple games without a veto player that have an infinite Nakamura number. A nonprincipal ultrafilter is an example, which can be used to define an aggregation rule (social welfare function) satisfying Arrow's conditions if there are infinitely many individuals.[7] A serious drawback of nonprincipal ultrafilters for this purpose is that they are not algorithmically computable.
  9. ^ The minimum element of the following set exists since every nonempty set of ordinal numbers has a least element.
  10. ^ See a section for Rice's theorem for the definition of a computable simple game. In particular, all finite games are computable.
  11. ^ Possible Nakamura numbers for computable simple games are given in each entry, assuming that an empty coalition is losing. The sixteen types are defined in terms of the four properties: monotonicity, properness, strongness, and nonweakness (lack of a veto player). For example, the row corresponding to type 1110 indicates that among the monotonic (1), proper (1), strong (1), weak (0, because not nonweak) computable simple games, finite ones have a Nakamura number equal to   and infinite ones do not exist. The row corresponding to type 1101 indicates that any   (and no  ) is the Nakamura number of some finite (alternatively, infinite) simple game of this type. Observe that among nonweak simple games, only types 1101 and 0101 attain a Nakamura number greater than 3.
  12. ^ The "if" direction is obvious while the "only if" direction is stronger than the statement of the theorem given above (the proof is essentially the same). These results are often stated in terms of weak preferences (e.g, Austen-Smith and Banks, 1999, Theorem 3.2[4]). Define the weak preference   by  . Then   is asymmetric iff   is complete;   is negatively transitive iff   is transitive.   is total if   implies   or  .
  13. ^ The framework distinguishes the algebra   of coalitions from the larger collection   of the sets of individuals to which winning/losing status can be assigned. For example,   is the algebra of recursive sets and   is the lattice of recursively enumerable sets (Kumabe and Mihara, 2011, Section 4.2).