Negotiation Strategies for Agents with Ordinal Preferences

1 Introduction

Negotiation is a dialogue between two or more parties over one or more issues, where each party has some preferences regarding the discussed issues, and the negotiation process aims to reach an agreement that would be beneficial to the parties. The basic automated negotiation protocol, which consists of two parties that alternate offers, was introduced by [Rubinstein, 1982]. Since then a lot of work has been done to develop other types of protocols, and to extend the basic bilateral negotiation protocol [Fatima et al., 2014].

Many common negotiation protocols work with cardinal utilities, i.e., with utility functions that give different outcomes a specific numerical value, according to the agents' preferences. This representation requires the agents to specify the magnitude of how much they prefer one outcome over another. However, this specification is not always readily available. Moreover, in many cases the agents need to act on behalf of humans, and the use of cardinal utilities for representing human preferences has been widely criticized on the grounds of cognitive complexity, difficulty of elicitation, and other factors (e.g., [Ali and Ronaldson, 2012]). On the other hand, ordinal preferences only rank the outcomes, so they reduce cognitive burden and are easier to elicit.

Indeed, there are some negotiation protocols that work with ordinal preferences. However, these protocols only start with the ordinal preferences, and they then convert them to a cardinal utility according to some assumptions [Nash Jr, 1950; Shapley, 1969]. Moreover, the traditional assumption in the negotiation theory is that there is a continuum of feasible outcomes. However, many real-life situations involve a finite number of outcomes, such as two managers choosing from among a few job candidates, or a couple choosing from among a few apartments. Even in negotiation over monetary payoffs, the number of outcomes is bounded by the indivisibility of the smallest monetary unit.

In this paper we study negotiation with ordinal preferences over a finite set of outcomes, without converting the ordinal preferences to a cardinal utility 1 . We analyze an intuitive protocol for bilateral negotiation that was introduced by [Anbarci, 1993], where the two parties make alternating offers. Each offer is a possible outcome, and we allow the parties to make any offer they would like, in any order. The only restriction is that no offer can be made twice, thus if there are m possible outcomes the negotiation will last at most m rounds.

We analyze the negotiation protocol in different settings. First, we assume that each party has full information about the other party's preference order, and she will thus take this into account and act strategically when deciding what to offer. We provide elegant strategies that specify a Sub-game Perfect Equilibrium (SPE) for the parties. Specifically, our strategies are easy to implement, and we improve the previous result of [Anbarci, 2006] and find a SPE strategy in linear time instead of quadratic time.

We note that there are several works that studied bargaining rules with ordinal preferences over a finite set of outcomes, but they are inherently different from non-cooperative negotiation protocols. A bargaining rule is a function that assigns to each negotiation instance a subset of the outcomes, which are considered the result of the negotiation. These rules are useful only in a cooperative environment, or where there is a central authority that can force the parties to offer specific outcomes in a specific order.

1 This is also the assumption in most of the voting literature [Brandt et al., 2016], but see [Boutilier et al., 2015] that analyzes social choice functions after extracting cardinal utilities from ordinal preferences.

The proof that our proposed strategies specify a SPE provides us with a deep understanding of the negotiation protocol, which enables us to establish a connection to the results of the designed Rational Compromise (RC) bargaining rule [Kıbrıs and Sertel, 2007]. Surprisingly, the SPE result of the negotiation protocol is always part of the set of results returned by the RC rule, even though the protocol does not force the parties to offer specific outcomes in a specific order as the RC rule does. This connection also enables us to prove that the SPE result of the protocol is monotonic.

We then move on to analyze the no information setting. We analyze the case where neither party knows the preference order of the other party nor do they know prior probability distribution over possible orders. In this setting we first show that an ex-post SPE does not exist. We then provide the maxmin strategy and the maxmin value of the game that is imposed by our protocol. We also show that in our setting, surprisingly, any pair of maxmin strategies also specifies a robust-optimization equilibrium. Finally, we consider the case where one party has full information while the other party has no information, and show how the informed party is able to use her information so that the negotiation result will be better for her.

The contribution of this work is threefold. First, we introduce elegant strategies that specify a SPE, and provide a substantial analysis for showing that they indeed form a SPE. We also provide an improved algorithm for computing a SPE strategy for the studied negotiation protocol. The second contribution of our work is that we show how the studied negotiation protocol almost completely implements the RC rule. As noted by [Kıbrıs and Sertel, 2007], who studied the RC rule, the descriptive relevance of the RC rule for real-life bargaining depends on the existence of non-cooperative games that implement it, and to the best of our knowledge our paper is the first to find such a connection. Finally, we provide an analysis of the negotiation protocol under a no information setting, which has not been considered before.

2 RelatedWork

Negotiation protocols and the strategic interaction they imply have been extensively studied. We refer to the books of [Osborne and Rubinstein, 1990], [Kraus, 2001], and [Fatima et al., 2014] for extensive coverage of the different approaches. The traditional assumption in negotiation theory is that there is a continuum of feasible outcomes, but many real-life negotiation scenarios violate these assumptions. Indeed, there are several works that consider problems with a finite number of outcomes. For example, see [Zlotkin and Rosenschein, 1996], [Mariotti, 1998], [Nagahisa and Tanaka, 2002] and recently [Nunez and Laslier, 2015]. All of these works focus on negotiation when the preferences are represented by a cardinal utility, while we study negotiation with ordinal preferences.

Many other works study negotiation with ordinal preferences over a finite set of outcomes (for example, [Zhang and Zhang, 2008]). Sequential procedures, in particular the fallback bargaining method, have attracted considerable interest [Sprumont, 1993; Hurwicz and Sertel, 1999; Brams and Kilgour, 2001; Kıbrıs and Sertel, 2007; Conley and Wilkie, 2012], since they satisfy some nice theoretical properties. All of these works study bargaining rules that are useful in a cooperative environment. We study a negotiation protocol that is useful in a non-cooperative environment, and show that its SPE almost completely implements the individually rational variant of the fallback bargaining method, i.e., the RC rule [Kıbrıs and Sertel, 2007]. We note that the RC bargaining rule is equivalent to Bucklin voting with two voters, and thus our result can also be interpreted as a (weak) SPE implementation of the Bucklin rule where there are two voters.

There are few works that study negotiation protocols with ordinal preferences over a finite set of outcomes. [De Clippel et al., 2014] study the problem of selection of arbitrators, and they concentrate on two-step protocols. The most closely related works are Anbarci's papers. In [Anbarci, 1993] he introduces the Voting by Alternating Offers and Vetoes (VAOV) negotiation protocol, which we study here, and shows the possible SPE results in different scenarios. Implicitly, this work shows that the SPE result is unique and Pareto optimal. In [Anbarci, 2006] he introduces three additional negotiation protocols. Moreover, he sharpens his previous result by exactly identifying the SPE result of the VAOV protocol, and by providing an algorithm that computes a SPE strategy. He also shows that if the outcomes are distributed uniformly over the comprehensive utility possibility set and as the number of outcomes tends to infinity the VAOV protocol converges to the equal area rule [Thomson, 1994]. We provide a more efficient algorithm that finds an elegant SPE strategy. In addition, we were able to establish the relationship between the VAOV protocol and the RC rule, which works with a finite number of outcomes, and we also analyze the no information setting.

3 The Negotiation Protocol

We assume that there are two negotiation parties, p1 and p2 , negotiating over a set of potential outcomes O = {o1, ..., om}, where p1 is the party that makes the first offer. Each party has a preference order over the potential outcomes that does not permit any ties. Formally, the preferences of a party p are a strict order, ≻p, which is a complete, transitive and irreflexive binary relation on O. We write o′ ≻p o to denote that party p strictly prefers o′ to o, and o′ ⪰p o to denote that o′ ≻p o or o′ = o (i.e o′ is the exact same outcome as o). Clearly, each party would like to maximize her utility, i.e., that the result of the negotiation will be the outcome that is placed as high as possible according to her preferences.

We analyze the following negotiation protocol, which is the VAOV protocol of [Anbarci, 1993]. The parties make offers alternately. No offer can be made twice, but an agreement must be reached since we assume that any agreement is preferred by both parties over a no-agreement result. We also assume that lotteries are not valid offers, as in most real-life negotiations. Formally, denote by Ot the set of available outcomes at round t, and the let O1 = O. At round 1, party p1

offers an outcome o ∈ O1 to p2 . If p2 accepts, the negotiation terminates successfully with o as the result of the negotiation. Otherwise, party p2 offers an outcome o′ ∈ O2 = O1 \ {o}. If p1 accepts, the negotiation terminates successfully with o′ as the result of the negotiation. Otherwise, p1 offers an outcome o′′ ∈ O3 = O2 \ {o′ } to p2 , and so on. If no offer was accepted until round m then the last available outcome is accepted in the last round as the result of the negotiation. We denote by pi the party whose turn it is to make an offer at a given round, and by pj the other party. That is, pi = p1 in odd round numbers and pi = p2 otherwise.

We first provide a general result that is useful with any model of information. Consider the following definition:

Definition 1. In each round t, let Ljt be the ⌊|Ot|/2⌋ lowest ranked outcomes in ≻pj . If |Ot| is odd, then let Lit be the ⌊|Ot|/2⌋ lowest ranked outcomes in ≻pi . If |Ot| is even, then Lit is the |Ot|/2 - 1 lowest ranked outcomes in ≻pi .

We show that in each round t we can identify a set of outcomes that cannot be the negotiation result if the parties are rational, regardless of the information they have. Intuitively, these are all the outcomes that are in the lower parts of the preference orders of both parties, denoted by Lowt. We denote all of the other outcomes by JGt.

Definition 2. Given a round t, let Lowt = {o : o ∈ Lit ∪Ljt }, and JGt = Ot \ Lowt.

Lemma 1. Let o be the result of the negotiation if both parties are rational. Then, o /∈ Lowt.

Proof. Starting from round t where |Ot| = mt, each party will be able to reject all of the offers that she would receive from the other party, except for the offer she would receive in the last round. Specifically, if mt is odd, pi and pj can reject at most ⌊mt/2⌋ offers. If mt is even, pi can reject at most ⌊mt/2⌋ - 1 offers (since it is pi 's turn to offer) and pj can reject at most ⌊mt/2⌋ offers. That is, each party pk , k ∈ {1, 2}, can reject at most |Lkt | offers. Therefore, each party will always be able to guarantee that the result of the negotiation will be an outcome that is placed higher than the |Lkt | lowest outcomes in her preference order. Therefore, o /∈ Lowt .

We now analyze the negotiation protocol under two different models of information: full information and no information. In each case we are interested in finding the best actions that a party should take, given the information that she has.

4 Full Information

In this setting we assume that each party has full information about the other party's preference order, and she will thus take this information into account when calculating her best strategy. Therefore, in the full information setting we are interested in finding a SPE. Since [Anbarci, 1993] showed that the SPE result is unique, it suffices to find one set of strategies that specify a SPE.

Recall that SPE is a mapping that maps the histories of players' choices. Note that in our case if an offer was accepted the game is over. Therefore, a history for pi , the party whose turn it is to make an offer at a given round, consists of a sequence of outcomes that were proposed and rejected in the previous rounds. Let Hi t = (o1 , o2 , ..., ot-1 ) be the history for pi at round t, and note that Ot = O \ Hi t . Let o-t be the least preferred outcome in Ot according to ≻pj . We show that the following strategy specifies the offering strategy in our SPE.

Strategy 1 (OFFERING STRATEGY). Given a history Hi t , if It = Lit ∩ Ljt ̸= ∅ then offer o ∈ It, else offer o-t .

A history for pj , the party whose turn it is to decide whether to accept or reject an offer at a given round, consists of a sequence of outcomes that were proposed and rejected in the previous rounds and an additional outcome o that was offered by pi in the current round. Let Hj t = Hi t + o = (o1 , o2 , ..., ot-1 , o) be the history for pj at round t. In addition, given a round t and history for pi , Hi t , let oit be an outcome o ∈ It = Lit ∩Ljt if It ̸= ∅, and o-t otherwise. Given a round t and history for pj , Hj t , let oa(Hj t ) be the single outcome in Om = O\Him, where Him = Hj t +oit+1 +...+oim-1 . That is, oa(Hj t ) is the result of the negotiation if both parties reject all of the offers that they get (except for the last offer) from round t and on, but use the offering strategy that is specified by Strategy 1 from round t+1 and on. We show that the following strategy specifies the response strategy in our SPE.

Strategy 2 (RESPONSE STRATEGY). Given a history Hj t , if o ⪰pj oa(Hj t ) then accept o, else reject o.

To illustrate the strategies of our SPE, consider the following examples:

Example 1. Suppose that

Following Definition 1, L11 = {o2, o1} and L21 = {o6, o4, o5}. Therefore, I1 = ∅ and according to the offering strategy (Strategy 1) p1 would offer p2 's least preferred outcome - o5. Then, according to the response strategy (Strategy 2) p2 would reject, since oa((o5)) = o3 ≻p2 o5, as we will show. In round 2, L12 = {o1, o2} and L22 = {o6, o4}, and thus p2 would offer o1. Now p1 would reject, and offer o4, p2 would reject and offer o2, p1 would reject and offer o6, and in the final round p2 would reject and offer o3 which is accepted as the result of the negotiation since no other outcome is available.

Example 2. Now suppose that

Following Definition 1, L11 = {o2, o1} and L21 = {o2, o4, o5}. Therefore, I1 = {o2} and according to Strategy 1 p1 would offer o2. Then, p2 will reject, since oa((o2)) = o6 ≻p2 o2, as we will show. In round 2, L12 = {o3, o1} and L22 = {o4, o5}, I2 = ∅, and thus p2 would offer o1. In each subsequent round the parties would offer each other the least preferred outcomes, until the final round where o6 will be accepted as the result of the negotiation.

In order to prove that our strategies specify a SPE, we need a deeper understating of the offering and response strategies. We note that in the offering strategy (Strategy 1), pi offers an outcome from the set It if it is not empty. We now show the relation between the set It and the set JGt. Due to space constraints, we defer the proofs of some of the lemmas to the full version of the paper [Erlich et al., 2018].

Considering Lemma 1, we show a simple corollary. Let oeq be the SPE result. We get:

Corollary 1. oeq /∈ Lowt.

If we combine the findings from Corollary 1 and Lemma 2, we get that if the set It is empty, i.e., the intersection between the lower parts of the preference orders of the parties is empty, then the set JGt contains only one outcome, oeq.

Next, we show how the transition from round t to round t + 1 affects the number of outcomes in Lkt+1 , k ∈ {1, 2}.

Lemma 3. Suppose that in round t, pi offered an outcome o and pj rejected it, then in round t +1, |Lit+1 | = |Ljt | -1 and |Ljt+1 | = |Lit |

Proof. Assume |Ot| = mt is even, then by definition |Lit | = mt 2 - 1 and |Ljt | = mt 2 . After that pi offered the outcome o and pj rejected it, mt+1 is odd, and the roles are switched between pi and pj . Therefore, |Lit+1 | = |Ljt+1 | = ⌊ mt+1 2 ⌋ = ⌊ mt-1 2 ⌋ = ⌊ mt 2 - 12 ⌋ = mt 2 -1. Now assume that mt is odd, then |Lit | = |Ljt | = ⌊ mt 2 ⌋ = mt-1 2 . After that pi offered the outcome o and pj rejected it, mt+1 is even, and the roles are switched between pi and pj . Therefore, |Ljt+1 | = mt-1 2 and |Lit+1 | = mt-1 2 -1 .

We note that the number of outcomes in Lkt is important, since we already showed in Corollary 1 that these are the outcomes that cannot be an equilibrium result. Indeed, it is more important to understand how the transition from round t to round t + 1 affects which outcomes become part of Lkt+1 . Obviously, it depends on the offer that was made in round t. The following three lemmas analyze this transition, based on the offers that are made according to Strategy 1. Specifically, Lemma 4 together with Lemma 5 cover the offering strategy where It = ∅, and Lemma 5 together with Lemma 6 cover the offering strategy where It ̸= ∅.

Lemma 4. In round t, if pi offers o /∈ Lit and pj rejects it, then Ljt+1 ← Lit

Lemma 5. In round t, if pi offers o ∈ Ljt and pj rejects it, then Lit+1 ← Ljt \ {o}

Lemma 6. In round t, if pi offers o ∈ Lit and pj rejects it, then Ljt+1 ← Lit \ {o} ∪ {o′ }

Note that when pj follows Strategy 2 she computes the outcome oa(Hj t ) to decide whether to accept or reject the offer that she gets from pi . By definition,

We now show that if, in a given round t, pi follows Strategy 1, i.e., oa(Hj t ) = oa(Hi t + oit ), then oa(Hj t ) has some desirable properties. For example, it is Pareto optimal in Ot, i.e., ∀o ∈ Ot \ {oa(Hi t + oit )}, oa(Hi t + oit ) ≻pi o or oa(Hi t + oit ) ≻pj o. For ease of notation, let oat = oa(Hi t + oit ).

Lemma 8. Given any history Hi t , oit ≺pj oat, oat ∈ JGt, and oat is Pareto optimal in Ot.

Proof. We prove by induction on m. If m = 2 and t = 1, without loss of generality (WLOG) assume that ≻p2= o1 ≻ o2. Since It = ∅, o1t = o-t = o2 and H1 t = () by definition. Thus, oat = oa(H1 t + o1t ) = o1. In addition, JGt = {o1}, and therefore o1t ≺p2 oat and oat ∈ JG1 as required. Since Ot \ {oat} = {o2} and o2 ≺p2 oat then oat is also Pareto optimal in Ot. Now, assume that if there are m-1 outcomes in round t+1, oit+1 ≺pj oa(Hi t+1 +oit+1 ), oa(Hi t+1 +oit+1 ) ∈ JGt+1 and oa(Hi t+1 + oit+1 ) is Pareto optimal in Ot+1. We show that when there are m outcomes in round t, oit ≺pj oa(Hi t + oit ) = oat, oat ∈ JGt and oat is Pareto optimal in Ot. According to Lemma 7, if Hj t = Hi t + oit we get that oat = oa(Hi t +oit ) = oa(Hi t +oit +oit+1 ) = oa(Hi t+1 +oit+1 ). Now, if It = ∅ and thus oit = o-t ∈ Ljt then according to Lemmas 4 and 5 JGt+1 = JGt. If It ̸= ∅ and thus oit ∈ It then according to Lemmas 5 and 6 JGt+1 ⊆ JGt. According to the induction assumption, oa(Hi t+1 + oit+1 ) ∈ JGt+1 and thus oat = oa(Hi t+1 + oit+1 ) ∈ JGt. In addition, oit ∈ Ljt by definition and since we showed that oat ∈ JGt, we get that oit ≺pj oat. Finally, since oat is Pareto optimal in Ot+1, Ot = Ot+1 ∪ {oit }, and oit ≺pj oat, we conclude that oat is Pareto optimal in Ot.

Rephrasing Lemma 8, we showed that given any history Hi t , if both parties follow Strategies 1 and 2 from round t and on, pj would always reject the offers that she gets from pi (i.e., oit , oit+1 , ..., oim-1 ), and the negotiation result would be oat, which would be accepted in the last round. Moreover, the negotiation result oat is Pareto optimal in Ot,Ot+1, ...,Om.

Before we prove that Strategies 1 and 2 specify a SPE we need to add some definitions. We first define a distance function for each party pk , that given an outcome ox /∈ Lkt counts the number of outcomes o /∈ Lkt such that ox ⪰pk o. Intuitively, this is the number of outcomes a party can offer until a round t′ where ox becomes part of Lkt′ . Formally:

We also define the number of offers that are made before reaching a round t′ where It′ = ∅.

Definition 4. Let ℓk,t be the number of offers a party pk offers according to Strategy 1 from round t until round t′ where It′ = ∅.

Recall our previous examples. In Example 1 at round 1, I1 = ∅ and thus ℓ1,1 = ℓ2,1 = 0. The distance of o3 at round 1 is d1,3,1 = 1 for party p1 and d2,3,1 = 2 for party p2 . In Example 2, I1 ̸= ∅ but I2 = ∅ and thus ℓ1,1 = 1 and ℓ2,1 = 0. The distance of o6 at round 1 for the parties is d1,6,1 = 4 and d2,6,1 = 1, and the distance of o3 at round 1 for the parties is d1,3,1 = 1 and d2,3,1 = 2.

We also make the following simple observation, which is true since we use an alternating offers protocol:

Our main theorem is as follows:

Theorem 10. Strategies 1 and 2 specify a SPE.

Proof. We prove by induction on m. If m = 2 and t = 1, WLOG assume that ≻p2= o1 ≻ o2. Thus, JGt = {o1}, and according to Corollary 2, o1 is the SPE result. Indeed, according to Strategy 1 p1 will offer o2 in the first round and p2 will reject it according to Strategy 2 since oa((o2)) = o1 ≻2 o2. In the next round pi = p2 will offer o1, p1 will accept it and then the negotiation will end with o1 as the negotiation result. Clearly there are only two states where p2 has the option to deviate: on the equilibrium path, i.e., where H2 t = (o2), and off the equilibrium path, i.e., where H2 t = (o1). Where H2 t = (o2), p2 has no incentive to deviate from the response strategy and accept the offer of o2 from p1 , since o1 ≻2 o2. Where H2 t = (o1), p2 has no incentive to deviate and reject the offer of o1, since then o2 would become the last available outcome and thus the negotiation result, but o1 ≻2 o2. Similarly, there is only one state where p1 has the option to deviate, i.e., H1 t = (). In this state p1 has no incentive to deviate from the offering strategy and offer o1, since p2 will accept it (because o1 ≻2 o2) and o1 is already the SPE result if p1 follows the offering strategy.

Now, assume that if there are m - 1 outcomes in round t + 1, our strategies specify a SPE. We show that they specify a SPE when there are m outcomes in round t. We first consider the strategy of pj at round t. Note that oa(Hj t ) = oa(Hi t + o) = oa(Hi t+1 ) by definition, and oa(Hi t+1 ) is the SPE result of following our strategies from state Hi t+1 according to Lemma 8 combined with the induction assumption. Clearly, if according to the response strategy (Strategy 2) pj should reject the offer o, it is because oa(Hj t ) ≻pj o. Therefore, it is not worthwhile for pj to deviate and accept o instead of oa(Hi t+1 ) = oa(Hj t ). Similarly, if according to the response strategy pj should accept an offer o, it is because o ⪰pj oa(Hj t ). Therefore, it is not worthwhile for pj to deviate and reject o in order to get as the negotiation result the outcome oa(Hi t+1 ) = oa(Hj t ). Overall, pj does not have an incentive to deviate in round t. According to the induction assumption, Strategies 1 and 2 specify a SPE when there are m- 1 outcomes in round t + 1. Therefore, pj does not have any incentive to deviate.

We now concentrate on the strategy of pi at round t, but we first derive some general inequalities. Given a history Hi t , suppose that there is an outcome ox ∈ Ot such that ox ≻pi oat = oa(Hi t + oit ). According to Lemma 8, since ox ≻pi oat, oat ≻pj ox. Suppose that both parties follow strategies 1 and 2, and let t′ be the round in which JGt′ = {oat}. Then, in round t, ℓi,t < di,at,t and ℓj,t < dj,at,t (otherwise, oat /∈ JGt′ ). By definition, t′ = ℓi,t + ℓj,t. In addition, since JGt′ = {oat}, ox must be part of Lowt′′ for some t′′ < t′ (otherwise, ox ∈ JGt′ ). Since ox ≻pi oat and ℓi,t < di,at,t, it must be that ox is part of Ljt′′ , that is, dj,x,t ≤ ℓj,t . In summary:

Now assume that in round t pi deviates, and the result of the negotiation, if both parties follow our strategies from round t+1, is ox. Note that pi in round t+1 is pj in round t, and thus oat ≻pi ox. Therefore, we use the same arguments as above to get

Now, assume by contradiction that there is an outcome od /∈ It such that if pi offers od the negotiation result will be ox, ox ≻pi oat. We first analyze the case where pj rejects the offer of od, since ox ≻pj od (otherwise, pj would have accepted). We examine the change in the distance function for pi and pj , for outcomes oat and ox, from round t to round t + 1. According to Lemma 3, |Lit+1 | + 1 = |Ljt |, and since ox ≻pj od and oat ≻pj od, dj,x,t and dj,at,t do not change when moving to round t + 1. Let c be an integer. Then:

If we combine (2) and (3) we get that:

Adding (1) we get that:

Adding Lemma 9 we can conclude that: ℓi,t+1 < ℓj,t ≤ ℓi,t < ℓi,t+1 - c. That is, ℓi,t+1 ≤ ℓi,t+1 - c - 2, thus c ≤ -2. However, the distance function cannot decrease by more than 1 when moving from round t to t+1, thus c ≥ -1.

We now analyze the case where pj accepts the offer of od, since od ⪰pj ox. We examine the change in the distance function for pi and pj , for outcomes oat and ox, from round t to round t + 1. Note that since pi deviates, od ≻pi oat. According to Lemma 8, oat ≻pj od. According to Lemma 3, |Lit+1 | + 1 = |Ljt |, and since oat ≻pj od, dj,at,t does not change when moving to round t + 1. However, since od ≻pj ox, dj,x,t increases by one when moving to round t + 1. Let c be an integer. Then:

If we combine (2) and (4) we get that:

Adding (1) we get that:ℓi,t < ℓj,t+1 - c

Adding Lemma 9 we can conclude that: ℓi,t+1 - 1 < ℓj,t ≤ ℓi,t < ℓj,t+1 - c. That is, ℓj,t+1 - 1 ≤ ℓj,t+1 - c - 2, thus c ≤ -1. However, in order for di,at,t to decrease by at least one, oat ≻pi od, but in our case od ≻pi oat.

Overall, we showed that pi does not have an incentive to deviate in round t. According to the induction assumption, Strategies 1 and 2 specify a SPE when there are m - 1 outcomes in round t + 1. Therefore, pi does not have any incentive to deviate.

Finally, note that trivial exploration of the whole game tree in order to derive the SPE would take at least O(2m) operations, since there can be m- 1 rounds in which a party pi can offer any outcome from the available outcomes and the other party pj can decide either to accept the offer or reject it. The complexity of finding a SPE strategy of [Anbarci, 2006] is not explicitly analyzed, but its running time is at least O(m2 ). Our approach provides elegant strategies that are easy to implement and are (computationally) more efficient: given a state in the game tree (i.e. given any history Hi t or Hj t ), we compute a SPE strategy from the current state in time that is linear inm. Indeed, in our approach we only need to simulate one branch of the tree (to find oa(Hi t ) or oa(Hj t )) and then trace the intersection between Lit and Ljt .

4.1 Properties

We first note that since we showed that the result of following Strategies 1 and 2 is Pareto optimal, we proved that they specify a SPE, and the SPE result is unique, we can infer that the SPE result of the protocol is Pareto optimal. We now move to analyze the relationship between the SPE result of the protocol and the results of the designed Rational Compromise (RC) bargaining rule [Kıbrıs and Sertel, 2007]. The RC rule is a private case of the Unanimity Compromise rule, where any agreement is preferred by both parties over a no-agreement result, as we assume. With our notations, the RC rule can be rephrased as the set RC = {ox| maxox∈O mink∈{1,2}(dk,x,1 + |Lk1 | - 1)}. It can also be computed by the following steps:

1. Let v = 1
2. For each k ∈ {1, 2}, let Bk v = {the v most preferred outcomes in ≻pk}.
3. If |B1 v ∩B2 v | > 0 then return B1 v ∩B2 v as the result.
4. Else, v ← v + 1 and go to line 2.

We note that the RC rule may return either one or two outcomes, while our protocol always results with a single outcome. Surprisingly, the SPE result of the negotiation protocol is always part of the set returned by the RC rule. The intuition is that our strategies specify a SPE by making offers and rejecting them until It = ∅. At this stage JGt = {oeq}, and by definition the set JGt is the intersection of the upper parts of the preferences of both parties, which corresponds to the B1 v ∩B2 v returned by RC.

Proof. Let t be the round where It = ∅ after both parties follow our strategies. By Corollary 2, JGt = {oeq}. Rephrasing the definition of JGt we get that JGt = Bi |Ot|-|Lit | ∩ Bj |Ot|-|Ljt | . If |Ljt | = |Lit |, then for any v where v ≤ |Ot| - |Ljt | , Biv ∩ Bjv = {oeq} or Biv ∩ Bjv = ∅. If |Ljt | = |Lit | + 1, then for any v where the v ≤ |Ot| - |Ljt |, Biv ∩Bjv = {oeq} or Biv ∩Bjv = ∅, and for v = |Ot| - |Lit | it is possible that Biv ∩ Bjv = {oeq, ox}, for some outcome ox. Overall, oeq ∈ RC.

Based on Theorem 11, we can derive interesting results regarding the relationship between the RC rule and the SPE result of the negotiation protocol:

1. If oeq is the SPE result let oeq′ be the SPE result if p1 and p2 switch their rules (i.e., p2 starts the negotiation). If oeq ̸= oeq′ , then RC = {oeq, oeq′}
2. If m is odd and ℓ1,1 + ℓ2,1 is even or if m is even and ℓ1,1 + ℓ2,1 is odd, then |RC| = 1.
3. If |RC| = {ox, oy} and ℓ1,1 + ℓ2,1 is odd then oeq = ox and ox ≻pi oy. If ℓ1,1 + ℓ2,1 is even then oeq = oy and oy ≻pj ox.

Proof. 1. An easy corollary of Theorem 11.

1. An easy corollary of Theorem 11.
2. If m is odd and ℓ1,1 + ℓ2,1 is even or if m is even and ℓ1,1+ℓ2,1 is odd, thenmt is odd. Therefore, |L1t | = |L2t | by definition. Then, by Theorem 11, for any v where v ≤ |Ot| - |L1t | , B1 v ∩ B2 v = {oeq} or B1 v ∩ B2 v = ∅. That is, RC = {oeq}.
3. |RC| = 2, thus there exists v such that B1 v ∩ B2 v = {ox, oy}, and for every v′ < v, B1 v′ ∩ B2 v′ = ∅. From Theorem 11, oeq = ox or oeq = oy. Let t be the round such that It = ∅ and JGt = {oeq}. That is, B1 |Ot |-|L1t | ∩ B2 |Ot|-|L2t | = {oeq}. Therefore, |L1t | ̸= |L2t |, and thus mt is even. If ℓ1,1 + ℓ2,1 is odd then it is p2 's turn to offer. That is, |L2t | + 1 = |L1t |, and since ox ≻p1 oy, oy ∈ L1t . Therefore, oeq = ox. Similarly, if ℓ1,1+ℓ2,1 is even then it is p1 's turn to offer. That is, |L1t |+1 = |L2t |, and since oy ≻p2 ox, ox ∈ L2t . Therefore, oeq = oy.

Finally, we adapt the monotonicity criterion that the RC rule satisfies for our domain, and show that the negotiation protocol is monotonic.

Definition 5. A negotiation protocol is monotonic if given an instance (O,≻p1,≻p2) where the SPE result is oeq, then for any instance (O′ ,≻′p1,≻′p2) such that:

1. O ⊂ O′ .

1. For any o1, o2 ∈ O, o1 ̸= o2, and for k ∈ {1, 2}, if o1 ≻pk o2 then o1 ≻′pk o2.
2. For any o ∈ O′ \ O, and for k ∈ {1, 2}, o ≻′pk oeq. we have that o′eq ≻′pk oeq.

Theorem 13. The negotiation protocol is monotonic.

Proof. Given an instance (O, ≻p1 , ≻p2 ), we know from Theorem 11 that oeq ∈ RC. If we add a set of outcomes O′ \ O such that for every outcome o ∈ O′ \ O, o ≻ oeq for both parties, then for every outcome o′ in the set returned by the RC rule on the modified instance (O′ ,≻′p1,≻′p2), o′ ≻ oeq by both parties. Since o′eq ∈ RC on (O′ ,≻′p1,≻′p2), we get that o′eq ≻ oeq for both parties, as required.

5 No Information

We now consider the case of no information, where we assume that neither party knows the preference order of the other party. Moreover, the parties do not even hold any prior probability distribution over each other's possible preference orders. A common solution concept for this case is an expost equilibrium, or in our case, an ex-post SPE. Intuitively, this is a strategy profile in which the strategy of each party depends only on her own type, i.e., its preference order, and it is a SPE for every realization of the other party's type (i.e. her private preference order). Formally, let sk(≺) be a strategy for player k ∈ {1, 2} given a preference order ≺, and let F([s1(≺), s2(≺′ )]) be the negotiation result if both parties follow their strategies. In the ex-post setting, a strategy for party k ∈ {1, 2}, sk, is a best response to s3-k if for every strategy s′k and for every preference orders ≺,≺′ , F([sk(≺), s3-k(≺′ )]) ⪰k F([s′k (≺), s3-k(≺′ )]). A strategy profile [s1, s2] is an ex-post equilibrium if s1 is a best response to s2 and s2 is a best response to s1, and it is an ex-post SPE if it is an ex-post equilibrium in every subgame of the game. We show that ex-post SPE is too strong to exist in our setting.

Theorem 14. There are no two strategies that specify an expost SPE for our protocol.

Proof. Clearly, every ex-post SPE is also a SPE (i.e., in the full information setting), and we can thus use our previous results that characterize the SPE. Assume by contradiction that there are two strategies s1, s2 for parties p1 , p2 , respectively, such that [s1, s2] is an ex-post SPE. Let ≺1= o1 ≺ o2 ≺ o5 ≺ o4 ≺ o3 ≺ o6, and let ≺2= o1 ≺ o2 ≺ o6 ≺ o3 ≺ o5 ≺ o4. Following our strategies we get that the SPE result is o4. Since the SPE result is unique and every ex-post SPE is also a SPE, F([s1(≺1), s2(≺2)]) = o4. Now consider ≺′1= o4 ≺ o5 ≺ o1 ≺ o2 ≺ o3 ≺ o6. According to Corollary 1, F([s1(≺′1 ), s2(≺2)]) = o3. Note that o4 ≺p1 o3. Consider the following strategy: s′1 (≺) = s1(≺′1 ) if ≺=≺1, and s′1 (≺) = s1(≺) otherwise. That is, F([s1(≺1), s2(≺2 )]) ≺p1 F([s′1 (≺1), s2(≺2)]), and thus s1 is not a best response to s2.

We note that Theorem 14 also implies that there is no solution in dominant strategies. Another approach to uncertainty, which follows a conservative attitude, is that a party pk , k ∈ {1, 2}, who wants to maximize her utility may want to play a maxmin strategy. That is, since the preference order and the strategy of the other party p3-k are not known, it is sensible to assume that p3-k happens to play a strategy that causes the greatest harm to pk , and to act accordingly. pk then guarantees the maxmin value of the game for her, which in our case is a set of outcomes such that no other outcome that is ranked lower than all of the outcomes in this set will be accepted as the result of the negotiation, regardless of the preferences of p3-k . Before we show the maxmin strategy we define the complement sets for the sets Lkt , i.e., the sets of highest ranked outcomes.

Definition 6. In each round t, for each party pk , k ∈ {1, 2}, U k t = Ot \ Lkt .

The maxmin strategy, which is composed of offering and response strategies, is defined as follows:

Strategy 3 (MAXMIN STRATEGY). Given a history Hi t , offer any o ∈ U i t . Given a history Hj t , if o ∈ U j t then accept o, else reject o.

We now prove that our strategy specifies a maxmin strategy, and that a party pk that follows it can guarantee the maxmin value of the game, which is the set U k 1 . We denote the party that uses Strategy 3 by pmax and the other party, which might try to minimize the utility of pmax , by pmin . Note that we need to handle both the case where pmax starts the negotiation (i.e, pmax = p1 ) and the case where pmin starts it (i.e., pmin = p1 ). We re-use Lemmas 4, 5 and 6, since they do not depend on the full-information assumption. Furthermore, we add a fourth lemma, which complements these three lemmas by considering the fourth possible offer type.

Lemma 15. In round t, if pi offers o /∈ Ljt and pj rejects it, then Lit+1 ← Ljt \ {o′ }, where o ̸= o′ .

For ease of notation, we write U ≻p o for U ⊂ O to denote that party p strictly prefers all of the outcomes in the set U over o. The intuition of our proof is as follows. We show that if pmax deviates from the strategy specified by Strategy 3, pmin is able to make the negotiation result in an outcome o, such that U max 1 ≻pmax o.

Theorem 16. Strategy 3 specifies a maxmin strategy, and the maxmin value of the game is the set U max 1 .

Proof. We will prove by induction on m. If m = 2 WLOG assume that ≻pmax= o1 ≻ o2. If pmax = p1 then U max 1 = {o1, o2} and clearly one of them will be the negotiation result. If pmax = p2 then U max 1 = {o1}. If pmin offers o1 in the first round, according to our strategy pmax should accept it. If pmin offers o2 in the first round, according to our strategy pmax should reject it, and offer o1 in the next round. Since this is the last round, o1 will be accepted. In any case, the negotiation result is o1. On the other hand, if pmax deviates and rejects the offer of o1 or accepts the offer of o2, then o2 will be the result of the negotiation, but U max 1 ≻pmax o2. Now, assume that if there are m- 1 outcomes in round t + 1 our strategy specifies a maxmin strategy, and the maxmin value of the game is the set U max t+1 . We show that our strategy specifies a maxmin strategy, and the maxmin value of the game is the set U max t when there are m outcomes in round t.

Assume that it is pmax 's turn to offer. Clearly, if pmax deviates and offers an outcome o such that U max t ≻pmax o then pmin can accept it, and the negotiation results in o. On the other hand, if pmax offers any o ∈ U max t then pmin can either accept or reject it. If pmin rejects it then there arem-1 outcomes in the next round, and according to the induction assumption pmax can guarantee the maxmin value of U max t+1 by following our strategy. However, according to Lemma 4, Lmax t+1 = Lmax t and thus U max t+1 ∪ {o} = U max t . Overall, the maxmin value of the game is the set U max t .

Now assume that it is pmin 's turn to offer, and pmin offers o ∈ U max t . Clearly, if pmax accepts then the negotiation result is from U max t . If pmax deviates and rejects, then according to induction assumption pmax can guarantee the maxmin value of U max t+1 . However, according to Lemma 15, Lmax t+1 = Lmax t \ {o′ }, and thus U max t+1 = U max t \ {o}∪{o′ }. That is, o′ is a possible result of the negotiation even though U max t ≻pmax o′ . Finally, assume that pmin offers o /∈ U max t . Clearly, if pmax deviates and accepts, then the negotiation results in o. On the other hand, if pmax follows our strategy and rejects, then according to the induction assumption pmax can guarantee the maxmin value of U max t+1 . However, according to Lemma 5, Lmax t+1 = Lmax t \{o}, and thus U max t+1 = U max t .

We note that even though a party does not hold any information regarding the preference order of the other party, she can still guarantee that the negotiation result will be from the upper part of her preference order (i.e., U k 1 ) by following Strategy 3. This is possible since both parties have some important common knowledge, which is the number of outcomes m, as formally captured in Lemma 1.

Now, what will be the negotiation result if neither party knows the preference order of the other party, but both are rational and will thus follow the maxmin strategy? Clearly, the negotiation result will be an outcome o such that o ∈ U 1 1 ∩U 2 1 . That is, an outcome from the set JG1 as defined in Definition 1. We then get an interesting observation: if I1 = ∅, JG1 = {0eq} according to Corollary 2, thus the negotiation result is the same for both the case of full information and the case of no information.

In addition, we note that a party pi cannot guarantee that the negotiation result will be from a subset U ⊂ U i1 , since we proved that this is the maxmin value. However, she can heuristically offer in each round t the best outcome in U i t , instead of an arbitrarily chosen o ∈ U i t . Since |U j t | ≥ |Ljt |, if the other party pj is also rational and plays the maxmin strategy, there are more cases where pj will accept this offer, and it is thus beneficial for pi to heuristically offer in each round t the best outcome in U i t .

The idea of the maxmin strategy is that a party, not knowing the preferences of the other party, makes a worst case assumption about the behavior of that party (i.e., that she does not need to be rational). This assumption may seem too restrictive, and we therefore also consider the robustoptimization equilibrium solution concept from [Aghassi and Bertsimas, 2006], which we adapt to out setting. Intuitively, in this solution concept each party makes a worst case assumption about the preference order of the other party, but each party still assumes that the other party will play rationally and thus her aim is to maximize her utility. Formally, given a strategy profile [s1, s2] and a preference order ≺, let ws1,≺,s2 = F([s1(≺), s2(≺′ )]), where ≺′ is a preference order such that for all ≺′′ , F([s1(≺), s2(≺′ )]) ⪯p1 F([s1(≺ ), s2(≺′′ )]). In the robust-optimization setting, a strategy for party k ∈ {1, 2}, sk, is a best response to s3-k if for all s′k and for all ≺, wsk,≺,s3-k ⪰pk ws′k ,≺,s3-k . A strategy profile [s1, s2] is a robust-optimization equilibrium if s1 is a best response to s2 and s2 is a best response to s1. We show that in our setting, surprisingly, every pair of maxmin strategies specifies a robust-optimization equilibrium.

Theorem17. If s1 and s2 aremaxmin strategies, then [s1, s2] is a robust-optimization equilibrium.

Proof. Given a preference order, ≺, let ≺op be the opposite preference order, i.e., if ≺= o1 ≺ o2 ≺ ... ≺ om then ≺op= o1 ≻ o2 ≻ ... ≻ om. According to Theorem 16, if sk is a maxmin strategy then the negotiation result is o ∈ U k 1 . That is, the worst negotiation result for pk is the least preferred outcome in U k 1 , denoted by owo. Since the other party p3-k is also using a maxmin strategy, o ∈ U k 1 ∩ U 3-k 1 . For every preference order, ≺, if the preference order of p3-k =≺op, U k 1 ∩ U 3-k 1 = {owo}. That is, ws1,≺,s3-k = owo. Assume by contradiction that there is another strategy s′k and a preference order ≺, such that ws′k ,≺,s3-k ≻pk owo. However, if the preference order of p3-k =≺op, ws′k ,≺,s3-k /∈ U 3-k 1 , in contradiction to Theorem 16.

Finally, consider an asymmetric information setting, where there exists one party that has full information about the other party's preference order, while the other party does not have this information. Let pinfo be the party that has the full information, and pnull be the other party. pnull has no information and she will thus act according to the maxmin strategy (Strategy 3). pinfo would like to take advantage of her knowledge, so the negotiation result will be better for her. However, according to Theorem 16, the maxmin value of the game is U null 1 . Therefore, the best strategy for pinfo is as follows. If pinfo starts the negotiation, she should offer the best outcome from U null 1 according to her preferences, and pnull will accept it. If pinfo starts the negotiation, she will offer an outcome from U null 1 . If this is the best outcome according to pinfo 's preferences, she should accept it. Otherwise, in the second round pinfo should offer the best outcome from U null 1 according to her preferences, and pnull will accept it.

6 Conclusion

We investigated the VAOV negotiation protocol, which is suitable for ordinal preferences over a finite set of outcomes. We introduced strategies that specify a SPE, and improved upon previous results by providing a linear time algorithm that computes a SPE strategy. We provided substantial analysis of our strategies, which showed the equivalence of the SPE result of the protocol in a non-cooperative setting, to the result of the RC rule in a cooperative setting. Finally, we analyzed the no information setting. We believe that our approach is especially suitable for non-cooperative, multi-agent systems, since we provide easy to implement strategies that can be computed only once if both agents follow the SPE strategy on the equilibrium path. Moreover, there is no need for a central authority to guarantee that the negotiation result will be Pareto optimal, if both agents are rational and follow the SPE strategy. For future work, we would like to extend the protocol to a multi-party setting and analyze the resulting SPE. In addition, it is important to find additional implementation of other bargaining rules by negotiation protocols, similar to the implementation that we showed for the RC rule by the SPE of the VAOV protocol.

Acknowledgments

This work was supported by the Israel Science Foundation, Grant No. 1488/14.