Imagine the following game:

10,000 players each receive the same 64-color pack of crayons. Each of those crayon colors is secretly and randomly assigned a value 1-64. The object of the game is simple: each player chooses 10 crayons, and whichever player (or players) have the highest total value among their crayons is a winner. Ties are irrelevant; if nobody outscores you, you win.

The catch is this: you get to choose your crayons last, and you get to see how popular each color was as a choice as a percentage among your opponents. The percentages you see vary from near 0% up to 30% at the high end for the most popular colors like red.

Do you choose the most popular colors or the least popular colors? Is there any strategy you can use to gain an advantage from your information?

What do you mean by win? Could this mean you receive a fixed sum of money? And each winner gets that same amount? Or is that fixed sum of money divided up when there is more than 1 winner? When each of 64 crayons is assigned a number in the range 1 to 64, is that number unique to that crayon or can more than 1 crayon have the same number assigned to it?

Once you have settled on the precise rules, the thing to do is to write a sim where each of your suggested strats is tried out to see how they do and proceed from there.

Another route to solution would be to simplify the problem to something like 5 crayon colors (rather than 64) and each of 3 players (rather than 10000) choosing 2 (rather than 10) of them. Then you could use what you learn to solve the larger version.

I would probably combine both approaches.

Good luck.

Thanks for the reply, Gilbert. I wanted to make it clear that you would not be penalized for ties. If you like, all winners get an apple, no matter how many winners there are.

My analysis of the smallest version of the game: You and I choose day or night, and I know ahead of time that 100% of my opponents chose day. I will always win by choosing day, and my information was obviously helpful.

I will also clarify that each crayon has a unique number 1-64.

It's really unclear. Obviously you duplicate one entry if there is only one entry, but if, for example, you knew that everybody picked 10 out of the same 11 crayons in various combinations, and presumably all combos were covered given 10000 people picking, then if you pick one of those combos, you have a 1 in 11 chance of winning, while if you picked random crayons, you appear to be around 38%ish. And if 9999 people picked 10 out of 11, and one person picked something with totally different crayons, you would obviously duplicate the unique entry. So you both A) want to duplicate somebody and B) want to avoid near-duplication.

If crayon values are random, and everyone gets their own independent pack, why would any strategy have an advantage over any other? Your score and your chance to win seems completely random. What am I missing?

He is asking if there is indeed some strategic value in knowing everyone else's choices.

I presume there is.

Toy examples can surely be found (as RGibert and TomCowley suggest).

Edit: All boxes are the same. All crayon values are the same across people.

Given the conditions in the OP, there can't be any value unless we add new assumptions (which may be happening inadvertently in these replies). This seems trivially obvious to me. I guess I'll feel stupid when somone points out the condition I failed to notice or misinterpreted.

Unless I am totally misunderstanding, there is clearly value in knowing your opponents' choices in the following situations.

-----

Consider 3 crayons, 2 opponents, and everybody chooses 2 crayons. Then there are clearly two cases to consider.

Case 1: Opponents choose the exact same two crayons.

It is obvious that my optimal strategy is to choose those exact two crayons.

Case 2: Opponents choose different two crayons (with one in common, of course).

It is easy to show that my optimal strategy in this case is to choose to duplicate one of my opponents' choices.

In both cases I win more than random choices would yield.

-----

Consider 4 crayons, 2 opponents, and everybody chooses 2 crayons. Then there are clearly three cases to consider.

Case 1: Opponents choose the exact same two crayons.

It is obvious that my optimal strategy is to choose those exact two crayons.

Case 2: Opponents choose different two crayons but with one in common.

It is easy to show that my optimal strategy in this case is to choose to duplicate one of my opponents' choices.

Case 3: Opponents choose two completely different crayons.

It is easy to show that my optimal strategy in this case is to choose to duplicate one of my opponents' choices.

In all three cases I win more than random choices would yield.

-----

In more complicated cases I imagine that there is still some value to be had, though the cases get trickier when the number of crayons, number of opponents, and number of crayons to choose gets more complicated.

I coded up slightly more complex cases in order to see if any optimal strategies involve choosing crayons NOT chosen by the others (so far all optimal strategies consisted of duplicating an opponent's choices).

-----

Consider 5 crayons, 3 opponents, and everybody chooses 2 crayons. I think there are seven cases to consider. Let me label the crayons ABCDE. What follows is the opponents' choices and then my optimal strategy (sometimes more than one option is included in the optimal strategy).

Case 1: {AB, AB, AB} => AB

Case 2: {AB, AB, AC} => AB or AC

Case 3: {AB, AB, CD} => AB or CD

Case 4: {AB, AC, AD} => BE or CE or DE

Case 5: {AB, AC, BD} => AC or BD

Case 6: {AB, AC, BC} => DE

Case 7: {AB, AC, DE} => DE

You will see that choosing away from your opponents' choices starts to enter in here. See Case 6 for the extreme.

P.S. In re-reading OP I see that he says that you are only told what percent of people chose each color, not the details of each of your opponents' choices. Dear Lord. I will have to do a wee re-think.

Okay, under the assumption that you are only given the number of opponents who have chosen each color crayon (not the detailed choices of each opponent), I have had to revise my previous situation as follows.

-----

Consider 5 crayons, 3 opponents, and everybody chooses 2 crayons.

I think there are six cases to consider. Let me describe each case by the number of opponents who chose each color. Of course, all that matters is the number and not the identity of the color (in essence, only the order of the counts matter).

Case 1: {33000} => 33 (meaning that you choose as your colors the two colors that were chosen by 3 opponents each)

This strategy wins 100% of the time whereas a random strategy would win 58% of the time in this case.

Case 2: {32100} => 32 or 31

This strategy wins 50% of the time whereas a random strategy would win 41.666% of the time in this case.

Case 3: {31110} => 31

This strategy wins 36.666% of the time whereas a random strategy would win 33% of the time in this case.

Case 4: {22200} => 00

This strategy wins 40% of the time whereas a random strategy would win 33% of the time in this case.

Case 5: {22110} => 10

This strategy wins 34.666% of the time whereas a random strategy would win 31.666% of the time in this case.

Case 6: {21111} => 21

This strategy wins 28.333% of the time whereas a random strategy would win 27.666% of the time in this case.

-----

Overall, combining all cases above by using their respective frequencies, the optimal strategy will win 37.50% of the time whereas a random strategy will win 33.25% of the time.

I hope this makes sense and I hope I didn't make any silly errors.

Thanks for the responses, everyone.

I think my attempt to sweep ties under the rug has done more harm than good. I didn't really want to consider them, but the obvious consequence of my stipulation is that there is equity to be gained by duplicating opponents. I think we would all agree that the strategic implications of ties, however we choose to handle them, can be substantial with smaller numbers, but are nearly irrelevant with large numbers like those suggested in the OP?

I am really curious about whether this effect persists with larger numbers (and if so how strong it is). I may work on a code based solution myself, and if so I will update the thread.

It's not that explicit perhaps, but the deal appears to be that each color has a random unknown value but that it's the same across boxes. My cerulean blue has the same number yours does, but neither of us knows what that number is.

I get that. Crayons have value 1-64 and you choose 10, so you are going to have a random point value of from a low of (1..10)=55 up to a maximum possible of (55..64)=595. So the net result is that each player is simply getting a random score of 55 to 595. The game would be exactly the same using an RNG and each player just getting their final number, and the crayon choices are totally irrelevant since they are unknown. It's just a mechanical RNG. It also doesn't matter if the crayon values are unique (all numbers 1-64 get used) or not, which was not specified.

So your choice of crayons has a random effect on your score, whether you know all the other player's choices or not. The big assumption here is that you don't get to know the other players' scores until after you have made your own selection, but the rules seem to say that (and the game would be pointless otherwise, you would almost always be able to win). So your final point value is still random. And no strategy of selection can make it non-random.

This is like saying, let's each draw blind for high card from our own standard deck of cards. I get to see your draw first before I draw mine, but I still have to draw mine without looking (random). How do I use that information to improve my draw? I can't.

I must still be missing something in the rules.

You can't change your score expectation- you're obviously drawing from a fixed distribution with a mean of 325 no matter what you pick- but you can definitely change the odds that your score is the highest score (or tied for the highest score) by correlating and uncorrelating your picks as described above.

Crayon 1 = 1
Crayon 2 = 2
Crayon 3 = 3

Opponent picks (1,2), (1,3)
Your pick (1, rand) = 50% win
Your pick (2,3) = win
So here you have a 2/3 chance of winning.

Opponent picks (1,2), (2,3)
Your pick (1, rand) = 50% win
Your pick (1,3) = loss
So 1/3 chance

Opponent picks (1,3), (2,3)
Your pick (3,rand) = 50%
Your pick (1,2) = loss
So 1/3 chance

Overall, picking the duplicate of your opponents will give you 50%, whereas not picking the duplicate will give you 33.33%

You seem to be the only one not catching on here.

Consider a similar game in which a "dealer" chooses a suit at random and four "players" each chooses a suit. The goal is to choose the same suit as the dealer. If N players choose the same suit, they each win P/N (where P is the prize). For what follows, suppose P=120 to make the numbers easier.

Of course, if nobody can see the other players' choices, this is a pure random game like you describe, and is not very interesting since there is no strategy involved.

However, tweak the rules to allow one player to choose his suit after the other three players have revealed their suits. Then strategy enters (which I hope is obvious).

Suppose your three opponents have collectively chosen three different suits. Then it should be obvious that your best strategy is to choose the fourth suit. If you are correct, you win 120. You will be correct one-fourth of the time so your expected value is 120/4=30.

If you choose another suit and are correct, you will win 120/2=60. Again, you will be correct one-fourth of the time so in this case your expected value is (120/2)/4=15.

In these small sample games, how you break ties can affect your strategy (as OP admits). But surely underlying strategy still exists, no matter how you break ties or even if ties are insignificant either by rule or by probability (many crayons, many opponents, many choices).

In the simple game above, if the rules are that a player only wins the prize if he is the only one to match suits with the dealer, strategy also exists (as is obvious again).

To summarize, I think it is clear that these types of games can allow strategic value to the person going last if he knows his opponents' choices (either individually or collectively).

The rules in the OP's game seem to be that every winner gets P, not P/N. So we don't care how many other winners there are.

And that was confirmed in post #3. We don't care if other people win, we still get our full prize regardless.

Hey, I was just trying to make it easier for you to see that strategy applies here no matter how ties are broken.

That's what I get for trying to be nice.

Sorry, I wasn't trying to be rude, but the P/N was a misdirection that doesn't apply to this game and so I didn't know if that was the source of disagreement.

I now get the idea of why the correlation between your choice and the other players matters. Simplified, if someone has the same choices as you, they can't beat you. To beat you they need different choices than you. But you have the advantage of going last with the knowledge of their choices.

Sorry for being dense.

Here is a slightly more complex case with interesting results.

8 opponents
7 crayons
3 picks

Opponents pick randomly. I looked at a situation in which crayon counts were [7,5,4,3,2,2,1]. This gives a good spread with some high counts and some low counts.

Optimal strategy in this case, with the original OP tie rules, is for me to choose (721). So I choose the highest chosen color, the lowest chosen, and one of the other next-lowest chosen.

If we change the tie rules so that ties count for nothing, then it is optimal for me to choose (221), the three lowest chosen colors.

So, as people have suggested, the tie rule can affect the strategies. We see when ties are equivalent to winning (the whole prize), then it is sometimes optimal to choose colors that many opponents have chosen. Sort of a way to cover that side of the bet. When ties get you nothing, then that aspect of the strategy can dissipate and the optimal can be to choose the least chosen colors.

Of course, deriving the optimal strategy is most easily accomplished with small cases (opponents, crayons, choice possibilities). In large cases, the tie aspect surely diminishes. But it appears to be an open question whether choosing the most or least chosen colors will be optimal (or what mix of the two) and, I presume, it will be affected by the tie-breaking rule.

Edit: Just saw NewOldGuy's post. No problem man. I wasn't trying to be a jerk about it.

Here is an ever-so-slightly more complex case with interesting results.

8 opponents
8 crayons
3 picks

Opponents pick randomly. I looked at a situation in which opponent crayon counts were [66522210]. This gives a good spread with some high counts and some low counts.

Optimal strategy in this case, with the original OP tie rules (tie=win), is for me to choose (210). So I choose the two least-chosen colors and one of the next-least-chosen colors.

If we change the tie rules so that ties count for nothing (tie=loss), then it is also optimal for me to choose (210), essentially the three lowest chosen colors.

Limited though these small-number situations are (since the problem gets very large very quickly), we may have uncovered some insight with this example. Of course, this so-called insight is probably obvious to most.

It appears that in this example the "state space" may be sufficiently sparse so that the innate value in "matching" your opponent choices may be sufficiently dissipated so that the value in "mapping out new territory" dominates. And this is true in both extreme tie-breaking regimes.

So, just based upon the results so far, I am definitely leaning toward the optimal strategy in generic "large" cases to be significantly made up of choosing colors which were least chosen by your opponents.

I think this is likely right outside of pathological cases (like my 9999+1), and I think that if you divide ties instead of ties win for everybody, and add the assumption that for each other player, that each of the 10 crayons they pick are independent of anything else they've already picked and are drawing from the same distribution (other than picking without replacement obviously), that it's never wrong to pick the least used.

While I agree with these general sentiments, and since I have all of the small-numbered situations already coded up, it was easy for me to check this conjecture.

Here is a counter-example (there are several others). Consider 5 crayons, 3 opponents, and 2 picks. Suppose opponents choose {(12), (12), (13)} and we are told each of our opponents' choices.

Then let's examine the optimal strategies under the three different tie-breaking regimes.

(1) Tie=Win. Then optimal to choose (12) or (13). Basically, there is great value in duplicating an opponent's choices when a tie is equivalent to a win in a small-numbered example like this.

(2) Tie=Loss. Then optimal to choose (14), (15), or (23). Note that (45), the case of choosing the least-chosen colors, is the eighth-best strategy. In the case of choosing (45) you are "too far in a corner" for it to be optimal, even when you have to win outright.

(3) Tie=Shared Win. Then optimal to choose (24) or (25). I admit that this is a little strange to me. (24) and (25) are a smidge higher-valued than (34) and (35), and all of them are a little higher-valued than (45). Note (14), (15), and (23) are a little bit behind (45) in this case of shared wins.

Mind-blown. Very nice post.