Moreover, I'm convinced the problem isn't O(N^2) in practice. Someone with more math skills than any poster in this thread (self included) needs to weigh in, but... again...
Math skills are not needed. This is a technical and business problem, not a mathematical one. I tried to sell just such a cooperative multihoming solution about 4 years ago when I was with Ebone. We had a client who needed highly available resilient connectivity and part of the RFP was that they wanted two provider networks. We chose BT as our partner because the Ebone fibre network was largely discontinuous with BT's network. It doesn't make sense to do this with two networks who share fibre or conduits or rights-of-way. In our case, the customer was large enough that we could do it by having BT announce a part of our address space, something on the order of a /20. The actual customer peering with both of us would have used private ASNs. The plan was scuttled by financial difficulties which resulted in the demise of the Ebone network. In any case, I agree that this is something that should be available in the market but since it only makes sense if the two providers are largely discontinuous, I don't think that there will be many possible pairings in most cities. Once you get past the technical issue of who is a suitable partner, the big hurdle is on the commercial side getting two competitors to agree on terms to provide a joint service. Although this would be useful for small multihomers, I don't see that as possible until after a large enterprise customer forces two competitors to negotiate terms. --Michael Dillon