2
$\begingroup$

I have a function $f = -20p\cdot q + 9p + 9q$. Player 1 chooses $p$ and player 2 chooses $q$. Both $p$ and $q$ are in the inclusive interval $[0, 1]$. Player 1 wants to maximize $f$ while player 2 wants to minimize $f$.

Player 1 goes first, what is the most optimal value of $p$ he should choose knowing that player 2 will choose a $q$ in response to player 1's choice of $p$?

This seems to be some sort of minimization-maximization problem, but I am unsure how to solve it. I was thinking about approaching this from a calculus perspective by taking the partial derivative of $f$ with respect to $p$, but it doesn't seem I get an intuition by doing this, and it seems that $p$ and $q$ are a function of each other. How should I approach solving this problem analytically?

$\endgroup$

2 Answers 2

3
$\begingroup$

Your problem can be formulated as:

$$\ \max_{p \in [0, 1]}\min_{q\in [0, 1]} f(p, q) = \max_{p\in[0, 1]} g(p) $$

Let's see $g(p)$, $$\ g(p) = \min_{q\in[0, 1]} -20pq + 9p + 9q = \min_{q\in[0, 1]} (9-20p)q + 9p $$

Case-1: $$\ 9-20p\geq0 \implies q=0 \\ \text{ Hence }g(p)=9p \text{ if } p \leq \frac{9}{20} $$

Case-2: $$\ 9-20p<0 \implies q=1 \\ \text{ Hence }g(p)=9-11p \text{ if } p > \frac{9}{20} $$

You can see $p=\frac{9}{20}$ is the best move for the first player. Similar to the previous answer but more mathematical. Note that even if $p\in \mathbb R$ we cannot gain any advantage.

$\endgroup$
2
$\begingroup$

Okay, I think I figured it out, but it would be great to get feedback. I'm also interested in other approaches, especially if there's an easy calculus method to solve this.


My solution:

Consider the first term, $-20p\cdot q$. This term can only be $ \leq 0$. If it is zero because $p=0$, then the only logical choice for $q$ is also $0$. If it's non-zero, i.e., $p, q > 0$, then choose $p'$ isn't trivial because it'll want to minimize $-20p\cdot q$ and also $9q$, but the two have opposite signs.

Consider the summation of these 2 terms: $$ -20p \cdot q + 9q \\ = q(9 - 20p) $$

If the term in parenthesis is negative, then it's obvious we pick $q = 1$. If the parenthesis term is positive, then it's obvious we choose $q = 0$. If the parenthesis term is zero, then it doesn't matter what we choose $q$ to be.

If $9-20p = 0 \implies p = 0.45 \implies f = 9p = 4.05$.

If $9 - 20p < 0 \implies p > 0.45, q = 1 \implies f < \sup_{p > 0.45} f = 0.45$.

If $9 - 20p > 0 \implies p < 0.45, q = 0 \implies f < \sup_{p < 0.45} f = 0.45$.

So from this we see that player 1 should choose $p=0.45$, which is the case where $(9 - 20p) = 0$ and $q$ can be whatever.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .