I agree this would be a huge improvement! I think the hierarchy of bonuses should be based on size, so that you allocate to the bonus with the fewest territories first. This would be intuitive in the common case of macro bonuses, as it would function the same as how anywhere does now, saving the most flexible allocation possible. On maps with complex semi overlapping bonuses, you could still get what you want, you just have to figure out the precedence. In the case of overlapping and equal size, could just default to alphabetical or something the user can figure out. Since this is an edge case compared with macro bonuses, I don't think this is that big a deal and the user can still get to anything they want!

I absolutely agree with Kris, that this should be trivial, when the bonuses are hierarchical (always deploy from the bottom of the hierarchy first) and would make a lot of maps usable!

Although the problem in general might not be easy to fix in an elegant way, there is a partial fix for plenty of maps with superbonuses, using the same strategy as you must have already implemented with "free armies" that can be deployed everywhere.

Suppose that there is a hierarchy of bonuses: if bonuses A and B overlap, then one of them (the superior bonus) contains all territories of the other (the inferior bonus). Then the armies from the most inferior bonus are deployed first. In this approach, the "free" army could be thought as coming from the most superior bonus. You could even list the deployed armies in a tree-like structure instead of a list, so that it's easy to track what is deployed and what is not.

Of course, this does not help with maps that have bonuses overlapping partially (Poland Big and the "coast bonus" comes to my mind) or maps with progressive bonuses (Biomes of America, Gotham City, Elitist Africa, etc.). However, it could be a great extension to the current system anyway.

Could you implement it using an eventual consistency strategy. whenever armies are deployed to a territory which is contained within multiple bonuses simply put an "*" beside those bonuses then instead of displaying the typical "x/y deployed to bonus" change it to "?/y deployed to bonus*".
Whenever a bonus reaches its limit in its own right go back to the "x/y deployed to bonus" format and remove the "*".You're hiding some information from the user to keep the UI clean without affecting functionality.

So using your example of:
"Imagine three territories: 1, 2, and 3. There’s a bonus A made up of territories 1 and 2, and a bonus B made up of territories 2 and 3. Both bonuses give 1 army per turn and therefore the player gets 2 income. Imagine a player controls all three territories (and therefore both bonuses), and then tries to deploy an army on territory 2. The game needs to know if it should allocate that army from bonus A or B."
When a player deploys in territory(T) 2 bonuses A and B become unknown. If an army is then deployed in T1 after then bonus A's value is full in its own right and will evaluate and then subsequently B becomes known as it is no longer being effected by another bonus.

So does a super bonus of multiple bonuses count as a overlap ? Would it not just be armies gained for bonuses must be deployed in bonuses and armies gained from superbonuses could be deployed to any bonus within the superbonus?

It is easy to implement - currently we can push units from bonus, and then you can push turn income units (that is the order given by game).

WIth more bonuses (bonus, superbonus, megabonus), first you use local units (bonus), then area units (superbonus) then any bonus above this, then income units but superbonuses should have some kind of hierarchy done by map creator. For easier access when you pick the bonus (deployment phase) the bonus should be shown on the screen (zoomed or extended).

When making maps, the map creator could have a superbonus option that allows you to select several bonuses. The deployed armies would first come from the bonus, then the superbonus then the base armies.

I agree strategies 1 and 2 are not optimal due to the problems you mention. Strategy 3 is definitely best. Second best would be allocate as follows, starting at the top and then ditching whatever alternatives lose a check (something is true for one or more bonuses, but not for all):

1) By whatever bonus still have armies to deploy
2) By bonus size in territories (smallest first)
3) Alphabetically

The last one rather than random so that it is deterministic. Players will inherently learn that "clicking first on Paris and then on Lyon works for this" even if they don't know the rule.

I think you can probably get a correct universal pseudo-code implementation of strategy 3 by going over the implementation together with others with coding experience. You've probably worked out almost every detail by now, so a fresh pair of eyes could maybe point you in the direction of why it does not work correctly. Unless you already have the right design and have made some mistake in the actual coding, that is.

When in doubt of whitch bonus to allocate always choose the small one first. Most overlaped territories, in most maps, are hyperbonus, that cover complete bonus together. If they have the same size choose randonly.

If it's an implementation issue of not knowing where the bonuses are coming from, it might be possible to do it the same way as the "anywhere" bonuses do today. The bonuses would pull from the most local bonus first and then the others and finally the anywhere bonus.

The one thing I'd really like to see too. For some large maps it might be helpful to highlight territories you've not yet deployed to also.

Agreed. It's a shame not to be able to play any of the more fun maps with local deployment.

That would be a superb addition to the game for sure.