Each player would begin as enemy to all, but as the game advances and gold runs short, allianses (sp?) are formed to start trading routes. The allainsses would be handeled by diplomats. Diplomats are a non-attacking unit that travels from the players home base to any enemy base, to propose a peace treaty. When the diplomat arraives, an automatic message will appear to the enemy with the proposition. The enemy chooses yes (which fires a trigger) or no (which fires another one). Two enemies arent able to become imediatly into allies, they go through a non-agression porcess of about 5 minutes, afterwards the allianse treaty is possible. The diplomatic affairs would be treated through triggers, to avoid cheating, and be completly secret to other players.
To break a alliance, the player should just kill, the enemy diplomat, which turns the players into immidate enemies.
Tribute will play a more important role in this game,since if you need to become neutral or allied to a certain player u offer him, gold, wood or food.
The map would be fairly open, to have big battles and important (vulnerable) trading routes. It would have a lot of resourses, except gold, which will be very scarce (still existent though). And a few well hidden, or hard to reach relics.
Hope you like the idea, and any good senario maker capable of good complex triggerwork, is more than invited to ry to make this senario.