A supermodular game is superadditive. But is a superadditive game is supermodular?

557 Views Asked by At

I came across a presentation by Mohammad T. Hajiaghayi from University of Maryland, where he talks about Coalition Game Theory, and he states that "every super-additive game is a convex game". He also states that, $ \lbrace \text{Additive games} \rbrace \subseteq \lbrace \text{Super-additive games} \rbrace \subseteq \lbrace \text{Convex games} \rbrace $. Now I don't quite get it. Where I can easily prove that a convex or supermodular game is super-additive, I can't prove the converse.

Definitions:

A game $G = (N, v)$ with $v(\varnothing) = 0$ is convex (supermodular) if for all $S,T \subseteq N$,

$$v(S \cup T) + v(S \cap T) \geq v(S) + v(T)$$

Also is a superadditive game if for all $S,T \subseteq N$, if $S \cap T = \varnothing$,

$$v (S \cup T) \geq v (S) + v (T)$$

1

There are 1 best solutions below

1
On BEST ANSWER

As Holger I. Meinhardt points out in a comment, the inclusion is wrong. For $v$ with $v(\emptyset)=0,$ super-modularity obviously implies super-additivity, but the reverse is not true. An explicit counterexample is the symmetric function on the powerset of $\{1,2,3\}$ with $$v(S)=\begin{cases} 0&\text{ if $|S|=0$}\\ 1&\text{ if $|S|=1$}\\ 3&\text{ if $|S|=2$}\\ 4&\text{ if $|S|=3.$}\\ \end{cases}$$

This is super-additive but it isn't super-modular: taking $S=\{1,2\}$ and $T=\{2,3\}$ we have $v(S\cup T)+v(S\cap T)=5<6=v(S)+V(T).$

If we don't require $v(\emptyset)=0$ then super-modularity does not imply super-additivity; for example taking $v(S)=1$ for all $S$ we find $v(\{1,2\})<v(\{1\})+v(\{2\}).$