>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.