Nakamura number

Overview

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: { 1 , 2 , 3 } , { 4 , 5 , 1 } , { 2 , 3 , 4 } .

Nakamura's theorem (1979) 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 x such that there is no alternative y that every individual in a winning coalition prefers to x ; 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), 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. 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. 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.

Framework

Let N be a (finite or infinite) nonempty set of individuals. The subsets of N are called coalitions. A simple game (voting game) is a collection W of coalitions. (Equivalently, it is a coalitional game that assigns either 1 or 0 to each coalition.) We assume that W is nonempty and does not contain an empty set. The coalitions belonging to W are winning; the others are losing. A simple game W is monotonic if S ∈ W and S ⊆ T imply T ∈ W . It is proper if S ∈ W implies N ∖ S ∉ W . It is strong if S ∉ W imples N ∖ S ∈ W . 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) T ⊆ N such that for all coalitions S , we have S ∈ W iff S ∩ T ∈ W .

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

A profile is a list p = ( ≻ i p ) i ∈ N of individual preferences ≻ i p . Here x ≻ i p y means that individual i prefers alternative x to y at profile p .

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

x ∈ C ( W , p ) if and only if there is no y ∈ X such that y ≻ W p x .

The Nakamura number: the definition and examples

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

ν ( W ) = min { # W ′ : W ′ ⊆ W ; ∩ W ′ = ∅ }

if ∩ W = ∩ S ∈ W S = ∅ (no veto player); otherwise, ν ( W ) = + ∞ (greater than any cardinal number).

it is easy to prove that if W is a simple game without a veto player, then 2 ≤ ν ( W ) ≤ # N .

Examples for finitely many individuals ( N = { 1 , … , n } ) (see Austen-Smith and Banks (1999), Lemma 3.2). Let W be a simple game that is monotonic and proper.

If W is strong and without a veto player, then ν ( W ) = 3 .

If W is the majority game (i.e., a coalition is winning if and only if it consists of more than half of individuals), then ν ( W ) = 3 if n ≠ 4 ; ν ( W ) = 4 if n = 4 .

If W is a q -rule (i.e., a coalition is winning if and only if it consists of at least q individuals) with n / 2 < q < n , then ν ( W ) = [ n / ( n − q ) ] , where [ x ] is the smallest integer greater than or equal to x .

Examples for at most countably many individuals ( N = { 1 , 2 , … } ). 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 without a veto player has a Nakamura number greater than 3 only if it is proper and nonstrong.