Well-known results in complexity theory have suggested that discovering (or even approximating) a NE in general games is computationally hard [1]}, [2]}, [3]}. As a result, researchers often also consider the correlated equilibrium (CE) [4]}, an alternative solution concept which is efficiently computable in all normal-form games. Whereas a NE is a probability distribution over actions \(A_i\)  for each player \(i\) , a CE is a probability distribution \(p\)  over the set of joint actions \(A\)  that satisfies certain incentive constraints. In order for a probability distribution over joint actions to be a CE, it must be the case that if a mediator were to sample a joint action \(a\)  from that distribution and privately share with each player \(i\)  their action \(a_i\)  that is part of the joint action, then no player could gain by deviating from that action. Formally, a CE is a probability distribution over joint actions in \(A\)  satisfying
\(\max _{i \in \mathcal {P}} \max _{\phi : A_i \rightarrow A_i} \sum _{a \in A} p(a) (u_i(\phi (a_i), a_{-i}) - u_i(a_i, a_{-i})) \le 0\) 
