Axiomatic Characterization of Task Oriented Negotiation

1 Introduction

Negotiation or bargaining is a typical form of interaction between intelligent agents. Initiated by Nash's seminal work [Nash, 1950], the study of negotiation in game theory has reached high sophistication with a variety of models and solutions. The theory has been extensively applied to economics, management science, social science as well as computer science [Binmore et al., 1992; Thomson, 1994; Rosenschein and Zlotkin, 1994; Jennings et al., 2001].

Game-theoretic account of bargaining consists of two typical models: axiomatic model (cooperative theory) and strategic model (non-cooperative theory). The axiomatic model specifies a bargaining problem as a one-shot game with complete information and characterizes bargaining solutions axiomatically [Thomson, 1994]. The strategic model devices explicit construction of negotiation procedures and identifies bargaining outcomes as equilibria [Binmore et al., 1992]. The attempt to establish the relationship between the two models is known as the Nash program.

The axiomatic model of negotiation is domain-dependent, which means that a solution can have totally different characteristics with different domain of problems. Given the Nash solution as an example, the axiomatic systems for convex domain, comprehensive domain, finite domain, and ordinal domain are significantly different (see Section 6 for a brief summary). This feature causes the axiomatic theory of bargaining rather complicated and the research exceedingly interesting.

∗This research was partially supported by the Australian Research Council through Discovery Project DP0988750.

Task Oriented Domain (TOD), introduced by Zlotkin and Rosenschein (1993), represents a class of negotiation problems that can be abstracted as task sharing among autonomous agents. More specifically, the domain specifies a certain kind of interaction among agents in which the agents have sets of tasks to carry out, and can exchange tasks and share in their execution. A range of real-world applications, such as parcel delivery, database queries, job allocation, can be described in this domain [Rosenschein and Zlotkin, 1994].

As originated from computer science and AI, the task oriented domain has specific features that differentiate it from those that have been studied in game theory. The domain is not convex even after randomization, therefore the traditional axiomatizations for the Nash solution, the Kalai-Smorodinsky (KS) solution and the Egalitarian solution are not applicable [Nash, 1950; Kalai and Smorodinsky, 1975]. The modern extensions of these solutions to the non-convex domain are inapplicable as well because the domain is not comprehensive [Conley and Wilkie, 1991; 1996; Xu and Yoshihara, 2006]. Those solutions specially designed for discrete domains are also not suitable for task oriented negotiation [Mariotti, 1998; ¨Ozg¨ur Kibris and Sertel, 2007]. As we will see, the above mentioned three solutions coincide within TODs and their axiomatic characterization is significantly different from the ones for any other domains.

The paper is organized as the following. Section 2 recalls the basic concepts on TOD from [Rosenschein and Zlotkin, 1994]. Section 3 presents a cooperative model of task oriented negotiation. In Section 4, we redefine and characterize three classical bargaining solutions in mixed deals. In Section 5, we demonstrate how the axiomatic characterization can be used to produce an approximate solution in pure deals. In the final two sections, we conclude the paper with a discussion of related work.

2 Task oriented domains

A task oriented domain specifies a negotiation situation in which a group of agents have to decide how to cooperate for reducing execution costs. More formally, we have the following definition.

Definition 1 [Zlotkin and Rosenschein, 1993] A task oriented domain (TOD) is a tuple 〈T , A, c〉 where:

1. T is a finite set of possible tasks;
2. A= {A1,A2} is the set of agents;
3. c : 2T → ℜ+ is a monotonic function that maps a set of possible tasks to a non-negative real number, satisfying X ⊆ Y ⊆ T implies c(X ) ≤ c(Y );

In other words, a task oriented domain specifies a set of possible tasks, a group of agents who are capable of carrying out any possible combination of tasks, and a cost function which determines the cost of execution of each set of tasks. Different from the original setting in [Zlotkin and Rosenschein, 1993], we restrict the set of possible tasks to be finite and the number of agents to be two.

Rosenschein and Zlotkin (1994) have demonstrated that a number of real-world negotiation scenarios can be specified in task oriented domains. All these scenarios satisfy the following common assumption:

In other words, regrouping tasks could reduce execution costs. This motivates the agents to negotiate for a better task distribution. Throughout this paper, we assume that all the domains we consider are subadditive.

3 Task oriented negotiation

In order to facilitate analysis of task oriented negotiation, Rosenschein and Zlotkin (1994) has introduced a few concepts to model the problems. Let us recall the basic concepts that will be used in this paper.

Given a TOD 〈T ,A, c〉, a pair (T1, T2) is an encounter within the TOD if, for each i ∈ {1, 2}, Ti is a subset of T . We denote the set of all encounters within the TOD by Σ(T , A, c).

Let T = (T1, T2) be an encounter, a pair (D1,D2) is a pure deal of T if D1 ∪D2 = T1 ∪ T2. In other words, a pure deal is a redistribution of tasks in T among the agents. We let Ω(T ) be the set of all pure deals of T . Note that T itself is always a pure deal of T , which is referred to as the conflict deal of the encounter. Also, (T1 ∪ T2, ∅) and (∅, T1 ∪ T2) are pure deals of T .

Let (D1,D2) be a pure deal of T . Any expression in the form of "(D1,D2) : p" is called a mixed deal of T if p is a probability, i.e, (0 ≤ p ≤ 1). Intuitively, (D1,D2) : p represents a probabilistic redistribution of the tasks in (D1,D2) in the way that agent 1 is assigned D1 with probability p and D2 with 1 - p while agent 2 receives the sets of tasks with the inverse probability. The set of all the mixed deals of T is denoted by Ω(T ). In certain context, we view a pure deal (D1,D2) as the mixed deal (D1,D2) : 1. Moreover, the mixed deal (T1 ∪ T2, ∅) : p is called to be an all-or-nothing deal of T . For more intuitive discussions on the above concepts, see [Rosenschein and Zlotkin, 1994] Chapters 3 & 4.

We would like to remark that the operation of randomization to generate a mixed deal is significantly different from the way that Nash uses to convexify a feasible set, where an "anticipation" is generated from two anticipations in the form: pD′ + (1 - p)D′′ . As a result, any feasible set becomes convex after Nash's randomization. However, the set of mixed deals is not necessarily convex (see Figure 1).

Next we extend the cost function of a TOD to mixed deals. For each encounter T within a TOD 〈T ,A, c〉, we define a cost function C : Ω(T ) → ℜ2 as follows: for each D = (D1,D2) : p ∈ Ω(T ), C defines the cost of the mixed deal to each agent, i.e., C(D) = (C1(D), C2(D)), where

Note that for a mixed deal (D1,D2) : p, we always have C1(D) + C2(D) = c(D1) + c(D2). In other words, the process of randomizing a pure deal redistributes cost (workload) between two agents but does not reduce cost. To reduce cost, we need to redistribute tasks. In fact, there are two major factors that determine the outcome of a task oriented negotiation: cost reduction and workload distribution. We will use these two factors as the criteria to compare deals.

For any two mixed deals D and D′ of an encounter, we say that D dominates D′ , denoted by D ⪰ D′ , if and only if Ci(D) ≤ Ci(D′ ) for all i ∈ {1, 2}. We say that D strongly dominates D′ , denoted by D ≻ D′ , if and only if D ⪰ D′ and there is an i such that Ci(D) < Ci(D′ ). Moreover, we say that D is equivalent to D′ , written as D ≈ D′ if and only if D ⪰ D′ and D′ ⪰ D. Obviously, ≈ is an equivalence relation on Ω(T ). Based on the concept of domination, we define the Pareto set of Ω(T ) as:

We can also compare two deals in terms of workload distribution. We consider a deal to be "fairer" than the other if its workload distribution between agents is closer to the original allocation of the encounter. Formally, for any D′ ,D′′ ∈ Ω(T ), we write D′ ▷T D′′ if and only if dist(D′ , T ) < dist(D′′ , T ), where

Intuitively, D′ ▷T D′′ means that the workload distribution of D′ is closer to T than that of D′′ . Note that we use the difference of costs to each agent to measure the workload distribution between the agents.

All the above concepts can also be defined on pure deals. To save space, we omit their definitions.

The following lemmas describe the properties of Pareto set, which will be frequently used in the proof of other theorems. The first lemma is a theorem in [Rosenschein and Zlotkin, 1994] (Theorem 9), which says that Pareto optimal deals maximize cost reduction. The second lemma asserts that any Pareto optimal deal has an all-or-nothing representative. We omit their proof here.

Lemma 1 [Rosenschein and Zlotkin, 1994] For any (D1,D2) : p ∈ P (T ), c(D1) + c(D2) = c(D1 ∪ D2).

Lemma 2 (D1,D2) : p ∈ P (T ) if and only if there exists an all-or-nothing deal D′ such that D ≈ D′ .

4 Negotiation solutions in mixed deals

In this section, we consider the solutions that take mixed deals as output. We apply three most outstanding bargaining solutions in game theory: the Nash solution, the KalaiSmorodinsky (KS) solution and the Egalitarian solution 1 , to TODs and characterize these solutions.

4.1 Game-theoretic bargaining model

Negotiation analysis aims to provide a clear-cut prediction of the outcomes of any negotiation situation within the domain under consideration. In game theory, a bargaining solution is a function that assigns to each bargaining game a single agreement or a set of agreements depending on the underlying domains.

Formally, a bargaining game is a pair (S, d), where S ⊆ ℜ2 is the feasible set that can be derived from possible agreements and d ∈ S stands for the disagreement point. A bargaining solution f is a function that assigns to each bargaining game (S, d) a unique point of S or a subset of S.

Given an encounter T within a TOD 〈T ,A, c〉, we can define a game-theoretic bargaining game by using Rosenschein and Zlotkin's utility function: for each D ∈ Ω(T ), u1(D) = c(T1) - C1(D) and u2(D) = c(T2) - C2(D). We let S = {(u1(D), u2(D)) : (D1,D2) ∈ Ω(T )} and d = (0, 0). Then (S, d) is the bargaining game that corresponds to the encounter T . One may think that the task oriented negotiation problem could have been solved if we apply a game-theoretic solution to each of the bargaining games. Unfortunately this is not the case. As we have mentioned in the introduction, all game-theoretic negotiation solutions are domain-dependent. As we will see in Example 1 and 2, all three solutions we consider in this section give different results in mixed deals and in pure deals.

Figure 1 shows an example of bargaining game in task oriented domain with mixed deals (the dots represent pure deals and the dashed lines represent mixed deals. We omit the original example due to space limitation). It is easy to see that such a bargaining game is neither convex nor comprehensive, which means that the existing characterizations for the classical bargaining solutions are not applicable to this domain.

1 see [Thomson, 1994] for a comprehensive introduction of these solutions.

4.2 Three classical solutions

Although the axiomatic characterizations for classical gametheoretic solutions are not applicable to task oriented negotiation, the solutions themselves can be applied to the domain of problems even though their behavior will be very likely different. In this subsection, we redefine the three classical bargaining solutions in the context of task oriented domains.

Definition 2 Given a TOD 〈T ,A, c〉, a negotiation solution f in mixed deals is a function that assigns to each encounter T ∈ Σ(T , A, c) a set of mixed deals, i.e., f (T ) ⊆ Ω(T ).

Note that a negotiation solution is set-valued, which means that the solution outputs a set of mixed deals as its prediction. This is because there might be several equivalent ways to redistribute tasks.

Now we define a few specific solutions. To facilitate these definitions, let I (T ) be the individual rational deals of T , i.e,

First, we define the Nash solution in the task oriented domain [Nash, 1950] (also see [Rosenschein and Zlotkin, 1994] p.50).

Definition 3 A negotiation solution f in mixed deals is the Nash solution if for all T ∈ Σ(T , A, c),

where argmax means the arguments of max function, i.e., the maximizers of the product of the utilities of two agents.

Next, we apply the Egalitarian solution to our domain:

Definition 4 A negotiation solution f in mixed deals is the Egalitarian solution if for all T ∈ Σ(T , A, c),

that is, the deals that maximize and divide equally the utilities of two agents.

Finally, we simulate Kalai-Smorodinsky's solution [Kalai and Smorodinsky, 1975]. To this end, let (a1, a2) = ( max D∈I(T )(c(T1) - C1(D), max D∈I(T )(c(T2) - C2(D)), i.e., the

ideal point. Then we have

Definition 5 A negotiation solution f in mixed deals is the Kalai-Smorodinsky solution if for all T ∈ Σ(T , A, c),

In other words, the solution gives the individual rational deals that maximize the utilities on the diagonal from (0, 0), the utilities of the conflict deal, to the ideal point (a1, a2).

Example 1 Let 〈T ,A, c〉 be a TOD where T = {a, b, c}, A = {A1, A2} and the cost function is the following:

Consider an encounter T = ({a, b}, {b, c}) within the TOD. It is not hard to know that the Nash solution, KS solution and Egalitarian solution give the same set of mixed deals with the elements that are all equivalent to the all-or-nothing deal ({a, b, c}, ∅) : 0.3. □

Lemma 3 For any encounter T within a TOD, f N (T ) = f KS (T ) = f E (T ), where f N , f KS , f E are the Nash solution, the KS solution and the Egalitarian solution, respectively.

Lemma 4 Let f be any of the three solutions defined above. For any encounter T within a TOD and any D,D′ ∈ f (T ), D ≈ D′ . In other words, each of the three solutions gives unique outcome modulo ≈.

The above results reflect the special features of task oriented domains. The first result says that these three solutions are actually the same. This is not surprising. Since a task oriented domain assumes that all agents share the same cost function, it is impossible for an agent to vary its utility to gain more negotiation power. In other words, all the agents have the same negotiation power. Therefore they can share the available utility equally (note that this does not mean that all the agents will be assigned the same amount of tasks or the tasks with the same cost). On the contrary, the second result is a bit surprising because typical solutions on non-convex domains are multiple-valued [Mariotti, 1998]. We have such a property because of the assumption of subadditivity on the cost function and randomization on pure deals.

4.3 Characterization

We have seen above that the task oriented domain is a specific domain that unifies three classical bargaining solutions. This indicates that the characterization of these solutions within a TOD requires specific axioms. It is well known that the Egalitarian solution can be characterized in convex domain by the axioms: Pareto optimality, scale invariance, symmetry and strong monotonicity [Thomson, 1994]. We notice that scale invariance is not applicable to a TOD because the agents share the same cost function. Without this axiom, symmetry becomes useless. In addition, strong monotonicity is also hard to apply because an arbitrary subset of the set of mixed deals does not necessarily correspond to another encounter. However, it is easy to see that Pareto optimality and individual rationality (implied by other axioms in game theory) are true with any TOD. In short, the following axioms will characterize all three solutions within a TOD.

IR: D ∈ f (T ) implies D ⪰ T . (Individual rationality)

PO: f (T ) ⊆ P (T ). (Pareto optimality)

Eq: D ∈ f (T ) and D ≈ D′ imply D′ ∈ f (T ). (Equivalence)

The first two axioms are standard requirements for negotiation solutions, which are self-expanatory. The other three are specific to the task oriented negotiation. NV says that the solution guarantees an output (obviously the worst case is the conflict deal). Eq says that all deals are treated the same if their costs to each agent are the same. WB says that a solution should guarantee that the workload distribution of the final agreement must be the closest to the original allocation. Note that this property implies that if an agent is originally allocated heavier tasks than the other (measured in their costs), the agent should receive also heavier tasks in the final agreement.

Theorem 1 Given a TOD 〈T ,A, c〉, a negotiation function in mixed deals is the Egalitarian solution (therefore, the Nash solution and the KS solution) if and only if it satisfies IR, PO, NV, Eq and WB.

It is easy to see that the key components of the characterization are the two optimality axioms: PO and WB. PO requires a solution to be the best in cost reduction while WB requires the solution to be the best to match the original workload distribution.

5 Negotiation solutions in pure deals

In the previous section we allow to randomize a pure deal so that the tasks can be divided in any portion to balance workload. If we disable randomization by restricting a solution to pure deals, the problem will become much harder. To see the problem, let's consider Example 1 again.

Example 2 Consider the negotiation encounter in Example 1. If we restrict the solutions introduced in Section 4.2 to pure deals, only the Nash solution is non-empty, which is {({a}, {b, c}), ({b}, {a, c}), ({a, b}, {c})}. In fact, these deals are exactly all the deals that are Pareto optimal and individual rational. The Egalitarian solution and KalaiSmorodinsky solution are empty. Therefore none of the solutions offers useful prediction.

The reason that causes the failure of all the solutions is that, without mixed deals, we are not always able to divide tasks to each agent to match the original workload distribution due to the indivisibility of atomic tasks. In fact, this is not a problem particularly to task oriented negotiation. Almost every negotiation domain has the same problem: a solution exists in an idealized domain, say convex hell or comprehensive hell, but cannot be found in its original domain. In this section, we demonstrate how to use the characterization we presented in the previous section to construct an approximate solution for the task oriented negotiation problems. First, we redefine negotiation solution by restricting the outcomes to be pure deals.

Given a TOD 〈T , A, c〉, a pure deal negotiation solution F is a function that assigns to each encounter T ∈ Σ(T , A, c) a set of pure deals of T , i.e., F (T ) ⊆ Ω(T ).

Definition 6 A pure deal negotiation solution F is the minimal distance solution if for all T ∈ Σ(T , A, c),

where NS (T ) = P (T ) ∩ I (T ), i.e., the negotiation set of T . P (T ), I (T ) and dist(D, T ) can be redefined in pure deals by using the equations (1), (3) and (2), respectively.

The following result indicates that the minimal distance solution is an approximation of the Egalitarian solution in mixed deals (we omit the proof of the proposition).

Proposition 1 Let f be the Egalitarian solution in mixed deals on a TOD 〈T , A, c〉. Then for any T ∈ Σ(T , A, c),

Example 3 Consider the negotiation encounter in Example 1 again. It is easy to calculate that the minimal distance solution of the encounter is:

Notice that different from the mixed deal solution, F (T ) is not unique even after modulo operation. However, the worst case is two modulo equivalence.

Lemma 5 For any encounter T in a TOD, the minimal distance solution F (T ) is non-empty and has at most two elements modulo ≈.

The following theorem shows that the minimal distance solution can be characterized by the same set of axioms for the mixed deal solutions.

Theorem 2 Given a TOD 〈T ,A, c〉, a negotiation function in pure deals is the minimal distance solution if and only if it satisfies the following properties:

IR: D ∈ F (T ) implies D ⪰ T . (Individual rationality)

PO: F (T ) ⊆ P (T ). (Pareto optimality)

NV: F (T ) ̸= ∅. (Non-vacuity)

Eq: D ∈ f (T ) and D ≈D′ imply D′ ∈ f (T ). (Equivalence)

WB: D ∈ F (T ) and D′ ▷T D imply D′ ̸∈ P (T ). (Workload balance)

This theorem again exhibits another specific feature of task oriented domains that different solutions share the same axiomatization. Note that the axioms may play different roles in different characterization. For instance, in Theorem 1, WB forces the solution to be zero distance to T while in Theorem 2, it just requires the solution to be as close to T as possible.

6 Related work

Axiomatic analysis of bargaining situations started from Nash (1950). Nash proposed a bargaining solution and characterized it with a set of axioms. Nash's characterization only applies to convex domains, which can be implemented via randomizing possible agreements. Kaneko (1980) extended Nash's characterization to non-convex domain but enforced continuity on the domain meanwhile allowing the solution to be set-valued. This result was refined by a few other authors so that the requirement for convexity is replaced by comprehensiveness without need to amend Nash's original axioms [Conley and Wilkie, 1996; Zhou, 1996; Xu and Yoshihara, 2006]). The result was also extended to the Kalai-Smorodinsky solution and Egalitarian solution [Conley and Wilkie, 1991; Hougaard and Tvede, 2003; Xu and Yoshihara, 2006]. However, these results are restricted to continuous domains. Characterizing a bargaining solution on discrete or finite domains is much harder mostly because the idealized points that satisfy certain axioms, say Nash's, may not exist in the feasible set. Among a few authors, Mariotti and Lahiri proposed two different characterizations of the Nash solution in finite domains [Mariotti, 1998; Lahiri, 2003]. Kibris and Sertel characterized a few nonstandard solutions for finite ordinal domains [ ¨Ozg¨ur Kibris and Sertel, 2007]. Unfortunately none of these results can be applied to the task oriented domains. Mariotti's axioms require to operate a feasible set by adding or removing a point. Such an operation is not allowed for our domain. Kibris and Sertel's axioms also apply set operations on feasible sets. Lahiri's characterization applies only on a special finite domain, in which the task oriented problems are not describable.

This work was developed based on Rosenschein and Zlotkin's framework [Zlotkin and Rosenschein, 1993; Rosenschein and Zlotkin, 1994]. The basic concepts of task oriented domains, pure deals and mixed deals are extended from their work. We would like to remark that the special design of randomization for mixed deals is the key to most of the elegant results. Different from Nash's approach, it does not convexify a domain but can guarantee the uniqueness of solution. It maximally keeps the link to original deals so that the original deals are still operable (see Lemma 1) while gains the benefit of divisibility of tasks.

7 Conclusion and discussions

We have presented an axiomatic analysis of negotiation problems within task oriented domains. We found that such a domain has a number of interesting features. Firstly, three classical bargaining solutions coincide when they are applied to a TOD with mixed deals but diverge if their outcomes are restricted to pure deals. Secondly, all these solutions in mixed deals have unique value by equivalence and their pure deal approximation has at most two values. Thirdly, the solutions in mixed deals and their pure deal approximation share the same axiomatic characterization. All these special features originate from the specific setting of task oriented domains. The combination of simplicity of cost function setting and requirement for dual optimality gives the domains rich properties with manageable complexity and makes the research deeply interesting.

Nash's axiomatic model laid on the foundation of bargaining theory. It is also one of the most fundamental models in modern economic theory [Rubinstein, 2000]. An axiomatic model of bargaining fully specify a domain and captures the nature of problems in the domain. It achieves great generality by avoiding any specification of bargaining processes therefore can serve as a guideline for devising variety of specific negotiation procedures or solutions for specific applications (Section 5 is a simple example of such an application).

Negotiation and bargaining has been a research area in economics and social science for nearly sixty years. The research has been mostly motivated by problems from economics and social science. Problems raised from computer science or AI can be appreciably different from those from other disciplines. Besides task oriented domains, similar domains of problems can also be found in AI literature, such as state oriented domains [Rosenschein and Zlotkin, 1994], argumentation-based negotiation [Kraus et al., 1998], contract negotiation [Dunne, 2005], and etc. Axiomatic analysis on these domains will not only help us to gain a better understanding of these problems but also would make a contribution towards the game-theoretic research of bargaining.