Throw $n$ balls into $n$ bins, and let $X_n$ be the max load. That is the number of balls in the fullest bin.  It is known that if the balls are thrown uniformly and independently at random then $\mathbb{E}(X_n)  = \Theta(\lg{n}/\lg{\lg{n}})$.  

If instead, for each ball considered sequentially we look at two bins chosen uniformly and independently at random, and throw the ball into the least full one (or a random one if they are equally full), then it is known that  $\mathbb{E}(X_n) = \Theta(\lg{\lg{n}})$, a dramatic decrease. See [this survey][1] for example for more discussion of this phenomenon. 

> What happens if we still look at two bins for each ball and the bins are still selected uniformly but only with pairwise independence?


  [1]: http://people.cs.umass.edu/~ramesh/Site/PUBLICATIONS_files/MRS01.pdf