Nakamura number


In cooperative game theory and social choice theory, the Nakamura number measures the degree of rationality
of preference aggregation rules, such as voting rules.
It is an indicator of the extent to which an aggregation rule can yield well-defined choices.
In contrast,
The larger the Nakamura number a rule has, the greater the number of alternatives the rule can rationally deal with.
For example, since the Nakamura number of majority rule is three,
the rule can deal with up to two alternatives rationally.
The number is named after Kenjiro Nakamura, a Japanese game theorist who proved the above fact
that the rationality of collective choice critically depends on the number of alternatives.

Overview

To introduce a precise definition of the Nakamura number, we give an example of a "game"
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 coalitions having at least three members:
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 members of a winning coalition prefer alternative x to alternative y,
then the society will adopt the same ranking.
The Nakamura number of a simple game is defined as the minimum number of winning coalitions with empty intersection.
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 gives the following necessary condition for a simple game to have a nonempty "core" 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 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
for all profiles of acyclic preferences;
for all profiles of transitive preferences; and
for all profiles of linear orders.
There is a different kind of variant,
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, Nakamura's theorem is more relevant.
An interesting question is how large the Nakamura number can be.
It has been shown that for a algorithmically computable simple game that has no veto player
to have a Nakamura number greater than three, the game has to be non-strong.
This means that there is a losing 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 be a nonempty set of individuals.
The subsets of are called coalitions.
A simple game is a collection of coalitions.
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 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 such that for all coalitions,
we have iff.
Let be a set of alternatives, whose cardinal number
is at least two.
A preference is an asymmetric relation on :
if ,
then.
We say that a preference is acyclic 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 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
:

Definition and examples

The Nakamura number of a simple game is the size
of the smallest collection of winning coalitions with empty intersection:
if ;
otherwise, .
it is easy to prove that if is a simple game without a veto player, then.
Examples for finitely many individuals .
Let be a simple game that is monotonic and proper.
Examples for at most countably many individuals.
Kumabe and Mihara comprehensively study the restrictions that various properties
for simple games
impose on their Nakamura number.
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.
TypeFinite gamesInfinite games
111133
1110+∞none
1101≥3≥3
1100+∞+∞
101122
1010nonenone
100122
1000nonenone
011122
0110nonenone
0101≥2≥2
0100+∞+∞
001122
0010nonenone
000122
0000nonenone

Nakamura's theorem for acyclic preferences

Nakamura's theorem.
Let be a simple game. Then the core is nonempty for all profiles of acyclic preferences if and only if is finite and.
Remarks
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,
a subset of some underlying set of alternatives.
Accordingly, it is appropriate to think of as an agenda here.
An alternative is a maximal element with respect to
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
.
The following solution excludes such an :
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.
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