A key element of the game is that each non-player house starts the game as a potential ally. Being the first to gain 2 of a non-player house’s Power Tokens in your Ally Pool potentially grants you that house’s Shield and therefore, their alliance (see Checking Alliances). Once you are a non-player house’s ally, all of that house’s Power Tokens on the map are now considered military strength for your house, and tokens on their mat may be recruited as well.
However, do not get too comfortable, as loyalty is fleeting. Alliances are checked at the end of each round. Players with at least 2 Power Tokens, and more of that nonplayer house's Power Tokens than anyone else, gain the alliance of that house. See Checking Alliances for more details on how alliances are earned and how they change.