Title:
|
A Study of Heuristic Approaches for Solving Generalized Nash Equilibrium Problems and Related Games |
Author:
|
Wild, Erin
|
Department:
|
Department of Mathematics and Statistics |
Program:
|
Mathematics and Statistics |
Advisor:
|
Cojocaru, Monica Thommes, Edward |
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. |
URI:
|
http://hdl.handle.net/10214/11483
|
Date:
|
2017-08 |
Rights:
|
Attribution-NonCommercial 2.5 Canada |
Terms of Use:
|
All items in the Atrium are protected by copyright with all rights reserved unless otherwise indicated. |