Unit 3: Game theory & sequencing
Operation Research notes · PTU syllabus (BBA501-18)
On this page
Unit summary
Game theory analyses competitive situations where each player's outcome depends on others' choices. Sequencing decides the order of jobs on machines to finish them fastest. This unit covers games with pure and mixed strategies, saddle points, dominance and sub-games, and sequencing jobs on two and three machines.
After this unit you can
- Solve games with a saddle point
- Solve 2 × 2 games without a saddle point using the odds method
- Reduce games by dominance and the sub-games method
- Sequence jobs through two and three machines using Johnson's rule
PTU syllabus topics
- Games with pure and mixed strategies
- saddle point
- odds method
- principle of dominance
- sub-games method
- sequencing problems — processing jobs through two and three machines
- Pure strategy
- Same move every time
- Mixed strategy
- Moves chosen with probabilities
- Saddle point
- Maximin = minimax: value of the game
- Dominance
- Drop a strategy that is always worse
- Zero-sum game
- One player's gain is the other's loss
Topic 1
Game theory basics
A two-person zero-sum game has two players where one's gain equals the other's loss. The payoff matrix shows the gains of the row player.
- Pure strategy: a player always chooses the same move.
- Mixed strategy: moves are chosen with probabilities.
- Saddle point: where the maximin (row player's best worst) equals the minimax (column player's best worst); this value is the value of the game.
Example
Payoff matrix rows A1: (4, 6), A2: (3, 2). Row minima 4, 2 → maximin 4; column maxima 4, 6 → minimax 4. Saddle point at (A1, B1); value = 4.
Topic 2
Mixed strategies: odds method
For a 2 × 2 game without a saddle point with matrix [a b; c d]:
- Row player plays row 1 with probability (d − c)/(a + d − b − c).
- Value of the game V = (ad − bc)/(a + d − b − c).
Example
Matrix [5 1; 3 4]: no saddle point. p = (4 − 3)/(5 + 4 − 1 − 3) = 1/5; V = (20 − 3)/5 = 3.4.
Topic 3
Dominance and sub-games
- Dominance: delete a row that is always worse (for the row player) than another row, and a column that is always worse for the column player, to reduce the matrix.
- Sub-games method (2 × n or m × 2 games): solve each 2 × 2 sub-game and choose the best for the player with more strategies; or use the graphical method.
Topic 4
Sequencing problems
Sequencing finds the order of jobs that minimises total elapsed time (and idle time).
- 1Find the smallest processing time among all jobs
- 2If it is on machine 1
Place the job first
- 3If it is on machine 2
Place the job last
- 4Remove that job and repeat
- 5Calculate elapsed and idle times
Three machines (A, B, C): convert to two fictitious machines G = A + B and H = B + C if min A ≥ max B or min C ≥ max B, then apply Johnson's rule.
Key terms
- Zero-sum game
- One player's gain equals the other's loss
- Saddle point
- Where maximin equals minimax
- Mixed strategy
- Choosing moves with probabilities
- Dominance
- Removing strategies that are always worse
- Johnson's rule
- Algorithm for sequencing jobs on two machines
Quick revision
- Saddle point: maximin = minimax = value.
- Odds method for 2 × 2: V = (ad − bc)/(a + d − b − c).
- Dominance reduces the matrix.
- Johnson: smallest on M1 → first; on M2 → last.
Important exam questions
Practice questions written to the PTU exam pattern for this unit's syllabus: short answers (Section A style) and long answers (Sections B and C style).
Short-answer questions
- Q1.Define a two-person zero-sum game.
- Q2.What is a saddle point?
- Q3.Differentiate between pure and mixed strategies.
- Q4.State the rule of dominance.
- Q5.State Johnson's rule.
Long-answer questions
- Q1.Solve a game using the maximin-minimax principle and dominance.
- Q2.Solve a 2 × 2 game without a saddle point.
- Q3.Sequence n jobs on two machines and find total elapsed time and idle times.
Stuck on this unit?
Message SBS on WhatsApp for help with Operation Research, or to ask about studying BBA at Synetic.