[Back]

F. Buccafurri, G. Gottlob:
"Multiagent Compromises, Joint Fixpoints, and Stable Models";
in: "LNAI 2407/Computational Logic: Logic Programming and Beyond", A. Kakas, F. Sadri (ed.); Springer, Berlin, 2002, ISBN: 3-540-43959-5, 561 - 585.

We assume the requirements of desires of an agent are modeled by a logic program. In a multi-agent setting, a joint decision of the agents, reflecting a compromise of the various requirements, corresponds to a suitable 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 agent 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 sudy 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.