Let E be a finite set and H a family of subsets of E such that the symmetric difference of any two members of this family is at least 2. Let F be the complement of H in P(E), the set of the subsets of E. In this paper we characterize the convex hull of the characteristic vectors of the elements of F. We consider also the polar of these polyhedra and study their links with some well known polyhedra.

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 do better by unilaterally 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.

Refining a linear optimization problem over the Klee-Minty n-cube recently introduced, we exhibit a nearly worst-case example for path-following interior point methods. Namely, while the theoretical iteration-complexity upper bound is $O(2^n n^{5/2})$, we prove that solving this n-dimensional linear optimization problem requires at least $2^n-1$ iterations.

We compute a maximum cardinality set of source to sink vertex-disjoint strictly monotone paths in a d-polytope, defined by n inequalities, directed by a linear objective function. (Holt and Klee proved that there exist at least d such paths). The algorithm uses a combination of networks flows, the simplex method, and reverse search. Computational results show that the algorithm excels when the input has little or no degeneracy, and is especially memory-efficient when the polytope has many vertices. Preliminary results show that the lengths of the disjoint paths are typically short.