Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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 :)

share|improve this question
    
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). –  Nekochan Jun 9 '11 at 16:59
2  
@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 . –  Theo Johnson-Freyd Jun 9 '11 at 17:09
4  
This is a continuous version of the Colonel Blotto combinatorial game; knowing that name may help your literature search. –  Brian Hopkins Jun 9 '11 at 18:21
1  
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. –  Douglas Zare Jun 10 '11 at 1:20
1  
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. –  Joël Jul 8 '11 at 10:53

3 Answers 3

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.

share|improve this answer

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.

share|improve this answer
1  
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. –  Nekochan Jun 9 '11 at 17:08
    
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. –  Emil Jeřábek Jun 9 '11 at 17:12
9  
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. –  Noah Stein Jun 9 '11 at 17:19
    
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. –  Douglas Zare Jun 26 '11 at 12:00

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.

share|improve this answer
1  
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. –  Emil Jeřábek Jun 9 '11 at 16:37
    
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. –  Matt Ollis Jun 9 '11 at 16:39
    
Oops, didn't see Emil's comment before I posted (and I also swapped a and c). –  Matt Ollis Jun 9 '11 at 16:40
1  
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. –  Nekochan Jun 9 '11 at 16:42
1  
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. –  Mark Bennet Jun 9 '11 at 17:36

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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