The Ohio State University
Heyman, Joseph Lee.
On the Computation of Strategically Equivalent Games.
Degree: PhD, Electrical and Computer Engineering, 2019, The Ohio State University
This dissertation is concerned with the efficient
computation of Nash equilibria (solutions) in nonzero-sum two
player normal-form (bimatrix) games. It has long been believed that
solutions to games in this class are hard, and recent results have
indicated that this is indeed true. Thus, in this dissertation we
focus on identifying subclasses of bimatrix games which can be
solved efficiently. Our first result is an algorithm that
identifies nonzero-sum bimatrix games which are strategically
equivalent to zero-sum games via a positive affine transformation.
Games in this class can then be solved efficiently by well-known
techniques for solving zero-sum games. The algorithm that we
propose runs in linear time to identify games in this class,
representing a significant improvement compared to existing
techniques.The second result uses the theory of matrix pencils and
the Wedderburn rank reduction formula to develop a generalized
theory of rank reduction in bimatrix games. The rank of a bimatrix
game is defined as the rank of the sum of the payoff matrices of
the two players. Under certain conditions on the payoff matrices of
the game, we devise a method that reduces the rank of the game
without changing the equilibrium of the game.The final result
applies the general theory to the subclass of strategically
equivalent rank-1 games. We show that for this subclass, which may
include games of full rank, it is possible to identify games in the
subclass and compute a strategically equivalent rank-1 game in
linear time. These games can then be solved in polynomial time by
relatively recent results for solving rank-1 games. Overall, our
results significantly expand the class of bimatrix games that can
be solved efficiently (in polynomial time).
Advisors/Committee Members: Gupta, Abhishek (Advisor).
Subjects/Keywords: Applied Mathematics; Computer Science; Electrical Engineering; Economics; game theory; algorithmic game theory; nonzero-sum games; wedderburn rank reduction; strategic equivalence in games
to Zotero / EndNote / Reference
APA (6th Edition):
Heyman, J. L. (2019). On the Computation of Strategically Equivalent Games. (Doctoral Dissertation). The Ohio State University. Retrieved from http://rave.ohiolink.edu/etdc/view?acc_num=osu1561984858706805
Chicago Manual of Style (16th Edition):
Heyman, Joseph Lee. “On the Computation of Strategically Equivalent Games.” 2019. Doctoral Dissertation, The Ohio State University. Accessed November 17, 2019.
MLA Handbook (7th Edition):
Heyman, Joseph Lee. “On the Computation of Strategically Equivalent Games.” 2019. Web. 17 Nov 2019.
Heyman JL. On the Computation of Strategically Equivalent Games. [Internet] [Doctoral dissertation]. The Ohio State University; 2019. [cited 2019 Nov 17].
Available from: http://rave.ohiolink.edu/etdc/view?acc_num=osu1561984858706805.
Council of Science Editors:
Heyman JL. On the Computation of Strategically Equivalent Games. [Doctoral Dissertation]. The Ohio State University; 2019. Available from: http://rave.ohiolink.edu/etdc/view?acc_num=osu1561984858706805