>I think calculating the optimal trade is a NP complete problem. Haven't checked this now, though
If you define the optimal trade as the trade involving as many people as possible, then the problem is NP-complete (it solves DIRECTED HAMILTONIAN CIRCUIT). There are good heuristics for solving this problem, though, so in most cases it won't matter.
I think the optimal trade would make most people happy, but ultimately it is hard to decide upon the best criterion? I remember that they use heuristics, or in any case they usually don't compute the best solution, just a reasonably good one.
If you define the optimal trade as the trade involving as many people as possible, then the problem is NP-complete (it solves DIRECTED HAMILTONIAN CIRCUIT). There are good heuristics for solving this problem, though, so in most cases it won't matter.