1
$\begingroup$

Context: I would like to know how likely a player is to pick a specific action, provided that he plays optimally and the action is optimal. Phrased like this, the question is ill-defined. But is there some way around the problem?

Details: I have a zero-sum symmetric matrix game. Is there some good notion of a Nash equilibrium with a maximum support [edit: maximum among the NE strategies]? Like something along the lines of "take the center of the simplex of NE strategies"?

The question: Is there some canonical solution to the vague question above? Possibly something already written down in a textbook or a paper. (It would feel silly to reinvent the wheel.)

$\endgroup$
0
$\begingroup$

I am assuming that in the game you are considering there are multiple Nash equilibria and you want to select the most likely equilibria among them. If you are restricting attention to zero-sum games, I am not sure why this is a problem, the min-max value is unique (if you allow for mixed strategies), so all equilibria must be outcome-equivalent.

If your game was not a zero-sum game, you probably want to look at the notions of risk dominance or payoff dominance. The first one selects the less risky NE by entertaining the idea that other players might not be playing the strategy they should according to NE, while the second one selects the NE that is Pareto dominant. To some extent, if there is a NE that makes all of the players better off, it could be argued that it is the most likely equilibrium to arise.

$\endgroup$
  • $\begingroup$ The focus was on zero-sum games. However, the purpose wasn't to find the optimal strategy or the value of the game. Rather, I have some specific action a (which I assume to in the support of some NE), and I wanted to know how likely am I to see players taking a, conditioning on them playing some (possibly different) NE strategy. (The motivating problem being "I know nothing about this agent except that he is optimal. How likely is he to exhibit behavior X?") But thank you anyway, the lack of an definitive answer is some evidence towards this not having a canonical solution yet. $\endgroup$ – Vojtěch Kovařík Jul 9 at 10:11
  • $\begingroup$ Ah, I think that you are assuming that you have a set of actions, that are played with strictly positive probability in some NE, and you are interested in finding the likelihood of observing one of these actions, call it $x_0$, given that you don't know which equilibrium are players coordinating on. In that case, you would need to somehow figure out, or attribute a likelihood for each equilibrium to occur. The only models of that kind that I know are population games, where you can consider multiple initial conditions on the actions of players that are small and move sequentially. $\endgroup$ – Regio Jul 9 at 17:22
  • $\begingroup$ In the limit a Nash equilibrium is reached (under general conditions), and since different initial conditions lead to different NE, you can compute a likelihood, by calculating the ratio of initial conditions that lead to some NE over the total number of initial conditions. $\endgroup$ – Regio Jul 9 at 17:24
  • $\begingroup$ Right, that seems to be the right approach in general (for general-sum games). Thanks for the tip! For zero-sum games, this might get even easier, since Nash equilibria have the mixing property there (any NE strategy is a best response to any other NE strategy). So in these games, you just need to fix a prior over the NE strategies. And with uniform prior is just equivalent to the center of the NE simplex. $\endgroup$ – Vojtěch Kovařík Jul 10 at 22:36
0
$\begingroup$

I am not sure about what exactly you mean by the maximum support NE but you may want to check the concept of Correlated Equilibrium. Any convex combination of NE payoff profiles is a Correlated Equilibrium (but not vice versa in general). So, what you wrote made me think about that. However, I don't think it makes much sense to use correlated equilibrium since, you know, there is no obvious advantage of correlation. Also, the NE payoff profile must be constant in your environment.

Another thing that comes to mind is restricting the attention to super-modular games. Then, you get a nice lattice of NE. So, I don't know if this makes sense either.

I would suggest playing around with some examples to understand what exactly it is that you want to characterize and asking a new one based on your examples.

$\endgroup$
  • $\begingroup$ "Any convex combination of NE payoff profiles is a Correlated Equilibrium" Both players cooperating in a one-shot prisoner's dilemma is not a Correlated Equilibrium. $\endgroup$ – Giskard Jul 8 at 10:25
  • $\begingroup$ Neither is it a convex combination of NE payoff profiles in that game, since the only NE in the one-shot prisoner's dilemma is playing the dominant strategies. So what was your point? What I said was a very simple fact. (Of course, I meant "correlated equilibrium payoff profile" in that sentence.) The set of correlated equilibrium payoffs is convex and for each NE, you can construct a corresponding CE with the same payoff profile. Hence, for each convex combination of of NE payoff profiles, there is a CE with that payoff profile. $\endgroup$ – econman Jul 8 at 11:40
  • $\begingroup$ My mistake, I missed the letters "NE". Sorry. You are right, and if you make any edit I will also remove my downvote. $\endgroup$ – Giskard Jul 8 at 18:52
  • 1
    $\begingroup$ No problem, it happens! $\endgroup$ – econman Jul 9 at 1:14
0
$\begingroup$

It seems that maximum-entropy Nash equilibrium is a relevant concept here. Or more generally, the question becomes well-defined once you fix a prior over all NE strategies, with the uniform prior (probably) being equivalent to the center of the NE simplex.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.