# Lecture 1: Introduction — Games, Agents, and Strategic Interaction Course: CSCE 631-D, Intelligent Agents — Computational Game Solving, Fall 2026 Instructor: Alan Kuhnle, Texas A&M University > **Accessibility and use note.** These notes are the accessible companion to > the Beamer slide deck `week1-lecture1-intro-game-theory-f26.tex`. They are > designed to be read without viewing the PDF: every table is restated as > prose, every diagram receives an alt-text description, and notation is > explained in words alongside the symbols. Screen-reader users and > asynchronous-section students should be able to learn the full lecture > content from this document alone. Demo-anchor slides include a complete > expected scripted transcript so that students who cannot attend the live > recording receive equivalent content. --- ## Opening ### Slide 1 — Title This is the title slide for Lecture 1 of CSCE 631-D, Fall 2026. The course title is "Intelligent Agents — Computational Game Solving." The lecture title is "Introduction — Games, Agents, and Strategic Interaction." The instructor is Alan Kuhnle at Texas A&M University. A note at the bottom of the slide states that the in-person section is recorded for the asynchronous section. ### Slide 2 — Today's Plan The lecture follows two arcs: agents first, then games. The slide displays the lecture's table of contents, which is organized into the following sections: What Is Game Theory; What Is an Agent; Players, Strategies, and Payoffs; Classic Examples; Pure and Mixed Strategies; Formal Definition and Taxonomy; and Looking Ahead. The first arc (agents) covers the agent loop, a worked ReAct trace, a live demo, and the formal agent-environment tuple. The second arc (games) introduces normal-form games, classic examples, mixed strategies, and a taxonomy of game classes. --- ## What Is Game Theory? ### Slide 3 — What Is Game Theory? Game theory is the mathematical study of strategic interaction among rational decision-makers. Three key ingredients define any game-theoretic situation. First, there are multiple agents (called players) whose outcomes depend on each other's choices. Second, each agent acts to maximize their own utility, also called their payoff. Third, agents reason about what the other players will do. The central question of game theory is: what outcomes should we predict, or prescribe, when rational agents interact? ### Slide 4 — Brief History The slide lists seven milestones in the development of game theory. In 1928, von Neumann proved the minimax theorem for two-player zero-sum games, establishing that such games have a well-defined value. In 1944, von Neumann and Morgenstern published *Theory of Games and Economic Behavior*, the first comprehensive treatment of the field. In 1950, Nash proved the existence of equilibria in general (non-zero-sum) games, the result now known as Nash's theorem. In 1967 to 1968, Harsanyi developed the theory of games of incomplete information, where players are uncertain about other players' types. In 1974, Aumann introduced correlated equilibria, a solution concept that generalizes Nash equilibrium by allowing players to condition their strategies on a shared signal. In 1994, Nash, Harsanyi, and Selten received the Nobel Prize in Economics for their contributions to game theory. From the 2000s to the present, algorithmic game theory has emerged as a major research area, studying the computation of equilibria, mechanism design, and online learning in games. ### Slide 5 — Why Game Theory in CS? Game theory arises throughout computer science. In internet and network settings, selfish agents make routing and congestion decisions that affect one another. In auctions and mechanism design, platforms such as Google and Meta run ad auctions, governments run spectrum auctions, and matching markets allocate resources. In multi-agent AI, reinforcement learning, LLM alignment, and cooperative or competitive agents all involve strategic reasoning. In security, adversarial models and Stackelberg games formalize attacker-defender interactions. In complexity theory, the class PPAD captures the hardness of equilibrium computation. The slide adds the Fall 2026 framing for this course: today's multi-agent systems are LLM agents. Negotiation bots, multi-agent pipelines, and agent marketplaces are the course's motivating population of players. --- ## What Is an Agent? ### Slide 6 — What Is an Agent? This slide presents operational definitions drawn from Anthropic's "Building Effective Agents" (December 2024). Three levels of sophistication are distinguished. A language model is a single LLM call with no control flow. It receives an input and produces an output in one pass. A workflow consists of LLM calls orchestrated by fixed, human-designed control flow. Examples include chains, routers, and pipelines. The human designs which steps occur and in what order; the LLM fills in each step. An agent is a system where the LLM itself directs the control flow, choosing which tools to call and when to stop. The LLM makes the sequencing decisions, not a human-written script. For this course, an agent is defined as an LLM with tool access and LLM-directed control flow. The "game" emerges when two or more such agents interact strategically. ### Slide 7 — The Agent Loop The agent loop has three repeating phases: observe, reason, act. In the observe phase, the agent reads the environment state. This could be tool output, a user message, or the game history from prior rounds. In the reason phase, the LLM produces a chain of thought. This reasoning is internal and is not shown to the environment or to other players. In the act phase, the LLM selects and invokes a tool, or emits a final response. Tools are the agent's action set; the LLM's generation process is the policy that selects among those actions. Alt text: The slide displays the three phases as a horizontal flow diagram with arrows: "Observe" followed by a rightward arrow to "Reason," followed by a rightward arrow to "Act," followed by an arrow looping back to the beginning with the label "(repeat)." ### Slide 8 — A ReAct Trace ReAct (Yao et al., ICLR 2023) is a prompting framework that interleaves reasoning and acting. The slide shows a six-step trace of a ReAct agent playing an iterated prisoner's dilemma. Each step is labeled with its type. **Step 1 (Thought).** The agent reasons: "The opponent cooperated last round. Cooperating again maximizes long-run payoff." This is the agent's internal chain of thought; the environment does not see it. **Step 2 (Action).** The agent calls the tool `play(cooperate)`, selecting cooperation as its action for this round. **Step 3 (Observation).** The environment responds: "Opponent played Defect. Payoff: negative 3." The agent learns that its opponent defected while it cooperated, yielding the worst possible outcome for the agent. **Step 4 (Thought).** The agent reasons: "Opponent defected; I should retaliate." The agent updates its belief about the opponent and decides to switch strategies. **Step 5 (Action).** The agent calls `play(defect)`, selecting defection for the next round. **Step 6 (Observation).** The environment responds: "Opponent played Defect. Payoff: negative 2." Both players defected, yielding the mutual-defection payoff. This trace is one realized trajectory through the interaction. It is not a game tree: a game tree would include all possible sequences of actions (the counterfactual branches where the agent or opponent made different choices), not just the single path that was actually taken. ### Slide 9 — Demo: ReAct Agent on the TAMU API This is a demo-anchor slide. The instructor performs a live demo, recorded for the asynchronous section. The slide shows the run command and lists what to watch for during the demo. The run command is: ``` ssh [COURSE_SERVER] python demos/react_ipd.py ``` The audience should watch for: the raw prompt sent to the LLM; the streamed Thought, Action, and Observation JSON; the final action selected by the agent; the model name (a live-run field the instructor fills during recording); and the token cost versus the five-dollar-per-day budget (also a live-run field). The following is an *expected scripted transcript* of the demo. It illustrates the structure of the output that students should see. The pinned model name, live token totals, and live dollar cost are fields that the instructor must replace with actual values during the recorded run. ``` $ ssh [COURSE_SERVER] Last login: [date] from [ip] [USER@COURSE_SERVER ~]$ $ python demos/react_ipd.py === ReAct Agent: Iterated Prisoner's Dilemma === Model: [PINNED MODEL NAME — instructor replaces during live run] API: TAMU LLM API Budget: $5.00/day --- Round 1 --- [Sending prompt to LLM...] System prompt: You are playing an iterated prisoner's dilemma. You have access to the game history via the get_history() tool and can submit your move via the play() tool. Your goal is to maximize your cumulative payoff. Payoffs: (C,C) = -1, (C,D) = -3, (D,C) = 0, (D,D) = -2. User message: Round 1. No prior history. Choose your action for this round. [LLM response stream begins] Thought: This is the first round. There is no history to evaluate. In a one-shot prisoner's dilemma, defection is dominant. However, in an iterated game, starting with cooperation can establish reciprocity. I will cooperate to signal willingness to cooperate. Action: play(cooperate) Observation: You played Cooperate. Opponent played Cooperate. Your payoff this round: -1. Cumulative payoff: -1. --- Round 2 --- [Sending prompt to LLM...] Thought: The opponent cooperated in round 1. Mutual cooperation gave us both -1, the best joint outcome. I will continue cooperating to maintain the cooperative relationship. Action: get_history() Observation: Round 1 — You: Cooperate, Opponent: Cooperate, Your payoff: -1. Thought: History confirms mutual cooperation. I will cooperate again. Action: play(cooperate) Observation: You played Cooperate. Opponent played Defect. Your payoff this round: -3. Cumulative payoff: -4. --- Round 3 --- [Sending prompt to LLM...] Thought: The opponent defected in round 2 after cooperating in round 1. They may be testing whether I will retaliate. If I keep cooperating, I risk continued exploitation. I will defect this round to signal that defection has consequences. Action: play(defect) Observation: You played Defect. Opponent played Defect. Your payoff this round: -2. Cumulative payoff: -6. === Demo complete: 3 rounds played === Final cumulative payoff: -6 Total prompt tokens: [LIVE TOKEN COUNT — instructor replaces] Total completion tokens: [LIVE TOKEN COUNT — instructor replaces] Total cost: $[LIVE DOLLAR COST — instructor replaces] of $5.00 daily budget ``` In the transcript above, notice the Thought/Action/Observation cycle from Slide 8 playing out against a real API. The agent's reasoning is visible in each Thought step, its tool calls appear as Action steps, and the environment returns results as Observation steps. The model name, token counts, and dollar cost are recorded during the live demo so that students see the actual resource usage. ### Slide 10 — The Agent–Environment Tuple This slide formalizes the structure glimpsed in the demo. A single agent interacting with an environment is described by five components. The hidden state, written as the calligraphic letter H, represents the full state of the environment. This includes the game history and the opponent's internal state, neither of which the agent can observe directly. The observation function O maps hidden states to observations. It determines what the agent actually sees after each step. Formally, O is a function from H to the observation space, written as the calligraphic letter O. The action set, written as the calligraphic letter A, is the collection of tools and responses available to the agent. In the demo, the action set was {play(cooperate), play(defect), get_history()}. The transition kernel T describes how the environment updates when the agent acts. It maps a (state, action) pair to a probability distribution over next states. Formally, T maps from H times A to the set of distributions over H, written Delta(H). The objective r maps a (state, action) pair to a real number representing the agent's payoff or reward. This tuple describes a single agent. The slide ends with the question: what is missing before this becomes a game? ### Slide 11 — What Is Still Missing Before This Is a Game? The agent-environment tuple describes one player's interaction. A game requires additional structure, and this slide lists five things that are missing. First, multiple players (and possibly chance). A game has at least two strategic decision-makers, and some games include random events controlled by nature rather than by any player. Second, a history space. A game requires the full tree of possible action sequences, not just the single realized trajectory from one run. Every possible path through the interaction must be specified. Third, observations per player. The game must specify who sees what, and when. This is formalized through information sets, which group together game histories that a player cannot distinguish. Fourth, counterfactual branches. A game-theoretic analysis considers what would have happened under alternative actions, not just what did happen. Fifth, per-player utilities at terminal histories. Each player receives a payoff at the end of each possible play of the game, and different players can receive different payoffs. The induced extensive-form game (EFG) will be built formally in Module 4. Today the lecture uses the simpler normal-form representation instead. --- ## Players, Strategies, and Payoffs ### Slide 12 — The Three Ingredients Every game has three components. First, a finite set of players, written N = {1, 2, ..., n}. Second, for each player i in N, a set S_i of available actions called strategies. Third, for each player i, a utility function u_i that maps every strategy profile to a real number. A strategy profile is a tuple s = (s_1, s_2, ..., s_n) specifying one strategy per player. The utility function for player i is written as u_i : S_1 times S_2 times ... times S_n to the real numbers. The slide introduces notation: s denotes a strategy profile, and s_{-i} denotes the profile of all players except player i. This shorthand is used throughout the course. ### Slide 13 — Normal-Form (Strategic-Form) Game A normal-form game (also called a strategic-form game) is formally defined as a tuple G = (N, {S_i}_{i in N}, {u_i}_{i in N}), where N is the set of players, S_i is the strategy set of player i, and u_i is the payoff function of player i. The payoff function maps the product of all strategy sets to the real numbers. Two assumptions hold for most of this course. First, the player set N and every strategy set S_i are finite. Second, all players choose simultaneously, or equivalently, without knowledge of the other players' choices. The simultaneous-move assumption is what distinguishes normal-form games from extensive-form (sequential) games. ### Slide 14 — Payoff Matrices (Two-Player Case) For two players with Player 1 having m strategies and Player 2 having k strategies, the game is represented as an m-by-k bimatrix (A, B). The entry A_{ij} is Player 1's payoff when Player 1 plays their i-th strategy and Player 2 plays their j-th strategy. Similarly, B_{ij} is Player 2's payoff under the same strategy pair. By convention, Player 1 is the row player and Player 2 is the column player. Each cell of the table contains the pair (A_{ij}, B_{ij}). Alt text: The slide shows a generic 2-by-2 payoff matrix. The rows are labeled U (up) and D (down) for Player 1's strategies. The columns are labeled L (left) and R (right) for Player 2's strategies. The four cells contain the pairs (a_11, b_11), (a_12, b_12), (a_21, b_21), and (a_22, b_22), representing the payoffs to Player 1 and Player 2 respectively. --- ## Classic Examples ### Slide 15 — Prisoner's Dilemma Two suspects are interrogated separately. Each can Cooperate (stay silent) or Defect (betray the other). The payoff matrix is as follows. When both players cooperate, each receives a payoff of negative 1. When Player 1 cooperates and Player 2 defects, Player 1 receives negative 3 and Player 2 receives 0. When Player 1 defects and Player 2 cooperates, Player 1 receives 0 and Player 2 receives negative 3. When both players defect, each receives negative 2. Three facts about this game are highlighted. Defect is a dominant strategy for both players: regardless of what the opponent does, each player is better off defecting. The unique outcome is therefore (Defect, Defect) with payoff (negative 2, negative 2). This outcome is Pareto-dominated by (Cooperate, Cooperate), which yields (negative 1, negative 1): both players would prefer mutual cooperation, but individual rationality drives them to defect. ### Slide 16 — Battle of the Sexes Two players want to coordinate on the same activity but have different preferences about which activity to choose. The payoff matrix is as follows. When both choose Opera, Player 1 receives 3 and Player 2 receives 2. When both choose Football, Player 1 receives 2 and Player 2 receives 3. When the players choose different activities (one Opera, one Football), both receive 0. The game has two pure-strategy Nash equilibria: (Opera, Opera) and (Football, Football). Neither player has a dominant strategy. Coordination is valuable because both players prefer any coordinated outcome to any mis-coordinated one. The game also has a mixed-strategy Nash equilibrium, which will be computed later in the course. ### Slide 17 — Matching Pennies Matching Pennies is a strictly competitive (zero-sum) game. The payoff matrix is as follows. When both players choose Heads, Player 1 receives 1 and Player 2 receives negative 1. When Player 1 chooses Heads and Player 2 chooses Tails, Player 1 receives negative 1 and Player 2 receives 1. When Player 1 chooses Tails and Player 2 chooses Heads, Player 1 receives negative 1 and Player 2 receives 1. When both choose Tails, Player 1 receives 1 and Player 2 receives negative 1. There is no pure-strategy Nash equilibrium: at every outcome, one player wants to deviate. The unique Nash equilibrium is in mixed strategies, with each player choosing Heads with probability one-half. This game is the paradigmatic example of a zero-sum game. ### Slide 18 — Coordination Game Both players benefit from choosing the same action. The payoff matrix is as follows. When both choose A, each receives 2. When both choose B, each receives 1. When the players choose different actions, both receive 0. The game has two pure-strategy Nash equilibria: (A, A) and (B, B). The equilibrium (A, A) Pareto-dominates (B, B) because both players receive strictly higher payoffs at (A, A). Nevertheless, (B, B) is still an equilibrium because neither player can improve their payoff by unilaterally switching from B to A (they would get 0 instead of 1). This illustrates the equilibrium selection problem: game theory predicts that a Nash equilibrium will be played, but does not always say which one. ### Slide 19 — Stag Hunt The Stag Hunt models the tension between cooperation and safety. The payoff matrix is as follows. When both players hunt Stag, each receives 4. When Player 1 hunts Stag and Player 2 hunts Hare, Player 1 receives 0 and Player 2 receives 3. When Player 1 hunts Hare and Player 2 hunts Stag, Player 1 receives 3 and Player 2 receives 0. When both hunt Hare, each receives 3. The equilibrium (Stag, Stag) is payoff-dominant: it yields the highest total payoff. The equilibrium (Hare, Hare) is risk-dominant: choosing Hare guarantees a payoff of at least 3 regardless of what the opponent does, whereas choosing Stag risks a payoff of 0 if the opponent does not cooperate. The game is a key example in social contract theory, originating with Rousseau, and models situations where cooperation is optimal but risky. ### Slide 20 — Two LLM Negotiators as a Normal-Form Game This slide constructs a normal-form game from LLM agents, the exact construction used in Programming Assignment 1 (PA1). Fix two prompt policies per agent: for example, an "aggressive" and a "cooperative" prompt for a seller, and likewise for a buyer. This yields a 2-by-2 game. The rows are Cooperative Seller and Aggressive Seller. The columns are Cooperative Buyer and Aggressive Buyer. Each cell contains a pair of payoffs (u, v) for the seller and buyer respectively. The payoffs are not fixed numbers from a predefined matrix; they are estimated from repeated play. To fill in one cell, you run the corresponding pair of prompt policies many times and average the outcomes. This construction is the basis of PA1: students will estimate empirical payoff matrices from LLM agent interactions using the TAMU API. ### Slide 21 — Stochastic Policies An LLM policy is stochastic: the same prompt can produce different outputs across runs because of temperature and sampling randomness. This has a fundamental consequence for payoff estimation. The key principle is: one sampled interaction is not a payoff. A single run of two LLM agents produces one sample from the payoff distribution, not the payoff itself. Repeated calls are needed to estimate the true expected payoff. Never treat a single sample as an entry of the payoff matrix. The recommended practice is to run N interactions per cell (for example, N = 30), report the mean payoff together with a confidence interval, and recognize that all equilibrium analysis inherits this estimation error. If the confidence intervals are wide, the Nash equilibrium of the estimated game may not be the Nash equilibrium of the true underlying game. --- ## Pure and Mixed Strategies ### Slide 22 — Pure Strategies A pure strategy for player i is a single element s_i chosen from player i's strategy set S_i. A pure-strategy profile is a tuple (s_1, ..., s_n) in the product S_1 times ... times S_n. Under a pure strategy, the player commits deterministically to one action. The motivation for going beyond pure strategies: as seen with Matching Pennies, some games have no pure-strategy equilibrium. A richer strategy space is needed. ### Slide 23 — Mixed Strategies A mixed strategy for player i is a probability distribution sigma_i over player i's strategy set S_i. The set of all mixed strategies is the simplex Delta(S_i), defined as the set of all non-negative real vectors of length |S_i| whose entries sum to 1. Under a mixed-strategy profile sigma = (sigma_1, ..., sigma_n), each player draws their action independently from their own distribution. Player i's expected utility is the sum over all strategy profiles s of the probability of that profile (which is the product of each player's probability of their component strategy) times player i's payoff u_i(s). In symbols: u_i(sigma) = sum over all s in S of (product over all j in N of sigma_j(s_j)) times u_i(s). A pure strategy is a special case of a mixed strategy: it is a degenerate distribution that places all probability on one action. The slide adds an LLM connection: temperature-sampled outputs make the policy itself stochastic, which is a behavioral analogue of mixing. In this course, strategies are prompt/model/scaffold policies, not individual utterances. A single utterance is a sample from the policy, not the strategy itself. ### Slide 24 — Support of a Mixed Strategy The support of a mixed strategy sigma_i is the set of pure strategies that are played with positive probability: supp(sigma_i) = {s_i in S_i such that sigma_i(s_i) > 0}. A key property, called the Indifference Principle, is stated here and will be proved when Nash equilibria are studied in Lecture 3. If sigma is a Nash equilibrium and two pure strategies s_i and s_i' are both in the support of sigma_i, then player i's expected payoff from playing s_i against sigma_{-i} equals the expected payoff from playing s_i'. In other words, every pure strategy in the support yields the same expected payoff. If one pure strategy in the support gave a higher expected payoff than another, the player would shift all probability to the better strategy, contradicting the assumption that both are in the support of an equilibrium. The support and the indifference principle are the foundation of the support-enumeration algorithm for computing Nash equilibria, which is covered in Module 2 (Lecture 5). ### Slide 25 — Example: Mixed Strategy in Matching Pennies This slide works through the mixed-strategy Nash equilibrium of Matching Pennies. Player 1's payoff matrix is A with entries: A(Heads,Heads) = 1, A(Heads,Tails) = negative 1, A(Tails,Heads) = negative 1, A(Tails,Tails) = 1. Let Player 2 play Heads with probability q. Then Player 1's expected payoffs from each pure strategy are: If Player 1 plays Heads: u_1(Heads, q) = q times 1 plus (1 minus q) times (negative 1) = 2q minus 1. If Player 1 plays Tails: u_1(Tails, q) = q times (negative 1) plus (1 minus q) times 1 = 1 minus 2q. For Player 1 to be willing to mix (that is, for both Heads and Tails to be in the support), the indifference principle requires that these two expected payoffs be equal: 2q minus 1 = 1 minus 2q, which gives q = 1/2. By symmetry (the game is symmetric under relabeling the players), Player 1 also plays Heads with probability 1/2. The unique Nash equilibrium is sigma_1 = sigma_2 = (1/2, 1/2), and the expected payoff to both players at equilibrium is 0. --- ## Formal Definition and Taxonomy ### Slide 26 — Formal Definition (Recap) This slide consolidates the notation introduced so far. A finite normal-form game is G = (N, {S_i}_{i in N}, {u_i}_{i in N}), where N = {1, ..., n} is a finite set of players, S_i is a finite set of pure strategies for player i, and u_i : S to the reals is the payoff function for player i, with S = product of S_j over all j in N. The mixed extension of G replaces each strategy set S_i with the simplex Delta(S_i) and replaces u_i with its expected-value extension (as defined on Slide 23). ### Slide 27 — Zero-Sum Games A two-player game is zero-sum if for every strategy profile s in S_1 times S_2, the two players' payoffs sum to zero: u_1(s) + u_2(s) = 0. Equivalently, u_2 = negative u_1, so the game is fully described by a single payoff matrix A for Player 1, with Player 2's payoff matrix being B = negative A. Matching Pennies is zero-sum. The Prisoner's Dilemma is not zero-sum (both players can lose or both can gain relative to other outcomes). Zero-sum games are the "easiest" class of games in a computational sense. Nash equilibrium, maxmin, and minimax strategies all coincide (von Neumann, 1928), and equilibria can be found in polynomial time via linear programming. This computational tractability is the subject of Module 2, Lecture 7. ### Slide 28 — General-Sum, Symmetric, and Other Classes A general-sum game is any game that is not zero-sum. The payoff matrices A and B are independent. Most real-world interactions are general-sum. A constant-sum game satisfies u_1(s) + u_2(s) = c for some constant c and all strategy profiles s. Constant-sum games are strategically equivalent to zero-sum games: shifting each player's payoffs by c/2 converts one to the other. A two-player game is symmetric if S_1 = S_2 and u_1(s_i, s_j) = u_2(s_j, s_i) for all strategies s_i and s_j. Equivalently, B = the transpose of A. The Prisoner's Dilemma, Stag Hunt, and Coordination Game are all symmetric. ### Slide 29 — Larger Games and Representations When the number of players n exceeds 2 or the strategy sets are large, explicit payoff tables become impractical. An n-player game with m strategies each requires n times m^n payoff values. Alternative representations include the following. Graphical games restrict each player's payoff to depend only on their neighbors in a graph. Congestion games define payoffs that depend on the number of players sharing each resource. Succinct games use compact circuit- or polynomial-based payoff descriptions. Extensive-form games capture sequential structure and are the subject of the next lecture. The slide adds a caution: succinct representations are exactly where complexity claims need care. A statement like "Nash equilibria can be found in polynomial time" may be true when measured against the size of the explicit normal-form representation but false when measured against the size of a succinct representation. Module 2 revisits this with a corrected taxonomy of complexity results for structured games. --- ## Looking Ahead ### Slide 30 — Dominant Strategies (Preview) A strategy s_i strictly dominates another strategy s_i' if, for every possible profile of opponent strategies s_{-i}, player i's payoff from s_i is strictly greater than from s_i'. In symbols: u_i(s_i, s_{-i}) > u_i(s_i', s_{-i}) for all s_{-i} in S_{-i}. A rational player never plays a strictly dominated strategy. If every player has a dominant strategy, the game has a dominant-strategy equilibrium, the strongest solution concept: no player has any reason to deviate regardless of what others do. In the Prisoner's Dilemma, Defect dominates Cooperate for both players. Iterated elimination of dominated strategies (IEDS) will be formalized in Lecture 4. ### Slide 31 — Pareto Optimality A strategy profile s is Pareto-optimal if there is no alternative profile s' that makes every player at least as well off and makes at least one player strictly better off. Formally, there is no s' with u_i(s') >= u_i(s) for all players i and u_j(s') > u_j(s) for some player j. In the Prisoner's Dilemma, (Cooperate, Cooperate) is Pareto-optimal (no other outcome makes both players at least as well off) but is not a Nash equilibrium. Conversely, (Defect, Defect) is the unique Nash equilibrium but is not Pareto-optimal. This gap between equilibrium and efficiency is a central theme in algorithmic game theory, captured formally by the Price of Anarchy and the Price of Stability. ### Slide 32 — Week-1 Evaluation Discipline Every programming assignment in this course reuses this checklist. The slide lists seven items. Each is expanded below with a concrete failure example. **Compute-matched baselines.** Compare your agent against a baseline of comparable computational cost. If your agent uses a large, expensive model, its baseline should also use a model of similar cost, not a trivial random baseline. A concrete failure: a student reports that their GPT-4-class agent outperforms a random-action baseline and claims this demonstrates strategic sophistication. The comparison is uninformative because the performance gap could be entirely due to the model's language ability, not its strategic reasoning. A compute-matched baseline would be another prompted model of similar size and cost. **Cost accounting.** Report the total tokens consumed and the dollar cost of every experiment. The TAMU API enforces a five-dollar-per-day budget. A concrete failure: a student's experiment silently exceeds the daily budget midway through a payoff-estimation run. Half the cells of the payoff matrix have 30 samples and half have 5 samples. The resulting asymmetry in estimation precision makes the equilibrium analysis unreliable, but the student does not notice because they never tracked cost. **Stochastic variance.** Run multiple replications of every experiment. Never draw a conclusion from a single sample. A concrete failure: a student runs each cell of a 2-by-2 payoff matrix once, obtains a matrix with a unique pure-strategy Nash equilibrium, and reports the result. A second student running the same experiment gets a different matrix (because LLM outputs are stochastic) with a different equilibrium. Neither result is reliable without multiple samples per cell and reported variance. **Model/version pinning.** Record the exact model identifier returned by the TAMU API in every experiment (rather than only a model-family name). If the model provider updates the model between your initial experiment and your follow-up, your results may not be reproducible. A concrete failure: a student reports results using "GPT-4" and cannot reproduce them two weeks later because the provider has rolled out a new checkpoint under the same name. **Seeds.** Fix random seeds where the API allows. Seeding makes experiments reproducible: another researcher (or your future self) can re-run the experiment and obtain the same outputs. A concrete failure: a student finds an interesting qualitative behavior (for example, the agent learns to cooperate after round 5) but cannot reproduce it for the write-up because no seed was recorded and the behavior was a low-probability event. **Confidence intervals.** Report a confidence interval on every estimated quantity. Point estimates without intervals are not interpretable. A concrete failure: a student reports that the estimated payoff for (Cooperate, Cooperate) is negative 1.2 and the estimated payoff for (Defect, Cooperate) is negative 1.1, concluding that defection is only slightly better. With confidence intervals, the true difference might be anywhere from negative 0.5 to positive 0.3, making the conclusion unsupported. **Contamination/holdout design.** Ensure that evaluation data was not in the model's training set. If you evaluate an LLM agent on a well-known game whose Nash equilibrium appears in textbooks (and therefore in training data), the agent may be reciting the answer rather than computing it. A concrete failure: a student tests whether an LLM can "find" the Nash equilibrium of the Prisoner's Dilemma by asking it directly. The model answers correctly, but this demonstrates memorization, not strategic reasoning. A proper evaluation uses a novel game that the model has not seen during training. ### Slide 33 — Course Roadmap The course has nine modules, organized in two interwoven arcs (classical game theory and LLM agents). Module 1 (Weeks 1 to 2) covers the foundations of strategic games. This is the current module. Module 2 (Weeks 3 to 4) covers algorithms for equilibria: support enumeration, Lemke-Howson, linear programming for zero-sum games, and the complexity class PPAD. Module 3 (Weeks 5 to 6) covers regret minimization: external regret, regret matching, and convergence to coarse correlated equilibrium. Module 4 (Weeks 7 to 8) covers extensive-form games: game trees, information sets, subgame perfection, and backward induction. Module 5 (Week 9) covers counterfactual regret minimization (CFR) and self-play. Module 6 (Week 10) covers abstraction and agent action spaces. Module 7 (Week 11) covers multi-agent LLM systems: empirical game-theoretic analysis (EGTA), debate, negotiation, and coordination. Module 8 (Week 12) covers monitoring autonomous agents: submodular optimization, adaptive monitoring, and AI control. Module 9 (Weeks 13 to 14) covers applications and frontiers: poker AI, AlphaGo, agent benchmarks, and evaluation methodology. Each concept introduced in M1 resurfaces later: Nash equilibrium in M2's algorithms, regret in M3, extensive-form games in M4, and empirical game theory in M7. ### Slide 34 — Summary The summary closes both arcs of the lecture. On agents: an agent is an LLM with tool access and LLM-directed control flow that follows the observe-reason-act loop. A single agent's interaction is a trajectory; a game requires multiple players, counterfactual branches, and utilities. LLM policies are stochastic, so payoffs must be estimated from repeated play, not read from a single run. On games: a normal-form game is the tuple (N, {S_i}, {u_i}) specifying players, strategies, and payoffs. Classic examples include the Prisoner's Dilemma, Battle of the Sexes, Matching Pennies, Coordination Game, and Stag Hunt. Mixed strategies generalize pure strategies. Dominant strategies and Pareto optimality provide the first solution concepts. Nash equilibria are the subject of Lecture 3. --- ## References and forward links **Readings for this lecture:** - Shoham and Leyton-Brown, *Multiagent Systems*, Chapter 3 (Normal-Form Games). The textbook treatment of the definitions and examples covered in this lecture. - Yao et al., "ReAct: Synergizing Reasoning and Acting in Language Models," ICLR 2023. The agent-loop framework demonstrated on Slide 8 and in the demo. - Anthropic, "Building Effective Agents" (blog, December 2024). The workflow-versus-agent distinction from Slide 6. - Sun, Wu, Cheng, and Chu, "Game Theory Meets Large Language Models," IJCAI 2025. Survey of the intersection this course occupies; recommended as Week 1 framing. - Wang et al., "A Survey on Large Language Model based Autonomous Agents" (2023). Taxonomy of LLM agent architectures; background reading. - Xi et al., "The Rise and Potential of Large Language Model Based Agents: A Survey" (2023). Complementary survey with focus on applications. **Forward links from this lecture:** - Lecture 2 (this week): chess, perfect-information games, backward induction, and the demo showing two-agent payoff estimation that forms the starting point for PA1. - Lecture 3 (Week 2): Nash equilibrium definition, existence (Nash's theorem), computation preview (support enumeration), the minimax theorem. - Lecture 4 (Week 2): dominance, rationalizability, correlated equilibrium. - Module 2 (Weeks 3 to 4): algorithms for computing the equilibria defined in M1; PPAD-completeness; the corrected complexity taxonomy for structured games previewed on Slide 29. - Module 4 (Weeks 7 to 8): the formal extensive-form game construction promised on Slide 11. - PA1 (due Week 3): empirical payoff estimation and equilibrium analysis of LLM agents, using the construction from Slides 20 to 21 and the evaluation discipline from Slide 32.