Sen's Liberal Paradox
Another solution can arise if you allow for uncertainty and for the planner to provide private information to each player. See Bergemann and Morris, 2018 for a survey in what is called information design. In that way, it is not hard to see how each player can be convinced that the social allocation is its most preferred outcome with high probability such that from the ex-ante perspective, the outcome is Pareto-optimal. 

Of course, I'm throwing a lot of details under the rug, but having asymmetric information seems like another solution to this conundrum.