Hubbry Logo
Best responseBest responseMain
Open search
Best response
Community hub
Best response
logo
7 pages, 0 posts
0 subscribers
Be the first to start a discussion here.
Be the first to start a discussion here.
Best response
Best response
Best response
View on Wikipedia
from Wikipedia

In game theory, the best response is the strategy (or strategies) which produces the most favorable outcome for a player, taking other players' strategies as given.[1] The concept of a best response is central to John Nash's best-known contribution, the Nash equilibrium, the point at which each player in a game has selected the best response (or one of the best responses) to the other players' strategies.[2]

Correspondence

[edit]
Figure 1. Reaction correspondence for player Y in the Stag Hunt game.

Reaction correspondences, also known as best response correspondences, are used in the proof of the existence of mixed strategy Nash equilibria.[3][4] Reaction correspondences are not "reaction functions" since functions must only have one value per argument, and many reaction correspondences will be undefined, i.e., a vertical line, for some opponent strategy choice. One constructs a correspondence b(·), for each player from the set of opponent strategy profiles into the set of the player's strategies. So, for any given set of opponent's strategies σ−i, bi(σ−i) represents player i's best responses to σ−i.

Figure 2. Reaction correspondence for player X in the Stag Hunt game.

Response correspondences for all 2 × 2 normal form games can be drawn with a line for each player in a unit square strategy space. Figures 1 to 3 graphs the best response correspondences for the stag hunt game. The dotted line in Figure 1 shows the optimal probability that player Y plays 'Stag' (in the y-axis), as a function of the probability that player X plays Stag (shown in the x-axis). In Figure 2 the dotted line shows the optimal probability that player X plays 'Stag' (shown in the x-axis), as a function of the probability that player Y plays Stag (shown in the y-axis). Note that Figure 2 plots the independent and response variables in the opposite axes to those normally used, so that it may be superimposed onto the previous graph, to show the Nash equilibria at the points where the two player's best responses agree in Figure 3.

There are three distinctive reaction correspondence shapes, one for each of the three types of symmetric 2 × 2 games: coordination games, discoordination games, and games with dominated strategies (the trivial fourth case in which payoffs are always equal for both moves is not really a game theoretical problem). Any payoff symmetric 2 × 2 game will take one of these three forms.

Coordination games

[edit]
Figure 3. Reaction correspondence for both players in the Stag Hunt game. Nash equilibria shown with points, where the two player's correspondences agree, i.e. cross

Games in which players score highest when both players choose the same strategy, such as the stag hunt and battle of the sexes, are called coordination games. These games have reaction correspondences of the same shape as Figure 3, where there is one Nash equilibrium in the bottom left corner, another in the top right, and a mixing Nash somewhere along the diagonal between the other two.

Anti-coordination games

[edit]
Figure 4. Reaction correspondence for both players in the hawk-dove game. Nash equilibria shown with points, where the two player's correspondences agree, i.e. cross

Games such as the game of chicken and hawk-dove game in which players score highest when they choose opposite strategies, i.e., discoordinate, are called anti-coordination games. They have reaction correspondences (Figure 4) that cross in the opposite direction to coordination games, with three Nash equilibria, one in each of the top left and bottom right corners, where one player chooses one strategy, the other player chooses the opposite strategy. The third Nash equilibrium is a mixed strategy which lies along the diagonal from the bottom left to top right corners. If the players do not know which one of them is which, then the mixed Nash is an evolutionarily stable strategy (ESS), as play is confined to the bottom left to top right diagonal line. Otherwise an uncorrelated asymmetry is said to exist, and the corner Nash equilibria are ESSes.

Games with dominated strategies

[edit]
Figure 5. Reaction correspondence for a game with a dominated strategy.

Games with dominated strategies have reaction correspondences which only cross at one point, which will be in either the bottom left, or top right corner in payoff symmetric 2 × 2 games. For instance, in the single-play prisoner's dilemma, the "Cooperate" move is not optimal for any probability of opponent Cooperation. Figure 5 shows the reaction correspondence for such a game, where the dimensions are "Probability play Cooperate", the Nash equilibrium is in the lower left corner where neither player plays Cooperate. If the dimensions were defined as "Probability play Defect", then both players best response curves would be 1 for all opponent strategy probabilities and the reaction correspondences would cross (and form a Nash equilibrium) at the top right corner.

Other (payoff asymmetric) games

[edit]

A wider range of reaction correspondences shapes is possible in 2 × 2 games with payoff asymmetries. For each player there are five possible best response shapes, shown in Figure 6. From left to right these are: dominated strategy (always play 2), dominated strategy (always play 1), rising (play strategy 2 if probability that the other player plays 2 is above threshold), falling (play strategy 1 if probability that the other player plays 2 is above threshold), and indifferent (both strategies play equally well under all conditions).

Figure 6 - The five possible reaction correspondences for a player in a 2 × 2 game. The axes are assumed to show the probability that the player plays their strategy 1. From left to right: A) Always play 2, strategy 1 is dominated, B) Always play 1, strategy 2 is dominated, C) Strategy 1 best when opponent plays his strategy 1 and 2 best when opponent plays his 2, D) Strategy 1 best when opponent plays his strategy 2 and 2 best when opponent plays his 1, E) Both strategies play equally well no matter what the opponent plays.

While there are only four possible types of payoff symmetric 2 × 2 games (of which one is trivial), the five different best response curves per player allow for a larger number of payoff asymmetric game types. Many of these are not truly different from each other. The dimensions may be redefined (exchange names of strategies 1 and 2) to produce symmetrical games which are logically identical.

Matching pennies

[edit]

One well-known game with payoff asymmetries is the matching pennies game. In this game one player, the row player (graphed on the y dimension) wins if the players coordinate (both choose heads or both choose tails) while the other player, the column player (shown in the x-axis) wins if the players discoordinate. Player Y's reaction correspondence is that of a coordination game, while that of player X is a discoordination game. The only Nash equilibrium is the combination of mixed strategies where both players independently choose heads and tails with probability 0.5 each.

Figure 7. Reaction correspondences for players in the matching pennies game. The leftmost mapping is for the coordinating player, the middle shows the mapping for the discoordinating player. The sole Nash equilibrium is shown in the right hand graph.

Dynamics

[edit]

In evolutionary game theory, best response dynamics represents a class of strategy updating rules, where players strategies in the next round are determined by their best responses to some subset of the population. Some examples include:

  • In a large population model, players choose their next action probabilistically based on which strategies are best responses to the population as a whole.
  • In a spatial model, players choose (in the next round) the action that is the best response to all of their neighbors.[5]

Importantly, in these models players only choose the best response on the next round that would give them the highest payoff on the next round. Players do not consider the effect that choosing a strategy on the next round would have on future play in the game. This constraint results in the dynamical rule often being called myopic best response.

In the theory of potential games, best response dynamics refers to a way of finding a Nash equilibrium by computing the best response for every player:

Theorem—In any finite potential game, best response dynamics always converge to a Nash equilibrium.[6]

Smoothed

[edit]
Figure 8. A BR correspondence (black) and smoothed BR functions (colors)

Instead of best response correspondences, some models use smoothed best response functions. These functions are similar to the best response correspondence, except that the function does not "jump" from one pure strategy to another. The difference is illustrated in Figure 8, where black represents the best response correspondence and the other colors each represent different smoothed best response functions. In standard best response correspondences, even the slightest benefit to one action will result in the individual playing that action with probability 1. In smoothed best response as the difference between two actions decreases the individual's play approaches 50:50.

There are many functions that represent smoothed best response functions. The functions illustrated here are several variations on the following function:

where E(x) represents the expected payoff of action x, and γ is a parameter that determines the degree to which the function deviates from the true best response (a larger γ implies that the player is more likely to make 'mistakes').

There are several advantages to using smoothed best response, both theoretical and empirical. First, it is consistent with psychological experiments; when individuals are roughly indifferent between two actions they appear to choose more or less at random. Second, the play of individuals is uniquely determined in all cases, since it is a correspondence that is also a function. Finally, using smoothed best response with some learning rules (as in Fictitious play) can result in players learning to play mixed strategy Nash equilibria.[7]

See also

[edit]

References

[edit]
Revisions and contributorsEdit on WikipediaRead on Wikipedia

Best response

View on Grokipedia
from Grokipedia
In , particularly in the context of non-cooperative games, a best response refers to a selected by a player that maximizes their expected payoff, given the strategies chosen by all other players. Formally, for a player ii with strategy set SiS_i and payoff function uiu_i, a σi∈Si\sigma_i \in S_i is a best response to the strategy profile σ−i\sigma_{-i} of the other players if ui(σi,σ−i)≥ui(si′,σ−i)u_i(\sigma_i, \sigma_{-i}) \geq u_i(s_i', \sigma_{-i}) for all alternative strategies si′∈Sis_i' \in S_i. This concept assumes that players act rationally, anticipating the actions of others to optimize their own outcomes. The notion of best response is foundational to analyzing strategic interactions, serving as a building block for more advanced solution concepts such as . In a Nash equilibrium, every player's strategy is a mutual best response to the strategies of the others, ensuring no unilateral deviation can improve a player's payoff. Introduced implicitly in John Nash's 1951 paper on non-cooperative games, the best response framework extends beyond pure strategies to mixed strategies, where players randomize over actions to achieve equilibrium in games without dominant strategies. This allows for the study of stability in diverse scenarios, from economic markets to . Best response dynamics, a process where players iteratively adjust strategies to best reply to current opponents' choices, further illustrate the concept's practical role in converging toward equilibria, though convergence is not guaranteed in all games. The idea underpins broader applications in fields like auction design, bargaining, and algorithmic game theory, where computing best responses aids in predicting outcomes under incomplete information. Despite its centrality, challenges arise in complex games with large strategy spaces, often requiring computational methods to identify best responses efficiently.

Fundamentals

Definition

In game theory, a best response is a strategy selected by a player that maximizes their expected payoff given the strategies chosen by the other players in the game. This concept is central to analyzing strategic interactions in normal-form games, where players simultaneously choose actions without knowledge of others' choices. Formally, in an nn-player normal-form game with strategy sets SiS_i for each player ii and payoff function ui:S→Ru_i: S \to \mathbb{R}, a pure strategy si∗∈Sis_i^* \in S_i is a best response to the strategy profile s−i=(sj)j≠is_{-i} = (s_j)_{j \neq i} of the other players if it satisfies si∗∈arg⁡max⁡si′∈Siui(si′,s−i).s_i^* \in \arg\max_{s_i' \in S_i} u_i(s_i', s_{-i}). That is, ui(si∗,s−i)≥ui(si′,s−i)u_i(s_i^*, s_{-i}) \geq u_i(s_i', s_{-i}) for all si′∈Sis_i' \in S_i. For mixed strategies, where each player ii randomizes over their pure strategies according to a probability distribution σi:Si→[0,1]\sigma_i: S_i \to [0,1] with ∑si∈Siσi(si)=1\sum_{s_i \in S_i} \sigma_i(s_i) = 1, a mixed strategy σi∗\sigma_i^* is a best response to σ−i\sigma_{-i} if σi∗∈arg⁡max⁡σiui(σi,σ−i),\sigma_i^* \in \arg\max_{\sigma_i} u_i(\sigma_i, \sigma_{-i}), where the expected payoff is given by ui(σi,σ−i)=∑si∈Siσi(si)∑s−i∈S−iui(si,s−i)∏j≠iσj(sj).u_i(\sigma_i, \sigma_{-i}) = \sum_{s_i \in S_i} \sigma_i(s_i) \sum_{s_{-i} \in S_{-i}} u_i(s_i, s_{-i}) \prod_{j \neq i} \sigma_j(s_j). In normal-form games, best responses are often illustrated using payoff matrices for finite two-player games. Consider a generic two-player game where Player 1 chooses rows (strategies A or B) and Player 2 chooses columns (strategies X or Y), with payoffs (u1,u2)(u_1, u_2) as follows:
XY
A(3, 2)(1, 4)
B(4, 1)(2, 3)
If Player 2 plays X, Player 1's best response is B (payoff 4 > 3); if Player 2 plays Y, Player 1's best response is B (payoff 2 > 1). Similarly, Player 2's best response to A is Y (4 > 2), and to B is Y (3 > 1). The concept of best response was introduced by in his 1928 paper on the for zero-sum games, where optimal strategies maximize minimum payoffs against adversaries. It was further developed by John Nash in 1951, who used it to define equilibrium points in non-cooperative games as strategy profiles where each player's strategy is a mutual best response to the others.

Properties and Relation to Equilibria

The best response correspondence BRi(s−i)BR_i(s_{-i}), which maps opponents' strategies to the set of optimal strategies for player ii, exhibits key mathematical properties that underpin equilibrium analysis in game theory. Under the assumption that player ii's payoff function is continuous and quasi-concave in their own strategy, the best response correspondence is nonempty, convex-valued, and upper hemicontinuous. These properties ensure that the joint best response correspondence over all players maps the compact, convex strategy space into itself in a manner suitable for fixed-point theorems. Specifically, in games with compact convex strategy sets and continuous quasi-concave payoffs, Kakutani's guarantees the existence of at least one mixed strategy , as the best response correspondence satisfies the theorem's conditions of upper hemicontinuity and convex values. Uniqueness of the best response for a given profile of opponents' holds when the payoff function is strictly quasi-concave in the player's own , implying a single optimal response rather than a set. This strictness eliminates flat portions in the payoff landscape, ensuring the argmax is a singleton. In contrast, quasi-concavity alone suffices for existence and convexity but permits multiple best responses, leading to a correspondence with positive dimension. A strategy profile s∗=(si∗,s−i∗)s^* = (s_i^*, s_{-i}^*) constitutes a Nash equilibrium if and only if each player's strategy is a best response to the others', formalized as si∗∈BRi(s−i∗)s_i^* \in BR_i(s_{-i}^*) for all players ii. This fixed-point characterization highlights that Nash equilibria are precisely the intersection points of the best response correspondences across players. When multiple best responses exist for some players—due to payoff indifference—games can admit sets of equilibria, including pure strategy ones (where all players play deterministic strategies) and mixed strategy ones (involving randomization). Such multiplicity arises in non-strictly concave settings and motivates refinements like trembling-hand perfect equilibria, which select robust outcomes as limits of approximate equilibria under small perturbations to strategies, ensuring stability against minor errors in play.

Best Response Correspondences

In Coordination Games

Coordination games are a class of strategic interactions in which players receive higher payoffs when their actions align, creating incentives for mutual strategy selection to achieve preferred outcomes. These games typically feature multiple equilibria, where each player's strategy is a best response to the others', reflecting the mutual reinforcement of coordinated choices. A canonical example is the game, in which two hunters decide whether to pursue a stag (requiring ) or a (pursuable independently). The payoff structure incentivizes matching: mutual stag yields (2, 2), mutual hare (1, 1), stag against hare (0, 1), and hare against stag (1, 0). In this setup, a player's best response is to hunt stag if the opponent's probability of choosing stag exceeds 0.5, hare otherwise, and any mixture at exactly 0.5. When visualized in the mixed strategy space [0,1]2[0,1]^2, where each axis represents a player's probability of selecting stag, the best response correspondences form L-shaped boundaries: for player 1, a horizontal line at probability 0 up to the opponent's 0.5, then a vertical line at 1 beyond 0.5, symmetric for player 2. These boundaries converge to the pure equilibria at (0,0) (all hare) and (1,1) (all stag), intersecting at the mixed equilibrium (0.5, 0.5). The exhibits two pure equilibria—all players choosing stag or all choosing —and one mixed where each plays stag with probability 0.5. Among these, the all-stag equilibrium is payoff dominant due to its higher joint payoffs, while the all-hare may be risk dominant if the payoff advantage of stag is sufficiently small, as dominance prioritizes equilibria resilient to perturbations in beliefs about opponents' play. Another illustrative coordination game is the Battle of the Sexes, where two players prefer different joint activities but value coordination over mismatch. With payoffs structured as (2, 1) mutually, (1, 2) mutually, and (0, 0) for mismatches, the best response for the player preferring opera is to choose it if the opponent's probability exceeds 1/3, ballet otherwise; symmetrically, the other player's threshold is 2/3 for ballet. This asymmetry leads to best responses that favor joint play, yielding two pure equilibria (mutual opera, mutual ballet) and one mixed equilibrium where probabilities are 2/3 and 1/3 for preferred actions, respectively.
Player 1 \ Player 2
(2, 1)(0, 0)
(0, 0)(1, 2)

In Anti-Coordination Games

Anti-coordination games constitute a class of symmetric two-player strategic interactions in which players receive higher payoffs when they select differing actions, incentivizing strategic divergence rather than alignment. A foundational example is the -Dove game, originally formulated to model animal conflicts over resources, where "Hawk" represents an aggressive strategy and "Dove" a passive one. In this setup, the payoff matrix yields positive returns for mismatched play: a confronting a Dove secures the full resource value V>0V > 0, while a Dove yields to a without cost; mutual Doves share V/2V/2 each; but mutual engage in costly conflict, netting (V−C)/2(V - C)/2 where C>VC > V is the injury cost. The best response correspondence in anti-coordination games reflects this mismatch incentive, mapping an opponent's mixed strategy to the player's optimal counter-strategy. For the Hawk-Dove game, if the opponent plays with probability pp, the expected payoff to playing is p⋅V−C2+(1−p)⋅Vp \cdot \frac{V - C}{2} + (1 - p) \cdot V, while playing Dove yields p⋅0+(1−p)⋅V2p \cdot 0 + (1 - p) \cdot \frac{V}{2}. The best response switches from pure (when p<V/Cp < V/C) to pure Dove (when p>V/Cp > V/C), forming a decreasing . Visualized in the unit square of mixed strategies (with axes for each player's Hawk probability), these correspondences appear as inverse L-shaped boundaries delineating regions of dominance, intersecting along the diagonal at the symmetric mixed equilibrium where p=V/Cp = V/C. Equilibria in anti-coordination games include two pure-strategy asymmetric Nash equilibria—(Hawk, Dove) and (Dove, Hawk)—where no player benefits from unilateral deviation, alongside a unique symmetric mixed-strategy Nash equilibrium at the intersection of best responses. In the Hawk-Dove game, this mixed equilibrium has each player adopting Hawk with probability V/C<1/2V/C < 1/2, ensuring indifference between strategies. From an evolutionary perspective, the mixed strategy qualifies as an evolutionarily stable strategy (ESS), as a population converging to it resists invasion by mutant pure strategies, provided the cost CC exceeds the benefit VV; pure equilibria, by contrast, are unstable to perturbations favoring the opposite strategy. A illustrative variant is the Chicken game, akin to Hawk-Dove but framed in human brinkmanship scenarios like mutually assured destruction in diplomacy. Here, "Straight" (aggressive, Hawk-like) against "Swerve" (yielding, Dove-like) rewards the aggressor with high prestige while the yielder avoids catastrophe; mutual Straight results in mutual loss, and mutual Swerve yields modest coordination. Best responses emphasize de-escalation to perceived aggression—Swerve against Straight—but risk exploitation if both hesitate, highlighting how anti-coordination structures amplify tension in high-stakes mismatched incentives.

In Games with Dominated Strategies

In games with dominated strategies, the analysis of best responses is streamlined because suboptimal strategies are systematically excluded, leading to predictable player behavior and unique outcomes. A strategy sis_i for player ii is strictly dominated by another strategy si′s_i' if, for every possible strategy profile s−is_{-i} of the opponents, the payoff to player ii from si′s_i' exceeds that from sis_i. Consequently, a strictly dominated strategy cannot constitute a best response to any conceivable beliefs about opponents' actions, as the dominating strategy always yields a superior payoff. This property facilitates iterative elimination of dominated strategies, a process that refines the strategy space until only rationalizable strategies remain, where best responses are confined to the surviving options. In such iterations, the best response at each step invariably selects the dominant strategy, progressively narrowing choices and often culminating in a singleton set of rationalizable strategies for each player. For instance, in the Prisoner's Dilemma, "Defect" strictly dominates "Cooperate" for both players, as defection provides a higher payoff irrespective of the opponent's decision to cooperate or defect. The best response correspondence in these games graphically manifests as a collapse to a single point or a horizontal line, indicating that the optimal response remains fixed at the dominant strategy across the full range of opponents' possible plays, effectively pruning all dominated alternatives from the feasible set. This reduction ensures that games solvable through iterated dominance possess a unique pure-strategy Nash equilibrium, exemplified by the (Defect, Defect) outcome in the Prisoner's Dilemma, where mutual defection is the only intersection of best responses.

In Asymmetric Games

In payoff-asymmetric games, players receive different payoffs for the same strategy profile, resulting in best response correspondences that lack the symmetry found in payoff-symmetric games, where one player's best response to a strategy mirrors the other's. This asymmetry arises because each player's utility maximization depends on their unique payoff structure, leading to non-identical reaction functions even when strategies are comparable. For instance, in games like the Battle of the Sexes, one player may prefer one coordination outcome while the other prefers a different one, causing best responses to favor distinct pure strategies depending on the opponent's choice. The shapes of best response correspondences in these games can vary significantly, including straight lines (as in linear demand Cournot duopolies with differing costs), kinked functions (as in Stackelberg leader-follower models where the follower's response shifts at boundary points), and S-curves (as in smoothed or quantal response approximations to discontinuous reactions). Other possible shapes encompass downward-sloping lines (reflecting strategic substitutes) and upward-sloping lines (indicating strategic complements), yielding up to five distinct forms that influence the number and location of equilibria; for example, intersecting kinked or S-shaped responses can produce multiple Nash equilibria, while straight lines often yield unique intersections. These diverse shapes highlight how payoff differences prevent the mirroring of best responses, complicating equilibrium selection compared to symmetric cases. A representative example is the generalized matching pennies game with unequal gains, where the row player receives X >1 when both select action 1 (e.g., heads for row, heads for column), and 0 otherwise, while the column player receives 1 when actions differ, and 0 when they match with row action 2. In this setup, the best responses are step functions: the row player (high payoff) chooses action 1 if the column player's probability of action 2 is less than X/(X+1) (>0.5 for X>1); the column player (low payoff) chooses action 1 if the row player's probability of action 1 is less than 0.5. The mixed has the row player mixing 50-50 on actions, and the column player selecting action 2 with probability X/(X+1) >0.5 (action 1 with 1/(1+X) <0.5). This reflects the column player's incentive to avoid the row's higher-stakes outcome more cautiously. Experimental data confirm deviations from this equilibrium due to own-payoff effects, with the row player (high X) observed to select action 1 more frequently than 0.5, e.g., around 0.60 for X=9, unlike the symmetric case (X=1) where both play 0.5. Asymmetry impacts stability by ensuring best responses do not symmetrically oppose or complement each other, potentially creating multiple intersection points that are asymptotically stable under best response dynamics in some directions but unstable in others, unlike the unique cycling in symmetric zero-sum games like standard matching pennies. This non-mirroring property often results in equilibria where one player's strategy exerts greater influence, altering the robustness of outcomes to perturbations.

In Matching Pennies

The Matching Pennies game is a canonical example of a two-player zero-sum game in noncooperative game theory, where each player simultaneously selects either Heads or Tails. If the choices match, Player 1 receives a payoff of +1 and Player 2 receives -1; if they mismatch, Player 1 receives -1 and Player 2 receives +1. The payoff matrix for Player 1 (with Player 2's payoffs as the negative) is as follows:
Player 1 \ Player 2HeadsTails
Heads+1-1
Tails-1+1
In pure strategies, Player 1's best response is to match Player 2's choice, while Player 2's best response is to mismatch it, resulting in no pure strategy Nash equilibrium. For instance, if Player 2 chooses Heads, Player 1's best response is Heads, but then Player 2 would prefer Tails, leading to endless cycling. In mixed strategies, let σ1\sigma_1 denote Player 1's probability of choosing Heads and σ2\sigma_2 Player 2's probability of Heads. Player 1's best response to σ2\sigma_2 is σ1=1\sigma_1 = 1 if σ2>1/2\sigma_2 > 1/2 (play Heads purely), σ1=0\sigma_1 = 0 if σ2<1/2\sigma_2 < 1/2 (play Tails purely), and any σ1∈[0,1]\sigma_1 \in [0,1] if σ2=1/2\sigma_2 = 1/2 (indifferent). Symmetrically, Player 2's best response to σ1\sigma_1 is σ2=1\sigma_2 = 1 if σ1<1/2\sigma_1 < 1/2, σ2=0\sigma_2 = 0 if σ1>1/2\sigma_1 > 1/2, and any σ2∈[0,1]\sigma_2 \in [0,1] if σ1=1/2\sigma_1 = 1/2. The uniform mixed strategy (σ1,σ2)=(1/2,1/2)(\sigma_1, \sigma_2) = (1/2, 1/2) is mutually best responding, as each player is indifferent between pure strategies and achieves an expected payoff of zero. The best response correspondences form step functions in the unit square: Player 1's rises sharply from 0 to 1 at σ2=1/2\sigma_2 = 1/2, while Player 2's falls from 1 to 0 at σ1=1/2\sigma_1 = 1/2, intersecting only at (1/2,1/2)(1/2, 1/2). This unique mixed has no pure counterparts and aligns with the value of the game under von Neumann's , where each player's guarantees a payoff of zero against optimal play.

Best Response Dynamics

Formulation

Best response dynamics describe the of strategies in repeated or evolutionary game-theoretic settings, where players or populations update their strategies by selecting myopic best responses to the current strategies of others. In these dynamics, agents focus solely on maximizing immediate payoffs against the prevailing strategy profile, without anticipating or accounting for future adjustments by opponents. In continuous-time formulations, the dynamics for a player's xix_i in a are given by the differential inclusion x˙i∈BRi(x−i)−xi,\dot{x}_i \in BR_i(x_{-i}) - x_i, where BRi(x−i)BR_i(x_{-i}) denotes the set of best responses for player ii to the strategies x−ix_{-i} of others, and the dot represents the time derivative. This setup models the instantaneous adjustment toward the best response, often resulting in a discontinuous due to the set-valued nature of BRiBR_i. In population games, the aggregate dynamics extend this to the population state xx, yielding x˙∈M(F(x))−x,\dot{x} \in M(F(x)) - x, where F(x)F(x) is the payoff vector to strategies, and M(F(x))M(F(x)) is the set of payoff-maximizing strategy distributions. Here, the fraction of the population adopting each shifts toward those offering the highest fitness against the average population behavior, reflecting an evolutionary process where higher-payoff strategies proliferate. Discrete-time versions, such as those derived from fictitious play, approximate these updates iteratively in finite strategy spaces. In a multi-player , the process proceeds as follows ( for synchronous updates):

Initialize strategy profile x^0 for all players For t = 1, 2, ..., T: For each player i: x_i^t = argmax_{s_i} u_i(s_i, x_{-i}^{t-1}) // x^t is the profile at time t

Initialize strategy profile x^0 for all players For t = 1, 2, ..., T: For each player i: x_i^t = argmax_{s_i} u_i(s_i, x_{-i}^{t-1}) // x^t is the profile at time t

This iterative best response update assumes players revise strategies in sequence or simultaneously based on the prior round's profile, leading to a through the strategy space. Smoothed variants, such as dynamics, regularize the discontinuous best response to ensure smoother .

Convergence and Stability

In potential games, best response dynamics are guaranteed to converge to a Nash equilibrium from any starting strategy profile, as the potential function serves as a strict that decreases with each best response update until an equilibrium is reached. This convergence holds in finite time for finite strategy sets, making potential games a key class where the dynamics exhibit global stability. Global asymptotic stability of Nash equilibria under best response dynamics is established in stable games, where self-defeating externalities ensure that the dynamics converge to the set of equilibria from any , with Lyapunov functions confirming asymptotic stability. In contrast, local stability, such as around asymptotically stable equilibria, applies more narrowly to isolated equilibria in these games, where perturbations remain bounded and the system returns to the equilibrium. However, in non-potential games like Rock-Paper-Scissors, the dynamics can exhibit perpetual cycles, as each player's best response to the opponent's strategy leads to a loop (e.g., rock beaten by paper, paper by scissors, scissors by rock), preventing convergence to equilibrium. Convergence in finite steps is also assured in supermodular games due to strategic complementarities, where the best response correspondence is increasing, allowing iterative updates to monotonically approach the unique or maximal . Similarly, when the best response mapping is a contraction in an appropriate metric, such as in certain continuous-time formulations or games with contracting payoff structures, the dynamics converge globally to equilibrium via the . Despite these results, best response dynamics may cycle indefinitely or diverge in general finite games without such structure, as demonstrated in Rock-Paper-Scissors where laboratory experiments confirm oscillatory behavior and failure to settle, with empirical frequencies tracing cycles rather than equilibria. Agent-based simulations across random normal-form games further reveal that nonconvergence due to cycles occurs in a significant fraction of cases, highlighting the limitations outside restricted classes like potential or supermodular games.

Smoothed Best Response

Mathematical Formulation

The smoothed best response, also known as the quantal response function, addresses the discontinuities in the pure best response by incorporating stochastic elements that assign positive probabilities to all actions, weighted by their expected utilities. A prominent formulation is the quantal response, where for player ii facing opponents' strategies s−is_{-i}, the probability of choosing action a∈Aia \in A_i is given by BRiλ(s−i)(a)=exp⁡(λui(a,s−i))∑a′∈Aiexp⁡(λui(a′,s−i)),\text{BR}^\lambda_i(s_{-i})(a) = \frac{\exp(\lambda u_i(a, s_{-i}))}{\sum_{a' \in A_i} \exp(\lambda u_i(a', s_{-i}))}, with λ>0\lambda > 0 serving as a precision parameter that controls the degree of . This function exhibits key limiting behaviors: as λ→∞\lambda \to \infty, the smoothed best response converges to the pure best response, selecting only utility-maximizing actions with probability 1; conversely, as λ→0\lambda \to 0, it approaches uniform randomization over all actions, reflecting maximal noise in decision-making. The quantal response equilibrium (QRE) emerges as a fixed point of the smoothed best response correspondence, where each player's distribution is a smoothed best response to the others' strategies, thereby generalizing the to account for and choice. Variants of the smoothed best response include the form, which uses the of distribution to weight , as well as entropy-regularized versions that explicitly maximize expected plus an term to encourage . The form, in particular, aligns closely with the softmax policy in , where it balances exploitation of high-value actions with via temperature-controlled randomization.

Applications and Extensions

In , smoothed best responses, as embodied in quantal response equilibrium (QRE), are applied in design to model bidders' noisy under , capturing deviations from perfect optimization in settings like all-pay auctions. Similarly, in market entry models, QRE incorporates probabilistic choices to represent agents' imperfect responses to competitors' strategies, leading to more realistic predictions of entry deterrence and coordination failures. Empirical studies in laboratory experiments demonstrate that QRE provides a superior fit to observed behavior compared to , as evidenced by McKelvey and Palfrey's foundational work on normal-form games, where players' choices align better with logit-based smoothing of payoffs. In and , smoothed best responses facilitate (RL) algorithms, where policy gradients optimize stochastic policies that approximate QRE by incorporating noise in action selection to handle exploration and uncertainty in multi-agent environments. No-regret learning methods, such as regret matching, leverage iterative best response adjustments to converge to coarse correlated equilibria, providing guarantees on performance in repeated games without requiring full . Recent advances in multi-agent RL up to 2025 emphasize decentralized approaches using best-response policies, enhancing scalability in and competitive settings through techniques like best response shaping, which refines agent interactions via targeted policy updates. Computationally, finding quantal response equilibria (fixed points of smoothed best responses) in general games is PPAD-hard, even for approximate solutions in some settings, underscoring the inherent difficulty of equilibrium computation under smoothing. Software tools like enable practical simulation and analysis of smoothed equilibria by supporting the and solving of finite normal-form games, including logit-based QRE calculations for and experimentation. Recent developments integrate smoothed best responses with for imperfect-information games, as seen in the Pluribus AI system (2019), which employs counterfactual regret minimization—a no-regret learning method to approximate equilibria—to achieve superhuman performance in six-player no-limit Texas Hold'em poker. Empirical studies further validate QRE models, showing that they predict behavioral data in strategic interactions more accurately than pure predictions, with logit smoothing explaining persistent errors and heterogeneity in human choices across diverse experimental paradigms.

References

  1. https://academics.hamilton.edu/economics/cgeorges/game-theory-files/Notation-Definitions.pdf
  2. https://ocw.mit.edu/courses/14-12-economic-applications-of-game-theory-fall-2012/0136e76dcd45a6f1d7b386c563452ff0_MIT14_12F12_chapter4.pdf
  3. https://www.cs.upc.edu/~ia/nash51.pdf
  4. http://theory.stanford.edu/~tim/f13/l/l16.pdf
  5. https://www.cs.jhu.edu/~mdinitz/classes/AGT/Spring2020/Lectures/lecture3.pdf
  6. https://nashpy.readthedocs.io/en/stable/text-book/best-responses.html
  7. https://vknight.org/Year_3_game_theory_course/Content/Chapter_04-Best_Responses/
  8. https://cs.uwaterloo.ca/~y328yu/classics/vonNeumann.pdf
  9. https://www.econstor.eu/bitstream/10419/233346/1/aboa-ce-dp131.pdf
  10. https://core.ac.uk/download/pdf/6805957.pdf
  11. https://sites.socsci.uci.edu/~bskyrms/bio/papers/StagHunt.pdf
  12. https://economics.uwo.ca/faculty/zheng/teaching/undergraduate_classes/Chapter9.pdf
  13. https://www.nature.com/articles/246015a0
  14. https://www.cirje.e.u-tokyo.ac.jp/research/workshops/micro/micropaper04/kojima.pdf
  15. https://assets.press.princeton.edu/chapters/s4-10001.pdf
  16. https://extranet.parisschoolofeconomics.eu/docs/guesnerie-roger/bernheim84.pdf
  17. https://www.cs.cornell.edu/~rafael/networks-html/chapter1.html
  18. http://slantchev.ucsd.edu/courses/gt/04-strategic-form.pdf
  19. https://doi.org/10.1016/S0899-8256(03)00089-4
  20. https://www.economics.utoronto.ca/osborne/igt/igtChapter4.pdf
  21. https://users.ssc.wisc.edu/~whs/research/2015_Handbook.pdf
  22. https://www.sciencedirect.com/science/article/pii/S0022053120300892
  23. https://people.maths.ox.ac.uk/scott/Papers/bestresponse.pdf
  24. https://www.sciencedirect.com/science/article/pii/S0899825696900445
  25. https://www.sciencedirect.com/science/article/pii/S0022053109000222
  26. https://arxiv.org/abs/2303.15386
  27. https://www.sciencedirect.com/science/article/pii/S0014292122002070
  28. https://arxiv.org/pdf/2106.15844
  29. https://www.sciencedirect.com/science/article/pii/S0899825685710238
  30. https://pubs.aeaweb.org/doi/10.1257/aer.98.1.180
  31. https://www.nature.com/articles/s41598-021-99428-0
  32. https://wwwf.imperial.ac.uk/~dturaev/Hart0.pdf
  33. https://www.frontiersin.org/journals/robotics-and-ai/articles/10.3389/frobt.2024.1229026/full
  34. https://arxiv.org/abs/2404.06519
  35. https://ojs.aaai.org/index.php/AAAI/article/view/16701/16508
  36. https://www.gambit-project.org/
  37. https://www.science.org/doi/10.1126/science.aay2400
  38. https://www.nature.com/articles/s41598-022-08426-3
Add your contribution
Related Hubs
User Avatar
No comments yet.