Compromise Strategies for Constraint Agents

Contents

We describe several joint problem solving strategies for a team of multi-interest constraint-based reasoning agents. Agents y/eld in one area of conflict in order to gain concessions in another area. For example, in a distributed meeting scheduling problem, individuals with different preferences may be willing to give up the choice of the location for the meeting if allowed to choose the time of the meeting. Compromise benefits the overall solution quality by allowing each agent an opportunity to participate in the solution. We demonstrate the utility of this approach using a collection of agents collaborating on random graph coloring problems. We propose several simple mettics for evaluating solutions from the perspective of individual agents, and additional metrics for evaluating the solutions as compromises. Finally, we experimentally evaluate the performance of the strategies with respect to the metrics.