Therefore, by (4) it follows that ∑ j v$_{j}$ (¯ x, ¯ y ) > k/ 3 ∗ 1 + (2 k/ 3) ∗ ( − 1 / 6) > k/ 6 . The proof of Lemma 4.1 uses the probabilistic method. Alon and Spencer [2, Section 2.5] use the probabilistic method to prove that for every initial configuration it is possible to switch lights to unbalance the matrix. We turn the probabilistic method ‘on its head’ to prove that there exists some initial configuration for which any switching will result in an unbalanced matrix. The argument follows the proof of lower bound in the classical discrepancy problem [2, Section 13.4]. Proof of Lemma 4.1. Fix k and let M$_{k}$$_{×}$$_{k}$ = { m$_{ij}$ } where m$_{ij}$ are independent random signs. For a fixed ¯ x , the entries of z = ¯ x · M are i.i.d , and each z$_{j}$ is distributed like the sum of k independent random signs. Thus, by the central limit theorem P ( | z$_{j}$ | ≤ √$_{k}$ 20 ) k →∞ − −− → 1 √$_{2}$$_{π}$ ∫ 1 / 20 − 1 / 20 e − τ $^{2}$/ $^{2}$d τ < 1 / 25 Fix a row vector ¯ x of length k with entries in { +1 , − 1 } and let E$_{¯}$ x be the event that (3) is not satisfied. Then E$_{¯}$ x is the event that there are more than 2 k/ 3 successes in k independent trials with probability of success smaller than 1 / 25. From Chernoff inequality [2, Theorem A.1.4] we get By (2), it follows that u$_{i}$ (¯ x, ¯ y ) < − 1 / 6 for some female i . Since every player inverts the sign of her payoff by changing strategy it follows that female i does not 1 / 3 best-respond to ¯ y . □ P ( E$_{¯}$ $_{x}$) ≤ exp ( − 2 k (2 / 3 − 1 / 25) $^{2}$) < 1 / 2 $^{k}$. Since there are only 2 k possible ¯ x -s, it follows that P ( ∪ ¯ $_{x}$E$_{¯}$ $_{x}$) < 1. Therefore, for some choice of M none of the E$_{¯}$ x obtains, as desired. □ 10