You don't need to do an exhaustive search because optimality here did not account for different amounts for each. A thing is optimally fair in this world if everyone's wealth goes up. That doesn't need exhaustiveness.

A thing that gives me 1 million and you 1 is as fair as one that gives us both 500k.

And yes, we did actually search everything possible because if something did not get done it was, by definition, impossible. After all, the agent that could have made something possible could not have acted as such because we know they did not. If they could have they would have. If they could not conceive of a better thing then the thing was impossible because it was not conceivable by anyone.