Package SALPMPE

This package implements the approximate best response iterative algorithm for approximating MPE for large scale dynamic stochastic games introduced in Farias, Saure and Weintraub (2011). Our Java/CPLEX implementation of the algorithm can be found here

See:
Description

Class Summary

ApproxAlgorithm	Defines the approximate best response iterative algorithm.
ApproxLP	Defines an instance of SALP program, builds model and recovers coefficients in approximation.
ApproxLP.prob	Defines the transition dynamics for the model (subclass).
Fdist	Defines distribution function of scrap value and entry cost random variables.
Parameters	Defines the running parameters for the SALP algorithm.
Profit	Defines the single period profit function.
Profit10	Defines the single period profit function for the capacity competition model.
Profit99	Defines the single period profit function for the quality ladder competition model.
sol_sep	Defines the separable approximating architecture.
state	Defines the representation of the industry state and associated operations.
strategy	Defines the representation of the strategy followed by firms in a given industry state.

Package approximation Description

This package implements the approximate best response iterative algorithm for approximating MPE for large scale dynamic stochastic games introduced in Farias, Saure and Weintraub (2011).

1. General Comments

• This package is for Java and requires ILOG Concert Technology to link the algorithm to CPLEX solver, which is available free of charge available to the academic community through the IBM Academic initiative.

• Methods on this package assume the model primitives described on Farias, Saure and Weintraub (2011). Later we explain how to customize the package to different model primitives.

• The method solveEquilibrium computes the approximate MPE, value function approximation and some industry statistics. Several output files are generated:
  • indicators-Nx-y.txt contains some long run statistics for the equilibrium strategy.
  • log-Nx-y.txt shows the evolution of the convergence criteria, up to convergence.
  • indlog-Nx-y.txt shows the evolution of the long run indicators and running times, up to convergence.
  • coefficients-Nx-y.txt contains equilibrium coefficients for the value function approximation.
  • values-Nx-y.txt, investment-Nx-y.txt, exit-Nx-y.txt and entry-Nx-y.txt contain the value function approximation and equilibrium investment, exit and entry strategies, respectively.

  On these files names x denotes the maximum number of firms in the industry, and y is a code for the single period profit function. Note that some of these files are generated only if the parameter small is set to true (i.e., when enumerating all states is feasible).

• All parameters are defined in the class Parameters. If you want to use the same functional forms as in Farias, Saure and Weintraub (2011) you only need to edit the Parameters.java file.

• Please write to Denis Saure with any comments, questions, or if you find an error. Also, if you end up using the package for an application please let us know.

2. Installation

• In order to use this package one should have Java installed on your server/desktop. You can download Oracle's latest Java SDK from www.oracle.com.

• You can edit any modification to this package on a regular text editor. Optionally, you can download Eclipse IDE from www.eplipse.org (this is what we used for debugging purposes).

• This package requires ILOG Concert Technology installed on your server/desktop in order to link the algorithm to the CPLEX LP solver, which is available free of charge available to the academic community through the IBM Academic initiative.

• To install the package when using Unix/Linux one should proceed as follows:
  • Make a directory called SALPMPE and unpack the content of SALPMPE.zip there.

  • Edit the file makefile indicating the path to the CPLEX installation folder (e.g. /common/opt/ilog/cplex91). You can use the find command to look for the CPLEX installation folder (e.g. type find /common -name cplex ).

  • In the SALPMPE directory type make (this compiles the code).

• To run the algorithm when using Unix/Linux one should proceed as follows:

  • Open a terminal and position it on the SALPMPE folder.

  • Modify the file parameters.java setting the algorithm's parameters according to your needs.

  • Type make clear followed by make every time you modify the source-code.

  • Type make run to run the algorithm. Alternatively you can modify the file makefile to submit the work to a grid dispatcher (see make wrap in the file for an example of this).

• When using Windows, we recommend Eclipse to install and use the package. The basic steps to install the package are:
  • Create a new project (File > New > Project). Create a package called SALPMPE (File > New > Package).

  • Import java source files located at SALPMPE.zip (File > Import > File System).

  • Add CPLEX.jar library to the project (on Package Explorer, right click over the package ->build path ->configure build path > Library >add Library); you should be able to find this file in CPLEX's local installation folder (e.g., C:\ILOG\CPLEX_Studio_AcademicResearch122\cplex\lib)

  • Modify the method loadCompact to include the path to the initial strategy to be used (compact.txt).

  • To run the algorithm go to the Run menu. Make sure to modify Parameters.java according to your needs.

  3. Customization

  We explain what classes/methods must be modified to accommodate different model primitives.

  3.1. Profit Function

  • To use a different single period profit function creat a new class including the methods profit, consur and mshare (see Profit99 for an example of such a class). Then, modify the class Profit to introduce a new profit function.

  • Introduce extra parameters required for the new profit function in Parameters and Parameters.java. In addition, update computeIndicator to report additional parameters.

  3.2. Transition Dynamics

  Transition dynamics specified in Farias, Saure and Weintraub (2011) allows a firm to jump at most one quality level (up or down) from period to period. If the transition dynamics to be implemented share this feature:
  • Modify setprob to introduce different transition dynamics.

  • Introduce extra parameters required for the new transition dynamics in Parameters and Parameters.java. In addition, update computeIndicator to report additional parameters.

  If the transition dynamics to be implemented do not share this feature:
  • Modify setprob to introduce different transition dynamics.

  • Rebuild computeCoeff according to new transition dynamics. Then, modify expectedValue, StratFromR and EntryFromR accordingly.

  • Modify sampling routines in sampleStates, and ComputeV according to new transition dynamics.

  • Introduce extra parameters required for the new transition dynamics in Parameters and Parameters.java. In addition, update computeIndicator to report additional parameters.

  3.3. Approximation Architecture

  Value function approximation under the approximation architecture in Farias, Saure and Weintraub (2011) is separable across quality levels. If the approximation architecture to be implemented share this feature:
  • Modify class sol_sep to reflect new structure of solution to the approximate LP.
  • Modify buildModel, getSolution, expectedValue, sampleRest, StratFromR, EntryFromR and ReduceBaseFunctions according to the new approximating architecture.

  • Modify reportValue and reportCoeff to report approximating architecture related outcome.

  • Introduce extra parameters required by the new approximation architecture in Parameters. In addition, update computeIndicator to report additional parameters.

  If the approximation architecture does not share this feature:
  • In addition to the modifications above, rebuild computeCoeff in order to compute Bellman operator under new approximation architecture.

  4. Exact MPE computation (for discrete actions)

  To solve for the exact MPE considering a finite and discrete set of actions, one must
  • Introduce the identity matrix as the approximation architecture, so every state in the state space is associated to a different basis (indicator) function (see Section 3.3. above).

  • Set parameter allstates=true in Parameters, so that all states in the state space are listed.

  • Optionally, modify convergenceCriteria to check uniform convergence of strategies.

  Last update:

  February, 2012

  Author:

  Denis Saure