World's most popular travel blog for travel bloggers.

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

, , No Comments
Problem Detail: 

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.

Asked By : alamaranka
Answered By : Rmn

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/38397

3200 people like this

 Download Related Notes/Documents

0 comments:

Post a Comment

Let us know your responses and feedback