Sobre la finitud de los Equilibros de Nash en juegos genéricos

Abstract

RESUMEN: En esta memoria, realizamos un estudio sobre la estructura y la cuantificación de los equilibrios de Nash en juegos finitos no cooperativos. Un juego finito es una interacción entre distintos agentes en la cuál cada uno posee un número finito de estrategias y obtiene una recompensa en función de su elección y la del resto de los jugadores. El término “no cooperativo” hace referencia a que los participantes eligen su estrategia de forma independiente y buscando el mayor beneficio personal. Un equilibrio de Nash es una estrategia grupal en las que cada agente, habiéndose fijando la elección del resto, consigue la máxima recompensa posible, o lo que es lo mismo, en los equilibrios de Nash todos los jugadores se quedan “contentos” con su elección, ya que no podían haber elegido otra mejor. En el Capítulo 1, reproduciremos la famosa Tesis de John F. Nash de 1950 en la que demostró la existencia de estos equilibrios en todo juego no cooperativo, y por la cuál, dada su relevancia y utilidad, obtuvo el premio Nobel en ciencias Económicas en 1994. En el Capítulo 2, estudiaremos primero la relación entre el conjunto de equilibrios y la Geometría Algebraica, viendo que es un conjunto semi-algebraico y que, por lo tanto, puede estudiarse como las soluciones de un sistema de ecuaciones e inecuaciones. También introduciremos las funciones multi-homogéneas, ya que veremos que el sistema que caracteriza los equilibrios es multi-homogéneo. Después analizaremos el conjunto de subjuegos de un juego dado y un tipo concreto de equilibrios: los totalmente mezclados. Por ultimo, daremos una demostración “from scratch” sobre la finitud de los equilibrios de Nash en juegos elegidos genéricamente. Hemos añadido también dos Apéndices en los que se recopilan notaciones básicas y resultados que utilizaremos a lo largo del trabajo. El Apéndice A trata los conjuntos y funciones convexas, y el Apéndice B describe términos de geometría algebraica, polinomios multihomogéneos y la relación entre los politopos y la cota BKK.

ABSTRACT: In this work we will study the structure and quantification of Nash equilibria in non-cooperative finite games. A finite game consist in an interaction between a group of agents in which each of them has a finite number of strategies and a payoff function that sets a profit depending of the choices of all the players. The term “Non-cooperative” means that players can not form alliances so each one of them seeks its greatest benefit. A Nash equilibria is a commun strategie in which each player, having fixed the strategies of the rest of them, get the maximun benefit, and therefore, in a Nash equilibria all the players are “satisfied” with their choice because for that situation, they could not choose a better strategy. In Chapter 1, we exhibit John F. Nash tesis (1950) in which he prooved that for any finite non-cooperative game exits at least one equilibria point. Because of the influence of his work in the field of Economics, he recived the Nobel Prize in Economic Science in 1994. In Chapter 2, we will first study the set of Nash equlibria as a semi-algebraic set, so Algebraic Geometry will be introduced to describe it as the solutions of a system of equations and inequations. Moreover, we will introduce the multi-homogeneous functions because the system we will use to describe the equilibria points is multi-homogeneous. Then, we will analize the set of sub-games of a game, and a particular type of equilibria: the totally mixed equilibria. Ultimately, we will proof by scratch the finitude of Nash equilibria in generic games. The manuscript is completed with 2 Appendices which recall some basic notations and facts used along the work. Appendix A describes propieties of convex sets and functions and Appendix B shows different terms and notations about Algebraic Geometry, multihomogeneous polynomial and the relation between Newton Polytopes and the BKK theorem.