<p>Note that this mixed strategy profile does not need to be a Nash equilibrium. I'm mostly looking for references, as I assume the answer is known, but my searches have only found results about Nash equilibria.</p>
<p>I'm interested in both deciding whether the given payoff profile can be achieved exactly, as well as a profile that weakly) Pareto improves on the given profile can be achieved. Also, I'm interested in both the 2-player case and the n-player case.</p>

CC BY-SA 4.0
2024-10-09T08:27:48.840Z
I know that for 2 players, the problems can be reduced to checking the feasibility of a bilinear program (with equality or inequality constraints, respectively). Are they also complete for that problem? And if so, what is the complexity?
Lisa Henderson
CC BY-SA 4.0
2024-10-10T18:58:27.757Z
Given, say, a zero-sum 2-player matrix game with payoff matrix $M$, can you say explicitly what you mean by mixed strategy "profile" and the "payoff vector" achieved by it?  I expected a profile to be a pair of mixed strategies $x$ and $y$, one for each player, but such a pair naturally induces a payoff value $xM y^T$, not a vector.   On the other hand, it also induces a pair of vectors that could be called payoff vectors $xM$ and $M y^T$, but it would be odd to formulate the question this way because it would decouple into two linear programs (one for $xM$ and one for $My^T$).
Neal Young
CC BY-SA 4.0
2024-10-11T22:11:54.660Z
@Neal I'm interested in general sum games, not zero sum games. So in the two player case, we have a pair of payoff matrices $M_1, M_2$. 

As you say, a strategy profile is a pair of mixed strategies, say $x, y$, and this pair induces a payoff profile $(xM_1 y^T, xM_2 y^T)$
Lisa Henderson
CC BY-SA 4.0
2024-10-11T22:19:54.070Z
By the way, I think the decision problem should be easy for zero sum games because [according to this answer](https://cstheory.stackexchange.com/a/19858) one can decide whether a single quadratic polynomial has real roots efficiently.
Lisa Henderson
<cc.complexity-theory><np-hardness><optimization><time-complexity><gt.game-theory>
Complexity of deciding whether a given payoff vector can be achieved by some mixed strategy profile in a normal form game
Lisa Henderson
# Complexity of deciding whether a given payoff vector can be achieved by some mixed strategy profile in a normal form game

(Asked by: username_0 on 2024-10-09)

Note that this mixed strategy profile does not need to be a Nash equilibrium. I'm mostly looking for references, as I assume the answer is known, but my searches have only found results about Nash equilibria.

I'm interested in both deciding whether the given payoff profile can be achieved exactly, as well as a profile that weakly) Pareto improves on the given profile can be achieved. Also, I'm interested in both the 2-player case and the n-player case.

**Tags:** cc.complexity-theory, np-hardness, optimization, time-complexity, gt.game-theory
> **Comments:**
> **username_0**: I know that for 2 players, the problems can be reduced to checking the feasibility of a bilinear program (with equality or inequality constraints, respectively). Are they also complete for that problem? And if so, what is the complexity?  
> **username_1**: Given, say, a zero-sum 2-player matrix game with payoff matrix $M$, can you say explicitly what you mean by mixed strategy "profile" and the "payoff vector" achieved by it?  I expected a profile to be a pair of mixed strategies $x$ and $y$, one for each player, but such a pair naturally induces a payoff value $xM y^T$, not a vector.   On the other hand, it also induces a pair of vectors that could be called payoff vectors $xM$ and $M y^T$, but it would be odd to formulate the question this way because it would decouple into two linear programs (one for $xM$ and one for $My^T$).  
> **username_0**: @Neal I'm interested in general sum games, not zero sum games. So in the two player case, we have a pair of payoff matrices $M_1, M_2$.   As you say, a strategy profile is a pair of mixed strategies, say $x, y$, and this pair induces a payoff profile $(xM_1 y^T, xM_2 y^T)$  
> **username_0**: By the way, I think the decision problem should be easy for zero sum games because [according to this answer](https://cstheory.stackexchange.com/a/19858) one can decide whether a single quadratic polynomial has real roots efficiently.  

---

## 0 answers

