# Providing an example in cooperative - games and coalitions

I am trying to construct an example to understand the idea of the following definitions of the game of Heller in 2005 paper.

Consider a game $$G=(N, (A^i)_{i\in N}, (g^i)_{i\in N})$$, $$N=\{1,2,\dots,n\}$$, $$A=\Pi_{i\in N}A_i$$ is the set of actions and $$g^i:A\to \mathbb{R}$$ is the payoff function. The latter can be extended from $$\Delta(A)$$, which is the set of (correlated) strategies, to the real line. If $$S$$ is a calition, it is a non-empty member of $$2^N$$ and $$A^S=\Pi_{i\in S}A^i$$ is the actions set of the memebers of the coalition where a memeber of $$\Delta(A^S)$$ is called an $$S-$$strategy profile. Also, $$-S$$ denoted the complementary coalition. Suppose that $$U$$ is the set of uncorrelated strategy profiles and $$U^S$$ the set of the uncorrelated $$S$$-strategy profiles .Given $$q\in U$$, we write $$q = (q^S , q^{−S})$$ where: $$q^S\in U^S$$ , $$q^{−S} \in U^{−S}$$.

$$\textbf{Definition 1:}$$ An uncorrelated strategy profile $$q\in U$$ is a $$k$$-strong Nash equilibrium if and only if for all coalitions $$S\subset N$$ satisfying $$|S|\leq k$$ and for every uncorrelated $$S$$-strategy profile $$p^S \in U^S$$, there exists a player $$i \in S$$ such that

$$g^i(q)=g^i(q^S,q^{-S})\geq g^i(p^S,q^{-S})$$

$$\textbf{Definition 2:}$$ Given a coalition $$S\subseteq N$$, we define an $$S$$-deviation scheme as a function $$d^s:A^s\to\Delta(A^s)$$. Given a strategy profile $$q$$, we say that $$p\in\Delta(A)$$ is an $$S$$-deviation from the strategy profile $$q$$, if there exists a deviating scheme $$d^s$$ s.t for all $$a\in A$$, we have that $$p(a)=\sum_{b^s\in A^s}q(b^s,a^{-s})\dot d^s(a^s|b^s)$$. Let $$D(q,S)$$ denote set of all deviations from $$q$$.

$$\textbf{Defintion 3:}$$ A profile $$q\in \Delta(A)$$ is a $$k$$-strong correlated equilibrium if and only if for every coalition $$S\subseteq N$$ satisfying $$|S|\leq k$$, and for every $$S$$-deviation of $$p\in D(q,S)$$, there is a player $$i\in S$$ s.t. $$g^i(q)\geq g^i(p)$$.

So, considering the above I am trying to understand the intuition of the above definitions and I want to conscruct an example that is intuitive, if anyone could help me. The exampe is the following:

Suppose that $$|N|=4$$ and $$A=\underbrace{\{x_1,x_2,x_3,x_4\}}_{A_1}\times \underbrace{\{y_1,y_2,y_3,y_4\}}_{A^2}\times \underbrace{\{u_1,u_2,u_3,u_4\}}_{A^3} \times \underbrace{\{z_1,z_2,z_3,z_4\}}_{A^4}$$ or

$$A=\{(x_1,y_1,u_1,z_1),(x_1,y_1,u_1,z_2),(x_1,y_1,u_2,z_1),(x_1,y_1,u_2,z_2),(x_1,y_2,u_1,z_1),(x_1,y_2,u_2,z_1),(x_1,y_2,u_1,z_2),(x_1,y_2,u_2,z_2),(x_2,y_1,u_1,z_1),(x_2,y_1,u_1,z_2),(x_2,y_1,u_2,z_1),(x_2,y_1,u_2,z_2),(x_2,y_2,u_1,z_1),(x_2,y_2,u_2,z_1),(x_2,y_2,u_1,z_2),(x_2,y_2,u_2,z_2)\}$$

and say that the coalition has 2 memebers, $$|S|=2$$, however the combinations can be whatever, namely a coalition between player $$1$$ and $$2$$, or player $$1$$ and $$3$$ or player $$1$$ and $$4$$ ans so on.

And let us assume that a correlated strategy $$q$$ that exists in the set $$\Delta(A)$$ and it is given, in its most generalized formulation as below

$$q=\left\{q(w^i),\quad i=\{1,2,\dots,16\}\big{\vert} \quad \sum_{i=1}^{16}q(w^i)=1\right\}$$

where for example $$w^1=(x_1,y_1,u_1,z_1)$$, $$w^2=(x_1,y_1,u_1,z_2)$$ and so on.

$$\textbf{Question:}$$ Can anyone with the help of the above, provide an example of

• an uncorrelated 2-strong Nash Equilibrium (because for us $$|S|=2$$)?
• an $$S$$-deviation scheme (2-players coalition again)?
• a k-strong correlated equilibrium (recall again 2-players coalition to simplify the example)?
• Is the following sentence true or false and why? can we also provide an exapmle? Either $$q$$ is a correlated equilibrium or not, there is always a coalition, this means that correlation and coalition do not have the same meaning and the players within a coalition can form a coalition without necessarily correlate their strategies."