UPI Study › Courses › Introduction to Artificial Intelligence › Free lessons › Lesson 4.5 Free with a free account
Strategic Reasoning: Game Theory in Intelligent Systems
Introduction to Artificial Intelligence · Chapter 4: Search, Heuristics, and Game StrategySection 4.5 · lesson 27 of 6912 min · free with a free account
Free preview
Create a free account to keep watching
It takes a minute and costs nothing. Your free account unlocks all of Chapter 1 and 3 more lessons of Introduction to Artificial Intelligence.
Lesson complete
Earn the 3 college credits for Introduction to Artificial Intelligence
Enrolling adds a quiz after each lesson, the graded work and the official transcript. Recommended for credit by NCCRS.
Next lesson: Climbing Toward Solutions: Local Search Methods →← Heuristic Approaches: Guided Problem SolvingNext lesson: Climbing Toward Solutions: Local Search Methods →
In this lesson
Normal-form games, Nash equilibria, and mixed strategies for interacting AI agents.
- Describe a normal-form game by its players, strategies, and payoffs
- Identify dominant strategies and Nash equilibria in payoff tables
- Contrast zero-sum and non-zero-sum games using the prisoner's dilemma
- Calculate a mixed strategy that leaves an opponent indifferent
Free study notes
Get this lesson's notes by email
The key points and 4 practice questions with answers, in your inbox. One email, free.
One email. Unsubscribe in one click.
Transcript
Everything said in the video, section by section (1,798 words). Read along, or search it.
Opening Question
When Outcomes Depend on Others
Much of AI imagines one agent, acting in a world that doesn't react. Real settings are rarely that quiet. A self-driving car shares the road with other drivers. A pricing program competes with rival programs. A game-playing system faces an opponent who's also trying to win. In each case, the best choice for one agent depends on what the others choose. So how can an agent choose well, when the outcome isn't up to it alone?
Definition
Mathematics of Strategic Interaction
Game theory is the mathematics of that kind of strategic interaction. It describes who chooses what, what each outcome is worth to each player, and which combinations of choices are stable. Here, the players choose at the same moment. Games played in turns, like chess, are handled by searching game trees, with minimax and alpha-beta.
Key Terms
Players, Strategies, Payoffs, and Normal Form
A game has three ingredients. The players are the decision makers. Each player has a set of strategies: the choices available to them. And a payoff is a number that says how good an outcome is for a player, such as profit, points, or time saved. A game in normal form lists every combination of strategies in a table, with one payoff for each player in each cell. Nobody sees the other's choice in advance.
Running Example
Two Companies Setting Prices
Two companies, A and B, each set a High or a Low price for a similar product. Their profits depend on both choices. A's choice picks the row, and B's picks the column. In each cell, A's profit comes first, in blue, then B's, in green. Both High: 5 each. Both Low: 3 each. If one goes Low while the other stays High, the Low pricer earns 8, and the High pricer gets 1.
Dominant Strategy
Low Wins Whatever the Rival Does
A dominant strategy is a choice that's best for a player, whatever the other does. Look at Company A. If B sets High, A earns 8 with Low, and only 5 with High. If B sets Low, A earns 3 with Low, and only 1 with High. Low wins either way, so Low is A's dominant strategy. The game is symmetric, so Low is dominant for B, too. Neither needs to guess what the other will do.
Nash Equilibrium
No Gain From Changing Alone
A Nash equilibrium is a set of choices, one per player, where no player can do better by changing only their own choice. Each choice is a best response to the others. Nothing pushes anyone to move, so it's stable. It's named after the mathematician John Nash. To find one, mark the row player's best payoff in each column, and the column player's best payoff in each row. A cell with both payoffs marked is an equilibrium. Here, that's Low, Low, where each company earns 3.
Coordination Games
Two Cars on a Narrow Road
Equilibria aren't always unique. Two self-driving cars approach each other on a narrow road. Each must pass on its left, or on its right. If both choose the same side, they pass safely, and each scores 3. If they choose different sides, they block each other, and score 0. This coordination game has two equilibria: both pass on the left, or both on the right. Either is stable, but the table can't say which one the cars will reach. They need a shared convention, like drive on the right, or a way to communicate.
Game Types
Zero-Sum Versus Non-Zero-Sum
In a zero-sum game, the payoffs always add up to zero, or to a constant. One player's gain is exactly the other's loss, so their interests are completely opposed. Chess, penalty kicks, and a two-player poker match for money are close to zero-sum. In a non-zero-sum game, the total can change. Players can gain together, lose together, or mix shared and clashing interests. Pricing, negotiation, and merging traffic are like that. Cooperation can pay, because joint gains exist. Real situations lie along a spectrum, from pure conflict to pure cooperation.
Classic Example
The Prisoner's Dilemma
The most famous non-zero-sum game is the prisoner's dilemma. Two suspects are questioned in separate rooms. Each can stay quiet, or confess. If both stay quiet, each serves 1 year. If one confesses and the other stays quiet, the confessor goes free, and the other serves 10. If both confess, each serves 5. Here, fewer years are better. If B stays quiet, A does better by confessing: 0 years instead of 1. If B confesses, A again does better by confessing: 5 instead of 10. So confessing is dominant for both. Both confess, and each serves 5 years: the Nash equilibrium. Yet both would be better off staying quiet, with 1 year each. That's the dilemma: choices that are sensible for each player alone lead to an outcome that's worse for everyone. The pricing game has exactly the same shape. That's why price wars can leave competing firms with lower profits. For AI, agents that each maximize their own payoff can end up somewhere none of them would choose, unless rules, repeated meetings, or communication change the incentives. In repeated play, simple strategies often do well, such as: cooperate first, then copy the other player's last move.
Quick Check
Two Food Trucks Pick a Spot
Quick check, with a new game. Two food trucks, A and B, each pick a spot for the day: the Park, or the Station. Profits are in hundreds of dollars, A's first. Both at the Park: 3 and 2. A at the Park, B at the Station: 5 and 1. A at the Station, B at the Park: 2 and 4. Both at the Station: 4 and 6. Which cell is the Nash equilibrium? Pause, and decide. Park, Park. For A, the Park is dominant: 3 beats 2, and 5 beats 4. B has no dominant spot. But when A is at the Park, B's best reply is the Park, too: 2 beats 1. So in Park, Park, neither truck gains by moving alone. Station, Station is tempting, because it pays both more. But there, A would move to the Park, for 5 instead of 4. And in Park, Station, B would move to the Park.
Mixed Strategies
Matching Pennies Has No Pure Equilibrium
Some games have no equilibrium in single choices. In matching pennies, the Matcher wins 1 if the two coins match, and loses 1 if they differ. The Mismatcher gets the opposite. Whatever side the Matcher picks, the Mismatcher can beat it. Then the Matcher wants to switch, and so on, forever. No cell has both payoffs marked. The way out is to be unpredictable on purpose. A mixed strategy chooses at random, with set probabilities. Here, each player picks Heads or Tails, half the time each. Check it. Say the Mismatcher plays Heads half the time. Then the Matcher's Heads earns one half times plus 1, plus one half times minus 1, which is zero. The Matcher's Tails also earns zero. The Matcher is indifferent, so no change of probabilities helps, and the same holds for the Mismatcher. A mixed strategy isn't indecision. It's a calculated way to avoid being exploited. Rock-paper-scissors works the same way, with each option played a third of the time.
Worked Example
Patrolling the Valuable Gate Three Nights in Four
Mixed strategies needn't be fifty-fifty. A guard can patrol only one of two gates each night, and an intruder picks a gate to attack. Gate A holds something worth 3 to the intruder, and Gate B, something worth 1. If the guard is at the attacked gate, the intruder gains nothing. Otherwise, the intruder gains the gate's value. It's zero-sum, so the table lists only the intruder's gain. Let g be the chance that the guard patrols Gate A. Attacking A then pays 3 times 1 minus g, because the intruder succeeds only when the guard is at B. Attacking B pays 1 times g. The guard wants the intruder to gain the same either way. Otherwise, the intruder would just pick the better gate. So set 3 times 1 minus g equal to g. That gives 3 equals 4 g, so g is three quarters. On the graph, that's where the two lines cross. The intruder's expected gain is then three quarters, from either gate. So the guard patrols the valuable Gate A three nights out of four, and Gate B one night in four. A similar calculation for the intruder gives a one in four chance of attacking Gate A. That's the surprise: the more valuable gate is attacked less often, because it's guarded more often. And the guard never becomes predictable.
AI Applications
Multi-Agent Systems and Mechanism Design
A multi-agent system is one where several AI agents act in a shared setting, each with its own goals. Game theory helps predict what they'll do, and shape the rules so the equilibrium is a good one. Self-driving cars merging in traffic face a coordination game, and need shared conventions. Automated bidders in online ad auctions need rules that make bids stable, and hard to exploit. Patrol scheduling uses mixed strategies to stay unpredictable. Randomized patrol schedulers have been used for security at airports and ports. Expert-level poker programs approximate an equilibrium, so their bluffing can't be predicted. And many route-choosing agents on shared roads face dilemma-style incentives, which can cause congestion. Designing the rules of a game so that self-interested agents behave well, like the rules of an auction, is called mechanism design.
Limits and Mistakes
Equilibrium as a Guide, Not a Guarantee
Game theory has limits. Real payoffs are hard to state exactly, and large games can be too big to solve completely. An equilibrium is stable, but not always good, as the prisoner's dilemma shows. And real agents don't always behave perfectly, so treat equilibrium as a guide, not a guarantee. Watch for four common mistakes. Thinking an equilibrium is best for everyone. Expecting every game to have one in single choices. Confusing a mixed strategy with indecision. And treating every game as zero-sum, when cooperation can create gains.
Quick Check
Guarding Two Storerooms
Quick check. A night guard covers two storerooms, but can visit only one each night. Room A holds goods worth 4 to a thief, and Room B, goods worth 2. A thief who finds the guard there gains nothing. How often should the guard patrol Room A? Pause, and decide. Two thirds. Let g be the chance the guard is at Room A. Attacking A pays 4 times 1 minus g. Attacking B pays 2 times g. Set them equal: 4 minus 4 g equals 2 g. So 4 equals 6 g, and g is two thirds. One half is tempting. But then Room A pays the thief 2, and Room B only 1, so the thief would always pick A. One third is backwards: it guards the cheaper room more.
Key Takeaways
Dominance, Equilibria, and Mixed Strategies
To sum up. A normal-form game lists players, strategies and payoffs in a table. A dominant strategy is best, whatever the others do. In a Nash equilibrium, no player gains by changing only their own choice. Some games have one, some several, and some none in single choices. Zero-sum games are pure conflict, and the prisoner's dilemma shows sensible choices leaving everyone worse off. Mixed strategies choose at random, with probabilities that leave the opponent indifferent.
About Introduction to Artificial Intelligence at UPI Study
Introduction to Artificial Intelligence (Computer Science 373) is a self-paced online course of 69 video lessons in 9 chapters, from intelligent agents and search to game strategy, neural networks, logic and reasoning, machine learning, language, robotics and AI ethics. It carries a NCCRS credit recommendation for 3 semester credits.
Every lesson transcript is free on pages like this one, and the videos are free with a free UPI Study account. Enrolling adds a practice quiz after each lesson, the graded work and final exam that earn the credit, lifetime access, and an official transcript on completion. UPI Study has helped over 130,000 students with college credits. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.
Enroll now → Course details Download the syllabus All Computer Science courses Every course with PRO →
Compare: AI vs Current Trends in CS and IT
Why take it here
Why students take Introduction to Artificial Intelligence with UPI Study
Where the credit goes
Universities that work with NCCRS
Introduction to Artificial Intelligence carries a NCCRS credit recommendation. These universities work with NCCRS; some are UPI Study's signed partners. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.
Thomas Edison State UniversitySigned partner
University of the PeopleSigned partner
Charter Oak State CollegeSigned partner
Strayer UniversitySigned partner
Columbia Southern UniversitySigned partner
Indiana TechSigned partner
Penn StateWorks with NCCRS
Southern New Hampshire UniversityWorks with NCCRS
SUNYWorks with NCCRS
+many more cooperating universitiesFind my college →Find my college → Not listed? Ask Athena in the corner of this page, or book a 15-minute call.
FAQ
Questions students ask us
About Strategic Reasoning: Game Theory in Intelligent Systems
What is a Nash equilibrium in game theory?
What is the prisoner's dilemma?
What is a mixed strategy in game theory?
What is the difference between zero-sum and non-zero-sum games?
About the Introduction to Artificial Intelligence course
How many college credits is Introduction to Artificial Intelligence?
How much does Introduction to Artificial Intelligence cost and what is included?
Which universities accept UPI Study credits?
How long does Introduction to Artificial Intelligence take?
How are the exams done?
How do my credits reach my college?
Ready for the full course? Earn 3 credits in Introduction to Artificial Intelligence.
69 video lessons, a quiz after each one, and the graded work that earns the credit. Recommended for credit by NCCRS.
3 credits · NCCRSEnroll →