Agents Multi Agent Systems And Rl
Multi-Agent Systems & Game Theory
Every architecture in Chapter 1 assumed a single agent (possibly reacting to an environment, but not to other decision-making agents). Module 2, Chapter 5 brief
Jr Codex AI Notes
Level: Intermediate–Advanced Prerequisites: Chapter 1 Time to complete: ~25 minutes
Table of Contents
- When One Agent Isn't Enough
- Types of Multi-Agent Interaction
- Game Theory Basics — Payoff Matrices
- Nash Equilibrium
- The Prisoner's Dilemma
- Cooperative Multi-Agent Systems
- Connecting Back to Adversarial Search
- Summary & Next Steps
1. When One Agent Isn't Enough
Every architecture in Chapter 1 assumed a single agent (possibly reacting to an environment, but not to other decision-making agents). Module 2, Chapter 5 briefly introduced adversarial search for two-player zero-sum games — this chapter generalizes that idea to multi-agent systems more broadly, including cooperation, non-zero-sum competition, and more than two agents.
Module 2's Adversarial Search This Chapter's Multi-Agent Systems
───────────────────────────── ─────────────────────────────
Exactly TWO agents Any NUMBER of agents
Strictly ZERO-SUM (one's gain NOT necessarily zero-sum —
is exactly the other's loss) agents might BOTH benefit,
or BOTH lose, depending on
Adversarial ONLY joint actions
Cooperative, competitive,
OR a mix of both
───────────────────────────── ─────────────────────────────
2. Types of Multi-Agent Interaction
Interaction Types
─────────────────────────────────────────
Cooperative: agents share a common goal, actively
help each other (e.g. search-and-rescue
robot teams)
Competitive: agents have opposing goals (e.g.
Module 2's chess — but now generalized
beyond strict zero-sum)
Mixed (Coopetitive): agents both cooperate AND compete,
depending on context (e.g. companies
in a market — sometimes forming
alliances, sometimes competing directly)
─────────────────────────────────────────
class MultiAgentEnvironment:
"""A minimal simulation harness for multiple agents acting in shared rounds."""
def __init__(self, agents):
self.agents = agents
def run_round(self, shared_state):
actions = {}
for agent in self.agents:
actions[agent.name] = agent.decide(shared_state)
return actions3. Game Theory Basics — Payoff Matrices
Game theory formalizes multi-agent decision-making using a payoff matrix — for each combination of actions across all players, it specifies the payoff (utility, Module 4, Chapter 5) each player receives.
# A simple two-player game: each can choose "Cooperate" or "Defect"
# payoff_matrix[my_action][their_action] = (my_payoff, their_payoff)
payoff_matrix = {
("Cooperate", "Cooperate"): (3, 3),
("Cooperate", "Defect"): (0, 5),
("Defect", "Cooperate"): (5, 0),
("Defect", "Defect"): (1, 1),
}
def get_payoffs(action1, action2):
return payoff_matrix[(action1, action2)]
print(get_payoffs("Cooperate", "Defect")) # (0, 5) — player 1 gets 0, player 2 gets 5Reading a Payoff Matrix
─────────────────────────────────────────
Player 2: Cooperate Player 2: Defect
Player 1: (3, 3) (0, 5)
Cooperate
Player 1: (5, 0) (1, 1)
Defect
(Player 1's payoff, Player 2's payoff)
─────────────────────────────────────────
4. Nash Equilibrium
A Nash equilibrium is a set of strategies (one per player) where no single player can improve their own payoff by unilaterally changing their strategy, assuming everyone else's strategy stays fixed.
def is_nash_equilibrium(payoff_matrix, action1, action2, all_actions):
"""Check if (action1, action2) is a Nash equilibrium for a 2-player game."""
current_payoff1, current_payoff2 = payoff_matrix[(action1, action2)]
# Would Player 1 benefit from unilaterally switching?
for alt_action in all_actions:
if alt_action != action1:
alt_payoff1, _ = payoff_matrix[(alt_action, action2)]
if alt_payoff1 > current_payoff1:
return False # Player 1 has an incentive to deviate
# Would Player 2 benefit from unilaterally switching?
for alt_action in all_actions:
if alt_action != action2:
_, alt_payoff2 = payoff_matrix[(action1, alt_action)]
if alt_payoff2 > current_payoff2:
return False # Player 2 has an incentive to deviate
return True
actions = ["Cooperate", "Defect"]
for a1 in actions:
for a2 in actions:
if is_nash_equilibrium(payoff_matrix, a1, a2, actions):
print(f"Nash equilibrium found: ({a1}, {a2})")Why (Defect, Defect) Is the Nash Equilibrium Here
─────────────────────────────────────────
At (Defect, Defect), payoffs are (1, 1).
Would Player 1 benefit from switching to Cooperate alone?
→ (Cooperate, Defect) gives Player 1 only 0 — WORSE. No incentive to switch.
Would Player 2 benefit from switching to Cooperate alone?
→ (Defect, Cooperate) gives Player 2 only 0 — WORSE. No incentive to switch.
NEITHER player can unilaterally improve — this IS a
Nash equilibrium, even though (Cooperate, Cooperate) would
have given BOTH players a higher payoff (3, 3)!
─────────────────────────────────────────
This apparent paradox — a Nash equilibrium that's worse for everyone than an alternative — is exactly the Prisoner's Dilemma, Section 5.
5. The Prisoner's Dilemma
The payoff matrix used throughout this chapter is the classic Prisoner's Dilemma — the single most famous example in game theory, illustrating why individually rational decisions can produce a collectively worse outcome.
The Classic Story
─────────────────────────────────────────
Two suspects are interrogated separately. Each can betray
the other (Defect) or stay silent (Cooperate with each other,
against the police). Regardless of what the OTHER suspect
does, betraying always gives a BETTER individual outcome —
but if BOTH betray, both suspects do WORSE than if both had
stayed silent.
─────────────────────────────────────────
# Verifying that Defect DOMINATES Cooperate for Player 1, REGARDLESS of Player 2's choice
for player2_action in ["Cooperate", "Defect"]:
payoff_if_cooperate, _ = get_payoffs("Cooperate", player2_action)
payoff_if_defect, _ = get_payoffs("Defect", player2_action)
print(f"If Player 2 plays {player2_action}: "
f"Cooperate gives {payoff_if_cooperate}, Defect gives {payoff_if_defect}")
# If Player 2 plays Cooperate: Cooperate gives 3, Defect gives 5 ← Defect is better
# If Player 2 plays Defect: Cooperate gives 0, Defect gives 1 ← Defect is STILL betterWhy This Matters Beyond a Toy Example
─────────────────────────────────────────
The Prisoner's Dilemma structure appears constantly in
real multi-agent AI settings:
- Autonomous vehicles deciding whether to yield or push
through an intersection
- Competing bidding agents in an ad auction
- Distributed systems deciding whether to share resources
or hoard them
Understanding WHY individually rational agents can produce
a collectively worse outcome is essential for designing
multi-agent systems that AVOID this trap — often through
repeated interaction (reputation, tit-for-tat strategies) or
explicit cooperation mechanisms (Section 6).
─────────────────────────────────────────
6. Cooperative Multi-Agent Systems
When agents share a common goal, the design challenge shifts from finding equilibria to effective coordination.
class CooperativeAgent:
"""A simplified agent in a search-and-rescue team, avoiding duplicated effort."""
def __init__(self, name):
self.name = name
def decide(self, shared_state, other_agents_claimed_areas):
available_areas = [a for a in shared_state["areas"] if a not in other_agents_claimed_areas]
if not available_areas:
return None
return min(available_areas, key=lambda a: shared_state["distance"][self.name][a])
def coordinate_search(agents, shared_state):
"""A simple greedy coordination protocol — agents claim areas one at a time."""
claimed = set()
assignments = {}
for agent in agents:
area = agent.decide(shared_state, claimed)
if area:
claimed.add(area)
assignments[agent.name] = area
return assignments
agents = [CooperativeAgent("RobotA"), CooperativeAgent("RobotB")]
shared_state = {
"areas": ["North", "South", "East"],
"distance": {
"RobotA": {"North": 5, "South": 2, "East": 8},
"RobotB": {"North": 3, "South": 6, "East": 1},
},
}
result = coordinate_search(agents, shared_state)
print(result) # e.g. {'RobotA': 'South', 'RobotB': 'East'} — avoiding duplicated coverageCoordination mechanisms range from this simple greedy claiming, to formal auction-based task allocation, to fully centralized planning (which reduces the multi-agent problem back to Module 3's single-agent planning, just with a bigger combined action space) — the right approach depends on whether agents can communicate, how much they trust each other, and how time-critical the coordination is.
7. Connecting Back to Adversarial Search
This Chapter vs Module 2, Chapter 5
─────────────────────────────────────────
Module 2's minimax: exactly TWO players, STRICTLY
zero-sum — one payoff number
fully determines both players'
outcomes (my gain = their loss)
THIS chapter's game theory: ANY number of players, payoffs
can be independent for each
player — allows outcomes where
BOTH players win, BOTH lose, or
anything in between
Zero-sum games are a SPECIAL CASE of the general game theory
framework covered here — and minimax (Module 2) is the
correct SOLUTION CONCEPT specifically for that special case,
while Nash equilibrium is the more general solution concept
covering zero-sum AND non-zero-sum games alike.
─────────────────────────────────────────
This connection is worth internalizing: minimax isn't a different technique from game theory, it's game theory's answer to one specific, important special case (adversarial, zero-sum, two-player) that Module 2 covered in depth precisely because it's so common in classic games (chess, Go, tic-tac-toe).
8. Summary & Next Steps
Key Takeaways
- Multi-agent systems generalize Module 2's two-player, zero-sum adversarial search to any number of agents, with cooperative, competitive, or mixed relationships.
- A payoff matrix specifies each player's outcome for every combination of actions; a Nash equilibrium is a set of strategies where no player benefits from unilaterally deviating.
- The Prisoner's Dilemma demonstrates that individually rational choices (each player's dominant strategy) can lead to a Nash equilibrium that's worse for everyone than an alternative, non-equilibrium outcome.
- Cooperative multi-agent systems shift the design challenge from finding equilibria to effective coordination — ranging from simple greedy claiming to formal auction-based allocation.
- Minimax (Module 2, Chapter 5) is a special case of this chapter's more general game theory framework, specifically for two-player, strictly zero-sum games.
Concept Check
- Why is (Defect, Defect) a Nash equilibrium in the Prisoner's Dilemma, even though (Cooperate, Cooperate) gives both players a better payoff?
- What's the key structural difference between the games Module 2's minimax handles and the more general games this chapter covers?
- Why might real-world multi-agent AI systems (like competing bidding agents) run into a Prisoner's Dilemma-style trap?
Next Chapter
→ Chapter 3: Introduction to Reinforcement Learning
Jr Codex — 1-on-1 Personalized Coaching | Back to Module Index