MPI-INF Logo
Campus Event Calendar

Event Entry

What and Who

A complete characterization of Nash-solvability of bimatrix games in terms of the exclusion of certain $2\times 2$ subgames

Khaled Elbassioni
Max-Planck-Institut für Informatik - D1
AG1 Mittagsseminar (own work)
AG 1, AG 3, AG 5, RG2, AG 2, AG 4, RG1, SWS  
AG Audience
English

Date, Time and Location

Friday, 6 June 2008
14:00
30 Minutes
E1 4
024
Saarbrücken

Abstract

In 1964 Shapley observed that a matrix

has a saddle point whenever every
$2 \times 2$ submatrix of it has one.
In contrast, a bimatrix game may have no
Nash equilibrium (NE) even when every
$2 \times 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 \times 2$ bimatrix games
into fifteen classes $C = \{c_1, \ldots, c_{15}\}$
depending on the preference pre-orders of the two players.
A subset $t \subseteq 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.

Contact

Khaled Elbassioni
--email hidden
passcode not visible
logged in users only

Khaled Elbassioni, 06/02/2008 22:39 -- Created document.