Here is the paper from chich I previously posted another definition here Definition of a $k-$strong Nash Equilibrium
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."
