In a recent opinion article by James Portnow entitled The Problem Of Choice, the idea was posited that there are two types of decisions that a player can be faced with in a game: "problems" and"choices".
The former is something that involves a "right answer" such as a mathematically optimal solution. Therefore, theoretically it can be solved. We are all familiar with such challenges ingames -- especially when designers make them all too transparent. The other type of decision is the "choice".
These are a little more amorphous in that there is no "right answer". Games such as Bioshock (i.e. the Little Sisters) have these elements but others such as Black & White and the two Fable games are rife with them. In fact, the entire game mechanic is built upon the idea of "make a choice and change the whole experience."