You guess is correct, assuming that by $x_1$ and $x_2$ you meant $s_1$ and $s_2$.
Indeed, the probability in question is $1-p_n$, where
\begin{equation}
p_n:=P(\exists i\in[n]\ D_i-\max_{j\in[n]\setminus\{i\}}D_j\ge cn),
\end{equation}
where $[n]:=\{1,\dots,n\}$ and $D_i$ is the out-degree of the $i$th vertex. We can write
\begin{equation}
D_i=\sum_{j\in[n]}D_{ij},
\end{equation}
where
\begin{equation}
D_{ij}:=I\{X_{ij}=1\},
\end{equation}
$I\{\cdot\}$ is the indicator function, and $(X_{ij})$ is a random $n\times n$ skew-symmetric matrix whose above-diagonal entries are independent Rademacher random variables (r.v.'s), with $P(X_{ij}=\pm1)=1/2$ if $1\le i<j\le n$.
We need to show that $p_n\to0$ (as $n\to\infty$), for each $c\in(0,1)$. In fact,
\begin{equation}
p_n\le nP(D_1-\max_{j\in[n]\setminus\{1\}}D_j\ge cn)
\le nP(D_1-D_2\ge cn).
\end{equation}
Next,
\begin{equation}
D_1-D_2=D_{12}-D_{21}+\sum_{j=3}^n Y_j,
\end{equation}
where $Y_j:=D_{1j}-D_{2j}$, so that the $Y_j$'s are iid zero-mean r.v.'s, with $|Y_j|\le1$. Also, $D_{12}-D_{21}\le1$. So, by (say) Hoeffding's inequality, for all large enough $n$,
\begin{equation}
p_n\le nP(D_1-D_2\ge cn)\le nP\Big(\sum_{j=3}^n Y_j\ge cn-1\Big)\le ne^{-(cn-1)^2/(2(n-2))}\to0,
\end{equation}
as desired.
