Iterative Dominance in Games
The concept of iterative dominance is a central concept in game theory. It is useful because it can greatly reduce the size of a player’s strategy space and make life easier for someone trying to find the Nash equilibrium. Let us start with some definitions first.
Strongly dominant strategies : A strategy s is said to strongly dominate another strategy s’ for a given player if s always provides a strictly better payoff than s’ no matter what strategies the other players play.
Weakly dominant strategies : A strategy s is said to weakly dominate another strategy s’ for a given player if s provides a strictly better payoff than s’ with at least one instance where it fares equally well as s’.
Let’s take a few zero-sum matrix game examples for better clarity. In all examples, the row player is the maximizer and the column player is the minimizer. And the matrix provided is the payoff matrix for the row player.
Take the above zero-sum matrix game. Both players have 3 strategies each . By taking a cursory look, can you identify the strongly dominant and weakly dominant strategies? Let me do the first ones for you. Observe rows 1& 2. Note that all entries in row 1 are strictly greater than entries in row 2. Since the row player is a maximizer, strategy 1 for the row player strongly dominates strategy 2. For the column player, strategy 3 weakly dominates strategy 2 and strongly dominates strategy 1. (Since the column player is a minimizer, this matrix is a cost matrix for her. And she is looking to minimize costs.) [2, 0, 4].T ≥ [1, 0, -1].T and [3, 2, 0].T > [1, 0, -1].T
Iterative Dominance :
Iterative dominance is the process of eliminating strategies from a player’s action set by identifying which strategies are clearly sub-optimal and would never be used by a rational player. It is iterative because strategies can be eliminated iteratively (the sub-optimality of a strategy may become clear only after some other strategies have already been eliminated.) Let us take the same example as above. We show how the principle of iterative dominance can help us to find a Nash equilibrium of the game.
Start with the row player. Since s1_row > s2_row, eliminate s2_row. This is because the row player, being rational, will never choose to play strategy 2 over strategy 1. So, our game is now 2 x 3. The column player knows that the row player is rational and would never play s2_row. She now observes that in the reduced game, s3_col < s2_col and s3_col < s1_col. Therefore, the column player will always play s3_col. The first and second columns can also be eliminated. The game further reduces to size 2 x 1. Since the row player knows that the column player will always choose s3_col, he decides to play s1_row because in the reduced game, s1_row > s3_row. Thus, by applying iterative dominance, both players arrive at suitable strategies that they would not deviate from. (s1_row, s3_col) is the Nash Equilibrium profile for the game. Let us verify whether this is indeed the NE, using the standard min-max approach.
Iterative dominance can be insanely useful in games with large action sets. Now that we have demonstrated the basics of this concept, let us try to apply our learning in a difficult problem.
Let us consider a n-player network game with complete information. Player i is located at node P_i. All of them want to reach the destination node D. Each player has 2 routes to reach the destination. They have access to a warp-drive(zero cost), but that leads them only to I2. From I2, they need to take the common highway to D. However, travelling on the highway is not free and the cost of travelling (1 unit) is equally divided among players who avail the highway. The other alternative is to travel to I1 and avail the community warp-drive to D. Player i travels from P_i to I1 at speed i. Since all players start equidistant from I1, the cost incurred to travel to I1 is assumed to vary as the inverse of their speeds. Note that in a network, the most common interpretation of cost is time required for transit. (That is why, warp-drives have zero cost because they travel at the speed of light.) Let us inspect the NE for such a network game.
From visual inspection, we quickly identify that there are 2 NE for this network game. In the first NE, all players choose to travel to I2 and then take the highway. In this case, each player incurs a cost of 1/n. In the second NE, all players choose to travel to I2 and then take the warp-drive to D. In this case, player i incurs a cost of 1/i. It is left as an exercise for the reader to verify why these two profiles are Nash equilibria (Hint : For each player, find the cost of unilateral deviation.) However, let us try to use the concept of iterative dominance to find the Nash equilibrium.
Let’s reason for a bit. For player n, the cost incurred for route 1(through the highway) ≥ 1/n. But he incurs a cost of exactly 1/n by choosing route 2 (community warp). Therefore, choosing route 2 is a weakly dominant strategy for player n. So he chooses route 2. Since the game is a complete information game, player n-1 knows that player n would choose route 2. Given that player n is out of the question, player n-1’s cost for route 1 ≥ 1/(n-1). While his cost for route 2 is exactly 1/(n-1) always. Thus route 2 is again the weakly dominant strategy for player n-1. By iterative logic, all players would find route 2 to be the weakly dominant strategy and all of them would end up choosing route 2. This is one of the NE that we found earlier. This is not unique because the dominance is weak. If we start with player 1 and again apply the idea of iterative dominance, we end up at the other Nash equilibrium. Pretty neat.
On a slightly tangential topic, which of these 2 NE is more efficient? This is easy actually. We can define the total network cost as the metric for measuring efficiency. With this metric, if all players choose the highway, the total network cost is 1. While, if all players choose the community warp-drive, the total network cost is (1+1/2+1/3+…….1/n). We know that the harmonic series diverges as n tends to infinity. Hence, we have a clear winner.
If you like this article and want to read more, please follow me on Medium! Cheers!