[Back]

F. Buccafurri, G. Gottlob:
"Multiagent Compromises, Joint Fixpoints and Stable Models";
Talk: 2003 Joint Conference on Declarative Programming, Reggio Calabria, Italien; 2003-09-03 - 2003-09-05; in: "Proceedings of the 2003 Joint Conference on Declarative Programming", (2003), 180 - 192.

We assume the requirements or desires of an agent are modeled by a logic program. In a multi-agent setting, a joint decision of the agents, reflecring a compromise of the various requirements, corresponds to a siutable joint model of the respective logic programs. In this paper, an appropriate semantics for selecting joint models representing compromises is proposed: the joint fixpoint semantics. The intended joint models are defined to be the (minimal) joint fixpoints of the agents programs. We study computational properties of this new semantics showing that determining whether two (or more) logic programs have a joint fixpoint is NP complete. This remains true even for entirely positive logic programs. We also studdy the complexity of skeptical and credulous reasoning under the joint fixpoint semantics. The former is proven to be co-NP complete, while the latter is Σ^P₂ complete. We show how the joint fixpoints of a set of logic programs can be computed as stable sets.