Table of Contents
The chess master sits across from her opponent, eyes narrowed. Every move she considers depends on a simple question: does she need to remember how they got here, or only where they are right now?
This question echoes through every repeated interaction in life. Your relationship with your roommate. Your negotiations with clients. Your decisions about whether to cooperate with colleagues. Game theory has spent decades wrestling with when memory matters and when it becomes dead weight.
The Elephant That Forgets Everything
Picture an elephant. Everyone knows elephants never forget. Now imagine an elephant that forgets everything that happened more than five seconds ago. Sounds ridiculous, right? Yet this forgetful elephant might actually make better decisions than its memory champion cousin.
This is the essence of a Markov strategy. Named after Russian mathematician Andrey Markov, these strategies operate on a beautifully simple principle: the present state contains all the information needed to make optimal decisions. The past might be interesting for historians, but for decision makers it’s just noise.
Consider a simple scenario. Two companies sell identical products on the same street. Every month, each company decides whether to price high or price low. If both price high, they split generous profits. If both price low, they split meager earnings. If one goes low while the other stays high, the low pricer steals all the customers and gets fat profits while the high pricer gets nothing.
A Markov strategy in this game might work like this: look at what your competitor did last month. If they priced high, you price high. If they priced low, you price low. Simple. Clean. No need to remember that three years ago during a price war they betrayed you for six consecutive months.
The current state (their last action) determines your next move. The rest is archaeology.
The Librarian Who Remembers Every Slight
Now meet the opposite approach. History dependent strategies keep detailed records. They remember every move, every betrayal, every cooperation. They are the librarians of game theory, cataloging every interaction in precise detail.
The most famous history dependent strategy is called Tit for Tat. The name captures its essence: whatever you did to me last time, I do to you this time. But even Tit for Tat is relatively simple as far as memory goes. More complex history dependent strategies might say: “If my opponent has cooperated at least 80% of the time over the last twenty rounds, and they cooperated in three of the last five rounds, and the total score differential is less than 100 points, then I cooperate. Otherwise I defect.”
These strategies turn every game into a novel. Each decision depends on reading back through previous chapters. They carry grudges. They recognize patterns across hundreds of interactions. They might forgive a betrayal if it was preceded by enough cooperation, or punish a single defection if it comes after a long peaceful period.
Returning to our pricing example, a history dependent strategy might say: “If my competitor has undercut me more than twice in the last six months, I will price low for the next three months regardless of what they do. If they maintained high prices for a full year, I will match their pricing unless they defect twice in a row.”
The strategy doesn’t just look at where you are. It cares deeply about how you got there.
When Amnesia Becomes Wisdom
Here’s where things get counterintuitive. You might assume that more information always leads to better decisions. After all, isn’t knowledge power? Shouldn’t strategies that remember everything outperform strategies that forget?
Not necessarily.
Consider a repeated game with a clear structure. You’re in state A or state B. In state A, action X is clearly best. In state B, action Y is clearly best. The history of how you moved between states carries no useful information about what to do next. Remembering whether you were in state A five turns ago tells you nothing about optimal play right now.
A Markov strategy that simply responds to the current state makes optimal choices. A history dependent strategy that tracks everything wastes mental energy (or computational resources, if we’re talking about algorithms) remembering irrelevant details. It’s like navigating with a map while also memorizing every street you passed yesterday. The map alone would suffice.
The Folk Theorem’s Whispered Secret
Game theorists have a result called the Folk Theorem. The name itself is ironic, suggesting something everyone knew but nobody had formally proven. The theorem essentially says: in repeated games that continue indefinitely, almost any outcome can be sustained as an equilibrium if players are patient enough.
Want both players to cooperate forever? Possible. Want them to alternate between cooperation and defection in elaborate patterns? Also possible. Want them to maintain any of thousands of different average payoff levels? All possible, as long as players care enough about the future.
The Folk Theorem originally worked with history dependent strategies. Players would threaten: “If you betray me, I will remember this betrayal for eternity and punish you accordingly.” These threats require memory. They require tracking who did what when.
Arguably you can achieve the same outcomes with Markov strategies. You don’t need to remember the entire history. You just need enough states to capture the relevant information.
Think of it like this. Instead of your strategy saying “Remember that on turn 47 my opponent defected, and also on turn 132, and the cumulative effect of these defections combined with their cooperation on turns 15, 23, and 94 means I should…” you can create states that summarize the relationship status.
State: Good Relations. If opponent cooperates, stay in Good Relations. If opponent defects, move to Soured Relations. In Good Relations, cooperate. In Soured Relations, defect until opponent cooperates three consecutive times, then return to Good Relations.
Same end result. Fraction of the memory required.
The Efficiency Paradox
Simple strategies can achieve complex outcomes. This statement sounds impossible, like saying you can paint the Mona Lisa with three brushstrokes. Yet game theory proves it mathematically.
The trick lies in understanding what matters. History dependent strategies remember everything because they don’t know in advance which details will prove relevant. They’re pack rats of information. Markov strategies, designed carefully, remember only what affects future payoffs.
Imagine a game where players’ reputations matter. A history dependent strategy might track: “My opponent has cooperated 247 times, defected 13 times, the longest cooperation streak was 89 rounds, their average payoff is 47.3 per round, and the standard deviation of their choices is 0.23.”
A Markov strategy achieves the same outcome with states like: “Trusted Partner,” “Under Probation,” or “Broken Trust.” The opponent’s actions trigger transitions between states. Each state prescribes an action. The numerical details become irrelevant once you’ve identified the meaningful categories.
This is the ultimate simplification. Not dumbing down, but distilling complexity to its essential elements.
When Memory Actually Matters
Fairness demands acknowledging where Markov strategies fall short. Some games genuinely require historical awareness in ways that simple states cannot capture.
Consider a game where players have private information that gets revealed gradually through play. Your opponent’s past actions might signal something about their hidden characteristics or preferences. Early cooperations might indicate they’re a cooperative type. Early defections might reveal aggressive tendencies. This learning process inherently depends on the sequence of observations, not just a summarized state.
Or imagine games where the relationship itself evolves in meaningful ways. Perhaps early interactions build trust that changes what’s possible later. Perhaps patterns of behavior create expectations that become self fulfilling. The narrative arc matters, not just the current chapter.
In these cases, history dependent strategies maintain their advantage. They can track subtle patterns, recognize trends, and adjust to complex conditional logic that would require exponentially many states to represent in Markov form.
The Prisoner’s Dilemma Revisited
The classic Prisoner’s Dilemma illustrates these concepts beautifully. Two criminals are arrested. The prosecutor offers each a deal: betray your partner and go free while they serve ten years. If both betray, both serve five years. If both stay silent, both serve one year.
Played once, betrayal dominates. Both prisoners defect, both serve five years. Tragedy all around.
But play this game repeatedly and everything changes. Now cooperation becomes possible through the shadow of future interactions. If you betray me today, I can punish you tomorrow. This threat sustains cooperation.
Tit for Tat, a history dependent strategy, famously performs well in repeated Prisoner’s Dilemmas. Start by cooperating. Then copy whatever your opponent did last round. Elegant and effective.
But you can build an equivalent Markov strategy. State A: Both players cooperated last round. Action: Cooperate. State B: I cooperated, they defected. Action: Defect. State C: I defected, they cooperated. Action: Return to cooperation. State D: Both defected. Action: Defect.
These states capture the Tit for Tat logic without explicitly remembering history. The current state embodies all relevant past information.
Computational Efficiency and Bounded Rationality
Real players, whether humans or computers, face limits. Memory isn’t free. Computation isn’t instant. This reality favors Markov strategies in practice.
A strategy that must analyze thousands of past moves before making each decision burns resources. It’s slow. It’s prone to errors when memory fails. It struggles to scale when facing multiple opponents or playing multiple games simultaneously.
A Markov strategy makes decisions fast. Look at the current state, apply the rule, done. This efficiency matters in real world applications from algorithmic trading to artificial intelligence to everyday human interactions.
Humans especially benefit from Markovian thinking. We’re notoriously bad at remembering precise details. We confuse sequences, misremember frequencies, and let emotions color our recollections. But we’re quite good at categorizing situations and applying rules to categories.
“My boss seems happy today” is a state we can recognize and respond to. “My boss’s mood correlates 0.73 with the S&P 500’s performance with a two day lag, and today the market rose 1.3% so I should expect elevated happiness tomorrow” is information humans can’t reliably process.
The Design Question
If Markov strategies can match history dependent strategies for outcomes while using less memory, why ever use history dependence?
The answer lies in design difficulty. Creating an optimal Markov strategy requires knowing in advance which states matter. You must identify the relevant dimensions of the situation and build your state space accordingly. This demands insight into the game’s structure.
History dependent strategies, by contrast, can be designed more mechanically. Just remember everything and apply conditional rules. It’s wasteful but straightforward.
This creates an ironic reversal. Simple strategies (Markov) require sophisticated design. Complex strategies (history dependent) allow for simpler design processes.
The Philosophical Dimension
Strip away the mathematics and you find a question about existence itself. Are we who we are because of our entire life story, or only because of our current circumstances?
Markov strategies say: you are your present state. The journey that brought you here matters only insofar as it determined where “here” is. Two people in identical current situations should make identical choices regardless of their different pasts.
History dependent strategies say: the path defines the destination. Who you are depends on where you’ve been. Identical current circumstances don’t imply identical optimal actions if the histories differ.
Real human behavior mixes both perspectives. We categorize situations Markovially (this is a first date, this is a job interview, this is a negotiation) but we also carry our personal histories into each moment. The balance between these approaches shapes personality itself.
Practical Implications
For anyone designing strategies, whether in business, politics, or personal life, the Markov insight offers liberation. You don’t need to track everything. You don’t need perfect records of every interaction. You need to identify the states that matter and respond appropriately to each state.
A company competing in markets needs to recognize a few key states: we lead the market, we’re tied, we’re behind, prices are stable, prices are volatile. Responding effectively to these states beats maintaining exhaustive competitive intelligence on every historical price point.
A person managing relationships needs to recognize states: this relationship is healthy, this relationship needs attention, this relationship is toxic. Responding to these categories beats keeping mental scorecards of every favor given and received.
The art lies in choosing the right states. Too few and you miss important distinctions. Too many and you’ve recreated the complexity of full history dependence. The sweet spot captures meaningful differences while discarding noise.
The Ultimate Simplification
Game theory reveals a profound truth: simplicity is not simplistic. Markov strategies represent the ultimate simplification not because they ignore complexity but because they distill it perfectly.
They answer the chess master’s question definitively. For many games, especially those with clear structure and repeated play, you only need to know where you are right now. The journey that brought you here has served its purpose. It determined your current state. Now that state determines your optimal move.
This doesn’t mean forgetting the past entirely. It means recognizing that the past’s influence flows through the present. The present state is memory compressed into actionable form.
…
The forgetful elephant, it turns out, might navigate the world just as well as its remembering cousin. Perhaps better, since it carries no unnecessary weight. It sees the landscape as it is, not filtered through the accumulated baggage of everywhere it’s been.
That’s not ignorance. That’s wisdom distilled to its essence. That’s the ultimate simplification.
