This is a horribly long and convoluted answer addressing one extremely specific case: $n = 1$ and $S(x)$ is an interval for any $x$. Since in $\mathbb{R}$, a subset is an interval iff it is connected iff it is convex, this might shed some light on the more general case where $S(x)$ is assumed connected convex but $n$ may not be $1$.
I claim that, in case $S(x)$ is always an interval in $\mathbb{R}$, the following are all possible $S$:
- In case $S(x)$ are all bounded, then there exists $c \in \mathbb{R}$, $d \in [-\infty, c]$, $e \in [c, \infty]$, s.t.
$$S(x) = \begin{cases} [d, c] &, \text{ if }x \leq d\\ [x, c] &, \text{ if }d < x \leq c\\ [c, x] &, \text{ if }c < x \leq e\\ [c, e] &, \text{ if }x > e \end{cases}$$
and any such choice of $c, d, e$ yields an $S$ that satisfies the requisite condition.
- In case $S(x)$ are all unbounded, then either there exists $e \in (-\infty, \infty]$, s.t.
$$S(x) = \begin{cases} (-\infty, x] &, \text{ if }x \leq e\\ (-\infty, e] &, \text{ if }x > e \end{cases}$$
and any such choice of $e$ yields an $S$ that satisfies the requisite condition; or, there exists $d \in [-\infty, \infty)$, s.t.
$$S(x) = \begin{cases} [d, \infty) &, \text{ if }x \leq d\\ [x, \infty) &, \text{ if }x > d \end{cases}$$
Note that by Alex’s answer, we already have $S(x)$ are either all bounded or all unbounded, so any $S$ falls within one of the above two situations.
I’ll leave you to check that all $S$ defined above indeed stiasfy the requisite condition. I’ll instead just prove the necessity.
For notational simplicity, if $I$ is an interval, we shall let $L(I)$ be its left endpoint (including possibly $-\infty$) and $R(I)$ be its right endpoint (including possibly $\infty$).
As $\varnothing \neq q(x, y) \subset S(x) \cap S(y)$ is nonempty for any $x, y$, Helly's theorem for $d=2$ implies that any finitely many $S(x)$ intersect nontrivially.
For notational simplicity, we note that in our current case, $p_{S(x)}(y)$ is always a singleton, so I’ll simply write $p_x(y)$ for the unique point in $p_{S(x)}(y)$. The condition $q(x, y) \neq \varnothing$ is simply equivalent to saying $p_x(y) = p_y(x)$ for all $x, y$.
For the bounded case, by compactness and the fact that any finitely many $S(x)$ intersect nontrivially, we must have $\cap_{x \in \mathbb{R}} S(x) \neq \varnothing$.
Lemma 3: $\cap_{x \in \mathbb{R}} S(x)$ is a singleton.
Proof: Let $c_0, c_1 \in \cap_{x \in \mathbb{R}} S(x)$. Then because $c_i \in \cap_{x \in \mathbb{R}} S(x) \subset S(c_{1 - i})$, we have $c_1 = p_{c_0}(c_1) = p_{c_1}(c_0) = c_0$. $\square$
Let $c$ denote the unique element of $\cap_{x \in \mathbb{R}} S(x)$. In particular, $c \in S(x)$ for all $x$, so $p_x(c) = c$ for all $x$. Now, we first observe that $S(c) = \{c\}$. Indeed, if $d \in S(c)$, then $c = p_d(c) = p_c(d) = d$. Next, for any $x < c$, we claim that $S(x)$ contains no point strictly larger than $c$. Indeed, assume to the contrary that $y > c$, $y \in S(x)$, then $p_y(x) = p_x(y) = y$, but $c \in S(y)$ is closer to $x$ than $y$, a contradiction. To put it another way, $R(S(x)) = c$. Similarly, for any $x > c$, $S(x)$ does not contain any point strictly smaller than $c$, i.e., $L(S(x)) = c$.
We also observe that, for any $x < c$, $L(S(x)) \geq x$. Indeed, assume to the contrary that $L(S(x)) < x$. Then $L(S(x))) = p_x(L(S(x))) = p_{L(S(x))}(x)$. In particular, the interval $S(L(S(x)))$ contains both $L(S(x))$ and $c$, so as $L(S(x)) < x < c$, we must have $x \in S(L(S(x)))$, so $p_{L(S(x))}(x) = x$, a contradiction.
If for all $x < c$, we have $L(S(x)) = x$, then $S(x) = [x, c]$ for all $x < c$ and we may pick $d = -\infty$. If, on the contrary, there exists an $x < c$ s.t. $L(S(x)) > x$, then let $d = L(S(x))$. As $c \in S(x)$, $d \leq c$. Now, for any $y \leq d$, we have $d = p_x(y) = p_y(x)$. As $R(S(y)) = c$, this means $L(S(y)) = d$, i.e., $S(y) = [d, c]$ for all $y \leq d$. On the other hand, for any $d < y < c$, so $y \in S(x)$, we have $y = p_x(y) = p_y(x)$, so similarly $S(y) = [y, c]$ for all $d < y < c$. The consideration for points on the RHS of $c$ is similar. This proves the case for bounded $S(x)$.
The unbounded case is essentially similar. The trick is to compactify $\mathbb{R}$ by adding two points, $-\infty$ and $\infty$. Then we add to unbounded intervals the apppropriate point or points at infinity to compactify them as well. Now that everything is compact, we can again say $\cap_{x \in \mathbb{R}} S(x)$ is nonempty. Since it is an interval, if it contains more than one point, it must contain more than one finite (real) points, so the same argument shows $\cap_{x \in \mathbb{R}} S(x)$ is a singleton. It cannot be a point $c \in \mathbb{R}$, as otherwise the same argument as above shows $S(c) = \{c\}$, so we would be back in the bounded case. So either $\cap_{x \in \mathbb{R}} S(x) = \{-\infty\}$, or $\cap_{x \in \mathbb{R}} S(x) = \{\infty\}$. The argument from this point onwards is very similar to the bounded case, so I’ll leave it to you to check.
