Skip to main content
MathOverflow

Return to Question

added 212 characters in body
Source Link
charles.y.zheng
charles.y.zheng
  • 241
  • 1
  • 4

For square matrix $P$, define

$$V(P) = \sup_x \inf_y x^T P y^T$$

where $x$ and $y$ lie on the unit $n-1$-simplex.

($P$ is a payoff matrix for a symmetric game, $x$ and $y$ are mixed strategies, and $V$ is the value of the game.)

It is known that determining $V(P)$ is NP-hard. However, is there some way to bound $V(P)$ by differentiable functions of the elements of $P$? If I am not mistaken, $V$ is monotonic in each element of $P$.

EDIT: The reason I want differentiable approximations for $V(P)$ is because I am interested in solving a system of equations

$p_1 = V(P_1), p_2 = V(P_2), ...$

where each $P_i$ depends on $p_1, p_2, ...$

For square matrix $P$, define

$$V(P) = \sup_x \inf_y x^T P y^T$$

where $x$ and $y$ lie on the unit $n-1$-simplex.

($P$ is a payoff matrix for a symmetric game, $x$ and $y$ are mixed strategies, and $V$ is the value of the game.)

It is known that determining $V(P)$ is NP-hard. However, is there some way to bound $V(P)$ by differentiable functions of the elements of $P$? If I am not mistaken, $V$ is monotonic in each element of $P$.

For square matrix $P$, define

$$V(P) = \sup_x \inf_y x^T P y^T$$

where $x$ and $y$ lie on the unit $n-1$-simplex.

($P$ is a payoff matrix for a symmetric game, $x$ and $y$ are mixed strategies, and $V$ is the value of the game.)

It is known that determining $V(P)$ is NP-hard. However, is there some way to bound $V(P)$ by differentiable functions of the elements of $P$? If I am not mistaken, $V$ is monotonic in each element of $P$.

EDIT: The reason I want differentiable approximations for $V(P)$ is because I am interested in solving a system of equations

$p_1 = V(P_1), p_2 = V(P_2), ...$

where each $P_i$ depends on $p_1, p_2, ...$

Source Link
charles.y.zheng
charles.y.zheng
  • 241
  • 1
  • 4

Approximating the maximin value of a zero-sum game

For square matrix $P$, define

$$V(P) = \sup_x \inf_y x^T P y^T$$

where $x$ and $y$ lie on the unit $n-1$-simplex.

($P$ is a payoff matrix for a symmetric game, $x$ and $y$ are mixed strategies, and $V$ is the value of the game.)

It is known that determining $V(P)$ is NP-hard. However, is there some way to bound $V(P)$ by differentiable functions of the elements of $P$? If I am not mistaken, $V$ is monotonic in each element of $P$.