Is it possible to give the player simple risk/reward choices that also affect the story. Ie. The player gets the choice of going through the dark scary wood to get to city x to protect it from attack, or going round the longer easier (and probably losing less soldiers) way but risking the enemy getting more of a headstart on their attack? That way it isn't just the immediate rewards of the decision that matter, but the decision also affects what happens in the storyworld.

Yes. It'll take more time to implement, of course.

I think RTS games employ this idea on a more subtle level already.

Rome: TW's world map presents you with these desicions all the time.

As for it programatically affecting the world in say an RPG, I don't think it would take as much effort as Beige suggests. Taking the shorter route through the woods would give the player more time, but less resources when they get to the city, the opposite would be true if they took the easier, lnoger route.

On a simple level, if the player takes the short route, the game would simply increase the amount of time until the enemy takes city x, although the player would have less men/resources to defend the city. Taking the long route would decrease the amount of time until the city is captured, but the player would have more resources when they got there.

Hmm, I think that this differentiates itself from the normal RPG way of having several different ways of doing the same object . Ie. Fight / Sneak / Barter.
What happens when the game gives each category of solution several different approaches.

Ie. Do you break the window and risk alerting the guards?
Or try to sneak behind them?

Do you make a distraction? Or confront them head on?

etc.