En teoría de juegos , un juego de bimatrix es un juego simultáneo para dos jugadores en el que cada jugador tiene un número finito de acciones posibles. El nombre proviene del hecho de que la forma normal de tal juego se puede describir mediante dos matrices : matriz describiendo los pagos del jugador 1 y la matriz describiendo los pagos del jugador 2. [1]
El jugador 1 a menudo se llama el "jugador de la fila" y el jugador 2 el "jugador de la columna". Si el jugador 1 tiene posibles acciones y el jugador 2 tiene posibles acciones, entonces cada una de las dos matrices tiene filas por columnas. Cuando el jugador de fila selecciona el-th acción y el jugador de la columna selecciona el -th acción, la recompensa para el jugador de fila es y la recompensa para el jugador de la columna es .
Los jugadores también pueden jugar estrategias mixtas . Una estrategia mixta para el jugador de fila es un vector no negativo de longitud tal que: . De manera similar, una estrategia mixta para el jugador de columna es un vector no negativo de longitud tal que: . Cuando los jugadores juegan estrategias mixtas con vectores y , la recompensa esperada del jugador de fila es: y del jugador columna: .
Equilibrio de Nash en juegos de bimatrix
Cada juego de bimatrix tiene un equilibrio de Nash en (posiblemente) estrategias mixtas. Encontrar tal equilibrio de Nash es un caso especial del problema de complementariedad lineal y se puede hacer en tiempo finito mediante el algoritmo de Lemke-Howson . [1]
Hay una reducción del problema de encontrar un equilibrio de Nash en un juego de bimatrix al problema de encontrar un equilibrio competitivo en una economía con utilidades de Leontief . [2]
Términos relacionados
Un juego de suma cero es un caso especial de un juego de bimatrix en el que.
Referencias
- ^ a b Chandrasekaran, R. "Juegos de Bimatrix" (PDF) . Consultado el 17 de diciembre de 2015 .
- ^ Codenotti, Bruno; Saberi, Amin; Varadarajan, Kasturi; Ye, Yinyu (2006). "Las economías de Leontief codifican juegos de dos jugadores de suma distinta de cero". Actas del decimoséptimo simposio anual ACM-SIAM sobre algoritmo discreto - SODA '06 . pag. 659. doi : 10.1145 / 1109557.1109629 . ISBN 0898716055.