Price Is Right

[brakos82]

Suppose you find yourself on Contestant's Row of The Price Is Right, the infamous price-guessing game show. On Contestant's Row, 4 contestants, one after the other, each guess the dollar value of a prize (always rounded to the nearest $1). The person who comes closest to the actual price (without going over) is the winner.

In this variance, however, the value of the prizes are randomly determined within a defined range ($1 to $3000, both inclusive).

Logically, the person in the 4th and final seat will bid $1 over another bid (or just $1) so that they have the best chance of winning. (This tactic is used all the time in the real game, sometimes even by the 2nd or 3rd players.)
Example:

Spoiler:

Player 1 bids $1300
Player 2 bids $1800
Player 3 bids $650
So, player 4, knowing the prizes have a range of 1 to 3000:
bidding $1 gives a 649/3000 chance of winning,
bidding $651 gives a 649/3000 chance also,
bidding $1301 gives a 499/3000 chance, and
bidding $1801 gives an 1200/3000 chance.
So player 4 would logically bid 1801.

We'll assume the first 3 contestants bid randomly between $1 and $3000, and the 4th contestant always bids $1 more than another player (or just $1) to give him/herself the best odds of winning.

As a logician, is there an optimal strategy of bidding so that you have the best chance of winning as the first, second, or third contestant?

[Kingreaper]

Spoiler:

Given as the 4th player will want to take the largest single region*, the 3rd player must ensure that their area is as large as possible WITHOUT including the largest single region.
(the largest contiguous series of numbers that belong to a single player, but are not directly claimed by any player)

That's as far as I can get right now, but am trying to work out 2nd player's strategy from there.

[campboy]

Perhaps surprisingly,

Spoiler:

they should all end up with an equal chance of winning, by guessing (in order) $2251, $1501, $751, $1. With the first three as above, fourth player does worse by choosing anything other than $1. If the first two are the same then any play by third of more than $751 does worse immediately; if third tries a lower play like $750, fourth will now do best by going $1 higher than third, so third is worse off again. Similarly, if first plays $2251 then second plays $x, somewhere from $752 to $1500, third should play somewhere from $x+1 to $1501, so second does worse. If first plays $2251 then second plays $x from $1 to $750 then third will play just over halfway between $x and $2250, and fourth will play $x+1. If second picks $751 then the other players have choices between equal plays for them; one of these leaves second with a 1/4 chance but the other leaves second with only a 1/3000 chance.

[t1mm01994]

Perhaps surprisingly,

Spoiler:

they should all end up with an equal chance of winning, by guessing (in order) $2251, $1501, $751, $1. With the first three as above, fourth player does worse by choosing anything other than $1. If the first two are the same then any play by third of more than $751 does worse immediately; if third tries a lower play like $750, fourth will now do best by going $1 higher than third, so third is worse off again. Similarly, if first plays $2251 then second plays $x, somewhere from $752 to $1500, third should play somewhere from $x+1 to $1501, so second does worse. If first plays $2251 then second plays $x from $1 to $750 then third will play just over halfway between $x and $2250, and fourth will play $x+1. If second picks $751 then the other players have choices between equal plays for them; one of these leaves second with a 1/4 chance but the other leaves second with only a 1/3000 chance.

Wait, how does $750 not work better for #4?

[mfb]

It is not specified what happens if the prize is below the lowest guess. However, if #4 picks 1$, he wins in the full range 1-750$ and he cannot improve that.

Do they win the prize afterwards? In this case, a successful guess in the range of 2000-3000$ should be better than one in the range of 1-1000$, right? You can modify campboy's strategy to get a similar result here.

[Tirian]

Perhaps surprisingly,

Spoiler:

they should all end up with an equal chance of winning, by guessing (in order) $2251, $1501, $751, $1. With the first three as above, fourth player does worse by choosing anything other than $1. If the first two are the same then any play by third of more than $751 does worse immediately; if third tries a lower play like $750, fourth will now do best by going $1 higher than third, so third is worse off again. Similarly, if first plays $2251 then second plays $x, somewhere from $752 to $1500, third should play somewhere from $x+1 to $1501, so second does worse. If first plays $2251 then second plays $x from $1 to $750 then third will play just over halfway between $x and $2250, and fourth will play $x+1. If second picks $751 then the other players have choices between equal plays for them; one of these leaves second with a 1/4 chance but the other leaves second with only a 1/3000 chance.

That was my initial reaction as well but

Spoiler:

Our rivals aside from the #4 are not acting rationally but are making random choices. If player #1 chooses $2251, it is certain that player #4 won't steal your slice of the pie as it were, but there is nearly even odds that either #2 or #3 would choose to share it. A priori, I am not certain if a smaller range would make it less likely that we will be spoiled in that manner that would make up for the lower range. On the other hand, since #2 and #3 are behaving randomly, it seems possible that we can choose a larger slice and hope that #4 will have a larger piece yet to steal.

It is not specified what happens if the prize is below the lowest guess.

FWIW, on the actual game everyone makes another choice in the same order being instructed to not guess higher than the lowest guess in the previous round.

[Kingreaper]

That was my initial reaction as well but

Spoiler:

Our rivals aside from the #4 are not acting rationally but are making random choices. If player #1 chooses $2251, it is certain that player #4 won't steal your slice of the pie as it were, but there is nearly even odds that either #2 or #3 would choose to share it. A priori, I am not certain if a smaller range would make it less likely that we will be spoiled in that manner that would make up for the lower range. On the other hand, since #2 and #3 are behaving randomly, it seems possible that we can choose a larger slice and hope that #4 will have a larger piece yet to steal.

A)

Spoiler:

Having a smaller piece is strictly inferior. For each additional point X your region contains* there is an additional way you can have space stolen from you (at point X). But the space stolen will only S>=X, all the space <X is as safe as it was before. So the only danger of adding points is the action of player 4.

*(using your chosen point as the origin, because it's so much easier this way)

B)

Spoiler:

Given opponents 2 and 3 are playing randomly, player 1 should pick a point <=2002. If they pick 2002 it is impossible that their region will be the largest available when player 4 plays.
The optimal play is a bit more difficult, but must be 2002 or less.*
*(but I can't find an easy, non-trial+error, way to find how much less.)

[mfb]

Wait... so we are 1, 2 or 3 (and should play perfect), and the other 2 play random, while 4 plays perfect?
I do not think this is an interesting setup, but a sum (or integration, neglecting the discrete nature of the money) over the picks of the random players after us should give a solution for every case.

[Xias]

#3:

Spoiler:

If the largest region is greater than or equal to double the second largest region, choose $x so that you cut the largest region in half (rounded down if necessary) and add 1. If the largest region is less than double the second largest region, take the second largest region.

#2:

Spoiler:

First we need to see if adding risk of being taken by player 4 is worth increased protection from player 3's randomness. So let's examine the 3 person case.
If you choose $2001, your odds are:
(2000/2999)(1000/3000) +
(1/2999)(999/3000) +
(1/2999)(998/3000) +
... +
(1/2999)(1/3000) =
0.2778148 chance of winning.

If you choose $2000, your odds are:
(1994/2999)(1001/3000) + (these are the odds that player 3 chooses randomly so that player 4 has a larger region to steal than yours)
(1/2)(2/2999)(1001/3000) + (these are the odds that player 3 chooses 998 or 1002, which offer a tie for player 4, and that player 4 does not steal your region.)
(1/2)(2/2999)(1/3000) + (these are the odds that player 3 chooses 998 or 1002 and player 4 steals your region)
(3/2999)(1/3000) + (these are the odds that player 3 chooses 999, 1000, or 1001, which leaves you with the largest region for 4 to steal)
(1/2999)(1000/3000) +
(1/2999)(999/3000)+
... +
(1/2999)(1/3000) =
0.2775924 chance of winning.

So increasing your region at the risk of being stolen by #4 is not worth it.

Player 2's strategy will be to take the top 1/3 of the largest region (adding one to the $ value and rounding down) if the smaller region is less than 1/3 of the largest region; take the smaller region if it is between 1/3 and 1/2 of the larger region, and take the top $1000 of the larger region if the smaller region is more than 1/2 of the larger region. For example:
Player 1 chooses $600: Smaller region is 599, larger region is 2400; You choose $2201.
Player 1 chooses $900: Smaller region is 899, larger region is 2100; You choose $1.
Player 1 chooses $1200: Smaller region is 1199, larger region is 1800; You choose $2001.

This guarantees that you get the maximum possible region so that it is impossible for player 4 to gain from stealing your region.

#1:

Spoiler:

$2251 guarantees that you will not get stolen from player 4, but I'm not certain that having two random guessers will have the same effect on your odds as having 1 if you drop to $2250. It's a lot of calculations that I'm working on right now. I'll post my results when I get them.

(edited to fix my ratio error)