Abstract
We considerS-games in which the setS is the parametric curve{(p 1 (t),⋯, p n(t)): t ∈ [0, 1]} and thep i(t) are real polynomials. These games will be referred to asS n -games. Two iterative algorithms are given in the case ofn = 2. One gives linear convergence to an optimal of player I, and the other gives monotone convergence. In the case of arbitraryn we give an algorithm of the cutting plane family converging to the value. The principal features of this algorithm are that the hyperplanes arise intrinsically as tangents to an associated concave function which is not in general differentiable, and the linear subproblems arise as matrix games. Because of the latter property inactive constraints are in principle automatically dropped. We give a game theoretic convergence proof. This algorithm may be used multiply for bounding optimals of player I.
Similar content being viewed by others
References
D. Blackwell and M.A. Girshick,Theory of games and statistical decisions (Wiley, New York, 1954).
I. Glicksberg, “A derivative test for finite solutions of games”,Proceedings of the American Mathematical Society 4 (1953) 895–897.
J.E. Kelley, “The cutting plane method for solving convex programs”,Society for Industrial and Applied Mathematics Journal of Applied Mathematics 8 (1960) 703.
A.F. Veinott, Jr., “The supporting hyperplane method for unimodal programming”,Journal of the Operations Research Society of America 15 (1967) 147.
L.C. Westphal and A.R. Stubberud, “The associated maximum problem for separable games”,Mathematical Programming (1973) 374–380.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Troutt, M.D. Algorithms for non-convexS n -games. Mathematical Programming 14, 332–348 (1978). https://doi.org/10.1007/BF01588975
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF01588975