Natural computational method of two- person zero- sum games

• Autores: J.V. Talacko
• Localización: Trabajos de estadística e investigación operativa, ISSN 0041-0241, Vol. 14, Nº. 1-2, 1963, págs. 17-60
• Idioma: español
• DOI: 10.1007/bf03013694
• Texto completo no disponible (Saber más ...)
• Resumen

  • This paper displays a concise, direct, computational procedure which solves mechanically and completely every numerical problem of two-person zero-sum games. A single algorithm of general applicability reduces the optimization process of linear inequalities to elementary manipulation of the given pay-off matrix. The routine does not require a complicated translation of the particular problem into linear programs or equations. It does not involve adjustments of original data and no slack vectors or artificial variables.

    Only oneStandard Form is involved. This form is simply a bordered original pay-off matrix by two pairs of identification and indicator vectors. It contains all pertinent information in a most compact manner at every stage of realization.A single algorithm applied to the Standard Form yields the complete solution in a uniform systematic way. The realization technique is a repetitive chain-process of oxact, pivotal transformation.

    The algorithm has three parts:

    1.

    Definition of the pivot or selection of the pivot by the marginal cross-product ratios, for every iteration. This way we select the best feasible bilinear nuclei of the system, until the optimum is attained.

    2.

    Transformation routine is a process of matrix inversion by complete partitioning, step by step. We invert whole rectangular composite matrix, the whole system, not only the kernel square matrix. The marginal vectors of the standard form indicate after every iteration if the optimum solution has been attained and if the resolvent is unique or if the multiple solution exists. In the case of unique resolvent, in addition to the pair of unique strategies for both players and the value of the game, we getthe unique characteristic kernel, invariant respect to the value of the game. This characteristic kernel characterizes the pay-off matrix respect to saddle point principle as the non-singular determinant is characterized by its roots or trace.

    3.

    In the case ofmultiple solution every distinct resolvent has a distinct characteristic kernel, which unmistakably identifies the bilinear nucleus of the resolvent. We have a rule of detection of all nuclei, step by step, which satisfy the unique value of the game and we findall distinct resolvents practically without a loss of a single iteration. The set of all distinct resolvents is calledthe complete solution. The method has many advantages if the value of the game is zero and if many distinct solutions exist over any other known method. It is suitable for hand paper computation, with control column adddd and for digital somputer, because it is compact and concise.

    This algorithm has been called Symmetric, because the dual symmetry and the symmetric duality play here a most important part in the development of the procedure.