Advanced search options

Advanced Search Options 🞨

Browse by author name (“Author name starts with…”).

Find ETDs with:

in
/  
in
/  
in
/  
in

Written in Published in Earliest date Latest date

Sorted by

Results per page:

You searched for id:"oai:etd.ohiolink.edu:osu1561984858706805". One record found.

Search Limiters

Last 2 Years | English Only

No search limiters apply to these results.

▼ Search Limiters


The Ohio State University

1. 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

Record DetailsSimilar RecordsGoogle PlusoneFacebookTwitterCiteULikeMendeleyreddit

APA · Chicago · MLA · Vancouver · CSE | Export to Zotero / EndNote / Reference Manager

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. http://rave.ohiolink.edu/etdc/view?acc_num=osu1561984858706805.

MLA Handbook (7th Edition):

Heyman, Joseph Lee. “On the Computation of Strategically Equivalent Games.” 2019. Web. 17 Nov 2019.

Vancouver:

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

.