Affiliations: Cork Constraint Computation Centre, Department of Computer Science, University College Cork, Cork, Ireland. Tel.: +353 21 425 5458; Fax: +353 21 425 5424; E-mail: roman@4c.ucc.ie | [x] Delft University of Technology, PO Box 5031, 2600 GA Delft, The Netherlands | [y] Jet propulsion Laboratory, 4800 Oak Grove Dr., Pasadena, CA 91750, USA
Abstract: Privacy is often cited as the main reason to adopt a multiagent approach for a certain problem. This also holds true for multiagent planning. Still, a metric to evaluate the privacy performance of planners is virtually non-existent. This makes it hard to compare different algorithms on their performance with regards to privacy. Moreover, it prevents multiagent planning methods from being designed specifically for this aspect. This paper introduces such a measure for privacy. It is based on Shannon's theory of information and revolves around counting the number of alternative plans that are consistent with information that is gained during, for example, a negotiation step, or the complete planning episode. To accurately obtain this measure, one should have intimate knowledge of the agent's domain. It is unlikely (although not impossible) that an opponent who learns some information on a target agent has this knowledge. Therefore, it is not meant to be used by an opponent to understand how much he has learned. Instead, the measure is aimed at agents who want to know how much privacy they have given up, or are about to give up, in the planning process. They can then use this to decide whether or not to engage in a proposed negotiation, or to limit the options they are willing to negotiate upon.
