Is it possible to make excluded search with for loop in Java? [closed]

Question

I am trying to calculate all pure strategy Nash equilibrium in a mxn game. It requires to check all pure strategy pairs (m.n pairs). Suppose player 1 has m strategies. Algorithm should start with the first pair (1,1) and compare (1,1) with (2,1),(3,1),...(m,1).

Same for all strategies, exp: (3,4) is compared by (1,4),(2,4),(4,4),...,(m,4).

In summary is it possible to make a search with for loop which excludes existing i:

Thank you.

Answer 1

First of all, if you want to check each combination of pure strategies, you will have two nested for loops:

int a, b;
for (b = 0; b < n; b++) {
  for (a = 0; a < m; a++) {
    compare(a, b);
  }
}

Additionally, compare(a,b) will then be compared to each alternative I have to exchange a under the assumption that my opponent will use b:

int compare(int a, int b) {
  for (int x = 0; x < m; x ++) {
    if (x == a) continue; // This will exclude the check (a, b), (a, b)
    System.out.println("Comparing (" + a + ", " + b ") and (" + x + ", " + b + ")");
  }
  return 0;
}

However, my knowledge of game theory is a little bit rusted. Aren't you trying to determine the best answer in pure strategies to each pure strategy of your opponent?

In fact, this comparison would have a complexity of $\mathcal{O}(m^2\cdot n)$. In order to determine the best answers with only a complexity of $\mathcal{O}(m\cdot n)$, you can gradually search the maximum payoff while traversing each possible combination of strategies:

int best_answers[n];
int a, b;
int max_payoff;
for (b = 0; b < n; b++) {
  best_answers[b] = 0;
  max_payoff = 0; // If negative payoffs are possible, adjust this.
  for (a = 0; a < m; a++) {
    if (payoff[a][b] > max_payoff) {
      max_payoff = payoff[a][b];
      best_answers[b] = a;
    }
  }
}

Here, I assume that int payoff[m][n] is a 2-dimensional array that encodes the payoff matrix. After running this algorithm, best_answers[b] contains the best answer strategy for strategy $0 \leq b < n$ of the opponent.