why not make the next one something like random team game? So you start off random and the first guy you meet gets to be your ally.
not much synnergy pregame , but afterwards you can start building up the relationship.
Or even easier to implement (and more falut-proof) just start with some random position, then everyone says where their capital is at, and depending on that we pair them up in teams.