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$:

 1. 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.

 2. 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][1], 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$).

**Lemma 1:** If $I_1, I_2, I_3$ are closed intervals s.t. any pair of them intersect nontrivially, then $I_1 \cap I_2 \cap I_3 \neq \varnothing$.

**Proof:** If any of the intervals contains another, then the result is obvious. Assume that is not the case. Note that if two closed intervals intersect, and if neither of them contains the other, then the intersection is a closed interval which contains one endpoint from each of the original intervals. In particular, $I_1 \cap I_2$ contains an endpoint of $I_1$, and similarly $I_1 \cap I_3$ contains an endpoint of $I_1$. If both contain the same endpoint of $I_1$, the result follows. Otherwise, we may WLOG that $L(I_1) \in I_2$ and $R(I_1) \in I_3$. But then $L(I_2) \leq L(I_1) \leq R(I_1) \leq R(I_3)$, so for $I_2$ and $I_3$ to intersect, we must have $R(I_2) \geq L(I_3)$. We also observe that, since none of the intervals contains each other, we have $R(I_2) < R(I_1) \leq R(I_3)$ and $L(I_3) > L(I_1) \geq L(I_2)$. Thus, $[L(I_3), R(I_2)] = I_2 \cap I_3$ is nonempty and also contained in $I_1$. Hence, $I_1 \cap I_2 \cap I_3 \neq \varnothing$. $\square$

**Lemma 2:** If $I_1, \cdots, I_n$, $n \geq 2$ are closed intervals s.t. any pair of them intersect nontrivially, then $I_1 \cap \cdots \cap I_n \neq \varnothing$.

**Proof:** By induction on $n$: The $n = 2$ case is trivial. Assume the result holds for some $n$ and consider the case for $n + 1$. Then $I_1 \cap I_{n + 1}, \cdots, I_n \cap I_{n + 1}$ are $n$ closed intervals. Any pair of them intersect nontrivially, since the intersection of any pair is the intersection of three $I_k$’s, whence it is nonempty by Lemma 1. Thus, by inductive assumption, $I_1 \cap \cdots \cap I_{n + 1} = (I_1 \cap I_{n + 1}) \cap \cdots \cap (I_n \cap I_{n + 1}) \neq \varnothing$. $\square$

As $\varnothing \neq q(x, y) \subset S(x) \cap S(y)$ is nonempty for any $x, y$, Lemma 2 implies 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_2}(c_1) = p_{c_1}(c_2) = c_2$. $\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 point, 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.


  [1]: https://mathoverflow.net/a/474256/504602