Editing Cooperative game theory (section)

== Mathematical properties ==
=== Superadditivity ===
Characteristic functions are often assumed to be [[superadditive]] {{harv|Owen|1995|p=213}}. This means that the value of a union of [[disjoint sets|disjoint]] coalitions is no less than the sum of the coalitions' separate values:

<math> v ( S \cup T ) \geq v (S) + v (T) </math> whenever <math> S, T \subseteq N </math> satisfy <math> S \cap T = \emptyset </math>.

=== Monotonicity ===
Larger coalitions gain more:

<math> S \subseteq T \Rightarrow v (S) \le v (T) </math>.

This follows from [[superadditive|superadditivity]]. i.e. if payoffs are normalized so singleton coalitions have zero value.

=== Properties for simple games ===
A coalitional game {{mvar|v}} is considered '''simple''' if payoffs are either 1 or 0, i.e. coalitions are either "winning" or "losing".<ref name="ChalkiadakisElkind2011">{{cite book|author1=Georgios Chalkiadakis|author2=Edith Elkind|author3=Michael J. Wooldridge|title=Computational Aspects of Cooperative Game Theory|url=https://books.google.com/books?id=bN9aC0uabBAC|date=25 October 2011|publisher=Morgan & Claypool Publishers|isbn=978-1-60845-652-9}}</ref>

Equivalently, a '''simple game''' can be defined as a collection {{mvar|W}} of coalitions, where the members of {{mvar|W}} are called '''winning''' coalitions, and the others '''losing''' coalitions.
It is sometimes assumed that a simple game is nonempty or that it does not contain an empty set. However, in other areas of mathematics, simple games are also called [[hypergraph]]s or [[Boolean functions]] (logic functions).

* A simple game {{mvar|W}} is '''monotonic''' if any coalition containing a winning coalition is also winning, that is, if <math>S \in W</math> and <math>S\subseteq T</math> imply <math>T \in W</math>.
* A simple game {{mvar|W}} is '''proper''' if the complement (opposition) of any winning coalition is losing, that is, if <math>S \in W</math> implies <math>N\setminus S \notin W</math>.
* A simple game {{mvar|W}} is '''strong''' if the complement of any losing coalition is winning, that is, if <math>S \notin W</math> implies <math>N\setminus S \in W</math>.
** If a simple game {{mvar|W}} is proper and strong, then  a coalition is winning if and only if its complement is losing, that is, <math>S \in W</math> iff  <math>N\setminus S \notin W</math>. (If {{mvar|v}} is a coalitional simple game that is proper and strong, <math>v(S) = 1 - v(N \setminus S)</math> for any {{mvar|S}}.)
* A '''veto player''' (vetoer) in a simple game is a player that belongs to all winning coalitions. Supposing there is a veto player, any coalition not containing a veto player is losing.  A simple game {{mvar|W}} is '''weak''' (''collegial'') if it has a veto player, that is, if the intersection <math>\bigcap W := \bigcap_{S\in W} S</math> of all winning coalitions is nonempty.
** A '''dictator''' in a simple game is a veto player such that any coalition containing this player is winning.  The dictator does not belong to any losing coalition. ([[Dictator game]]s in experimental economics are unrelated to this.)
* A '''carrier'''  of a simple game {{mvar|W}} is a set <math>T \subseteq N</math> such that for any coalition {{mvar|S}}, we have <math>S \in W</math> iff <math>S\cap T \in W</math>.  When a simple game has a carrier, any player not belonging to it is ignored.  A simple game is sometimes called ''finite'' if it has a finite carrier (even if {{mvar|N}} is infinite).
* The '''[[Nakamura number]]''' of a simple game is the minimal number of ''winning coalitions'' with empty intersection.  According to Nakamura's theorem, the number measures the degree of rationality; it is an indicator of the extent to which an aggregation rule can yield well-defined choices.

A few relations among the above axioms have widely been recognized, such as the following
(e.g., Peleg, 2002, Section 2.1<ref name=peleg02hbscw>{{Cite book | last1 = Peleg | first1 = B. | chapter = Chapter 8 Game-theoretic analysis of voting in committees | doi = 10.1016/S1574-0110(02)80012-1 | title = Handbook of Social Choice and Welfare Volume 1 | volume = 1 | pages = 395–423 | year = 2002 | isbn = 9780444829146 }}</ref>):

* If a simple game is weak, it is proper.
* A simple game is dictatorial if and only if it is strong and weak.

More generally, a complete investigation of the relation among the four conventional axioms
(monotonicity, properness, strongness, and non-weakness), finiteness, and algorithmic computability<ref>See
[[Rice's theorem#An analogue of Rice's theorem for recursive sets|a section for Rice's theorem]]
for the definition of a computable simple game.  In particular, all finite games are computable.</ref>
has been made (Kumabe and Mihara, 2011<ref name=kumabe-m11jme>{{Cite journal | last1 = Kumabe | first1 = M. | last2 = Mihara | first2 = H. R. | doi = 10.1016/j.jmateco.2010.12.003 | title = Computability of simple games: A complete investigation of the sixty-four possibilities | journal = Journal of Mathematical Economics | volume = 47 | issue = 2 | pages = 150–158 | year = 2011 | url = http://mpra.ub.uni-muenchen.de/29000/1/MPRA_paper_29000.pdf| arxiv = 1102.4037 | bibcode = 2011arXiv1102.4037K | s2cid = 775278 }}</ref>),
whose results are summarized in the Table "Existence of Simple Games" below.

{| class="wikitable"
|+ Existence of Simple Games<ref>Modified from Table 1 in Kumabe and Mihara (2011).
The sixteen types are defined by the four conventional axioms (monotonicity, properness, strongness, and non-weakness).
For example, type {{mono|1110}} indicates monotonic (1), proper (1), strong (1), weak (0, because not nonweak) games.
Among type {{mono|1110}} games,  there exist no finite non-computable ones, there exist finite computable ones, there exist no infinite non-computable ones, and there exist no infinite computable ones.
Observe that except for type {{mono|1110}}, the last three columns are identical.
</ref>
|-
! Type
! Finite Non-comp
! Finite Computable
! Infinite Non-comp
! Infinite Computable
|-
| {{mono|1111}}
| {{no}}
| {{yes}}
| {{yes}}
| {{yes}}
|-
| {{mono|1110}}
| {{no}}
| {{yes}}
| {{no}}
| {{no}}
|-
| {{mono|1101}}
| {{no}}
| {{yes}}
| {{yes}}
| {{yes}}
|-
| {{mono|1100}}
| {{no}}
| {{yes}}
| {{yes}}
| {{yes}}
|-
| {{mono|1011}}
| {{no}}
| {{yes}}
| {{yes}}
| {{yes}}
|-
| {{mono|1010}}
| {{no}}
| {{no}}
| {{no}}
| {{no}}
|-
| {{mono|1001}}
| {{no}}
| {{yes}}
| {{yes}}
| {{yes}}
|-
| {{mono|1000}}
| {{no}}
| {{no}}
| {{no}}
| {{no}}
|-
| {{mono|0111}}
| {{no}}
| {{yes}}
| {{yes}}
| {{yes}}
|-
| {{mono|0110}}
| {{no}}
| {{no}}
| {{no}}
| {{no}}
|-
| {{mono|0101}}
| {{no}}
| {{yes}}
| {{yes}}
| {{yes}}
|-
| {{mono|0100}}
| {{no}}
| {{yes}}
| {{yes}}
| {{yes}}
|-
| {{mono|0011}}
| {{no}}
| {{yes}}
| {{yes}}
| {{yes}}
|-
| {{mono|0010}}
| {{no}}
| {{no}}
| {{no}}
| {{no}}
|-
| {{mono|0001}}
| {{no}}
| {{yes}}
| {{yes}}
| {{yes}}
|-
| {{mono|0000}}
| {{no}}
| {{no}}
| {{no}}
| {{no}}
|}

The restrictions that various axioms for simple games impose on their [[Nakamura number]] were also studied extensively.<ref name= kumabe-m08scw>{{Cite journal | last1 = Kumabe | first1 = M. | last2 = Mihara | first2 = H. R. | title = The Nakamura numbers for computable simple games| journal = Social Choice and Welfare | volume = 31 | issue = 4 | page = 621 | year = 2008 | doi = 10.1007/s00355-008-0300-5 | url=http://econpapers.repec.org/paper/pramprapa/3684.htm| arxiv = 1107.0439 | s2cid = 8106333 }}</ref>
In particular, a computable simple game without a veto player has a Nakamura number greater than 3 only if it is a ''proper'' and ''non-strong'' game.