The polynomial hierarchy and a simple model for competitive analysis.(English)Zbl 0588.90053
The multi-level linear programs ofW. Candler andR. Norton [”Multi-level programming and development policy”, World Bank Staff Working Paper No.258, Washington (1977)] andW. Candler andR. Townsley [Computers Oper. Res. 9, 59-76 (1982)] are a simple class of sequenced-move games, in which players are restricted in their moves only by common linear constraints, and each seeks to optimize a fixed linear criterion function in his/her own continuous variables and those of other players. All data of the game and earlier moves are known to a player when he/she is to move. The one-player case is just linear programming.
We show that questions concerning only the value of these games exhibit complexity which goes up all levels of the polynomial hierarchy and appears to increase with the number of players.
For three players, the games allow reduction of the \(\Sigma_ 2\) and \(\Pi_ 2\) levels of the hierarchy. These levels essentially include computations done with branch-and-bound, in which one is given an oracle which can instantaneously solve NP-complete problems (e.g., integer linear programs). More generally, games with \((p+1)\) players allow reductions of \(\Sigma_ p\) and \(\Pi_ p\) in the hierarchy.
An easy corollary of these results is that value questions for two-player (bi-level) games of this type is NP-hard.
We show that questions concerning only the value of these games exhibit complexity which goes up all levels of the polynomial hierarchy and appears to increase with the number of players.
For three players, the games allow reduction of the \(\Sigma_ 2\) and \(\Pi_ 2\) levels of the hierarchy. These levels essentially include computations done with branch-and-bound, in which one is given an oracle which can instantaneously solve NP-complete problems (e.g., integer linear programs). More generally, games with \((p+1)\) players allow reductions of \(\Sigma_ p\) and \(\Pi_ p\) in the hierarchy.
An easy corollary of these results is that value questions for two-player (bi-level) games of this type is NP-hard.
Keywords:
NP-completeness;computational complexity;Stackelberg strategies;multi- level linear programs;sequenced-move games;polynomial hierarchyCite
Full Text:DOI
References:
| [1] | J.F. Bard, ”Sequential optimization in hierarchical structures”, Working Paper 82-12, College of Business Administration, Northeastern University (Boston, MA, 1982). |
| [2] | J.F. Bard and J.E. Falk, ”An explicit solution to the multi-level programming problem”,Computers and Operations Research 9 (1982) 77–100. ·doi:10.1016/0305-0548(82)90007-7 |
| [3] | T. Baker, J. Gill and R. Solovay, ”Relativizations of theP = ?NP questions”,SIAM Journal on Computing 4 (1975) 431–442. ·Zbl 0323.68033 ·doi:10.1137/0204037 |
| [4] | W.F. Bialas and M.H. Karwan, ”On two-level optimization”,IEEE Transactions on Automatic Control AC-27 (1982) 211–215. ·Zbl 0487.90005 |
| [5] | W. Candler and R. Norton, ”Multi-level programming and development policy”, World Bank Staff Working Paper no. 258, IBRD (Washington, DC, 1977). |
| [6] | W. Candler and R. Townsley, ”A linear two-level programming problem”,Computers and Operations Research 9 (1982) 59–76. ·doi:10.1016/0305-0548(82)90006-5 |
| [7] | V. Chvatal, ”Rational behaviour and computational complexity”, Technical Report SOCS-78.9, McGill University (Montreal, 1978). |
| [8] | S.A. Cook, ”The complexity of theorem proving procedures”,Proceedings of the Third Annual ACM Symposium on Theory of Computing (1971) 151–158. ·Zbl 0253.68020 |
| [9] | J. Fortuny and B. McCarl, ”Multi-level programming”, Industrial Engineering Department, Purdue University (West Lafayette, IN, 1979). ·Zbl 0459.90067 |
| [10] | M. Garey and D.S. Johnson,Computers and intractibility (W.H. Freeman, San Francisco, 1979). |
| [11] | R.G. Jeroslow, ”Bracketing discrete problems by two problems of linear optimization”, in:Operations Research Verfahren XXV (Verlag Anton Hain, Meisenheim am Glan, 1977) pp. 205–216. ·Zbl 0398.90076 |
| [12] | R.M. Karp, ”Reducibility among combinatorial problems”, in: R.E. Miller and J.W. Thatcher, eds.,Complexity of computer computations (Plenum Press, New York, 1972) pp. 85–104. |
| [13] | L.G. Khachiyan, ”A polynomial algorithm for linear programming”,Doklady Akademii Nauk SSR 244 (1979) 1093–1096 (English translation in Soviet Mathematics Doklady 20, 191–194). ·Zbl 0414.90086 |
| [14] | T.S. Motzkin, H. Raiffa, G.L. Thompson and R.M. Thrall, ”The double description method”, in:Contributions to the theory of games II, H.W. Kuhn and A.W. Tucker, eds., (Princeton University Press, Princeton, NJ, 1953) pp. 51–73. |
| [15] | N.J. Nilsson,Problem-solving methods in artificial intelligence (McGraw-Hill, New York, 1971). |
| [16] | C.H. Papadimitriou, ”Games against nature”,Proceedings of the Twenty Fourth Symposium on the Foundations of Computer Science, 1983. ·Zbl 0583.68020 |
| [17] | K. Pasumarty, ”Product positioning in a competitive market”, College of Management, Georgia Institute of Technology (Atlanta, GA, 1982). |
| [18] | E.C. Prescott and M. Visscher, ”Sequential location among firms with foresight”,Bell Journal of Economics 8 (1977) 378–393. ·doi:10.2307/3003293 |
| [19] | H. Rogers,Theory of recursive functions and effective computability (McGraw-Hill, New York, 1967). ·Zbl 0183.01401 |
| [20] | H. Scarf (with T. Hansen)The computation of economic equilibria (Yale University Press, New Haven, 1973). ·Zbl 0311.90009 |
| [21] | M. Simaan and J.B. Cruz, Jr., ”On the Stackelberg strategy in nonzero-sum games”,Journal of Optimization Theory and Applications 11 (1973) 533–555. ·doi:10.1007/BF00935665 |
| [22] | H.D. Sherali, A.L. Soyster and F.H. Murphy, ”Stackelberg-Nash-Cournot equilibria characterizations and computations”,Operations Research 31 (1983) 253–276. ·Zbl 0506.90011 ·doi:10.1287/opre.31.2.253 |
| [23] | H.D. Sherali, ”A multiple leader Stackelberg model and analysis”,Operations Research 32 (1984) 390–404. ·Zbl 0581.90008 ·doi:10.1287/opre.32.2.390 |
| [24] | R. Smullyan,First order logic (Springer-Verlag, New York, 1968). ·Zbl 0172.28901 |
| [25] | H. Stackelberg,Marktform und Gleichgewicht (Julius Springer, Vienna, 1934). |
| [26] | L.J. Stockmeyer, ”The polynomial-time hierarchy”,Theoretical Computer Science 3 (1977) 1–22. ·Zbl 0353.02024 ·doi:10.1016/0304-3975(76)90061-X |
| [27] | J. Stoer and C. Witzgall,Convexity and optimization in finite dimensions: I (Springer-Verlag, New York, 1970). ·Zbl 0203.52203 |
| [28] | C. Wrathall, ”Complete sets and the polynomial time hierarchy”,Theoretical Computer Science 3 (1977) 23–33. ·Zbl 0366.02031 ·doi:10.1016/0304-3975(76)90062-1 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
