Missions
I think the player or the AI should be able to 'commit' to a mission. Commiting is the complement of rejecting. When a cation commits to a mission, it means it will wholeheartedly embrace it and try to accomplish it with the best of its abilities. Fulfilling a mission without commiting to it should have a smaller relationship benefit.
It should also be possible to be able to, as a mission, ask a faction to 'defend gravwel X for X minutes'.
Additionally, I think there could be a 'goodwill' balance between each faction. Goodwill can be 0 for both, or lean toward a single side of the relation. By performing a 'goodwill' commitment, Faction Awill do a mission for Faction B no financial reward. The catch is that the faction A still gets the relationship bonus, and goodwill points instead of the financial reward. For each goodwill point From Faction A towards faction B, the next time Faction A puts a mission to faction B, B will feel more obliged to commit to A's mission. If faction B performs a goodwill mission however, it will reduce the goodwill balance of Faction A toward it. If it is already 0, the balance will turn, and faction A will get a positive balance over faction B.
This adds a strategic element to missions, where you will attempt to get a positive balance to convince a faction to do missions of strategic importance.
The AI should also be smart about putting missions for faction-vs-faction actions. If C is a neighbor of D and B, and knows that A is allied with B but not D, and wants to boost its relationship with A, it should be smart about putting missions against D, which A is more likely to want to accomplish.
Where is the bargain?
Actually, I think missions should be explictly accepted, or 'commited to', before any faction receives any reward besides the indirect 'positive bonus for military actions against a common enemy'. Once a mission is offered, there should be a possibility of bargaining. The other side should analyze it, and either reject the mission outright or do a counter-offer: 'If you pay me X more credits/metal/crystal I will do it. what do you say?'. Relationship would pay a part on how much reward factions demand to accept a mission.
Likewise, I would like to be able to bargain a ceasefire with one faction. I could offer a ceasefire and say 'make your price', the AI could ask me to break an alliance and attack the faction. If it makes sense strategically, I might do it.
Bargaining could be a way to get to pacts earlier too.
Impossible to win is OK
I personally think that it's OK to have an AI which is 'invincible' given a hard enough game. one player versus 8 unfair AIs with locked teams, for example, should be an endless barrage of enemies which would make it impossible to win.
The AI should not only be a reasonable challenge, it should actively try to win. Of course, it does not need to be 'perfect', or it would be impossible to win.
AI should have its own agenda, regardless of alliances.
The AI should also be aware of the strongest empire and winning conditions, and act accordingly. The AI should be aware - or at least be able to estimate - the empire power based on how many gravwells (it thinks) each faction has, size of fleets last seen etc. to be able to estimate the strongest faction.
Modifiers which would be positive if it were an empire at the middle of the pack should become NEGATIVE if it is the leader; or at least if it is the leader by some margin. In other words, the more the leader faction is ahead of another faction, the military strength bonus would diminish to the point that is reversed to a penalty.
Let me try to flesh out some mechanics for that...
From now on, when I say 'player' it's human. When I say AI, I mean computer-controlled (duh). When I say 'faction' or 'empire', it doesn't matter, it should act the same with either (except on very hard difficulties, where other AIs could have a better chance of getting friendly to each other).
The AI should have its own agenda, and be aiming for the golden prize. Even though it might have a very high relationship with an empire, if that empire becomes more powerful that the AI itself, it should look for opportunities to turn the table arond - and become the strongest.
First of all, being allied does not mean always acting in favor of the allied empire. If the AI's team - I mean allies and cease-fire empires - is the strongest team, it will actively pursue the leadership though.
If the AI's team is not the strongest, the AI's actions would be to indirectly hold back the growth of their allies, while helping it to grow as fast as possible. for example, it should be able to send missions to 'defend planet X for Y minutes', so that it can have one (or more) allies defending its empire while it punches a strong offensive.
If an AI is too much behind the power ladder, though, it will be more inclined to do more direct actions though, such as e.g. give some bounty to the pirates for them to attack the strongest player, even if it is an ally. Or putting up missions with generous bounties to reduce the animosity with currently in-war factions, trying to convince them to attack the strongest faction.
If the AI team is the strongest, and has the strongest faction, the other factions in the same team should be even less scrupulous about underhanded proxy attacks.
Backstabbing anyone?
