Initially it looks like so long as a sufficient number of agents are using a decision theory that can provably cooperate on one shot PD (as in the Modal Agent paper discussed recently) they can coordinate to decrease the individual cost below the Nash Equilibrium. The number of agents required depends on the network graph. Agents that can provably pick a Nash-suboptimal path if enough other agents provably pick complementary paths such that the individual cost is reduced will have lower costs than the original Nash Equilibrium.

In the A-B network example on Wikipedia the number of agents required to cooperate would be >1000 to beat the 80 minute equilibrium cost by lowering the T/100 path costs below 35 minutes each by half the agents taking the start-A-end path and the other half taking the start-B-end path, leaving <3500 start-A-B-end paths.