Multilateral Negotiation in Boolean Games with Incomplete Information Using Generalized Possibilistic Logic

1 Introduction and RelatedWork

Boolean games (BGs) are a strategic framework which uses propositional logic to formalize the goals of agents [Harrenstein et al., 2001]. Each agent controls the truth value of a subset of the atoms which build up these goals. In this paper, we investigate BGs in which the agents are uncertain about the preferences of the other agents. For example, suppose Bob and Alice are planning their Sunday afternoon: they can go to the beach or the forest or stay at home, and Alice can bring the dog or leave it at home. Since being a couple does not imply having identical preferences nor knowing exactly each other's preferences, Bob and Alice will have to compromise under incomplete information. However, they are not completely ignorant about each other's goals; for instance, Bob knows that Alice loves the dog and Alice knows that Bob loves the beach. In this paper, we investigate how they can use such knowledge to reach an agreement through negotiation. Moreover, we explore the link between having information about other agents' goals and obtaining a satisfactory agreement. To the best of our knowledge, our process is the

∗This research is funded by the Research Foundation Flanders (FWO).

Steven Schockaert

School of Computer Science and Informatics Cardiff University, Cardiff, UK schockaerts1@cardiff.ac.uk

Martine De Cock

Center for Data Science University of Washington, Tacoma, USA mdecock@uw.edu

first multilateral negotiation protocol for BGs that takes uncertainty w.r.t. the other agents' goals into account.

Although uncertainty in games has been studied extensively (see e.g. [Osborne and Rubinstein, 1994]), the literature on BGs with incomplete information is currently limited. In one framework, agents have beliefs about the values of environment variables, which are not controlled by any of the agents [Grant et al., 2011]. Another approach limits the set of action variables of which an agent can observe the assigned values [ ˚Agotnes et al., 2013b]. The latter framework has been extended to epistemic BGs [ ˚Agotnes et al., 2013a], describing goals by means of a multi-agent epistemic modal logic. However, in the latter approach agents are still fully aware of each others' goals, i.e. ˚Agotnes et al. [2013a] consider agents whose goal is to obtain a particular epistemic state. To the best of our knowledge, the only work on BGs with uncertainty w.r.t. the agents' goals is [De Clercq et al., 2014], which uses possibilistic knowledge bases to formalize the beliefs of the agents about the goals of others.

In this paper, we propose the use of generalized possibilistic logic (GPL) [Dubois et al., 2014] to define BGs with incomplete information. Note that this is different from the use of uncertainty models, such as the Bayesian approaches commonly applied to study games with uncertainty (see e.g. [Harsanyi, 1967]), which can be used e.g. to model beliefs about the characteristics of other agents. Although De Clercq et al. [2014] also use possibilistic logic to model uncertainty in BGs, our motivation differs: whereas the former work uses possibilistic logic to encode graded beliefs about other agents goals, we use possibilistic logic to compactly describe agents' preferences, and generalized possibilistic logic to describe incomplete knowledge about another agent's preferences. Our use of GPL also differs from approaches such as CP-nets, which also aim to compactly model preferences, but only capture a single preference structure and are thus less suitable for modeling incomplete information. To the best of our knowledge, this is the first research on using GPL to model uncertainty about other agents' preferences.

We then investigate how knowledge about other agents' goals can be used for multilateral negotiation. Negotiating allows agents in a strategic setting to settle on an agreement outcome, where agents can be human as well as artificial, such as computers, robots or self-driving cars. A multilateral bargaining protocol in BGs with complete information has been investigated in [Dunne et al., 2008], showing that, when the logical structure of the goals is restricted, the protocol is guaranteed to end in a Pareto optimal outcome, i.e. no agent can improve its position without another agent being worse off. In this paper, we propose a protocol which converges to an acceptable agreement without restrictions on the game structure. Moreover, under complete information our protocol always results in a discrimin optimal outcome. Discrimin optimality refines Pareto optimality [Dubois et al., 1997], and while the latter indeed ensures efficiency, it is often not sufficient to characterize desirable outcomes [Bouveret and Lang, 2008]. Suppose, for instance, that two agents are negotiating in a situation with two Pareto optimal outcomes, with utility vectors (1, 0.2) respectively (0.5, 0.6), where utility reflects the degree of satisfaction of the agents. A natural concept arising in negotiation is fairness: intuitively, the latter utility vector is more fair than the former. In the literature, several notions of fairness apart from discrimin optimality have been introduced and studied; we refer the interested reader to [Tungodden, 2000] for an overview and discussion.

We investigate negotiation in BGs with incomplete information since, in strategic settings, it is often irrealistic to assume that an agent has access to another agent's goals. Indeed, agents might deliberately conceal such information, or might not have exchanged it. The literature on bargaining is extensive, and covers a wide range of possible settings, such as discrete versus continuous bargaining (e.g. prices [Fatima et al., 2002]), bilateral [Amgoud and Prade, 2003; Luo et al., 2003] versus multilateral bargaining, transferable and non-transferable utility, limited versus unlimited number of responses, modeling incomplete knowledge through probability theory [Fatima et al., 2002], through Cartesian products of complete knowledge problems [Bossert and Peters, 2001], or by means of possibilistic logic [Amgoud and Prade, 2003]. To the best of our knowledge, our work is the first research on negotiation that considers incomplete knowledge about other agents' goals in a BG setting.

The paper is structured as follows. First, we give some background on BGs. In Section 3, we propose a negotiation protocol for BGs with complete information and characterize the agreement outcomes. Next, we explain how GPL can be used to represent knowledge about other agents' preferences in Section 4. Then we generalize the negotiation protocol of Section 3 to BGs with incomplete information. We characterize the agreement outcomes, linking back to those under complete information. Additionally, we show how knowledge is crucial for an agent to reach a satisfying agreement. To conclude, we discuss several future work directions.

2 Background on Boolean Games

The logical language LΦ associated with a finite set of atoms Φ contains the following formulas: (i) every atom of Φ, (ii) the logical constants ⊥ and ⊤, and (iii) the formulas ¬ϕ and ϕ ∧ ψ for every ϕ, ψ ∈ LΦ. As usual, we use the abbreviations ϕ → ψ ≡ ¬(ϕ∧¬ψ) and ϕ∨ψ ≡ ¬(¬ϕ∧¬ψ). An interpretation of Φ is defined as a subset ν of Φ, with the convention that all atoms in ν are interpreted as true (⊤) and all atoms in Φ \ ν are interpreted as false (⊥). An interpretation can be extended to LΦ in the usual way. If a formula ϕ ∈ LΦ is true in an interpretation ν, we denote this as ν |= ϕ. We denote the set of interpretations in which ϕ is true as JϕK.

Originally, the utilities in BGs were binary, but several extensions have been introduced to allow more general preferences. Examples are the addition of costs [Dunne et al., 2008], the use of a prioritized goal base instead of a single goal [Bonzon et al., 2006; De Clercq et al., 2014] or the use of many-valued Łukasiewicz logic to formalize the idea of weighted goal satisfaction [Marchioni and Wooldridge, 2014]. In our paper, we use the definition of a BG as stated in [De Clercq et al., 2014]. The latter is a particular case of generalized BGs [Bonzon et al., 2006] in which the preference relations are total. Additionally, we incorporate a constraint δ, restricting the possible joint actions of the agents. This is a generalization of the constraints in [Bonzon et al., 2012], which only restrict the individual actions of the agents.

Definition 1 (Boolean Game)

A Boolean game (BG) is a tuple G = (δ,Φ1, . . . ,Φn, Γ1, . . . , Γn). For every agent i in N = {1, . . . , n}, Φi is a finite set of atoms such that Φi ∩ Φj = ∅, ∀j ̸= i. We write Φ = ⋃i∈N Φi. For every i ∈ N, Γi = {γ 1 i ; . . . ; γ p i } is i's prioritized goal base. The formula γm i ∈ LΦ is agent i's goal of priority m. We assume that every agent has p priority levels and that δ∧γm i ̸= ⊥ for every i ∈ N andm ∈ {1, . . . , p}. Finally, δ is a consistent formula in LΦ, which encodes the integrity constraints of the game G.

The set Φ contains all action variables. Agent i controls Φi and can set these atoms to true or false. By convention, goals are ordered from high (level 1) to low priority (level p).

Example 1

Alice and Bob, who share a car, are planning their afternoon. Alice controls Φ1 = {bA, fA, dA} and Bob controls Φ2 = {bB, fB}. Agent i can drive to the beach (set bi to true) or to the forest (set fi to true). If Alice sets dA to true, she takes the dog. The game is constrained by δ = ¬(bB ∧ fB) ∧ ¬(bA ∧ fA) ∧ (bB → ¬fA) ∧ (bA → ¬fB). Alice and Bob's goal

Thus Alice prefers staying at home with her dog over leaving without it. Bob prefers to take Alice to the beach without the dog. However, he still prefers to go to the beach with Alice and the dog over going to the forest with Alice, and he prefers going to the forest with Alice over all remaining possibilities.

Definition 2 (Outcome)

An interpretation of Φ is called an outcome of G. We denote the set of all outcomes as V.

For the ease of presentation, we define a utility function that is scaled to the unit interval.

Definition 3 (Utility Function)

For each i ∈ N and ν ∈ V, the utility of i in ν is defined as

with min ∅ = p + 1.

The utility takes values in Λp = {0, 1p , 2p , . . . , 1}. We will denote the vector of utility functions (u1(ν), . . . , un(ν)) as U(ν). In Example 1, we have for instance U({fA, fB, dA}) = (1, 0.33), U({bB, bA}) = (0, 1), U({bA, bB, dA}) = (0.67, 0.67) and U({fA, bB}) = (0, 0). In the context of bargaining, it is natural that agents try to achieve an outcome that is, among others, efficient. A wellknown efficiency concept is Pareto optimality.

Definition 4 (Pareto Efficiency)

For every ν, ν ′ ∈ V it holds that ν >p ν ′ iff

We denote the set of Pareto optimal outcomes in V as

Intuitively, an outcome is Pareto optimal if no agent can be better off without another agent being worse off. It is easy to see that every BG has at least one Pareto optimal outcome.

A well-known refinement of the Pareto ordering incorporating a notion of fairness is the discrimin ordering [Dubois et al., 1997]. To define it, we denote the set of agents whose utility is the same in ν and ν ′ as eq(U(ν), U(ν ′ )), i.e. eq(U(ν), U(ν ′ )) = {i ∈ N | ui(ν) = ui(ν ′ )}.

Definition 5 (Discrimin Ordering)

For every ν, ν ′ ∈ V it holds that ν >d ν ′ iff

We define the set of discrimin optimal outcomes as

It is easy to see that >d is a strict order relation on V. Straightforwardly, it holds that Optdiscri ⊆ Optpar and Optdiscri ̸= ∅. In Example 1, (bA, bB, dA) is the unique discrimin optimal outcome, although it is not the only Pareto optimal outcome.

3 Negotiating under Complete Information

We are interested in a negotiation protocol that is guaranteed to converge within a finite number of steps. Therefore, we want agents to make offers according to a negotiation rule, which assures that every offered outcome is an improvement compared to the previous one. For instance, an agent might only be allowed to make a counteroffer if no agent is worse off than in the previous offer. Obviously, this rule will lead to Pareto optimal outcomes. However, the rule is so strict that the result can hardly be called fair: the first agent simply offers the outcome which yields its personal highest utility and no other agent is allowed to make a counteroffer which lowers the first agent's utility. Suppose, for instance, that there are two possible utility vectors: (1, 0) and (0.5, 0.5). If the first agent opens the negotiation with (1, 0), the other agent would not be allowed to counter this offer with (0.5, 0.5). To develop a fairer rule, we consider two properties that characterize a valid counteroffer. First of all, an agent is only interested in making a counteroffer if its own utility improves compared to the original offer. Second, the agents apply the silver rule or ethic of reciprocity, proposed by the Confucian Way of Humanity [Hertzler, 1934]:

One should not treat others in ways that one would not like to be treated.

In our negotiation protocol, an agent reasons as follows: if I do not accept an offer of utility k, I should not lower another agent's utility to k or less in order to improve my own. Therefore, if an agent decides to lower other agents' utilities, it should offer more than k. We formally define the set co(i, ν) of agent i's legal counteroffers to ν as follows (i ∈ N, ν ∈ V):

We suggest the following negotiation protocol. In a given order, agents make proposals one by one. Without loss of generality, we assume that this order is {1, 2, . . . , n}.

Algorithm 1 Negotiation Protocol for BG

ν ← ν ′ with ν ′ ∈ JδK % Agent 1 proposes ν ′ accepted ← 1; i ← 2 while accepted < n do if co(i, ν) == ∅ then % Agent i accepts the offer accepted ← accepted +1 else% Agent i rejects the offer and makes a counteroffer ν ← ν ′ with ν ′ ∈ co(i, ν) accepted ← 1 end if i ← (i == n ? 1 : i +1) end while

Algorithm 1 depends on a selection function to choose which ν ′ ∈ JδK and ν ′ ∈ co(i, ν) are made as an offer. However, the results discussed in the paper hold regardless of this selection. The negotiation protocol ends if an offer ν is made such that no counteroffers can be made, i.e. ∀i ∈ N : co(i, ν) = ∅. We can prove that, whenever an offer is rejected, the new offer is fairer according to the discrimin ordering.

Proposition 1

Sketch. This follows immediately from the definitions of co(i, ν) and >d, and the fact that either uj(ν ′ ) > uj(ν) or uj(ν ′ ) < uj(ν) for every j /∈ eq(U(ν), U(ν ′ )).

It follows that every discrimin optimal outcome is accepted.

Corollary 2

Conversely, we can also show that only discrimin optimal outcomes will be overall accepted.

Proposition 3

Sketch. By definition of Optdiscri, there exists a ν ′ ∈ V such that ν ′ >d ν. It is straighforward to prove that ν ′ ∈ co(i, ν) for every agent i /∈ eq(U(ν), U(ν ′ )) such that ui(ν) = minj /∈eq(U(ν),U(ν ′ )) uj (ν).

Note that since there are only a finite number of offers that can be made, and because each offer must strictly improve the previous offer in terms of the discrimin ordering, we know that the negotiation protocol always ends. From Corollary 2 and Proposition 3 we moreover know that the possible outcomes at the end of the negotiation protocol are exactly the discrimin optimal outcomes. This result implies that the first offering agent still has a strong advantage, as this agent can select the discrimin optimal outcome that yields the highest personal utility, which no agent is allowed to reject. For instance, if the only discrimin optimal outcomes have utility vectors (1,0.5) and (0.5,1), agent 1 should propose the former and agent 2 has no choice but to accept. If the first agent follows this strategy, the negotiation ends within one step.

Remark 1

In our protocol, it is irrelevant which agent controls which atoms. The dependence of actions implied by the constraint δ forces agents to negotiate about what actions they will undertake. In Example 1, Alice and Bob cannot decide individually to go out. However, Alice can decide to stay with the dog without violating δ. Moreover, both Alice and Bob can decide to stay home without restricting the other agent's options w.r.t. the constraint. Thus Alice is able to reach a utility of 0.33 without negotiating, and Bob will be stuck with a utility of 0. The utility vector (0.33, 0) can be viewed as the disagreement point [Binmore et al., 1986], i.e. the utility the agents would receive if they fail to reach an agreement. This information could be added to the framework: Alice rejects everything with a lower utility than 0.33, ergo Bob should not make such offers during the negotiation. Note that we can incorporate this info in the constraint δ, demanding that the utility of every agent is greater than its disagreement utility.

4 Modeling Knowledge about Preferences using Generalized Possibilistic Logic

Possibilistic logic extends classical logic by associating weights with formulas. These weights were originally interpreted as degrees of certainty [Dubois et al., 1994], but can also be viewed as degrees of satisfaction [Dubois et al., 1996; Benferhat et al., 2001], allowing the use of possibilistic logic for modeling preferences. Generalized possibilistic logic (GPL) is a recent extension of possibilistic logic, which was introduced to model incomplete knowledge about the beliefs of another agent [Dubois et al., 2014]. In this paper, we use GPL to compactly encode what each agent knows about the preferences of another agent.

We define Λ+p = { 1p , 2p , . . . , 1}. The GPL language LpN with p + 1 satisfaction levels is defined as follows:

• If α ∈ LΦ and λ ∈ Λ+p , then Nλ(α) ∈ LpN.
• If γ1 ∈ LpN and γ2 ∈ LpN, then ¬γ1 and γ1 ∧ γ2 in LpN. We define the involutive function inv : Λ+p → Λ+p with inv(λ) = p+1 p -λ. GPL uses the following abbreviations:

where ϕν for ν ∈ V is defined as the conjunction of literals that are true in ν, i.e. ϕν = ∧ν|=p p ∧ ∧ν̸|=p ¬p. The semantics of GPL formulas are defined through normalized possibility distributions. In this context, a possibility distribution π is a V → Λp mapping, encoding the degree to which each outcome is desirable to a given agent. A GPL knowledge base K is a finite set of formulas in LpN. It holds that π is a model of a GPL knowledge base K iff π is a model of each formula in K. Moreover:

• π is a model of Nλ(α) iff N(α) ≥ λ;
• π is a model of γ1 ∧ γ2 iff π is a model of γ1 and π is a model of γ2;
• π is a model of ¬γ1 iff π is not a model of γ1;

where N is the necessity measure induced by π, i.e. N(α) = minν̸|=α (1 - π(ν)). The set of all models of K is denoted as Mod(K). In this paper, we use the following established links between syntax and semantics [Dubois et al., 2014]:

In particular, it holds for every ν ∈ V that:

We explain the intuition of GPL formulas below, after introducing the BG framework with incomplete preferenceinformation by means of GPL knowledge bases.

Definition 6 (BG with Incomplete Preference-Information)

A Boolean game with incomplete preference-information is a tuple G = (δ,Φ1, . . . ,Φn, Γ1, . . . , Γn, K1, . . . ,Kn) with Φ1, . . . , Φn, Γ1, . . . , Γn as before and Ki = {K1 i , . . . ,Kn i }, where Kj i is a GPL knowledge base such that N1(δ) ∈ Kj i , Mod(Ki i ) = {ui} and uj ∈ Kj i for every i, j ∈ N.

The GPL base Kj i encodes what agent i knows about the preferences of j. The assumption N1(δ) ∈ Kj i means that each agent knows that all agents are aware of the integrity constraint, i.e. agent i knows that the utility of agent j is 0 if the outcome violates δ. The assumption Mod(Ki i ) = {ui} means that agent i knows its own utility. This can be accomplished if Ki i ∧δ)

i contains the formulasNmp (∨ml=1 γ l i ) and∆inv( mp ) (γm for every m ∈ {1, . . . , p}. Finally, the assumption uj ∈ Kj i means that the pieces of information that agent i has about agent j's preferences do not conflict with agent j's real preferences.

Note that GPL, in contrast to e.g. CP-nets [Boutilier et al., 2004], has the ability to model ignorance. Indeed, CP-nets can encode that an agent has no preference between two alternatives, but it cannot encode that we do not know whether the agent has a preference. On the other hand, GPL does assume that the preferences can be modeled by means of a total order. Importantly, GPL allows us to compactly describe information about another agent's preferences. For instance, through use of the operators N and ∆, we can naturally encode necessary and sufficient conditions, respectively, for an agent to reach a certain utility. Moreover, we can easily encode comparative preferences, stating that the utility of an agent will always be higher for outcomes satisfying a formula α than for outcomes satisfying a formula β. To this end, we introduce some abbreviations for α, β ∈ LΦ:

Intuitively, whenever Kj i |= α′ ⪰ α, agent i knows that the utility of agent j in any outcome that satisfies α′ is at least the utility of j in any outcome that satisfies α. Similarly, whenever Kj i |= α′ ≻ α, agent i knows that agent j strictly prefers any outcome in which α′ is true to any outcome in which α is true. Another useful abbreviation is:

Intuitively, whenever Kj i |= α′ ≻c α, agent i knows that the outcome with the highest utility satisfying α′ is strictly preferred to the outcome with the highest utility satisfying α. This allows us to model conditional preferences. For instance, α ∧ β1 ≻c α ∧ β2 means that, in an ideal world, if α is true, the agent strictly prefers β1 over β2. An exception x to the latter can be modeled by α ∧ x ∧ β2 ≻c α ∧ x ∧ β1. This is similar in spirit to the possibilistic semantics of conditionals [Benferhat et al., 1997]. Conditional preferences in possibilistic logic have been studied among others in [Dubois et al., 2006].

We illustrate the expressiveness of GPL for modeling preferences in the following example.

Example 2

Recall the context of Example 1 and suppose Alice knows that Bob's first priority goal can only be fulfilled without bringing the dog. This is encoded as N1 3 (¬dA) ∈ K2 1 . If Alice knows that Bob prefers going to the beach exclusively with her over going to the beach with her and the dog, this is encoded as (bA ∧ bB ∧ ¬dA) ≻ (bA ∧ bB ∧ dA) ∈ K2 1 . If Bob knows that Alice is unhappy without her dog, this is encoded as N1(dA) ∈ K1 2 . For Bob to encode that Alice is at least partially happy when she is with the dog, regardless of whatever else happens, he adds ∆13 (dA) to K1 2 .

We now define a set of possibilistic discrimin optimal outcomes in V. Intuitively, an outcome ν is optimal if for any outcome ν ′ which dominates ν according to the discrimin ordering, the agents who are better off in ν ′ than in ν are not aware that ν ′ is a valid counteroffer in the sense of (1).

Definition 7 (Possibilistic Discrimin)

We define the set of possibilistic discrimin optimal outcomes:

It is easy to see that Optdiscri ⊆ Optpdiscri . In particular, when each agent has full knowledge, i.e. Mod(Kj i ) = {uj} for every i, j ∈ N, Optdiscri and Optpdiscri coincide.

5 Negotiating under Incomplete Information

We now analyze negotiation in BGs under incomplete information. The protocol remains as specified in Algorithm 1: agents take turns in responding to an offer, by accepting it or making a counteroffer. However, the set of legal counteroffers co(i, ν) might be unknown to agent i. Indeed, determining the allowed counteroffers requires - possibly unknown - information about the other agents' utility. Therefore, we replace co(i, ν) by cop (i, ν), which intuitively contains every outcome ν ′ ∈ JδK for which agent i has enough information to derive that ν ′ is indeed a legal counteroffer to ν:

with ≻ and ⪰ as defined in (2). As before, an outcome ν is agreed upon iff cop (i, ν) = ∅ for every i ∈ N.

We can prove that every possibilistic discrimin optimal outcome is generally accepted. To this end, we first prove the following link between the sets of valid counteroffers under complete and incomplete information.

Proposition 4

Proof. Let ν ′ be an arbitrary element of cop (i, ν). By definition, it holds that ui(ν ′ ) > ui(ν) ∧ ∀j ∈ N : Kj i |= (∆ui(ν)+ 1p (ϕν ′) ∨ ν ′ ⪰ ν). Let j ∈ N. It remains to prove that uj(ν ′ ) < uj(ν) ⇒ uj(ν ′ ) > ui(ν) or equivalently uj(ν ′ ) ≥ uj(ν) ∨ uj(ν ′ ) > ui(ν). By definition 6, it holds that uj is a model of Kj i . Consequently, it holds that uj satisfies either ∆ui(ν)+ 1p (ϕν ′) or ν ′ ⪰ ν. In the first case, it holds that uj(ν ′ ) ≥ ui(ν) + 1p or thus uj(ν ′ ) > ui(ν). In the second case, it holds that uj(ν ′ ) ≥ uj(ν). In any case it holds that uj(ν ′ ) ≥ uj(ν) ∨ uj(ν ′ ) > ui(ν).

Proposition 5

Proof. Let ν ∈ Optpdiscri and i ∈ N. Suppose there exists some ν ′ ∈ cop (i, ν). If ¬(ν ′ >d ν), then Propositions 1 and 4 imply that ν ′ /∈ cop (i, ν), a contradiction. Now assume that ν ′ >d ν. Since ν ′ ∈ cop (i, ν) and Mod(Ki i ) = {ui} it follows that ui(ν ′ ) > ui(ν). Because ν ∈ Optpdiscri , we know that there exists some j ∈ N and uji ∈ Mod(Kj i ) such that uji (ν ′ ) < uji (ν) and uji (ν ′ ) ≤ ui(ν). Consequently, uji does not satisfy ∆ui(ν)+ 1p (ϕν ′ ), nor ν ′ ⪰ ν. This contradicts the fact that Kj

Conversely, we can also show that only possibilistic discrimin optimal outcomes will be generally accepted.

Proposition 6

Proof. For ν ∈ V \ Optpdiscri there exists a ν ′ ∈ V such that ν ′ >d ν and there exists an agent i ∈ N such that ui(ν ′ ) > ui(ν), and for every j ∈ N and uji ∈ Mod(Kj i ) it holds that uji (ν ′ ) ≥ uji (ν) or uji (ν ′ ) > ui(ν). Since Mod(Ki i ) = {ui}, it follows that Ki i |= ν ′ ≻ ν. Now let j be an arbitrary agent in N. For every model uji of Kj i such that uji (ν ′ ) ≥ uji (ν) it holds that uji models ν ′ ⪰ ν. For every model uji of Kj i such that uji (ν ′ ) > ui(ν) it holds that uji models ∆ui(ν)+ 1p (ϕν ′). Consequently, we have Kj i |= (∆ui(ν)+ 1p (ϕν ′) ∨ ν ′ ⪰ ν), and thus ν ′ ∈ cop (i, ν).

Note that since the number of possible offers is finite and because each offer must strictly improve the previous offer in terms of the discrimin ordering, the negotiation protocol always ends. From Corollary 5 and Proposition 6 we know that the possible outcomes at the end of the negotiation protocol are exactly the possibilistic discrimin optimal outcomes.

From Optdiscri ⊆ Optpdiscri and Proposition 5, it follows that any discrimin optimal offer is overall accepted under incomplete information. However, Example 3 shows that the opposite does not hold, i.e. a non-discrimin optimal outcome might be accepted under incomplete information.

Example 3

Suppose, in the context of Example 1, that Alice has absolutely no information concerning Bob's goals. If Bob may make the first offer and suggests to go to the beach together without the dog, Alice's utility is 0. Although this outcome is discrimin dominated by going to the beach with the dog, Alice is unable to make this counteroffer, because she does not know whether Bob's utility is at least 0.33 in that case or whether Bob's utility is at least the same as in his first offer.

Note that, in contrast to a fully informed agent, an agent with limited knowledge might not be able to open with a discriminoptimal solution. It is clear that having no information leaves an agent in a very weak position. Indeed, if agent i knows nothing about the preferences of another agent, it holds that cop (i, ν) = ∅ for every ν ∈ V, thus agent i is obliged to accept every offer. In contrast, an agent who has full knowledge knows all valid counteroffers and may be able to achieve a better outcome than in any discrimin optimal outcome, cfr. Bob in Example 3. Note that an agent with full knowledge can either use a safe or a risky selection function. Suppose for instance that there are only three possible utility vectors: (0.6, 0.4), (0.4, 0.6) and (1, 0.2). If agent 1 proposes (0.6, 0.4), it is certain that agent 2 accepts. Alternatively, if agent 1 proposes (1, 0.2) and agent 2 does not know that there exists a valid counteroffer, agent 1 can get away with an unfair agreement, yielding a higher utility than in any fair outcome. However, if agent 2 knows that (0.4, 0.6) is a valid counteroffer, the negotiations end in (0.4, 0.6), leaving agent 1 worse off than if it had proposed (0.6, 0.4) right away. This discussion shows that an interesting extension of the framework would be to allow agents to reason about the knowledge of others. Such knowledge can be encoded using multi-agent extensions of modal logics for epistemic reasoning, although we are then forced to express knowledge about preferences at the propositional level (e.g. by introducing variables gm i to denote the mth most preferred goal of agent i as in [De Clercq et al., 2014]). This extension would allow agents to act based on their knowledge of how other agents would react to various counteroffers, as is common in the field of epistemic game theory [Perea, 2012].

6 Conclusion and FutureWork

We have developed a framework for BGs with incomplete information, using GPL to compactly represent agents' knowledge about the preferences of others. We also proposed a multilateral negotiation protocol, which uses an intuitive negotiation rule based on the ethic of reciprocity principle and is guaranteed to converge within a finite number of steps. Moreover, we characterized the set of possible outcomes of the negotiation process, confirming the intuition that incomplete knowledge may lead to negotiation inefficiency, i.e. the agreement outcome may not be fair or efficient. In our protocol, the order of the agents plays an important role, which is natural in hierarchical contexts (e.g. leader-follower type setting, where followers can only question proposals by leaders if they can prove their unfairness). Alternatively, the power of agents [Ben-Naim and Lorini, 2014] can be used to deduce a sensible ordering in which agents are allowed to make offers: the most powerful agent can make the initial offer. Note, however, that the use of GPL for encoding knowledge about the preferences of others is independent of the negotiation protocol. Consequently, future research w.r.t. alternative negotiation protocols e.g. for settings in which agents have equal status can also rely on our GPL framework.

Even though the negotiation model we have discussed in this paper is rather simple, it offers a rich basis from which we can study a wide variety of settings. Interesting extensions could include the use of agents who expand their knowledge base during the protocol, by drawing conclusions from the offering behavior of other agents [Cramton, 1984]. Another option is to use different negotiation rules, e.g. an agent could be allowed to make a counteroffer ν if it does not know that ν is an illegal counteroffer. Additionally, we can allow

'third party' agents to protest against offers, in case they know that the offer is illegal. However, protesting against an unfair proposal requires the revelation of knowledge, which might weaken the bargaining power of the agent. Hence, it is not straightforward that protesting is always in the protester's advantage, even if it initially leads to a higher utility. Other options for alternative protocols include the addition of time constraints [Kraus et al., 1995] or the use of arguments to support an offer [Amgoud and Prade, 2003].