Improving Coalition Performance by Exploiting Phase Transition Behavior

摘要

This document describes research into the effects of phase transitions and related phenomena on the design and operation of autonomous negotiating teams (ANTs). Results are reported in three areas: computational thresholds, solution clusters, and pseudo-Boolean solvers. First, the existence of computational thresholds below the usual computational hardness phase transition is shown, and the implications of these thresholds for 'anytime', 'good enough soon enough' behavior are discussed. Second, the effects of solution-clustering behavior on problem decomposition and negotiation strategy are explored, and it is shown that focusing negotiations on clusters both increases the chance of success and reduces the number of rounds of negotiation required. Finally, the application of pseudo-Boolean representations and solvers to ANTS problems is discussed, including the impacts of various heuristic choices and learning strategies that were necessary to provide practical leverage on the ANTs program's demonstration problems.