finding nash equilibria

[Stormyman]

Hi,

Suppose a game where 2 players [1,2] invest into capacity (that costs) and earn their profit according to their fraction of total capacity.
So profit(player 1)=capacity(player1)/ (capacity(player1)+capacity(player2)) and vice versa.

I cannot just let one player optimize his profit, holding the other players actions constant.
Both players simultaneously choose their optimal investment. The mututally best answers are a Nash equilibrium.

I found a way to compute this in Vensim manually.
I first let player 1 optimize, given a fixed action of player 2. Taking the new optimal value for player 1 fixed, I let player 2 optimize. Taking this new value I let player 1 optimize again, fixing the new optimal value of player 2. After repeating this several times. Both players do not want to deviate anymore.

However, I am working with larger games containing more than 2 players and it takes 2 hours to find the Nash equilibrium by hand.
Now my question is: How can I automate the optimizations ?
That one optimization follows another ?

How can I tell vensim to
1. optimize profit 1 varying investment1
2. take the new optimal investment 1
3. optimize profit 2 varying investment 2
4. take the new optimal investment 2
5. repeat 1 to 4. 100 times
6. quit and save new values

Do I have to use external functions or is there an easier way ?

[bob@vensim.com]

It sounds like you are working a static problem. If that is the case you can write a batch file that alternates between optimizing the behavior of the N players using the results of one as input for the next. Call that batch file iteratively (a batch file with multiple FILE>SHELL commands will work).

If your model is dynamic then this won't work as well. Putting in optimization in the loop (similar to FIND ZERO) is planned but not yet here.

Bob Eberlein

[Stormyman]

Thank you for the reply.
In a dynamic problem wouldn't it work to use investment vectors that are optimized until no player wants to deviate from the investment vector anymore given the vectors of all other players ?
With a single player this works.

How would such a batch file with FILE>SHELL commands look like ?

[bob@vensim.com]

Yes you could optimize on the vector - I am not so sure about convergence but I guess just give it a try and see.

The file command is simply

FILE>SHELL|optfile.cmd
FILE>SHELL|optfile.cmd
FILE>SHELL|optfile.cmd

and so on. The trick in all of this it so make sure that optfile.cmd leaves things in a state where it can pick up on the next round - unfortunately there is no way to see if convergence has occurred so you just need to have a bunch of calls and see it it worked.

[LAUJJL]

Hi

Here is joined the basic static model without any optimisation.
I think it is best to be sure that it represents your problematic.

The problem is to maximize the sum of the profits of both players.
Looking at the model, if nothing diffentiates the player, the optimum will correpond to both players having the same capacity, if there is one solution to the problem.
And one can simplify the model with one unique player.
Before trying then to explore the question, it is better to explain the conditions of the problem first and to give some explanations.
There is eventually a solution with a find zero function, with a loop going from the total profit and running through both capacities. the problem being to find some way that makes the find zero converge.
But before doing that it is better to differentiate both players
first.
Another problem is how the players will continue playing if the model becomes dynamic. What will be the link between
different succesive simulations even if there has been an
optimization through a find zero function.
Regards.
JJ

[LAUJJL]

Hi

One can too use the optimization technique, and
put total profit as maximum, and for example vary the
constants capacity between 0 and 100, and the maximum for
total profit will be one, and with many solutions and symetric.
Here is joined the same model with two time steps, one does not need more, the model being static and a slight mofication using a zidz function.
Regards.
JJ

[Stormyman]

I first have to learn to program batch files, when I did, I will post here.
Fotunately it should easily be possible to test if convergence was achieved, but just letting one or some only players maximize and see if thy choose another optimum.

LAUJJL ,

Thank you for the reply. The concept of nash equilibria unfortuantely is not so simple.
The solution to maximize the sum of profits is only true if both players cooperate. Or if they are one firm - one monopolist. If they do not cooperate, but only think of themselves the solution will be different. Suppose the following situation, each player has 2 strategies Cooperate and Defect.

A's profit stategy "cooperate":3 if B cooperates, 0 if B defects
A's profit stategy "defect":5 if B cooperates, 1 if B defects
B's profit stategy "cooperate":3 if A cooperates, 0 if A defects
B's profit stategy "defect":5 if A cooperates, 1 if A defects

Player A thinks : If B will play "cooperate" , I will play "Defect", since 5>3. If B plays "defect" I will play "deceft" because 1>0.

Player B: If A plays cooperate I will play defect , because 5>3, if he plays defect, I play defect.

No player will cooperate, but play defect in all sitatutions ! In the equilibrium profits are 1 and 1. Not 3 and 3. Although 3 and 3 (both cooperating) would be better.
The sum of profits is the greatest if both players cooperate (6), if they defect it is small (2).

I do not want to find the 3,3 point, but the 1,1 point ! Because the 3,3 is no equilibrium, both will deviate.

Hence for Vensim to find the equilibrium, it needs to compute the point of mutually best answers. Each player needs to maximize, given the optimal action of the other.
And the equilibrium often is not the point, where the sum of profits is maximized, but the point, that is stable, if both players maximize individually.

[Edited on 7-9-2007 by Stormyman]

[LAUJJL]

Hi

I understand your point.
Each player has to find his best strategy supposing that the other player chooses his best stragegy too and that he is
clever enough to find it.
But anyhow you have to explain what are the differences between the two players otherwise you are back to a symetrical game where you are looking for the maximum of
total profits but with the constraint that the POLICIES MUST BE EQUAL!
See model attached with the constraint built in the objective function to maximize. It delivers a solution where the policies are equal where in the preceeding model you had many policies possible.
As soon as one introduces a difference between the two players it is no more possible to use this constraint of equality and the problem is changing.
Il would good to post a simple model to illustrate your point of view!
It would permit to clarify if the problem is strictly static or dynamic. What kind of stability, instantaneous or dynamic?
Regards.
JJ

[Stormyman]

Hi there,
I built a model to illustrate my problem.
I didn't add units , but I hope its understandable.

2 Players make profit by offering a capacity to the market.
The profit in a period is:

profit (player)=demand*(capacity 1/(capacity 1+capacity2))-investment cost
Player 1 starts with a capacity of 50 and player 2 start with 100.

Both players can buy additional capacity, that costs money.
The more capacity they already have, the more expensive it
is to attain additional capacity !

The game lasts 20 periods.

Both players maximize the cumulated profit of period 20.
They can only choose once how much capacity to buy periodically at the
beginning of the game.
If they are smart - and cooperate - both will buy no capacity at
all, since their profit depends only on their RELATIVE capacity and
not on their ABSOLUTE capacity.
You find that solution if you maximize "final total profit" by
a variation of INVESTMENT 1 and INVESTMENT 2.
So the cooperative solution is :

INVESTMENT 1 = 0
INVESTMENT 2 = 0

But in the game, this optimal solution doesnt occur !
What happens is something like an "arms race".

Each player has a unilateral incentive to deviate by buying additional
capacity, because he can get a bigger market share (until the
point where cost gets too high).
You find that out if you take the cooperative investment solution (0,0)
and let only player 1 maximize "final profit 1" varying "investment 1", keeping
investment 2 constant. He suddenly wants to invest 10.6895 !

Player 1 doesnt feel like staying at the cooperative solution, he
wants to deviate by investing more than zero.
However player 2 can answer simulatenously and maximize final profit 2 by
varying investment 2.
By letting both players maximize again and again, given the optimal solution
of the other I find the Nash equilibrium:
INVESTMENT 1 = 11.2814
INVESTMENT 2 = 7.66649
No player wants to deviate from this solution. Try it out by letting one of the players maximize, given the answer of the other. The soluation above gives mutually best answers.
Thats the game equilibrium !

With many players fiding the equilibrium is a long process if I do it by hand
and takes easily 2 hours. I want to automate this process somehow in vensim.

Greetings

[Edited on 7-10-2007 by Stormyman]

[LAUJJL]

Hi

Some remarks with your model.

I feel very uneasy to work with a model without units.
It is easy to use units and anything that can be done to make a model less error prone must be used
Especially if it is easy.

When building the units, one can make some remarks.

First investment should be valued with ‘dollars’, and capacity with ‘capacity unit’ or ‘capacity’.
And one should use a constant ‘Cost of a unit capacity’ with unit ‘Capacity / dollars’.
One does not need then the parameter cost factor that is anyhow very ambiguous.

Profit accumulation should be put in a box and the flows clearly shown as for the capacity.

The formulation of the profit accumulation seems strange.
It is conceivable that the profit is depending linearly from the ratio (capacity1 / (capacity1 + capacity2))
Although simplistic but it is more a mathematical problem than a real life one, but making the profit depend
linearly from the demand is difficult to imagine.
If the demand exceeds the capacity, the linear dependence does not exist anymore.
So the relation to my opinion should be reformulated.
It should be better to write the models with subscripts so as to be able to add more players.

As soon as I have some time, I will propose a model that solves these problems.

Regards.

JJ

[Stormyman]

The model is NOT to illustrate a real life problem nor should be used for that.
It was built within a few minutes just to point out mathematical problem in the forum here.

Alternatively you can use a cournot competition, that is a bit more realistic, having the same mathematical problem.

I have larger models representing real life problems, but they are too large to illustrate the mathematical problem here quickly.

[Edited on 7-11-2007 by Stormyman]

[LAUJJL]

Hi

I will have a look at the formal definition of the Nash equilibrium or Cournot (2 players) equilibrium at Wikilpedia.
Regards.
JJ

[Stormyman]

I built a small counot model for illustration in Vensim.
If you maximize Joint Profit varying quantity 1 and quanity 2...youget mulitple solutions.
That is one player supplies 50, the other 0.
Or both players supply 25.

However you can easily test that one player will deviate from all these solutions if he maximizes his own profit varying his own quanity.

The Nash equilibrium is 33.3333 and 33.3333
No player will deviate. You can checkt it .

I find it by letting 1 maximize, taking new value, letting 2 maximize, taking new value... repeating it 10 times. How can that be done automatically ?

For real life that means: Firms will supply MORE than if they compete than they would if they cooperate (acting as if they were one firm). 66 > 50. But they will still do so, taking into account the actions of the other.
The resulting price will be lower with competition than without.

[LAUJJL]

Hi

I have looked at Wikipedia.
If we want to carry on this thread, it would be better that you clarify what you want.
There are two sort of Nash equilibrium, a pure equilibrium and a mixed stratety equilibrium where the player is playing randomly over a choosen distribution of strategies.
For example, stragegy 1 in 20% of cases and strategy 2 on 80% of cases. One must then build a model with distribution and optimize the parameters of the distribution.
something that is not clear in the definition of Wikipedia, is if
every player needs to know the strategy of all the other players.
On the informal definition, it looks first not necessary, then necessafy.
In the formal definition it does not seem necessary.
Regards.
JJ

[LAUJJL]

Hi

I have checked the model Nash equilibrium3.

The solutions delivered are not a Nash equilibrium as any
time where capacity 1 = capacity 2, delivers a total profit of 2, according that both capacity can vary between 0 and 100.
Or if one player knows that his opponent has a capacity of say 50, he can change his strategy to anything more than 50
and he will better his stragegy.
The evident Nash optimum is 100 for both players the maximum than every player can play.
To find the Nash equal to 100, joined a model, that calculates the Nash equilbrium.
Regards.
JJ

[LAUJJL]

Hi

To be completely rigorous, one should look for the optimum for each player one after the other, but because it is necessarye symetric one can put as pay off the total of the
profit or both players.
But if one puts only the profit of say player one as optimum and as parameter to optimize the capacity of player one, one finds again the same capacity say 100 if 100 is the maximum capacity allowed.
Regards.
JJ

[Stormyman]

> LAUJJL
I am not sure if you understood the concept of Nash Equilibria. There are games with no equilibria, with pure equilibria, with mixed equilibria and with both.

Of course its best to find all equilibria. But the pure ones would already be enough.
In your file without a restriction there is no equilibrium at all, players want to invest as much capacity as possible and nothing prevents them from doing so. If you add a restriction, both want to have the maximum possible.

I managed to write a small program that solves cournot. Players can choose between quantities of 0,25,33,50,66,100
The model solves the problem. There are 2 pure Nash equilibria.
However I can only test the predefined stratigies. Also with many players/strategies... it takes years to calculate.

I guess anything else has to be done via batch files.

[LAUJJL]

Hi

The concept of Nash equilibruim is very general, and in your model you find a Nash equilibrium where the capacities are limited as in my model. The only difference is that the strategies are discreet, so you can easiliy find the maximum strategy for each player whatever plays the other one.
I my model I need to optimize, but in both models the Nash is at the maximum of the allowed capacity.
I recognize that my model is simplistic and the solution evident but it is a Nash equilibrium meaning that if a player plays the Nash optimum he is sure to have the best strategy whatever other players play, which is the definition of the
Nash equilibrium.
But it seems that the other conditions are not fixed and you are free to choose conditions simplistic, as in my model and yours, or complex.
In your model, a player by playing the maximum allowed, forces both players to have zéro profit, when one studies
how the price is generated, both sell at a price of zero.
It it then an even more strange optimum than mine.
It is goo to put a lookup extrpolate to avoid error messages from the lookup function.
It seems too that if a player chooses the strategy 50, it looks too like a Nash equilibrium, because the other player can never have a capacity that is more than his.
Any strategy beween 50 and 100 will do too, except that with 50, the player increases his chances to have some profit if the other player plays less than 50.

About predefined strategies, in my model there is no predefined strategy except an interval of permitted strategy.
If you have many predefined strategies and many players, the only thing to do is to add subscripts.
But adding subscripts if there are many players is possible only with 8 players, because of the limitation of the number of subscripts.
The only way is to have continuous strategies, eventually random as the model joined.
See joined model.
The model calculates an optimal strategy but does not suppose that each player knows the strategy of the other, and supposes that the strategy of the player 2 is random.
One can too play with as many players wanted.
To find Nash equilibrium I think that one must have a loop
between the players capacity to take into account the information from the other player.
It necessitates a find zero function I suppose.
I will try to find one.
Regards.
JJ