Consider a random bipartite multigraph $G$ with $n$ left nodes and $m \geq n\geq2$
right nodes. Each left node $x$ has $d_x\geq1$ random right neighbors.
The average left degree $\mean$ is fixed, $\mean\geq2$.
We ask whether for the probability that $G$ has a left-perfect matching
it is advantageous not to fix $d_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 $\mean$ is an integer, then it is optimal to use a fixed degree of $\mean$ for all left nodes.
If $\mean$ is non-integral, then an optimal degree-distribution has the property that
each left node $x$ has two possible degrees, $\floor{\mean}$ and $\ceil{\mean}$,
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{\mean}-\mean$.
Furthermore, if $c=n/m$ and $\mean>2$ are constant,
then each distribution of the left degrees that meets the conditions above determines the same
threshold $c^*(\mean)$ that has the following property as $n$ goes to infinity:
If $cc^*(\mean)$ then asymptotically almost surely there exists no left-perfect matching.
The threshold $c^*(\mean)$ is the same as the known threshold for offline $k$-ary cuckoo hashing
for integral or non-integral $k=\mean$.