# multicontext_system_for_optimization_problems__53322270.pdf

The Thirty-Third AAAI Conference on Artiﬁcial Intelligence (AAAI-19)

Multi-Context System for Optimization Problems

Tiep Le, Tran Cao Son, Enrico Pontelli Department of Computer Science New Mexico State University {tile, tson, epontell}@cs.nmsu.edu

This paper proposes Multi-context System for Optimization Problems (MCS-OP) by introducing conditional costassignment bridge rules to Multi-context Systems (MCS). This novel feature facilitates the deﬁnition of a preorder among equilibria, based on the total incurred cost of applied bridge rules. As an application of MCS-OP, the paper describes how MCS-OP can be used in modeling Distributed Constraint Optimization Problems (DCOP), a prominent class of distributed optimization problems that is frequently employed in multi-agent system (MAS) research. The paper shows, by means of an example, that MCS-OP is more expressive than DCOP, and hence, could potentially be useful in modeling distributed optimization problems which cannot be easily dealt with using DCOPs. It also contains a complexity analysis of MCS-OP.

Introduction

The paradigm of Multi-context Systems (MCS) has been introduced in (Mc Carthy 1987; Roelofsen and Seraﬁni 2005; Brewka and Eiter 2007) as a framework for integration of knowledge from different sources. Intuitively, an MCS (Brewka and Eiter 2007) consists of several theories, referred to as contexts, e.g., representing different reasoning components in distributed settings or different agents in multi-agent systems (MAS). The contexts may be heterogeneous, in the sense that each context could use a different logical language for its knowledge base (e.g., deductive databases, triple-stores, description logic, logic programming (Gelfond and Lifschitz 1991)) and thus may use a different inference system. The ﬂow of information between contexts are modeled via bridge rules in a declarative way, where bridge rules describe how the beliefs of one context depend on the beliefs of other contexts. The semantics of MCS is deﬁned in terms of equilibria (Brewka and Eiter 2007). An equilibrium of an MCS can be seen as a state where each context holds a set of its beliefs, and those sets of beliefs of contexts must together satisfy the conditions speciﬁed in the bridge rules. Therefore, MCSs are very suitable for modeling distributed satisfaction problems. However, it

Copyright c 2019, Association for the Advancement of Artiﬁcial Intelligence (www.aaai.org). All rights reserved.

does not provide a means for modeling distributed optimization problems where distributed components (or agents) coordinate with each other to achieve a most preferred (best) solution. This is because an MCS may have many equilibria but there is no means to express the preference among them as well as obtain a most preferred equilibrium. In a different line of research, within the MAS community, Distributed Constraint Optimization Problems (DCOPs) (Modi et al. 2005; Petcu and Faltings 2005; Mailler and Lesser 2004; Gershman, Meisels, and Zivan 2009; Yeoh and Yokoo 2012) have emerged as a prominent agent model to govern the agents autonomous behavior in solving distributed optimization problems. A DCOP is typically speciﬁed by a ﬁnite set of variables and a ﬁnite set of constraints among these variables. Each constraint indicates a utility for each value assignment of the variables involved in it. Agents in DCOPs need to coordinate value assignments of their variables, in a decentralized and distributed manner, to optimize their objective functions. Researchers have used DCOPs to model various multiagent coordination and resource allocation problems (Maheswaran et al. 2004; Zivan, Glinton, and Sycara 2009; Zivan, Okamoto, and Peled 2014; Lass et al. 2008; Kumar, Faltings, and Petcu 2009; Ueda, Iwasaki, and Yokoo 2010; L eaut e and Faltings 2011). Although both the MCS and DCOP research communities have the similar goal of developing a general framework for modeling multi-agent and distributed systems, it is interesting to observe that there is little connection between the two communities. Obviously, the two frameworks cannot be more different: DCOP is homogeneous and MCS is heterogenous. DCOP emphasizes optimization and MCS satisfaction. There have been several systems developed for computing solutions of DCOP whilst only a few experimental systems for computing equilibria of MCSs are available. Can we develop a framework that exploits the advantages of both MCS and DCOP? In this paper, we make the ﬁrst steps to bridge the two different research directions, MCS and DCOP, exploiting their advantages in modeling distributed optimization problems. We introduce a novel, more general form of MCS, called MCS for Optimization Problems (MCS-OP), where each bridge rule can be associated to a conditional cost via the so-called cost-assignment bridge rules. This feature al-

lows MCS-OP to derive preferences among its equilibria using their total incurred cost. This paper contributes to both areas of MCS and DCOP by formally showing how a DCOP can be modeled using an MCS-OP. For the MCS community, this demonstrates that MCS-OP can be used to represent a large and interesting class of optimization problems that DCOP can, something beyond the immediate capabilities of the original MCS model, and hence, a useful and much-needed extension of MCS to model distributed optimization problems. For the DCOP community, MCS-OP can be viewed as an extension of DCOP allowing heterogeneous agents to work with each other. The paper is organized as follows: after recalling the background on MCS, we introduce the MCS-OP framework, study its computational properties. Next we illustrate how to use MCS-OP to model DCOP and show that MCS-OP is more expressive than DCOP. This is followed by a discussion on the related work. The paper ends with its conclusion and future works1.

Background: Multi-context System

A logic L is a tuple (KBL, BSL, ACCL) where KBL is the set of well-formed knowledge bases of L each being a set of formulae. BSL is the set of possible belief sets; each element of BSL is a set of syntactic elements representing the beliefs L may adopt. ACCL : KBL 2BSL describes the semantics of L by assigning to each element of KBL a set of acceptable sets of beliefs. An MCS M = (C1, . . . , Cn) consists of contexts Ci=(Li, kbi, bri), (1 i n), where Li = (KBi, BSi, ACCi) is a logic, kbi KBi is a speciﬁc knowledge base of Li, and bri is a set of Li-bridge rules of the form:

(ri k) s (c1 : p1), . . . , (cj : pj), not (cj+1 : pj+1), . . . , not (cm : pm) (1)

where, ri k is the name of the bridge rule (e.g., the k-th bridge rule in the context Ci) and for each 1 t m, we have that: 1 ct n, pt is an element of some belief set of Lct, and kbi {s} KBi. Intuitively, a bridge rule r allows us to add s to a context, depending on the beliefs in the other contexts. We denote with head(r) the part s of r, and denote with body(r) the right-hand part of the arrow in r. The semantics of MCS is described by the notion of belief states. Let M=(C1, . . . , Cn) be an MCS. A belief state is a tuple S=(S1, . . . , Sn) where each Si is an element of BSi. Let Bri be the set of the names of all bridge rules in bri. Given a belief state S = (S1, . . . , Sn) and a bridge rule r of the form (1), we say that r is applicable in S if pv Scv for each 1 v j and pk Sck for each j + 1 k m. By app(B, S) we denote the set of the bridge rules r B that are applicable in S.

1Due to space constraint, most proofs of lemmae and theorems are presented in the supplemental ﬁle at the URL https://www.cs. nmsu.edu/ tile/AAAI19/supplementary.pdf

A belief state S = (S1, . . . , Sn) of M is an equilibrium if, for all 1 i n, we have that Si ACCi(kbi {head(r) | r app(bri, S)}).

Example 1. Consider a scenario in which two people want to travel together. The ﬁrst person C1 needs to decide whether they purchase the business (b) or economic (e) class for their ﬂight whilst the second person C2 chooses whether they will stay in Hilton (h) or Inn (i) hotel. Note that the knowledge bases of C1 and C2 are given under Answer Set Programming (ASP) (Gelfond and Lifschitz 1991)) and Propositional Logic under the closed world assumption (PL), respectively. There are constraints among such selections in order to have an affordable travel together. If C2 chooses to stay in a fancy hotel like h (resp. affordable hotel like i), C1 would choose a cheaper ﬂight like e (resp. more comfortable ﬂight like b). Similarly, if C1 picks b (resp. e) class for their ﬂights, C2 would select i (resp. h) to stay. This scenario can be modeled as an MCS Mfh = (C1, C2) where L1 and L2 are ASP and PL, respectively2. The knowledge bases and the bridge rules are given as follows.

kb1 = { 1{b; e}1 } kb2 = {(h i) ( h i)}

( (r1 1) e (2 : h) (r1 2) b (2 : i) br2 =

( (r2 1) h (1 : e) (r2 2) i (1 : b)

It is possible to see that Mfh has two equilibria:

S = ({e}, {h}). S = ({b}, {i}).

S (resp. S ) corresponds to the group decision in which C1 selects economic class (e) and C2 selects Hilton (h) (resp. C1 selects business class (b) and C2 selects Inn (i)) for their ﬂight and hotel respectively.

MCS-OP: Multi-context System for Optimization Problems Motivation Roughly speaking, there is no qualitative distinction among the equilibria of an MCS. As such, MCSs are ideal for modeling (distributed) satisfaction problems; e.g., the scenario in Example 1 where a decision for C1 and C2 to travel together need to satisfy the constraints among them. In many scenarios, some selection among the equilibria might be preferred. Let us consider the following example.

Example 2. Let us continue with Example 1. Assume that business class and economic class tickets cost $100 and $50 respectively. Further, staying in Hilton or Inn hotels cost $120 or $60 respectively. The most preferred group decision is to select the ﬂight and the hotel in such a way that minimizes the total cost. Intuitively, the preference of C1 and C2 indicates that equilibrium S is more preferred than S since the total cost associated with S ($160) is smaller than the total cost associated with S ($170).

2The logics of ASP and PL were given in (Brewka and Eiter 2007).

As we have mentioned earlier, MCSs were not focused on providing a mechanism for preferring an equilibrium over another. For this reason, to utilize MCS in solving the problem in Example 2, certain modiﬁcations to Mfh needs to be done. For example, one might have to add to Mfh (i) rules to encode the total cost of a selection to some contexts; and (ii) rules to eliminate the less desirable equilibrium. We next introduce MCS for Optimization Problems (MCS-OP), an extension of MCS, that allows for a principled and efﬁcient way to model distributed optimization problems.

Syntax There are many possible ways to take into consideration preferences among equilibria. Previous work in this direction such as the framework on Multi-Context System with Preferences (MCSP) in (Le, Son, and Pontelli 2018) focuses on creating an order among equilibria from individual preferences which are expressed in each context. In this paper, we focus on establishing a notion of the aggregate preference of an equilibrium and using this notion in deﬁning an order among equilibria. Inspired by the formulation of Distributed Constraint Optimization Problem (see below), where, intuitively, constraints among agents that could be considered as bridges between contexts are associated with costs/utilities, we consider that the aggregate preference of an equilibrium depends on the bridge rules. For this reason, we introduce an extra component to MCS, the costassignment bridge rules. Formally, a cost-assignment bridge rule is deﬁned as follows. Deﬁnition 1. Let M=(C1, . . . , Cn) be a multi-context system where Ci = (Li, kbi, bri) with 1 i n. A Ck-costassignment bridge rule over M, 1 k n, is of the form

r@x (c1 : p1), . . . , (cj : pj), not (cj+1 :pj+1), . . . , not (cm :pm) (2)

where: r Brk is the name of a bridge rule in brk; x R {+ } that speciﬁes the cost of the bridge rule r; for each 1 k m, we have that: 1 ck n, pk is an element of some belief set of Lck. Let cr be a cost-assignment bridge rule of the form (2). We denote with the head(cr) (resp. body(cr)) of cr, the lefthand (resp. right-hand) part of the arrow in cr. Intuitively, (2) states that if its right hand side is satisﬁed then the context Ck will incur a cost x. Deﬁnition 2. A Multi-Context System for Optimization Problems (MCS-OP) M = (C1, . . . , Cn) consists of a collection of cost-assignment contexts Ci = (Li, kbi, bri, cbri), where M = (C 1, . . . , C n) with C i = (Li, kbi, bri) is a MCS and cbri is a ﬁnite set of Ci-cost-assignment bridge rules over M . For simplicity, given an MCS-OP M = (C1, . . . , Cn) where Ci = (Li, kbi, bri, cbri), we denote with MCS(M) the multi-context system MCS(M) = (C 1, . . . , C n) in which C i = (Li, kbi, bri). Example 3. To model the problem in Example 2, we extend the MCS Mfh described

in Example 1 into an MCS-OP M where: MCS(M)=Mfh; and cbr1={r1 1@50 ; r1 2@100 }, cbr2={r2 1@120 ; r2 2@60 }.

The proposal to use cost-assignment bridge rules deserves some discussion. One can observe that it is possible to have bridge rules deriving costs straightforwardly, we decide to use cost-assignment bridge rules mainly because of the following reason. We want to extend original MCS in a modular way, where bridge rules are dedicated to model the ﬂow of information between contexts while cost-assignment bridge rules are dedicated exclusively to assign costs to bridge rules. One beneﬁt of such a modular extension is that one can apply preference elicitation techniques to elicit the costs of bridge rules in future work.

Most Preferred Equilibria

For an MCS-OP M, a belief state of M is deﬁned as a belief state of MCS(M). Given a belief state S of M, a bridge rule r is applicable in S with respect to M if r is applicable in S with respect to MCS(M). A belief state S is an equilibrium of an MCS-OP M iff S is an equilibrium of MCS(M). As our goal in proposing cost-assignment bridge rules is to select best equilibria, we establish a preference order among belief states of an MCS-OP. Clearly, this order has to be based on the set of cost-assignment bridge rules. We ﬁrst deﬁne the applicability of a cost-assignment bridge rule.

Deﬁnition 3. A cost-assignment bridge rule of the form (2) is ﬁreable in a belief state S = (S1, . . . , Sn) if r is applicable in S; and its body is satisﬁed in S, i.e., pv Scv for each 1 v j and pk Sck for each j + 1 k m.

Given a belief state S = (S1, . . . , Sn) and a costassignment bridge rule cr of the form (2), we deﬁne the cost impact of cr in S, denoted with c S(cr), as follows: i. c S(cr) = 0 if cr is not ﬁreable in S, that is, either r is not applicable or pk Sck for some k {1, . . . , j}, or some pk Sck for k {j + 1, . . . , m}; otherwise, ii. c S(cr) = x if cr is ﬁreable in S. Intuitively, cr has some impact on the belief state S if it is ﬁreable in S. As such, for case (i), since cr is not ﬁreable, the cost impact of cr is 0. For case (ii), cr is ﬁreable, its body is satisﬁed and the bridge rule r is actually applicable in S. As such, the indicated cost of x is incurred, for the application of r. Then, the cost impact of cr is x.

Deﬁnition 4. Let Ci = (Li, kbi, bri, cbri) be a context of an MCS-OP M. The cost impact of the context Ci in a belief state S of M, denoted by ci S, is deﬁned as

cr cbri c S(cr)

The cost impact of an MCS-OP in a belief state S is the summation of the cost impacts of all contexts in S.

Deﬁnition 5. Let M = (C1, . . . , Cn) be an MCS-OP and S be a belief state of M. The cost impact of M in S, denoted by c M S , is deﬁned as c M S = P

When no confusion is possible, we omit the superscript M in c M S . It is worth to notice that given an MCS-OP M, a belief state S, and a cost-assignment bridge rule cr, by the deﬁnition of the cost impact of cr in S, c S(cr) is always determined. As such, the following proposition is derived immediately given Deﬁnitions 4 and 5.

Proposition 1. Given an MCS-OP M, c M S is well-deﬁned, i.e., it is determined for every belief state S of M.

The cost impact can be used to deﬁne a preference order among belief states as follows.

Deﬁnition 6. Let S1 and S2 be two belief states of an MCSOP M. We write S1 S2 if c S1 c S2, S1 S2 if c S1 < c S2, and S1 S2 if c S1 = c S2.

is referred to as the preference order among belief states.

Proposition 2. The ordering is a total preorder, i.e., is total, reﬂexive, and transitive.

Since is a preorder, we can use this ordering to deﬁne an order among the equilibria of an MCS-OP as follows.

Deﬁnition 7. A belief state S of an MCS-OP M is a most preferred equilibrium of M if S is an equilibrium of M, and There does not exist another equilibrium S of M where S = S such that S S.

Let EM be the set of all equilibria of an MCS-OP M. In other words, a most preferred equilibrium S of M can be deﬁned mathematically as S = arg min S EM c S. Note that, in this paper, we consider cost instead of utility, i.e., whenever a bridge rule is applied, a cost is incurred instead of a utility is produced. As such, a most preferred equilibrium minimizes the total incurred cost. The framework can thus easily be adapted to consider utility instead of cost, i.e., deﬁning S1 S2 if c S1 c S2 and maximizing utility by using S = arg max S EM c S.

Example 4. The MCS-OP M in Example 3 has two equilibria S and S that are the two equilibria of the MCS Mfh in Example 1 because MCS(M)=Mfh. In addition, c S = c1 S+c2 S = 50+120 = 170. Similarly, c S = c1 S +c2 S = 100+60 = 160. S S since c S < c S, and thus, S is the most preferred equilibrium of M.

Complexity Analysis We present some results on complexity analysis of MCS-OP M in this section. We consider here two problems: CONS(M): Decide whether M has a most preferred equilibrium; MOST (M, S): Decide whether a belief state S is a most preferred equilibrium of M. For this, we utilize the approach of output-projected belief states similar as in (Eiter et al. 2014; Brewka et al. 2011). Given an MCS-OP M, br M (resp. cbr M) denotes the set of all bridge rules (resp. cost-assignment bridge rules) in M.

Deﬁnition 8. Given an MCS-OP M and a context Ci of M, OUTi = {p | p is a belief of Ci, (i : p) or not (i : p) occurs in the body of some bridge rule or cost-assignment

CC(M) in P ΣP i PSPACE EXPTIME CONS(M) NP ΣP i PSPACE EXPTIME MOST (M, S) DP 0 DP i PSPACE EXPTIME

Table 1: Complexity of problems CONS(M) and MOST (M, S) with i 1.

bridge rule of some other context Cj in M} is called the set of output beliefs of Ci. Furthermore, given a belief state S = (S1, . . . , Sn) of M, the output-projected belief state S = (S 1, . . . , S n) is the projection of S to output beliefs of M: S i = Si OUTi. An output-projected belief state provides sufﬁcient information to evaluate the applicability of bridge rules, and thus one can deﬁne witnesses for equilibria using this projection. Deﬁnition 9. An output-projected belief state S = (S 1, . . . , S n) of an MCS-OP M is an output-projected equilibrium iff the following holds: for all 1 i n, S i ACCi(kbi {head(r) | r app(bri, S )}) OUTi. An output-projected belief state S contains information about all output beliefs, which is sufﬁcient to determine whether a bridge rule is applicable and its cost impact as well. Thus, app(bri, S) = app(bri, S ), and c S = c S . In addition, equilibria of an MCS-OP M are deﬁned as equilibria of MCS(M) which is identical to M excluding costassignment bridge rules. As a result, Lemma 1 below is obtained immediately from Lemma 1 in (Eiter et al. 2010). Lemma 1. For each equilibrium S of an MCS-OP M, its output-projected belief state S is an output-projected equilibrium. Conversely, for each output-projected equilibrium S of M, there exists at least one equilibrium T of M and its output-projected belief state T such that T = S . Following (Eiter et al. 2010), we also let the context complexity of a context Ci be the complexity of the problem: given an output-projected belief state S = (S 1, . . . , S n) of an MCS-OP M, decide whether there exists an Si ACCi(kbi {head(r) | r app(bri, S )}) such that S i = Si OUTi. The context complexity of an MCS-OP M, denoted with CC(M), is a (smallest) upper bound for the context complexity classes of all contexts Ci in M. For complexity analysis, as in (Brewka et al. 2018), we only consider ﬁnite MCS-OP, i.e., we do not consider rule schemas (which stand potentially for an inﬁnite amount of bridge rules or cost-assignment bridge rules), and assume that all knowledge bases in the given MCS-OP are ﬁnite. The complexity of MCS-OP are speciﬁed in Theorem 1. Theorem 1. Table 1 summarizes the complexities of membership of problems CONS(M) and MOST (M, S) depending on the context complexity. Here, the class DP 0 contains decision problems which are the conjunction of a P and an independent co-NP decision problem. Further, the class of DP i with i 1 contains decision problems which are the conjunction of a ΣP i and an independent ΠP i decision problem (e.g., for i = 1, a SAT and an independent UNSAT instance).

Proof. For CONS(M): By Proposition 2, the problem CONS(M) is equivalent with consistency checking (equilibrium existence) of M. As such, by the deﬁnition of equilibria of M, the complexity of CONS(M) is obtained based on the complexity of consistency checking (equilibrium existence) of MCS(M) whose result was investigated in (Brewka and Eiter 2007) and is given in Table 1. For MOST (M, S): Checking whether a belief state S = (S1, . . . , Sn) is a most preferred equilibrium includes: (T1) checking whether S is an equilibrium of M, and (T2) checking there is no other equilibrium T that is preferred to S (i.e., there is no T such that c T < c S). For (T1): this can be decided by (T1.1) evaluating the bridge rules on S, yielding for each context Ci a set Hi of applied bridge rule heads with respect to S which is linear with the ﬁnite number of bridge rules in Ci; and (T1.2) decides whether Si ACCi(kbi Hi) which is the context complexity of Ci. As such, (T1) can be decided in CC(M). For (T2): this can be decided by: (T2.1) guessing all output-projected belief states T ; (T2.2) evaluating the bridge rules on each T T , yielding for each context Ci a set Hi of applied bridge rule heads with respect to T which is linear with the ﬁnite number of bridge rules in Ci; (T2.3) deciding, whether there exists an T = (T1, . . . , Tn) such that Ti ACCi(kbi Hi) and T i = Ti OUTi which is the context complexity of Ci. (T2.4) checking whether c T = c T < c S. Note that if there are many T that satisfy (T2.3), then they will all incur identical costs, which equal to c T . (T2.4) the instance is yes instance iff all such checks fail, leading to the class co-NP (resp. ΠP i ) if CC(M) = P (resp. CC(M) = ΣP i ). If CC(M) = P, the complexity of MOST (M, S) is the class DP 0 that contains decision problems which are the conjunction of a P (i.e., for (T1)) and an independent co NP decision problem (i.e., for (T2)). Further, if CC(M) = ΣP i with i 1, the complexity of MOST (M, S) is the class of DP i that contains decision problems which are the conjunction of a ΣP i (i.e., for (T1)) and an independent ΠP i decision problem (i.e., for (T2)). Similarly, if CC(M) = PSPACE (resp. EXPTIME), then MOST (M, S) is the class of PSPACE (resp. EXPTIME).

Modeling Distributed Constraint Optimization

Distributed Constraint Optimization Problems (DCOPs) have emerged as a prominent agent model to govern the agents autonomous behavior, where agents coordinate their value assignments, in a decentralized and distributed manner, to optimize their objective functions. DCOPs can effectively model a wide range of problems in MAS setting (Fioretto, Pontelli, and Yeoh 2018). Next, we will review DCOP and show how it can be modeled by MCS-OP. A Distributed Constraint Optimization Problem (DCOP) (Modi et al. 2005; Petcu and Faltings 2005;

x1 x2 f1 0 0 10 0 1 20 1 0 35 1 1 40

x2 x3 f2 0 0 7 0 1 9 1 0 6 1 1 15

x3 x1 f3 0 0 9 0 1 2 1 0 27 1 1 35

Figure 1: Three Constraints of DCOP in Example 5

Gershman, Meisels, and Zivan 2009; Yeoh and Yokoo 2012) is a tuple D = X, D, F, A, α where X = {x1, . . . , xm} is a ﬁnite set of (decision) variables; D = {D1, . . . , Dm} is a set of ﬁnite domains, where each Di is the domain of variable xi X; F = {f1, . . . , fp} is a ﬁnite set of constraints, where each kj-ary constraint fj : Dj1 Dj2 . . . Djkj 7 R {+ } speciﬁes the cost of each combination of values of the variables in its scope; the scope of fj is denoted by scp(fj) = {xj1, . . . , xjkj };3

A = {a1, . . . , an} is a ﬁnite set of agents; α : X 7 A maps each variable to an agent. In the DCOP literature, the constraints fj are also called objective functions or cost functions. We say that an agent ai owns the variable xj if α(xj) = ai. Each constraint in F can be either hard (i.e., some value combinations result in a utility of + and must be avoided), or soft, (i.e., all value combinations result in a ﬁnite cost and need not be avoided). Given a constraint fj and a complete value assignment x (i.e., a value assignment for all variables), we denote with xfj a partial value assignment from x for all variables in scp(fj). For simplicity, given two value assignments x and x , we write x = x whenever (1) if (xi = di) x, then (xi = di) x , and (2) conversely, if (xi = di) x , then (xi = di) x. A solution of a DCOP is a complete value assignment x, and its corresponding total cost is the evaluation of all cost functions on x. The goal of a DCOP is to ﬁnd a cost-minimal solution x = arg minx Pp j=1 fj(xfj). In this paper, we adopt a simplifying assumption that each agent owns exactly one variable. This assumption is a common practice in the DCOP literature (Petcu and Faltings 2005; Gershman, Meisels, and Zivan 2009; Ottens, Dimitrakakis, and Faltings 2012). Thus, without loss of generality, we assume α(xi) = ai. It is relatively straightforward to generalize the ideas presented below to model a general DCOP, which allows agents to own multiple variables.

Example 5. Considering a DCOP D = X, D, F, A, α where X = {x1, x2, x3}, D = {D1, D2, D3} in which Di = {0, 1} with i {1, 2, 3}, A = {a1, a2, a3}, and α is deﬁned as α(xi) = ai. Figure 1 exhibits the three constraints f1, f2, and f3 between x1 and x2, between x2 and x3, and between x3 and x1, respectively. It is possible to see that the solution of D is the value assignment in which x1 = x2 = x3 = 1 which yields the minimal total cost of 40 + 15 + 35 = 90.

We will now show how a DCOP can be encoded using an MCS-OP. We ﬁrst specify the space of all solutions of a

3For simplicity, we assume a given ordering of variables

DCOP D = X, D, F, A, α with n agents (i.e., |A| = n) as equilibria of an MCS M D = (C1, . . . , Cn) of n contexts. Each context Ci corresponds to the agent ai A. For simplicity, we specify Ci=(Li, kbi, bri), for 1 i n, where: Li is the logic of the Answer Set Programming (ASP) framework (Gelfond and Lifschitz 1991). We also use the extended syntax of logic programs such as choice atoms, aggregates, etc. that have been adapted and implemented in most ASP solvers. kbi consists of a rule (assuming that Di = {d1 i , . . . , ds i})

1{value(xi, d1 i ), . . . , value(xi, ds i)}1 (3)

Intuitively, the rule of the form (3) enforces the selection of exactly one of the listed values (i.e., value(xi, dℓ i) with 1 ℓ s) to an answer set of kbi. Furthermore, value(xi, dℓ i) in an answer set of kbi means that the variable xi is assigned the value dℓ i Di. bri consists of bridge rules of the form

(Bfj(dj1 ,...,djkj )) costfj(V ) (j1 : value(xj1, dj1)),

. . . , (4) (jkj : value(xjkj , djkj ))

for each constraint fj (e.g., scp(fj) = {xj1, . . . , xjkj }) such that α(xj1) = ai, where for 1 ℓ kj, djℓ Djℓ and V = fj(dj1, . . . , djkj ). Intuitively, V is the cost speciﬁed by the constraint fj with respect to the respective value assignment of variables in scp(fj) that are given in the body of the bridge rule (i.e., value(xjℓ, djℓ)). Thus, V R {+ }. Note that bri will contain |Dj1| |Dj2| . . . |Djkj | bridge rule(s) for every fj such that α(xj1) = ai. In (4), Bfj(dj1,...,djkj ) is the unique name of the respective bridge rule. Given a solution x of a DCOP D in which xi is assigned value di Di (i.e., xi = di) for 1 i n, let E(x) = (S1, . . . , Sn) be a belief state where:

Si ={value(xi, di)} (5) {costfj (V ) | scp(fj) = {xj1, . . . , xjkj }, α(xj1) = ai,

V = fj(xj1 = dj1, . . . , xjkj = djkj )} (6)

Furthermore, given a belief state S = (S1, . . . , Sn) of M D, we let A(S) be a (partial) value assignment in which xi = di if value(xi, di) Si. The next theorem relates D and M D.

Theorem 2. Let D be a DCOP and M D be its corresponding MCS. We have:

If S is an equilibrium of M D, then x = A(S) is a solution of D; and If x is a solution of D, then, S = E(x) is an equilibrium of M D.

To be able to model the cost-minimal solution of DCOP, we extend the MCS M D into an MCS-OP MD by adding a set of cost-assignment bridge rules (i.e., cbri) to contexts of M D. Formally, given a DCOP D let MD = (C1, . . . , Cn) be an MCS-OP with Ci = (Li, kbi, bri, cbri)

where MCS(MD) = M D and cbri is: cbri ={Bfj(dj1,...,djkj )@V | Bfj(dj1,...,djkj ) bri,

head(Bfj(dj1,...,djkj )) costfj(V )} (7)

Intuitively, a cost-assignment bridge rule of the form (7) means that if the bridge rule Bfj(dj1,...,djkj ) is applicable

and its head (e.g., costfj(V )) is added to the respective knowledge base, then this bridge rule will incur a cost (e.g., a cost of V ). By Deﬁnition 5 and cost-assignment bridge rules of the form (7), it is simple to derive Lemma 2 below. Let us remind that, given a belief state S of MD, c MD S (c S, for short) is the cost impact of MD in S. Lemma 2. Let S be an equilibrium of MD. We have

costfj (V ) S V (8)

We also can conclude the next lemma to relate c S with the total cost on value assignment x = A(S). Lemma 3. Let D be a DCOP and MD be its corresponding MCS-OP. If x is a solution of D and S = E(x) is an equilibrium of MD (see the second item of Theorem 2), then

j=1 fj(xfj) (9)

The next theorem relates DCOP D and MCS-OP MD. Theorem 3. Let D be a DCOP and MD be its corresponding MCS-OP. We have: If S is a most preferred equilibrium of MD, then x = A(S) is a cost-minimal solution of D; and If x is a cost-minimal solution of D, then S = E(x) is a most preferred equilibrium of MD. To sum up, Theorem 3 means that one can use MCS-OP to model DCOPs, where the semantics of MCS-OP as most preferred equilibria are directly related to the semantics of DCOPs as cost-minimal solutions. Example 6. The DCOP D in Example 5 can be modeled using a MCS-OP MD = (C1, C2, C3) where with i {1, 2, 3} Ci = (Li, kbi, bri, cbri) in which (for short, in the following we use predicate val instead of value ): kbi = {1{val(xi, 0), val(xi, 1)}1 }

(br1 1) costf1(10) (1 : val(x1, 0)), (2 : val(x2, 0)) (br1 2) costf1(20) (1 : val(x1, 0)), (2 : val(x2, 1)) (br1 3) costf1(35) (1 : val(x1, 1)), (2 : val(x2, 0)) (br1 4) costf1(40) (1 : val(x1, 1)), (2 : val(x2, 1))

(br2 1) costf2(7) (2 : val(x2, 0)), (3 : val(x3, 0)) (br2 2) costf2(9) (2 : val(x2, 0)), (3 : val(x3, 1)) (br2 3) costf2(6) (2 : val(x2, 1)), (3 : val(x3, 0)) (br2 4) costf2(15) (2 : val(x2, 1)), (3 : val(x3, 1))

(br3 1) costf3(9) (3 : val(x3, 0)), (1 : val(x1, 0)) (br3 2) costf3(2) (3 : val(x3, 0)), (1 : val(x1, 1)) (br3 3) costf3(27) (3 : val(x3, 1)), (1 : val(x1, 0)) (br3 4) costf3(35) (3 : val(x3, 1)), (1 : val(x1, 1))

(br1 1)@10 (br1 2)@20 (br1 3)@35 (br1 4)@40

(br2 1)@7 (br2 2)@9 (br2 3)@6 (br2 4)@15

(br3 1)@9 (br3 2)@2 (br3 3)@27 (br3 4)@35

It is possible to see that MD has the most preferred equilibria: S = ({val(x1, 1)}, {val(x2, 1)}, {val(x3, 1)})

Expressivity: MCS-OP vs. DCOP

The previous section shows that MCS-OP can model DCOP. For a researcher in the DCOP community, it raises the question whether the use of MCS-OP would bring any advantages over the DCOP formalization or it is just yet another way to formalize DCOP. This section answers this question by presenting a problem that can be straightforwardly formalized using MCS-OP but not in DCOP.

Example 7. We extend Example 2 assuming that C2 also decides whether they go to their hotel by shuttle (s) or taxi (t). If they stay in Hilton, using s (resp. t) costs them $10 (resp. $30), and if they stay in Inn, using s or t costs them $40 or $30 respectively. C2 prefers the cheaper transportation because he will pay for this cost because it is not accounted to the total cost for C1 and C2 to travel together.

It is clear to see that since the cost of going to hotel is not accounted to the total cost, the most preferred group decision is the same as the one in Example 2 (i.e., select b and i) and thus taking a taxi to go to Inn because it is cheaper than taking a shuttle. The total cost remains the same as $160. Example 7 can be modeled using the MCS-OP M in Example 3, with the following modiﬁcation: (i) L2 is answer set optimization program (Brewka, Niemel a, and Truszczynski 2003), and (ii) kb2 is extended with the two rules s > t h and t > s i. Intuitively, the former rule states that if C2 stays in h, he prefers s to t. The latter rule means that if he stays in i, he prefers t to s. It is possible to check that the most preferred equilibrium of this updated MCS-OP is ({b}, {i, t}) that corresponds to the most preferred group decision mentioned above (i.e., select b, i and t). If we were to use DCOP to model Example 7, it is necessary to introduce three variables x1, x2, and x3 to represent the ﬂight, hotel, and taxi, respectively. Formally, a DCOP that may model Example 7 is D = {x1, x2, x3}, {D1, D2, D3}, {f1, f2, f3, f4}, {C1, C2}, α where D1 = {b, e}, D2 = {h, i}, D3 = {s, t}, α(x1) = C1, α(x2) = C2, α(x3) = C2, and the four constraints f1, f2, f3, and f4 are given in Figure 2. Intuitively, f1 and f2 represent the cost relation for x1 (by C1) and x2 (by C2), respectively. While f3 models the hard constraints between x1 and x2 (similar to br1 and br2), f4 represents the cost relation between x2 and x3 (by C2).

x1 f1 e 50 b 100

x2 f2 h 120 i 60

x1 x2 f3 e h 0 e i b h b i 0

x2 x3 f4 h s 10 h t 30 i s 40 i t 30

Figure 2: Four Constraints of DCOP Modeling Example 7

It is possible to check that this DCOP D derives an unexpected cost-minimal solution (i.e., select e, h, and s) which yields the minimal total cost of $180. It is because the preferences of C2 on taking a taxi or a shuttle to the hotel must be encoded as a constraint (i.e., f4), and thus its respective cost is accumulated to the total cost, deriving an unexpected minimal-cost solution. We believe that the lack of expressibility of the representation formalism of DCOP is the reason that prevents DCOP from successfully modeling the scenario in Example 7. MCS-OP is indeed more expressive than DCOP and could be useful in scenarios where some preferences among agents need to be considered locally and not be accounted for in the aggregation.

Related Work

To the best of our knowledge, MCS with preferences (MCSP), introduced in (Le, Son, and Pontelli 2015) and extended in (Le, Son, and Pontelli 2018) is the most similar proposal to MCS-OP in that both approaches aim at deﬁning a preference order (or a qualitative comparison) among equilibria of MCSs. We therefore relate MCSP and MCS-OP in details before discussing others extensions of MCS. MCSP assumes that the underlying logic of each context is a ranked logic, i.e., a logic with a preference order among its pairs of knowledge bases and belief sets. The preference order among equilibria of an MCSP is deﬁned by pairwise combining the local preference orders. Speciﬁcally, an equilibrium S = (S1, . . . , Sn) is strongly (weakly) preferred to another equilibrium S = (S 1, . . . , S n) if for every i, Si is strongly (weakly) preferred to S i with respect to the underlying ranked logic of context i. An equilibrium is most strongly (weakly) preferred if there exists no other equilibrium that is strongly (weakly) preferred to it. Thus, a most strongly (weakly) preferred equilibrium in MCSP is similar to a Nash equilibrium of a game for personal preferences among the contexts. Then, it is not an easy task to use MCSP in formalizing problems such as DCOP where the preference order often spans more than a single local context. Differently from MCSP, MCS-OP introduces an extra component, the cost-assignment bridge rules, to MCS and deﬁnes the notion of a cost impact of a belief state of the underlying MCS, which is used to deﬁne the order among belief states, and hence, equilibria. Being a non-negative value, the cost impact allows for the deﬁnition of a preorder among equilibria. Although it is convenient to use MCS-OP in modeling DCOP, we envision that MCS-OP might not be the best knowledge representation framework to model MCS with preferences where utilities/costs are difﬁcult to obtain. For this reason, we see MCS-OP as a useful alternative that compensates rather than competes with MCSP. Example 7 also

shows that MCS-OP can be used in scenarios where agents do have local preferences which, desirably, should not be considered in the aggregate preferences of the whole system. In this sense, MCS-OP provides a continuum from fully cooperative agents (as in MCS with a centralized controller) to non-cooperative or self-interested agents (as in MCSP). Beside equilibrium semantics, (Brewka and Eiter 2007) proposed minimal/grounded equilibria and well-founded semantics for MCS. For the former, one can directly utilize our approach (i.e., assigning conditional cost to bridge rules) to derive the preferences among equilibria, and thus obtain the semantics of the most preferred minimal/grounded equilibria. Moreover, it is unclear how our approach could be used to derive the preference in the well-founded semantics, as it is deﬁned using an antimonotone operator γM(.). Some signiﬁcant extensions of the MCS framework have been recently introduced. Managed MCS (m MCS) (Brewka et al. 2011) allows applied bridge rules to also perform arbitrary operations on context knowledge bases, e.g., deletion or revision operators. Reactive MCS (r MCS) (Brewka et al. 2018) and evolving MCS (e MCS) (Gonc alves, Knorr, and Leite 2014) are extensions of m MCS to allow changes of observations over time. In order to model real-world situations of multi-agent systems (MAS), DACMACS (Costantini and Gasperis 2015) integrates Data-Aware Commitmentbased MAS and MCS where agents not only interact among themselves, but also consult external heterogeneous dataand knowledge-bases to extract useful information. Clearly, these extensions are not designed to derive the preference among their respective equilibria, sequences of equilibria, or runs. It is our belief that an integration of cost-assignment bridge rules in these frameworks can enhance them by allowing the determination of a best run (or most preferred equilibrium). Other extensions of MCS have been proposed, where the introduction of a preference order requires more indepth study and will be the subject of future work, e.g., preference order among supported equilibrium semantics in generalized MCS (Tasharroﬁand Ternovska 2014), in operational-like semantics of asynchronous MCS (Ellmauthaler and P uhrer 2015), or in idealized run semantics of streaming MCS (Dao-Tran and Eiter 2017). Another related line of research is preference-based inconsistency management in MCS. An MCS is inconsistent if it does not have an equilibrium; research has been done to analyze the inconsistency to identify the most preferred diagnoses (Eiter et al. 2014). A diagnosis of an MCS intuitively is a pair of the set of all bridge rules that are either removed or set to be applicable in all belief states to make the MCS consistent. There are ways to accommodate preferences among diagnoses (see (Eiter and Weinzierl 2017)), and intuitively one can see that the most preferred equilibrium of M is an equilibrium of M after being applied to the most preferred diagnosis. Different from using diagnoses, (Mu, Wang, and Wen 2016) proposed to use Preferential MCS (PMCS), which are stratiﬁed MCS based on predetermined partial ordering among contexts. From such ordering, to address the inconsistency, one may ask for a maximal consistent section as the semantics of PMCS. Compared to our

work in this paper, there is a signiﬁcant difference: the works in inconsistency management are used to resolve MCS that do not admit an equilibrium, while in MCS-OP preference information is directly integrated into the semantics to select among existing equilibria. We note that there have been attempts to extend the DCOP model. For example, Asymmetric DCOPs (Grinshpoun et al. 2013) allows different agents owning variables in the scope of a constraint can incur to different costs, given a ﬁxed join assignment. Multi-Objective DCOPs (Marler and Arora 2004) are problems involving more than one objective function to be optimized simultaneously. However, these extensions do not address the difﬁculty in modeling scenarios where some preferences among agents need to be considered locally and not be accounted for in the aggregation. MCSOP could therefore be viewed as an alternative to DCOP that avoids this difﬁculty.

Conclusions and Future Works

We proposed Multi-context System for Optimization Problems (MCS-OP), which associate each context with a set of cost-assignment bridge rules that assign conditional cost to its bridge rules. The preferences order among equilibria are determined by the total incurred cost of actually-applied bridge rules in the equilibria. We discussed the MCS-OP s complexity and showed how to model DCOPs using MCSOP to illustrate the contribution of this paper to both the MCS community and the DCOP community. It is not difﬁcult to see that cost-assignment bridge rules can be introduced to any of the existing MCS extensions (e.g., MCSP, m MCS, asynchronous MCS (Ellmauthaler and P uhrer 2015) and streaming MCS (Dao-Tran and Eiter 2017)). In other words, MCS-OP can be easily integrated with almost all of the MCS extensions and the notion of a most preferred equilibrium of such an extension can be deﬁned as in the Most Preferred Equilibria subsection. For this reason, it would be interesting to investigate the integration of MCS-OP into other extensions of MCS and their properties (e.g., as we have mentioned in the previous subsection, the cost-assignment bridge rules could be useful in m MCS to identify the best runs). We also plan to investigate the use of a meta-reasoning transformation as in (Eiter and Weinzierl 2017), which implements a rewriting technique, to select most preferred equilibria. Furthermore, as we have mentioned in the introduction, there is only a few systems for computing MCS that have been developed. On the other hand, many efﬁcient and scalable systems for solving DCOPs. As such, we also plan to investigate algorithms for computing MCS/MCS-OP that can take advantage of approaches used in computing DCOP solutions.

Acknowledgments

The authors acknowledge the partial support from the NSF grants HRD-1345232 and IIS-1812628.

References Brewka, G., and Eiter, T. 2007. Equilibria in heterogeneous nonmonotonic multi-context systems. In Proc. of AAAI, 385 390. Brewka, G.; Eiter, T.; Fink, M.; and Weinzierl, A. 2011. Managed multi-context systems. In Proc. of IJCAI, 786 791. Brewka, G.; Ellmauthaler, S.; Gonc alves, R.; Knorr, M.; Leite, J.; and P uhrer, J. 2018. Reactive multi-context systems: Heterogeneous reasoning in dynamic environments. Artif. Intell. 256:68 104. Brewka, G.; Niemel a, I.; and Truszczynski, M. 2003. Answer set optimization. In Proc. of IJCAI, 867 872. Costantini, S., and Gasperis, G. D. 2015. Exchanging data and ontological deﬁnitions in multi-agent-contexts systems. In Proc. of Rule ML. Dao-Tran, M., and Eiter, T. 2017. Streaming multi-context systems. In Proc. of IJCAI, 1000 1007. Eiter, T., and Weinzierl, A. 2017. Preference-based inconsistency management in multi-context systems. J. Artif. Intell. Res. 60:347 424. Eiter, T.; Fink, M.; Sch uller, P.; and Weinzierl, A. 2010. Finding explanations of inconsistency in multi-context systems. In Proc. of KR. Eiter, T.; Fink, M.; Sch uller, P.; and Weinzierl, A. 2014. Finding explanations of inconsistency in multi-context systems. Artif. Intell. 216:233 274. Ellmauthaler, S., and P uhrer, J. 2015. Asynchronous multicontext systems. In Advances in Knowledge Representation, Logic Programming, and Abstract Argumentation - Essays Dedicated to Gerhard Brewka on the Occasion of His 60th Birthday, 141 156. Fioretto, F.; Pontelli, E.; and Yeoh, W. 2018. Distributed constraint optimization problems and applications: A survey. J. Artif. Intell. Res. 61:623 698. Gelfond, M., and Lifschitz, V. 1991. Classical negation in logic programs and disjunctive databases. New Generation Comput. 9(3/4):365 386. Gershman, A.; Meisels, A.; and Zivan, R. 2009. Asynchronous forward bounding for distributed cops. J. Artif. Intell. Res. 34:61 88. Gonc alves, R.; Knorr, M.; and Leite, J. 2014. Evolving multi-context systems. In Proc. of ECAI, 375 380. Grinshpoun, T.; Grubshtein, A.; Zivan, R.; Netzer, A.; and Meisels, A. 2013. Asymmetric distributed constraint optimization problems. J. Artif. Intell. Res. 47:613 647. Kumar, A.; Faltings, B.; and Petcu, A. 2009. Distributed constraint optimization with structured resource constraints. In Proc. of AAMAS, 923 930. Lass, R.; Kopena, J.; Sultanik, E.; Nguyen, D.; Dugan, C.; Modi, P.; and Regli, W. 2008. Coordination of ﬁrst responders under communication and resource constraints (Short Paper). In Proc. of AAMAS, 1409 1413. Le, T.; Son, T. C.; and Pontelli, E. 2015. Multi-context systems with preferences. In Proc. of PRIMA, 449 466.

Le, T.; Son, T. C.; and Pontelli, E. 2018. Multi-context systems with preferences. Fundam. Inform. 158(1-3):171 216. L eaut e, T., and Faltings, B. 2011. Coordinating logistics operations with privacy guarantees. In Proc. of IJCAI, 2482 2487. Maheswaran, R.; Tambe, M.; Bowring, E.; Pearce, J.; and Varakantham, P. 2004. Taking DCOP to the real world: Efﬁcient complete solutions for distributed event scheduling. In Proc. of AAMAS, 310 317. Mailler, R., and Lesser, V. 2004. Solving distributed constraint optimization problems using cooperative mediation. In Proc. of AAMAS, 438 445. Marler, R., and Arora, J. 2004. Survey of multi-objective optimization methods for engineering. Structural and Multidisciplinary Optimization 26(6):369 395. Mc Carthy, J. 1987. Generality in artiﬁcial intelligence. Commun. ACM 30(12):1029 1035. Modi, P. J.; Shen, W.; Tambe, M.; and Yokoo, M. 2005. Adopt: asynchronous distributed constraint optimization with quality guarantees. Artif. Intell. 161(1-2):149 180. Mu, K.; Wang, K.; and Wen, L. 2016. Preferential multicontext systems. Int. J. Approx. Reasoning 75:39 56. Ottens, B.; Dimitrakakis, C.; and Faltings, B. 2012. DUCT: an upper conﬁdence bound approach to distributed constraint optimization problems. In Proc. of AAAI. Petcu, A., and Faltings, B. 2005. A scalable method for multiagent constraint optimization. In Proc. of IJCAI, 266 271. Roelofsen, F., and Seraﬁni, L. 2005. Minimal and absent information in contexts. In Proc. of IJCAI, 558 563. Tasharroﬁ, S., and Ternovska, E. 2014. Generalized multicontext systems. In Proc. of KR. Ueda, S.; Iwasaki, A.; and Yokoo, M. 2010. Coalition structure generation based on distributed constraint optimization. In Proc. of AAAI, 197 203. Yeoh, W., and Yokoo, M. 2012. Distributed problem solving. AI Magazine 33(3):53 65. Zivan, R.; Glinton, R.; and Sycara, K. 2009. Distributed constraint optimization for large teams of mobile sensing agents. In Proc. of IAT, 347 354. Zivan, R.; Okamoto, S.; and Peled, H. 2014. Explorative anytime local search for distributed constraint optimization. Artiﬁcial Intelligence 212:1 26.