This problem is a variation of the distributed consensus problem in computer science. The canonical solutions (Paxos, Raft, et al) are non-trivial and there are unsolved corner cases. In short - this is problem where they are looking at your approach to problem solving rather than the solution itself.
But the other party could have informed you their strategy too. So you tell them "Let's use strategy X", and the same step you receive "Let's use strategy Y" from them. Looks like the first meta-task is to agree on a strategy :^)
The arbitrary message "constraint" seems to be an escape hatch.
But I think you could just use the same approach: "Every turn, keep suggesting a strategy until you receive the same strategy you suggest". Once that happens, then you both execute that strategy.
Both players are trying to collaborate here, so they'll naturally subordinate themselves on the first opportunity to win the game, they'll implement randomness or backoff naturally.