Game Theory - A Very Short Introduction

From charlesreid1

Binmore, K. (2007). Game Theory: A Very Short Introduction. Oxford University Press.

Summary

Here is a summary of "Game Theory: A Very Short Introduction" by Ken Binmore:

  • Chapter 1: The name of the game. This chapter introduces game theory as the study of strategic interaction between rational individuals. It explains that a "game" can refer to any situation where people interact, from courtship to economics to international politics. The chapter emphasizes that game theory works best when people behave rationally, though it can also explain the behavior of mindless animals or companies eliminated by market forces if they act irrationally. It also introduces the concept of utility to measure players' preferences and discusses how Nash equilibrium, where all players make the best reply to others' strategies, is a fundamental concept.
  • Chapter 2: Chance. This chapter delves into the role of chance and mixed strategies in game theory, where players randomize their choices to keep opponents guessing. It explains that even if players don't consciously randomize, their behavior can be effectively random from an opponent's perspective. The chapter discusses how mixed Nash equilibria arise when players adjust their strategies to make their opponents indifferent between choices, sometimes leading to seemingly paradoxical outcomes like in the Good Samaritan Game or voting scenarios. It also touches upon Von Neumann's minimax theorem, which applies to two-person, zero-sum games and states that players should aim to maximize their minimum possible payoff.
  • Chapter 3: Time. This chapter explores games where the timing of moves is crucial, such as Chess or Poker, which can be represented in extensive form as game trees. It introduces backward induction as a method to solve finite games of perfect information by working backward from the end of the game, determining the best choices at each step. The chapter discusses concepts like subgame-perfect equilibrium, where strategies are optimal not just for the whole game but for every possible subgame, and common knowledge, where all players know something, know that everyone else knows it, and so on. It also touches upon the Chain Store paradox, highlighting complexities when a player's rationality is refuted by an unexpected move.
  • Chapter 4: Conventions. This chapter discusses how conventions, or commonly accepted ways of behaving, help solve equilibrium selection problems in games with multiple Nash equilibria, like the Driving Game. It introduces Schelling's concept of focal points, which are solutions people tend to converge on based on contextual cues, even without explicit agreement. The chapter emphasizes that many societal rules, including language and money, are conventions that evolved because they coordinate behavior on an equilibrium. It also explores how inefficient conventions can arise and persist, as illustrated by Schelling's Solitaire model of segregation, and discusses social dilemmas like the Tragedy of the Commons, where individual incentives conflict with collective well-being.
  • Chapter 5: Reciprocity. This chapter focuses on reciprocity as a key mechanism for sustaining cooperation in repeated interactions. It explains that in indefinitely repeated games, like the Prisoner's Dilemma, cooperative strategies such as GRIM (cooperate until the opponent defects, then defect forever) can form Nash equilibria if players value future payoffs enough. The folk theorem is introduced, suggesting that any mutually beneficial outcome can be supported as an equilibrium in a sufficiently long-term relationship with reliable monitoring and punishment for deviations. The chapter also discusses TIT-FOR-TAT, its successes and limitations, and how emotions like anger can serve as commitment devices to enforce reciprocal behavior.
  • Chapter 6: Information. This chapter deals with games of imperfect information, where players do not fully know what has happened or what others know, using the concept of information sets to model this uncertainty. Poker is presented as the archetypal game of imperfect information, where bluffing and reading opponents are key. The chapter explains Harsanyi's contribution of transforming situations with incomplete information (where players may have different types, preferences, or beliefs) into games of imperfect information by introducing a "typecasting" chance move. It also explores how costly signals can be used by players to credibly convey their type or intentions, as in the Handicap Principle observed in biology.
  • Chapter 7: Auctions. This chapter introduces mechanism design, the process of creating rules and incentives to align agents' behavior with a principal's goals, particularly in situations with information asymmetry. Auctions are highlighted as a successful application, designed to make bidders reveal their true valuations by putting their money where their mouths are. Various auction types are described, including English, Dutch, first-price sealed-bid, and Vickrey auctions, and the chapter explains the revenue equivalence theorem, which states that under certain conditions, these auction types yield the same average revenue for the seller. The chapter also discusses the "winner's curse" in common-value auctions, where the winner may overpay due to overly optimistic estimates.
  • Chapter 8: Evolutionary biology. This chapter applies game theory to evolutionary biology, where fitness (average number of extra children carrying a trait) is analogous to utility, and behavioral traits are strategies. It explains that natural selection can lead to animals behaving as though they are rational players, with replicators (like genes) that confer higher fitness becoming more prevalent. The concept of an Evolutionarily Stable Strategy (ESS) is introduced as a strategy that, if adopted by a population, cannot be invaded by any alternative mutant strategy. The chapter discusses examples like the Hawk-Dove game (and its relation to the Prisoner's Dilemma and Chicken), kin selection (Hamilton's rule explaining cooperation among relatives), and the evolution of cooperation through reciprocal altruism in unrelated individuals.
  • Chapter 9: Bargaining and coalitions. This chapter distinguishes between noncooperative game theory (which explains cooperation from strategic choices) and cooperative game theory (which assumes players can make binding agreements). The Nash program aims to bridge this by modeling bargaining itself as a noncooperative game. It introduces the Nash bargaining solution, which predicts outcomes based on players' risk attitudes and the status quo, and Rubinstein's alternating-offers model, which provides a noncooperative foundation for it, emphasizing the role of patience. The chapter also explores coalition formation, discussing concepts like the core (outcomes no coalition can improve upon for all its members) and the Shapley value (an average of a player's marginal contributions to all possible coalitions).
  • Chapter 10: Puzzles and paradoxes. This chapter addresses common misunderstandings and fallacies in game theory, often arising when intuition clashes with equilibrium arguments. It debunks several fallacies related to the Prisoner's Dilemma, such as the misapplication of Kant's categorical imperative or the "fallacy of the twins" which wrongly assumes players' choices are not independent. The chapter also tackles Newcomb's paradox, showing its apparent contradiction arises from flawed assumptions about the game structure, and clarifies the surprise test paradox by highlighting the importance of correctly defining the game being analyzed. Finally, it discusses the role of common knowledge and its implications for coordination, as seen in the "three old ladies" puzzle and the Email Game.

My Not Very Short Notes

I wanted to really dig into each chapter of this "very short" book, and hopefully come up with some insights that go beyond what's covered in the book - and/or potentially expand

Chapter 1: The name of the game

What is a game?

  • A "game" can refer to any situation where people interact, from courtship to economics to international politics
  • Game theory is concerned with situations where individuals' choices are interdependent, meaning the outcome for each participant depends not only on their own actions but on the actions of others as well
  • Game theory works best when people behave rationally, though it can also explain the behavior of mindless animals or companies eliminated by market forces if they act irrationally.

Essential tools and concepts:

  • Payoffs represent the outcomes for players, which don't necessarily have to be monetary.
  • The theory of revealed preference - basis for understanding player motivation
  • Utility is a way to numerically represent preferences, derived from observing choices rather than making psychological assumptions
  • Von Neumann's method for measuring utility by assessing the risks a person is willing to take
  • Nash equilibrium is where all players make the best reply to others' strategies, meaning no player has an incentive to unilaterally change their strategy.

The 3 key points:

  1. Definition and Scope of Game Theory
  2. Rationality, Utility, and Revealed Preference
  3. Nash Equilibrium as a Central Concept

Mathematical Underpinnings of Nash Equilibrium

"A Nash equilibrium occurs when all the players are simultaneously making a best reply to the strategy choices of the others." Mathematically, this is built on a few components:

1. Players,

2. Strategy sets for each player . A strategy is a complete plan of action for player i, specifying what they will do in every possible situation or contingency that might arise in the game.

(Note: for toy games, these are often small, discrete sets: heads/tails, slower/faster. Strategies can become a very complicated function for complex games.)

3. Strategy profile is a combination of strategies, one for each player.

4. Payoff functions (utility functions): each player has a payoff/utility function

Now we can define Nash equilibrium more formally as a strategy profile that satisfies the following condition for every player and for every strategy available to player i:

In simple terms: No player i can improve their own payoff by unilaterally changing their strategy from si*​ to any other strategy si​, given that all other players stick to their strategies in s*.

Player i's star strategy is a "best reply" to the other players' star strategies

Complexities of Modeling with Game Theory

Game theory (esp. introductory game theory) uses several abstractions and simplifications to model the complexities of the real world:

  • People:
    • Rationality - often assumed to be rational, meaning they consistently choose actions that maximize their own utility, given their beliefs about the game and other players' actions. The term "rational" is about consistency of choice, not about wisdom or lack of emotion.
    • Utility functions - individual preferences, values, risk attitudes, and motivations can be condensed into a utility function. This doesn't require knowing what is in someone's head, it requires observing consistent choices. (Risk aversion captured by response to increasing amounts of money or differing probabilities of outcomes.)
    • Player types - to deal with incomplete information (other players don't know each other's exact payoffs or private information), game theory models players as having different "types". A type encapsulates all of a player's private information (preferences, beliefs about other players' types, etc.). Game starts with chance move that assigns a type to each player. This is a way to bring uncertainty about others into a formal model.
  • All Possible Choices:
    • Set of all possible choices for a player is exactly their strategy set
    • This requires a modeler to carefully define the boundaries and rules of the game.
    • Think of it like, if you had to tell a machine how to play for you while you go to the restroom, what rules would you give it? What about corner cases? (Runaway trading algorithms)
    • Toy games can simplify complex real-world choices into more manageable discrete outcomes and strategies, to make analysis tractable.
    • A strategy is a complete plan of action. (Chess has astronomical number of moves, but concept allows for formal definition.)
  • The universe of information that affects the game
    • Rules - the fundamental structure, including who the players are, what actions they can take, and when they can take them, and what the outcomes are, is assumed to be defined, and often common, knowledge
    • Common knowledge - crucial assumption, often implicit, is that the rules of the game and the rationality of the players is common knowledge. Everyone knows it, everyone knows that everyone knows it, etc. Avoids infinite they think i think they think...
    • Information sets - imperfect information happens when players don't know previous moves of other players (simultaneous-move games, or hidden action). This info is modeled with information sets.
    • An information set groups decision nodes for a player when they cannot distinguish which node they are actually at. A strategy specifies one action per information set, not per node.
    • Example: Matching Pennies
    • Incomplete information and types - Harsanyi's framework converts games of incomplete information (where players are uncertain about some fundamental aspect of the game, like others' payoffs) into games of imperfect information by introducing player types and prior probability distributions over these types.

Matching Pennies

Matching Pennies is a classic, simple game used in game theory to illustrate fundamental concepts of conflict, strategy, and equilibrium.

Basic Setup:

  • The game involves two players, typically named Alice and Bob. Each player has a coin and simultaneously chooses to show either "heads" (H) or "tails" (T).
  • Alice wins if both coins show the same face (both heads or both tails).
  • Bob wins if the coins show different faces (one heads and one tails).
  • Payoffs: The outcomes are directly opposed. If Alice wins, Bob loses, and vice versa. This makes it a game of pure conflict.
  • The book often represents payoffs with icons (thumbs-up for winning, thumbs-down for losing) or with numerical utilities, such as +1 for winning and -1 for losing.
  • If we assign +1 to the winner and -1 to the loser, the payoff table looks like this (Alice's payoff is listed first, then Bob's):
|              | Bob: Heads | Bob: Tails |
| :----------- | :--------- | :--------- |
| Alice: Heads | (+1, -1)   | (-1, +1)   |
| Alice: Tails | (-1, +1)   | (+1, -1)   |

Zero-Sum Game:

  • Because the players' interests are diametrically opposed (one's gain is exactly the other's loss), the sum of their payoffs in any outcome is zero (e.g., +1 + (-1) = 0). This is why it's called a zero-sum game.

Strategies and equilibrium: Pure strategies:

  • Pure strategies (where each player chooses a single action and sticks to it) - each player has two pure strategies: choose Heads or choose Tails.
  • No pure strategy Nash equilibrium - you cannot find a Nash equilibrium in Matching Pennies using only pure strategies
  • Binmore explains by noting that if you circle the best outcomes in the payoff table for each player, no cell will have both payoffs circled for both players.
  • Continuous cycle of best responses, with no stable outcome when both players are simultaneously playing their best reply to the other.

Strategies and equilibrium: Mixed strategies:

  • The resolution to this problem, and the way to find a Nash equilibrium, is through "mixed strategies." A mixed strategy involves players randomizing their choice of pure strategy.
  • In Matching Pennies, the intuitive solution, and indeed the Nash equilibrium, is for each player to choose Heads with 50% probability and Tails with 50% probability, independently and unpredictably.
  • If both players adopt this 50/50 mixed strategy, each player will win, on average, half the time. Given that the opponent is randomizing 50/50, a player cannot improve their own outcome by choosing any other strategy (pure or mixed). For example, if Bob plays Heads 50% of the time and Tails 50% of the time, Alice gets an expected payoff of 0 whether she plays Heads, Tails, or any mix of her own.
  • This randomization keeps the opponent guessing, which is the core of the strategy in such a game.

Role in Illustrating Game Theory Concepts:

  • Conflict vs. Cooperation: It's presented as a game of pure conflict, contrasting with games of pure coordination like the Driving Game (where both players want to coordinate on the same action, e.g., driving on the same side of the road).
  • Minimax Theorem: Von Neumann's minimax theorem, which applies to two-person, zero-sum games, finds its solution in Matching Pennies where players use their maximin strategy (maximizing their minimum guaranteed payoff), which corresponds to the 50/50 randomization.
  • Learning to Play an Equilibrium: The book discusses how boundedly rational players (robots in an example) might learn to play the mixed strategy equilibrium in Matching Pennies over time by adjusting their play based on past frequencies of the opponent's moves. The frequencies of playing heads or tails converge towards the 50/50 equilibrium.
  • Information Sets: When discussing games in extensive form (tree form), Matching Pennies is used to illustrate "information sets." If one player moves first but the second player doesn't know the first player's move, the second player's decision nodes are grouped in an information set, signifying their lack of knowledge. This makes the sequential game strategically equivalent to a simultaneous-move game.
  • Surprise Test Paradox: In a variation, the surprise test paradox is compared to a version of Matching Pennies where a teacher (Alice) chooses a day for a test, and a pupil (Bob) predicts the day. The optimal strategy involves both randomizing.
  • In essence, Matching Pennies is a foundational "toy game" in game theory. Its simplicity allows for a clear illustration of why mixed strategies are necessary, the nature of zero-sum conflict, and how rational (or even evolving) players might approach situations where unpredictability is key to not being exploited.

Matching Pennies - A Few Examples

A few examples given in the book of an analogous Matching Pennies game:

  • Sherlock Holmes and Professor Moriarty: Binmore mentions that Holmes and Moriarty played a version of Matching Pennies on the way to their confrontation at the Reichenbach Falls. Holmes had to decide at which train station to disembark, while Moriarty had to decide at which station to lie in wait.
  • Accountants and Auditors: A real-life counterpart is seen with dishonest accountants deciding when to cheat and their auditors deciding when to inspect the books.
  • Edgar Allan Poe's "The Purloined Letter": Poe describes a boy who consistently wins at Matching Pennies by supposedly intuiting his opponent's thoughts through imitation. Binmore points out the flaw: both players can't successfully use this trick simultaneously.

Why Bother with Toy Games?

In addition to the need for brevity, sometimes game theory gets a math-light treatment or authors skip details because a high level of abstraction is needed to create generalizable models.

Game theory doesn't aim to perfectly replicate every nuance of a specific real-world situation with all its psychological and informational complexities. Instead, it:

  • Identifies key strategic elements.
  • Models these elements formally, often simplifying other aspects.
  • Analyzes the logical consequences of these modeled interactions under assumptions of rationality.

The power of game theory comes from this ability to strip down complex situations to their strategic core. While "toy games" might seem overly simplistic, they illuminate fundamental strategic principles that can then be applied to understand more complex scenarios.

More advanced mathematical game theory does build significantly more complex models, but the foundational ideas of players, strategies, payoffs, and equilibrium concepts remain central.

Chapter 2: Chance

Chapter 1 introduced Matching Pennies, a game where if Alice knew Bob's move (or vice versa), the predictable player would always lose. This highlighted a problem: in such games of pure conflict, there's no stable outcome if players stick to a single, predictable ("pure") strategy.

Chapter 2 delves into the crucial concept of mixed strategies, where players introduce randomness into decision-making to find equilibria (stable solutions) in cases where pure strategies fail to provide one.

Side note on real-world parallels: random strategies in games may look like a roll of the die, but in real life they look like "keeping others guessing" or "throwing everything at the wall and seeing what sticks". In a simple game like Matching Pennies, the optimal random strategy may seem obvious, but in more complex games, it won't be.

Mixed Strategies and Mixed Nash Equilibrium

A key concept of the mixed strategy Nash equilibria function is the principle of maying the other player indifferent. Binmore puts it this way:


A player will only be willing to randomize between two or more pure strategies if they are indifferent between them... Therefore, in a mixed Nash equilibrium, each players' mixed strategy is chosen precisely to make the OTHER player(s) indifferent between the pure strategies they are randomizing over.


To put this in a more rigorous way, consider a game with N players,

Each player i has a finite set of pure strategies

A mixed strategy for player i is a probability distribution over their pure strategies . The set of all mixed strategies for player i is denoted

If is the probability that player i plays strategy , then

(note that each probability is nonzero and all probabilities for a given player add up to 1, )

A mixed strategy profile (which describes each player's mixed strategy) can be defined as

For each player i, their expected payoff/utility function is the weighted average of the payoffs player i would receive from all possible pure strategy profiles, where the weights are the probabilities that each pure strategy profile occurs given the mixed strategies

If denotes the utility for player i when the pure strategy profile s = (s1, s2, ... sN) is played, then

(where S is the profile set of all pure strategy profiles)

Mathematics of Indifference in Mixed Strategy Nash Equilibrium

A mixed strategy profile is a Nash equliibrium if, for every player i and for all possible mixed strategies , the following statement holds true:

(that is, the expected utility for their mixed strategy U_i cannot be made any greater by going with any other mixed strategy)

Now, focusing on the indifference principle:

  • A rational player will only be willing to assign positive probability to multiple pure strategies in a mixed strategy if their expected payoff from playing each pure strategy (against other players' equilibrium strategies ) is the same.
  • Consider the smaller set of strategies, "the Support", that consist only of the pure strategies where the player assigns a positive probability .
  • If the player is playing a mixed strategy, then the two pure strategies being mixed (call them A and B) must have the same utility for the player,
  • Furthermore, if a player is not considering a pure strategy C as part of "the Support", i.e., the player has determined the probability , then we also know that the utility of C must be smaller than the utility of A or B:
  • This means any pure strategy that's actually being played in the mix must give the same expected payoff - and that payoff must be as good as, or better than, any pure strategy that isn't being included in the mix.

Focusing on the indifference principle, but this time making other players indifferent:

  • Consider a two-player game. For a player 1 to be willing to mix strategies A and B (), Player 1 must be indifferent between them. This can be achieved by Player 2 choosing a mixed strategy
  • Specifically, Player 2 chooses probabilities in such that:

  • Symmetrically, Player 1 chooses probabilities in that will make Player 2 indifferent between the pure strategies in "the Support" of

Let's Play Some Shadowrun - Nash Equilibrium Style

Alright, chummer, settle in. Your commlinks are buzzing, but the channels are all over the place. Your teammate, "Glitch," got snatched by the Crimson Katanas, and word on the street is they're holding em somewhere in the old Redmond Barrens, probably some Z-zone residential block they've 'renovated' syndicate-style.

Now, the Johnson wants em back, and so do you. But there's a glitch in your own team's comms – you've got two lead operators here, and their preferred MOs are about as compatible as a Renraku exec and a striking dockworker.

The Players & Their Preferred Ops

  • "Zero" (The Decker): Prefers the subtle approach. Wants to do a "Matrix-First" insertion, blinding the Katanas and creating an opening for the extraction team.
    • Their Plan (Ghost Op): Use local Matrix access points, spoof some credentials, ghost through the building's (likely shoddy) security systems, locate Glitch, disable any internal comms or alarms, and guide an extraction team (or just Glitch herself) out through a quiet back route. Minimal fuss, minimal heat. This is a residential area; going loud could bring down a world of hurt from Lone Star, or worse, awaken something even nastier.
    • Their Payoff: If this works perfectly, it's clean, efficient, and leaves fewer traces. Zero values precision and a low risk of escalating collateral damage. This is their ideal coordinated outcome.
  • "Raze" (The Street Samurai): Chrome-souped and itching for a fight. Prefers the "Shock and Awe" approach.
    • Their Plan (Hard Target Extraction): Roll up in something loud and armored, breach the perimeter with controlled demolitions (or just a well-placed rocket), suppress any opposition with overwhelming firepower, grab Glitch, and exfil before serious reinforcements can arrive. Make a statement: don't frag with this team.
    • Their Payoff: If this works, it's fast, decisive, and sends a message. Raze values direct action and the psychological impact of a bold move. This is their ideal coordinated outcome.


The Dilemma: "The Extraction Execution"

Here's the crux of the extraction dilemma:

  • You're at a temporary safe house, a grimy basement under a noodle shop. Comms are spotty, and you can only reliably get one set of final instructions through to the support elements (like getaway drivers or a drone operator) before you move. Zero and Raze are in different parts of the city, prepping their gear, and they each have to commit to their primary approach before they know what the other has definitively chosen for the point of entry and initial engagement.
  • Both know the mission is to rescue Glitch. They both want the rescue to succeed. If they go in with conflicting plans (e.g., Zero is trying to sneak in while Raze starts blowing walls down), the op is likely to go sideways fast: alarms blare, the Katanas are fully alerted, Glitch might get moved or executed, and the team could be walking into a meatgrinder. That's a mission failure.

Payoffs (Representing Mission Success & Style Preference):

Let's assign some abstract "Success Points" (SP) that combine successful extraction with how well the op aligns with their preferred style:

Both Commit to Ghost Op (Zero's Preference):

  • Zero: 2 SP (Mission success, ideal execution)
  • Raze: 1 SP (Mission success, but not their style – too quiet)

Both Commit to Hard Target Extraction (Raze's Preference):

  • Zero: 1 SP (Mission success, but too loud and risky for their liking)
  • Raze: 2 SP (Mission success, ideal execution)

Conflicting Plans (e.g., Zero goes Ghost, Raze goes Hard Target):

  • Zero: 0 SP (High chance of mission failure, op compromised)
  • Raze: 0 SP (High chance of mission failure, op compromised)
                             | Raze Commits to HARD TARGET | Raze Commits to GHOST OP |
Zero Commits to GHOST OP     | (Z: 0, Raze: 0)	              (Z: 2, Raze: 1)
Zero Commits to HARD TARGET  | (Z: 1, Raze: 2)	              (Z: 0, Raze: 0)
  • They both desperately want to succeed in the overall mission (rescuing Glitch), which means they need to coordinate their approach.
  • However, Zero strongly prefers the Ghost Op if they coordinate, and Raze strongly prefers the Hard Target Extraction if they coordinate.

If they can't get their signals straight before they hit the target location, they risk total mission failure.

  • So, chummers, what's the call? How do Zero-Cool and Raze decide, knowing the other is making their own call at the same time, and any misstep could mean Glitch flatlines? This is where the game theory kicks in – pure strategy equilibria at (Ghost, Ghost) or (Hard Target, Hard Target), or that messy mixed strategy where they might just end up fragging the whole op by trying to do two different things at once.

Applying Game Theory Concepts to the Extraction

Okay, chummer, let's come at this classic coordination problem with conflicting preferences, and try and find a "best" way for Zero and Raze to act, even if they can't communicate. Let's hit the math, but keep it street.

First, let's use p to refer to Zero and q to refer to Raze, and set

  • = probability Zero goes GHOST OP
  • = probability Zero goes HARD TARGET
  • = probability Raze chooses GHOST OP
  • = probability Raze choses HARD TARGET

The Core Idea: Make The Other Chummer Indifferent

For a mixed strategy to be stable (Nash equilibrium), each player must choose their probabilities in such a way that the other player gets the exact same average payoff window from either of their own pure strategies.

Step 1: Figure out Raze's probabilities to make Zero indifferent

Zero will only randomly choose between GHOST and HaRD TARGET if the expected payoff from doing GHOST is the same as their expected payoff from doing HARD TARGET, given whatever Raze is doing.

Zero's expected payoff if Zero decides GHOST:

Expected Payoff = (Raze chooses GHOST) x (Zero's payoff if GHOST,GHOST) + (Raze chooses HARD) x (Zero's payoff if GHOST,HARD)

Mathematically:

And Zero's expected payoff if Zero decides HARD TARGET:

Expected Payoff = (Raze chooses GHOST) x (Zero's payoff if HARD,GHOST) + (Raze chooses HARD) x (Zero's payoff if HARD,HARD)

Mathematically:

For Zero to be indifferent, these two quantities must be equal:

Solving gives

This means Raze should choose GHOST with a probability of 1/3, and HARD TARGET with a probability of 2/3.

Step 2: Figure out Zero's Probabilities (to make Raze indifferent)

Do the same for Raze. Raze will only randomly choose between GHOST and HARD TARGET if their expected payoff from GHOST is the same as the expected payoff from HARD TARGET, given whatever Zero is doing.

Raze's expected payoff if Raze decides GHOST:

Expected Payoff = (Zero chooses GHOST) x (Raze's payoff if GHOST,GHOST) + (Zero chooses HARD) x (Raze's payoff if HARD,GHOST)

Mathematically:

And Raze's expected payoff if Raze decides HARD TARGET:

Expected Payoff = (Zero chooses GHOST) x (Raze's payoff if GHOST,HARD) + (Zero chooses HARD) x (Raze's payoff if HARD,HARD)

Mathematically:

For Raze to be indifferent, these two must be equal:

Which results in:

This means Zero should choose GHOST with a probability of 2/3, and HARD TARGET with a probability of 1/3.

What It Means for the Mission

If you've got a D6 handy, this is basically an assistance test with 1D6:

  • Zero should decide whether to assist Raze and go HARD TARGET (on success, 5 or 6) or leave em hanging and hack it with GHOST OP (on fail, 1 2 3 4)
  • Raze should decide whether to assist Zero and go GHOST OP (on success, 5 or 6) or leave em hanging and go in guns blazing with HARD TARGET (on fail, 1 2 3 4)

(Of course, if both tests "succeed" then both will fail...)

The expected payoff for each player would be:

  • Zero's expected payoff: SP
  • Raze's expected payoff: SP
  • Both expect to get 2/3 Success Points if they play this mixed strategy. This is better than the 0 SP they'd get if they definitely miscoordinated, but worse than the 1 or 2 SP they could get from successful pure strategy coordination.

And the probabilities of each different outcome can be enumerated:

  • (GHOST,GHOST): (2/3)*(1/3) = 2/9 (approx 22.2%)
    • Payoff: Z 2, R 1
  • (HARD,HARD): (1/3)*(2/3) = 2/9 (approx 22.2%)
    • Payoff: Z 1, R 2
  • (Z-GHOST,R-HARD): (2/3)*(2/3) = 4/9 (approx 44.4%)
  • (Z-HARD,R-GHOST): (1/3)*(1/3) = 1/9 (approx 11.1%)
  • Total miscoordination probability: 4/9 + 1/9 = 5/9 (55.6%)

The So What for Gamemaster

If they can't communicate and have to commit independently, this mixed strategy is the only stable way for them to play if they are both rational and expect the other to be rational. It's not a great outcome – there's a high chance (over 50%) they completely drek the run-up and the Katanas are alerted before anything useful happens.

The 2/3 SP expected payoff is pretty grim compared to a guaranteed 1 or 2 SP from successful coordination. This mathematical result starkly shows the value of fixing those comms or having a pre-agreed standard operating procedure (a "convention" in game theory terms) for this kind of situation! Without it, even smart, rational runners are forced into a gamble with pretty lousy odds of perfect success.

So, chummer, tell your players: if they're going in blind on each other's final call, this is what a cold, calculating Sprawl brain would do. It ain't pretty, but it's equilibrium. Now, maybe they'll try to find a way to signal each other after all... or just hope pure luck is on their side.

Mixed Nash Equilibria, the Indifference Principle, and Paradoxical Outcomes

The core idea here is that in many games, stable outcomes or "Nash equilibria" only emerge when players introduce randomness into their choices, known as playing a mixed strategy.

The "indifference principle" is the idea that a player will only be willing to randomize among several pure strategies if they expect to get the same payoff from each of them given the strategy chosen by their opponent(s) (otherwise, they'd go with the pure strategy with the higher payoff!).

Paradoxically, for this to work in equilibrium, each player's mixed strategy must be precisely calibrated to make their opponent indifferent among the choices the opponent is randomizing over. This mutual adjustment of probabilities, designed to create indifference in the other party, is what defines and sustains a mixed Nash equilibrium.

The Good Samaritan Game

The "Good Samaritan Game" provides a striking example of these dynamics leading to a seemingly paradoxical outcome. In this game, a whole population of identical players faces a situation where someone needs help. Everyone in the population gets a positive payoff (say, 10 utils) if someone responds to the cry for help, and zero if nobody helps. However, the act of helping incurs a small personal cost (say, 1 util, so a helper gets 10−1=9 utils if they help and someone is helped).

If you are the only one considering helping, you help because 9 utils is better than 0. If you know for sure someone else will help, you'd prefer not to help to avoid the cost, getting 10 utils. The only way an individual becomes indifferent between helping and not helping is if there's a specific chance that nobody else will help.

This critical probability (in this example, 1/10, making the expected payoff of not helping equal to the payoff of helping if no one else does) must remain constant for the indifference condition to hold, regardless of population size.

This leads to the paradox: as the population gets larger, the probability that any single player offers help must get smaller to maintain that constant 1/10 chance that no one else helps from each individual's perspective. While with two players, each might help with high probability (e.g., 9/10, making the chance both don't help 1/100), with a million players, each individual's probability of helping becomes minuscule.

The overall chance that nobody at all answers the cry for help actually increases and stabilizes at a non-negligible level (around 10% in the example), even though everyone wants help to be given.

This illustrates how individual rationality in a mixed strategy equilibrium can lead to collectively undesirable or surprising outcomes.

Voting Scenarios

Binmore extends this logic to voting scenarios.

He argues that if voters are rational and consider the costs (even minor ones like time) versus the benefits of voting, they might only vote if their vote has a chance of being decisive. In a large election, the probability of any single vote being pivotal is extremely small. If many voters adopt a mixed strategy (randomizing whether to vote or not based on this tiny chance of being decisive), the overall turnout might be lower than ideal. This can lead to situations where a candidate who is not the most preferred by the majority could win if their supporters turn out more consistently or if the opposition's supporters individually (and rationally, from a game theory perspective) decide their chance of impact is too low to bother.

The pundits who decry non-voters as irrational, Binmore suggests, are missing this game-theoretic point: if the system makes an individual vote seem inconsequential, rational abstention based on an indifference calculation becomes a plausible outcome.

The core of Binmore's argument, drawing parallels with the Good Samaritan game, is that a rational individual might choose to vote only if the perceived benefit of their vote outweighs its cost. The "indifference calculation" comes into play when a voter weighs these factors.

The key component for the benefit of voting, in a purely instrumental sense (i.e., wanting your vote to change the outcome), is the probability that your single vote will be decisive, multiplied by the value you place on your preferred candidate winning over another. If this expected benefit is less than the cost of voting, a rational, self-interested individual might abstain. The point of indifference is where this expected benefit roughly equals the cost, potentially leading to a mixed strategy where the individual sometimes votes and sometimes doesn't, or where a certain proportion of the electorate with similar calculations might abstain.

The cost of voting C can vary significantly:

  1. In some systems, voting might be very easy – mail-in ballots sent to everyone, polling places nearby with no queues, same-day registration. Here, C is minimal, perhaps just the few minutes to fill out a form or a short walk. Even with a low cost, if the perceived probability of being decisive (P) is astronomically small, the expected benefit (P×B) can still be less than this trivial C.
  2. In other systems, voting could involve taking an hour or two off work (if not a holiday), traveling some distance to a polling station, waiting in a significant queue, or the effort of researching candidates if one is not already decided. As C increases, the expected benefit (P×B) needed to induce voting also increases.
  3. In some situations or for certain individuals, voting costs can be very high. This might include long travel distances in rural areas, needing to arrange childcare, facing voter suppression tactics (like extremely long lines in specific precincts, restrictive ID laws requiring effort and expense to meet), physical disability making travel difficult, or even risks to personal safety in unstable political environments. When C is very onerous, the probability of being decisive (P) would have to be perceived as quite substantial (or the benefit B incredibly high) to make voting seem rational from this narrow instrumental perspective.

Binmore's point is that even if C is very small, if P is small enough, the product P×B can easily become smaller than C, leading a rational individual to abstain. Pundits who assume everyone should vote often overlook or downplay these costs, or they assume a different primary motivation for voting than influencing the outcome (e.g., civic duty, expressive voting, which are outside this particular rational calculation).

How Size of Voting Population Affects Analysis

The size of the electorate (N) has a dramatic impact on the probability (P) of a single vote being decisive.

  1. Small Elections (e.g., Local Club, Small County/Town Election) - When N is small, the chance that your vote could break a tie or shift the outcome by one vote is relatively higher. For example, if only a few dozen or a few hundred people are voting, P is small but not infinitesimally so. In such cases, P×B might more frequently exceed C, making voting rational for more people.
  2. Medium Elections (e.g., Some City or Congressional District Elections) - As N grows to thousands or tens of thousands, P drops significantly. The number of plausible scenarios where one vote matters becomes much smaller.
  3. Large Elections (e.g., State-wide, National Presidential Elections) - When N is in the millions, the probability (P) of a single vote being the deciding factor becomes vanishingly small.

(Binmore directly addresses the case of large elections and P becoming vanishingly small in Chapter 10 with "The myth of the wasted vote".)

He provides hypothetical calculations: "With one million voters of whom 5% are undecided, Alice’s vote would count only once in every 8,000 years, even if the same freakish circumstances were repeated every four years." And in even more typical scenarios, "Alice’s vote would count only once in every 20 billion billion years."

Binmore argues that in such large electorates, the logic from the Good Samaritan game applies: "As in the Good Samaritan Game, adding more voters makes things worse for the individual incentive to act based on decisiveness."

Von Neumann's Minimax Theorem

John Von Neumann's minimax theorem is a foundational result in game theory, but it's important to understand that it applies specifically to a particular class of games: two-person, zero-sum games. In these games, there are only two players, and their interests are diametrically opposed – whatever one player gains, the other player loses by an equivalent amount. The sum of their payoffs is always zero (or a constant, which can be normalized to zero). Matching Pennies is a prime example Binmore uses. Von Neumann believed the purpose of studying a game was to identify an unambiguous rational solution, and these games provided such a case.

The minimax theorem, in essence, states that every finite two-person, zero-sum game has a "value," which is the average payoff the first player (Player 1) can guarantee themselves if they play optimally, and which Player 2 cannot prevent Player 1 from achieving (and vice-versa, Player 2 can guarantee they won't lose more than this value). Moreover, there exist optimal strategies (which may be mixed strategies) for both players that allow them to achieve this value. When players use these optimal strategies, the outcome is a Nash equilibrium.

The way players identify these optimal strategies in a two-person, zero-sum game is by applying the maximin principle. To "maximize the minimum possible payoff" means that a player (say, Alice) considers each of her available strategies (pure or mixed). For each strategy, she calculates the worst possible average outcome (her minimum payoff) that she could receive if her opponent (Bob) knew her strategy and played his best counter-strategy to minimize her payoff. After evaluating all her strategies in this pessimistic light, Alice then chooses the strategy that yields the largest of these minimum payoffs. This chosen strategy is her maximin strategy, and the associated payoff is her maximin value.

This approach is rational in a two-person, zero-sum game because, as Binmore puts it, "if Alice is playing Bob in a zero-sum game, he is the relevant universe and so the universe is indeed her personal enemy in this special case." Bob is trying to do as well as possible, which in a zero-sum game is equivalent to trying to make Alice's payoff as low as possible. By choosing her maximin strategy, Alice guarantees herself a certain payoff level, regardless of what Bob does (assuming Bob is also rational and trying to maximize his own payoff). Bob, by playing his own maximin strategy (which is equivalent to a "minimax strategy" from his perspective – minimizing the maximum Alice can get), ensures he doesn't lose more than this value. The minimax theorem shows that Alice's maximin payoff and Bob's maximin payoff sum to zero (or, Alice's maximin equals her minimax value). Therefore, neither player can improve upon their maximin payoff if the other plays rationally; it's the best they can guarantee in the face of a perfectly rational, adversarial opponent.


The Goal of Randomizing Strategies

"Even if players don't consciously randomize, their behavior can be effectively random from an opponent's perspective."

This statement bridges the abstract concept of mixed strategies with how we observe behavior in the real world. When Binmore, in Chapter 2, suggests that "even if players don't consciously randomize, their behavior can be effectively random from an opponent's perspective," he's highlighting a crucial aspect of how game theory interprets strategic interaction.

What is the goal of randomization? In many games, particularly those with a strong element of conflict where being predictable is a disadvantage (like Matching Pennies, or Rock-Paper-Scissors), the strategic advantage of a mixed strategy comes from its unpredictability. If your opponent can guess your move, they can exploit it. Therefore, the aim is to choose your actions in such a way that your opponent cannot find a pattern and hence cannot systematically counter you.

Sometimes randomness is conscious - for example, if someone literally makes their decision by flipping a coin or rolling a die. This is used to decide what pure strategy to play.

Sometimes randomness is more complex - players may have a complex decision making process, or be influenced by subtle factors (gut feeling, intuition, a "sign from the universe") or deliberate attempts to vary their behavior. If the process is sufficiently complex or opaque to the opponent, it may appear random - and therefore effectively be rrandom.

(Even if a company's internal method for setting prices seems, and likely is, deterministic, to an outsider it is complex enough and changes often enough that it is effectively random.)

In essence, game theory's concept of mixed strategies focuses on the informational state of the opponent. If your opponent cannot predict your next move any better than by assigning probabilities to your possible actions, then your behavior is "effectively random" from their strategic standpoint, regardless of whether you achieved that unpredictability through conscious randomization or through a complex, opaque, but ultimately deterministic process designed to "keep them guessing."

Retrieved from "https://charlesreid1.com/w/index.php?title=Game_Theory_-_A_Very_Short_Introduction&oldid=30136"