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


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."


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.