Namespaces
Variants
Actions

Difference between revisions of "Bimatrix game"

From Encyclopedia of Mathematics
Jump to: navigation, search
(Importing text file)
 
(TeX)
 
Line 1: Line 1:
A finite [[Non-cooperative game|non-cooperative game]] between two players. A bimatrix game is specified by two matrices <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016290/b0162901.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016290/b0162902.png" /> of the same dimension <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016290/b0162903.png" />, which are, respectively, the payoff matrices (or gain matrices) of the players I and II. The strategy of player I is the selection of a row, that of player II the selection of a column. If player I chooses <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016290/b0162904.png" /> (<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016290/b0162905.png" />), while player II chooses <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016290/b0162906.png" /> (<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016290/b0162907.png" />), their respective payoffs (gains) will be <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016290/b0162908.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016290/b0162909.png" />; if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016290/b01629010.png" /> for all <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016290/b01629011.png" />, the bimatrix game becomes a [[Matrix game|matrix game]]. The theory of bimatrix games is the simplest branch of the general theory of non-cooperative games, but even bimatrix games are not always solvable according to Nash or strongly solvable. Various algorithms are available to find equilibrium solutions in bimatrix games: a method of describing the submatrices of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016290/b01629012.png" /> yielding all extreme points of the set of equilibrium solutions [[#References|[1]]], [[#References|[2]]]; and methods which reduce the problem of finding the equilibrium solutions of a bimatrix game to a problem of [[Quadratic programming|quadratic programming]] [[#References|[3]]], [[#References|[4]]], [[#References|[5]]].
+
{{TEX|done}}
 +
A finite [[Non-cooperative game|non-cooperative game]] between two players. A bimatrix game is specified by two matrices $A=\|a_{ij}\|$ and $B=\|B_{ij}\|$ of the same dimension $m\times n$, which are, respectively, the payoff matrices (or gain matrices) of the players I and II. The strategy of player I is the selection of a row, that of player II the selection of a column. If player I chooses $i$ ($1\leq i\leq m$), while player II chooses $j$ ($1\leq j\leq n$), their respective payoffs (gains) will be $a_{ij}$ and $b_{ij}$; if $a_{ij}+b_{ij}=0$ for all $i,j$, the bimatrix game becomes a [[Matrix game|matrix game]]. The theory of bimatrix games is the simplest branch of the general theory of non-cooperative games, but even bimatrix games are not always solvable according to Nash or strongly solvable. Various algorithms are available to find equilibrium solutions in bimatrix games: a method of describing the submatrices of $A,B$ yielding all extreme points of the set of equilibrium solutions [[#References|[1]]], [[#References|[2]]]; and methods which reduce the problem of finding the equilibrium solutions of a bimatrix game to a problem of [[Quadratic programming|quadratic programming]] [[#References|[3]]], [[#References|[4]]], [[#References|[5]]].
  
 
====References====
 
====References====
 
<table><TR><TD valign="top">[1]</TD> <TD valign="top">  N.N. Vorob'ev,  "Equilibrium points in bimatrix games"  ''Theory Probab. Appl'' , '''3''' :  3  (1958)  pp. 297–309  ''Teor. Veroyatnost. i Primenen.'' , '''3''' :  3  (1958)  pp. 318–331</TD></TR><TR><TD valign="top">[2]</TD> <TD valign="top">  H.W. Kuhn,  "An algorithm for equilibrium points in bimatrix games"  ''Proc. Nat. Acad. Sci. USA'' , '''47'''  (1961)  pp. 1657–1662</TD></TR><TR><TD valign="top">[3]</TD> <TD valign="top">  H. Mills,  "Equilibrium points in infinite games"  ''J. Soc. Ind. Appl. Math.'' , '''8''' :  2  (1960)  pp. 397–402</TD></TR><TR><TD valign="top">[4]</TD> <TD valign="top">  O.L. Mangasarian,  "Equilibrium points of bimatrix games"  ''J. Soc. Ind. Appl. Math.'' , '''12''' :  4  (1964)  pp. 778–780</TD></TR><TR><TD valign="top">[5]</TD> <TD valign="top">  C.E. Lemke,  J.T. Howson, jr.,  "Equilibrium points of bimatrix games"  ''J. Soc. Ind. Appl. Math.'' , '''12''' :  2  (1964)  pp. 413–423</TD></TR></table>
 
<table><TR><TD valign="top">[1]</TD> <TD valign="top">  N.N. Vorob'ev,  "Equilibrium points in bimatrix games"  ''Theory Probab. Appl'' , '''3''' :  3  (1958)  pp. 297–309  ''Teor. Veroyatnost. i Primenen.'' , '''3''' :  3  (1958)  pp. 318–331</TD></TR><TR><TD valign="top">[2]</TD> <TD valign="top">  H.W. Kuhn,  "An algorithm for equilibrium points in bimatrix games"  ''Proc. Nat. Acad. Sci. USA'' , '''47'''  (1961)  pp. 1657–1662</TD></TR><TR><TD valign="top">[3]</TD> <TD valign="top">  H. Mills,  "Equilibrium points in infinite games"  ''J. Soc. Ind. Appl. Math.'' , '''8''' :  2  (1960)  pp. 397–402</TD></TR><TR><TD valign="top">[4]</TD> <TD valign="top">  O.L. Mangasarian,  "Equilibrium points of bimatrix games"  ''J. Soc. Ind. Appl. Math.'' , '''12''' :  4  (1964)  pp. 778–780</TD></TR><TR><TD valign="top">[5]</TD> <TD valign="top">  C.E. Lemke,  J.T. Howson, jr.,  "Equilibrium points of bimatrix games"  ''J. Soc. Ind. Appl. Math.'' , '''12''' :  2  (1964)  pp. 413–423</TD></TR></table>

Latest revision as of 07:37, 23 August 2014

A finite non-cooperative game between two players. A bimatrix game is specified by two matrices $A=\|a_{ij}\|$ and $B=\|B_{ij}\|$ of the same dimension $m\times n$, which are, respectively, the payoff matrices (or gain matrices) of the players I and II. The strategy of player I is the selection of a row, that of player II the selection of a column. If player I chooses $i$ ($1\leq i\leq m$), while player II chooses $j$ ($1\leq j\leq n$), their respective payoffs (gains) will be $a_{ij}$ and $b_{ij}$; if $a_{ij}+b_{ij}=0$ for all $i,j$, the bimatrix game becomes a matrix game. The theory of bimatrix games is the simplest branch of the general theory of non-cooperative games, but even bimatrix games are not always solvable according to Nash or strongly solvable. Various algorithms are available to find equilibrium solutions in bimatrix games: a method of describing the submatrices of $A,B$ yielding all extreme points of the set of equilibrium solutions [1], [2]; and methods which reduce the problem of finding the equilibrium solutions of a bimatrix game to a problem of quadratic programming [3], [4], [5].

References

[1] N.N. Vorob'ev, "Equilibrium points in bimatrix games" Theory Probab. Appl , 3 : 3 (1958) pp. 297–309 Teor. Veroyatnost. i Primenen. , 3 : 3 (1958) pp. 318–331
[2] H.W. Kuhn, "An algorithm for equilibrium points in bimatrix games" Proc. Nat. Acad. Sci. USA , 47 (1961) pp. 1657–1662
[3] H. Mills, "Equilibrium points in infinite games" J. Soc. Ind. Appl. Math. , 8 : 2 (1960) pp. 397–402
[4] O.L. Mangasarian, "Equilibrium points of bimatrix games" J. Soc. Ind. Appl. Math. , 12 : 4 (1964) pp. 778–780
[5] C.E. Lemke, J.T. Howson, jr., "Equilibrium points of bimatrix games" J. Soc. Ind. Appl. Math. , 12 : 2 (1964) pp. 413–423
How to Cite This Entry:
Bimatrix game. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Bimatrix_game&oldid=12972
This article was adapted from an original article by E.B. Yanovskaya (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article