a game theory problem

godelproof · #1 $Old$ June 22nd, 2009, 09:10 PM

2N (N>=1) players play a game: each player wears a hat that's either red or blue. Each player can see all the other 2N-1 players' hats but can not see his own hat. The game rule forbids any form of signaling between players during the game. But before the game (before they are put on hats), players can discuss and thus adopt some form of strategy. When the game begins, all players are required to report the color of his own hat simultaneously.

prove: there does not exist a strategy whatsoever that will guarantee at least N+1 players always report correctly in all possible situations.

(i have a proof based on the limit of some probability. but it seems to me that such a proof relies on one's intuitive understanding of probability. i don't know if someone knows a better proof)

Laurent · #2 $Old$ June 24th, 2009, 04:59 PM

Quote:

Originally Posted by godelproof $View Post$

2N (N>=1) players play a game: each player wears a hat that's either red or blue. Each player can see all the other 2N-1 players' hats but can not see his own hat. The game rule forbids any form of signaling between players during the game. But before the game (before they are put on hats), players can discuss and thus adopt some form of strategy. When the game begins, all players are required to report the color of his own hat simultaneously.

prove: there does not exist a strategy whatsoever that will guarantee at least N+1 players always report correctly in all possible situations.

(i have a proof based on the limit of some probability. but it seems to me that such a proof relies on one's intuitive understanding of probability. i don't know if someone knows a better proof)

Do you really have a rigorous proof involving probability ? If the players answer at random, it doesn't help since it may very well happen that all players fail, however unlikely this is.

I found a solution. The idea is simple, but it is a bit complicated to turn it into a quite rigorous proof (it is very tempting to take some things for self-evident about what strategy should be better...). I'm going to give you the main idea, and provide a complete proof afterward (because I was so proud of it!

)

--------------

Here's the hint. The idea is to compare two situation: A) "N blue, N red", and B) "N+1 blue, N-1 red". In situation A), each player sees N-1 hats of one color, and N of the other colour, and their own colour is the one with N-1 hats. In situation B), N+1 players see N hats of one colour and N-1 of the other colour, and their own colour is the one with N hats (so that's the contrary to before). (and there are N-1 other players)
A strategy is a way for each player to decide what to answer when he sees some number of red and blue hats. Suppose each player decides that, if he sees N hats of one colour, he answers this colour. Then N+1 players win in situation B, but all players lose in situation A... On the other hand, if each player decides that, if he sees N hats of one colours, he answers the other colour, then all win in situation A, but N+1 lose in situation B hence at most N-1 win.
The difficulty for a complete proof is that the strategy may a priori depend on the player...

-----

Now for the proof, fully rigorously. Assume by contradiction that there is a strategy for which at least N+1 players win in any configuration. Take a team of 2N players who apply this strategy.

Consider the first situation: Put N hats of each colour on the heads of the players. Let's say a number A of red hat players answer right (according to their strategy). That means that their strategy tells them: "If you see N-1 red hats, answer red". In the same way, a number B of blue hat players answer right. We have $A+B\geq N+1$ by assumption on the strategy.

Now (for the same players) switch the colors of the hats (between blue/red) and play again. Then A' blue hat (ex red hat) players answer right, and B' red hat (ex blue hat) players answer right, with $A'+B'\geq N+1$ .

We have $(A+B')+(A'+B)\geq N+2$ , hence either $A+B'\geq N+1$ or $A'+B\geq N+1$ . In other words,there is a colour C (either red or blue) for which at least N+1 players answer C if they see N-1 hats of colour C.

Denote by C' the colour different from colour C, and consider the following experiment: put hats of colour C' on N+1 players among the latters (i.e. the ones who answer C if they see N-1 hats of colour C), and hats of colour C on the N-1 other players. What happens? The first N+1 players will see N hats of colour C', and N-1 hats of colour C. Due to the way these players were selected, they will answer C, which is not their own colour. Therefore, at least these N+1 players will lose. Hence at most N-1 will win. This contradicts the initial assumption.

As a conclusion, no strategy allows in any situation at least N+1 players to win. QED.

-----------------

Remark: We know now that it is not possible to make at least N+1 players win every time. But conversely, is there a strategy for which at least N players win in any situation? This should be a simpler question, but I can't find it (and, well, it's almost 1 o'clock in the morning...).

An obvious strategy would be: "Answer the colour that appears more often". This strategy will make more than N winners if there are more hats of one colour (the players with the dominant colour win). But it will completely fail if there are equally many red and blue hats... This is the same problem as above.

Any idea welcome !!

Laurent · #3 $Old$ June 24th, 2009, 06:17 PM

Quote:

Originally Posted by Laurent $View Post$

Remark: We know now that it is not possible to make at least N+1 players win every time. But conversely, is there a strategy for which at least N players win in any situation? This should be a simpler question, but I can't find it (and, well, it's almost 1 o'clock in the morning...).

I couldn't sleep with this problem in mind...

This seems pretty weird: the players know the colors of the other players, but they know absolutely nothing about their own color (since they can't benefit from information from other players). It seems impossible to do better than random choice, which doesn't guarantee any minimum number of winners...

Yet it can be done.

You may want to think about it for yourself before you open the following box:

Spoiler:

godelproof · #4 $Old$ June 24th, 2009, 10:28 PM

thanks Laurent!

I tried hard to utilize the assymmetry of the problem (N+1 out of 2N) to find some kind of "switching" that would lead me to a contradiction but couldn't make it. Your construction is creative and genius!

However, there is something which i haven't quite thought through, but still risk to say. I'd say your proof is absolutely rigorous and consistent up to your definition of "strategy". For 2N players, code them from 1 to 2N. I'd like to define a strategy of a player i as a function Fi that maps the states of hats' colors CONTINGENT ON THE CODING. For if there is no coding, how will you be able to adopt a strategy like the one that guarantees N players always report correctly?

Laurent · #5 $Old$ June 25th, 2009, 03:52 AM

Quote:

Originally Posted by godelproof $View Post$

thanks Laurent!

I tried hard to utilize the assymmetry of the problem (N+1 out of 2N) to find some kind of "switching" that would lead me to a contradiction but couldn't make it. Your construction is creative and genius!

However, there is something which i haven't quite thought through, but still risk to say. I'd say your proof is absolutely rigorous and consistent up to your definition of "strategy". For 2N players, code them from 1 to 2N. I'd like to define a strategy of a player i as a function Fi that maps the states of hats' colors CONTINGENT ON THE CODING. For if there is no coding, how will you be able to adopt a strategy like the one that guarantees N players always report correctly?

Yes, indeed: any strategy would actually consist in assigning each player a number (from 1 to 2N) and a function like you said, which may involve the players numbers.

godelproof · #6 $Old$ June 25th, 2009, 10:06 AM

Quote:

Originally Posted by Laurent $View Post$

Yes, indeed: any strategy would actually consist in assigning each player a number (from 1 to 2N) and a function like you said, which may involve the players numbers.

you proved a subset of the set of all strategies (i.e.,the strategies that don't require a coding to work out) . Today i thought of another proof, which is rigorous and much simpler, but far less ingenious than yours. If you want to see it, i can post it.

Another thing, i'd like to know your opinion on a probabilistic proof. Its idea is very simple: 1/2 (independent) probability to put on red hat on every one. Then the expectation of numbers of players win is N for any strategy (easy to verify!). If there is a strategy that guarantees at least N+1 players always win, then the expectation should be no less than N+1, which is a contradiction. Do you think such a proof is acceptable? Well i feel very uncomfortable with it. but i can give no clear reasons to object it.

Laurent · #7 $Old$ June 25th, 2009, 02:05 PM

Quote:

Originally Posted by godelproof $View Post$

you proved a subset of the set of all strategies (i.e.,the strategies that don't require a coding to work out) .

Now I understand your point: indeed I assumed implicitly that the decisions of the player only depend on the number of coloured hats they see. And the strategy I gave for N winners doesn't fit into this scheme... So my proof isn't very satisfying after all...

Quote:

Today i thought of another proof, which is rigorous and much simpler, but far less ingenious than yours. If you want to see it, i can post it.

Sure I'd like to! I guess it looks like the one at the end of this post...

Quote:

Another thing, i'd like to know your opinion on a probabilistic proof. Its idea is very simple: 1/2 (independent) probability to put on red hat on every one. Then the expectation of numbers of players win is N for any strategy (easy to verify!). If there is a strategy that guarantees at least N+1 players always win, then the expectation should be no less than N+1, which is a contradiction. Do you think such a proof is acceptable? Well i feel very uncomfortable with it. but i can give no clear reasons to object it.

That looks clever! Let me give a try at writing a clean proof:

For $1\leq i\leq 2N$ , let $F_i$ be a function that defines a strategy for player $i$ , i.e. $F_i:\{R,B\}^{2N}\to\{R,B\}$ is any function that does not depend on the $i$ -th coordinate.

Let $X=(X_i)_{1\leq i\leq N}$ be a vector of independent r.v. with $P(X_i=R)=P(X_i=B)=1/2$ . The number of winners in configuration $X$ is $W(X)=\sum_{i=1}^{2N}{\bf 1}_{(F_i(X)=X_i)}$ .

Since $F_i(X)$ depends only on $(X_j)_{j\neq i}$ , which is independent of $X_i$ , $P(F_i(X)=X_i)=E[P(F_i(X)=X_i)|(X_j)_{j\neq i}]=1/2$ . Therefore, the expected number of winners is $E[W(X)]=\sum_{i=1}^{2N} P(F_i(X)=X_i)=N$ .

If the functions $F_1,\ldots,F_{2N}$ could be chosen in such a way that $W(x)\geq N+1$ for any $x\in\{R,B\}^{2N}$ , then we would have $W(X)\geq N+1$ a.s. hence $E[W(X)]\geq N+1$ , contradicting the previous paragraph.

-------

One could also write the exact same proof without random variables, which may look more convincing. We have (keeping notations):

$\sum_{X\in\{R,B\}^{2N}}W(X)= \sum_{i=1}^{2N} \sum_{X\in\{R,B\}^{2N}} {\bf 1}_{(F_i(X)=X_i)}$ $= \sum_{i=1}^{2N} \sum_{(X_j)_{j\neq i}\in\{R,B\}^{2N-1}} ({\bf 1}_{(F_i(X)=R)}+{\bf 1}_{(F_i(X)=B)})$

(the last parenthesis correspond to the summation over $X_i\in\{R,B\}$ , which makes sense since $F_i(X)$ does only depend on $(X_j)_{j\neq i}$ )
The sum of the two indicator functions is obviously 1. Therefore, we get:

$\sum_{X\in\{R,B\}^{2N}}W(X)=\sum_{i=1}^{2N} \sum_{(X_j)_{j\neq i}\in\{R,B\}^{2N-1}} 1= 2N 2^{2N-1}=N 2^{2N}.$

We have a sum of $2^{2N}$ terms on the left-hand side, which equals $N 2^{2N}$ , hence at least one term must be less than or equal to N: there exists a configuration $X$ such that $W(X)\leq N$ . QED.

godelproof · #8 $Old$ June 25th, 2009, 11:12 PM

thanks! its very helpful to me to have this thorough discussion.

indeed the probabilistic proof IS as clean as the nonprobabilistic one. (my proof for the latter is essentially the same as yours)

interesting! but now it seems like a really simple question, isn't it!

Laurent · #9 $Old$ June 27th, 2009, 03:02 AM

Quote:

Originally Posted by godelproof $View Post$

interesting! but now it seems like a really simple question, isn't it!

Yes it does, after all... I find the probabilistic proof illuminating since it highlights the fact that each player has no way to know his own colour; only a "pigeon hole principle" can allow some to win surely.

Just for the sake of having a more general problem: if there are $N\in\mathbb{N}$ players and $C\in\mathbb{N}^*$ different colours of hats, then there is a strategy that makes at least $\left\lfloor\frac{N}{C}\right\rfloor$ players win in any configuration, and no strategy can do better.

Indeed, the above proofs (generalized to C colours) show that for any strategy we have $E[W(X)]=\frac{N}{C}<\left\lfloor\frac{N}{C}\right\rfloor+1$ , hence we can't have $W(X)\geq \left\lfloor\frac{N}{C}\right\rfloor+1$ almost surely.

And, for the existence:
One can replace colours by integers modulo $C$ . Consider the sum $S=\sum_i X_i$ of all $N$ hat colours (modulo $C$ ). If the $i$ -th player knows $S$ , then he can deduce his hat colour by doing $S-\sum_{j\neq i}X_j$ (modulo $C$ ). It is not possible to know $S$ however, hence the following strategy:
Each player $i\in\{1,\ldots,N\}$ is first given alternatingly a number $S_i$ between 1 and C (I mean they are numbered 1,2,...,C,1,2,...,C,1,2,.. and so on till the end), so that at least $\left\lfloor\frac{N}{C}\right\rfloor$ players have each number between 1 and C. Then each player answers $S_i-\sum_{j\neq i}X_j$ (modulo C).
All players that have the sumber $S_i=S$ will give their own colour, and there are at least $\left\lfloor\frac{N}{C}\right\rfloor$ of them.
(You can also do it in a slightly different way by grouping players C by C and proceding to the same strategy but inside each group, so that one player wins in each group)