A few good agents: Multi-agent social learning

Jean Hyaejin Oh and Stephen Smith
Conference Paper, Proc. of the Seventh International Joint Conference on Autonomous Agents and Multiagent Systems (AAMAS), pp. 339-346, May, 2008

View Publication

Copyright notice: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.


In this paper, we investigate multi-agent learning (MAL) in a multi-agent resource selection problem (MARS) in which a large group of agents are competing for common resources. Since agents in such a setting are self-interested, MAL in MARS domains typically focuses on the convergence to a set of non-cooperative equilibria. As seen in the example of prisoner’s dilemma, however, selfish equilibria are not necessarily optimal with respect to the natural objective function of a target problem, e.g., resource utilization in the case of MARS. Conversely, a centrally administered optimization of physically distributed agents is infeasible in many real- life applications such as transportation traffic problems. In order to explore the possibility for a middle ground solution, we analyze two types of costs for evaluating MAL algorithms in this context. The quality loss of a selfish algorithm can be quantitatively measured by the price of anarchy, i.e., the ratio of the objective function value of a selfish solution to that of an optimal solution. Analogously, we introduce the price of monarchy of a learning algorithm to quantify the practical cost of coordination in terms of communication cost. We then introduce a multi-agent social learning approach named A Few Good Agents (AFGA) that motivates self- interested agents to cooperate with one another to reduce the price of anarchy, while bounding the price of monarchy at the same time. A preliminary set of experiments on the El Farol bar problem, a simple example of MARS, show promising results.

author = {Jean Hyaejin Oh and Stephen Smith},
title = {A few good agents: Multi-agent social learning},
booktitle = {Proc. of the Seventh International Joint Conference on Autonomous Agents and Multiagent Systems (AAMAS)},
year = {2008},
month = {May},
pages = {339-346},
keywords = {multiagent learning},
} 2017-09-13T10:41:40-04:00