Extra uitleg (film)

Stelling: Laat $(N,v)$ een coöperatief spel zijn. Dan geldt $$I(v)\neq\emptyset \Leftrightarrow v(N)\geq \sum_{i \in N} v(\{i\}).$$

Bewijs: Merk op dat de stelling in feite uit twee beweringen bestaat. De eerste bewering is dat als de imputatieverzameling van een spel $(N,v)$ niet leeg is, dan geldt dat $v(N)\geq v(\{1\})+v(\{2\})+\ldots+v(\{n\})$. De tweede bewering is dat als voor een spel $(N,v)$ geldt dat $v(N)\geq v(\{1\})+v(\{2\})+\ldots+v(\{n\})$ dan geldt $I(v)\neq\emptyset$.

We beginnen met het bewijs van de eerste bewering. Laat $(N,v)$ een spel zijn zodanig dat $I(v)\neq\emptyset$. Er bestaat dus een verdeling $x=(x_1,x_2,\ldots,x_n)$ waarvoor geldt dat
$$x_1+x_2+\ldots+x_n=v(N)$$
en voor elke speler $i\in N$ geldt dat
$$x_i\geq v(\{i\}).$$
Combineren we deze gelijkheid en ongelijkheden dan volgt dat
$$\begin{align} v(N)=&x_1+x_2+\ldots+x_n\\ \geq& v(\{1\})+v(\{2\})+\ldots+v(\{n\}), \end{align}$$
wat de eerste bewering bewijst.

We bewijzen nu de tweede bewering. Laat $(N,v)$ een spel zijn zodanig dat $v(N)\geq v(\{1\})+v(\{2\})+\ldots+v(\{n\})$. We bewijzen dat de verdeling $$x=\Big(v(\{1\}),v(\{2\}),\ldots,v(\{n-1\}),v(N)-v(\{1\})-v(\{2\})-\ldots-v(\{n-1\})\Big)$$
in de imputatieverzameling ligt. Merk op dat $$x_1+x_2+\ldots+x_n=v(N),$$
en $$x_i\geq v(\{i\})$$ voor alle $i=1,\ldots,n-1$. We moeten nog bewijzen dat $x_n\geq v(\{n\})$. Maar uit de aanname $$v(N)\geq v(\{1\})+v(\{2\})+\ldots+v(\{n\})$$ volgt door herschrijven
$$v(N)-v(\{1\})-v(\{2\})-\ldots-v(\{n-1\})\geq v(\{n\}),$$ wat precies aantoont dat $x_n\geq v(\{n\})$.