Is this solved correctly?
Give an interpretation such that $\phi=\forall x\exists y(P(x,y)\to\lnot P(y,y))$ is not valid.
Let I be an interpretation such that the domain is $\mathbb N$ and $P(x,y) = " y\le x "$. Thus if $y=1$ always, then $\phi=F$, i.e. it's not valid for I.
Yes, that works!
Here is a simpler one that also works:
Domain: $\{ a \}$ (i.e. just one object $a$)
$P(x,y)$: $x=y$ (i.e. $a$ stands in relation $P$ to itself)
Given that there is just one object, the whole statement collapses to: $a = a \rightarrow \neg a = a$, and is thus false.