Premium
Multi‐Agent Constraint Systems with Preferences: Efficiency, Solution Quality, and Privacy Loss
Author(s) -
Franzin M. S.,
Rossi F.,
Freuder E. C.,
Wallace R.
Publication year - 2004
Publication title -
computational intelligence
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.353
H-Index - 52
eISSN - 1467-8640
pISSN - 0824-7935
DOI - 10.1111/j.0824-7935.2004.00238.x
Subject(s) - computer science , mathematical optimization , constraint (computer aided design) , rotation formalisms in three dimensions , constraint satisfaction problem , quality (philosophy) , set (abstract data type) , pareto principle , scheduling (production processes) , multi agent system , fuzzy logic , artificial intelligence , mathematics , philosophy , geometry , epistemology , probabilistic logic , programming language
In this paper, we consider multi‐agent constraint systems with preferences, modeled as soft constraint systems in which variables and constraints are distributed among multiple autonomous agents. We assume that each agent can set some preferences over its local data, and we consider two different criteria for finding optimal global solutions: fuzzy and Pareto optimality. We propose a general graph‐based framework to describe the problem to be solved in its generic form. As a case study, we consider a distributed meeting scheduling problem where each agent has a pre‐existing schedule and the agents must decide on a common meeting that satisfies a given optimality condition. For this scenario we consider the topics of solution quality, search efficiency, and privacy loss, where the latter pertains to information about an agent's pre‐existing meetings and available time‐slots. We also develop and test strategies that trade efficiency for solution quality and strategies that minimize information exchange, including some that do not require inter‐agent comparisons of utilities. Our experimental results demonstrate some of the relations among solution quality, efficiency, and privacy loss, and provide useful hints on how to reach a tradeoff among these three factors. In this work, we show how soft constraint formalisms can be used to incorporate preferences into multi‐agent problem solving along with other facets of the problem, such as time and distance constraints. This work also shows that the notion of privacy loss can be made concrete so that it can be treated as a distinct, manipulable factor in the context of distributed decision making.