Nice post
One of the problems along this line is workers in Civ V, they have to choose between every tile in the empire and also what to build, the larger the empire the more choices it has to make increasing exponentially the turn time, then you multiply it by the number of workers plus the same thing for every civ.
I think that if the turn times were five seconds instead of forty many more people would like Civ V or at least hate it less
Actually workers aren't so bad, the number of tiles in your own territory is a fairly small number. The number of improvements you can put on a tile is fairly small as well. You're probably only looking at 100,000 or so possibilities in a typical setting.. the AI uses a function to score each of them, and picks the improvement that gives the maximum score to build. The score can depend on factors like worker-distance, a benefit value of the improvement, whether it replaces an existing improvement, or pretty much anything at all really. Computing the actual function scores for each tile improvement probably takes less than 1 millionth of a second, so doing all 100,000 and picking one, probably takes about 1/10th of a second. Even if there are 40 AI workers in the game, and you recalculate these values all the time, the workers are largely staying improving their current improvement, so you only have to calculate lets say 15 workers a turn, which takes probably 1.5 seconds at worst.
It's not actually exponential because it's not critical to consider what worker A is going to do, when you are deciding what to do with worker B. You don't have to consider all possible orderings of all possible workers to assign tasks.