5
$\begingroup$

Alice and Bob have $N_A$ and $N_B$ warriors under their command, numbered $1$~$N_A$ and $1$~$N_B$ respectively. Alice has $1$ fighting power at her disposal, and Bob has $b$ ($b\gt 0$). Before the game, they privately distribute their power between their warriors. When the game begins, both send their warrior #1 to a 1-to-1 fight. If a warrior with power $x$ fights one with power $y$, the former wins with probability $\frac{x}{x+y}$, and the latter with $\frac{y}{x+y}$. If #1 is defeated, #2 is sent to continue the next round of fight, so on and so forth until one side has all of their warriors defeated and loses the game. There's a small twist though: after a warrior defeats an $x$ power opponent, his power will increase by $cx$ ($c\geq 0$).

Clearly, a player's strategy is their method of distributing fighting power.

Question 1: if Alice and Bob are equally matched ($N_A=N_B$ and $b=1$), does Alice have a strategy that can guarantee her no less than 50% winning probability, no matter how Bob plays?

Question 2: is there a dominant strategy for Alice?


Note: question 2 is a stronger claim, and implies question 1. For $c=1$, I know the answer is yes for both questions, because in that case the game is essentially the gambler's ruin problem, so every strategy gives the same winning probability for Alice. I suspect but can't prove an equal distribution is dominant for $c=0$ and give-it-all-to-one is dominant for $c\gt1$. A simulation for $N_A=N_B=2$, $b=1$ and $c=1/2$ suggests that giving 0.420341... to the first warrior guarantees 50% winning probability for Alice.

$\endgroup$
4
  • $\begingroup$ Are the values of N_A, N_B and b all known by both parties? $\endgroup$ Commented Jul 11, 2021 at 10:59
  • $\begingroup$ @M.D. Yes, they are. $\endgroup$
    – Eric
    Commented Jul 11, 2021 at 13:28
  • $\begingroup$ The rule for this game seems to be "the winner stays at the table (or in the arena)", is this right? $\endgroup$
    – Wlod AA
    Commented Jul 12, 2021 at 5:24
  • 1
    $\begingroup$ @WlodAA That's right. $\endgroup$
    – Eric
    Commented Jul 12, 2021 at 7:29

2 Answers 2

1
$\begingroup$

This answer expands on my previous answer. It is too long for a comment on comment.

The outcome of the game to a player is 1 if he/she wins and 0 if he/she lose. Every pair of strategies induces an expected outcome, which is a number between 0 and 1 - the probability that the player wins. The min-max value of the game is (the infimum over all strategies of Bob of the supremum over all strategies of Alice of the probability that Alice wins). Similarly, the max-min value of the game is (the supremum over all strategies of Alice of the infimum over all strategies of Bob of the probability that Alice wins). If the two quantities coincide, the common number is called the value of the game. In the game you describe the two players are symmetric: when one player wins, the other loses; every strategy available to Alice is also available to Bob; and if each player adopts the strategy of their opponent, the probabilities that they win change as well. In symmetric games, the value, if it exists, is 0.5.

The question is, then, whether the value exists. There are theorems that guarantee the existence of the value, and they require:

  1. The set of pure strategies should be compact (in a nice enough space; the space here is Euclidean, which is nice).
  2. The payoff function should be continuous.

If I am not mistaken, in your example both conditions hold.

$\endgroup$
1
  • $\begingroup$ You should edit this into your first answer instead of posting it as a second one. $\endgroup$
    – Arno
    Commented Jul 12, 2021 at 16:31
1
$\begingroup$

For question 1: If I properly understood the question, the two players are symmetric. The set of pure strategies is compact (all partitions of $N_A$ (or $N_B$) to the warriors), and so the set of mixed strategies is compact as well. The payoff function seems to be continuous in the strategies of the players, hence the value in mixed strategies exists. Since the players are symmetric, the value of the game is 0.5, hence each player has a strategy that ensures winning with probability 0.5.

$\endgroup$
2
  • $\begingroup$ What does "the value of the game is 0.5" mean? Can you be a bit more specific on why symmetry+compactness+continuity implies the existence of such a strategy? $\endgroup$
    – Eric
    Commented Jul 12, 2021 at 7:35
  • 1
    $\begingroup$ Can the value of the game be determined if $b\ne 1$? $\endgroup$ Commented Jul 12, 2021 at 16:32

You must log in to answer this question.

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