A Study of Heuristic Approaches for Solving Generalized Nash Equilibrium Problems and Related Games

Abstract

The use of various computational heuristics for solving generalized Nash equilibrium problems (GNEPs) and related games is explored. In a model of competitive helping, agent-based simulations are used as a complementary analysis tool in conjunction with replicator equations. These agent-based simulations highlight the emergence of behaviours as well as equilibrium amounts of help provided by individuals. Using a concept of Nash dominance, an evolutionary algorithm utilizing the Sierpinski representation was then developed to find representable solution sets for GNEPs in general. Following this is a comparison of two methods which attempt to find optimal strategies for playing a classic GNEP turned card game called deck-based divide-the-dollar. The first method uses evolutionary computation to evolve optimal players who are represented by binary decision automata. The second method uses Monte Carlo policy evaluation, a form of reinforcement learning, to iteratively optimize a player's strategy through experience with particular game states and eventual outcomes. The thesis concludes with some final remarks and suggestions for future work.