Possibilistic Reasoning and Privacy/Efficiency Tradeoffs in Multi-agent Systems

In cooperative problem solving, while some communication is necessary, privacy issues can limit the amount of information transmitted. We study this problem in the context of meeting scheduling. Agents propose meetings consistent with their schedules while responding to other proposals by accepting or rejecting them. The information in their responses is either a simple accept/reject or an account of meetings in conflict with the proposal. The major mechanism of inference involves an extension of CSP technology, which uses information about possible values in an unknown CSP. Agents store such information within ‘views’ of other agents. We show that this kind of possibilistic information in combination with arc consistency processing can speed up search under conditions of limited communication. This entails an important privacy/efficiency tradeoff, in that this form of reasoning requires a modicum of actual private information to be maximally effective. If links between derived possibilistic information and events that gave rise to these deductions are maintained, actual (meeting) information can be deduced without any meetings being communicated. Such information can also be used heuristically to find solutions before such discoveries can occur.