Or, at least, it seems fair right up until you flip the coin and one of them loses. Then there are suddenly all sorts of overlooked issues and last-minute considerations ("I had to go first last time!", "I have longer hair!").

The way I deal with this is by confirming buy-in before randomization. I won't randomize unless they agree that we should resolve this randomly, that they will abide by the results without fussing, and that if they do fuss it's time-out. Even though they know this rule with me, I still repeat it every time: it doesn't take that long compared to the rest of the process, and it being fresh in their minds when we randomize works much better.

In cases where the randomization is for their benefit ("which park should we go to?", "who gets the first Nora cuddle?"), if they don't accept the terms we can fall back to neither. In other cases, though, where I need to impose randomization, I'll be mildly coercive: if one of them won't agree to these terms I say I'll resolve it in the other's favor. At which point they prefer half a chance of getting their way to no chance, decide to participate, and confirm they won't fuss.