# Lecture 4: Dominance, Rationalizability, and Correlated Equilibria **Course:** CSCE 631-D, Intelligent Agents: Computational Game Solving, Fall 2026 **Instructor:** Alan Kuhnle, Texas A&M University **Companion notes for:** `m1/week1-lecture4-correlated-equilibria-f26.tex` > **Accessibility and use note.** > These notes are the accessible companion to the Lecture 4 Beamer slides. > Every slide is represented by a headed subsection (`### Slide N`) in deck > order. Terse slide bullets are expanded into readable prose; every equation > is restated in words; every table is rendered as one prose claim per row; > and every TikZ or diagrammatic figure carries a clearly labeled `Alt text:` > paragraph. The notes are designed so that a reader using a screen reader, or > studying asynchronously without the PDF, can learn the full lecture content > from this document alone. Section headings match the Beamer `\section{}` > titles. Cross-references to other lectures and modules use the Fall 2026 > numbering (M1 Lectures 1 to 4, M2 Lectures 5 to 8). --- ## Title and Plan ### Slide 1 -- Title Course title: CSCE 631-D, Intelligent Agents: Computational Game Solving. Lecture 4: Dominance, Rationalizability, and Correlated Equilibria. Instructor: Alan Kuhnle, Texas A&M University, Fall 2026. The course runs in two sections: an in-person recorded section and an asynchronous section. ### Slide 2 -- Today's Plan This lecture covers four topics in sequence. First, we review the maxmin concept and individual rationality from Lecture 3. Second, we develop the theory of dominated strategies and iterated elimination. Third, we introduce rationalizability and its relationship to dominance and Nash equilibrium. Fourth, we define correlated equilibrium and coarse correlated equilibrium, compare them to Nash equilibrium, and connect these ideas to coordination mechanisms for multi-agent LLM systems. The new arc in this lecture is the idea that shared prompts and orchestrator messages in multi-agent LLM systems act as correlating devices, linking the formal concept of correlated equilibrium to modern agent architectures. --- ## Review of Maxmin ### Slide 3 -- Maxmin and Security Level (Review) This slide reviews the maxmin concept from Lecture 3. The maxmin value of player i, written v_i with an overline, is defined as the maximum over player i's mixed strategies sigma_i of the minimum over all opponent mixed-strategy profiles sigma_{-i} of player i's expected utility u_i(sigma_i, sigma_{-i}). In words: player i chooses the strategy that maximizes the worst-case payoff, assuming opponents play adversarially. The maxmin value v_i is called the security level. It is the payoff that player i can guarantee regardless of what the opponents do. A maxmin strategy is pessimistic: it assumes the worst about opponent behavior. In zero-sum games, the maxmin strategy coincides with the Nash equilibrium strategy. In general-sum games, the maxmin strategy and the Nash equilibrium strategy are generally different; the maxmin strategy is typically more conservative than Nash equilibrium play. ### Slide 4 -- Individual Rationality A payoff vector $(w_1,\ldots,w_n)$ is individually rational if $w_i$ is at least player $i$'s security level $\overline v_i$ for every player $i$. The proposition on this slide states: in any Nash equilibrium $\sigma^*$, the payoff $u_i(\sigma^*)$ is at least $\overline v_i$ for every player $i$. The proof is short. In a Nash equilibrium, sigma_i* is a best response to the opponents' strategies. Its payoff cannot fall below the maxmin value, because player i could deviate to the maxmin strategy and guarantee v_i. The consequence is that Nash equilibrium payoffs are always individually rational. The converse is false: not every individually rational payoff profile corresponds to a Nash equilibrium. --- ## Dominated Strategies ### Slide 5 -- Strict Dominance Strategy s_i strictly dominates strategy s_i' if, for every possible opponent strategy profile s_{-i}, the payoff u_i(s_i, s_{-i}) is strictly greater than u_i(s_i', s_{-i}). A strategy is strictly dominated if some other strategy strictly dominates it. The proposition states: a rational player never plays a strictly dominated strategy. Moreover, no strictly dominated strategy appears in the support of any Nash equilibrium. The proof follows directly from the definition. If s_i' is strictly dominated by s_i, then for any opponent mixed strategy sigma_{-i}, the payoff from s_i exceeds the payoff from s_i'. Therefore s_i' is never a best response, and a Nash equilibrium assigns positive probability only to best responses. ### Slide 6 -- Weak Dominance Strategy s_i weakly dominates strategy s_i' if, for every opponent strategy profile s_{-i}, the payoff u_i(s_i, s_{-i}) is at least u_i(s_i', s_{-i}), with strict inequality for at least one s_{-i}. Unlike strict dominance, weakly dominated strategies can appear in Nash equilibria. Whether to eliminate weakly dominated strategies is debatable, because elimination can change the set of Nash equilibria. Weak dominance plays an important role in mechanism design. The property called "dominant-strategy incentive-compatible" typically refers to weak dominance: truth-telling weakly dominates every other strategy. ### Slide 7 -- Dominance by Mixed Strategies A pure strategy can be strictly dominated by a mixed strategy, even when no single pure strategy dominates it. The slide gives an example. Consider a game where Player 1 chooses among T, M, and B, and Player 2 chooses between L and R. Player 1's payoffs are: T gets 3 against L and 0 against R; M gets 0 against L and 3 against R; B gets 1 against L and 1 against R. Neither T nor M dominates B: T loses to B against R, and M loses to B against L. However, the mixed strategy that plays T with probability 1/2 and M with probability 1/2 yields expected payoff 3/2 against both L and R. Since 3/2 is strictly greater than 1 (the payoff from B against either column), this mixed strategy strictly dominates B. The lesson is that when checking for dominance, one must consider mixed strategies, not only pure strategies. --- ## Iterated Elimination of Dominated Strategies ### Slide 8 -- IEDS: The Idea Iterated elimination of strictly dominated strategies (IEDS) proceeds in rounds. In each round, find and remove all strictly dominated strategies. In the reduced game, repeat. Continue until no dominated strategies remain. The key property is that IEDS never eliminates a Nash equilibrium. The justification rests on common knowledge of rationality. A rational player never plays a strictly dominated strategy. If all players are rational, and this fact is common knowledge, then iterative reasoning applies: round k of elimination corresponds to k levels of iterated knowledge ("I know that you know that I know ... that no one plays a dominated strategy"). ### Slide 9 -- IEDS: Example The example is a 3-by-3 game. Player 1 chooses among T, M, and B; Player 2 chooses among L, C, and R. The payoff pairs (Player 1, Player 2) are: T against L yields (1, 0); T against C yields (1, 2); T against R yields (0, 1). M against L yields (0, 3); M against C yields (0, 1); M against R yields (2, 0). B against L yields (0, 1); B against C yields (2, 0); B against R yields (3, 1). Round 1 checks for strict dominance. For Player 2, the payoff columns are L = (0, 3, 1), C = (2, 1, 0), R = (1, 0, 1). No pure strategy of Player 2 strictly dominates another. For Player 1, compare rows. Row B gives payoffs (0, 2, 3) and row M gives payoffs (0, 0, 2). Since 0 = 0 (tie at L), 2 > 0, and 3 > 2, row B only weakly dominates row M — not strictly. The elimination proceeds instead via mixed-strategy dominance: the mixture σ₁ = ¼T + ¾B strictly dominates M, since expected payoffs against L, C, R are (¼, 7/4, 9/4) vs M's (0, 0, 2), all strictly greater. This ties back to the "Dominance by Mixed Strategies" slide earlier in the lecture. Eliminate M. ### Slide 10 -- IEDS: Example (cont.) After eliminating M, the reduced game has Player 1 choosing between T and B, and Player 2 choosing among L, C, and R. The payoff pairs are: T against L yields (1, 0); T against C yields (1, 2); T against R yields (0, 1). B against L yields (0, 1); B against C yields (2, 0); B against R yields (3, 1). Round 2 checks Player 2's payoffs in the reduced game: L = (0, 1), C = (2, 0), R = (1, 1). R weakly dominates L (both entries at least as large, with strict inequality in the first coordinate), but this is strict IEDS, and L is not strictly dominated by any pure strategy. One might consider the mixed strategy (1/2)C + (1/2)R for Player 2, which gives payoffs (3/2, 1/2). Comparing against L's payoffs (0, 1): the first coordinate 3/2 exceeds 0, but the second coordinate 1/2 is less than 1. So L is not strictly dominated by this mixture either. IEDS terminates here. The surviving game may still have multiple Nash equilibria. ### Slide 11 -- IEDS: Formal Properties Three formal properties of IEDS are stated as a theorem. First, order independence: the set of strategies surviving IEDS with strict dominance is the same regardless of the order in which dominated strategies are eliminated. Second, NE preservation: every Nash equilibrium of the original game survives IEDS. Third, solvability: if IEDS reduces the game to a single strategy profile, that profile is the unique Nash equilibrium. An important warning accompanies the theorem. Order independence fails for iterated elimination of weakly dominated strategies. The set of surviving strategies can depend on the elimination order. --- ## Rationalizability ### Slide 12 -- Rationalizability Rationalizability, introduced independently by Bernheim (1984) and Pearce (1984), is defined as follows: a strategy s_i is rationalizable if it survives iterated elimination of strategies that are never a best response. Equivalently, s_i is rationalizable if there exist beliefs sigma_{-i} (a probability distribution over opponents' strategies) such that s_i is a best response to those beliefs, and the beliefs are "consistent" in the sense that they assign positive probability only to rationalizable strategies of the opponents. A theorem relates rationalizability to IEDS. For two-player games, the set of rationalizable strategies equals the set of strategies surviving IEDS. For games with more than two players, rationalizability is weakly more permissive than IEDS: every strategy surviving IEDS is rationalizable, but some rationalizable strategies may not survive IEDS. ### Slide 13 -- Relationship: Dominance, Rationalizability, NE This slide presents a TikZ inclusion diagram showing how the key solution concepts nest inside one another. Alt text: The figure shows four horizontally centered rounded rectangles stacked vertically, connected by downward arrows. From top to bottom, the boxes are labeled "All Strategies," "Strategies surviving IEDS," "Rationalizable Strategies," and "Nash Equilibria." The arrow from "All Strategies" to "Strategies surviving IEDS" is labeled with a subset symbol, indicating that strategies surviving IEDS are a subset of all strategies. The arrow from "Strategies surviving IEDS" to "Rationalizable Strategies" is labeled "= (2-player)," indicating that in two-player games these two sets coincide. The arrow from "Rationalizable Strategies" to "Nash Equilibria" is labeled with a superset symbol, indicating that the set of rationalizable strategies contains the set of Nash equilibrium strategies. The containment relationships, from largest to smallest set, are as follows. The set of all strategies is the largest. IEDS removes strictly dominated strategies round by round; what survives is a subset of all strategies. In two-player games, the rationalizable strategies are exactly the strategies surviving IEDS; in games with more than two players, the rationalizable set can be strictly larger than the IEDS survivors. The Nash equilibrium strategies are a subset of the rationalizable strategies: every strategy played with positive probability in some Nash equilibrium is rationalizable, but not every rationalizable strategy is part of a Nash equilibrium. A concrete witness for the strict inclusion between NE and rationalizability: in a 3-by-3 game, a strategy may be a best response to some belief over the opponent's rationalizable strategies yet fail to appear in any Nash equilibrium, because the belief itself need not be an equilibrium belief. --- ## Correlated Equilibrium ### Slide 14 -- Motivation: Beyond Nash Nash equilibrium has three limitations that motivate a broader solution concept. First, when multiple Nash equilibria exist, players face a coordination problem: which equilibrium should they play? Second, mixed Nash equilibria require players to randomize independently; no correlation is allowed. Third, the Nash equilibrium payoff can be Pareto-dominated by outcomes that are achievable through correlated play. The idea, due to Aumann (1974), is to allow players to receive correlated signals from a trusted mediator before choosing their actions. This leads to a strictly larger set of achievable outcomes called the correlated equilibria. ### Slide 15 -- The Mediator / Signal Device The setup for correlated equilibrium involves three steps. First, a mediator draws a strategy profile s = (s_1, ..., s_n) from a joint distribution p over the set of all strategy profiles S. Second, the mediator privately tells each player i their recommended action s_i, without revealing the other players' recommendations. Third, each player decides whether to follow the recommendation. A correlated equilibrium is a distribution p such that every player finds it optimal to follow the recommendation, given their private signal. The key distinction from Nash equilibrium is the source of randomness. In a Nash equilibrium, players randomize independently. In a correlated equilibrium, randomization can be correlated through the mediator's joint distribution. ### Slide 16 -- Shared Prompts as Correlating Devices This slide connects the formal mediator concept to multi-agent LLM systems, where two forms of correlation arise. The first form is the private mediator model, which matches the correlated equilibrium setup. A mediator draws a joint recommendation and sends each agent its action privately. Each agent observes only its own signal and conditions its decision on that signal alone. The second form is shared public context. A common system prompt or orchestrator message is observed by all agents. Every agent sees the same context. This is not the same information structure as a private mediator: because each agent knows the full signal (not just its own recommendation), the deviation incentives change. Both forms correlate play, but the equilibrium analysis differs. Private recommendations support the correlated equilibrium concept, where each agent conditions on its own signal and has no incentive to deviate. A shared prompt creates common knowledge; agents coordinate, but the analysis must account for the fact that each agent knows what the others were told. ### Slide 17 -- Correlated Equilibrium: Formal Definition The formal definition, due to Aumann (1974), is as follows. A probability distribution p over the set S_1 times ... times S_n of strategy profiles is a correlated equilibrium if, for every player i and every pair of strategies s_i and s_i' in S_i, the following inequality holds: The sum over all opponent profiles s_{-i} of p(s_i, s_{-i}) times [u_i(s_i, s_{-i}) minus u_i(s_i', s_{-i})] is at least zero. The interpretation is: conditional on being told to play s_i, player i has no incentive to deviate to any alternative action s_i'. The left-hand side measures the expected gain from obedience over deviation, weighted by the probability that the mediator's joint draw includes s_i for player i. The condition can be restated using conditional expectations. For all players i, all s_i, and all s_i': the expected utility of playing s_i when opponents are drawn from the conditional distribution p(. | s_i) is at least as large as the expected utility of deviating to s_i' under the same conditional distribution. ### Slide 18 -- Example: Traffic Light as a Correlated Equilibrium The example is the Game of Chicken, modeling two cars at an intersection. Each player chooses Go or Stop. The payoff pairs are: Go against Go yields (-10, -10), representing a crash. Go against Stop yields (5, 0). Stop against Go yields (0, 5). Stop against Stop yields (0, 0). The game has two pure Nash equilibria: (Go, Stop) with payoff sum 5, and (Stop, Go) with payoff sum 5. A mixed Nash equilibrium also exists, but it assigns positive probability to the crash outcome (Go, Go). A traffic light acts as a mediator. It signals (Go, Stop) with probability 1/2 and (Stop, Go) with probability 1/2. This avoids the crash entirely. To verify the correlated equilibrium condition: if a player is told "Go," they know the opponent was told "Stop," so going yields payoff 5 and stopping yields 0; obedience is optimal. If a player is told "Stop," they know the opponent was told "Go," so stopping yields 0 and going yields -10; obedience is again optimal. The expected payoff under this correlated equilibrium is (5/2, 5/2), which is better for the disadvantaged player than either pure Nash equilibrium. ### Slide 19 -- Another CE: Game of Chicken This slide shows that a correlated equilibrium can place positive probability on a profile that is not itself a Nash equilibrium while preserving obedience. Consider the following joint distribution over the Game of Chicken: p(Go, Go) = 0; p(Go, Stop) = 1/3; p(Stop, Go) = 1/3; p(Stop, Stop) = 1/3. Verification: if told "Go," the player knows the opponent plays Stop (the only possibility consistent with a positive-probability recommendation of Go). Playing Go gives 5; deviating to Stop gives 0. Obedience is optimal. If told "Stop," the opponent plays Go with probability 1/2 and Stop with probability 1/2 (since the two outcomes with s_i = Stop are equally likely). The expected payoff from obeying (playing Stop) is (1/2)(0) + (1/2)(0) = 0. The expected payoff from deviating (playing Go) is (1/2)(-10) + (1/2)(5) = -5/2, which is negative. Obedience is optimal. Player 1 receives 5 only at (Go, Stop), so Player 1's expected payoff is (1/3)(5) = 5/3. Player 2 receives 5 only at (Stop, Go), so Player 2's expected payoff is also 5/3. Total welfare is therefore 10/3. This CE distribution is outside the convex hull of Nash-equilibrium distributions: the mixed NE assigns positive probability to (Go, Go), while the two pure NE assign zero probability to both (Go, Go) and (Stop, Stop), so no convex combination can simultaneously have p(Go, Go) = 0 and p(Stop, Stop) = 1/3. Its payoff vector (5/3, 5/3), however, lies inside the convex hull of the NE payoff vectors. The strict-containment claim is about distributions, not necessarily their payoff projection. --- ## Correlated Equilibrium as a Linear Program ### Slide 20 -- CE as an LP The correlated equilibrium constraints are linear in the distribution p. The CE feasibility problem can be written as a linear program. The variables are the probabilities p(s) for each strategy profile s in S. The total number of variables is the product of the strategy-set sizes across all players. The constraints are of two types. The incentive constraints state that for every player i and every pair of strategies s_i, s_i': the sum over s_{-i} of p(s_i, s_{-i}) times [u_i(s_i, s_{-i}) minus u_i(s_i', s_{-i})] is at least zero. The total number of incentive constraints is the sum over all players of |S_i| times (|S_i| minus 1). The probability constraints state that all p(s) are nonnegative and sum to 1. Because all constraints are linear, the set of correlated equilibria forms a convex polytope, and finding a CE is a polynomial-time LP feasibility problem. One can optimize any linear objective over this polytope, for instance maximizing social welfare or fairness. Computation of CE and its variants is deepened in Lecture 8 (M2). ### Slide 21 -- CE vs. NE: Computational Comparison This slide contrasts Nash equilibrium and correlated equilibrium across five dimensions. Nash equilibrium is defined as a fixed point of best-response correspondences. Correlated equilibrium is defined by linear incentive constraints. The structure of the NE set involves nonlinear (product) constraints. The structure of the CE set is a convex polytope defined by linear inequalities. Computing a Nash equilibrium is PPAD-complete in general two-player games. Computing a correlated equilibrium is polynomial-time via linear programming. The set of Nash equilibria is finite (generically). The set of correlated equilibria is a convex polytope, which is infinite when it has positive dimension. Uniqueness is rare for both concepts. The tractability gap between CE and NE is the central computational insight of this comparison: the convexity of the CE polytope (an intersection of half-spaces) is what makes it computationally tractable, while the NE conditions involve polynomial constraints. ### Slide 22 -- Optimizing over CE Given a two-player game, one can optimize various objectives over the CE polytope. To maximize social welfare, one solves: maximize over p in CE of the sum over all profiles s of p(s) times [u_1(s) + u_2(s)]. This is a linear objective over a polytope, hence a linear program. To maximize fairness (the egalitarian objective), one solves: maximize over p in CE of the minimum over players i of the sum over s of p(s) times u_i(s). This is not directly a linear program, but a standard transformation introduces an auxiliary variable t representing the minimum payoff, adds constraints requiring each player's expected payoff to be at least t, and maximizes t. The result is again a linear program. To maximize any single player's payoff, one solves: maximize over p in CE of the sum over s of p(s) times u_i(s). This is a linear program directly. --- ## Relationship Between NE and CE ### Slide 23 -- Every NE Is a CE The theorem states: if sigma* = (sigma_1*, ..., sigma_n*) is a Nash equilibrium, then the product distribution p(s) = the product over all players i of sigma_i*(s_i) is a correlated equilibrium. The proof uses the independence structure of Nash equilibrium. Under the product distribution, the conditional distribution of opponents' strategies given player i's action s_i is exactly sigma_{-i}* (by independence). So the CE incentive constraint, which requires that following the recommendation is optimal conditional on one's own signal, reduces to the NE best-response condition, which holds by assumption. The conclusion is that NE is a subset of CE when Nash equilibria are viewed as product distributions over strategy profiles. The inclusion is generally strict: correlated equilibria allow joint distributions that are not product measures, and these can achieve payoffs outside the NE set. ### Slide 24 -- The CE Polytope Contains the NE Convex Hull This slide presents a schematic two-dimensional projection of the geometric relationship between the CE polytope and Nash-equilibrium product distributions in probability-distribution space. Alt text: The figure is a schematic two-dimensional projection of probability-distribution space. A filled five-sided region represents the CE polytope. Inside it, three points labeled NE_1, NE_2, and NE_3 represent Nash product distributions. A dashed triangle connects those points and represents their convex hull. The triangle lies entirely within the larger CE region, which illustrates that convex mixtures of Nash distributions remain correlated equilibria and that additional correlated distributions may lie outside that hull. The CE polytope is convex and contains every Nash equilibrium when an NE is represented by its product distribution over profiles. Because it is convex, it contains every convex combination of those product distributions. The Game of Chicken distribution on Slide 19 witnesses strict containment in distribution space. Its payoff vector need not lie outside the convex hull of NE payoff vectors, because mapping distributions to expected payoffs is a projection that can collapse distinct distributions. ### Slide 25 -- Aumann's Result Aumann's theorem (1974) establishes three properties of the CE set for finite games. First, the set of correlated equilibria is a convex polytope, defined by the intersection of the linear incentive constraints. Second, it is a superset of the convex hull of Nash equilibria. Third, it is nonempty, because every finite game has at least one Nash equilibrium, and every Nash equilibrium is a correlated equilibrium. Aumann's broader philosophical point is that if players share a common prior and have common knowledge of rationality, the appropriate solution concept is correlated equilibrium, not Nash equilibrium. Nash equilibrium implicitly assumes that players randomize independently. Correlated equilibrium relaxes this to allow any joint distribution that is consistent with incentive compatibility. --- ## Comparison of Solution Concepts ### Slide 26 -- Solution Concepts: Two Related Hierarchies This slide separates two relationships that cannot be written as one total chain because they compare different kinds of mathematical objects. The first hierarchy concerns probability distributions over action profiles: every dominant-strategy equilibrium is a Nash equilibrium; every Nash equilibrium induces a correlated equilibrium; and every correlated equilibrium is a coarse correlated equilibrium. Thus dominant-strategy equilibria are a subset of NE, which is a subset of CE, which is a subset of CCE. CE permits deviations after a player observes a private recommendation. CCE tests only deviations selected before the recommendation is observed. Lecture 8 defines CCE, and Module 3 proves its connection to external regret. The second hierarchy concerns sets of pure strategies. Every pure strategy used with positive probability in some Nash equilibrium is rationalizable, but some rationalizable strategies need not occur in any Nash equilibrium. In two-player games, the rationalizable strategies coincide with those surviving iterated elimination of strictly dominated strategies when domination by mixed strategies is allowed. The two hierarchies meet at Nash equilibrium, but rationalizable strategies are not a superset of CCE distributions, and CCE distributions are not a superset of rationalizable strategies. One is a set of strategies; the other is a set of distributions over profiles. ### Slide 27 -- When to Use Which Concept? This slide presents guidance on when each solution concept is appropriate. Dominant-strategy equilibrium is the goal of mechanism design: the designer constructs the game so that truth-telling is a dominant strategy. IEDS is appropriate when common knowledge of rationality is a plausible assumption. Nash equilibrium is the standard prediction for independently deployed agents. Correlated equilibrium applies when a mediator exists, such as a traffic light, a communication protocol, or an orchestrator in a multi-agent system. Coarse correlated equilibrium applies when agents learn via no-regret dynamics (Module 3). Maxmin or security strategies apply in adversarial settings where worst-case guarantees are needed. For multi-agent LLM systems specifically: CE is the natural concept when an orchestrator or shared prompt coordinates agents; NE is the natural concept when agents are independently deployed with no shared coordination mechanism. The choice of solution concept often depends on a computational question: can we compute it, learn it, or enforce it? ### Slide 28 -- Computational Complexity Summary This slide summarizes the computational complexity of finding each solution concept, with all claims stated relative to the explicit (fully enumerated) representation. Dominant-strategy equilibrium in explicit form can be found in polynomial time, specifically O(|S|^2) where |S| is the strategy-space size. IEDS in explicit form can be computed in polynomial time. Nash equilibrium for two-player zero-sum games in explicit bimatrix form can be computed in polynomial time via linear programming (class P). Nash equilibrium for two-player general-sum games in explicit bimatrix form is PPAD-complete. Correlated equilibrium in explicit form can be computed in polynomial time via linear programming (class P). Coarse correlated equilibrium in explicit form can be computed in polynomial time via linear programming (class P). Maxmin strategies in explicit bimatrix form can be computed in polynomial time via linear programming (class P). Structured games (potential, congestion, symmetric, low-rank) and approximate Nash equilibrium have nuanced complexity depending on the representation; these are treated in detail in Lecture 6 (M2). --- ## Extended Examples ### Slide 29 -- CE of Battle of the Sexes This slide derives the CE constraints for the Battle of the Sexes game. The joint distribution is written with four variables: p_{OO} for (Opera, Opera), p_{OF} for (Opera, Football), p_{FO} for (Football, Opera), and p_{FF} for (Football, Football). The CE incentive constraints for Player 1 are as follows. If told Opera: the expected payoff from playing Opera must be at least the expected payoff from deviating to Football. This gives 3 p_{OO} >= 2 p_{OF}. If told Football: the expected payoff from playing Football must be at least the expected payoff from deviating to Opera. This gives 2 p_{FF} >= 3 p_{FO}. The CE incentive constraints for Player 2 are symmetric in the appropriate sense. If told Opera: 2 p_{OO} >= 3 p_{FO}. If told Football: 3 p_{FF} >= 2 p_{OF}. The probability constraints are: p_{OO} + p_{OF} + p_{FO} + p_{FF} = 1, with all four variables nonnegative. ### Slide 30 -- CE of Battle of the Sexes: Optimal Maximizing social welfare over the CE polytope means maximizing the sum of both players' payoffs. The objective is: maximize 5 p_{OO} + 5 p_{FF}, subject to the CE constraints from Slide 29. Every distribution supported on the two coordinated outcomes (Opera, Opera) and (Football, Football) attains the maximum total welfare of 5. One symmetric welfare-optimal solution is p_{OO} = p_{FF} = 1/2 and p_{OF} = p_{FO} = 0. This is the "fair coin flip" CE: the mediator recommends that both players go to Opera together or both go to Football together, each with probability 1/2. The expected payoffs under this CE are u_1 = 5/2 and u_2 = 5/2. For comparison, the three Nash equilibria of Battle of the Sexes yield the following payoffs. The pure NE at (Opera, Opera) gives (3, 2). The pure NE at (Football, Football) gives (2, 3). The mixed NE gives (6/5, 6/5). The welfare-optimal CE achieves higher total payoff than the mixed NE and is fairer than either pure NE (which each favor one player). --- ## Coordination in Multi-Agent LLM Systems ### Slide 31 -- Coordination in Multi-Agent LLM Pipelines This slide reinterprets common multi-agent LLM architectures as correlation devices. In a debate architecture, two agents argue opposing sides of a question. The protocol (turn order, the identity of the judge, and the scoring rule) acts as the correlating device that structures the interaction. In an orchestrator-worker architecture, a central agent assigns roles and aggregates outputs. The orchestrator's dispatch message to each worker is a private signal, analogous to the mediator's private recommendation in a correlated equilibrium. In a role-assignment architecture, agents receive role prompts such as "you are the critic." The role specification correlates play by constraining each agent's behavior. The central incentive question is: if an agent gains by ignoring its assigned role (for example, if the "critic" agent produces better evaluations by also suggesting solutions), then the architecture is not incentive-compatible. The agent has a profitable deviation from the recommended behavior. Module 7 formalizes this question: under what conditions does a multi-agent LLM pipeline constitute an equilibrium of the game induced by the architecture? ### Slide 32 -- No-Regret Learning and CCE (Preview) This slide previews a major result from Module 3. The standard external-regret theorem states that if all players have vanishing external regret in repeated play, the empirical distribution of play approaches the set of coarse correlated equilibria (CCE); see Cesa-Bianchi and Lugosi (2006). Hart and Mas-Colell's regret matching and Foster and Vohra's calibrated learning instead support the stronger CE target through internal or swap-regret-style conditions. CCE is the convergence target of no-regret dynamics. The containment hierarchy is NE is a subset of CE, which is a subset of CCE. With no-swap-regret (a stronger condition than no-regret), convergence is to CE itself, not merely CCE. Three practical consequences follow. First, no external mediator is needed: the history of play serves as the correlating device. Second, no-regret dynamics are computationally efficient, unlike exact NE computation (which is PPAD-complete). Third, this provides a constructive path to equilibrium: let agents play repeatedly and the empirical distribution converges. Module 3 develops regret minimization in full and proves this convergence result. ### Slide 33 -- Summary This lecture covered four main topics. Maxmin review: the security level v_i is the payoff a player can guarantee regardless of opponents. Nash equilibrium payoffs are always individually rational. Dominated strategies and IEDS: strictly dominated strategies never appear in Nash equilibrium support. IEDS preserves all Nash equilibria and is order-independent for strict dominance. Rationalizability: strategies consistent with common knowledge of rationality. In two-player games, the rationalizable set equals the IEDS survivors. Correlated equilibrium (CE): obedience to a mediator's private signal. The CE set is a convex polytope, computable by linear programming. Coarse correlated equilibrium (CCE): the containment is NE subset of CE subset of CCE. No-regret dynamics converge to CCE (Module 3). There are two related hierarchies, not one total chain. For distributions over profiles, dominant-strategy equilibria are a subset of NE, which is a subset of CE, which is a subset of CCE. Separately, pure strategies used in Nash equilibria are rationalizable. Rationalizable strategies and CCE distributions are different object types and are not nested. For multi-agent LLM systems: shared prompts and orchestrators are correlating devices. The distinction between private signals and public context determines which equilibrium concept applies. --- ## References and forward links **References cited in this lecture:** - Aumann, R. (1974). "Subjectivity and Correlation in Randomized Strategies." *Journal of Mathematical Economics*, 1(1), 67--96. (Correlated equilibrium: definition, existence, and the philosophical argument for CE over NE.) - Bernheim, B. D. (1984). "Rationalizable Strategic Behavior." *Econometrica*, 52(4), 1007--1028. (Rationalizability.) - Pearce, D. G. (1984). "Rationalizable Strategic Behavior and the Problem of Perfection." *Econometrica*, 52(4), 1029--1050. (Rationalizability, independent of Bernheim.) - Cesa-Bianchi, N., and Lugosi, G. (2006). *Prediction, Learning, and Games.* Cambridge University Press. (Vanishing external regret implies convergence of empirical play to CCE.) - Hart, S., and Mas-Colell, A. (2000). "A Simple Adaptive Procedure Leading to Correlated Equilibrium." *Econometrica*, 68(5), 1127--1150. (Regret matching and the stronger CE target.) - Foster, D. P., and Vohra, R. V. (1997). "Calibrated Learning and Correlated Equilibrium." *Games and Economic Behavior*, 21(1--2), 40--55. (Calibrated learning and CE.) **Textbook:** - Shoham, Y., and Leyton-Brown, K. *Multiagent Systems: Algorithmic, Game-Theoretic, and Logical Foundations.* Chapter 3 (Normal-Form Games) covers dominance, IEDS, rationalizability, NE, and correlated equilibrium. **Forward links within the course:** - Lecture 5 (M2): Computing Nash equilibria via support enumeration and Lemke-Howson. The algorithmic tools for the games analyzed here. - Lecture 6 (M2): PPAD-completeness of Nash equilibrium, approximate Nash equilibrium, and the corrected structured-games complexity table. The computational hardness that makes CE's polynomial-time computability significant. - Lecture 8 (M2): Correlated equilibrium LP computation in depth, coarse correlated equilibrium (CCE) formal definition, safe best response, and empirical game-theoretic analysis (EGTA). - Module 3 (Weeks 5 to 6): Regret minimization, regret matching, and the convergence of no-regret dynamics to CCE. - Module 7 (Week 11): Multi-agent LLM systems, EGTA applied to LLM populations, and the formal treatment of incentive compatibility in multi-agent LLM pipelines. - PA1 (due Week 3): Empirical payoff estimation and equilibrium analysis of LLM agents. Students compute Nash equilibria and analyze sensitivity to payoff estimation error.