# Probability to be the winner in a tournament

In a project in Game Theory we (Ayala Arad and Ariel Rubinstein) are stuck with the following "simple" question. We are sure of the conjecture but we failed to find a (hopefully simple) proof:

Let $$A$$ and $$B$$ be two non-empty finite disjoint sets of players. Any two players in $$A$$ are "matched" and $$\2$$ are transferred from one to the other. Any player in $$A$$ is also matched with any player in $$B$$ and $$\1$$ is transferred from one to the other. The two possible directions of each transfer are equally likely and independent. No transfers are carried out between players in $$B$$. The winner is the player with the highest net transfers. In the case of a tie, the winner is selected randomly from among the highest scoring players. (For example if $$|A|=1$$ and $$|B|=2$$ the probability of winning for the player in $$A$$ is $$1/4$$ and the probability for the player in $$B$$ is $$3/8$$. If $$|A|=|B|=2$$ the corresponding numbers are $$21/64$$ and $$11/64$$).

Claim: If $$|AUB|>3$$ then the probability of winning for any player in $$A$$ is strictly larger than that of any player in $$B$$.

• Dear Ariel, Welcome to MathOverflow! May the force be with you :) Mar 18, 2012 at 14:16
• Wouldn't any two players in A have the same number of transfers, and the same for B? I guess I don't understand the game. Mar 18, 2012 at 18:15
• To Patrick: Note, that the direction of transfer between any two players is indepedent from the directions in other "matches". Mar 18, 2012 at 22:00
• Thanks, it's clearer now. So we could say that every pair of players in $A$ flip a fair coin and the winner gets $\$2$. Every pair of players with one from$A$and one from$B$flip a fair coin and the winner gets$\$1$. Interesting problem! Mar 19, 2012 at 8:33

Here's a partial answer, I believe that the technique can be generalized to include more cases.

Suppose that $|A|=|B|=n$ and $n$ is large enough. As $n\to \infty$, the distribution of what an $A$-player gets is roughly $N(0,3n-2)$ and what $B$=player gets is roughly $N(0,n)$. Hence, we can choose some threshold $t_n$ (about $\sqrt{\log n}$ or so) such that the expected number of $A$-players getting more than $t_n$ is large (tends to infinity) and the expected number of $B$-players getting more then $t_n$ is small (tends to zero). The probability that a $B$-player will get more then $t_n$ therefore also goes to 0.

Furthermore, the amounts different players get are almost pairwise independent (they are independent up to the amount one of them pays the other). Thus, a second moment argument easily show that the probability of some $A$-player gets more then $t_n$ goes to 1. So the probability that an $A$-player will win goes to 1. Since the players are symmetric and there are equal number of $A$ and $B$ players, we get that the probability of an $A$-player to win is strictly larger then that of a $B$-player.

This can be extended to other regimes by analyzing what $t_n$ and the probabilities actually are and perhaps using the binomial distribution instead of Normal (actually, I now notice that the argument is not precise as it is since I use Normal approximation in a regime where it is not formally valid, but it's easy to correct). Perhaps all cases where either $|A|$ or $|B|$ are large enough can be covered that way and perhaps "large enough" turns out to be pretty small after all. Perhaps I'll try to give a more complete answer later.

One final remark: it seems that (at least asymptotically) it is not important that $2>1$, but only that $2>0$.

• Thanks. We do need the result for small values as well (and not just for large numbers). Note that for general |A| and |B| (not for the case that |A|=|B|) we need the condition that $2>$1: Consider the case that the transfer between a member of A and a member of B (which is now $1) is very very high then if |A|>|B|, the probability of a member of B to win will be larger (the transfers inside B will be negligible). Mar 18, 2012 at 21:58 This was intended to be a comment to Ori's post but it is too long, so I'm posting it as an answer. First of all, let us modify the game a bit by initially giving each player a random score between$0$and$\varepsilon$. That will break the ties just as needed but will allow us to talk about the winner. Now the case$|A|=|B|$is trivial. Let's do all transactions between$A$and$B$first and look at the resulting configurations. They split into natural pairs (swapping$A$and$B$). Now let$a$be the top score in$A$and$b$be the top score in$B$. Arrange the pair so that$a>b$. Then we need to show that for every configuration the probability that the top score in$A$will become less than$b$after transactions in$A$is less than that the probability that the top score in$B$will become larger than$a$if we do the transactions in$B$. Identify$A$with$B$in some way so that the top scorers are identified. Any way to do the transactions in$A$that moves the winner to$B$should bring the score$a$of the top scorer in$A$below$b$at the very least and that may be insufficient in some configurations. On the other hand, if have one such way and do the inverse transactions in$B$instead, they'll bring the top scorer in$B$above$a$and it is not necessary to move the winner to$B\$. That's all one needs to say about the equal cardinalities case.

Now, like Ori, I have to say that I'll try to give a more complete answer later.

For the little it might be worth, here are the results of some simulations:

The columns correspond to values of $$|A|$$ and the rows to values of $$|B|$$. The four-tuple in each cell is (Probability winner is in $$A$$, Probability winner is in $$B$$, Probability a given member of $$A$$ is the winner, Probability a given member of $$B$$ is the winner).

I simulated each of these 10,000 times, rounded results to the nearest percent, and retyped them (which has a small chance of having introduced additional errors).

I was struck by the non-monotonicity in the third entry as you go down the third column, so I repeated these trials and got the same result.