Artículo

Este artículo es de Acceso Abierto y puede ser descargado en su versión final desde nuestro repositorio
Consulte el artículo en la página del editor
Consulte la política de Acceso Abierto del editor

Abstract:

We present an algorithm to compute a parametric description of the totally mixed Nash equilibria of a generic game in normal form with a fixed structure. Using this representation, we also show an algorithm to compute polynomial inequality conditions under which a game has the maximum possible number of this kind of equilibria. Then, we present symbolic procedures to describe the set of isolated totally mixed Nash equilibria of an arbitrary game and to compute, under certain general assumptions, the exact number of these equilibria. The complexity of all these algorithms is polynomial in the number of players, the number of each player's strategies and the generic number of totally mixed Nash equilibria of a game with the considered structure. © 2009 Elsevier Ltd. All rights reserved.

Registro:

Documento: Artículo
Título:A parametric representation of totally mixed Nash equilibria
Autor:Jeronimo, G.; Perrucci, D.; Sabia, J.
Filiación:Departamento de Matemática, FCEN, Universidad de Buenos Aires, Ciudad Universitaria, 1428 Buenos Aires, Argentina
Departamento de Ciencias Exactas, CBC, Universidad de Buenos Aires, Ciudad Universitaria, 1428 Buenos Aires, Argentina
CONICET, Argentina
Palabras clave:Complexity; Multihomogeneous resultants; Nash equilibria; Noncooperative game theory; Polynomial equation solving; Complexity; Multihomogeneous resultants; Nash equilibria; Noncooperative game theory; Polynomial equation solving; Polynomials; Game theory
Año:2009
Volumen:58
Número:6
Página de inicio:1126
Página de fin:1141
DOI: http://dx.doi.org/10.1016/j.camwa.2009.06.043
Título revista:Computers and Mathematics with Applications
Título revista abreviado:Comput Math Appl
ISSN:08981221
CODEN:CMAPD
PDF:https://bibliotecadigital.exactas.uba.ar/download/paper/paper_08981221_v58_n6_p1126_Jeronimo.pdf
Registro:https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_08981221_v58_n6_p1126_Jeronimo

Referencias:

  • von Neumann, J., Morgenstern, O., (1944) Theory of Games and Economic Behaviour, , Princeton University Press, Princeton, NJ
  • Nash, J.F., Non-cooperative games (1951) Ann. of Math. (2), 54, pp. 286-295
  • Sturmfels, B., Solving systems of polynomial equations (2002) CBMS Regional Conference Series in Mathematics, 97. Published for the Conference Board of the Mathematical Sciences, Washington, DC, , American Mathematical Society, Providence, RI
  • Lemke, C.E., Howson Jr., J.T., Equilibrium points of bimatrix games (1964) J. Soc. Indust. Appl. Math., 12, pp. 413-423
  • von Stengel, B., Computing equilibria for two person games (2002) Handbook of Game Theory with Economic Applications, 3, pp. 1723-1759. , Aumann R.J., and Hart S. (Eds)
  • Scarf, H., The approximation of fixed points of a continuous mapping (1967) SIAM J. Appl. Math., 15, pp. 1328-1343
  • R. Datta, Finding all Nash equilibria of a finite game using polynomial algebra, Econ. Theory (doi:10.1007/s00199-009-0447-z); Herings, P., Peeters, R., A globally convergent algorithm to compute all Nash equilibria for n person games (2005) Ann. Oper. Res., 137, pp. 349-368
  • Sommese, A., Wampler, C.W., (2005) The Numerical Solution of Systems of Polynomials Arising in Engineering and Science, , World Scientific Publishing Co. Pte. Ltd., Hackensack, NJ
  • http://gambit.sourceforge.net, R. McKelvey, A. McLennan, T. Turocy, Gambit: Software Tools for Game Theory, Version 0.2007.01.30, 2007; Basu, S., Pollack, R., Roy, M.-F., (2006) Algorithms in Real Algebraic Geometry. second ed., , Springer Verlag, Berlin
  • Lipton, R., Markakis, E., Nash equilibria via polynomial equations (2004) Lecture Notes in Comput. Sci., 2976, pp. 413-422. , Proc. of the 6th Latin American Symposium on Theoretical Informatics
  • McKelvey, R., McLennan, A., Computation of equilibria in finite games (1996) Handb. of Comput. Econom., 1, pp. 87-142
  • Lazard, D., Résolution des systèmes d'équations algébriques (1981) Theoret. Comput. Sci., 15 (1), pp. 77-110
  • A.L. Chistov, D. Yu, Grigoriev, Subexponential-time solving systems of algebraic equations I, II, Steklov Mathematical Institute, Leningrad department, LOMI Preprints E-9-83, E-10-83, Leningrad, 1983; Giusti, M., Heintz, J., La détermination des points isolés et de la dimension d'une variété algébrique peut se faire en temps polynomial (1993) Sympos. Math., XXXIV, pp. 216-256. , Computational Algebraic Geometry and Commutative Algebra (Cortona, 1991), Cambridge Univ. Press, Cambridge (in French)
  • Rouillier, F., Solving zero-dimensional systems through the rational univariate representation (1999) Appl. Algebra Engrg. Comm. Comput., 9 (5), pp. 433-461
  • Jeronimo, G., Sabia, J., Effective equidimensional decomposition of affine varieties (2002) J. Pure Appl. Algebra, 169 (2-3), pp. 229-248
  • Giusti, M., Heintz, J., Hägele, K., Morais, J.E., Pardo, L.M., Montaña, J.L., Lower bounds for Diophantine approximations. Algorithms for algebra (Eindhoven, 1996) (1997) J. Pure Appl. Algebra, 117-118, pp. 277-317
  • Giusti, M., Heintz, J., Morais, J.E., Morgenstern, J., Pardo, L.M., Straight-line programs in geometric elimination theory (1998) J. Pure Appl. Algebra, 124 (1-3), pp. 101-146
  • Giusti, M., Lecerf, G., Salvy, B., A Gröbner free alternative for polynomial system solving (2001) J. Complexity, 17 (1), pp. 154-211
  • Lecerf, G., Computing the equidimensional decomposition of an algebraic closed set by means of lifting fibers (2003) J. Complexity, 19 (4), pp. 564-596
  • Cox, D., Little, J., O'Shea, D., Ideals, varieties, and algorithms (2007) Undergraduate Texts in Mathematics, , An Introduction to Computational Algebraic Geometry and Commutative Algebra. third ed., Springer, New York
  • Jeronimo, G., Sabia, J., Computing multihomogeneous resultants using straight-line programs (2007) J. Symbolic Comput., 42 (1-2), pp. 218-235
  • Schost, E., Computing parametric geometric resolutions (2003) Appl. Algebra Engrg. Comm. Comput., 13 (5), pp. 349-393
  • Heintz, J., Jeronimo, G., Sabia, J., Solernó, P., (2005) Intersection theory and deformation algorithms: The multi-homogeneous case, , manuscript
  • McKelvey, R., McLennan, A., The maximal number of regular totally mixed Nash equilibria (1997) J. Econom. Theory, 72 (2), pp. 411-425
  • Lazard, D., Rouillier, F., Solving parametric polynomial systems (2007) J. Symbolic Comput., 42 (6), pp. 636-667
  • Weispfenning, V., Comprehensive Gröbner bases (1992) J. Symbolic Comput., 14 (1), pp. 1-29
  • Shafarevich, I., (1974) Basic Algebraic Geometry, , Springer-Verlag, Berlin
  • Heintz, J., Definability and fast quantifier elimination in algebraically closed fields (1983) Theoret. Comput. Sci., 24, pp. 239-277
  • von zur Gathen, J., Parallel arithmetic computations: A survey (1986) Lecture Notes in Comput. Sci., 33, pp. 93-112. , Proc. 12th FOCS, Bratislava
  • Bürgisser, P., Clausen, M., Shokrollahi, M.A., (1997) Grundlehren der Mathematischen Wissenschaften, 315. , Springer-Verlag, Berlin
  • Heintz, J., Schnorr, C.-P., Testing polynomials which are easy to compute (1982) Monogr. Enseign. Math., 30, pp. 237-254
  • Osborne, M.J., Rubinstein, A., (1994) A Course in Game Theory, , MIT Press, Cambridge MA
  • Morgan, A., Sommese, A., Wampler, C., A product-decomposition bound for Bézout numbers (1995) SIAM J. Numer. Anal., 32 (4), pp. 1308-1325
  • McLennan, A., The maximum number of real roots of a multihomogeneous system of polynomial equations (1999) Beiträge Algebra Geom., 40 (2), pp. 343-350
  • Bernstein, D.N., The number of roots of a system of equations (1975) Functional Anal. Appl., 9 (3), pp. 183-185
  • Oka, M., Non-degenerate complete intersection singularity (1997) Actualités Mathématiques, , Hermann, Paris
  • Kronecker, L., Grundzüge einer arithmetischen Theorie de algebraischen Grössen (1882) J. Reine Angew. Math., 92, pp. 1-122
  • König, J., (1903) Einleitung in die allgemeine Theorie der algebraischen Gröszen, , Druck und Verlag von B.G. Teubner, Leipzig
  • Durvye, C., Lecerf, G., A concise proof of the Kronecker polynomial system solver from scratch (2008) Expo. Math., 26 (2), pp. 101-139
  • Minimair, M., Sparse resultant under vanishing coefficients (2003) J. Algebraic Combin., 18 (1), pp. 53-73
  • González Vega, L., Lombardi, H., Recio, T., Roy, M.-F., Spécialisation de la suite de Sturm. RAIRO (1994) Inform. Théor. Appl., 28 (1), pp. 1-24
  • Lickteig, T., Roy, M.-F., Sylvester-Habicht sequences and fast Cauchy index computation (2001) J. Symbolic Comput., 31 (3), pp. 315-341
  • Berkowitz, S.J., On computing the determinant in small parallel time using a small number of processors (1984) Inform. Process. Lett., 18 (3), pp. 147-150
  • Strassen, V., Vermeidung von divisionen (1973) J. Reine Angew. Math., 264, pp. 184-202
  • Brown, W., Traub, J., On Euclid's algorithm and the theory of subresultants (1971) J. Assoc. Comput. Mach., 18, pp. 505-514
  • Ben-Or, M., Kozen, D., Reif, J., The complexity of elementary algebra and geometry (1986) J. Comput. System Sci., 32 (2), pp. 251-264
  • Canny, J., Improved algorithms for sign determination and existential quantifier elimination (1993) Comput. J., 36 (5), pp. 409-418
  • von zur Gathen, J., Gerhard, J., (1999) Modern Computer Algebra, , Cambridge University Press, New York
  • Coste, M., Roy, M.-F., Thom's lemma, the coding of real algebraic numbers and the computation of the topology of semi-algebraic sets (1988) J. Symbolic Comput., 5 (1-2), pp. 121-129
  • Zippel, R., Probabilistic algorithms for sparse polynomials (1979) Lecture Notes in Comput. Sci., 72, pp. 216-226. , Symbolic and algebraic computation (EUROSAM '79, Internat. Sympos., Marseille, 1979)
  • Giusti, M., Hägele, K., Lecerf, G., Marchand, J., Salvy, B., The projective Noether Maple package: Computing the dimension of a projective variety (2000) J. Symbolic Comput., 30 (3), pp. 291-307
  • Sturmfels, B., On the Newton polytope of the resultant (1994) J. Algebraic Combin., 3 (2), pp. 207-236
  • Pedersen, P., Sturmfels, B., Product formulas for resultants and Chow forms (1993) Math. Z., 214, pp. 377-396

Citas:

---------- APA ----------
Jeronimo, G., Perrucci, D. & Sabia, J. (2009) . A parametric representation of totally mixed Nash equilibria. Computers and Mathematics with Applications, 58(6), 1126-1141.
http://dx.doi.org/10.1016/j.camwa.2009.06.043
---------- CHICAGO ----------
Jeronimo, G., Perrucci, D., Sabia, J. "A parametric representation of totally mixed Nash equilibria" . Computers and Mathematics with Applications 58, no. 6 (2009) : 1126-1141.
http://dx.doi.org/10.1016/j.camwa.2009.06.043
---------- MLA ----------
Jeronimo, G., Perrucci, D., Sabia, J. "A parametric representation of totally mixed Nash equilibria" . Computers and Mathematics with Applications, vol. 58, no. 6, 2009, pp. 1126-1141.
http://dx.doi.org/10.1016/j.camwa.2009.06.043
---------- VANCOUVER ----------
Jeronimo, G., Perrucci, D., Sabia, J. A parametric representation of totally mixed Nash equilibria. Comput Math Appl. 2009;58(6):1126-1141.
http://dx.doi.org/10.1016/j.camwa.2009.06.043