Real life motivation. In my younger son's class, there are $18$ students. His teacher provided $18$ time slots for the parents of each child to have a 30-minute conversation of their kid's progress in school and asked the parents to provide $4$ possible time slots that would be convenient for them. I wondered how probable it is that given all the choices, the teacher can select a convenient time slot for the parents of every child so that everyone can have the "progress conversation."

Formal version. We say that an $n$-tuple $(S_1,\ldots,S_n)$ of $k$-element subsets of $\{1,\ldots,n\}$ has the satisfiability property if there is a permutation $\sigma \in \mathfrak{S}_n$ with $\sigma(i)\in S_i$ for all $i=1,\ldots,n$.

Given an integer $n>1$, what is the smallest $k$ (in terms of $n$) such that at least half of the $n$-tuples $(S_1,\ldots,S_n)$ of $k$-element subsets of $\{1,\ldots,n\}$ have the satisfiability property? If no exact formula can be given, is there an approximation for when $n\to\infty$?