a framework for coalitional normative systems
We propose coalitional normative system (Cns), which can selectively restrict the joint behavior of a coalition, in this paper. We extend the semantics of Atl and propose Coordinated Atl (Co-Atl) to support the formalizing of Cns. We soundly and completely characterize the limitation of the normative power of a coalition by identifying two fragments of Co-Atl language corresponding to two types of system properties that are unchangeable by restricting the joint behavior of such a coalition. Then, we prove that the effectiveness checking, feasibility and synthesis problems of Cns are Ptime-complete, Np-complete and Fnp-complete, respectively. Moreover, we define two concepts of optimality for Cns, that is, minimality and compactness, and prove that both minimality checking and compactness checking are Conp-complete while the problem of checking whether a coalition is a minimal controllable coalition is Dp-complete. The relation between Ns and Cns is discussed, and it turns out that Nss intrinsically consists of a proper subset of Cnss and some basic problems related to Cns are no more complex than that of Ns.
normative systems complexity logic model checking