3
$\begingroup$

I run into this problem in my attempt to answer another question on math.stackexchange

(In the original problem the strategies can be made discrete and finite, but I am interested in the infinite version here)

We have a 2-player game with an infinite set of strategies. The strategies are essentially the same basic strategy with a parameter that tweaks it. The parameter takes values between $0$ and $1$, hence infinite strategies are born. Let's name these strategies $H_a$ where $a$ is the parameter that can change. We also know the payoff function that provides the gain of one strategy over another. Let's denote the gain of strategy $H_b$ over strategy $H_a$ as $G(H_b, H_a)$. The payoff is symmetrical, so one's gain is the other one's loss.

For our particular game the payoff function looks like this $$G(H_b, H_a) = \begin{cases} G^-(H_b, H_a), & \text{if $a \le b$} \\ G^+(H_b, H_a), & \text{if $a>b$} \end{cases}$$

with $$G^-(H_b, H_a) = b\left[\frac{a(b-a)}{b} - (1-a)\frac{a-b+2}{2}\right] + (1-b)\left[a + (1-a)\frac{2(b-a)}{1-a}\right]$$ $$G^+(H_b, H_a) = b\left[\frac{a(b-a)}{a} - (1-a)\right] + (1-b)\left[a\cdot\frac{b-a+2}{2} + (1-a)\frac{2(b-a)}{1-b}\right]$$

Simplifying them so that their quadratic form becomes apparent: $$G^-(H_b, H_a) = (a^2b - ab^2 + 5ab - 2a^2 - 3b^2 +2b -2a)/2$$ $$G^+(H_b, H_a) = (a^2b - ab^2 - 5ab + 3a^2 + 2b^2 +2b -2a)/2$$

From either of these formulas we can also calculate that $G(H_a, H_a)=0$

There is no dominant strategy. For any strategy $H_a$ you can find strategies that are better, and strategies that are worse. To get a better a sense have a look at the following two graphs. They show the gain of two strategies $H_{0.5}$ and $H_{0.8}$ against any possible strategy.

The $x$ axis on both graphs is just the parameter $a$ going from $0$ to $1$ while the $y$ axis is $G(H_{0.5}, H_a)$ for the graph on the left and $G(H_{0.8}, H_a)$ for the graph on the right.

Gain for H_0.5 Gain for H_0.8

You can notice for example that $H_{0.5}$ is better than $H_{0.2}$, $H_{0.8}$ is better than $H_{0.5}$, but $H_{0.2}$ is better than $H_{0.8}$.

How do we find the mixed strategy Nash equilibrium for our problem? In other words, what is the p.d.f. $f_M$ of random variable M that we use to define our Nash Equilibrium mixed strategy $H_M$?

When I was first faced with this problem I did not have any formal knowledge of mixed strategies or Nash equilibria, but I did try intuitively the simplest mixed strategy: $M$ being uniformly distributed in the interval $[0,1]$. I realised that this does not lead to an equilibrium and then I stopped because I was not sure whether this meant that no equilibria exist, or that I needed to find a different distribution for $M$. I read a bit on game theory and mixed strategy equilibria before posting this question and now I believe that a mixed strategy should exist. The infinite number of strategies might complicate things but this is how I am seeing the problem:

Since this is a symmetrical zero-sum game I should find the distribution of $M$ such that whatever strategy $H_a$ my opponent chooses, my expected gain will be zero.

More formally, we need to find the p.d.f. for $M$ such that $\underset{M}{\mathbb E}[G(H_M, H_a)]=0, \forall a \in [0,1]$.

(where $\underset{X}{\mathbb E}[F(X)]$ is the expected value of function $F()$ over random variable $X$ )

Is this right? If so, then I believe we can proceed like so:

$$\underset{M}{\mathbb E}[G(H_M, H_a)]=0, \forall a \in [0,1] \Leftrightarrow$$ if $f_M$ is the probability density function of random variable M we get $$\int_0^1 G(H_x, H_a)f_M(x)dx =0, \forall a \in [0,1] \Leftrightarrow$$

$$\int_0^a G^+(H_x, H_a)f_M(x)dx + \int_a^1 G^-(H_x, H_a)f_M(x)dx=0, \forall a \in [0,1] \Leftrightarrow$$

I am stuck at this point, I am not sure how to solve this parametric differential equation. If an analytic solution is not possible, can I apply numerical methods?

Finally, a small side note because I got it wrong initially: In the equation above notice how $G^+$ goes with the integral that spans $[0,a]$, and how $G^-$ goes with the integral that spans $[a,1]$. This is because gain is seen from the viewpoint of the first argument of $G()$. So if the first argument is $H_x$, with $x \le a$, while the second argument is $H_a$, then we should use the $G^+$ branch/case.

$\endgroup$
7
  • $\begingroup$ Why don't you refer to the strategy as $a$ instead of $H_a$ and $b$ instead of $H_b$? The simpler you write, the more people will read your question. $\endgroup$ Sep 26 '16 at 14:37
  • $\begingroup$ Please, remove the side question, try to keep your question as simple as possible. $\endgroup$ Sep 26 '16 at 14:43
  • $\begingroup$ When you write the payoff of the player as $G(H_b,H_a)$ is the player choosing $H_a$ or $H_b$? I'm trying to answer the question but without this information, I can't do much... $\endgroup$ Sep 26 '16 at 15:29
  • 1
    $\begingroup$ @SergioParreiras thank you, I should probably make the side question separate. The notation was transferred from the other post, maybe it can be made simpler, but $a$ is a real number in [0,1], while $H_a$ is the strategy. Writing the real number as the strategy might be confusing. About G(x,y): as I write in the question this means the payoff of the first strategy (x), over the second (y). So if G(x,y) is positive this means that x wins over y. $\endgroup$
    – Thanassis
    Sep 26 '16 at 15:57
  • 1
    $\begingroup$ @SergioParreiras, I removed the side question (now found here: math.stackexchange.com/questions/1944686/…), I provided some simpler forms for $G^+()$ and $G^-()$, and I slightly changed some notation and wording to make the problem clearer. I hope this helps. $\endgroup$
    – Thanassis
    Sep 28 '16 at 9:00

Your Answer

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

Browse other questions tagged or ask your own question.