An Epistemic Logic for Arbitration (Extended Abstract)

An Epistemic Logic for Arbitration (Extended Abstract)

Churn-Jung Liau

Institute of Information Science Academia Sinica, Taipei, 115, Taiwan liaucj @iis.sinica.edu.tw

Arbitration is the process of settling a conflict between two or more persons[Liberatore and Schaerf, 1995; Revesz, 1993; 1997]. The first version of the arbitration operator between knowledge bases is proposed in [Revesz, 1993] via the so­ called model-fitting operators. The postulates for model­ fitting operators and the corresponding semantic characteri­ zation are presented. Arbitration is defined as a special kind of model-fitting operators.

In [Revesz, 1997], the arbitration operator is further gen­ eralized to make it applicable to weighted knowledge bases. A set of postulates is also directly used in characterizing the arbitration between a weighted knowledge base and a regu­ lar knowledge base. A weighted knowledge base in [Revesz, 1997] is defined as a mapping k from model sets to non­ negative real numbers and a regular knowledge base is just a finite set of propositional sentences. A generalized loyal assignment is then defined as a function that assigns to each weighted knowledge base k , a pre-order ~k between propo­ sitional sentences so that some conditions are satisfied for the pre-orders. Finally, the arbitration of a weighted knowledge base k by a regular knowledge base K' is defined as

where min(K', ~k) is the set of ~k-minimal sentences in K'. However, this kind of arbitration is obviously syntax­ dependent. For example, if r.p1 and r.p2 are two propositional sentencessuchthatr.p1 <k 'P2,thenK6{r.p1,'P2} = {r.pl} =1k 6{ 'Pl A 'P2} = { r.p1 A 'P2} even though the two knowledge bases { 'Pl, 'P2} and { 'Pl A 'P2} are semantically equivalent.

An alternative, seemingly more natural characterization for arbitration is given in [Liberatore and Schaerf, 1995] with­ out resorting to model-fitting operators. A knowledge base in that work is identified with a set of propositional models. Thus the semantic characterization for this kind of arbitration is given by assigning to each subset of models A a binary relation ~A over the set of model sets that satisfies the fol­ lowing conditions (the subscript is omitted when it means all binary relations of the form ~A):

1. transitivity: if A~ Band B ~ C then A~ C,
2. if A ~ B then B ~ A,
3. A~AUBorB~AUB,
4. B ~A C for every C iff A n C =1- 0,

Then the arbitration between two sets of models A and B is defined as

Note that although the relationship ~A is defined between sets of models, in the definition for arbitration, only ~A be­ tween singletons is used. Thus by slightly abusing the nota­ tion, ~A may also denote an ordering between models.

While arbitration is originally proposed for the merging of knowledge bases, it is also applicable in multi-agent sys­ tems. In particular, we can apply it to the reasoning about belief fusion of multiple agents. Epistemic logic is an impor­ tant framework for reasoning about knowledge or belief of agents[Fagin et al., 1996], so the incorporation of arbitration operators into epistemic logic will facilitate its application to belief fusion.

To incorporate the arbitration operator of [Liberatore and Schaerf, 1995] into epistemic logic, we must first note that according to (1), the arbitration is commutative but not neces­ sarily associative. Therefore, the arbitration operator should be a binary one between two agents. We can directly add a class of modal operators for arbitration into epistemic logic. However, to be more expressive, we will also consider the in­ teraction between arbitration and other epistemic operators, so we define the set of arbitration expressions over the agents recursively as the smallest set containing {1 , 2, · · · , n} and closed under the binary operators +, ·, and 6. Here + and · correspond respectively to the distributed belief and the so­ called "everybody knows" operators in multi-agent epistemic logic[Fagin et al., 1996].

Let C denote the language of our logic. The alphabet of C consists of a countable set <Po = {p, q, r, ... } of atomic propositions, the propositional constants _l (falsum or fal­ sity constant) and T (verum or truth constant), the binary Boolean operator V (or), the unary Boolean operator -,(not), a set Ag = {1, 2, ... , n} of agents, the set of arbitration ex­ pressions over Ag, and the auxiliary symbols "[" ,"]", "(" , ")",and",".

The set of well-formed formulas(wffs) of Cis the smallest set containing <Po U { _l, T} and closed under Boolean opera­ tors and the following rule:

• if 'P is a wff and a is an arbitration expression, then [a]<p is a wff.

As usual, other classical Boolean connectives A (and), :J (implication), and = (equivalence) can be defined as abbre­ viations. Also, we will write (a)<p as the abbreviation for ·[a]·<p. Note that it has been shown that the only associa­ tive arbitration satisfying postulates 7 and 8 of [Liberatore and Schaerf, 1995] is A6B = AU B, so if .0. is an asso­ ciative arbitration satisfying those postulates, then [a.0.b]<p is reduced to [a · b] <p, which is, in turn, equivalent to [a]<p A [b]<p.

For the semantics, a possible model is a tuple

where

• W is a set of possible worlds,
• each Ri is a serial binary relation over W 1 ,
• V : <1>0 x W --+ { 0, 1} is a truth assignment, and
• :::; is a function assigning to each subset of possible worlds A a binary relation :S:A~ 2w x 2w satisfying the five conditions for the definition of arbitration oper­ ator.

Note that the first two conditions imply that :S:A is a pre-order over 2 w. For each arbitration expression, we can define the binary relations Rat:;.b, Ra·b and Ra+b over W recursively by

Thus the satisfaction for the wff [a]<p is defined as

When the arbitration expression a is a single agent in­ dex, the formula [a]<p corresponds to Ka'P in epistemic logic, which means that the agent a knows or believes <p. We can also abbreviate [i1 + (i2 + · · · (ik-l + ik))] as [G] where G = { i1, i2, · · · , ik}. [G]<p corresponds to the distributed knowl­ edge formula K c'P of [Fagin eta!., 1996], which means that the combined knowledge of agents in G implies <p.

Since the set of possible worlds W may be infinite in our logic, the minimal models in (2) may not exist, so we define coherent models as those satisfying the limit assumption[Arlo-Costa and Shapiro, 1992] for each binary relations :S:A such that A ~ W:

for any nonempty U ~ W, min(U, :S:A) is nonempty.

An axiomatic system for coherent models is presented in figure I, where a, b, and c are meta-variables for arbitration expressions, i is for agent, 'P and 'lj; are for wffs, and G1 and G2 are for groups of agents. Axioms (f)-(1) correspond to the postulates 2-8 of [Liberatore and Schaerf, 1995] and the limit assumption is needed for the soundness of axioms (i) and (I). Though the completeness of such a system is not yet proved, this brief presentation has shown that the modal logic approach can provide a framework for integrating epistemic reasoning and different knowledge merging operators at the object logic level.

1 A binary relation R over W is called serial if it satisfies: \fw:lu.R(w, u).

l. Axioms:

• (a) P: all tautologies of the propositional calculus
• (b) ([a]<p A [a](<p :J ¢)) :J [a]¢
• (c) ·[{i}]_l_
• (d) [GI] 'P :J [G2J 'P if G1 c G2
• (e) [a· b] <p = ([a]<p A [b]<p)
• (f) [a.0.b]<p = [b.0.a]<p
• (g) [a.0.b]<p :J [a+ b]<p
• (h) ·[a + b]l_ :J ([a+ b] <p :J [a.0.b]<p)
• (i) [a.0.b]_l_ :J [a]_l_ A [b]_l_
• (j) ([a.0.(b · c)]'P = [a.0.b]<p) V ([a.0.(b · c)]'P [a.0.c]<p) V ([a.0.(b · c)]'P = [(a.0.b) · (a.0.c)]'P)
• (k) [a]<p A [b]<p :J [a.0.b]<p
• (I) ·[a]_l_ :J ·[a + (a.0.b)]l_

2. Rules of Inference:

• (a) Modus ponens(MP):

• (b) Necessitation(Nec) :

Figure I: An axiomatic system for the logic of arbitration

Acknowledgments

We would like to thank two anonymous referees for their helpful comments.