3
$\begingroup$

We had left the TV on after the news finished and on came the Monopoly Millionaire's Club. I had no knowledge of its existence and watched some out of curiosity. The particular game in question was No Vacancy. The gameplay is fairly straightforward:

  1. The player has a hotel with 21 rooms divided evenly among 3 floors so that each floor has 7 rooms.
  2. Each turn, 5 cars appear in front of the hotel. Each car holds between 1 and 5 people, inclusive. (It is not specified whether or not each number is represented or if every car is assigned randomly and independently of each other.) (The cars are refreshed every turn so the cars you didn't pick disappear and new ones come in. I.E., the cars you've already picked have no bearing on what cars you can pick next.)
  3. The player picks one of the cars and is then told how many people are in the car.
  4. The player must give each person in the car a room in the hotel and they must all be on the same floor.
  5. Filling rooms on the first floor yields \$1,000 each, the second yields \$2,000 each, and the third yields \$3,000 each. (Yes, these are very expensive rooms.)
  6. Once every floor has at least 3 people, the player can quit after any turn and take what money is earned thus far.
  7. If ever the player is unable to place everyone from the car on the same floor, the game ends and the player receives nothing.
  8. If every room is filled, the player receives \$100,000.

Now, given that the entire game is electronic, it would be easy for the house to force every player to lose by simply spamming every vehicle as having 5 passengers. Let us presume, though, that the producers are not out to steal hope from their contestants. Even with that, though, it struck me as being much more about chance than strategy despite all the dramatic music and lighting - combined with the dramatic host - indicating that strategy was key.

If you play perfectly, how much can you expect to win on average?

Does it matter if each car is random vs. all five cars holding every number from 1 to 5?

$\endgroup$
  • $\begingroup$ I'd say that the random car passengers vs one with each of 1 - 5 passengers is a major difference. In the case of the cars holding each of 1-5 passengers, You would always end up with the top two floors filled (top floor is the 5 & 2 cars, middle is the 4 & 3 cars, bottom is the 1 car) and the player always wins! $\endgroup$ – nurdyguy Aug 10 '15 at 21:47
  • $\begingroup$ Are the cars refreshed every time you pick a car? If so, it can't matter whether the cars for each turn are independent or hold 1-5, because either way every car you pick is 1-5 with equal probability. $\endgroup$ – f'' Aug 11 '15 at 15:01
  • $\begingroup$ Is the \$100,000 in addition to the \$42,000 you'd get for filling every room? $\endgroup$ – 2012rcampion Aug 11 '15 at 15:24
  • $\begingroup$ @2012rcampion It is not clearly stated but I believe the answer is no. The contestant either chooses to stop and take those winnings, fail and get nothing, or finish and get \$100,000. $\endgroup$ – Engineer Toast Aug 11 '15 at 15:53
  • 2
    $\begingroup$ @EngineerToast It doesn't make a difference whether the cars are assigned before or after you make your pick, right? So if the cars are independently random, when you choose one, it's equally likely to be 1-5, just as if they are all different. $\endgroup$ – f'' Aug 11 '15 at 16:16
6
$\begingroup$

If passenger counts from 1 to 5 are equally distributed, it's possible to compute for each of the 343 (7x7x7) possible population distributions the expected value if one stands pat and if one takes another car (the stand-pat case is easy; for the take-another car case, figure out for each passenger count 1-5 which of the three possible resulting distributions would be the best, and then take the average of the best values from those five passenger counts).

If I figured the math right, that would yield an expected value of $37,480 starting with all rooms empty (all expected values rounded to the nearest dollar). In this table, the two numbers in the row heading show the number of occupied rooms on the first two floors; the column headings give the number of occupied rooms on the third floor. The cells marked with "**" indicate the expected value from betting; those without asterisks indicate the expected value from standing pat (when it's higher than that from betting). Cells marked with dashes indicate combinations that won't arise when using an optimal strategy. Looking at the table, there's no apparent pattern for what moves are optimal. For example, if the first car has 1, 2, 3, or 5 people in it, they should be placed on the top floor, but if it has exactly four they should go on the second floor--a result that's far from intuitively obvious. I'm not sure how well a naïve strategy would do, but the optimal strategy yields a result which is better than 37% of the maximum value. I'm not sure how the expected value using optimal strategy compares with what the expected value would be if the player knew car capacities in advance.

         0        1        2        3        4        5        6        7
0 0: 37480**  38370**  40128**  38014**  -----    35153**  36910**  39856** 
0 1: -----    -----    -----    38543**  -----    -----    36843**  40564** 
0 2: -----    39658**  40945**  40433**  -----    38576**  39321**  43320** 
0 3: -----    38259**  40520**  -----    -----    34348**  36099**  39678** 
0 4: 35734**  36893**  39069**  -----    -----    32844**  34855**  38105** 
0 5: -----    -----    -----    34327**  -----    31807**  34418**  37614** 
0 6: -----    36154**  39222**  35625**  -----    33700**  35582**  39238** 
0 7: 38728**  39545**  42685**  38769**  -----    36262**  38478**  43832** 

1 0: -----    -----    40179**  -----    -----    -----    -----    40404** 
1 1: -----    -----    -----    -----    -----    -----    -----    -----   
1 2: -----    -----    40505**  39800**  -----    37976**  38689**  42889** 
1 3: -----    -----    39924**  -----    -----    -----    -----    39471** 
1 4: -----    -----    39046**  -----    -----    -----    -----    38454** 
1 5: -----    -----    38343**  -----    -----    -----    -----    38478** 
1 6: -----    -----    38536**  -----    -----    -----    -----    38672** 
1 7: -----    -----    42182**  38489**  -----    37006**  37872**  43360** 

2 0: -----    -----    41017**  -----    -----    -----    -----    42729** 
2 1: -----    -----    40641**  39251**  -----    37331**  38047**  42392** 
2 2: -----    -----    40701**  40957**  39599**  38785**  39182**  44212** 
2 3: -----    38977**  41090**  -----    -----    -----    37759**  43846** 
2 4: -----    38152**  39922**  -----    -----    35321**  36694**  41238** 
2 5: -----    37217**  39100**  -----    34769**  34150**  36718**  41032** 
2 6: -----    37473**  39086**  37529**  35808**  36006**  36672**  41360** 
2 7: -----    41348**  43493**  43008**  40006**  39672**  40560**  52800** 

3 0: -----    -----    -----    -----    -----    -----    -----    -----   
3 1: -----    -----    -----    -----    -----    -----    35248**  39349** 
3 2: -----    38790**  40514**  -----    37569**  37630**  38216**  43817** 
3 3: -----    -----    -----    -----    -----    -----    -----    -----   
3 4: -----    -----    -----    -----    -----    -----    -----    -----   
3 5: -----    -----    -----    -----    -----    28000    31000    34000   
3 6: -----    34320**  37923**  -----    -----    30000    33000    36000   
3 7: -----    38059**  42956**  -----    29200**  32000    35000    44000** 

4 0: -----    -----    -----    -----    -----    -----    -----    -----   
4 1: -----    -----    -----    -----    -----    -----    34775**  38521** 
4 2: -----    -----    39668**  -----    -----    36349**  37411**  41848** 
4 3: -----    -----    -----    -----    -----    -----    -----    -----   
4 4: 31137**  32718**  35585**  -----    24000    27000    30000    33000   
4 5: -----    -----    36784**  -----    -----    29000    32000    35000   
4 6: -----    33851**  37180**  -----    -----    31000    34000    37000   
4 7: 36379**  37156**  40963**  -----    30000    33000    36000    39000   

5 0: -----    -----    -----    -----    -----    -----    -----    -----   
5 1: -----    -----    -----    -----    -----    -----    34539**  38168** 
5 2: -----    37244**  38753**  -----    35150**  34852**  37056**  41206** 
5 3: -----    -----    -----    -----    -----    26000    29000    32000   
5 4: -----    -----    36136**  -----    -----    28000    31000    34000   
5 5: -----    -----    35172**  25210**  -----    30000    33000    36000   
5 6: -----    33468**  36723**  27008**  29000    32000    35000    38000   
5 7: -----    36523**  40136**  30040**  31000    34000    37000    40000   

6 0: -----    -----    -----    -----    -----    -----    -----    -----   
6 1: -----    -----    -----    -----    -----    -----    33825**  37126** 
6 2: -----    -----    38227**  -----    35558**  35632**  36134**  40672** 
6 3: -----    -----    -----    -----    -----    -----    30000    33000   
6 4: -----    -----    36213**  -----    -----    29000    32000    35000   
6 5: -----    -----    36011**  -----    28000    31000    34000    37000   
6 6: -----    32459**  35456**  27840**  30000    33000    36000    39000   
6 7: -----    35336**  39280**  31200**  32000    35000    38000    41000   

7 0: -----    -----    -----    -----    -----    -----    -----    41958** 
7 1: -----    -----    -----    -----    -----    -----    35526**  41632** 
7 2: -----    40407**  42104**  41980**  38984**  38486**  39072**  51360** 
7 3: -----    -----    -----    -----    -----    -----    31000    42800** 
7 4: -----    -----    39331**  -----    -----    30000    33000    36000   
7 5: -----    -----    38776**  -----    29000    32000    35000    38000   
7 6: -----    34616**  38480**  30600**  31000    34000    37000    40000   
7 7: 40776**  40480**  50400**  42000**  35000**  36000    39000    100000   

Incidentally, although the game would allow a contestant to stop with only three occupants on each floor, the only situation where a contestant who is playing optimally would be in any "danger" without at least four occupants on every floor would have five occupants on each of two floors, and three on the other. A player who is using optimal strategy may have such a situation arise with the three occupants on any floor. If the three occupants are on one of the lower floors, the player should stand pat with an expected value of \$26,000 or \$28,000. If the three occupants are on the top floor, standing pat would have an expected value of \$24,000 but continuing on would--despite the risk--have an expected value of \$25,210.

$\endgroup$
  • 1
    $\begingroup$ I wrote a program to solve this and got the same answer ($37,479.84). $\endgroup$ – f'' Aug 11 '15 at 16:55
  • $\begingroup$ @f'': My table was correct; my description of it was wrong (now fixed); row "4 0" has an empty column 0, but row "0 4" has $35,734" in that column. Otherwise, how do you like the table? Any suggested improvements? $\endgroup$ – supercat Aug 11 '15 at 17:29
  • $\begingroup$ As far as naive strategies go, "take a car unless you have at least 3 on every floor" gives \$36,859. "Take a car unless you have at least 4 on every floor" is better than that, at \$37,180. $\endgroup$ – f'' Aug 11 '15 at 17:44
  • $\begingroup$ @f'': It's interesting that such a simple strategy for choosing whether or not to proceed is so close to optimal, but is that still being combined with an optimal strategy for placing people? What if you simplify both? $\endgroup$ – supercat Aug 11 '15 at 17:50
  • $\begingroup$ Oops, I forgot to make an assumption about where people were being placed and let it optimize automatically. I'll recalculate with some simple placement strategies. $\endgroup$ – f'' Aug 11 '15 at 18:15
1
$\begingroup$

If the number of people in a car you pick is evenly distributed between 1 and 5, on average a car will have 3 people, or that any two cars on average will have 6 people.

So, most of the time, you'll have 6 people on each floor, for $36,000 total.

For a strategy, I would fill floors from the top, until there are 3 or fewer rooms left (average car). Then I would move to the next floor unless there is a gap above it that it perfectly fits. Fill until 3 or fewer rooms. At that point, if you can get the top to 1 or 0, do that. Otherwise, go to the bottom row.

$\endgroup$
  • $\begingroup$ I feel like the risk of losing all your money if those vacancies aren't there will temper the average a bit. $\endgroup$ – Joe Z. Aug 11 '15 at 1:28
0
$\begingroup$

It struck me that it's always possible to guarantee a nonzero amount of money won - follow the strategy that if any floor has two or fewer occupants, pick a car and give rooms to the people in that car. Stand pat as soon as all floors have at least three occupants.

This works because any floor with at most two people always has at least five vacancies, and so can always accommodate another carful of people.

This may not be an optimal expected value, but it does give at least $18,000 in the worst case, which is quite a lot of money.

$\endgroup$
  • $\begingroup$ When filling the 2nd floor to 3 people, couldn't you be filling the 3rd floor instead? $\endgroup$ – JonTheMon Aug 11 '15 at 13:02
  • $\begingroup$ aka, wouldn't the worst cast safe scenario be 4-4-4? $\endgroup$ – JonTheMon Aug 11 '15 at 13:16
  • $\begingroup$ @JonTheMon: If the first three cars have four people, one would have no choice but to place them as 4-4-4, whereupon optimal strategy would be to stand pat for \$24,000. If the first car has three people, optimal strategy would be to put it on the \$3,000 floor; if the next two have five, standing pat with 5-5-3 would also yield \$24,000 but the expected value of continuing would be \$25,210. $\endgroup$ – supercat Aug 11 '15 at 17:17
  • 1
    $\begingroup$ @JoeZ.: Either 4-4-4 or 5-5-3 (with three on the highest-dollar floor) are the two lowest-dollar cases where a good strategy would reach danger. If you look at the table above, you'll notice that column 3 of rows 3-0 through 3-7 is vacant, row 3-3 is vacant, and column 3 of rows 0-3, 1-3, 2-3, etc. through 7-3 are vacant. If the first two cars had three people each and one placed them in the upper two floors, one might then get stuck with 5-3-3 worth only \$20,000, but having placed the first carload on the top floor there would be no reason not to place the second one there as well. $\endgroup$ – supercat Aug 11 '15 at 17:39
  • 1
    $\begingroup$ @Taemyr: Interesting question. Changing the loss payout from 0 to -1000000 reduces the initial expected value to \$36,859, and means that the optimal first move will be to place any number of passengers on the top floor (if the loss payout is zero, best expected value would be obtained by putting an initial four-passenger load on the second floor). $\endgroup$ – supercat Aug 12 '15 at 15:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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