A Complete Characterization of Nash-Solvability of Bimatrix Games in Terms of the Exclusion of Certain 2×2 Subgames Export

@incollection{citeulike:4522960, abstract = {In 1964 Shapley observed that a matrix has a saddle point whenever every 2 ×2 submatrix of it has one. In contrast, a bimatrix game may have no Nash equilibrium (NE) even when every 2 ×2 subgame of it has one. Nevertheless, Shapley's claim can be generalized for bimatrix games in many ways as follows. We partition all 2 ×2 bimatrix games into fifteen classes C = {c 1, ..., c 15} depending on the preference pre-orders of the two players. A subset t ⊆ C is called a NE-theorem if a bimatrix game has a NE whenever it contains no subgame from t. We suggest a general method for getting all minimal (that is, strongest) NE-theorems based on the procedure of joint generation of transversal hypergraphs given by a special oracle. By this method we obtain all (six) minimal NE-theorems.}, author = {Boros, Endre and Elbassioni, Khaled and Gurvich, Vladimir and Makino, Kazuhisa and Oudalov, Vladimir}, citeulike-article-id = {4522960}, citeulike-linkout-0 = {http://dx.doi.org/10.1007/978-3-540-79709-8_13}, citeulike-linkout-1 = {http://www.springerlink.com/content/d84740735u26m260}, doi = {10.1007/978-3-540-79709-8_13}, journal = {Computer Science – Theory and Applications}, keywords = {transversals}, pages = {99--109}, posted-at = {2009-05-15 11:21:40}, priority = {2}, title = {A Complete Characterization of Nash-Solvability of Bimatrix Games in Terms of the Exclusion of Certain 2×2 Subgames}, url = {http://dx.doi.org/10.1007/978-3-540-79709-8_13}, year = {2008} }

TY - CHAP ID - citeulike:4522960 L3 - citeulike-article-id:4522960 N2 - In 1964 Shapley observed that a matrix has a saddle point whenever every 2 ×2 submatrix of it has one. In contrast, a bimatrix game may have no Nash equilibrium (NE) even when every 2 ×2 subgame of it has one. Nevertheless, Shapley’s claim can be generalized for bimatrix games in many ways as follows. We partition all 2 ×2 bimatrix games into fifteen classes C = {c 1, ..., c 15} depending on the preference pre-orders of the two players. A subset t ⊆ C is called a NE-theorem if a bimatrix game has a NE whenever it contains no subgame from t. We suggest a general method for getting all minimal (that is, strongest) NE-theorems based on the procedure of joint generation of transversal hypergraphs given by a special oracle. By this method we obtain all (six) minimal NE-theorems. JF - Computer Science – Theory and Applications EP - 109 TI - A Complete Characterization of Nash-Solvability of Bimatrix Games in Terms of the Exclusion of Certain 2×2 Subgames SP - 99 KW - transversals AU - Boros, Endre AU - Elbassioni, Khaled AU - Gurvich, Vladimir AU - Makino, Kazuhisa AU - Oudalov, Vladimir PY - 2008/// UR - http://dx.doi.org/10.1007/978-3-540-79709-8_13 ER -