This paper is concerned with evaluating different multiagent learning (MAL) algorithms in problems where individual agents may be heterogenous, in the sense of utilizing different learning strategies, without the opportunity for prior agreements or information regarding coordination. Such a situation arises in ad hoc team problems, a model of many practical multiagent systems applications. Prior work in multiagent learning has often been focussed on homogeneous groups of agents, meaning that all agents were identical and a priori aware of this fact. Also, those algorithms that are specifically designed for ad hoc team problems are typically evaluated in teams of agents with fixed behaviours, as opposed to agents which are adapting their behaviours. In this work, we empirically evaluate five MAL algorithms, representing major approaches to multiagent learning but originally developed with the homogeneous setting in mind, to understand their behaviour in a set of ad hoc team problems. All teams consist of agents which are continuously adapting their behaviours. The algorithms are evaluated with respect to a comprehensive characterisation of repeated matrix games, using performance criteria that include considerations such as attainment of equilibrium, social welfare and fairness. Our main conclusion is that there is no clear winner. However, the comparative evaluation also highlights the relative strengths of different algorithms with respect to the type of performance criteria, e.g., social welfare vs. attainment of equilibrium.
Harsanyi pioneered the study of incomplete information games. In his 1967 paper @cite_31 , he describes the , a game in which players have beliefs about missing information. He develops the concept of the Bayesian Nash equilibrium @cite_34 in which each player plays a best response against the other players, based on the personal beliefs of the player. Jordan @cite_17 showed that, for any repeated game, if the players play a Bayesian Nash equilibrium in each repetition, and if the personal beliefs of the players satisfy certain conditions, then this will converge to a true Nash equilibrium.
@cite_31 @cite_34 @cite_17
2102794165 2129760941
Part I of this paper has described a new theory for the analysis of games with incomplete information. It has been shown that, if the various players' subjective probability distributions satisfy a certain mutual-consistency requirement, then any given game with incomplete information will be equivalent to a certain game with complete information, called the “Bayes-equivalent” of the original game, or briefly a “Bayesian game.” Part II of the paper will now show that any Nash equilibrium point of this Bayesian game yields a “Bayesian equilibrium point” for the original game and conversely. This result will then be illustrated by numerical examples, representing two-person zero-sum games with incomplete information. We shall also show how our theory enables us to analyze the problem of exploiting the opponent's erroneous beliefs. However, apart from its indubitable usefulness in locating Bayesian equilibrium points, we shall show it on a numerical example the Bayes-equivalent of a two-person cooperative game that the normal form of a Bayesian game is in many cases a highly unsatisfactory representation of the game situation and has to be replaced by other representations e.g., by the semi-normal form. We shall argue that this rather unexpected result is due to the fact that Bayesian games must be interpreted as games with “delayed commitment” whereas the normal-form representation always envisages a game with “immediate commitment.” This paper studies myopic Bayesian learning processes for finite-player, finite-strategy normal form games. Initially, each player is presumed to know his own payoff function but not the payoff functions of the other players. Assuming that the common prior distribution of payoff functions satisfies independence across players, it is proved that the conditional distributions on strategies converge to a set of Nash equilibria with probability one. Under a further assumption that the prior distributions are sufficiently uniform, convergence to a set of Nash equilibria is proved for every profile of payoff functions, that is, every normal form game.