To be clear, are you asking for the expected value of the ordered histogram, i.e., the value of the first bin is the expected amount of money held by the thief who has the most, rather than for thief number 1? I'm pretty sure that the average distribution by index is just a constant $1.
Figuring out the distribution after the first round would be very difficult, requiring us to determine what strategy they are using. It gets very complicated if you start considering future moves (do I play badly in the early rounds in the hope that I will be ignored until I make an epic play in the last round?).
I replied to Xavier below with my own version of this question, but to answer your strategy question, I don't think the first round could possibly have a strategy. Each person just picks someone at random, because there's no information to go on yet. I suspect that the future weeks' puzzles will explore later rounds.
I agree. There is no possible strategy in the first round other than to pick someone at random. That's why it works to ask about the distribution after one round.
As soon as a round starts with a non-uniform distribution, strategy must come into play. I don't think that it's possible to come up with a general strategy. Instead, every distinct distribution will produce a different optimal strategy, which cannot be the same for all thieves.
What I was driving at was the full distribution of the wealth for the players after round 1. Agreed, the expected value would just be 1. The expected value of the thief that has the most after round 1 would also be interesting though so if you want to do that analysis, I’d be happy to include it in the solution write-up!
Came here to ask the same question, but I don't think I quite understand still.
Let's take n=3 as an example. WLOG, let A steal from B, and B from C. Then, there are two equally likely possibilities:
- C steals from A. This just creates a loop of stealing, so everyone ends up with 1.
- C steals from B. Now, A gets 0.5 since both A and C steal from B, so A ends with 1.5. B loses his 1, then steals 1 from C, so B ends with 1. And C loses his 1 and gets 0.5 from B, so C ends with 0.5.
My question: since each of these is equally likely, do we average each person's winnings to make the distribution? So A is 1.25, B is 1, and C is 0.75.
Ohh ok, I think I see what you’re getting at. Assume everyone is acting according to a Nash equilibrium. In this case, since everyone has the same starting wealth, you can assume everyone selects their target randomly and uniformly from among all potential targets. Does this clarify?
With three thieves, do we consider the distribution of (A,B,C)=(1.5,1,0.5) to be different from (A,B,C)=(0.5,1,1.5)? If these are distinct then the expected distribution would be trivially uniform. If they are the same then the expected distribution is, from highest to lowest, (1.375,1,0.625).
They can be treated as separate. Not sure I understand the third sentence. The solution I was envisioning would be a probably distribution for the different possible wealths for a player.
That makes sense. That distribution is not trivial. For the 3 player case, it would be 0.5 1/4 of the time, 1 1/2 of the time (a third of 75% of the time plus all of 25% of the time), and 1.5 1/4 of the time.
The 10 player distribution seems a lot more involved/interesting. Unlike the 3 player distribution, I can't simply work it out in my head.
To be clear, are you asking for the expected value of the ordered histogram, i.e., the value of the first bin is the expected amount of money held by the thief who has the most, rather than for thief number 1? I'm pretty sure that the average distribution by index is just a constant $1.
Figuring out the distribution after the first round would be very difficult, requiring us to determine what strategy they are using. It gets very complicated if you start considering future moves (do I play badly in the early rounds in the hope that I will be ignored until I make an epic play in the last round?).
I replied to Xavier below with my own version of this question, but to answer your strategy question, I don't think the first round could possibly have a strategy. Each person just picks someone at random, because there's no information to go on yet. I suspect that the future weeks' puzzles will explore later rounds.
I agree. There is no possible strategy in the first round other than to pick someone at random. That's why it works to ask about the distribution after one round.
As soon as a round starts with a non-uniform distribution, strategy must come into play. I don't think that it's possible to come up with a general strategy. Instead, every distinct distribution will produce a different optimal strategy, which cannot be the same for all thieves.
What I was driving at was the full distribution of the wealth for the players after round 1. Agreed, the expected value would just be 1. The expected value of the thief that has the most after round 1 would also be interesting though so if you want to do that analysis, I’d be happy to include it in the solution write-up!
Came here to ask the same question, but I don't think I quite understand still.
Let's take n=3 as an example. WLOG, let A steal from B, and B from C. Then, there are two equally likely possibilities:
- C steals from A. This just creates a loop of stealing, so everyone ends up with 1.
- C steals from B. Now, A gets 0.5 since both A and C steal from B, so A ends with 1.5. B loses his 1, then steals 1 from C, so B ends with 1. And C loses his 1 and gets 0.5 from B, so C ends with 0.5.
My question: since each of these is equally likely, do we average each person's winnings to make the distribution? So A is 1.25, B is 1, and C is 0.75.
Or does distribution mean something else?
Ohh ok, I think I see what you’re getting at. Assume everyone is acting according to a Nash equilibrium. In this case, since everyone has the same starting wealth, you can assume everyone selects their target randomly and uniformly from among all potential targets. Does this clarify?
With three thieves, do we consider the distribution of (A,B,C)=(1.5,1,0.5) to be different from (A,B,C)=(0.5,1,1.5)? If these are distinct then the expected distribution would be trivially uniform. If they are the same then the expected distribution is, from highest to lowest, (1.375,1,0.625).
They can be treated as separate. Not sure I understand the third sentence. The solution I was envisioning would be a probably distribution for the different possible wealths for a player.
Ohhh, so you focus on one player and make a probability distribution for that player. Got it now!
That makes sense. That distribution is not trivial. For the 3 player case, it would be 0.5 1/4 of the time, 1 1/2 of the time (a third of 75% of the time plus all of 25% of the time), and 1.5 1/4 of the time.
The 10 player distribution seems a lot more involved/interesting. Unlike the 3 player distribution, I can't simply work it out in my head.