×

Computation of equilibria in noncooperative games. (English) Zbl 1121.91006

Summary: This paper presents algorithms for finding equilibria of mixed strategy in multistage noncooperative games of incomplete information (like probabilistic blindfold chess, where at every opportunity a player can perform different moves with some probability). These algorithms accept input games in extensive form. Our main result is an algorithm for computing aeguential equilibrium, which is the most widely accepted notion of equilibrium (for mixed strategies of noncooperative probabilistic games) in mainstream economic game theory. Previously, there were no known algorithms for computing sequential equilibria strategies (except for the special case of single stage games).
The computational aspects of passage from a recursive presentation of a game to its extensive form are also discussed. For nontrivial inputs the concatenation of this procedure with the equilibrium computation is time intensive, but has low spatial requirements. Given a recursively represented game, with a position space bound \(S(n)\) and a log space computable next move relation, we can compute an example mixed strategy satisfying the sequential equilibria condition, all in space bound \(O(S(n)^{2})\), Furthermore, in space \(O(S(n)^{3})\), we can compute the connected components of mixed strategies satisfying sequential equilibria.

MSC:

91A10 Noncooperative games
91A18 Games in extensive form
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Kreps; Wilson, Sequential equilibria, Econometrics, 50, 4, 863-894 (1982), July · Zbl 0483.90092
[2] Hopcroft, J. E.; Ullman, J. D., Introduction to Automata Theory, Languages and Computation (1975), Addison-Wesley Publishing Company: Addison-Wesley Publishing Company Amsterdam · Zbl 0307.68053
[3] Lewis, H.; Papadimitriou, C. H., Elements of Theory of Computation (1981), Prentice-Hall, Inc. · Zbl 0464.68001
[4] Selten, R., Spieltheoretische behandlung eines oligopolmodells mit nachfragetragheit, Zeitschrift fur die gesamte Staatswissenschaft, 121, 301-324 (1975)
[5] Renegar, J., On the computational complexity and geometry of the first-order theory of the Reals: Part III—quantifier elimination, (Technical Report 856 (1989), School of Operations Research and Industrial Engineering, Cornell University: School of Operations Research and Industrial Engineering, Cornell University Englewood Cliffs, NJ), August · Zbl 0798.68073
[6] Renegar, J., On the computational complexity and geometry of the first-order theory of the Reals; Part I, (Technical Report 853 (1989), School of Operations Research and Industrial Engineering, Cornell University: School of Operations Research and Industrial Engineering, Cornell University Ithaca, NY), July
[7] Renegar, J., On the computational complexity and geometry of the first-order theory of the Reals: Part II, (Technical Report 854 (1989), School of Operations Research and Industrial Engineering: School of Operations Research and Industrial Engineering Ithaca, NY), July
[8] Renegar, J., On the computational complexity of approximating solutions for Real algebraic formulae, (Technical Report 858 (1989), School of Operations Research and Industrial Engineering, Cornell University: School of Operations Research and Industrial Engineering, Cornell University Ithaca, NY), August · Zbl 0768.65022
[9] Canny, J., A new algebraic method for robot motion planning and real geometry, (Proceedings of the 28th Annual IEEE Symposium on Foundations of Computer Science (1987)), 39-48, October
[10] Renegar, J., A faster \(p\)-apace algorithm for deciding the existential theory of real closed fields, (Proceedings of the 29th Annual IEEE Symposium on Foundations of Computer Science (1988)), 291-295, October
[11] Kozen, D.; Yap, C. K., Algebraic cell decomposition in nc, (Proceedings of the \(26^{th}\) Annual IEEE Symposium on Foundations of Computer Science (1985)), 515-521, October
[12] Dijkstra, E., A Discipline of Programming (1976), Prentice-Hall, Inc.: Prentice-Hall, Inc. Ithaca, NY · Zbl 0368.68005
[13] Hoare, C., An axiomatic basis for computer programming, Communications of the ACM, 12, 10, 576-583 (1969) · Zbl 0179.23105
[14] Floyd, R., Assigning meanings to programs, (Proc. Symposium Applied Math, 19 (1967)), 19-32 · Zbl 0189.50204
[15] Hantler, S.; King, J., An introduction to proving the correctness of programs, ACM Computing Surveys, 8, 3, 331-353 (1976) · Zbl 0345.68009
[16] King, J., Proving programs to be correct, IEEE Transactions on Computers, C-20, 11, 1331-1336 (1971) · Zbl 0231.68014
[17] Owicki, S.; Gries, D., An axiomatic proof technique for parallel programs, Acta Informatics, 6, 319-340 (1976) · Zbl 0312.68011
[18] Manna, Z.; Pnueli, A., Temporal verification of concurrent programs, (Boyer, R.; Strother, J., The Correctness Problem in Computer Science (1981), Academic Press) · Zbl 0206.17503
[19] Deutsch, L., An Interactive Program Verifier, (Ph.D. Thesis (1973), University of California)
[20] Good, D.; Cohen, R.; Hoch, C.; Hunter, L.; Har, D., Report on the language Gypsy, (Technical Report ICSCA-CMP-10 (1978), The University of Texas: The University of Texas Berkeley, CA)
[21] Blum, M.; Kannan, S., Designing programs that check their work, (Proceedings of the \(21^{st}\) Annual ACM Symposium on Theory of Computing (1989)), 86-97, May
[22] Apt, R.; Roever, W., A proof system for communicating sequential processes, ACM Transactions on Programming Languages and Systems, 2, 3, 359-385 (1981) · Zbl 0468.68023
[23] Levin, G. M.; Gries, D., A proof technique for communicating sequential process, Acta Information, 15, 281-302 (1981) · Zbl 0463.68034
[24] Owicki, S.; Gries, D., An axiomatic proof technique for parallel programs, Acta Informatica, 6, 319-340 (1976) · Zbl 0312.68011
[25] Arnon, D. S.; Mignotte, M., On mechanical quantifier elimination for elementary algebra and geometry, Journal of Symbolic Computation, 5, 237-259 (1988) · Zbl 0644.68051
[26] Chandra, A. K.; Stockmeyer, L. J., Alternation, (Proceedings of 17th Annual IEEE Symposium on Foundations of Computer Science (1976)), 98-108, October
[27] Chandra, A. K.; Kozen, D. C.; Stockmeyer, L. J., Alternation, Journal of ACM, 28, 1, 114-133 (1981) · Zbl 0473.68043
[28] Reif, J. H., The complexity of two-player games of incomplete information, Journal of Computer and System Sciences, 29, 2, 274-301 (1984) · Zbl 0551.90100
[29] Azhar, S.; Peterson, G. L.; Reif, J. H., Decision algorithms for multiplayer non-cooperative games of incomplete information, Journal of Computers and Mathematics with Applications, 43, 179-206 (2002), Jan. · Zbl 1011.91026
[30] Azhar, S.; Peterson, G. L.; Reif, J. H., Lower bounds for multiplayer non-cooperative games of incomplete information, Journal of Computers and Mathematics with Applications, 41, 957-992 (2001), April · Zbl 0991.91007
[31] Papadimitriou, C. H., Games against nature, (Proceedings of 24th IEEE Symposium on Foundations of Computer Science (1983)), 446-450, October
[32] Papadimitriou, C. H., Games against nature, Journal of Computer and System Sciences, 31, 288-301 (1985) · Zbl 0583.68020
[33] Babai, L., Trading group theory for randomness, (Proceedings of the 17th Annual ACM Symposium on Theory of Computing (1985)), 421-429, May
[34] Goldwasser, S.; Miceli, S.; Rackoff, C., The knowledge complexity of interactive protocols, (Proceedings of the 17th Annual ACM Symposium on Theory of Computing (1985)), 291-304, May · Zbl 0900.94025
[35] Goldwasser, S.; Sipser, M., Public coins versus private coins in interactive proof systems, (Proceedings of the 18th Annual ACM Symposium on Theory of Computing (1986)), May
[36] Shamir, A., \( Ip = p\) space, (Proceedings of the \(31^{st}\) Annual IEEE Symposium on Foundations of Computer Science (1990)), 11-15, October
[37] Condon, A.; Ladner, R., Probabilistic Game Automata, Journal of Computer and System Sciences, 30, 3, 452-489 (1988), June · Zbl 0682.68072
[38] Blum, L.; Shub, M.; Smale, S., On a theory of computation and complexity over the real numbers: NP-completeness, recursive functions and universal machines, Bulletin of American Mathematical Society, 21, 1, 1-46 (1989), July · Zbl 0681.03020
[39] von Neumann, J.; Morgenstern, O., Theory of Games and Economic Behavior (1953), Princeton University Press: Princeton University Press Austin, Texas · Zbl 0053.09303
[40] Kuhn, H., (Extensive Games and the Problem of Information, Volume 2 (1953), Princeton University Press: Princeton University Press Princeton, NJ), 193-216
[41] Kohlberg, E.; Mertens, J.-F., On the strategic stability of equilibria, Econometrics, 54, 1003-1037 (1986), September · Zbl 0616.90103
[42] Nash, J., Noncooperative games, Annals of Mathematics, 54, 443-460 (1951)
[43] Kakutani, S., A generalization of Brouwer’s fixed point theorem, Duke Mathematical Journal, 8, 457-458 (1944) · JFM 67.0742.03
[44] Bernheim, B. D., Rationalizable strategic behavior, Econometrics, 52, 1007-1028 (1984), July · Zbl 0552.90098
[45] Pearce, D. G., Rationalizable strategic behavior and the problem of perfection, Econometrics, 52, 1029-1050 (1984) · Zbl 0552.90097
[46] Moulin, H., Game Theory for Social Sciences, ((1986), New York University Press: New York University Press Princeton, NJ), 129-146
[47] Grote, J., Global theory of games, J. of Mathematical Economics, 1, 3, 223-236 (1974) · Zbl 0299.90029
[48] McLennan, A., Consistent conditional systems in noncooperative game theory, International Journal of Game Theory, 18 (1989) · Zbl 0677.90092
[49] Csanky, L., Fast parallel matrix inversion algorithms, SIAM J. Computing, 5, 618-623 (1976) · Zbl 0353.68063
[50] Hen-Or, M.; Kozen, D.; Reif, J. H., The complexity of elementary algebra and geometry, Journal of Computer and System Sciences, 32, 251-264 (1986) · Zbl 0634.03031
[51] Ben-Or, M.; Feig, E.; Kozen, D.; Tiwari, P., A fast parallel algorithm for determining all roots of a polynomial with real roots, SIAM Journal of Computing, 17, 6, 1081-1092 (1988), December · Zbl 0663.68047
[52] McLennan, A., Justifiable beliefs in sequential equilibrium, Econometrics, 53, 889-904 (1985), July · Zbl 0587.90103
[53] Cho, I.-K., A refinement of sequential equilibrium, Econometrics, 55, 1367-1389 (1987), November · Zbl 0641.90095
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.