Message Boards Message Boards

Nash equilibrium with non-linear utility functions and continuous variables

Posted 7 years ago

Not sure if the file is readable. I'll try again if not. Does anyone know an algorithm to do this kind of optimization? For now just two functions, each in two variables, each is maximized with only one variable. I tried, Solve, Reduce, and nested Argmax. Nothing has worked so far.

Attachments:
POSTED BY: Iuval Clejan
13 Replies

Glad to help.

Speeding things up: While you are experimenting, lower the precision to speed things up by adding

AccuracyGoal -> 4, PrecisionGoal -> 4

or even

AccuracyGoal -> 2, PrecisionGoal -> 2

to the findroot. Also, if you can give it a better starting point it helps. You can also set limits for the variables to narrow the search space.

POSTED BY: Neil Singer

luval,

You need to "protect" your functions with ArgMax from the solver trying to evaluate it -- it needs to be reserved for only numbers. I would do this:

eq1[v2n_Real] := ArgMax[f1[r, v1, v2n, x1star, x2star], v1]
eq2[v1n_Real] := ArgMax[f2[r, v1n, v2, x1star, x2star], v2]

Note that eq1 and eq2 will only evaluate when v2n and v1n are real numbers.

I do not get a solution from your equations but if I change a sign in one, I do get an answer. (Maybe there is a sign or equation problem??). But Mathematica can now solve these equations. You will need to look at the origin of your equations to see why there is no solution as they were originally written.

sol2 = FindRoot[{v1n == eq1[v2n], 
   v2n == -eq2[v1n]}, {{v1n, 1}, {v2n, -1}} ]

to get

{v1n->0.539353,v2n->-1.13056}

You need to use FindRoot because the equations are now only numerical. If you do not "protect" the equations by putting _Real in the definition, you will get an error when Mathematica first tries to evaluate the equations symbolically.

I hope this helps.

Regards

Neil

POSTED BY: Neil Singer
Posted 7 years ago

Neil, you got it. Now I just have to figure out why my equations are not right. Also, it takes a long time to give output.

POSTED BY: Iuval Clejan
Posted 7 years ago

Yes, correct. Thanks!

POSTED BY: Iuval Clejan

I thought of a simple way for you to fix this problem. I will post something when I return to be in front of a computer. I assume that you are OK with a numerical solution and not an analytical one. Correct?

POSTED BY: Neil Singer

Look at the first equation. V1n == Argmax(f(v1, v2n),v1). The expression inside the argmax has the variable, v2n in it. The expression is non-numerical as v1 is varied.

To explore this, just copy the equation-- you will get an error when you evaluate it.

POSTED BY: Neil Singer
Posted 7 years ago

Not at all. Solve, or NSolve might be giving ArgMax a non-numerical variable, but I don't know how to prevent that. Here is the relevant piece of code again (the original had Solve, now it's NSolve:

sol2 = NSolve[{v1n == ArgMax[f1[r, v1, v2n, x1star, x2star], v1], 
    v2n == ArgMax[f2[r, v1n, v2, x1star, x2star], v2]}, {v1n, 
    v2n}][[1, 1]]

v1n and v2n are both real numbers, but perhaps NSolve takes them as something else in intermediate steps. How could this be reformulated?

POSTED BY: Iuval Clejan

Luval,

ArgMax is a numerical function and you are giving it an equation with non-numerical variables. You need to reformulate the expressions.

Regards

POSTED BY: Neil Singer
Posted 7 years ago

Hi Michael,

Thanks again for your help. Unfortunately, the article you mentioned is about a non-linear programming algorithm, which has only 1 utility function. In game theory, there are 2 or more (2 in the simple example I submitted) utility functions to be optimized simultaneously, sharing dependent variables. The problem is much simpler (and can easily be solved by known techniques) when the functions are linear, as is the case for many classical (bi-matrix) games, but even this is not true in my case. It appears that for bi-linear games, it is possible to use Reduce and the KT algorithm, as that article does.

Still, I would be surprised if nothing exists out there. I will keep searching.

POSTED BY: Iuval Clejan
Posted 7 years ago

Hello Iuval, I had a closer look, you are right, the solution that Solve gives in my reply is not what you are looking for. Solve will put v2n there to zero. And executing your version where you assign numerical values to the parameters in the beginning I also get the error.

So I do not have a good suggestion at hand. In the Mathematica Journal there was a contribution to make use of Reduce[] SÉRGIO O. PARREIRAS, Using Reduce to Compute Nash equilibria, maybe this can help.

POSTED BY: Michael Helmle
Posted 7 years ago

I'm not sure I believe you that Solve finds a solution with v1n=1.16, even in the newer version. When I try

ArgMax[f2[v1,v2]/.v1->1.16,v2]

The output is v2=-0.96

And when I try

ArgMax[f1[v1,v2]/.v2->-0.96, v1]

The output is v1=0.62.

So whatever you found is not a Nash Equilibrium (there is no Nash equation, look up the concept of Nash equilibrium, which is basically what the Argmax equations say for continuous variables).

I wonder what algorithm Solve uses to find the solution. Just setting the derivatives to zero does not give the correct solution, since the second derivatives have to be negative. I tried it with FindRoot, setting derivatives to zero, and it does not give the solution with negative second derivatives, but with zero or positive ones. I think FindRoot might use a multifunction version of Newton-Raphson, but it does not work in this case. What was the v2n that you say Solve gave you?

POSTED BY: Iuval Clejan
Posted 7 years ago

Hi Michael and thanks for your reply. Perhaps it is my old version, but with the same parameters as you, I still get the same error as before (sa, and sk are not needed, not sure why you had them as parameters). I enclose the file in order to show the output error messages.

Attachments:
POSTED BY: Iuval Clejan
Posted 7 years ago

Hi, Mathematica finds numerical solutions to your problem. I pick only the 1st in the list of solutions.

sol2 = Solve[{v1n == ArgMax[f1[r, v1, v2n, x1star, x2star], v1], 
    v2n == ArgMax[f2[r, v1n, v2, x1star, x2star], v2]}, {v1n, 
    v2n}][[1, 1]]

Since I am not familiar with the Nash equation I took arbitrary numerical values (my choice probably does not make sense in the context of your problem):

sol2 /. { sk -> 2, sk2 -> 3.7, x1star -> 3, x2star -> 4, sa -> 0.7, 
  sa2 -> 0.9, beta -> 0.6, r -> 1, Km -> 1.}

which results in:

v1n -> 1.16268

In order to explore a larger space you can use this:

prmLst = { sk, sk2, x1star, x2star, sa , sa2, beta , r, Km};
tab = Map[
   Flatten[{#, 
      Quiet[Check[sol2 /. Thread[prmLst -> #], 
        Text["Convergence failed", 
         BaseStyle -> {Red, FontFamily -> "Times", Italic}]]]}] &, 
   RandomReal[{-1, 1}, {50, Length[prmLst]}]];
TableForm[tab, TableHeadings -> {None, Join[prmLst, {"solution"}]}, 
 TableDepth -> 2]

For some parameter sets Solve does not converge (see table entries)

POSTED BY: Michael Helmle
Reply to this discussion
Community posts can be styled and formatted using the Markdown syntax.
Reply Preview
Attachments
Remove
or Discard

Group Abstract Group Abstract