A [good] game is a series of interesting choices - Sid Meier (Rollings & Morris 2000, p. 38). 

One of the defining features of video games is interactivity, however one could argue that the amount of decisions and interactions presented to players in most video games, with regards to narrative, are still often very limited and rarely have meaningful and/or long term results within the game story.

Ideally the player should be presented with multiple courses of action which will each result in different and meaningful results, fulfilling the players phychological need for autonomy (Przybylski, Andrew K, C. Scott Rigby, and Richard M. Ryan. 2010), and motivating the player to engage and interact with the environment and story.

Player agency vs linear narrative:

The clash between player agency and linear narrative was first described by Aylett, R. (1999), who introduced the concept of emergent narrative as the potential solution, however it has been argued that emergent narratives often lack the emotional impact of linear pre-designed narrative.

A big problem when it comes to the typical linear method of storytelling is that it does not allow for participation, at least not without a clever story teller that is capable of inventing coherent story on the fly. 

In the case of games, this would require a very complicated story generator AI, capable of understanding story structure, and making sure that the story generated is coherant, as stated by Earnest Adams (2013, pp 11) in the following line: “at any point in the story, the conditions that obtain at that point in the story have got to be rationally derivable from everything that went beforehand“.

I would say we are still a long way off such AI.

The most common solution to this problem of player participation is to constrain player agency/freedom, not letting the player do anything that would go against the narrative, by either limiting the actions that can be performed by the player or by "gating" the player with game over screens.

Another increasingly common solution is to offer branching narratives, although they are still often quite constraining and require the content to be pre designed, at a large cost to manpower and time, and limiting the interaction available to players, as stated by Louchart S, et al. (2008), Branching techniques developed over the years have created limited forms of interaction.

Adams (2013, pp 16) concludes that player agency and linear narratives are not mutually exclusive but rather in an inverse relationship, the designer has to sacrifice narrative control in exchange for interactivity, and vice versa. He also states (pp 24) : “It’s not our job to tell stories. It’s our job to build worlds in which players can live a story of their own creation”

Social agents as a solution:

"Stories are about people, not things" - Chris Crawford (2012), he's also doing a kickstarter game.

Often in games, Non Player Characters (NPC)'s remain very un-dynamic with regards to personality, motivations, history and relationships, they mostly just react to what exists and/or happens around them. The ideal situation would be to have them interact with each other and with the player based on these previously mentioned traits, and the results of said interactions should affect them profoundly and fundamentally.

Allowing agents to form groups based on mutual feelings, motivations,interestests,etc will add an extra layer of depth to these agents, one could go as deep as having information networks.

As stated by Grey, J., & Bryson, J. J. (2011), “The interactionist approach — dynamic, behaviour based or sometimes ‘reactive’ AI — is sometimes denigrated as being too simple to carry a narrative plot, because the individual agents ‘only’ react to their environment and the opportunities is presents. In both individual agents and game AI more generally, many have felt a need to reintroduce the structure of a more formal planning system “on top” of the behaviour based system, in order to guarantee structured, coherant plans.“

There are multiple examples of work that dive into this area such as the systems proposed by Luis Guimaraes, Doran, J., & Parberry, I. (2011, June), Swartjes, I., & Vromen, J. (2007, November), Loyall, A. B. (1997), Dwarf Fortress, and Ken Levine.

Dynamic drama

Story telling has played a central role in all of human history for aeons, as such the structure of narrative has had a long time to get established, with theories on narrative structure dating back to Aristotle (350 B.C.E).

Freytags pyramid: The typical dramatic structure.

This structure is very engrained in the way stories are told and received, as such it is very important that the player is feeling the right amount of dramatic tension at the right time.

Some games have used an dynamic drama manager to control the dramatical structure of the story depending on the how the player is progressing, such as Left 4 Dead's director AI (Turtle Rock Studios, 2008), Facade's drama manager AI (Mateas, M., & Stern, A. 2005, June) and the system proposed by Yu, H., & Riedl, M. (2012, June).

References:

Adams, Ernest W. (2013). Resolutions to some problems in interactive storytelling. (Doctoral dissertation, University of Teesside).

Aristotle, The Poetics. Buffalo, NY: Prometheus Books, 1992. T. Buckley translation. Original work published in 350 B.C.E.

Aylett, R. (1999). Narrative in Virtual Environments - Towards Emergent Narrative. In Proceedings of the AAAI fall symposium on narrative intelligence. 83-86.

Crawford, C. (2012). Chris Crawford on interactive storytelling. New Riders.

Doran, J., & Parberry, I. (2011, June). A prototype quest generator based on a structural analysis of quests from four MMORPGs. In Proceedings of the 2nd International Workshop on Procedural Content Generation in Games (p. 1). ACM.

Grey, J., & Bryson, J. J. (2011). Procedural quests: A focus for agent interaction in role-playing-games. In Proceedings of the AISB 2011 Symposium: AI & Games (pp. 3-10). University of Bath.
 

Louchart, S., Aylett, R., Kriegel, M., Dias, J., Figueiredo, R., & Paiva, A. (2008). Authoring emergent narrative-based games. The journal of game development. 3 (1), 19 .

Loyall, A. B. (1997). Believable agents: building interactive personalities (Doctoral dissertation, Mitsubishi Electric Research Laboratories).

Mateas, M., & Stern, A. (2005, June). Structuring Content in the Façade Interactive Drama Architecture. In AIIDE (pp. 93-98).

Przybylski, Andrew K., C. Scott Rigby, and Richard M. Ryan. (2010). A motivational model of video game engagement. Review of general psychology. 14(2), 154.

Rollings, A., & Morris, D. (1999). Game Architecture and Design. Coriolis Group Books. 38

Swartjes, I., & Vromen, J. (2007, November). Emergent story generation: Lessons from  improvisational  theater. In Intelligent Narrative Technologies: Papers from the  AAAI  Fall Symposium. Number  FS-07-05 in AAAI Fall Symposium Series.

Yu, H., & Riedl, M. O. (2012, June). A sequential recommendation approach for  interactive personalized  story generation. In Proceedings of the 11th  International Conference on Autonomous Agents and  Multiagent Systems- Volume 1 (pp. 71-78). International Foundation for Autonomous Agents and  Multiagent Systems.