1. Random assignment of games. To eliminate collusion you assign everyone to games randomly. The player can start a game and get random players and choose to be assigned to one via the Auto-match feature. This feature can be expanded to allow players to select number of opponents and type of map they want.
2. Make an Alliance Free game option. Everyone is on his own. This won't eliminate collusion but add a greater element of mystery.