Expected Payouts: Electrical Engineering Meets Game Theory
A common problem in zero-sum game theory is determining the expect payout of a player in a game when each player plays optimally. This involves finding the mixed Nash equilibrium and then using those optimal probability values for each strategy to calculate the expected payoff. In a simple scenario where each player only has two strategies the above method isn’t computationally cumbersome. Take the following network and payoff matrix from the article, for example.
|
Traveler\\Troll |
N |
S |
|
N |
0,1 |
1,0 |
|
S |
2, 0 |
0, 2 |
We assign a probability that each strategy is played by each player and set those expressions equal to each other to solve for the mixed Nash equilibrium. Doing this calculation, it is easy to verify that the expected payoff of the Traveler is 2/3 when the game is played optimally.
What is unique about the value 2/3 in this case is that it is the harmonic mean between the cost of the two roads.
Harmonic mean? What?
The harmonic mean is the ratio of 1 to the sum of the reciprocal of the values. So, in this case, 1/ (1/1 + ½) = 2/3. This looks awfully similar to a very common problem seen in electrical engineering – circuit analysis.
In an electric circuit consisting solely of resistors we can find the equivalent resistance of the circuit which is simply modeling that entire circuit as another with only one resistor. This allows seemingly difficult problems to be simplified down to very basic ones. And the rules of simplification are simple. In a circuit, if a set of resistors is parallel their equivalent resistance is the ratio of 1 to the sum of the inverses of each resistor’s resistance. If a set of resistors is in series, their equivalent resistance is simply the sum of each resistor’s resistance.
The following diagram helps visualize this.
R_eq = 1\(1\R1 + 1\R2 + … + 1\Rn)
R_eq = R1 + R2 + … + Rn
Ok, enough about circuits, let’s get back to game theory.
If we assume the network structure can be modeled as resistors where the ‘cost’ induced by each path is the resistance value, we can now solve for the expected payout of a player in a more complicated network.
Consider the following, more complicated network.
Finding the expected amount that our Traveler will pay boils down to finding the harmonic mean of this network.
So, SN, SM, SS can be considered to have an equivalent cost as the sum of the inverse of their reciprocals. Call this value S2.
Then we treat S and S2 like resistors in series and sum their values – call this value S3. We then compute the inverse of the sum of the reciprocals between N and S3. This is the final answer.
The diagrams below illustrate the above jumble of words.
The expected payout of the Traveler is now the harmonic mean between these two values. Which is 39/67. This result can be verified by using a zero-sum solver.
We could have done this by making a payoff matrix and assigning a probability to each initial route and using those to find the mixed Nash equilibrium and then compute the expected payout of the Traveler with those probability values, OR we could do what we did above which is clean simple math.
In conclusion, we used what we knew from another area and applied it to a new, situation and found that the results hold. This illustrates the beauty of mathematics, how the same math applies to multiple topics. In the case of networks, it helps us solve for the expected value in two player zero-sum games. While we haven’t done problems to this extend in the course, we now have the tools to.
Image Sources
https://www.allaboutcircuits.com/uploads/articles/Parallel-Resistance-Calculator.jpg