Perhaps something to make alliances a visible part of the game would be interesting.
Tribes join an alliance and the leaders (barons/baronettes and dukes/duchesses) elect a king/queen of the alliance and can select a number of princes/princesses or lords/ladies (just see however far you want to go about that) who'll take similar duties on hand as regular tribe matters. Could also make it oligarchic and set up a council who vote for every thing, but that seems a bit too unwieldy.
The official leaders (king/queen and prince/princess) can set a flag, write some policy etc. Only king can promote others to "royalty" of the alliance or disband. All royalty can declare war on another alliance (or a single tribe) or allow/deny tribes to join the alliance (as well as remove them from the alliance). Unlike barons, princes etc can remove a king from power trough a vote (with a time limitation in how long the voting can last and how much time minimum between a vote to remove from power. During a vote, the king can not demote the princes, or if it's to be truly democratic, every member of the alliance could vote), this to prevent a player who went inactive or just fell from grace to remain in a spot where he/she is not wanted anymore by the populace.
Would be neat to have a ranking on the alliances as well so there is some sort of a visual idea to strength of alliances etc.
Mind you that just as the enemy marking on the map, the ally marking on the map should still act independently and alliances like this should not be compulsory.
It'd implement another layer of "tribe" basically wherein the individual tribes are members. Some other pro's of this could be the distinct splitting of numerous shared forums with a bunch of tribes into one separate forum entity "Alliance forum" accessible from an "Alliance" tab on the header menu.
Not sure how this would work with end-game scenario's, but frankly, a lot of newer worlds tend to end in a big hug so alliance win would pretty much be the same idea.
Personally I would not limit the number of tribes able to join an alliance as that isn't the case right now anyway and people usually just don't get along well enough to form world encompassing alliances (except in special cases).