A binary relation $R$ on a set $D$ is rigid iff the unique $D → D$ bijection that fixes $R$ is the identity function.
Any well-ordering is rigid, so the Well-Ordering Principle has the consequence that any set $D$ admits some rigid relation $R$.
My question is whether the converse holds. In other words, is the claim that every set admits some rigid binary relation as strong as the Axiom of Choice (in the context of ZF set theory)? Or is it strictly weaker? Can it be proved in ZF without Choice?
This came up on MO a while back. This paper addresses your question.