Game theory - Solution Concepts

Game Theory Solution Concepts Introduction A solution concept in game theory is a prediction of which strategy each player will choose, or equivalently, which outcome will result from a game. The most fundamental solution concepts are based on the idea of equilibrium—a situation where no player wants to change their strategy given what the other players are doing. This guide covers the major equilibrium concepts you'll encounter, from the most foundational to more refined variations. Nash Equilibrium: The Foundation Definition and Core Intuition A Nash equilibrium is a set of strategies (one for each player) where no player can increase their payoff by unilaterally deviating—that is, by changing their own strategy while holding all other players' strategies fixed. The key word here is unilaterally. A player might wish others would choose different strategies, but given what others are actually doing, they have no incentive to deviate alone. Why This Matters Nash equilibrium captures a natural stability condition: if you're in a Nash equilibrium, there's no individual pressure for any player to change their behavior. This makes it useful for predicting outcomes in strategic situations. An Intuitive Example Imagine two students choosing where to study: either the library or a café. Each student prefers to study where the other student is (for companionship), but if they end up in different places, both would rather be alone than with a stranger. If both go to the library: neither wants to switch alone (that would leave them with a stranger) If both go to the café: same reasoning applies If they're in different locations: each might want to switch if the other stays put, but individually switching away from a stranger doesn't help Here, "both in the library" and "both in the café" are both Nash equilibria. Pure-Strategy Nash Equilibrium A pure-strategy Nash equilibrium involves each player choosing a single, definite action (rather than randomizing). This is the simplest form of Nash equilibrium. Finding Pure-Strategy Equilibria To find pure-strategy equilibria, check every possible combination of strategies. For each combination, ask: would any player want to deviate? If no one wants to deviate, you've found an equilibrium. Example: The Coordination Game Consider the sequential game shown above. Trace through each path: If player 1 chooses C and player 2 chooses D, player 1 gets payoff 1 If player 1 chooses C and player 2 chooses O, player 1 gets payoff 2 By examining all terminal nodes and working backward, you can identify which strategy combinations constitute equilibria (we'll discuss this more formally under subgame perfect equilibrium). Mixed-Strategy Nash Equilibrium When and Why Players Randomize A mixed-strategy Nash equilibrium is one where at least one player randomizes—that is, plays different actions with specified probabilities rather than playing one action with certainty. This seems counterintuitive at first: why would a rational player flip a coin? The answer is that randomization can be an equilibrium response when the game structure creates a "mismatch" that pure strategies can't resolve. The Indifference Condition The key insight to mixed-strategy equilibrium is this: if a player is randomizing over several actions in equilibrium, the opponent must be making them indifferent between those actions. Here's why: suppose player 1 is mixing between action A (with probability $p$) and action B (with probability $1-p$). For player 1 to actually want to randomize (rather than play just A or just B), the expected payoff from A must equal the expected payoff from B. The opponent's strategy choice—reflected in the probabilities they assign to their actions—determines those expected payoffs. Finding Mixed Equilibria To find a mixed-strategy equilibrium: Assume each player randomizes over certain actions Write out the opponent's expected payoff from each action they might choose Set these expected payoffs equal to each other Solve for the randomization probabilities Example: Matching Pennies Consider the classic game where one player (Matcher) wants heads and tails to match, while the other (Mismatcher) wants them to differ. | | Heads | Tails | |---|---|---| | Heads | 1, -1 | -1, 1 | | Tails | -1, 1 | 1, -1 | In any pure strategy, one player can profitably deviate. The unique equilibrium is: Matcher plays Heads and Tails each with probability $\frac{1}{2}$ Mismatcher plays Heads and Tails each with probability $\frac{1}{2}$ At these probabilities, Matcher gets expected payoff 0 from either action, and Mismatcher gets expected payoff 0 from either action—so neither wants to deviate. A Crucial Point: Existence Every finite game has at least one Nash equilibrium, though it may involve mixed strategies. This is Nash's famous existence theorem. However, not all games have pure-strategy equilibria. Subgame Perfect Equilibrium The Problem with Simple Nash Equilibrium in Sequential Games In sequential games (games played over multiple periods, where players move at different times), some Nash equilibria can rely on non-credible threats—strategies that a player announces but wouldn't actually follow through on. Consider this scenario: "If you enter my market, I'll start a price war that destroys us both." This threat might deter entry (supporting a Nash equilibrium), but it's not credible—if you actually enter, the incumbent wouldn't follow through because a price war hurts them too. Definition: Subgame Perfection A subgame perfect equilibrium (SPE) eliminates such non-credible threats by requiring that the strategy profile constitutes a Nash equilibrium in every subgame—that is, in every possible continuation game starting from any decision point. Intuitively: a threat is credible only if you'd actually carry it out when the time comes. Backward Induction The standard method for finding subgame perfect equilibria in finite sequential games is backward induction: Start at the end of the game tree (the last decision point) At each decision node, determine what the player would choose if that node were reached Work backward to the beginning The resulting path is the unique subgame perfect equilibrium In the tree shown, Player 1 moves first (choosing F or U), then Player 2 moves (choosing A or R at each node). Working backward: At Player 2's right node (after U), Player 2 compares payoffs: A gives 8, R gives 0. Player 2 chooses A (payoff 8). At Player 2's left node (after F), Player 2 compares: A gives 0, R gives 0. Indifferent; suppose Player 2 chooses R (payoff 0). At Player 1's initial node, Player 1 anticipates these responses. Choosing F leads to payoff 0; choosing U leads to payoff 2. Player 1 chooses U. The SPE path is U, then A, yielding payoffs (2, 8). Why SPE is Important for Exams SPE is a critical concept because it's the natural equilibrium notion for sequential games. When you see a game tree on an exam, you should almost certainly be finding the subgame perfect equilibrium, not just any Nash equilibrium. Trembling-Hand Perfect Equilibrium Robustness to Mistakes A trembling-hand perfect equilibrium is a Nash equilibrium that remains an equilibrium even if players occasionally make small mistakes—"trembles." This refinement ensures strategies are robust to human fallibility. More formally: a strategy profile is trembling-hand perfect if it's the limit of completely mixed Nash equilibria (equilibria where every action is played with positive probability) as the mistake probability approaches zero. Why This Matters This concept distinguishes between equilibria that are stable against small perturbations (trembling-hand perfect) and those that aren't. In many games, some Nash equilibria rely on players avoiding certain actions entirely, which is fragile if any small tremble occurs. Importance for Your Exam Trembling-hand perfection is a useful refinement of Nash equilibrium. It's particularly important when multiple Nash equilibria exist and you need to determine which is "more robust." However, it's less commonly tested than SPE; focus on understanding the intuition rather than the formal definition. <extrainfo> Evolutionarily Stable Strategy (ESS) An evolutionarily stable strategy is a concept from evolutionary game theory. A strategy is evolutionarily stable if, when adopted by most of the population, it cannot be invaded by a small fraction of mutants adopting a different strategy. This is similar to trembling-hand perfection but comes from a different motivation: rather than robustness to mistakes, it captures robustness to invasion by mutants. This concept is useful in biological applications and population dynamics but is less central to most game theory exams unless you're specifically studying evolutionary game theory. </extrainfo> Advanced Equilibrium Concepts <extrainfo> Correlated Equilibrium A correlated equilibrium generalizes Nash equilibrium by allowing players to condition their strategies on signals from a public correlation device—essentially a random signal that players can observe. The key difference from mixed Nash: in a correlated equilibrium, the correlation device generates correlated signals (not independent randomization). This can allow players to coordinate better and achieve payoffs impossible under independent mixing. For example, a traffic light correlates drivers' actions: when you see red, you stop; when you see green, you go. This simple correlation device improves efficiency dramatically. Correlated equilibria are mathematically elegant but less commonly examined than Nash or subgame perfect equilibrium, unless your course specifically covers them. </extrainfo> <extrainfo> Core and Shapley Value These are solution concepts for cooperative games where players can form binding agreements and coalitions. The Core consists of payoff allocations from which no coalition of players can improve by breaking away. An outcome is in the core if every coalition of players is satisfied with their allocation. The Shapley Value assigns a unique payoff to each player based on their average marginal contribution across all possible orderings in which players could join a coalition. It's a "fair" allocation principle, though it may not be in the core. These concepts matter most in coalitional games and cooperative game theory, but may be less critical if your course focuses on non-cooperative games (simultaneous-move games). </extrainfo> <extrainfo> Incentive Compatibility and Mechanism Design Incentive compatibility ensures that when players have private information, their best strategy is to truthfully reveal that information. This is central to mechanism design—the field of designing games (mechanisms) to achieve desired outcomes. For example, an auction mechanism is incentive compatible if bidders' dominant strategy is to bid truthfully according to their private valuations. The key insight: you can't just ask people to report their private information; you must structure incentives so that truthful reporting is their best response. This concept is critical if your exam covers mechanism design or auctions, but may be less central in pure strategic game theory. </extrainfo> <extrainfo> Nash Bargaining Solution The Nash bargaining solution applies when two players must agree on how to divide a surplus; if they fail to agree, they get a disagreement payoff. The solution selects the allocation that maximizes the product of each player's gain above their disagreement point: maximize $(u1 - d1)(u2 - d2)$ where $ui$ is player $i$'s payoff and $di$ is their disagreement payoff. This solution is elegant and uniquely satisfies natural fairness axioms. However, it's most relevant in courses specifically covering bargaining or cooperative game theory. </extrainfo> Quick Reference: When to Use Each Concept | Concept | When to Use | |---|---| | Pure-strategy Nash Equilibrium | Simultaneous-move games; checking all strategy combinations | | Mixed-strategy Nash Equilibrium | Games with no pure equilibria; equilibria involving randomization | | Subgame Perfect Equilibrium | Sequential games; use backward induction | | Trembling-hand Perfect | When you need to rule out equilibria fragile to small mistakes | | Correlated Equilibrium | When a correlation device is explicitly present in the game | | Core/Shapley Value | Coalitional games with side payments | | Incentive Compatibility | Mechanism design; private information settings | | ESS | Evolutionary or population-based game theory | | Nash Bargaining | Two-player bargaining with disagreement point | The three concepts most likely to appear on a standard game theory exam are Nash Equilibrium (pure and mixed), Subgame Perfect Equilibrium, and possibly Incentive Compatibility or Trembling-Hand Perfection depending on your course focus.