←All memories

The Art of Strategy - Your Ultimate Guide to Game Theory!

 — #Game Theory#CS Basics

Welcome back, strategic thinkers! ♟️ In our previous journey into Game Theory, we scratched the surface of how rational decision-makers interact. Now, we're going to dig deeper, unpacking the core concepts with more detail and exploring the nuances that make this field so endlessly fascinating and applicable.

Game Theory is more than just a set of abstract models; it's a lens that clarifies the complex dance of strategy in economics, politics, biology, computer science, and even our daily lives. If you're ready to enhance your understanding of conflict, cooperation, and decision-making, let's embark on this more detailed exploration!

The Game is On! Deeper into Strategic Form Games

The strategic form (or normal form) is a fundamental way to represent a game. Let's dissect its components and implications more thoroughly.

  • What's a Game? Game Frames Revisited:

    • Players: The decision-makers involved. It's assumed players are rational, meaning they aim to maximize their own payoffs and can make complex calculations to achieve this. Critically, it's often assumed to be common knowledge that all players are rational, that all players know all players are rational, and so on, ad infinitum.
    • Actions/Strategies: An action is a single move a player makes at a point in the game. A strategy is a complete plan of action, specifying what action a player will take in every possible contingency or at every decision node they might encounter. For static games, an action and a strategy can be the same thing.
    • Payoffs: These represent the utility, benefit, or value a player receives for a given outcome of the game (a specific combination of strategies chosen by all players). Payoffs can be ordinal (ranking outcomes) or cardinal (assigning specific numerical values).

  • Dominant Strategies: The Power of Obvious Choices:

    • Strict Dominance: Strategy SiS_i for player ii strictly dominates another strategy Si′S'_i if the payoff for choosing SiS_i is always higher than the payoff for Si′S'_i, regardless of what strategies other players choose. Rational players will never play a strictly dominated strategy.
    • Weak Dominance: Strategy SiS_i weakly dominates Si′S'_i if SiS_i yields a payoff at least as good as Si′S'_i for all opponents' strategy combinations, and strictly better for at least one such combination. While rational players generally avoid weakly dominated strategies, the argument is less forceful than for strict dominance.
    • Iterated Deletion of Strictly Dominated Strategies (IDSDS): This is a powerful solution concept. You identify and eliminate all strictly dominated strategies for all players. This creates a smaller, simpler game. Then, you repeat the process in the reduced game, eliminating any newly strictly dominated strategies. If this process leads to a unique outcome, that's the game's solution.
      • Example: Consider a pricing game where Firm A can price High, Medium, or Low, and so can Firm B. If pricing Low always gives Firm A lower profits than Medium, regardless of Firm B's price, then Low is strictly dominated for Firm A by Medium and can be eliminated.

  • Nash Equilibrium: The Stable Point of No Regrets: Named after John Nash, this is a set of strategies (one for each player) where no player can improve their payoff by unilaterally changing their own strategy, assuming all other players stick to their chosen strategies. It's a state of mutual best response.

    • Pure vs. Mixed Strategies: A pure strategy is a deterministic choice. A mixed strategy involves choosing among several pure strategies randomly, according to pre-defined probabilities. Many games that don't have a Nash Equilibrium in pure strategies (like Rock-Paper-Scissors) will have one in mixed strategies. For example, the Nash Equilibrium in Rock-Paper-Scissors is to play each option with 1/3 probability.

  • Classic Examples with More Nuance:

    • Prisoner’s Dilemma:
      Suspect 2 Stays Silent Suspect 2 Confesses
      Suspect 1 Stays Silent (-1, -1) (-10, 0)
      Suspect 1 Confesses (0, -10) (-5, -5)
      (Payoffs as years in prison; lower is better). For Suspect 1, Confess strictly dominates Silent (0 > -1 if S2 is Silent; -5 > -10 if S2 Confesses). Same for S2. Thus, (Confess, Confess) is the unique Nash Equilibrium and the outcome of IDSDS.
      • Broader Implications: This simple game models many real-world situations like arms races (both countries arm, though both would be better off disarmed), price wars, or contributions to fighting climate change (individual nations may prefer not to curb emissions due to cost, even if global cooperation is better for all).
    • "Stravinsky" (Battle of the Sexes):
      He goes to Stravinsky He goes to Football
      She goes to Stravinsky (2, 1) (0, 0)
      She goes to Football (0, 0) (1, 2)
      Two pure strategy Nash Equilibria: (Stravinsky, Stravinsky) and (Football, Football). There's also a mixed strategy Nash Equilibrium. The problem is coordination. How do they pick one? This highlights the role of focal points (Schelling points) – outcomes that seem natural, special, or relevant to the players, even without explicit communication (e.g., if they went to Stravinsky last time, that might become a focal point).
    • Market Equilibrium and Pricing:
      • Cournot Duopoly: Firms compete by choosing quantities. Each firm's best-response quantity depends on the quantity chosen by the other. The Nash Equilibrium occurs where their best-response functions intersect.
      • Bertrand Duopoly: Firms compete by choosing prices. If firms sell identical products and have the same constant marginal cost, the surprising Nash Equilibrium is for both firms to price at marginal cost (like perfect competition), assuming consumers buy from the cheapest seller.

Information is Power: Deeper into Perfect vs. Imperfect Information ️‍️

The structure of information flow is critical.

  • Perfect Information Games: All players know the full history of the game (all previous moves by all players) whenever it's their turn to move. There's no private information about past actions.

    • Strategies in Extensive Form: These games are often represented by a game tree (extensive form). A strategy for a player is a complete plan that specifies their choice at every decision node they might reach in the tree.
    • Games with Two Players: Chess, Go, Tic-Tac-Toe are classic examples.
    • Backward Induction: This is the primary method for solving finite perfect information games.
      1. Start at the terminal nodes (final outcomes) of the game tree.
      2. Move to the decision nodes just before the terminal nodes. For each of these nodes, determine the optimal action for the player whose turn it is, assuming they want to maximize their payoff given the outcomes that would follow.
      3. Replace these decision nodes with the payoffs that result from the optimal action.
      4. Continue this process backward up the tree until you reach the initial node. The path determined by these optimal choices constitutes a subgame perfect Nash equilibrium (SPNE) – a Nash equilibrium that is also a Nash equilibrium in every subgame of the original game.
      • Example: A simple game tree like "Player 1 chooses A or B. If A, Player 2 chooses C or D. If B, game ends." Backward induction would first analyze Player 2's optimal choice between C and D if A is chosen.
    • Electoral Competition: Median Voter Theorem:
      • Assumptions: Voters' preferences are single-peaked (they have an ideal point, and their utility decreases as the policy moves away from this ideal point in either direction) and distributed along a single dimension (e.g., liberal-conservative). Candidates are purely vote-maximizing.
      • Implication: Both candidates will locate their platforms at the ideal point of the median voter. If a candidate deviates, the other candidate can capture more than half the votes by positioning slightly closer to the median.

  • Imperfect Information Games: At least one player, when making a decision, does not know the complete history of the game. This could be because moves are simultaneous or because some actions are hidden.

    • Information Sets: In game trees, an information set for a player is a collection of decision nodes that the player cannot distinguish between. When a player is at an information set, they know they are at one of the nodes in the set, but not which specific one. A strategy must specify the same action for all nodes within an information set.
    • Strategies: Still a complete plan, but it must specify actions for each information set a player might encounter.
    • Games with Chance Moves: These games include random events controlled by "Nature."
      • Example: In Poker, the dealing of cards is a chance move.
      • Players maximize their expected payoff, which is the sum of (payoff of an outcome ×\times probability of that outcome), over all possible outcomes.

Dealing with Uncertainty: Deeper into Bayesian Games & Static Encounters

When players lack information about other players' payoffs, preferences, or strategies, we enter the realm of incomplete information, modeled by Bayesian games.

  • Bayesian Games (Games of Incomplete Information):

    • Each player has a "type," which is private information relevant to their payoffs (e.g., a firm's production cost, a buyer's valuation for a good).
    • Players have beliefs (prior probability distributions) over the possible types of other players. These beliefs are updated using Bayes' Rule if new information becomes available (though in static Bayesian games, updating isn't the focus).
    • A strategy for a player in a Bayesian game is a function that specifies an action for each possible type that player might be.
    • Bayesian Nash Equilibrium (BNE): A set of strategies (one for each type of each player) such that each type of each player is choosing an action to maximize their expected payoff, given their beliefs about the opponents' types and given the strategies being played by the opponents' types.

  • Cournot’s Duopoly with Imperfect Information:

    • Two firms (duopoly) choose quantities to produce simultaneously.
    • Each firm knows its own production cost (its type, e.g., cLc_L for low cost or cHc_H for high cost) but is uncertain about the other firm's production cost. It has a probability belief (e.g., believes the other firm is low cost with probability pp and high cost with probability 1−p1-p).
    • Each firm's chosen quantity will be a function of its own cost. For example, a low-cost firm might produce more. In equilibrium, each firm's quantity choice maximizes its expected profit given its cost and its belief about the other firm's cost and quantity choice.

  • Public Goods Games with Incomplete Information:

    • Players simultaneously decide how much to contribute to a public good. The total amount contributed provides a benefit to all players, but contributing is costly for the individual.
    • If players have private information about their valuation of the public good or their cost of contribution, it becomes a Bayesian game.
    • This can exacerbate the free-rider problem (tendency for individuals to under-contribute, hoping others will bear the cost). Uncertainty about others' valuations might make players even more conservative in their contributions. This is related to the Tragedy of the Commons, where shared resources are overused due to individual incentives conflicting with collective well-being.

  • Auctions with Incomplete Information:

    • Each bidder has a private valuation for the item (their type). This is the classic setup for most auction theory.
    • Strategies involve deciding how much to bid as a function of one's private valuation.
    • In common value auctions (where the item has the same true value to everyone, but bidders have different private estimates of this value, e.g., an oil lease), bidders face the winner's curse: the winning bid often comes from the person who most overestimated the item's value. Rational bidders will shade their bids downwards to account for this.

  • Static Games with Varying Information Structures:

    • One-sided complete information: Player A knows Player B's type, but B doesn't know A's type. Player A can use their knowledge to their advantage.
    • Two-sided incomplete information: As in the Cournot example, both players have private information. This is a very common modeling scenario.
    • Multi-sided incomplete information: With many players, each having private information, the complexity of forming beliefs and determining optimal strategies increases significantly. Market interactions often fall into this category. The impact of these asymmetries is that players must make decisions based on expected values and consider how their actions might reveal (or conceal) their own private information.

Making Moves & Deals: Deeper into Signaling, Bargaining & Mechanism Design

Many strategic interactions are dynamic and involve communication (explicit or implicit) and negotiation.

  • Signaling Games: One informed player (Sender, S) takes an action (sends a signal) to influence an uninformed player (Receiver, R), who then takes an action that affects both players' payoffs. The Sender's type is private information.

    • Credibility of Signals: For a signal to be informative, it often needs to be costly in a way that only certain types would be willing to incur it. This is the essence of Spence's job-market signaling model, where high-ability individuals invest in education (a costly signal) to differentiate themselves from low-ability individuals. The cost of education must be lower for high-ability types for the signal to be credible.
    • Equilibria:
      • Separating Equilibrium: Different types of Senders choose different signals, allowing the Receiver to perfectly infer the Sender's type.
      • Pooling Equilibrium: All types of Senders choose the same signal, so the signal conveys no information, and the Receiver relies on their prior beliefs.
      • Partially pooling equilibria are also possible.

  • Bargaining: Dividing the Pie Strategically:

    • Rubinstein Bargaining Model with Alternating Offers:
      • Two players bargain over how to split a surplus (e.g., a dollar). They make alternating offers.
      • A key element is the discount factor (δi\delta_i for player ii), where 0<δi<10 < \delta_i < 1. This represents players' impatience: a dollar tomorrow is worth less than a dollar today. A higher discount factor means more patience.
      • The unique subgame perfect equilibrium involves an immediate agreement. The player making the first offer gets a larger share, and this share depends on both players' discount factors. The more patient a player is (higher δ\delta), the better the deal they can secure.
    • Nash Bargaining Solution (Axiomatic Approach): This is a non-strategic approach. It defines a "fair" or "reasonable" outcome based on four axioms:
      1. Pareto Efficiency: No other agreement makes at least one player better off without making any player worse off.
      2. Symmetry: If the players are identical in terms of their utility functions and disagreement points, they should receive equal gains.
      3. Independence of Irrelevant Alternatives (IIA): If a solution is chosen from a set of possible agreements, and this set is then shrunk (but the original solution and disagreement point remain), the original solution should still be chosen.
      4. Scale Invariance (or Invariance to Equivalent Utility Representations): The solution should not change if a player's utility function is linearly transformed (e.g., converted from dollars to cents).
      The solution is the agreement that maximizes the product of the players' gains from their disagreement points (the Nash product).
    • Relation of Axiomatic and Strategic Model: The Rubinstein model (a strategic, process-oriented model) provides a non-cooperative foundation for the Nash Bargaining Solution (an axiomatic, outcome-oriented model). As the time delay between offers in the Rubinstein model approaches zero (or players become almost infinitely patient relative to the delay), the SPNE division of the surplus converges to the division predicted by the Nash Bargaining Solution.

  • Two Illustrations – More Detail:

    • a. Trade in a Market: Consider a buyer with valuation VBV_B and a seller with cost CSC_S, where VB>CSV_B > C_S. A trade is mutually beneficial. The price PP such that CS≤P≤VBC_S \le P \le V_B creates a surplus of VB−CSV_B - C_S to be divided. The exact price will depend on the bargaining protocol (e.g., who makes the first offer, alternating offers) and the players' patience or outside options. If bargaining breaks down, the surplus is lost.
    • b. Bargaining in Wireless Network Auction: After a spectrum auction, firms might hold licenses for adjacent blocks of spectrum. They might need to bargain over how to coordinate their use to avoid interference or to enable more efficient use of the spectrum (e.g., by agreeing on guard bands or technology standards). The outcome of this bargaining will affect the value derived from their auctioned licenses. Their relative bargaining power, discount factors, and the specific bargaining protocol will influence the terms.

  • Auction and Mechanism Design with Applications – Deeper Dive:

    • Auctions:
      • We discussed the four main types. The Vickrey Auction (second-price sealed-bid) is notable because it is truthful (dominant strategy for bidders is to bid their true valuation), which is a desirable property for achieving efficiency.
    • Mechanism Design: This is about setting up the rules of interaction to achieve specific societal or system-wide goals, understanding that participants will act strategically.
      • The Revelation Principle: This powerful principle states that if a social choice function can be implemented by some mechanism (in Bayesian Nash equilibrium), then it can be implemented by a direct mechanism in which participants truthfully report their private information (their types), and the mechanism then computes the outcome. This simplifies the search for optimal mechanisms.
      • Applications in CS: Resource allocation in cloud computing, task scheduling in distributed systems, designing recommendation systems that elicit truthful preferences, setting up peer-to-peer file-sharing protocols that incentivize sharing. For instance, designing an ad auction (like Google's generalized second-price auction) involves choosing rules for how ad slots are allocated and priced to maximize revenue while encouraging participation and truthful (or near-truthful) bidding.

Key Takeaways: Strategy is Now Even Clearer!

This deeper exploration of Game Theory has hopefully illuminated more of its richness and power. We've reinforced that:

  • Clearly defining players, strategies, payoffs, and information structures is paramount.
  • Nash Equilibrium remains a central solution concept, but understanding its forms (pure, mixed, subgame perfect, Bayesian) is key.
  • Information asymmetry (incomplete and imperfect information) profoundly impacts strategic choices, leading to concepts like Bayesian Nash Equilibrium.
  • Dynamic interactions involving signaling, bargaining, and repeated play add layers of complexity and realism.
  • Mechanism Design shows how we can proactively engineer strategic environments to achieve desirable outcomes.

Game Theory is not just an academic discipline; it's a practical toolkit for navigating a world full of interdependent decisions. The more deeply we understand its principles, the better equipped we are to analyze complex situations, predict behavior, and make more informed strategic choices ourselves.