Statistics

Problem Statement for "Nash"

Problem Statement

In game theory, a Nash Equilibrium is a situation where none of the individual parties involved has a rational incentive to change what they are doing. The options available to all parties are represented in a game matrix that displays the outcomes of every possible scenario. For the purposes of this problem, assume there are only two parties involved, so the game matrix will always be two-dimensional.

The following is a sample game matrix. 
4:4  -1:5

5:-1  8:8

The game matrix is filled with ordered pairs representing the payoffs for each of the two players. The left number represents the payoff for the row player. The right number represents the payoff for the column player. The more positive the payoff, the better. The row player can move from the current square to any other square IN THE SAME COLUMN. In other words, the row player can choose the row and the column player can choose the column.

Grid indices are simply used for naming purposes and do not effect the payoffs. Indices start from 1 and increase along the rows. For example, 4:4 is index 1, -1:5 is index 2, 5:-1 is index 3, and 8:8 is index 4. The following is the grid indices for a 3x3 grid 

1  2  3
4  5  6
7  8  9

Grid index 1 with the 4:4 means that the row player will get a payoff of 4 and the column player will get a payoff of 4. In this situation, both the row player and the column player would rather change strategies. For example, the row player can move down to the bottom row to grid index 3 containing 5:-1. In this case, the row player would get a payoff of 5 instead of 4. Grid index 1 is not a Nash Equilibrium.

If the players are at grid index 3, then the column player would rather change strategies to a different column (staying on the same row). The column player would move to grid index 4, 8:8, in order to increase his payoff to 8 from -1. Grid index 3 is not a Nash Equilibrium. Similarly, grid index 2 is not a Nash Equilibrium.

At grid index 4, 8:8, neither player has an incentive to move because doing so would not result in a higher payoff. This is a Nash Equilibrium.

Write a method findEq that takes as input a String[] representing a game matrix and outputs the space-delimited grid indices of all Nash Equilibriums in ascending order. Return an empty String if there are no Nash Equilibriums in the provided game matrix.

Definition

Class:
Nash
Method:
findEq
Parameters:
String[]
Returns:
String
Method signature:
String findEq(String[] gameMatrix)
(be sure your method is public)

Notes

  • A game matrix might have more than one Nash Equilibrium, or might not have any.
  • If the players are indifferent to moving or staying, then consider that a Nash Equilibrium (see example 2).

Constraints

  • The game matrix will be a square matrix. That is, if there are n rows, then there must be n columns. The number of columns is the number of grid squares in each row.
  • There must be at least one row in the game matrix.
  • A grid square must be of the form x:y where x and y are ints between -99 and 99, inclusive.
  • Each pair of grid squares within a row are separated by exactly one space with no trailing space after the last square.
  • gameMatrix contains between 1 and 50 elements, inclusive.
  • Each element of gameMatrix contains between 1 and 50 characters, inclusive.
  • Each element of gameMatrix contains the same number of terms as the number of elements in gameMatrix.

Examples

  1. {"4:4 -1:5", "5:-1 0:0"}

    Returns: "4"

    This is the well known prisoner's dilemma. Even though it is obvious that both parties are best off in the top left corner (4:4), the only Nash Equilibrium is in the bottom right corner (0:0). That is because at any other grid index, at least one player has an incentive to change their strategy. At grid index 4, however, any change in strategy will result in the changing player scoring -1 instead of 0.

  2. {"4:4 4:4", "4:4 4:4"}

    Returns: "1 2 3 4"

    In this grid, every single grid square is exactly the same, so no player will ever have an incentive to move.

  3. {"10:-10 0:0", "0:0 10:-10"}

    Returns: ""

    In this grid, there are no Nash Equilibriums because at every square, one player would rather change strategies. In square 1, the column player would want to move in order to change payoffs from -10 to 0. In square 2, the row player would want to move in order to change payoffs from 0 to 10. In square 3, the row player would want to move in order to change payoffs from 0 to 10. Finally, in square 4, the column player would want to change to move from -10 to 0.

  4. {"6:0 3:1 2:2", "4:1 0:0 0:0", "7:7 0:0 0:0"}

    Returns: "3 7"

    In this game, the bottom left corner and top right corner squares are the only Nash Equilibriums. Note that even though the (7:7) square is clearly the much better square for both players, (2:2) is still an equilibrium since no individual player will have an incentive to move. The players must assume that the other player will not move.

  5. {"-10:-10"}

    Returns: "1"

    There is only one possible situation available to the players, hence it must be a Nash Equilibrium.

  6. {"3:5 5:7 7:9 4:4","1:0 2:0 5:5 8:8","-1:-3 -3:-5 -4:-4 0:10","-11:10 -6:8 -2:2 5:0"}

    Returns: "3 8"

  7. {"3:5 5:7 7:9 4:4","1:0 2:0 5:5 8:8","10:20 -3:-5 -4:-4 0:10","-11:10 40:40 0:0 5:0"}

    Returns: "3 8 9 14"

  8. {"0:0 1:1 2:2 3:3 4:4 5:5 6:6 7:7","0:0 1:1 2:2 3:3 4:4 5:5 6:6 7:7","0:0 1:1 2:2 3:3 4:4 5:5 6:6 7:7","0:0 1:1 2:2 3:3 4:4 5:5 6:6 7:7","0:0 1:1 2:2 3:3 4:4 5:5 6:6 7:7","0:0 1:1 2:2 3:3 4:4 5:5 6:6 7:7","0:0 1:1 2:2 3:3 4:4 5:5 6:6 7:7","7:7 7:7 7:7 7:7 7:7 7:7 7:7 7:7"}

    Returns: "8 16 24 32 40 48 56 57 58 59 60 61 62 63 64"

  9. {"4:4 -1:5","5:-1 0:0"}

    Returns: "4"

  10. {"4:4 4:4","4:4 4:4"}

    Returns: "1 2 3 4"

  11. {"10:-10 0:0","0:0 10:-10"}

    Returns: ""

  12. {"6:0 3:1 2:2","4:1 0:0 0:0","7:7 0:0 0:0"}

    Returns: "3 7"

  13. {"-10:-10"}

    Returns: "1"

  14. {"3:5 5:7 7:9 4:4","1:0 2:0 5:5 8:8","-1:-3 -3:-5 -4:-4 0:10","-11:10 -6:8 -2:2 5:0"}

    Returns: "3 8"

  15. {"3:5 5:7 7:9 4:4","1:0 2:0 5:5 8:8","10:20 -3:-5 -4:-4 0:10","-11:10 40:40 0:0 5:0"}

    Returns: "3 8 9 14"

  16. {"0:0 1:1 2:2 3:3 4:4 5:5 6:6 7:7","0:0 1:1 2:2 3:3 4:4 5:5 6:6 7:7","0:0 1:1 2:2 3:3 4:4 5:5 6:6 7:7","0:0 1:1 2:2 3:3 4:4 5:5 6:6 7:7","0:0 1:1 2:2 3:3 4:4 5:5 6:6 7:7","0:0 1:1 2:2 3:3 4:4 5:5 6:6 7:7","0:0 1:1 2:2 3:3 4:4 5:5 6:6 7:7","7:7 7:7 7:7 7:7 7:7 7:7 7:7 7:7"}

    Returns: "8 16 24 32 40 48 56 57 58 59 60 61 62 63 64"

  17. {"2:-1"}

    Returns: "1"

  18. {"-10:0 10:3","0:0 3:1"}

    Returns: "2"

  19. {"-1:0 0:0","9:10 -1:0"}

    Returns: "2 3"

  20. {"1:1 2:2","2:2 1:1"}

    Returns: "2 3"

  21. {"4:4 4:4","4:4 4:4"}

    Returns: "1 2 3 4"

  22. {"6:0 3:1 2:2","4:1 0:0 0:0","7:7 0:0 0:0"}

    Returns: "3 7"

  23. {"6:0 3:1 2:2 3:3","4:1 0:0 3:3 0:0","7:7 0:0 0:0 1:1","-1:9 1:1 0:0 0:0"}

    Returns: "4 7 9"

  24. {"6:0 3:1 2:2","4:1 0:0 0:0","7:7 0:0 0:0"}

    Returns: "3 7"

  25. {"4:4 4:4","4:4 4:4"}

    Returns: "1 2 3 4"

  26. {"-10:-10"}

    Returns: "1"

  27. {"1:1 0:0 0:0","0:0 0:0 0:0","0:0 0:0 5:5"}

    Returns: "1 5 9"

  28. {"6:0 3:1 2:2","4:1 0:0 0:0","7:7 0:0 0:0"}

    Returns: "3 7"

  29. {"10:10"}

    Returns: "1"

  30. {"-10:-10"}

    Returns: "1"

  31. {"4:4 0:0 1:1","6:6 7:7 -1:-1","1:1 -1:-1 0:0"}

    Returns: "5"

  32. {"10:10 0:0 0:0","0:0 0:0 0:0","20:20 0:0 0:0"}

    Returns: "5 6 7"

  33. {"0:0 0:0 0:1","0:0 0:0 0:-1","0:0 0:0 0:0"}

    Returns: "3 4 5 7 8 9"

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2024, TopCoder, Inc. All rights reserved.
This problem was used for: