1
$\begingroup$

Consider a general-sum game with $N$ players. Let $u_i(a_1, \ldots, a_N)\colon \prod_{i=1}^N A_i \rightarrow \mathbb{R} $ be the payoff of the player $i\in \{ 1, \ldots, N \}$ when each player takes action $a_i \in A_i$, where $A_i $ is the action set of player $i$. Let $\sigma^*$ be any notion of correlated equilibrium (CE) that is computable and unique. For example, the social optimal correlated equilibrium or max-entropy correlated equilibrium, both can be solved efficiently using linear programming. Thus, $\sigma^*$ is a probability measure on the joint action space $\prod_{i=1}^N A_i$. Then the expected payoff of player $i$ is $$ V_i( u_1, \ldots, u_N) = \mathbb{E}_{(a_1, \ldots, a_N) \sim \sigma^*} \bigl [ u_i(a_1, \ldots a_n) \bigr ] \\ = \sum_{(a_1, \ldots, a_N)\in \prod_{i=1}^N A_i} u_i(a_1, \ldots a_n) \cdot \sigma^* (a_1, \ldots a_n). $$ Note that the value of game at a social optimal CE or a max-entropy CE is unique. I was wondering whether the values of the game $( V_1, \ldots, V_N)\in \mathbb{R}^N$ is Lipschitz with respect to the utility functions. That is, suppose we have two sets of utility functions $\{ u_i \}_{i=1}^N $ and $\{\tilde u_i \}_{i=1}^N $ and we solve for the same kind of CE on both games. Is it possible to show that $$ \max_{i\in \{1, \ldots, N \} } \bigl | V_i ( u_1, \ldots, u_N) - V_i(\tilde u_1, \ldots, \tilde u_N) \bigr | \leq C \cdot \max_{j\in \{1,\ldots, N\} } \| u_j - \tilde u_j \|_{\infty} $$ for some constant $C$?

P.S.: For zero-sum games, it seems that we can show this with $C = 1$.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
2
$\begingroup$

Consider the following 2x2 two player game \begin{array}{c|c} 1,1 & 0,1 \\ \hline 1,0 & 0,0 \end{array} In this game, all strategy profiles are Nash equilibria, and consequently every point in the unit square is an equilibrium payoff (and a correlated equilibrium payoff). Take now the following perturbation of this game (for positive $\epsilon$) \begin{array}{c|c} 1+\epsilon,1+\epsilon & \epsilon,1 \\ \hline 1,\epsilon & 0,0 \end{array} In this game each player has a dominant strategy, hence the unique correlated equilibrium payoff is $(1+\epsilon,1+\epsilon)$. Take the same game with negative $\epsilon$. The unique correlated equilibrium payoff is (0,0). Does this example answer you question?

Regarding zero-sum games: in a zero-sum game, the unique correlated equilibrium payoff coincides with the value. Since the value is 1-Liphschitz in the maximum norm, then the answer to your question is positive (for zero-sum games).

Improve this answer
$\endgroup$
2
  • $\begingroup$ Thanks very much for your answer. For the perturbed game you constructed, it seems that the value of the game can change drastically. However, it seems that the CE of the game is rather stable in the sense that the CE of a game $G$ is the $\epsilon$-approximate CE of the $\epsilon$-perturbed game of $G$. In particular, any strategy profile is an $\epsilon$-CE of the game you constructed, because adopting the alternative strategy unilaterally at most hurts the payoff by $\epsilon$. $\endgroup$
    – Steve
    Dec 5, 2019 at 6:11
  • $\begingroup$ The set valued function that assigns to each strategic-form game its set of correlated equilibrium payoffs is upper semi continuous. This is what you refer to in your last response. But this was not what you asked at first. There you asked whether this set valued function is continuous in some proper way, and the answer is negative as the example above shows: for $\epsilon < 0$, the unique correlated equilibrium payoff is (0,0), while for $\epsilon > 0$, the unique equilibrium payoff is $(1+\epsilon,1+\epsilon)$. I probably do not fully understand your question. $\endgroup$
    – Eilon
    Dec 6, 2019 at 7:47

Your Answer

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