wu :: forums
« wu :: forums - Number game »

Welcome, Guest. Please Login or Register.
Nov 29th, 2024, 12:46am

RIDDLES SITE WRITE MATH! Home Home Help Help Search Search Members Members Login Login Register Register
   wu :: forums
   riddles
   hard
(Moderators: Grimbal, SMQ, Icarus, Eigenray, ThudnBlunder, towr, william wu)
   Number game
« Previous topic | Next topic »
Pages: 1 2  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print
   Author  Topic: Number game  (Read 2462 times)
Deedlit
Senior Riddler
****





   


Posts: 476
Number game  
« on: Apr 25th, 2005, 6:40pm »
Quote Quote Modify 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
*





  iyerkri  


Gender: male
Posts: 17
Re: Number game  
« Reply #1 on: Apr 28th, 2005, 4:57am »
Quote Quote Modify 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: male
Posts: 13730
Re: Number game  
« Reply #2 on: Apr 28th, 2005, 5:59am »
Quote Quote Modify 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.. Tongue
IP Logged

Wikipedia, Google, Mathworld, Integer sequence DB
iyerkri
Newbie
*





  iyerkri  


Gender: male
Posts: 17
Re: Number game  
« Reply #3 on: Apr 28th, 2005, 7:53am »
Quote Quote Modify 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: male
Posts: 13730
Re: Number game  
« Reply #4 on: Apr 28th, 2005, 8:19am »
Quote Quote Modify 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: male
Posts: 2276
Re: Number game  
« Reply #5 on: Apr 28th, 2005, 9:07am »
Quote Quote Modify 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 Quote Modify 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 Quote Modify Modify

on Apr 28th, 2005, 5:59am, towr wrote:
It'd be a lot easier if the range of numbers was finite.. Tongue

 
What if you could prove that it never makes sense to pick values beyond a certain limit?  Wink
IP Logged
JocK
Uberpuzzler
*****






   


Gender: male
Posts: 877
Re: Number game  
« Reply #8 on: Apr 30th, 2005, 2:24pm »
Quote Quote Modify 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 ...  Undecided )
 
 
« 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 Quote Modify Modify

Correct!  Smiley 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: male
Posts: 877
Re: Number game  
« Reply #10 on: May 1st, 2005, 12:51am »
Quote Quote Modify 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: male
Posts: 877
Re: Number game  
« Reply #11 on: May 1st, 2005, 1:07am »
Quote Quote Modify Modify

The problem for a=2 is still unsolved!
 
(Leave that for someone else... Wink ).  
 
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
*





7195044 7195044    


Gender: male
Posts: 46
Re: Number game  
« Reply #12 on: May 1st, 2005, 8:47am »
Quote Quote Modify 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: male
Posts: 500
Re: Number game  
« Reply #13 on: May 1st, 2005, 9:54am »
Quote Quote Modify 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 Quote Modify 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: male
Posts: 2276
Re: Number game  
« Reply #15 on: May 3rd, 2005, 4:33am »
Quote Quote Modify 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 Quote Modify 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: male
Posts: 7527
Re: Number game  
« Reply #17 on: May 5th, 2005, 5:03am »
Quote Quote Modify Modify

If a<=0, the game boils down to who has the lowest number.  You just play 1 all the time.   Smiley
IP Logged
Deedlit
Senior Riddler
****





   


Posts: 476
Re: Number game  
« Reply #18 on: May 5th, 2005, 4:32pm »
Quote Quote Modify Modify

Is that all the optimal strategies?
IP Logged
Barukh
Uberpuzzler
*****






   


Gender: male
Posts: 2276
Re: Number game  
« Reply #19 on: May 5th, 2005, 11:25pm »
Quote Quote Modify 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.  Undecided
IP Logged
Deedlit
Senior Riddler
****





   


Posts: 476
Re: Number game  
« Reply #20 on: May 6th, 2005, 9:13am »
Quote Quote Modify 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.  Undecided

 
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: male
Posts: 2276
Re: Number game  
« Reply #21 on: May 7th, 2005, 1:31am »
Quote Quote Modify 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.  Undecided
IP Logged
Deedlit
Senior Riddler
****





   


Posts: 476
Re: Number game  
« Reply #22 on: May 7th, 2005, 4:28pm »
Quote Quote Modify 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: male
Posts: 2276
Re: Number game  
« Reply #23 on: May 8th, 2005, 4:25am »
Quote Quote Modify 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
*





7195044 7195044    


Gender: male
Posts: 46
Re: Number game  
« Reply #24 on: May 8th, 2005, 8:38am »
Quote Quote Modify 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
Pages: 1 2  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print

« Previous topic | Next topic »

Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright © 2000-2004 Yet another Bulletin Board