Suppose we have a directed complete graph. Can we always find a subset $S\neq \emptyset$ of the vertices such that for every vertex $v$, $v$ has incoming edge from at least $\dfrac{|S|}{2}$ of the vertices in $S$?
Note that $v$ can be in $S$. Also, we assume that each vertex has an incoming edge from itself.
Not always. I claim that for large $n$ a random tournament on $n$ vertices satisfies your property with probability tending to 0.
We use the following
Lemma. Consider a random tournament on $m$ vertices $1,\ldots,m$. For a given sequence $(d_1,\ldots,d_m)$ the probability that $\deg(i)=d_i$ for all $i=1,2,\ldots,m$ is at most $\exp(-cm\log m)$ (for a universal constant $c$).
Proof. Fix what happens between the first $m_1:=\lceil m/2\rceil$ vertices. Then the event that these $m_1$ vertices have prescribed degrees is an intersection of $m_1$ independent events (corresponding to these vertices) each of which has probability at most $O(m^{-1/2})$ (by de Moivre — Laplace local central limit theorem: each event for a fixed vertex is that the sum of $m-m_1$ independent 0-1's has prescribed value).
Return to your problem. The probability that a given set $S$ satisfies your condition for all $v\notin S$ is at most $(1/2)^{n-|S|}$. The sum over all $S$ of size, say, less than $n/10$, is clearly $o(1)$. For $|S|\geqslant n/10$ we look at vertices $v\in S$, that is, we are interested only in a random tournament induced on $S$. I claim that the probability that it satisfies your requirement is $o(1/2^n)$, that suffices for my initial claim.
Denote $m=|S|$. Your requirement yields that the indegree of each vertex $v\in S$ is at least $m/2-1$. If $m$ is odd, this means that the indegree is at least $(m-1)/2$, thus all indegrees are equal to $(m-1)/2$ (since it is the average indegree), and we just apply Lemma. If $m=2m_1$ is even, then all indegrees must be at least $m_1-1$. Enumerate $S$ and denote the indegrees $m_1-1+\varepsilon_i$ ($i=1,2,\ldots,2m_1$). Then $\sum \varepsilon_i=m_1$. Such a sequence of non-negative $\varepsilon_i$'s may be chosen by ${3m_1-1\choose 2m_1-1}$ ways, which is only exponential in $m$, while the Lemma says that for a fixed degree sequence the probability that it arises in a random tournament is superexponentially small.
