A Web-Based Bimatrix Game Optimization Model of Polynomial Complexity

Abstract. The objective of this paper is the description, justification, and web-based implementa-tion of polynomial time algorithms for equilibrium search of Quadratic Bimatrix Games (QBG). An algorithm is proposed combining exact and heuristic parts. The exact part has the Irelevant Fraud (IF) component for cases when an equilibrium exists with no pure strategies. The Direct Search (DS) component finds a solution if an equilibrium exists in pure strategies. The heuristic Quadratic Strategy Elimination (QSE) part applies IF and DS to reduced matrices obtained by se-quential elimination of strategies that lead to non-positive IF solutions. Finally, penalties needed to prevent unauthorized deals are calculated based on Nash axioms of two-person bargaining the-ory. In the numeric experiments QSE provided correct solution in all examples. The novel results include necessary and sufficient conditions when the QBG problem is solved by IF algorithm, the development of software and the experimental testing of large scale QBG problems up to n = 800. The web-sit