Frequently Asked Questions Flashcards
Explain how to modify the table so that the Hungarian algorithm can be used to find the matching for which the total score is maximised?
Subtract each entry from a constant (eg. 10) to convert from maximising problem to minimising problem.
How do you know S is the source?
There is no flow in, only flow out.
Explain why AB cannot be full to capacity.
At most 5 flows out of AB along BC so 7 can’t enter it.
Explain what a maximin route is.
A route where the minimum arc weight on that route is largest.
Why does row A dominate row B?
No matter which card the other team plays, row B will always score less points than row A
Why is {ST} {ABCD} not a cut?
S and T are in the same set.
What does an action value of 1 mean in the last row?
It represents the transition from (0;0) to (1;1)
Use the table to explain how to find the route.
From stage (0;0) the suboptimal minimax corresponds to action 1 which corresponds to stage (1:1) etc.
How to use maximum flow minimum cut theorem?
Find cut and state this cut = flow found.
Max flow >= flow
Min cut =
What does zero sum mean for how you play the game?
Collaboration can’t benefit both players, no reason to cooperate.
What does zero sum mean?
The number of points the first player gains is equal to the number of points the second player loses.
Total number of points won is always equal to zero.
What does stable mean for how you play the game?
Playing safe is the best strategy for both players in the long run.
What does unstable mean for how you play the game?
Playing safe is not the best strategy for both players.
Why is a dummy activity needed between A and B?
So A and B both don’t have a common start and common finish.
Why are the critical activities equal to the maximum route on the network?
They have no slack and are a continuous path therefore the longest path
Explain why subtracting 5 from the scores gives a zero sum game.
For each pairing the total of the points equals 10, so taking away 5 makes the total 0. Eg 7 and 3 –> 2 and -2
How do you know M is a maximin solution?
We want to maximise M which only differs from m by a constant, and m is the minimum expected value for each value of p.
Why is 10 subtracted from the scores?
HA solves minimum allocation problem so subtracting from 10 converts it from a maximising to minimising problem.
Why is p1+p2+p3 =
So the simplex algorithm can be used.
Amy plays using her optimal strategy, why might she win more than her expected payoff?
Bea might not play her best strategy.
Why is three taken away from m in the objective row?
3 is added throughout for non negativity, this gets rid of it again.
Why is it m=
The expected payoff can’t be less than the minimum of the three expressions so it must be less than or equal to.