Probability to be the winner in a tournament

Question

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$.

Answer 1

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$.

Answer 2

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.

Answer 3

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

_{(source: landsburg.com)}

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.