Consider a random bipartite multigraph $\graph$ with $\keys$ left nodes and $\cells \geq \keys\geq2$
right nodes. Each left node $x$ has $\degr_x\geq1$ random right neighbors.
The average left degree $\Amean$ is fixed, $\Amean\geq2$.
We ask whether for the probability that $\graph$ has a left-perfect matching
it is advantageous not to fix $\degr_x$ for each left node $x$ but rather choose it
at random according to some (cleverly chosen) distribution. We show the following,
provided that the degrees of the left nodes are independent:
If $\Amean$ is an integer then it is optimal to use a fixed degree of $\Amean$ for all left nodes.
If $\Amean$ is non-integral then an optimal degree-distribution has the property that
each left node $x$ has two possible degrees, $\floor{\Amean}$ and $\ceil{\Amean}$,
with probability $p_x$ and $1-p_x$, respectively, where $p_x$ is from the closed interval~$[0,1]$
and the average over all $p_x$ equals $\ceil{\Amean}-\Amean$.
Furthermore, if $\keys=c\cdot \cells$ and $\Amean>2$ is constant,
then each distribution of the left degrees that meets the conditions above determines the same
threshold $c^*(\Amean)$ that has the following property as $\keys$ goes to infinity:
If $cc^*(\Amean)$ then there exists no left-perfect matching with high probability.
The threshold $c^*(\Amean)$ is the same as the known threshold for offline $k$-ary cuckoo hashing
for integral or non-integral $k=\Amean$.