Combining preference and feasibility in multi agent local search

Within a multi agent system, rational agents communicate and negotiate to solve a common global constraint satisfaction problem. Given that there are many possible solutions and that each agent has its own preference, such negotiation should not only lead to just any solution, but one that is fair and mutually beneficial to the all the participants. The Nash bargaining solution to the bargaining problem can be applied to a cooperative multi agent environment in order to achieve pareto optimal solutions, where no party can benefit without causing harm to others.; We propose a marginalization strategy that approximates the bargaining set and allows for a more effective local search in the presence of non-binary constraints. This technique considers both feasibility and preferences and is able to better distinguish between infeasible states while searching for solutions. We evaluate this method on sport scheduling problem using all-different constraints with preferences and on random binary CSPs with preferences. Experimental results show that it has significant advantage over local search using only min-conflict heuristic. (Abstract shortened by UMI.)...