Author |
Topic: Number game (Read 2462 times) |
|
Deedlit
Senior Riddler
Posts: 476
|
|
Number game
« on: Apr 25th, 2005, 6:40pm » |
Quote Modify
|
Two players play the following game: each player picks a natural number (er, I mean positive integer). If the numbers are the same, the game is a draw. If the numbers differ by 1, the person who picked the lower number pays the other $2. If ther numbers differ by more than 1, the person who picked the higher number pays the other $1. Defining an "optimal strategy" as a strategy that at least breaks even against any strategy your opponent can use, what are the optimal strategies for this game? Generalization: replace $2 with $a, for arbitrary real number a.
|
|
IP Logged |
|
|
|
iyerkri
Newbie
Gender:
Posts: 17
|
|
Re: Number game
« Reply #1 on: Apr 28th, 2005, 4:57am » |
Quote Modify
|
Hi, I havent worked out or anything but this is what i feel intuitively......if its correct let me know...i will try to come up with rigorous arguments then, The optimal strategy is definitely a mixed strategy. I feel that one has to randomize between numbers 1 & 2. two thirds of the time on has to say 2 and one thirds of the time one has to choose 1. Let me know about this. kris
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Number game
« Reply #2 on: Apr 28th, 2005, 5:59am » |
Quote Modify
|
If you do that, then I'd always pick 2. And either draw or win, every time. It'd be a lot easier if the range of numbers was finite..
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
iyerkri
Newbie
Gender:
Posts: 17
|
|
Re: Number game
« Reply #3 on: Apr 28th, 2005, 7:53am » |
Quote Modify
|
well , i have assumed that one does not know what strategy the other guy is going to employ. if not, then the first guy can retaliate by always saying 3. what i am assuming is both the player choose the number simultaneously without knowing what the other guys strategy is. in this case the problem is symmetrical, and the optimal strategy for both of the would be the same.
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Number game
« Reply #4 on: Apr 28th, 2005, 8:19am » |
Quote Modify
|
Yes, but if it's played multiple times, then you can start speculating about the other's strategy, and adjust yours accordingly.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: Number game
« Reply #5 on: Apr 28th, 2005, 9:07am » |
Quote Modify
|
Besides, kris, your strategy does not satisfy the definition of “optimality”: on Apr 25th, 2005, 6:40pm, Deedlit wrote:Defining an "optimal strategy" as a strategy that at least breaks even against any strategy your opponent can use, what are the optimal strategies for this game? |
| Also, Deedlit as usual challenges us with something requiring very sly strategy!
|
|
IP Logged |
|
|
|
Deedlit
Senior Riddler
Posts: 476
|
|
Re: Number game
« Reply #6 on: Apr 28th, 2005, 7:29pm » |
Quote Modify
|
As towr and Barukh have said, the fact that your opponent can just pick 2 or 3 all the time and beat you (by dumb luck perhaps) is enough to keep your strategy from being optimal. Although nothing was said about knowing your opponent's strategy, if you do have an optimal strategy, you can cockily tell your opponent what it is, and challenge him to find a strategy that beats you - you're not worried, because he can't!
|
|
IP Logged |
|
|
|
Deedlit
Senior Riddler
Posts: 476
|
|
Re: Number game
« Reply #7 on: Apr 29th, 2005, 2:12am » |
Quote Modify
|
on Apr 28th, 2005, 5:59am, towr wrote:It'd be a lot easier if the range of numbers was finite.. |
| What if you could prove that it never makes sense to pick values beyond a certain limit?
|
|
IP Logged |
|
|
|
JocK
Uberpuzzler
Gender:
Posts: 877
|
|
Re: Number game
« Reply #8 on: Apr 30th, 2005, 2:24pm » |
Quote Modify
|
on Apr 25th, 2005, 6:40pm, Deedlit wrote:Generalization: replace $2 with $a, for arbitrary real number a. |
| For 0 < a < (1+sqrt(5))/2 the strategy of selecting 1, 2 or 3 with respective probabilities a/(1+2a), 1/(1+2a) and a/(1+2a) can not be beaten: to break even, the opponent has to limit his/her strategy to the same three numbers, selecting higher numbers would lead to an expected loss. For values of a exceeding the Golden Mean, the optimum strategy (Nash equilibrium) should involve selecting values above 3 as well. (haven't cracked this more tedious problem yet ... )
|
« Last Edit: Apr 30th, 2005, 2:45pm by JocK » |
IP Logged |
solving abstract problems is like sex: it may occasionally have some practical use, but that is not why we do it.
xy - y = x5 - y4 - y3 = 20; x>0, y>0.
|
|
|
Deedlit
Senior Riddler
Posts: 476
|
|
Re: Number game
« Reply #9 on: Apr 30th, 2005, 2:48pm » |
Quote Modify
|
Correct! Can you prove it? (i.e. why can no strategy beat it, and why is there no other optimal strategy?)
|
|
IP Logged |
|
|
|
JocK
Uberpuzzler
Gender:
Posts: 877
|
|
Re: Number game
« Reply #10 on: May 1st, 2005, 12:51am » |
Quote Modify
|
on Apr 30th, 2005, 2:48pm, Deedlit wrote:[..] why can no strategy beat it [..] |
| This is straightforward: when you use the indicated probabilities for selecting 1, 2 and 3, the expected gain for the opponent when selecting 1, 2, 3, 4, 5, 6, etc. is: 0, 0, 0, a^2-a-1, -2a-1, -2a-1, etc. For a < (sqrt(5)+1)/2 positive expected gains do not emerge for the opponent. on Apr 30th, 2005, 2:48pm, Deedlit wrote:[..] and why is there no other optimal strategy?) |
| I have to think about this one. It should be obvious that there is no alternative Nash equilibrium that is limited to selecting the lowest three numbers, but in principle there could be alternative Nash equilibria involving selecting higher numbers.
|
|
IP Logged |
solving abstract problems is like sex: it may occasionally have some practical use, but that is not why we do it.
xy - y = x5 - y4 - y3 = 20; x>0, y>0.
|
|
|
JocK
Uberpuzzler
Gender:
Posts: 877
|
|
Re: Number game
« Reply #11 on: May 1st, 2005, 1:07am » |
Quote Modify
|
The problem for a=2 is still unsolved! (Leave that for someone else... ). Meanwhile, I started wondering about multi-player versions of this game. For instance: what would be the optimal strategy if three players play the game using the rule that the single highest bidder receives $1 from each player that bids one less, but the single lowest bidder receives $1 from each player that bids higher by more than one? (I.e. you never gain when one of the other players bids the same number as you.) Is the (non-cooperative) optimal strategy for this 3-player game also limited to bidding the lowest three numbers? Is this strategy robust against the two other players cooperating in some way?
|
|
IP Logged |
solving abstract problems is like sex: it may occasionally have some practical use, but that is not why we do it.
xy - y = x5 - y4 - y3 = 20; x>0, y>0.
|
|
|
Earendil
Newbie
Gender:
Posts: 46
|
|
Re: Number game
« Reply #12 on: May 1st, 2005, 8:47am » |
Quote Modify
|
A strategy* bets on an independent and identicaly distributed sequence of random variables. Does this hold? "A strategy* is optimal if and only if it is better or equal to every strategy which goes always on the same number." in that case, is it easy to solve something like this? (Or, at least divise if it has a solution or not) { a[1], a[2], a[3], a[4] >= 0 { 2a[2] - a[3] - a[4] >= 0 { -2a[1] +2a[3] - a[4] >= 0 { a[1] - 2a[2] +2a[4] >= 0 { a[1] + a[2] -2a[3] >= 0 { a[1] + a[2] + a[3] - 2a[4] >= 0 { { a[1] + a[2] + a[3] + a[4] = 1
|
« Last Edit: May 1st, 2005, 9:06am by Earendil » |
IP Logged |
|
|
|
Michael Dagg
Senior Riddler
Gender:
Posts: 500
|
|
Re: Number game
« Reply #13 on: May 1st, 2005, 9:54am » |
Quote Modify
|
There are more equations that there are unknowns. Try starting with the last two relationships to see 0 <= a4 <=1/3 and then concentrate on eliminating some of the equations.
|
|
IP Logged |
Regards, Michael Dagg
|
|
|
Deedlit
Senior Riddler
Posts: 476
|
|
Re: Number game
« Reply #14 on: May 1st, 2005, 1:42pm » |
Quote Modify
|
on May 1st, 2005, 8:47am, Earendil wrote:A strategy* bets on an independent and identicaly distributed sequence of random variables. |
| Of course this does not include all possible strategies, but you can argue why you only need to consider this narrower type. Quote: Does this hold? "A strategy* is optimal if and only if it is better or equal to every strategy which goes always on the same number." |
| Yup. How do you determine the expected payoff of a mixed strategy? Quote: in that case, is it easy to solve something like this? (Or, at least divise if it has a solution or not) { a[1], a[2], a[3], a[4] >= 0 { 2a[2] - a[3] - a[4] >= 0 { -2a[1] +2a[3] - a[4] >= 0 { a[1] - 2a[2] +2a[4] >= 0 { a[1] + a[2] -2a[3] >= 0 { a[1] + a[2] + a[3] - 2a[4] >= 0 { { a[1] + a[2] + a[3] + a[4] = 1 |
| Well, I guess this is a problem in linear programming - the solution will be a polytope in three dimensions (the first and last equations restrict it to a 4-simplex), which you can describe by finding the boundaries of the faces. The faces lie on the planes satisfying one of the above inequalities turned into equality (like a[1] = 0, or a[1] + a[2] + a[3] - 2a[4] = 0); the edges line on the intersections of two, and the vertices lie on the intersections of three. It looks rather complicated to me, but perhaps someone more practiced could simplify it. In any case, it isn't quite how I solved it - I made some simplifying assumptions first.
|
|
IP Logged |
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: Number game
« Reply #15 on: May 3rd, 2005, 4:33am » |
Quote Modify
|
In case a = 2, the optimal strategy contains first 5 numbers with probabilities 1/16, 5/16, 1/4, 5/16, 1/16. Generally, 5 numbers are always sufficient when a > (1 + [sqrt]5)/2, and the rest was covered by Jock's strategy with 3 numbers. Of course, Jock's ingenious solution was a crusial step!
|
|
IP Logged |
|
|
|
Deedlit
Senior Riddler
Posts: 476
|
|
Re: Number game
« Reply #16 on: May 4th, 2005, 6:28pm » |
Quote Modify
|
That's correct! Can you give the general strategy for arbitrary a, and a proof? Also, what happens at a = (1+sqrt(5))/2, and a <= 0?
|
|
IP Logged |
|
|
|
Grimbal
wu::riddles Moderator Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Number game
« Reply #17 on: May 5th, 2005, 5:03am » |
Quote Modify
|
If a<=0, the game boils down to who has the lowest number. You just play 1 all the time.
|
|
IP Logged |
|
|
|
Deedlit
Senior Riddler
Posts: 476
|
|
Re: Number game
« Reply #18 on: May 5th, 2005, 4:32pm » |
Quote Modify
|
Is that all the optimal strategies?
|
|
IP Logged |
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: Number game
« Reply #19 on: May 5th, 2005, 11:25pm » |
Quote Modify
|
on May 1st, 2005, 8:47am, Earendil wrote:"A strategy* is optimal if and only if it is better or equal to every strategy which goes always on the same number." |
| Call this simple strategy n-strategy if the number is n. on May 4th, 2005, 6:28pm, Deedlit wrote:That's correct! Can you give the general strategy for arbitrary a, and a proof? |
| For any a > (1+[sqrt]5)/2, the probability vector of an optimal strategy is (a2-a-1, 2a+1, a2, 2a+1, a2-a-1) / (3a2+2a). It is not difficult to check that this strategy ties with every n-strategy for n <= 5, and wins over 6-strategy (for big a, asymptotically 5/3a). The solution I came with was of course inspired by Jock’s solution. If an optimal strategy covers numbers from 1 to n, then we need to consider a system of n+1 linear inequalities (corresponding to 1-, 2-, … (n+1)-strategy of the opponent), plus a normalizing equality for probabilities (Earendil gave an example for n=4). That’s tedious, so I considered only strategies where the first n inequalities become equalities (isn’t it the same simplifying assumption Deedlit mentioned?). Namely, such an optimal strategy will tie against all i-strategies for i <= n. Then, we get a homogeneous system of n equations. The necessary and sufficient condition for such a system to have a non-trivial solution is that the determinant of the coefficients’ matrix equals to 0. Fortunately, the matrix at hand has a special structure: it’s anti-symmetric, and therefore has a determinant 0 for every odd n. The rest is straightforward: get the general solution for the system (I used a nice on-line solver), and check that (1) it’s indeed a probability vector (all numbers are positive), and (2) it doesn’t loose against (n+1)-strategy. Quote:Also, what happens at a = (1+sqrt(5))/2 |
| Isn’t that covered in Jock’s solution? on May 5th, 2005, 4:32pm, Deedlit wrote:Is that all the optimal strategies? |
| I don’t know.
|
|
IP Logged |
|
|
|
Deedlit
Senior Riddler
Posts: 476
|
|
Re: Number game
« Reply #20 on: May 6th, 2005, 9:13am » |
Quote Modify
|
on May 5th, 2005, 11:25pm, Barukh wrote: For any a > (1+[sqrt]5)/2, the probability vector of an optimal strategy is (a2-a-1, 2a+1, a2, 2a+1, a2-a-1) / (3a2+2a). It is not difficult to check that this strategy ties with every n-strategy for n <= 5, and wins over 6-strategy (for big a, asymptotically 5/3a). |
| Whoops! Sorry, this doesn't work for all a > (1+[sqrt]5)/2 (my previous reply suggested that it did, my bad). If you calculate the expected return against an opponent who always picks 6, you get (1 + 4a + 3a2 - a3) / (3a2 + 2a) which turns negative eventually. Quote: The rest is straightforward: get the general solution for the system (I used a nice on-line solver), |
| Incidentally, what are some good on-line solvers? Quote: Isn’t that covered in Jock’s solution? |
| Well, I'm being anal - I want to know all the optimal solutions! Quote: I don’t know. |
| For a = 2 (we still have more work to do for general a!) we can in fact prove that the inequalities need to be equalities. Do you see why?
|
|
IP Logged |
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: Number game
« Reply #21 on: May 7th, 2005, 1:31am » |
Quote Modify
|
on May 6th, 2005, 9:13am, Deedlit wrote:Whoops! Sorry, this doesn't work for all a > (1+[sqrt]5)/2 (my previous reply suggested that it did, my bad). If you calculate the expected return against an opponent who always picks 6, you get (1 + 4a + 3a2 - a3) / (3a2 + 2a) which turns negative eventually. |
| Silly me! I was so blinded by the ‘a = 2’ case, that I took for the last expected return in the general case the expression p1 + … + p4 - 2p5, instead of changing the last coefficient to a! So, it seems (at least for me) that 5 numbers are not sufficient for all a. It seizes to give a non-negative return for a slightly less than 4.05. And then… go to 7 numbers. I haven’t proved that but it seems that the system is solvable for any odd dimension n, with ever increasing “limited a” for the last (n+1)-strategy. The actual expressions for probability vectors are interesting: they involve expressions from lower dimensions. I believe it’s not a coincidence. It just means I lack a true understanding of solution’s structure. Quote:Incidentally, what are some good on-line solvers? |
| Go to Interactive Mathematics Server, Online calculators and plotters -> Linear Solver. I used “matrix method”. Note that you may specify parameters in your system. Quote:Well, I'm being anal - I want to know all the optimal solutions! |
| Well, looking at my solution for 5 numbers, it seems it should work also for phi (golden ratio). In this case, it degenerates into 3 numbers (2, 3, 4) taken with probabilities phi:1:phi – just like in Jock’s solution. Quote:For a = 2 (we still have more work to do for general a!) we can in fact prove that the inequalities need to be equalities. Do you see why? |
| Not yet.
|
|
IP Logged |
|
|
|
Deedlit
Senior Riddler
Posts: 476
|
|
Re: Number game
« Reply #22 on: May 7th, 2005, 4:28pm » |
Quote Modify
|
Ah, thanks, Barukh. It looks like a good resource. A hint: Strict inequality seems OK, since it's good for you - but it's bad for your opponent!
|
|
IP Logged |
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: Number game
« Reply #23 on: May 8th, 2005, 4:25am » |
Quote Modify
|
on May 7th, 2005, 4:28pm, Deedlit wrote:A hint: Strict inequality seems OK, since it's good for you - but it's bad for your opponent! |
| Aha! What happens if both players use the optimal strategy? Then, the expected gain for both should be non-negative, therefore, equal to 0. In that case, the (n+1)-strategy is never used. on May 6th, 2005, 9:13am, Deedlit wrote:(we still have more work to do for general a!) |
| It seems the same argument works for general a (given we can always solve the n equations system for appropriately chosen odd n).
|
|
IP Logged |
|
|
|
Earendil
Newbie
Gender:
Posts: 46
|
|
Re: Number game
« Reply #24 on: May 8th, 2005, 8:38am » |
Quote Modify
|
I had a funny doubt now... It looks like it is possible for a given 'a' to have more then one optimal solution. In that case, even though an optimal strategy always has 0 payoff against another one, isn't it possible for one to have a better general income then the other? If that is considered, can't a more restrictive concept of optimality be created? I tought about a strategy which isn't an independent and identicaly distributed sequence of random variables but somehow seems optimal in a nice way. I) At every time, you consider the whole past of your oponents guesses and suppose his strategy corresponds to a random variable with a distribution which corresponds to the frequencies in that past. II) Your guess is a random variable which maximizes the payoff against that distribution.
|
« Last Edit: May 8th, 2005, 12:35pm by Earendil » |
IP Logged |
|
|
|
|