Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
    
Dear Ariel, Welcome to MathOverflow! May the force be with you :) –  Gil Kalai Mar 18 '12 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. –  Patrick Reardon Mar 18 '12 at 18:15
    
To Patrick: Note, that the direction of transfer between any two players is indepedent from the directions in other "matches". –  Ariel Rubinstein Mar 18 '12 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! –  Patrick Reardon Mar 19 '12 at 8:33

3 Answers 3

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

share|improve this answer
1  
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). –  Ariel Rubinstein Mar 18 '12 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.

share|improve this answer

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.

share|improve this answer
    
Thanks. We conducted here similar simulation for all |A|,|B|<11 In case you are interested: arielrubinstein.tau.ac.il/simulation.pdf –  Ariel Rubinstein Mar 19 '12 at 5:43

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.