We define a new protocol rule, Now or Never (NoN), for bilateral negotiation processes which allows self-motivated competitive agents to efficiently carry out multi-variable negotiations with remote untrusted parties, where privacy is a major concern and agents know nothing about their opponent. By building on the geometric concepts of convexity and convex hull, NoN ensures a continuous progress of the negotiation, thus neutralising malicious or inefficient opponents. In particular, NoN allows an agent to derive in a finite number of steps, and independently of the behaviour of the opponent, that there is no hope to find an agreement. To be able to make such an inference, the interested agent may rely on herself only, still keeping the highest freedom in the choice of her strategy. We also propose an actual NoN-compliant strategy for an automated agent and evaluate the computational feasibility of the overall approach on instances of practical size.
Automated negotiation among rational agents is crucial in Distributed
Artificial Intelligence domains as, e.g., resource allocation [
We present a framework which allows two self-motivated, competitive agents to negotiate efficiently and find a mutually satisfactory agreement in a particularly hostile environment, where each party has no information on constraints, preferences, and willingness to collaborate of the opponent. This means that also the bounds of the domains of the negotiation variables are not common knowledge. Our framework deals with negotiations over multiple constrained variables over the type of real numbers, regarding integer or categorical variables as special cases.
The present setting is very different from what is often assumed in the
literature: the set of possible agreements is infinite and agents do not even know (or
probabilistically estimate) possible opponent’s types, variable domain bounds
or most preferred values. It is not a split-the-pie game as, e.g., in [
A major problem in our setting is that even termination of the negotiation process is not granted: it is in general impossible for the single agent to recognise whether the negotiation is making some progress, or if the opponent is just wasting time or arbitrarily delaying the negotiation outcome.
We solve this problem by proposing a new protocol rule, Now or Never (NoN) (Section 3), explicitly designed as to ensure a continuous progress of the negotiation. The rule (whose fulfilment can be assessed independently by each party using only the exchanged information) forces the agents to never reconsider already taken decisions, thus injecting a minimum, but sufficient amount of efficiency in the process. This leads to the monotonic shrinking of the set of possible agreements, which in turn allows each agent to derive in a finite number of steps, independently of the behaviour of the opponent, that there is no hope to find an agreement.
Furthermore, we discuss the notion of non-obstructionist agents, i.e., agents who genuinely aim at efficiently finding an agreement, even sacrificing their preferences (among the agreements they would accept). If both agents are nonobstructionist, the NoN rule guarantees that, whenever the termination condition arises, then no agreement actually exists. Hence, in presence of nonobstructionist agents, our approach is both complete and terminates.
We also propose (Section 4) a full NoN-compliant strategy for an agent which
ensures termination independently of the behaviour of the opponent. The
strategy, which takes into full account the presence of a utility function on the set of
acceptable deals, is inspired to the well-known mechanism of Monotonic
Concessions (MC) [
Section 5 specialises NoN to discrete and categorical variables and Section 6 presents experimental results showing that enforcing the NoN rule in practical negotiation instances is computationally feasible. 2
In the following, we denote with R the set of real numbers and with N+ the set of strictly positive integers.
Our framework deals with (possibly multi-deal) negotiations between two agents (agent 0 and agent 1) over multiple constrained variables. Agents do not have any information about constraints, goals, preferences, reasoning capabilities, willingness to collaborate, and strategy of the opponent. The only knowledge common to both agents is the set of negotiation variables and the protocol rules.
Definition 1 introduces the main concepts of our framework. Some of them are standard in the literature and are adapted to our framework to ease presentation of the following definitions and results.
Definition 1 (Negotiation process). A negotiation process is a tuple π = hV, s, k, Ri where V is a finite set of negotiation variables, s ∈ {0, 1} is the agent starting the negotiation, and R is the set of protocol rules.
The negotiation space is the multi-dimensional real vector space R|V|. Each point D ∈ R|V| is a deal. A proposal for π is a set of at most k deals or the distinguished element ⊥. Value k ∈ N+ is the maximum number of deals that can be included in a single proposal.
Negotiation proceeds in steps (starting from step 1) with agents (starting from agent s) alternately exchanging proposals. The proposal exchanged at any step t ≥ 1 is sent by agent ag(t), defined as s if t is odd and 1 − s if t is even.
The status of negotiation process π at step t ≥ 1 is the sequence P = P1, P2, . . . Pt of proposals exchanged up to step t.
At each step, the status of π must satisfy the set R of procotol rules, a set of boolean conditions on sequences of proposals.
A strategy for agent A ∈ {0, 1} for π is a function σA that, for each step t such that ag(t) = A and each status P = P1, P2, . . . Pt−1 of π at step t − 1, returns the proposal Pt to be sent by agent A at step t, given the sequence of proposals already exchanged (σA is constant for t = 1 and A = s).
Our alternating offers [
Protocol rules are important to prevent malicious or inefficient behaviour. Well-designed rules are of paramount importance when the process involves selfmotivated and/or unknown/untrusted opponents. For protocol rules to be effective, agents must be able at any time to verify them using the current negotiation status only.
We will use Example 1 as a running example throughout the paper. Example 1 (Alice vs. Bob). Alice wants to negotiate with her supervisor Bob to schedule a meeting. At the beginning, agents agree on the relevant variables V: (i) the start day/time t; (ii) the meeting duration d.
Deals are assignments of values to variables, as, e.g., D = ht = “Mon 11 am”, d = “30 min”i. Deals can be easily encoded as points in R2.
Definition 2 (Negotiation outcomes). Let π = hV, s, k, Ri be a negotiation process whose status at step T > 1 is P = P1, P2, . . . PT . We say that π terminates at step T if and only if T is the smallest value such that one of the following two cases holds: – success: PT = {D} ⊆ PT −1 (ag(T ) accepts deal D proposed by ag(T − 1) at step T − 1) – opt-out: PT =⊥ (ag(T ) opts-out).
Success, opt-out and non-term are the possible negotiation outcomes.
A negotiation process can be infinite (case non-term) or terminate in a finite number of steps, either with an agreement found (case success, where point D is the agreement ) or with a failure (case opt-out, where one of the agents proposes ⊥, which aborts the process).
For a deal to be acceptable to an agent, some constraints must be satisfied. Such constraints, which are private information of the single agent, are formalised by Definition 3. Definition 3 (Feasibility region). Let π = hV, s, k, Ri be a negotiation process. The feasibility region of agent A ∈ {0, 1}, denoted by RA, is the subset of the negotiation space R|V| of deals acceptable to A.
For agent A, any deal in RA is better than failure. An agreement is thus any deal D ∈ R0 ∩ R1.
Example 2 (Alice vs. Bob (cont.)). Alice wants the meeting no later than Wednesday. Normally she needs at least 30 minutes and does not want the meeting to last more than one hour; however, if she has to wait until Wednesday, she would have time during her Tuesday’s trip to prepare new material to show; in this case she wants the meeting to last at least one hour, but no more than 75 minutes. Conversely, Bob has his own, private, constraints.
Fig. 1a shows Alice’s feasibility region in a 2D space, as the areas delimited by the three polygons. The region takes into account duties in her agenda (e.g., Alice is busy on Monday from 1pm to 4pm).
Agents may have preferences on the deals in their feasibility region. Such preferences are often represented by a private utility function. Fig. 1a shows that, e.g., Alice prefers a long meeting on Monday. We will handle the agent utility function in Section 4 when we present a full strategy for an agent.
We assume (as typically done, see, e.g., [
We are interested in negotiations which are guaranteed to terminate in a finite number of steps (note that, being negotiation variables real-valued, the set of potential agreements is infinite), so we want to avoid case non-term of Definition 2. In this section we define a protocol rule, the Now or Never (NoN) rule, which is our key to drive a negotiation process towards termination, avoiding malicious or inefficient agents behaviour. The rule relies on the notions of Definition 4. Definition 4 (Convex region, convex hull, operator S♦). Let Rn be the n-dimensional real vector space (for any n > 0). Region R ⊆ Rn is convex if, for any two points D1 and D2 in R, the straight segment D1D2 is entirely in R.
Given a finite set of points D ⊂ Rn, the convex hull of D, conv(D), is the smallest convex region of Rn containing D.
Given a collection of finite sets of points D, S♦D is the union of the convex hulls of all sets in D: S♦D = SD∈D{conv(D)}.
Convexity arises often in feasibility regions of agents involved in negotiations.
An agent feasibility region is convex if, for any two acceptable deals D1 and D2,
all intermediate deals (i.e., those lying on D1D2) are acceptable as well. In some
cases [
Example 3 (Alice vs. Bob (cont.)). Knowing that deals ht = “Mon at 11am”, d = “30 min”i and ht = “Wed at 3pm”, d = “1 hour”i are both acceptable to Bob would not be a strong support for Alice to assume that also ht = “Tue at 1pm”, d = “45 min”i would be acceptable to him. On the other hand, if ht = “Mon at 9am”, d = “40 min”i and ht = “Mon at 9.30am”, d = “20 min”i are both acceptable to Bob, it would not be surprising if also ht = “Mon at 9.15am”, d = “30 min”i is acceptable.
Before formalising the NoN rule (Definition 6), we introduce it using our example.
Steps below are shown in Fig. 1.
Steps 1 and 2. Alice starts the negotiation by sending proposal P1 = {A1a, Ab1}. As a reply, she receives P2 = {B2a, B2b} (see Fig. 1b). As none of Bob’s counteroffers, B2a and B2b, belong to conv({A1a, Ab1}) = A1aAb1, all such deals are removed from further consideration (by exploiting NoN). The rationale is as follows: (a) Bob had no evidence that conv({A1a, Ab1}) includes deals outside RAlice (i.e., at the end of step 1 Bob had no evidence that this portion of RAlice is not convex).
(b) Given that Bob has not proposed any such deal therein, then either RBob ∩conv({A1a, Ab1}) = ∅ (in which case, Bob has no interest at all in proposing there), or Bob has chosen not to go for any such a deal now (as, e.g., he currently aims at higher utility).
(c) In the latter case, NoN forbids Bob to reconsider that decision anymore (never ).
Step 3. Alice, having no evidence that conv({B2a, B2b}) includes deals outside RBob, proposes P3 containing deal A3a ∈ conv({B2a, B2b}) ∩ RAlice (see Fig. 1c): by proposing A3a she aims at closing the negotiation successfully now, believing that such a deal (intermediate to B2a and B2b) is likely to be acceptable also to Bob. Alice also includes in P3 deal Ab3.
Step 4. It’s Bob’s turn again. By receiving P3 = {A3a, Ab3}, Bob knows that such deals belong to RAlice. Assume that Bob rejects P3 by sending a counteroffer. As there is no evidence that conv({A1a, A3a, Ab3}), conv({Ab1, Ab3}), or conv({Ab1, A3a}) (the 3 light-grey areas in Fig. 1c) include deals outside RAlice, NoN forces him to take a decision: either his counteroffer P4 contains some deals in one of such regions, or he must forget those regions forever. Note that NoN does not apply to, e.g., conv({Ab1, A3a, Ab3}), as this region contains B2b, which was part of a Bob’s proposal already rejected by Alice. Hence, there is already evidence that some of the deals in conv({Ab1, A3a, Ab3}) are acceptable to Bob and NoN does not forbid agents to further explore that region. Legend:
S♦NoN (1) = S♦Never (2) S♦NoN (2) where Pt is the proposal sent by ag(t) at step t and Never (0) = ∅.
At each step t, S♦NoN (t) represents the region, defined by ag(t)’s deals, for which the other agent 1 − ag(t) needs, in the next step (t + 1) to take a NoN decision: to offer a deal therein (showing to ag(t) that she is potentially interested to that region) or to neglect that region forever. Similarly, S♦Never (t) represents the region, defined by (1 − ag(t))’s deals, for which ag(t) has taken a never decision. Deals therein cannot be offered any more. Note that S♦Never (t) ⊇ S♦Never (t − 2) for all t ≥ 2 (i.e., sequences Never (t) for odd and even values of t are monotonically non-decreasing). Fig. 1 shows NoN and Never regions at all steps of the previous example.
Definition 6 formalises our NoN protocol rule, which forbids agents to reconsider never decisions already taken.
Definition 6 (Now or Never rule). Status P = P1, P2, . . . PT of negotiation process π = hV, s, k, Ri satisfies the NoN protocol rule if, for all steps 2 ≤ t ≤ T , Pt ∩ S♦Never (t − 2) = ∅.
Proposition 1 shows that the NoN rule of Definition 6 allows agents to infer when no further agreements are possible. All proofs are omitted for lack of space. Proposition 1 (Termination condition). Let π = hV, s, k, Ri be a negotiation process where the NoN rule is enforced and let P = P1, P2, . . . PT be the status of π at step T ≥ 2.
If Rag(T ) ⊆ S♦Never (T − 1) ∪ S♦Never (T − 2) and PT is not a singleton {D} ⊆ PT −1, then: (a) there exists no extension P 0 = P1, P2, . . . , PT −1, PT , . . . , PT 0 of P to step T 0 > T such that PT 0 ={D}⊆PT 0−1
(b) for all D ∈ R0 ∩ R1, there exists 1 < tD < T such that D ∈ S♦NoN (tD − 1) ∩ S♦Never (tD).
A consequence of (a) is that, if at step T ≥ 2, Rag(T ) ⊆ S♦Never (T − 1) ∪ S♦Never (T − 2) and agent ag(T ) cannot or does not want to accept a deal offered in the last incoming proposal PT −1, she can safely opt-out by proposing PT =⊥, as she has no hope to reach an agreement in the future. Also, from (b), for every mutually acceptable agreement D, there was a step tD < T in which agent ag(tD) took a never decision on a NoN region containing D. This means that ag(tD), although knowing that D ∈ Rag(tD) was likely to be acceptable also to the opponent (because she had no evidence, at that time, that the portions of the opponent region defined by deals in NoN (tD − 1) were not convex), explicitly decided not to take that chance and proposed elsewhere.
As a matter of fact, NoN can be thought as a deterrent, for each agent, to delay the negotiation by ignoring plausible agreements which, although acceptable to her, do not grant herself the utility she currently aims at. As NoN forbids the agents to propose such deals in the future, any such “obstructionist” behaviour has a price in terms of opportunities that must be sacrificed forever.
Definition 7 defines non-obstructionist agents. 1. if Pt−1 ∩ RA 6= ∅, then Pt = {D} ⊆ Pt−1 2. else if S♦NoN (t−1)∩RA 6=∅, then Pt ∩ S♦NoN (t−1)6=∅.
Definition 7 (Non-obstructionist agent). Let π = hV, s, k, Ri be a negotiation process where the NoN rule is enforced. Agent A ∈ {0, 1} is non-obstructionist if her strategy satisfies the following conditions for all t ≥ 2 such that ag(t) = A:
A non-obstructionist agent A accepts any acceptable deal D ∈ RA and takes a now decision at all steps t when S♦NoN (t−1) intersects RA. Non-obstructionist agents genuinely aim at finding an agreement efficiently, even sacrificing their preferences among deals they would accept. However, they are not necessarily collaborative, as they do not disclose to the opponent their constraints and preferences.
Proposition 2 shows that, in a negotiation process between two non-obstructionist agents, if one of the parties reaches the termination condition of Proposition 1, then no agreement exists (i.e., R0 ∩ R1 = ∅).
Proposition 2 (Completeness). Let π = hV, s, k, Ri be a negotiation process between two non-obstructionist agents where the NoN rule is enforced.
If π reaches, at step T − 1 ≥ 2, status P = P1, P2, . . . PT −1 s.t. Rag(T ) ⊆ S♦Never (T − 1) ∪ S♦Never (T − 2), then R0 ∩ R1 = ∅. 4
Propositions 1 and 2 show that the Now or Never (NoN) rule allows each agent to detect when the negotiation process can be safely terminated, as no agreement can be found in the sequel. However, still the termination condition may not arise in a finite number of steps. In this section we show that, with NoN, termination can be enforced by any agent alone, without relying on the willingness to terminate of the counterpart. To this end, from now on we focus on one agent only, which we call agent A (A can be either 0 or 1). To ease presentation, the other agent, agent 1 − A, will be called agent B.
We make some assumptions on the feasibility region of agent A: (a) RA is bounded and defined as the union P1 ∪ · · · ∪ Pq of a finite number q of convex sub-regions; (b) each convex sub-region Pi (1 ≤ i ≤ q) of RA is defined by linear constraints, hence is a (bounded) polyhedron in R|V|. Any bounded feasibility region can be approximated arbitrarily well with a (sufficiently large) union of bounded polyhedra. However, in many practical cases, a finite and small number of polyhedra suffices.
Deals in RA may not be equally worth for agent A, who may have a (again, private) utility function uA to maximize. We assume that uA is piecewise-linear and defined (without loss of generality) by a linear function uiA for each polyhedron Pi of RA (1 ≤ i ≤ q). For this definition to be well founded, if a deal D belongs to two different polyhedra Pi and Pj of RA, it must be uiA(D) = ujA(D). Note that, again, any differentiable utility function can be approximated arbitrarily well with a piecewise-linear utility, provided RA is decomposed in an enough number of polyhedra.
In this setting, we define a full strategy for agent A for negotiation processes π = hV, s, k, Ri for which k ≥ 2, i.e., in which exchanged proposals can contain multiple deals. Although our strategy is correct independently of the opponent region shape, it is designed for the common cases where agent A believes that the opponent feasibility region is the union of a small number of convex subregions (not necessarily polyhedra). Hence, a task of agent A while following the strategy is to discover non-convexities of the opponent region during negotiation and take them into account.
Our strategy is inspired by (but different from) the well-known mechanism
of Monotonic Concessions (MC) [
Agent A keeps and dynamically revises two utility thresholds, α and u, which are, respectively, the responding and the proposing threshold. At each step t such that ag(t) = A, agent A uses: (a) threshold α to decide whether to take a now decision (if t > 1), by including, in the proposal Pt she will propose next, a deal in S♦NoN (t − 1) (possibly accepting one deal in Pt−1), and (b) threshold u to select the other deals to include in Pt (t ≥ 1).
By generalising [
Our strategy for this phase is decomposed into responding, proposing and
conceding sub-strategies as in [
(1) If Pt−1 contains deals in RAα − S♦Never (t − 2), then Pt = {D}, where D is one such a deal giving agent A the highest utility (i.e., agent A accepts the best deal D among those acceptable in Pt−1 granting herself at least utility α). Otherwise:
(2) Pt contains a deal in ( S♦NoN (t − 1) ∩ RAα) − S♦Never (t − 2) if and only if this region is not empty (now decision taken).
Given that the closer deals in a set D defining NoN (t − 1) (see Definition 5) the more likely they belong to a single convex sub-region of RB, as for (2) agent A selects a deal with the highest utility in a set D having the minimum diameter. Proposing. At any step t ≥ 1 such that ag(t) = A, if agent A has not accepted an incoming deal (case (1) of the responding sub-strategy), proposal Pt contains additional deals (as to make |Pt| = k ≥ 2). Let RAu = {D ∈ RA | uA(D) ≥ u} (which is again a union of bounded polyhedra, as uA is piecewise-linear). Deals to be proposed in Pt are carefully selected among vertices of RAu (some of them can be vertices of the overall region RA) which do not belong to S♦Never (t − 2), as agent A needs to comply with the NoN rule. If t > 1, vertices of RAu to be proposed will be carefully selected by reasoning on the evidence provided by the past opponent behaviour. The reasoning is as follows.
Let nˆ(t) be the minimum number of convex sub-regions that must compose RB − S♦Never (t − 1), i.e., the opponent region minus the regions for which the opponent has taken a never decision (and in which, by the NoN rule, no agreements can be found in the sequel): nˆ(t) is the minimum value such that there exists a nˆ(t)-partition {D1, . . . , Dnˆ(t)} of dealsB(t − 1) (i.e., a mapping of each opponent deal to one sub-region) such that for all 1 ≤ j ≤ nˆ(t), conv(Dj ) ∩ S♦Never (t − 1) = ∅.
Agent A temporarily focuses on nˆ(t), assuming that RB − S♦Never (t − 1) is the union of exactly nˆ(t) convex sub-regions. We call this assumption Nonobstructionist Opponent Assumption (NOA). Under NOA, agent A tries to regard the past opponent behaviour as non-obstructionist, hence interprets the already taken never decisions as an admission that RB ∩ S♦Never (t − 1) = ∅ (Proposition 2). Value nˆ(t) is the minimum number of convex sub-regions that must compose RB which is consistent with this (optimistic) hypothesis.
Agent A computes the subsets D of the opponent deals that might belong to the same convex sub-region of RB − S♦Never (t − 1), provided that NOA is correct. We call these sets of deals Possible Opponent Clusters (POCs): K(t)=
D⊆dealsB(t−1) ∃ nˆ(t)-partition D1, . . . , Dnˆ(t) of dealsB(t−1)
s.t. ∀j ∈[1, nˆ(t)] conv(Dj )∩ S♦Never (t−1)=∅
(1)
Let proj(R, R0) (the projection of region R onto R0) be the set of points X for
which there exists Y ∈ R such that XY intersects R0 [
D∈K(t)
proj(conv(D), S♦Never (t − 1)) does not contain agreements that can be still reached.
Proposition 3. If, at step t ≥ 3 s.t. ag(t) = A, NOA is correct, then Π(t) ∩ (RB − S♦Never (t − 1)) = ∅.
Example 5 (Alice vs. Bob (cont.)). Consider Fig. 2b. At step 4 Bob sent Alice proposal P4 = {B4a}. At step 5 (Alice’s turn), nˆ(5) is 3, as it is clear that B2a, B2b, and B4a belong to all-different convex sub-regions of RBob − S♦Never (4). POCs are K(5) = {{B2a}, {B2b}, {B4a}}. Region Π(5) is the area in light-grey: if NOA is correct (RBob − S♦Never (4) or, equivalently, RBob if Bob is non-obstructionist, consists of exactly 3 convex sub-regions), then no X ∈ Π(5) can belong to RBob − S♦Never (4).
Besides always ignoring vertices in S♦Never (t−2) (as to comply with the NoN rule), as a result of Proposition 3 agent A (exploiting NOA) can temporarily ignore vertices of RAu in Π(t) while choosing deals to propose at step t. By exploiting the fail-first principle, we define the following criterion (best vertex under NOA) to select the next vertices in RAu − Π(t) (and not in S♦Never (t − 2)) to propose: those that, if rejected, would make the highest number of vertices be excluded in the next step, under NOA.
Conceding. When no more vertices in RAu − Π(t) (and not in S♦Never (t − 2))
can be proposed, agent A reduces threshold u, if possible, by a given amount
Δu, whose value, possibly varying during time (see, e.g, [
Let Tˆ (ag(Tˆ) = A) be the step in which agent A reduces u and RAu becomes equal to RA (i.e., u cannot be further reduced). From step Tˆ onwards, the strategy of agent A moves to the non-obstructionist phase. 4.2
Our strategy for this phase is decomposed into responding and proposing substrategies. As utility threshold u has already reached its minimum, in this phase there is no conceding sub-strategy.
Responding. The responding sub-strategy is identical to that of the utilitydriven phase with α = u. Given that in the non-obstructionist phase u is at its minimum, agent A accepts any incoming acceptable deal and takes a now decision whenever possible. Thus, the agent is now certainly non-obstructionist, independently of the value of her respond policy ξ.
Proposing. As a result of acting in a non-obstructionist way, from step Tˆ onwards the following result holds: Proposition 4. For each step t ≥ Tˆ such that ag(t) = A, RA ∩ S♦Never (t−2) = RA ∩ S♦Never (Tˆ − 2).
Hence, for each step t ≥ Tˆ such that ag(t) = A, if agent A has not accepted an incoming deal, the region in which the additional deals to propose will be selected (as to make |Pt| = k ≥ 2 whenever possible), i.e., RA − S♦Never (t − 2), is steadily equal to RA − S♦Never (Tˆ − 2).
In this phase, agent A aims at proposing vertices of RA − S♦Never (Tˆ − 2) with the goal of eventually covering it within the never set of the opponent, as to reach the termination condition of Proposition 1. Unfortunately, as both RA and S♦Never (Tˆ − 2) are unions of polyhedra, their difference might not be represented as a union of polyhedra. Anyway, it can be always represented as a union of Not Necessarily Closed polyhedra (i.e., polyhedra possibly defined by some strict inequalities, with some of their faces and vertices not belonging to them). In order to comply with the NoN rule, the agent must not propose vertices of RA − S♦Never (Tˆ − 2) not belonging to that region, as they would belong to S♦Never (Tˆ − 2). The problem is solved by computing a suitable underapproximation bRA − S♦Never (Tˆ − 2)c ⊆ RA − S♦Never (Tˆ − 2) which can be defined as a union of bounded (and closed) polyhedra. Note that such an underapproximation can be computed in order to make the error
RAerr = (RA − S♦Never (Tˆ − 2)) − bRA − S♦Never (Tˆ − 2)c arbitrarily small. As a special case, if agent A was non-obstructionist from the beginning of the negotiation process, RA ∩ S♦Never (Tˆ − 2) = ∅ and RAerr = ∅.
Agent A continues to use both NOA and Π(t) as defined in the utilitydriven phase. In particular, the agent proposes vertices of bRA − S♦Never (Tˆ −2)c which are not in Π(t). When no more such vertices can be proposed, NOA is gradually relaxed (i.e., nˆ(t) is gradually increased) and the remaining vertices of bRA − S♦Never (Tˆ − 2)c are enabled. By construction, nˆ(t) cannot grow beyond the number of deals proposed by the opponent so far. If also in that case Π(t) covers bRA − S♦Never (Tˆ − 2)c, the agent sets Π(t) to S♦Never (t − 1), hence assumes that RB consists of at least one convex sub-region not yet disclosed by the opponent (i.e., not containing any of the past incoming deals).
As it happens in the utility-driven phase, given that multi-deal proposals are allowed (k ≥ 2), all vertices will be proposed within a finite number of steps independently of the number of now decisions taken. When all vertices have been proposed and no agreement has been reached, agent A enters the terminating phase. 4.3
In this phase, agent A continues by sending empty proposals until she receives and accepts an acceptable deal or infers RA −RAerr ⊆ S♦Never (T −1)∪ S♦Never (T −2). Proposition 5 states that also this condition will arise in a finite number of steps. Proposition 5. Let π = hV, s, k, Ri be a negotiation process (k ≥ 2) where the NoN rule is enforced. If any agent A ∈ {0, 1} uses the strategy above, then, within ˆ a finite number of steps T ≥ T ≥ 2 such that ag(T ) = A, either an agreement is found or condition RA − RAerr ⊆ S♦Never (T − 1) ∪ S♦Never (T − 2) is satisfied. X
R' R
Y (a) proj(R, R0) (grey area)
Condition of Proposition 5 can be considered the termination condition of Proposition 1 in case agent A had admissible region RA − RAerr. Given that region RAerr can be chosen as to be arbitrarily small, agent A can terminate the negotiation when this condition is reached. Any possible remaining acceptable deals would be in the (arbitrarily small) region RAerr.
We stress again that, in case agent A is non-obstructionist from the beginning, for all t ≥ Tˆ such that ag(t) = A, RAerr can be made empty. Hence, as it happens for any acceptable deal in RA ∩ S♦Never (t − 2) = RA ∩ S♦Never (Tˆ − 2), any acceptable deal in RAerr can be considered as an opportunity (with arbitrarily small Euclidean distance to RA ∩ S♦Never (Tˆ − 2)) that agent A had to sacrifice for having behaved in an obstructionist way (at most) up to step Tˆ − 2. 5
The NoN rule works also when (some of) the variables are discrete (e.g., integer),
if we consider the union of the integer hulls [
Our framework has at its core well-studied tasks in computational geometry and
(integer) linear programming [
In the following we present an empirical evaluation of the computational feasibility of the approach. Negotiations have been performed between two identical agents. We evaluated our implementation on both random and structured instances using a single computer (a PC with a dual-core AMD Opteron 3GHz and 8GB RAM) for both agents. At each step, agents can exchange contracts of at most k = 2 deals. Note that, as our approach requires agents to comply with the NoN rule, it cannot be evaluated against other negotiators.
Random Instances. We generated 100 random negotiation instances over 3 variables. Feasibility regions are unions of 3 random polyhedra, each with at most 10 vertices. In about 44% of the instances R0 ∩ R1 6= ∅. The average volume of the intersection is 2.19% of the volume of each agent’s region (stddev is 4.5%). Agents have random piecewise-linear utilities and concede constant Δu = 0.2span each time all vertices of Rau (a ∈ {0, 1}) belong to Π.
Such negotiations terminate in < 5 minutes and 20–30 steps. Agreements were found in > 95% of the instances for which R0 ∩R1 6= ∅. Fig. 3 shows average time, success rate (i.e., number of negotiations closed successfully / number of negotiations such that R0 ∩ R1 6= ∅), and average quality of the agreement found for each agent (the quality of an agreement D for agent a ∈ {0, 1} is (ua(D) − La)/(Ha − La), where Ha and La are, respectively, the highest and lowest values of agent a utility in R0∩R1) as a function of the respond policies used (ξ0 and ξ1).
It can be seen that moderate respond policies (intermediate values of ξ) lead
to very high probabilities (> 97%) of finding an agreement if one exists;
moreover, the quality of such agreements for the two agents is similar if their respond
policies are similar (fairness). Conversely, if agents use very different values for ξ,
the more conceding agent unsurprisingly gets lower utility with the agreement,
but negotiations are more often aborted by the other, more demanding, agent.
Structured Instances. We evaluated our system on the 6 scenarios in Table 1a:
two scenarios (AB1, AB2) of the Alice vs. Bob example, two scenarios (SU1,
SU2) of a negotiation problem regarding the rental of a summerhouse, and two
scenarios (EZ1, EZ2) of a variation of the England-Zimbabwe problem of [
Table 1a shows also some relevant properties of these negotiation scenarios. Column “vars” gives the number of negotiation variables. Columns “polys” and “con” give, respectively, the number of polyhedra and the overall number of Avg. Negotiation time
Success ratio
Avg. agr. quality for agent 0 Avg. agr. quality for agent 1 300 280 260 240 220 200 180 160 AB1 AB2 SU1 SU2 EZ1 EZ2 linear constraints defining each agent feasibility region, R0 and R1. The two last columns give the ratio of the volume of R0 ∩ R1 (i.e., the volume of the space of the possible agreements) with respect to the volume of the feasibility region of each agent (“–” means that R0 ∩ R1 is empty, hence no agreement is possible).
Table 1b shows some results on the above negotiation scenarios, under different values of the respond policies of each agent (ξ0 and ξ1). All instances have been run with k (the maximum number of deals in a proposal) equal to 2. For each instance, column “agr. found” tells whether an agreement has been found (an agreement exists if and only if R0 ∩ R1 6= ∅, see Table 1a), column “steps” gives the number of negotiation steps needed to conclude the negotiation process, column “time” gives the overall negotiation time, and column “polys” gives the overall number of polyhedra computed by PPL during the process. For each negotiation instance, the number of all-SAT instances solved to compute POCs (see formula (1)) is equal to the number of negotiation steps.
Our results show that enforcing NoN is computationally feasible: negotiation processes with hundreds of interaction steps could be performed in minutes, even when NoN enforcement and agents reasoning require the computation of millions of polyhedra and the resolution of hundreds of all-SAT instances. 7
In this paper we defined a new protocol rule, Now or Never (NoN), for bilateral negotiation processes which allows self-motivated competitive agents to efficiently carry out multi-variable negotiations with remote untrusted parties, where privacy is a major concern and agents know nothing about their opponent. NoN has been explicitly designed as to ensure a continuous progress of the negotiation, thus neutralising malicious or inefficient opponents.
We have also presented a NoN-compliant strategy for an agent that, under mild assumptions on her feasibility region, allows her to derive, in a finite number of steps and independently of the behaviour of her opponent, that there is no hope to find an agreement. We finally evaluated the computational feasibility of the overall approach on random and structured instances of practical size. Acknowledgements. This research was founded by the EU 7th Framework Programme under grant agreements n. 317761 (SmartHG) and n. 600773 (PAEON).