Study of turn-taking coordination for nagents in game-theoretic scenarios, with reinforcement learning: Proposal of an evaluation framework of Perfect Alternation Equilibria for multi-agent environments

Abstract

In this thesis, a novel performance evaluation framework is introduced for several dynamic multi-agent interpretations of the Battle of the Exes scenario, which are also proposed for the first time. The Multi-Agent BoE scenario (MBoE) was modeled as a Markov Game and was computationally examined in 7 branches of 2-6 and 2-10 agents’ experiments (43 experiments) for two types of state-representations, two numbers of episodes and various reward systems. New variations of Fairness (Multi-agent Fairness & Reward Fairness) were proposed, with the latter being used to measure the systems’ performance, as literature’s 2-agents metrics were found insufficient for n-agents games. Furthermore, a Perfect Alternation equilibrium was introduced, defined and evaluated, as an ideal equilibrium, robust to the number of agents and episodes of a system. For the purposes of this thesis, it was hypothesized and eventually shown, that a Fair and Efficient equilibrium in multi-agent dynamic environments such as MBoE does not necessarily signify Perfect Alternation. Furthermore, new types of metrics and indicators for measuring and evaluating the performance of a system towards Perfect Alternation were introduced and tested: Rotation (RT, with 2 sub-metrics and 2 forms), Alternation (ALT, 6 versions) and Proportional Individual Performance. ALT metrics definitions were found sufficient for evaluating of Perfect Alternation, thus they was benchmarked and tested through the series of experiments, aspiring to initiate this branch of studies and contribute novel tools for deeper understanding of complexsystems, such as the social behavior of cognitive systems.