Task Allocation Search: OCSM Contracts

In the simple individual hill-climbing protocol each agent tries to give/get one task to/from another agent. This protocol will always increase the global utility but will often get stuck in a local optimum.
One way to get around this problem is to connect every single possible task allocation to every other one in one step. This way, the global optimum is always just one step away (ahh, but which step?).
This is what OCSM contracts do. Instead of just trading one task between agents, they make every deal possible, with any number of tasks and agents. OCSM contracts beg the question of how to find the global optimum.