We study network formation with $n$ players. Players choose their neighbors
simultaneously, and a link is formed between two players only if both players
select each other. The value of a link between a pair of players is modeled
using a random variable, and the values of $n(n-1)/2$ different possible links
are
given by independent random variables with a common, continuous distribution.
Each player chooses $N(n)$ neighbors that offer the highest values. Because two
players receive the same value from a link between them, this introduces
coupling in the set of neighbors selected by the players. We show that $N(n)$
must
increase as $\Theta(\log(n))$ in order for the ensuing network to be connected
with
probability one as $n$ increases.