Kagan Tumer's Publications

Display Publications by [Year] [Type] [Topic]


A Replicator Dynamics Analysis of Difference Evaluation Functions (Extended Abstract). M. Colby and K. Tumer. In Proceedings of the Fourteenth International Joint Conference on Autonomous Agents and Multiagent Systems, pp. , Istanbul, Turkey, May 2015.

Abstract

One of the key difficulties in cooperative coevolutionary algorithms is solving the credit assignment problem. Given the performance of a team of agents, it is difficult to determine the effectiveness of each agent in the system. One solution to solving the credit assignment problem is the difference evaluation function, which has produced excellent results in many multiagent coordination domains, and exhibits the desirable theoretical properties of alignment and sensitivity. However, to date, there has been no prescriptive theoretical analysis deriving conditions under which difference evaluations improve the probability of selecting optimal actions. In this paper, we derive such conditions. Further, we prove that difference evaluations do not alter the Nash equilibria locations or the relative ordering of fitness values for each action, meaning that difference evaluations do not typically harm converged system performance in cases where the conditions are not met. We then demonstrate the theoretical findings using an empirical basins of attraction analysis.

Download

[PDF]167.7kB  

BibTeX Entry

@inproceedings{tumer-colby_Dtheory-aamas15,
author = {M. Colby and K. Tumer},
title = {A Replicator Dynamics Analysis of Difference Evaluation Functions (Extended Abstract)},
booktitle = {Proceedings of the Fourteenth International Joint Conference on Autonomous Agents and Multiagent Systems},
month = {May},
pages ={},
address = {Istanbul, Turkey},
abstract={One of the key difficulties in cooperative coevolutionary algorithms is solving the credit assignment problem.  Given the performance of a team of agents, it is difficult to determine the effectiveness of each agent in the system.  One solution to solving the credit assignment problem is the difference evaluation function, which has produced excellent results in many multiagent coordination domains, and exhibits the desirable theoretical properties of alignment and sensitivity.  However, to date, there has been no prescriptive theoretical analysis deriving conditions under which difference evaluations improve the probability of selecting optimal actions.  In this paper, we derive such conditions.  Further, we prove that difference evaluations do not alter the Nash equilibria locations or the relative ordering of fitness values for each action, meaning that difference evaluations do not typically harm converged system performance in cases where the conditions are not met.  We then demonstrate the theoretical findings using an empirical basins of attraction analysis.},
	bib2html_pubtype = {Refereed Conference Papers},
	bib2html_rescat = {Multiagent Systems, Evolutionary Algorithms},
year = {2015}
}

Generated by bib2html.pl (written by Patrick Riley ) on Tue Jun 26, 2018 19:10:42