Novel dynamic diversity controlling EAs for coevolving optimal negotiation strategies

Abstract

Finding optimal strategies for negotiation with incomplete information is a challenging issue in agent-based automated negotiation research. Although there are some previous works on finding the strategies through coevolutionary learning using evolutionary algorithms (EAs), their coevolving strategies tend to converge to non-global optima (which bring about ineffective negotiation outcomes for participating agents) due to biased coevolution and failures in coevolution. To cope with these drawbacks, this work introduces and compares novel genetic algorithms (GAs) and estimation of distribution algorithms (EDAs) that have additional capability of dynamic diversity control: (1) the dynamic diversity controlling GA ((DC)-C-2-GA), (2) the dynamic diversity controlling EDA ((DC)-C-2-EDA), (3) the improved (DC)-C-2-GA ((IDC)-C-2-GA) and (4) the improved (DC)-C-2-EDA ((IDC)-C-2-EDA). While (DC)-C-2-GA and (DC)-C-2-EDA adopt the novel diversification and refinement (DR) procedure, (IDC)-C-2-GA and (IDC)-C-2-EDA adopt the modified and enhanced DR (mDR) procedure with two additional local heuristics population repair and local neighborhood search. An extensive series of experiments were carried out to compare and evaluate the performance of the simple GA (S-GA), the simple EDA (S-EDA), and the novel GAs and EDAs in coevolving effective negotiation strategies of two self-interested negotiation agents for their various deadline combinations. Favorable empirical results showed that (i) (IDC)-C-2-EDA could coevolve (near-)optimal negotiation strategies for all the considered cases due to its good generalization performance and (ii) it also generally 'outperformed S-GA, S-EDA, (DC)-C-2-GA, (DC)-C-2-EDA and (IDC)-C-2-GA in terms of solution accuracy, coevolutionary search capability and average coevolution restart ratio. Interestingly, it was also found that the coevolution performance of (IDC)-C-2-GA and (IDC)-C-2-EDA is complementary in that (IDC)-C-2-GA and (IDC)-C-2-EDA generally achieved better results in the cases of equal and different deadlines, respectively. (C) 2014 Elsevier Inc. All rights reserved.