Skip to Main Content
 

Global Search Box

 
 
 
 

Files

File List


Heyman_Dissertation.pdf (764.56 KB)

ETD Abstract Container

Abstract Header

On the Computation of Strategically Equivalent Games

Heyman, Joseph Lee
http://rave.ohiolink.edu/etdc/view?acc_num=osu1561984858706805

Abstract Details

2019, Doctor of Philosophy, Ohio State University, Electrical and Computer Engineering.
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).
Abhishek Gupta (Advisor)
Atilla Eryilmaz (Committee Member)
Kevin Passino (Committee Member)
Ness Shroff (Committee Member)
140 p.
Applied Mathematics; Computer Science; Economics; Electrical Engineering
game theory; algorithmic game theory; nonzero-sum games; wedderburn rank reduction; strategic equivalence in games

Recommended Citations

Citations

  • Heyman, J. L. (2019). On the Computation of Strategically Equivalent Games [Doctoral dissertation, Ohio State University]. OhioLINK Electronic Theses and Dissertations Center. http://rave.ohiolink.edu/etdc/view?acc_num=osu1561984858706805

    APA Style (7th edition)

  • Heyman, Joseph. On the Computation of Strategically Equivalent Games. 2019. Ohio State University, Doctoral dissertation. OhioLINK Electronic Theses and Dissertations Center, http://rave.ohiolink.edu/etdc/view?acc_num=osu1561984858706805.

    MLA Style (8th edition)

  • Heyman, Joseph. "On the Computation of Strategically Equivalent Games." Doctoral dissertation, Ohio State University, 2019. http://rave.ohiolink.edu/etdc/view?acc_num=osu1561984858706805

    Chicago Manual of Style (17th edition)

osu1561984858706805
948
© 2019, all rights reserved.
This open access ETD is published by The Ohio State University and OhioLINK.