Brown CS Colloquium: Bernhard von Stengel in Lubrano on September 11, 2003 at 4 pm.

-------- Original Message --------
Subject: [Brown CS Talks] Brown CS Colloquium: Bernhard von Stengel in Lubrano
on September 11, 2003 at 4 pm.
Date: Thu, 21 Aug 2003 13:09:28 -0400
From: [email protected]
Reply-To: [email protected]
To: <[email protected]>

BROWN UNIVERSITY
COMPUTER SCIENCE COLLOQUIUM

presents

Bernhard von Stengel
Department of Mathematics, London School of Economics
Thursday, September 11, 2003 at 4 pm
Lubrano Conference Room (CIT 4th floor)
Refreshments will be served at 3:45 pm

Hard-to-solve bimatrix games

A bimatrix game is a two-player game in strategic form, a basic model
in game theory.  A Nash equilibrium is a pair of (possibly randomized)
strategies, one for each player, so that no player can unilaterally do
better by changing his or her strategy.  The problem of finding one
Nash equilibrium of a bimatrix game is considered as ``one of the most
important concrete open questions on the boundary of P
[polynomial-time computability] today'' [Papadimitriou, 2001].

In this talk, which will introduce the main concepts and geometric
tools, we show that the commonly used Lemke-Howson algorithm for
finding one equilibrium of a bimatrix game is NOT polynomial. This
question had been open for some time.  The algorithm is a pivoting
method similar to the simplex algorithm for linear programming.  We
present a class of square bimatrix games for which the shortest
Lemke-Howson path grows exponentially in the dimension of the game d.
We construct the games using pairs of dual cyclic polytopes with 2d
facets in d-space.

Joint work with Rahul Savani (LSE).

                  Host: Professor Eli Upfal