Dispersion games: general definitions and some specific learning results

摘要

Dispersion games are the generalization of the anti-coordination game to arbitrary numbers of agents and ac-tions. In these games agents prefer outcomes in which the agents are maximally dispersed over the set of possible ac-tions. This class of games models a large number of natu-ral problems, including load balancing in computer science, niche selection in economics, and division of roles within a team in robotics. Our work consists of two main contribu-tions. First, we formally define and characterize some inter-esting classes of dispersion games. Second, we present sev-eral learning strategies that agents can use in these games, including traditional learning rules from game theory and ar-tificial intelligence, as well as some special purpose strate-gies. We then evaluate analytically and empirically the per-formance of each of these strategies.