11
$\begingroup$

Hello, here is a little two-players game.

Players A and B choose three numbers : a, b and c for A, a', b' and c' for B. The values are numbers between 0 and 1, their sum is 1, and they are ordered: $a \geq b \geq c$ and $a' \geq b' \geq c'$.

Then, the players A and B compare their choices : $a$ vs $a'$, $b$ vs $b'$ and $c$ vs $c'$. If a player has 2 values bigger than the other, he wins (otherwise it's a tie).

I would like to study whether there is a good strategy in this game but I don't know how to start. Do you have an idea on the general way of studying this kind of game? Any reference of book/article is welcomed :)

$\endgroup$
8
  • $\begingroup$ I have an idea but I don't know if it is useful. Consider the values $\lambda=a-b$ and $\mu=b-c$. One may draw a triangle of possible values ($\lambda$,$\mu$) which are one-to-one with the choice of ($a$,$b$,$c$). Then for any point ($\lambda$,$\mu$) in the triangle, one may draw three line crossing in this point (whose direction do not depend on the point) which define areas of winning and losing opponent's choice (they should alternate around the point). $\endgroup$
    – Nekochan
    Jun 9, 2011 at 16:59
  • 2
    $\begingroup$ @Nekochan: Without some more discussion on your part, I don't think that this is a good question for MathOverflow, which is primarily for research-level mathematics; see mathoverflow.net/faq . Certainly game theory questions can be research level, but as posed I don't think this one is (although I am not an expert) — if I'm wrong, please provide more background/motivation to explain the research interests; see mathoverflow.net/howtoask . You may, though, be better served at some of the other sites listed in the FAQ — perhaps artofproblemsolving.com/Forum/index.php . $\endgroup$ Jun 9, 2011 at 17:09
  • 5
    $\begingroup$ This is a continuous version of the Colonel Blotto combinatorial game; knowing that name may help your literature search. $\endgroup$ Jun 9, 2011 at 18:21
  • 1
    $\begingroup$ The correspondence with a Colonel Blotto game is not obvious, since the Blotto game does not force the players to choose numbers with the same ordering. If there is an isomorphism, then there is a solution linked to the Blotto game Wikipedia page. $\endgroup$ Jun 10, 2011 at 1:20
  • 2
    $\begingroup$ I like the question and don't see why it shouldn't be on mathoverflow. I would be happy to see the answer worked out along the line suggested by Gowers below. $\endgroup$
    – Joël
    Jul 8, 2011 at 10:53

4 Answers 4

6
$\begingroup$

It seems to me that this game is illuminated a little if one considers a huge generalization. Take a probability space $(X,\mu)$ and define on it a measurable directed graph, which we can think of as a measurable subset $A$ of $X\times X.$ The first player chooses a point $x$ and the second player chooses a point $y$. The first player wins if and only if $(x,y)\in A$. (It might also be nice to add the conditions that the measure is absolutely continuous and that if $x\ne y$ then $(x,y)\in A$ if and only if $(y,x)\notin A$, but I'm not sure that affects the discussion too much.)

Now consider a randomized strategy for the first player. This consists in choosing a different probability measure on $X$, which for convenience I'll assume is a density $f$ with respect to $\mu$ (though I may have to drop that assumption later). If the second player knows $f$, then the second player will choose $y$ such that $\int f(x)\mathbb{1}_A(x,y)d\mu(x)$ is minimized.

This produces a problem that's a continuous version of the following problem: given an $n\times n$ matrix $A$, find a non-negative vector $v$ with coordinates summing to 1 such that the smallest coordinate of $Av$ is as large as possible. If the rows of $A$ are $a_1,\dots,a_n$ then this is asking us to maximize the minimum of the inner products $\langle a_i,v\rangle$ subject to the coordinates of $v$ being positive and adding up to 1, which is similar in flavour to a linear programming problem. (Can it be turned into one? I don't see it immediately. The difference is that the objective function is a minimum of linear functions rather than a linear function. So it is a convex programming problem but with the convex function of a relatively simple form.)

I imagine that all this is either incorrect or very standard game theory. Apologies in advance if there's a Wikipedia article that says similar things more clearly and authoritatively.

$\endgroup$
6
$\begingroup$

https://arxiv.org/abs/1708.07916

This arxiv paper might be helpful. The abstract is reproduced below:

This paper explores the Nash equilibria of a variant of the Colonel Blotto game, which we call the Asymmetric Colonel Blotto game. In the Colonel Blotto game, two players simultaneously distribute forces across n battlefields. Within each battlefield, the player that allocates the higher level of force wins. The payoff of the game is the proportion of wins on the individual battlefields. In the asymmetric version, the levels of force distributed to the battlefields must be nondecreasing. In this paper, we find a family of Nash equilibria for the case with three battlefields and equal levels of force and prove the uniqueness of the marginal distributions. We also find the unique equilibrium payoff for all possible levels of force in the case with two battlefields, and obtain partial results for the unique equilibrium payoff for asymmetric levels of force in the case with three battlefields.

Theorem 3.3 on page 5 characterized all Nash Equilibrium Strategies for the game described in the question.

$\endgroup$
2
  • 1
    $\begingroup$ Please give details on how it might be helpful in your answer. Specific theorem numbers and page numbers would greatly improve the answer. $\endgroup$
    – Todd Trimble
    Nov 18, 2017 at 12:23
  • $\begingroup$ @ToddTrimble Answer edited. $\endgroup$
    – Yifan Zhu
    Nov 18, 2017 at 13:53
1
$\begingroup$

This is a rather degenerate “game”, there being only one round with no interaction between the moves of the players. But whatever.

There is no strategy that would guarantee winning or tying against any other strategy: a strategy $(a,b,c)$ can be beaten by $(a-2\varepsilon,b+\varepsilon,c+\varepsilon)$ [or $(a+\varepsilon,b-2\varepsilon,c+\varepsilon)$ if $a=b>c$, the case $a=b=c=1/3$ being left to the reader] for small enough positive $\varepsilon$.

Hence the next best result you can achieve is a strategy that would give a high probability (say, $\ge1/2$) of winning against a randomly chosen counterstrategy. Whether such a strategy exists and what it looks like will likely depend on the probability distribution on the counterstrategies, so you’d have to specify that first.

$\endgroup$
4
  • 1
    $\begingroup$ Thanks! Actually I know that there is no winning strategy in only one move. I would like to find a set of moves (with a probability of choosing each one) such that the expected gain is non negative. $\endgroup$
    – Nekochan
    Jun 9, 2011 at 17:08
  • $\begingroup$ As I wrote, in this case you need to first define the probability distribution on the moves you are considering. There is no canonical choice for that, given all the constraints. $\endgroup$ Jun 9, 2011 at 17:12
  • 10
    $\begingroup$ What Nekochan is looking for is a maximin strategy. In this case that means a probability distribution over actions for one player which makes that player win at least as often as lose regardless of the strategy chosen by his opponent. Due to the discontinuities, such a probability distribution may or may not exist. $\endgroup$
    – Noah Stein
    Jun 9, 2011 at 17:19
  • $\begingroup$ This is no more degenerate than many other games in game theory, e.g., many games studied by Borel and Nash. Combinatorial game theory studies different games. $\endgroup$ Jun 26, 2011 at 12:00
-1
$\begingroup$

I think the result with proper play is always a draw as this appears to be a variant of "who can name the biggest number". I want to pick three numbers two of them are as big a possible so the obvious choice is a=1/X, b=1/2-1/X and c=1/2 where X is the biggest number I can think of. If both players do this then they tie on c and each wins one of a and b for an overall tie. And this strategy beats any other strategy that doesn't have c=1/2.

$\endgroup$
5
  • 1
    $\begingroup$ You seem to have swapped $a$ and $c$. Your last claim is incorrect, I can beat your strategy with e.g. 2/3, 1/6, 1/6 (assuming your $X$ is bigger than 6), which does not have 1/2. $\endgroup$ Jun 9, 2011 at 16:37
  • $\begingroup$ I'm not convinced that the best strategy is to get two numbers as big as possible (I'm not convinced otherwise either). What if we try and win on $a$ and $c$ and give up on $b$? That suggests a strategy of the form $a = b = (1-c)/2$, and if we choose $c > 1/2$ we beat someone using your method. $\endgroup$
    – Matt Ollis
    Jun 9, 2011 at 16:39
  • $\begingroup$ Oops, didn't see Emil's comment before I posted (and I also swapped a and c). $\endgroup$
    – Matt Ollis
    Jun 9, 2011 at 16:40
  • 1
    $\begingroup$ Hmm I'm not sure that I understand well your answer. It seems to me that your strategy consists in playing values of the form (1/2, 1/2-$\varepsilon$, $\varepsilon$). Then a winning counter-strategy is to play values of the form (1/2+2$\varepsilon$, 1/4-$\varepsilon$, 1/4-$\varepsilon$). Please correct if this doesn't match your idea. $\endgroup$
    – Nekochan
    Jun 9, 2011 at 16:42
  • 1
    $\begingroup$ If I know your choice I can always win. I pick 2 of your numbers and go $\varepsilon$ above and then am $2\varepsilon$ below your third number. I can beat any pair I choose in this way. This implies a mixed strategy is necessary to play well. Predictability is exploitable. Well played the game is trivially a long-term draw because the two players have the same choices, and the same strategies are available for each. If I want to win the top number I choose 1-$\varepsilon$ for my top, to win the middle one I need my second to be $1/2-\varepsilon$ and for the third I choose $1/3$ for all. $\endgroup$ Jun 9, 2011 at 17:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.