A Two-Period Stochastic Linear Programming Game

Abstract

We formulate and discuss a model of two-period stochastic optimization which allows for the possibility of the probability distribution over a non-empty finite set of states of nature-exactly one member of which will be realized in the future period- to depend on the control variable chosen in the initial period. In the second and terminal period, the decision maker chooses the value of a control variable vector which along with the control variable vector chosen in the initial period, solve a linear programming problem. The parameters of the linear programming are determined by an uncertain state of nature that is realized at the beginning of the terminal period. In order to obtain specific results, we assume that in the initial period, the decision maker can choose any one alternative from a finite set of alternatives, each such alternative being “a system of linear inequality constraints.” It is further assumed that solution sets of any two different systems are mutually disjoint and the probability distribution of the uncertain components of the state variables that is realized in the second period is determined by the system of linear inequalities chosen in the initial period. We refer to the overall problem as a “two-period stochastic linear programming game”. Our first result for a two-period stochastic linear programming game is that the optimal value for such a game as well as the optimal solutions for each of the finite number of stochastic linear programs can be found by solving a linear programming problem and our second result in this context says that the (optimal) solution for the dual of this linear programming contains a component that determines “at least one” stochastic linear programming problem any solution of which when substituted in its objective function, yields the optimal value of the two-period stochastic linear programming game. There is no need to solve any other subproblem or the primal problem to derive the optimal value of the game.

AMS Classifications: 90C05, 90C15, 90C39, 90C46, 91A65

JEL Classifications: C61, C79, D81