This work is a study of a particular form of games in Game Theory: Bimatrix and Polymatrix Games. Compared to extensive or dynamic games, decision making is simultaneous, static and unique in bimatrix and polymatrix games. Complete Enumeration of Extreme Equilibria helps identifying all the equilibria sets that could be obtained for such a class of games. The purpose of this paper is to present a new mixed 0-1 linear formulation of bimatrix and polymatrix games and a new algorithm that enumerates all there extreme equilibria. The paper is organized as follows. Bimatrix Games and Polymatrix Games are introduced in Sections 2 and 3. New formulations of bimatrix and polymatrix games are proposed in Section 4. Elimination of dominated strategies is clarified in Section 5. In Section 6, E³-MIP algorithm for enumeration of extreme equilibria is presented and illustrated on some examples. Results of E³-MIP and EEE on randomly generated bimatrix games are compared and discussed, then E³-MIP results on randomly generated polymatrix games are presented in Section 7.

We consider the problem of determining a set of optimal prices on a subset of all thearcs of a highway network in order to maximize the revenue of the government or private firms. We can formulate this problem as a bilinear bilevel problem. We develop heuristics to solve the problem and present computational results.

The talk will explain natural extensions of Dantzig-Wolfe and Benders decomposition methods from the realm of optimization models to equilibrium models, specifically to equilibrium models that are represented as variational inequality problems. Conditions for convergence of the algorithms are met by many economic equilibrium models.

We propose an algorithm which uses Gomory cuts to solve the Bilevel Linear Problem BLP. First, we present the mathematical model of BLP and its properties. We emphasize the links between Bilevel Linear Programming and Linear Mixed 0-1 Programming. Next, we propose a set of valid cuts to the BLP. These cuts are generated from the mixed reformulation for the BLP. We examine their depths. Then a new algorithm Al(coupes) for Bilevel Linear Programming is introduced. Our algorithm includes two steps. The first one generates Gomory cuts to reduce the feasible region. The second step is a Branch-and-Bound procedure. We study the different features of the algorithm, in particular the cut selection criterion and the branching criterion. We also propose a set of tests and procedures that streamline the algorithm. Finally, we feature the optimal algorithmic criteria and evaluate the effectiveness of the cuts through experimental results. Our algorithm Al(coupes) outperforms the CPLEX resolution of mixed reformulation when tested on a series of randomly generated test problems.