Thursday, April 2, 2015

Diagonalization Algorithm

Following

image

we can write a simple diagonalization / relaxation algorithm in GAMS that computes the oligopolistic market equilibrium of the problem described here: http://yetanothermathprogrammingconsultant.blogspot.com/2015/03/oligopolistic-producer-behavior-or-why.html.

In this algorithm we solve a sub-problem where we maximize profits (varying the output) for each firm while we keep the output of the other firms constant in the sub-problem (i.e. we take them from the previous iteration of the algorithm). The sub-problem is now a straightforward NLP. It looks like:

image

We run this model in a loop until it converges: the quantities produced don’t change anymore:

 image

We see we can reproduce the results from the paper:

image

----    104 PARAMETER trace 

             firm1       firm2       firm3       firm4       firm5        diff

iter0       10.000      10.000      10.000      10.000      10.000
iter1       55.029      56.193      55.760      53.414      49.142     219.538
iter2       27.188      32.991      36.158      36.505      34.382     102.314
iter3       42.618      46.760      48.008      46.372      42.300      58.834
iter4       33.565      38.853      41.170      40.545      37.475      34.451
iter5       38.886      43.533      45.192      43.922      40.220      20.146
iter6       35.778      40.804      42.835      41.927      38.583      11.827
iter7       37.607      42.411      44.218      43.092      39.534       6.935
iter8       36.536      41.470      43.406      42.406      38.972       4.071
iter9       37.165      42.022      43.883      42.808      39.301       2.388
iter10      36.796      41.698      43.603      42.572      39.108       1.402
iter11      37.013      41.888      43.767      42.710      39.221       0.822
iter12      36.886      41.777      43.671      42.629      39.154       0.483
iter13      36.960      41.842      43.727      42.677      39.193       0.283
iter14      36.916      41.804      43.694      42.649      39.170       0.166
iter15      36.942      41.826      43.714      42.665      39.184       0.098
iter16      36.927      41.813      43.702      42.656      39.176       0.057
iter17      36.936      41.821      43.709      42.661      39.181       0.034
iter18      36.931      41.816      43.705      42.658      39.178       0.020
iter19      36.934      41.819      43.707      42.660      39.180       0.012
iter20      36.932      41.818      43.706      42.659      39.179       0.007

It is always nice to see that we can reproduce some results.

Notes:

  • Note: to speed up the iterations we can set solprint and solvelink:
    image 
  • Patrick Harker has been appointed as the next president of the Fed in Philadelphia [link].
  • The trace output illustrates the linear convergence of this algorithm: the difference is halved by each iteration.
  • This algorithm is also known as the PIES-q algorithm [link].