What is the optimal size in the finite axiom of symmetry?

Given $k$, let $X=\{1,2,\dots,2k\}$. We must have $1$ in $A_1$, else we could take $x=y=1$. We may assume $A_1=\{1,2,\dots,k\}$. So $r$ is not in $A_1$ for $r=k+1,k+2,\dots,2k$. So we must have $1$ in $A_r$ for $r=k+1,k+2,\dots,2k$. That is, $1$ must be in $k+1$ of the sets $A_r$ (since it's also in $A_1$). But there's nothing special about $1$, so each of the elements $1,2,\dots,2k$ must be in $k+1$ of the sets $A_r$. But there isn't room for $2k(k+1)$ elements in $2k$ sets of size $k$. Therefore, if $n=2k$, there must be $x$ and $y$ (possibly $x=y$) with $x$ not in $A_y$, and $y$ not in $A_x$.

If $n=2k-1$, let $A_1=\{1,2,\dots,k\}$, $A_2=\{2,3,\dots,k+1\}$, and so on, to $A_{2k-1}=\{2k-1,1,2,\dots,k-1\}$, then there are no $x$ and $y$ with $x$ not in $A_y$ and $y$ not in $A_x$.

Suppose we have $|A|=n\in\mathbb N,$ and $A_x\in\binom Ak$ for each $x\in A,$ such that for any two distinct elements $x,y\in A,$ either $x\in A_y$ or $y\in A_x.$ Define a tournament $T$ on the vertex-set $V(T)=A$ so that $xy\in E(T)\implies y\in A_x.$ Then the score (outdegree) of each vertex is $\le k.$ Since the sum of all the scores is $\binom n2=\frac{n(n-1)}2,$ the average score is $\frac{n-1}2,$ whence $\frac{n-1}2\le k,$ i.e., $n\le2k+1.$

That is, if $|A|\ge2k+2,$ and if $|A_x|\le k$ for each $x\in A,$ then there exist two distinct elements $x,y\in A$ with $x\notin A_y$ and $y\notin A_x.$

On the other hand, it is quite easy to construct a tournament on $2k+1$ vertices in which each vertex has score $k;$ namely, put the vertices on a circle, and draw directed edges from each vertex to the next $k$ vertices clockwise.

P.S. Replacing "distinct" with "not necessarily distinct" amounts to imposing the condition $x\in A_x$ which amounts to replacing $k$ with $k-1.$

This seems really easy? Let $A \subseteq X^2$ be the set of all $(x,y)$ such that $y \in A_x$, and let $A^r$ be the reflection of this across the main diagonal. You are asking whether $A\cup A^r = X^2$. Suppose, for a contradiction, that $n \ge 2k$ and that $A\cup A^r = X^2$. Then $A$ must certainly contain the diagonal of $X^2$, so by the Principle of Inclusion and Exclusion, we have

$|X^2| = |A\cup A^r| = |A| + |A^r| - |A \cap A^r| \le 2nk - n < n^2 = |X^2|,$

a contradiction. On the other hand, if $n \le 2k-1$ then we can take $X = \mathbb{Z}/n$ and $A_x = \{x, x+1, ..., x+k-1\}$, so that $A = \{(x,y) \mid y-x \in \{0, ..., k-1\}\}$.