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$

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.