A Web-Based Bimatrix Game Optimization Model of Polynomial Complexity

Article type: Research Article

Authors: Mockus, Jonas

Affiliations: Institute of Mathematics and Informatics, Akademijos 4, LT-08663 Vilnius, Lithuania, e-mail: [email protected]

Abstract: The objective of this paper is the description, justification, and web-based implementation 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 sequential 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 theory. 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-site http://pilis.if.ktu.lt/~jmockus includes this and accompanying optimization models.

Keywords: game theory, heuristics, optimization, economics, education

Journal: Informatica, vol. 20, no. 1, pp. 79-98, 2009