Peer-to-peer is only O(n^2) if every node is always connected to every other node. But Valve's organization seems to work by creating much smaller sub-networks on an ad-hoc basis, so that at any given instant, each node is only actually connected to a small set of other nodes. Instead of a hierarchical system which would have each sub-network be permanently defined with clear boundaries, and create a network-of-networks to coordinate them, this method ensures coordination among the sub-networks by relying on most nodes being a part of multiple sub-networks and having a slightly different set of connections, such that there's an overall mesh that does actually connect every node in the graph, directly or indirectly.

Sort of the way torrents work, in fact: there's a pool of seeds and peers - which might have thousands of members - but your client is only exchanging data with maybe a few dozen at any given time. But since each peer has its own slightly different set of connections, data anywhere in the system can still propagate to the entire system.

I suppose it would be an interesting problem to figure out, given n nodes, with each node having a minimum of x and a maximum of y edges per node, and a maximum of z edges per path, what the minumum total set of edges would be to ensure that there exists a path between any two nodes.

I think a flat hierarchy necessitates 'adhocracy', but from a cultural and operational standpoint, I'd expect them to mutually reinforce each other quite well.