Abstract:
A multiagent system may be thought of as an artificial society of autonomous software agents and we can apply concepts borrowed from welfare economics and social choice theory to assess the social welfare of such an agent society. In this paper, we study an abstract negotiation framework where agents can agree on multilateral deals to exchange bundles of indivisible resources. We then analyse how these deals affect social welfare for different instances of the basic framework and different interpretations of the concept of social welfare itself. In particular, we show how certain classes of deals are both sufficient and necessary to guarantee that a socially optimal allocation of resources will be reached eventually.

---

Extracted Text

Journal of Artificial Intelligence Research 25 (2006) 315-348 Submitted 08/05;
published 03/06

Negotiating Socially Optimal Allocations of Resources Ulle Endriss ulle@illc.uva.nlILLC,
University of Amsterdam 1018 TV Amsterdam, The Netherlands Nicolas Maudet
maudet@lamsade.dauphine.frLAMSADE, Universit'e Paris-Dauphine

75775 Paris Cedex 16, France Fariba Sadri fs@doc.ic.ac.ukDepartment of Computing,
Imperial College London

London SW7 2AZ, UK Francesca Toni ft@doc.ic.ac.uk Department of Computing,
Imperial College London London SW7 2AZ, UK

Abstract A multiagent system may be thought of as an artificial society of
autonomous softwareagents and we can apply concepts borrowed from welfare
economics and social choice theory

to assess the social welfare of such an agent society. In this paper, we
study an abstractnegotiation framework where agents can agree on multilateral
deals to exchange bundles of indivisible resources. We then analyse how these
deals affect social welfare for differentinstances of the basic framework
and different interpretations of the concept of social welfare itself. In
particular, we show how certain classes of deals are both sufficient and
necessaryto guarantee that a socially optimal allocation of resources will
be reached eventually.

1. Introduction A multiagent system may be thought of as an artificial society
of autonomous software agents. Negotiation over the distribution of resources
(or tasks) amongst the agents inhabiting such a society is an important area
of research in artificial intelligence and computer science (Rosenschein
& Zlotkin, 1994; Kraus, 2001; Chavez, Moukas, & Maes, 1997; Sandholm, 1999).
A number of variants of this problem have been studied in the literature.
Here we consider the case of an artificial society of agents where, to begin
with, each agent holds a bundle of indivisible resources to which it assigns
a certain utility. Agents may then negotiate with each other in order to
agree on the redistribution of some of these resources to benefit either
themselves or the agent society they inhabit.

Rather than being concerned with specific strategies for negotiation, we
analyse how the redistribution of resources by means of negotiation affects
the well-being of the agent society as a whole. To this end, we make use
of formal tools for measuring social welfare developed in welfare economics
and social choice theory (Moulin, 1988; Arrow, Sen, & Suzumura, 2002). In
the multiagent systems literature, the utilitarian interpretation of the
concept of social welfare is usually taken for granted (Rosenschein & Zlotkin,
1994; Sandholm, 1999; Wooldridge, 2002), i.e. whatever increases the average
welfare of the agents inhabiting a society is taken to be beneficial for
society as well. This is not the case in welfare economics,

cfl2006 AI Access Foundation. All rights reserved.

Endriss, Maudet, Sadri, & Toni for instance, where different notions of social
welfare are being studied and compared with each other. Here, the concept
of egalitarian social welfare takes a particularly prominent role (Sen, 1970;
Rawls, 1971; Moulin, 1988; Arrow et al., 2002). In this model, social welfare
is tied to the individual welfare of the weakest member of society, which
facilitates the incorporation of a notion of fairness into the resource allocation
process. While the discussion of the respective advantages and drawbacks
of different notions of social welfare in the social sciences tends to be
dominated by ethical considerations,1 in the context of societies of artificial
software agents the choice of a suitable formal tool for modelling social
welfare boils down to a clear-cut (albeit not necessarily simple) technical
design decision (Endriss & Maudet, 2004). Indeed, different applications
may call for different social criteria. For instance, for the application
studied by Lema^itre, Verfaillie, and Bataille (1999), where agents need
to agree on the access to an earth observation satellite which has been funded
jointly by the owners of these agents, it is important that each one of them
receives a "fair" share of the common resource. Here, a society governed
by egalitarian principles may be the most appropriate. In an electronic commerce
application running on the Internet where agents have little or no commitments
towards each other, on the other hand, egalitarian principles seem of little
relevance. In such a scenario, utilitarian social welfare would provide an
appropriate reflection of the overall profit generated. Besides utilitarian
and egalitarian social welfare, we are also going to discuss notions such
as Pareto and Lorenz optimality (Moulin, 1988), as well as envy-freeness
(Brams & Taylor, 1996).

In this paper, we study the effect that negotiation over resources has on
society for a number of different interpretations of the concept of social
welfare. In particular, we show how certain classes of deals regarding the
exchange of resources allow us to guarantee that a socially optimal allocation
of resources will be reached eventually. These convergence results may be
interpreted as the emergence of a particular global behaviour (at the level
of society) in reaction to local behaviour governed by the negotiation strategies
of individual agents (which determine the kinds of deals agents are prepared
to accept). The work described here is complementary to the large body of
literature on mechanism design and game-theoretical models of negotiation
in multiagent systems (see e.g. Rosenschein & Zlotkin, 1994; Kraus, 2001;
Fatima, Wooldridge, & Jennings, 2004). While such work is typically concerned
with negotiation at the local level (how can we design mechanisms that provide
an incentive to individual agents to adopt a certain negotiation strategy?),
we address negotiation at a global level by analysing how the actions taken
by agents locally affect the overall system from a social point of view.

As we shall see, truly multilateral deals involving any number of agents
as well as any number of resources may be necessary to be able to negotiate
socially optimal allocations of resources. This is certainly true as long
as we use arbitrary utility functions to model the preferences of individual
agents. In some application domains, however, where utility functions may
be assumed to be subject to certain restrictions (such as being additive),
we are able to obtain stronger results and show that also structurally simpler
classes of deals (in particular, deals involving only a single resource at
a time) can be sufficient to negotiate socially optimal allocations. Nevertheless,
for other seemingly strong restrictions on agents'

1. A famous example is Rawls' veil of ignorance, a thought experiment designed
to establish what constitutes

a just society (Rawls, 1971).

316

Negotiating Socially Optimal Allocations of Resources utility functions (such
as the restriction to dichotomous preferences) we are able to show that no
reduction in the structural complexity of negotiation is possible.

Our approach to multiagent resource allocation is of a distributed nature.
In general, the allocation procedure used to find a suitable allocation of
resources could be either centralised or distributed. In the centralised
case, a single entity decides on the final allocation of resources amongst
agents, possibly after having elicited the agents' preferences over alternative
allocations. Typical examples are combinatorial auctions (Cramton, Shoham,
& Steinberg, 2006). Here the central entity is the auctioneer and the reporting
of preferences takes the form of bidding. In truly distributed approaches,
on the other hand, allocations emerge as the result of a sequence of local
negotiation steps. Both approaches have their advantages and disadvantages.
Possibly the most important argument in favour of auctionbased mechanisms
concerns the simplicity of the communication protocols required to implement
such mechanisms. Another reason for the popularity of centralised mechanisms
is the recent push in the design of powerful algorithms for combinatorial
auctions that, for the first time, perform reasonably well in practice (Fujishima,
Leyton-Brown, & Shoham, 1999; Sandholm, 2002). Of course, such techniques
are, in principle, also applicable in the distributed case, but research
in this area has not yet reached the same level of maturity as for combinatorial
auctions. An important argument against centralised approaches is that it
may be difficult to find an agent that could assume the role of an "auctioneer"
(for instance, in view of its computational capabilities or in view of its
trustworthiness).

The line of research pursued in this paper has been inspired by Sandholm's
work on sufficient and necessary contract (i.e. deal) types for distributed
task allocation (Sandholm, 1998). Since then, it has been further developed
by the present authors, their colleagues, and others in the context of resource
allocation problems (Bouveret & Lang, 2005; Chevaleyre, Endriss, Estivie,
& Maudet, 2004; Chevaleyre, Endriss, Lang, & Maudet, 2005a; Chevaleyre, Endriss,
& Maudet, 2005b; Dunne, 2005; Dunne, Laurence, & Wooldridge, 2004; Dunne,
Wooldridge, & Laurence, 2005; Endriss & Maudet, 2004, 2005; Endriss, Maudet,
Sadri, & Toni, 2003a, 2003b). In particular, we have extended Sandholm's
framework by also addressing negotiation systems without compensatory side
payments (Endriss et al., 2003a), as well as agent societies where the concept
of social welfare is given a different interpretation to that in the utilitarian
programme (Endriss et al., 2003b; Endriss & Maudet, 2004). The present paper
provides a comprehensive overview of the most fundamental results, mostly
on the convergence to an optimal allocation with respect to different notions
of social welfare, in a very active and timely area of ongoing research.

The remainder of this paper is organised as follows. Section 2 introduces
the basic negotiation framework for resource reallocation we are going to
consider. It gives definitions for the central notions of allocation, deal,
and utility, and it discusses possible restrictions to the class of admissible
deals (both structural and in terms of acceptability to individual agents).
Section 2 also introduces the various concepts of a social preference we
are going to consider in this paper. Subsequent sections analyse specific
instances of the basic negotiation framework (characterised, in particular,
by different criteria for the acceptability of a proposed deal) with respect
to specific notions of social welfare. In the first instance, agents are
assumed to be rational (and "myopic") in the sense of never accepting a deal
that would result in a negative payoff. Section 3 analyses the first variant
of this model of rational negotiation, which allows for monetary side payments
to increase the range of

317

Endriss, Maudet, Sadri, & Toni acceptable deals. As we shall see, this model
facilitates negotiation processes that maximise utilitarian social welfare.
If side payments are not possible, we cannot guarantee outcomes with maximal
social welfare, but it is still possible to negotiate Pareto optimal allocations.
This variant of the rational model is studied in Section 4. Both Section
3 and 4 also investigate how restrictions to the range of utility functions
agents may use to model their preferences can affect such convergence results.

In the second part of the paper we apply our methodology to agent societies
where the concept of social welfare is given a different kind of interpretation
than is commonly the case in the multiagent systems literature. Firstly,
in Section 5 we analyse our framework of resource allocation by negotiation
in the context of egalitarian agent societies. Then Section 6 discusses a
variant of the framework that combines ideas from both the utilitarian and
the egalitarian programme and enables agents to negotiate Lorenz optimal
allocations of resources. Finally, Section 7 introduces the idea of using
an elitist model of social welfare for applications where societies of agents
are merely a means of enabling at least one agent to achieve their goal.
This section also reviews the concept of envy-freeness and discusses ways
of measuring different degrees of envy.

Section 8 summarises our results and concludes with a brief discussion of
the concept of welfare engineering, i.e. with the idea of choosing tailor-made
definitions of social welfare for different applications and designing agents'
behaviour profiles accordingly.

2. Preliminaries The basic scenario of resource allocation by negotiation
studied in this paper is that of an artificial society inhabited by a number
of agents, each of which initially holds a certain number of resources. These
agents will typically ascribe different values (utilities) to different bundles
of resources. They may then engage in negotiation and agree on the reallocation
of some of the resources, for example, in order to improve their respective
individual welfare (i.e. to increase their utility). Furthermore, we assume
that it is in the interest of the system designer that these distributed
negotiation processes --somehow-- also result in a positive payoff for society
as a whole.

2.1 Basic Definitions An instance of our abstract negotiation framework consists
of a finite set of (at least two) agents A and a finite set of resources
R. Resources are indivisible and non-sharable. An allocation of resources
is a partitioning of R amongst the agents in A.

Definition 1 (Allocations) An allocation of resources is a function A from
A to subsets of R such that A(i) " A(j) = { } for i 6= j and Si2A A(i) =
R.

For example, given an allocation A with A(i) = {r3, r7}, agent i would own
resources r3 and r7. Given a particular allocation of resources, agents may
agree on a (multilateral) deal to exchange some of the resources they currently
hold. In the most general case, any numbers of agents and resources could
be involved in a single deal. From an abstract point of view, a deal takes
us from one allocation of resources to the next. That is, we may characterise
a deal as a pair of allocations.

318

Negotiating Socially Optimal Allocations of Resources Definition 2 (Deals)
A deal is a pair ffi = (A, A0) where A and A0 are allocations of resources
with A 6= A0.

The set of agents involved in a deal ffi = (A, A0) is given by Affi = {i
2 A | A(i) 6= A0(i)}. The composition of two deals is defined as follows:
If ffi1 = (A, A0) and ffi2 = (A0, A00), then ffi1 ffi ffi2 = (A, A00). If
a given deal is the composition of two deals that concern disjoint sets of
agents, then that deal is said to be independently decomposable.

Definition 3 (Independently decomposable deals) A deal ffi is called independently
decomposable iff there exist deals ffi1 and ffi2 such that ffi = ffi1 ffi
ffi2 and Affi1 " Affi2 = { }.

Observe that if ffi = (A, A0) is independently decomposable then there exists
an intermediate allocation B different from both A and A0 such that the intersection
of {i 2 A | A(i) 6= B(i)} and {i 2 A | B(i) 6= A0(i)} is empty, i.e. such
that the union of {i 2 A | A(i) = B(i)} and{

i 2 A | B(i) = A0(i)} is the full set of agents A. Hence, ffi = (A, A0) not
being independently decomposable implies that there exists no allocation
B different from both A and A0 such that either B(i) = A(i) or B(i) = A0(i)
for all agents i 2 A (we are going to use this fact in the proofs of our
"necessity theorems" later on).

The value an agent i 2 A ascribes to a particular set of resources R will
be modelled by means of a utility function, that is, a function from sets
of resources to real numbers. We are going to consider both general utility
functions (without any restrictions) and several more specific classes of
functions.

Definition 4 (Utility functions) Every agent i 2 A is equipped with a utility
function ui : 2R ! R. We are going to consider the following restricted classes
of utility functions:

* ui is non-negative iff ui(R) >= 0 for all R ` R.

* ui is positive iff it is non-negative and ui(R) 6= 0 for all R ` R with
R 6= { }.

* ui is monotonic iff R1 ` R2 implies ui(R1) <= ui(R2) for all R1, R2 ` R.

* ui is additive iff ui(R) = Pr2R ui({r}) for all R ` R.

* ui is a 0-1 function iff it is additive and ui({r}) = 0 or ui({r}) = 1
for all r 2 R.

* ui is dichotomous iff ui(R) = 0 or ui(R) = 1 for all R ` R. Recall that,
given an allocation A, the set A(i) is the bundle of resources held by agent
i in that situation. We are usually going to abbreviate ui(A) = ui(A(i))
for the utility value assigned by agent i to that bundle.

2.2 Deal Types and Rationality Criteria In this paper we investigate what
kinds of negotiation outcomes agents can achieve by using different classes
of deals. A class of deals may be characterised by both structural constraints
(number of agents and resources involved, etc.) and rationality constraints
(relating to the changes in utility experienced by the agents involved).

Following Sandholm (1998), we can distinguish a number of structurally different
types of deals. The most basic are 1-deals, where a single item is passed
from one agent to another.

319

Endriss, Maudet, Sadri, & Toni Definition 5 (1-deals) A 1-deal is a deal
involving the reallocation of exactly one resource. This corresponds to the
"classical" form of a contract typically found in the Contract Net protocol
(Smith, 1980). Deals where one agent passes a set of resources on to another
agent are called cluster deals. Deals where one agent gives a single item
to another agent who returns another single item are called swap deals. Sometimes
it can also be necessary to exchange resources between more than just two
agents. In Sandholm's terminology, a multiagent deal is a deal that could
involve any number of agents, where each agent passes at most one resource
to each of the other agents taking part. Finally, deals that combine the
features of the cluster and the multiagent deal type are called combined
deals by Sandholm. These could involve any number of agents and any number
of resources. Therefore, every deal ffi, in the sense of Definition 2, is
a combined deal. In the remainder of this paper, when speaking about deals
without further specifying their type, we are always going to refer to combined
deals (without any structural restrictions).2

An agent may or may not find a particular deal ffi acceptable. Whether or
not an agent will accept a given deal depends on the rationality criterion
it applies when evaluating deals. A selfish agent i may, for instance, only
accept deals ffi = (A, A0) that strictly improve its personal welfare: ui(A)
< ui(A0). We call criteria such as this, which only depend on the utilities
of the agent in question, personal rationality criteria. While we do not
want to admit arbitrary rationality criteria, the classes of deals that can
be characterised using personal rationality criteria alone is somewhat too
narrow for our purposes. Instead, we are going to consider rationality criteria
that are local in the sense of only depending on the utility levels of the
agents involved in the deal concerned.

Definition 6 (Local rationality criteria) A class Delta  of deals is said
to be characterised by a local rationality criterion iff it is possible to
define a predicate Phi  over 2A*R*R such that a deal ffi = (A, A0) belongs
to Delta  iff Phi ({(i, ui(A), ui(A0)) | i 2 Affi}) holds true.

That is, Phi  is mapping a set of triples of one agent name and two reals
(utilities) each to truth values. The locality aspect comes in by only applying
Phi  to the set of triples for those agents whose bundle changes with ffi.
Therefore, for instance, the class of all deals that increase the utility
of the previously poorest agent is not characterisable by a local rationality
criterion (because this condition can only be checked by inspecting the utilities
of all the agents in the system).

2.3 Socially Optimal Allocations of Resources As already mentioned in the
introduction, we may think of a multiagent system as a society of autonomous
software agents. While agents make their local decisions on what deals to
propose and to accept, we can also analyse the system from a global or societal
point of view and may thus prefer certain allocations of resources over others.
To this end, welfare economics provides formal tools to assess how the distribution
of resources amongst the members of a society affects the well-being of society
as a whole (Sen, 1970; Moulin, 1988; Arrow et al., 2002).

2. The ontology of deal types discussed here is, of course, not exhaustive.
It would, for instance, also be of

interest to consider the class of bilateral deals (involving exactly two
agents but any number of items).

320

Negotiating Socially Optimal Allocations of Resources Given the preference
profiles of the individual agents in a society (which, in our framework,
are represented by means of their utility functions), a social welfare ordering
over alternative allocations of resources formalises the notion of a society's
preferences. Next we are going to formally introduce the most important social
welfare orderings considered in this paper (some additional concepts of social
welfare are discussed towards the end of the paper). In some cases, social
welfare is best defined in terms of a collective utility function. One such
example is the notion of utilitarian social welfare.

Definition 7 (Utilitarian social welfare) The utilitarian social welfare
swu(A) of an allocation of resources A is defined as follows:

swu(A) = X

i2A

ui(A)

Observe that maximising the collective utility function swu amounts to maximising
the average utility enjoyed by the agents in the system. Asking for maximal
utilitarian social welfare is a very strong requirement. A somewhat weaker
concept is that of Pareto optimality. An allocation is Pareto optimal iff
there is no other allocation with higher utilitarian social welfare that
would be no worse for any of of the agents in the system (i.e. that would
be strictly better for at least one agent without being worse for any of
the others).

Definition 8 (Pareto optimality) An allocation A is called Pareto optimal
iff there is no allocation A0 such that swu(A) < swu(A0) and ui(A) <= ui(A0)
for all i 2 A.

The first goal of an egalitarian society should be to increase the welfare
of its weakest member (Rawls, 1971; Sen, 1970). In other words, we can measure
the social welfare of such a society by measuring the welfare of the agent
that is currently worst off.

Definition 9 (Egalitarian social welfare) The egalitarian social welfare
swe(A) of an allocation of resources A is defined as follows:

swe(A) = min{ui(A) | i 2 A} The egalitarian collective utility function swe
gives rise to a social welfare ordering over alternative allocations of resources:
A0 is strictly preferred over A iff swe(A) < swe(A0). This ordering is sometimes
called the maximin-ordering. The maximin-ordering only takes into account
the welfare of the currently weakest agent, but is insensitive to utility
fluctuations in the rest of society. To allow for a finer distinction of
the social welfare of different allocations we introduce the so-called leximin-ordering.

For a society with n agents, let {u1, . . . , un} be the set of utility functions
for that society. Then every allocation A determines a utility vector hu1(A),
. . . , un(A)i of length n. If we rearrange the elements of that vector in
increasing order we obtain the ordered utility vector for allocation A, which
we are going to denote by ~u(A). The number ~ui(A) is the ith element in
such a vector (for 1 <= i <= |A|). That is, ~u1(A) for instance, is the utility
value assigned to allocation A by the currently weakest agent. We now declare
a lexicographic ordering over vectors of real numbers (such as ~u(A)) in
the usual way: ~x lexicographically precedes ~y iff ~x is a (proper) prefix
of ~y or ~x and ~y share a common (proper) prefix of length k (which may
be 0) and we have ~xk+1 < ~yk+1.

321

Endriss, Maudet, Sadri, & Toni Definition 10 (Leximin-ordering) The leximin-ordering
OE over alternative allocations of resources is defined as follows:

A OE A0 iff ~u(A) lexicographically precedes ~u(A0) We write A _ A0 iff either
A OE A0 or ~u(A) = ~u(A0). An allocation of resources A is called leximin-maximal
iff there is no other allocation A0 such that A OE A0.

Finally, we introduce the concept of Lorenz domination, a social welfare
ordering that combines utilitarian and egalitarian aspects of social welfare.
The basic idea is to endorse deals that result in an improvement with respect
to utilitarian welfare without causing a loss in egalitarian welfare, and
vice versa.

Definition 11 (Lorenz domination) Let A and A0 be allocations for a society
with n agents. Then A is Lorenz dominated by A0 iff

kX

i=1

~ui(A) <=

kX

i=1

~ui(A0)

for all k with 1 <= k <= n and, furthermore, that inequality is strict for
at least one k. For any k with 1 <= k <= n, the sum referred to in the above
definition is the sum of the utility values assigned to the respective allocation
of resources by the k weakest agents. For k = 1, this sum is equivalent to
the egalitarian social welfare for that allocation. For k = n, it is equivalent
to the utilitarian social welfare. An allocation of resources is called Lorenz
optimal iff it is not Lorenz dominated by any other allocation.

We illustrate some of the above social welfare concepts (and the use of ordered
utility vectors) by means of an example. Consider a society with three agents
and two resources, with the agents' utility functions given by the following
table:

u1({ }) = 0 u2({ }) = 0 u3({ }) = 0 u1({r1}) = 5 u2({r1}) = 4 u3({r1}) =
2 u1({r2}) = 3 u2({r2}) = 2 u3({r2}) = 6 u1({r1, r2}) = 8 u2({r1, r2}) =
17 u3({r1, r2}) = 7

First of all, we observe that the egalitarian social welfare will be 0 for
any possible allocation in this scenario, because at least one of the agents
would not get any resources at all. Let A be the allocation where agent 2
holds the full bundle of resources. Observe that this is the allocation with
maximal utilitarian social welfare. The corresponding utility vector ish

0, 17, 0i, i.e. ~u(A) = h0, 0, 17i. Furthermore, let A0 be the allocation
where agent 1 gets r1, agent 2 gets r2, and agent 3 has to be content with
the empty bundle. Now we get an ordered utility vector of h0, 2, 5i. The
initial element in either vector is 0, but 0 < 2, i.e. ~u(A) lexicographically
precedes ~u(A0). Hence, we get A OE A0, i.e. A0 would be the socially

preferred allocation with respect to the leximin-ordering. Furthermore, both
A and A0 are Pareto optimal and neither is Lorenz-dominated by the other.
Starting from allocation A0, agents 1 and 2 swapping their respective bundles
would result in an allocation with the ordered utility vector h0, 3, 4i,
i.e. this move would result in a Lorenz improvement.

322

Negotiating Socially Optimal Allocations of Resources 3. Rational Negotiation
with Side Payments In this section, we are going to discuss a first instance
of the general framework of resource allocation by negotiation set out earlier.
This particular variant, which we shall refer to as the model of rational
negotiation with side payments (or simply with money), is equivalent to a
framework put forward by Sandholm where agents negotiate in order to reallocate
tasks (Sandholm, 1998). For this variant of the framework, our aim will be
to negotiate allocations with maximal utilitarian social welfare.

3.1 Individual Rationality In this instance of our negotiation framework,
a deal may be accompanied by a number of monetary side payments to compensate
some of the agents involved for accepting a loss in utility. Rather than
specifying for each pair of agents how much money the former is supposed
to pay to the latter, we simply say how much money each agent either pays
out or receives. This can be modelled by using what we call a payment function.

Definition 12 (Payment functions) A payment function is a function p from
A to real numbers satisfying the following condition:X

i2A

p(i) = 0

Here, p(i) > 0 means that agent i pays the amount of p(i), while p(i) < 0
means that it receives the amount of -p(i). By definition of a payment function,
the sum of all payments is 0, i.e. the overall amount of money present in
the system does not change.3

In the rational negotiation model, agents are self-interested in the sense
of only proposing or accepting deals that strictly increase their own welfare
(for a justification of this approach we refer to Sandholm, 1998). This "myopic"
notion of individual rationality may be formalised as follows.

Definition 13 (Individual rationality) A deal ffi = (A, A0) is called individually
rational iff there exists a payment function p such that ui(A0) - ui(A) >
p(i) for all i 2 A, except possibly p(i) = 0 for agents i with A(i) = A0(i).

That is, agent i will be prepared to accept the deal ffi iff it has to pay
less than its gain in utility or it will get paid more than its loss in utility,
respectively. Only for agents i not affected by the deal, i.e. in case A(i)
= A0(i), there may be no payment at all. For example, if ui(A) = 8 and ui(A0)
= 5, then the utility of agent i would be reduced by 3 units if it were to
accept the deal ffi = (A, A0). Agent i will only agree to this deal if it
is accompanied by a side payment of more than 3 units; that is, if the payment
function p satisfies -3 > p(i).

For any given deal, there will usually be a range of possible side payments.
How agents manage to agree on a particular one is not a matter of consideration
at the abstract level at which we are discussing this framework here. We
assume that a deal will go ahead as long as there exists some suitable payment
function p. We should point out that this

3. As the overall amount of money present in the system stays constant throughout
the negotiation process,

it makes sense not to take it into account for the evaluation of social welfare.

323

Endriss, Maudet, Sadri, & Toni assumption may not be justified under all
circumstances. For instance, if utility functions are not publicly known
and agents are risk-takers, then a potential deal may not be identified as
such, because some of the agents may understate their interest in that deal
in order to maximise their expected payoff (Myerson & Satterthwaite, 1983).
Therefore, the theoretical results on the reachability of socially optimal
allocations reported below will only apply under the assumption that such
strategic considerations will not prevent agents from making mutually beneficial
deals.

3.2 An Example As an example, consider a system with two agents, agent 1
and agent 2, and a set of two resources R = {r1, r2}. The following table
specifies the values of the utility functions u1 and u2 for every subset
of {r1, r2}:

u1({ }) = 0 u2({ }) = 0 u1({r1}) = 2 u2({r1}) = 3 u1({r2}) = 3 u2({r2}) =
3 u1({r1, r2}) = 7 u2({r1, r2}) = 8

Also suppose agent 1 initially holds the full set of resources {r1, r2} and
agent 2 does not own any resources to begin with.

The utilitarian social welfare for this initial allocation is 7, but it could
be 8, namely if agent 2 had both resources. As we are going to see next,
the simple class of 1-deals alone are not always sufficient to guarantee
the optimal outcome of a negotiation process (if agents abide to the individual
rationality criterion for the acceptability of a deal). In our example, the
only possible 1-deals would be to pass either r1 or r2 from agent 1 to agent
2. In either case, the loss in utility incurred by agent 1 (5 or 4, respectively)
would outweigh the gain of agent 2 (3 for either deal), so there is no payment
function that would make these deals individually rational. The cluster deal
of passing {r1, r2} from agent 1 to 2, on the other hand, would be individually
rational if agent 2 paid agent 1 an amount of, say, 7.5 units.

Similarly to the example above, we can also construct scenarios where swap
deals or multiagent deals are necessary (i.e. where cluster deals alone would
not be sufficient to guarantee maximal social welfare). This also follows
from Theorem 2, which we are going to present later on in this section. Several
concrete examples are given by Sandholm (1998).

3.3 Linking Individual Rationality and Social Welfare The following result,
first stated in this form by Endriss et al. (2003a), says that a deal (with
money) is individually rational iff it increases utilitarian social welfare.
We are mainly going to use this lemma to give a simple proof of Sandholm's
main result on sufficient contract types (Sandholm, 1998), but it has also
found useful applications in its own right (Dunne et al., 2005; Dunne, 2005;
Endriss & Maudet, 2005).

Lemma 1 (Individually rational deals and utilitarian social welfare) A deal
ffi = (A, A0) is individually rational iff swu(A) < swu(A0).

324

Negotiating Socially Optimal Allocations of Resources Proof. `)': By definition,
ffi = (A, A0) is individually rational iff there exists a payment function
p such that ui(A0) - ui(A) > p(i) holds for all i 2 A, except possibly p(i)
= 0 in case A(i) = A0(i). If we add up the inequations for all agents i 2
A we get:X

i2A(

ui(A0) - ui(A)) > X

i2A

p(i)

By definition of a payment function, the righthand side equates to 0 while,
by definition of utilitarian social welfare, the lefthand side equals swu(A0)
- swu(A). Hence, we really get swu(A) < swu(A0) as claimed.

`(': Now let swu(A) < swu(A0). We have to show that ffi = (A, A0) is an individually
rational deal. We are done if we can prove that there exists a payment function
p such that ui(A0) - ui(A) > p(i) for all i 2 A. We define the function p
: A ! R as follows:

p(i) = ui(A0) - ui(A) - swu(A0) - swu(A)|A| (for i 2 A) First, observe that
p really is a payment function, because we get Pi2A p(i) = 0. We also get
ui(A0) - ui(A) > p(i) for all i 2 A, because we have swu(A0) - swu(A0) >
0. Hence, ffi must indeed be an individually rational deal. 2

Lemma 1 suggests that the function swu does indeed provide an appropriate
measure of social well-being in societies of agents that use the notion of
individual rationality (as given by Definition 13) to guide their behaviour
during negotiation. It also shows that individual rationality is indeed a
local rationality criterion in the sense of Definition 6.

3.4 Maximising Utilitarian Social Welfare Our next aim is to show that any
sequence of deals in the rational negotiation model with side payments will
converge to an allocation with maximal utilitarian social welfare; that is,
the class of individually rational deals (as given by Definition 13) is sufficient
to guarantee optimal outcomes for agent societies measuring welfare according
to the utilitarian programme (Definition 7). This has originally been shown
by Sandholm (1998) in the context of a framework where rational agents negotiate
in order to reallocate tasks and where the global aim is to minimise the
overall costs of carrying out these tasks.

Theorem 1 (Maximal utilitarian social welfare) Any sequence of individually
rational deals will eventually result in an allocation with maximal utilitarian
social welfare.

Proof. Given that both the set of agents A as well as the set of resources
R are required to be finite, there can be only a finite number of distinct
allocations of resources. Furthermore, by Lemma 1, any individually rational
deal will strictly increase utilitarian social welfare. Hence, negotiation
must terminate after a finite number of deals. For the sake of contradiction,
assume that the terminal allocation A does not have maximal utilitarian social
welfare, i.e. there exists another allocation A0 with swu(A) < swu(A0). But
then, by Lemma 1, the deal ffi = (A, A0) would be individually rational and
thereby possible, which contradicts our earlier assumption of A being a terminal
allocation. 2

325

Endriss, Maudet, Sadri, & Toni At first sight, this result may seem almost
trivial. The notion of a multilateral deal without any structural restrictions
is a very powerful one. A single such deal allows for any number of resources
to be moved between any number of agents. From this point of view, it is
not particularly surprising that we can always reach an optimal allocation
(even in just a single step!). Furthermore, finding a suitable deal is a
very complex task, which may not always be viable in practice. The crucial
point of Theorem 1 is that any sequence of deals will result in an optimal
allocation. That is, whatever deals are agreed on in the early stages of
negotiation, the system will never get stuck in a local optimum and finding
an allocation with maximal social welfare remains an option throughout (provided,
of course, that agents are actually able to identify any deal that is theoretically
possible). Given the restriction to deals that are individually rational
for all the agents involved, social welfare must increase with every single
deal. Therefore, negotiation always pays off, even if it has to stop early
due to computational limitations.

The issue of complexity is still an important one. If the full range of deals
is too large to be managed in practice, it is important to investigate how
close we can get to finding an optimal allocation if we restrict the set
of allowed deals to certain simple patterns. Andersson and Sandholm (2000),
for instance, have conducted a number of experiments on the sequencing of
certain contract/deal types to reach the best possible allocations within
a limited amount of time. For a complexity-theoretic analysis of the problem
of deciding whether it is possible to reach an optimal allocation by means
of structurally simple types of deals (in particular 1-deals), we refer to
recent work by Dunne et al. (2005).

3.5 Necessary Deals The next theorem improves upon Sandholm's main result
regarding necessary contract types (Sandholm, 1998), by extending it to the
cases where either all utility functions are monotonic or all utility functions
are dichotomous.4 Sandholm's original result, translated into our terminology,
states that for any system (consisting of a set of agents A and a set of
resources R) and any (not independently decomposable) deal ffi for that system,
it is possible to construct utility functions and choose an initial allocation
of resources such that ffi is necessary to reach an optimal allocation, if
agents only agree to individually rational deals. All other findings on the
insufficiency of certain types of contracts reported by Sandholm (1998) may
be considered corollaries to this. For instance, the fact that, say, cluster
deals alone are not sufficient to guarantee optimal outcomes follows from
this theorem if we take ffi to be any particular swap deal for the system
in question.

Theorem 2 (Necessary deals with side payments) Let the sets of agents and
resources be fixed. Then for every deal ffi that is not independently decomposable,
there exist utility functions and an initial allocation such that any sequence
of individually rational deals leading to an allocation with maximal utilitarian
social welfare must include ffi. This continues to be the case even when
either all utility functions are required to be monotonic or all utility
functions are required to be dichotomous.

4. In fact, our theorem not only sharpens but also also corrects a mistake
in previous expositions of this

result (Sandholm, 1998; Endriss et al., 2003a), where the restriction to
deals that are not independently decomposable had been omitted.

326

Negotiating Socially Optimal Allocations of Resources Proof. Given a set
of agents A and a set of resources R, let ffi = (A, A0) with A 6= A0 be any
deal for this system. We need to show that there are a collection of utility
functions and an initial allocation such that ffi is necessary to reach an
allocation with maximal social welfare. This would be the case if A0 had
maximal social welfare, A had the second highest social welfare, and A were
the initial allocation of resources.

We first prove the existence of such a collection of functions for the case
where all utility functions are required to be monotonic. Fix ffl such that
0 < ffl < 1. As we have A 6= A0, there must be an agent j 2 A such that A(j)
6= A0(j). We now define utility functions ui for agents i 2 A and sets of
resources R ` R as follows:

ui(R) = ae |R| + ffl if R = A0(i) or (R = A(i) and i 6= j)|R| otherwise Observe
that ui is a monotonic utility function for every i 2 A. We get swu(A0) =
|R|+ffl*|A| and swu(A) = swu(A0) - ffl. Because ffi = (A, A0) is not individually
decomposable, there exists no allocation B different from both A and A0 such
that either B(i) = A(i) or B(i) = A0(i) for all agents i 2 A. Hence, swu(B)
<= swu(A) for any other allocation B. That is, A0 is the (unique) allocation
with maximal social welfare and the only allocation with higher social welfare
than A. Therefore, if we were to make A the initial allocation then ffi =
(A, A0) would be the only deal increasing social welfare. By Lemma 1, this
means that ffi would be the only individually rational (and thereby the only
possible) deal. Hence, ffi is indeed necessary to achieve maximal utilitarian
social welfare.

The proof for the case of dichotomous utility functions is very similar;
we only need to show that a suitable collection of dichotomous utility functions
can be constructed. Again, let j be an agent with A(j) 6= A0(j). We can use
the following collection of functions:

ui(R) = ae 1 if R = A0(i) or (R = A(i) and i 6= j)0 otherwise We get swu(A0)
= |A|, swu(A) = swu(A0)-1 and swu(B) <= swu(A) for all other allocations
B. Hence, A is not socially optimal and, with A as the initial allocation,
ffi would be the only deal that is individually rational. 2

We should stress that the set of deals that are not independently decomposable
includes deals involving any number of agents and/or any number of resources.
Hence, by Theorem 2, any negotiation protocol that puts restrictions on the
structural complexity of deals that may be proposed will fail to guarantee
optimal outcomes, even when there are no constraints on either time or computational
resources. This emphasises the high complexity of our negotiation framework
(see also Dunne et al., 2005; Chevaleyre et al., 2004; Endriss & Maudet,
2005; Dunne, 2005). The fact that the necessity of (almost) the full range
of deals persists, even when all utility functions are subject to certain
restrictions makes this result even more striking. This is true in particular
for the case of dichotomous functions, which are in some sense the simplest
class of utility functions (as they can only distinguish between "good" and
"bad" bundles).

To see that the restriction to deals that are not independently decomposable
matters, consider a scenario with four agents and two resources. If the deal
ffi of moving r1 from agent 1 to agent 2, and r2 from agent 3 to agent 4
is individually rational, then so will be

327

Endriss, Maudet, Sadri, & Toni either one of the two "subdeals" of moving
either r1 from agent 1 to agent 2 or r2 from agent 3 to agent 4. Hence, the
deal ffi (which is independently decomposable) cannot be necessary in the
sense of Theorem 2 (with reference to our proof above, in the case of ffi
there are allocations B such that either B(i) = A(i) or B(i) = A0(i) for
all agents i 2 A, i.e. we could get swu(B) = swu(A0)).

3.6 Additive Scenarios Theorem 2 is a negative result, because it shows that
deals of any complexity may be required to guarantee optimal outcomes of
negotiation. This is partly a consequence of the high degree of generality
of our framework. In Section 2.1, we have defined utility functions as arbitrary
functions from sets of resources to real numbers. For many application domains
this may be unnecessarily general or even inappropriate and we may be able
to obtain stronger results for specific classes of utility functions that
are subject to certain restrictions. Of course, we have already seen that
this is not the case for either monotonicity (possibly the most natural restriction)
or dichotomy (possibly the most severe restriction).

Here, we are going to consider the case of additive utility functions, which
are appropriate for domains where combining resources does not result in
any synergy effects (in the sense of increasing an agent's welfare). We refer
to systems where all agents have additive utility functions as additive scenarios.
The following theorem shows that for these additive scenarios 1-deals are
sufficient to guarantee outcomes with maximal social welfare.5

Theorem 3 (Additive scenarios) In additive scenarios, any sequence of individually
rational 1-deals will eventually result in an allocation with maximal utilitarian
social welfare.

Proof. Termination is shown as for Theorem 1. We are going to show that,
whenever the current allocation does not have maximal social welfare, then
there is still a possible 1-deal that is individually rational.

In additive domains, the utilitarian social welfare of a given allocation
may be computed by adding up the appropriate utility values for all the single
resources in R. For any allocation A, let fA be the function mapping each
resource r 2 R to the agent i 2 A that holds r in situation A (that is, we
have fA(r) = i iff r 2 A(i)). The utilitarian social welfare for allocation
A is then given by the following formula:

swu(A) = X

r2R

ufA(r)({r})

Now suppose that negotiation has terminated with allocation A and there are
no more individually rational 1-deals possible. Furthermore, for the sake
of contradiction, assume that A is not an allocation with maximal social
welfare, i.e. there exists another allocation A0 with swu(A) < swu(A0). But
then, by the above characterisation of social welfare for additive scenarios,
there must be at least one resource r 2 R such that ufA(r)({r}) < ufA0(r)({r}).
That is, the 1-deal ffi of passing r from agent fA(r) on to agent fA0(r)
would increase social welfare. Therefore, by Lemma 1, ffi must be an individually
rational deal, i.e. contrary to our earlier assumption, A cannot be a terminal
allocation. Hence, A must be an allocation with maximal utilitarian social
welfare. 2

5. This has also been observed by T. Sandholm (personal communication, September
2002).

328

Negotiating Socially Optimal Allocations of Resources We conclude this section
by briefly mentioning two recent results that both extend, in different ways,
the result stated in Theorem 3 (a detailed discussion, however, would be
beyond the scope of the present paper). The first of these results shows
that rational deals involving at most k resources each are sufficient for
convergence to an allocation with maximal social welfare whenever all utility
functions are additively separable with respect to a common partition of
R --i.e. synergies across different parts of the partition are not possible
and overall utility is defined as the sum of utilities for the different
sets in the partition (Fishburn, 1970)-- and each set in this partition has
at most k elements (Chevaleyre et al., 2005a).

The second result concerns a maximality property of utility functions with
respect to 1-deals. Chevaleyre et al. (2005b) show that the class of modular
utility functions, which is only slightly more general than the class of
additive functions considered here (namely, it is possible to assign a non-zero
utility to the empty bundle), is maximal in the sense that for no class of
functions strictly including the class of modular functions it would still
be possible to guarantee that agents using utility functions from that larger
class and negotiating only individually rational 1-deals will eventually
reach an allocation with maximal utilitarian social welfare in all cases.

4. Rational Negotiation without Side Payments An implicit assumption made
in the framework that we have presented so far is that every agent has got
an unlimited amount of money available to it to be able to pay other agents
whenever this is required for a deal that would increase utilitarian social
welfare. Concretely, if A is the initial allocation and A0 is the allocation
with maximal utilitarian social welfare, then agent i may require an amount
of money just below the difference ui(A0) - ui(A) to be able to get through
the negotiation process. In the context of task contracting, for which this
framework has been proposed originally (Sandholm, 1998), this may be justifiable,
but for resource allocation problems it seems questionable to make assumptions
about the unlimited availability of one particular resource, namely money.
In this section, we therefore investigate to what extent the theoretical
results discussed in the previous section persist to apply when we consider
negotiation processes without monetary side payments.

4.1 An Example In a scenario without money, that is, if we do not allow for
compensatory payments, we cannot always guarantee an outcome with maximal
utilitarian social welfare. To see this, consider the following simple problem
for a system with two agents, agent 1 and agent 2, and a single resource
r. The agents' utility functions are defined as follows:

u1({ }) = 0 u2({ }) = 0 u1({r}) = 4 u2({r}) = 7

Now suppose agent 1 initially owns the resource. Then passing r from agent
1 to agent 2 would increase utilitarian social welfare by an amount of 3.
For the framework with money, agent 2 could pay agent 1, say, the amount
of 5.5 units and the deal would be individually rational for both of them.
Without money (i.e. if p j 0), however, no individually rational deal is
possible and negotiation must terminate with a non-optimal allocation.

329

Endriss, Maudet, Sadri, & Toni As maximising social welfare is not generally
possible, instead we are going to investigate whether a Pareto optimal outcome
(see Definition 8) is possible in the framework without money, and what types
of deals are sufficient to guarantee this.

4.2 Cooperative Rationality As will become clear in due course, in order
to get the desired convergence result, we need to relax the notion of individual
rationality a little. For the framework without money, we also want agents
to agree to a deal, if this at least maintains their utility (that is, no
strict increase is necessary). However, we are still going to require at
least one agent to strictly increase their utility. This could, for instance,
be the agent proposing the deal in question. We call deals conforming to
this criterion cooperatively rational.6

Definition 14 (Cooperative rationality) A deal ffi = (A, A0) is called cooperatively
rational iff ui(A) <= ui(A0) for all i 2 A and there is an agent j 2 A such
that uj(A) < uj(A0).

In analogy to Lemma 1, we still have swu(A) < swu(A0) for any deal ffi =
(A, A0) that is cooperatively rational, but not vice versa. We call the instance
of our negotiation framework where all deals are cooperatively rational (and
hence do not include a monetary component) the model of rational negotiation
without side payments.

4.3 Ensuring Pareto Optimal Outcomes As the next theorem will show, the class
of cooperatively rational deals is sufficient to guarantee a Pareto optimal
outcome of money-free negotiation. It constitutes the analogue to Theorem
1 for the model of rational negotiation without side payments.

Theorem 4 (Pareto optimal outcomes) Any sequence of cooperatively rational
deals will eventually result in a Pareto optimal allocation of resources.

Proof. Every cooperatively rational deal strictly increases utilitarian social
welfare (this is where we need the condition that at least one agent behaves
truly individually rational for each deal). Together with the fact that there
are only finitely many different allocations of resources, this implies that
any negotiation process will eventually terminate. For the sake of contradiction,
assume negotiation ends with allocation A, but A is not Pareto optimal. The
latter means that there exists another allocation A0 with swu(A) < swu(A0)
and ui(A) <= ui(A0) for all i 2 A. If we had ui(A) = ui(A0) for all i 2 A,
then also swu(A) = swu(A0); that is, there must be at least one j 2 A with
uj(A) < uj(A0). But then the deal ffi = (A, A0) would be cooperatively rational,
which contradicts our assumption of A being a terminal allocation. 2

Observe that the proof would not have gone through if deals were required
to be strictly rational (without side payments), as this would necessitate
ui(A) < ui(A0) for all i 2 A. Cooperative rationality means, for instance,
that agents would be prepared to give away resources to which they assign
a utility value of 0, without expecting anything in return. In

6. Note that "cooperatively rational" agents are still essentially rational.
Their willingness to cooperate

only extends to cases where they can benefit others without any loss in utility
for themselves.

330

Negotiating Socially Optimal Allocations of Resources the framework with
money, another agent could always offer such an agent an infinitesimally
small amount of money, who would then accept the deal.

Therefore, our proposed weakened notion of rationality seems indeed a very
reasonable price to pay for giving up money.

4.4 Necessity Result As our next result shows, also for the framework without
side payments, deals of any structural complexity may be necessary in order
to be able to guarantee an optimal outcome of a negotiation.7 Theorem 5 improves
upon previous results (Endriss et al., 2003a) by showing that this necessity
property persists also when either all utility functions belong to the class
of monotonic functions or all utility functions belong to the class of dichotomous
functions.

Theorem 5 (Necessary deals without side payments) Let the sets of agents
and resources be fixed. Then for every deal ffi that is not independently
decomposable, there exist utility functions and an initial allocation such
that any sequence of cooperatively rational deals leading to a Pareto optimal
allocation would have to include ffi. This continues to be the case even
when either all utility functions are required to be monotonic or all utility
functions are required to be dichotomous.

Proof. The details of this proof are omitted as it is possible to simply
reuse the construction used in the proof of Theorem 2. Observe that the utility
functions defined there also guarantee ui(A) <= ui(A0) for all i 2 A, i.e.
A is not Pareto optimal, but A0 is. If we were to make A the initial allocation,
then ffi = (A, A0) would be the only cooperatively rational deal (as every
other deal would decrease social welfare). 2

4.5 0-1 Scenarios We conclude our study of the rational negotiation framework
without side payments by identifying a class of utility functions where we
are able to achieve a reduction in structural complexity.8 Consider a scenario
where agents use additive utility functions that assign either 0 or 1 to
every single resource (this is what we call 0-1 functions).9 This may be
appropriate when we simply wish to distinguish whether or not the agent needs
a particular resource (to execute a given plan, for example). This is, for
instance, the case for some of the agents defined in the work of Sadri, Toni,
and Torroni (2001). As the following theorem shows, for 0-1 scenarios (i.e.
for systems where all utility functions are 0-1 functions),

7. This theorem corrects a mistake in the original statement of the result
(Endriss et al., 2003a), where the

restriction to deals that are not independently decomposable had been omitted.
8. As dichotomous functions are a special case of the non-negative functions,
the full range of (not independently decomposable) deals is also necessary
in scenarios with non-negative functions. Interestingly, this changes when
we restrict ourselves to positive utility functions. Now the result of Theorem
5 would not hold anymore, because any deal that would involve a particular
agent (with a positive utility function) giving away all its resources without
receiving anything in return could never be cooperatively rational. Hence,
by Theorem 4, such a deal could never be necessary to achieve a Pareto optimal
allocation either. 9. Recall the distinction between 0-1 functions and dichotomous
functions. The latter assign either 0 or 1

to each bundle, while the former assign either 0 or 1 to each individual
resource (the utilities of bundles then follow from the fact that 0-1 functions
are additive).

331

Endriss, Maudet, Sadri, & Toni 1-deals are sufficient to guarantee convergence
to an allocation with maximal utilitarian social welfare, even in the framework
without monetary side payments (where all deals are required to be cooperatively
rational).

Theorem 6 (0-1 scenarios) In 0-1 scenarios, any sequence of cooperatively
rational 1- deals will eventually result in an allocation with maximal utilitarian
social welfare.

Proof. Termination is shown as in the proof of Theorem 4. If an allocation
A does not have maximal social welfare then it must be the case that some
agent i holds a resource r with ui({r}) = 0 and there is another agent j
in the system with uj({r}) = 1. Passing r from i to j would be a cooperatively
rational deal, so either negotiation has not yet terminated or we are indeed
in a situation with maximal utilitarian social welfare. 2

This result may be interpreted as a formal justification for some of the
negotiation strategies proposed by Sadri et al. (2001).

5. Egalitarian Agent Societies In this section, we are going to apply the
same methodology that we have used to study optimal outcomes of negotiation
in systems designed according to utilitarian principles in the first part
of this paper to the analysis of egalitarian agent societies. The classical
counterpart to the utilitarian collective utility function swu is the egalitarian
collective utility function swe introduced in Definition 9 (Moulin, 1988;
Sen, 1970; Rawls, 1971). Therefore, we are going to study the design of agent
societies for which negotiation can be guaranteed to converge to an allocation
of resources with maximal egalitarian social welfare.

Our first aim will be to identify a suitable criterion that agents inhabiting
an egalitarian agent society may use to decide whether or not to accept a
particular deal. Clearly, cooperatively rational deals, for instance, would
not be an ideal choice, because Pareto optimal allocations will typically
not be optimal from an egalitarian point of view (Moulin, 1988).

5.1 Pigou-Dalton Transfers and Equitable Deals When searching the economics
literature for a class of deals that would benefit society in an egalitarian
system we soon encounter Pigou-Dalton transfers. The Pigou-Dalton principle
states that whenever a utility transfer between two agents takes place which
reduces the difference in utility between the two, then that transfer should
be considered socially beneficial (Moulin, 1988). In the context of our framework,
a Pigou-Dalton transfer (between agents i and j) can be defined as follows.

Definition 15 (Pigou-Dalton transfers) A deal ffi = (A, A0) is called a Pigou-Dalton
transfer iff it satisfies the following criteria:

* Only two agents i and j are involved in the deal: Affi = {i, j}.

* The deal is mean-preserving: ui(A) + uj(A) = ui(A0) + uj(A0).

* The deal reduces inequality: |ui(A0) - uj(A0)| < |ui(A) - uj(A)|.

332

Negotiating Socially Optimal Allocations of Resources The second condition
in this definition could be relaxed to postulate ui(A) + uj(A) <= ui(A0)
+ uj(A0), to also allow for inequality-reducing deals that increase overall
utility.

Pigou-Dalton transfers capture certain egalitarian principles; but are they
sufficient as acceptability criteria to guarantee negotiation outcomes with
maximal egalitarian social welfare? Consider the following example:

u1({ }) = 0 u2({ }) = 0 u1({r1}) = 3 u2({r1}) = 5 u1({r2}) = 12 u2({r2})
= 7 u1({r1, r2}) = 15 u2({r1, r2}) = 17

The first agent attributes a relatively low utility value to r1 and a high
one to r2. Furthermore, the value of both resources together is simply the
sum of the individual utilities, i.e. agent 1 is using an additive utility
function (no synergy effects). The second agent ascribes a medium value to
either resource and a very high value to the full set. Now suppose the initial
allocation of resources is A with A(1) = {r1} and A(2) = {r2}. The "inequality
index" for this allocation is |u1(A) - u2(A)| = 4. We can easily check that
inequality is in fact minimal for allocation A (which means that there can
be no inequality-reducing deal, and certainly no Pigou-Dalton transfer, given
this allocation). However, allocation A0 with A0(1) = {r2} and A0(2) = {r1}
would result in a higher level of egalitarian social welfare (namely 5 instead
of 3). Hence, Pigou-Dalton transfers alone are not sufficient to guarantee
optimal outcomes of negotiations in egalitarian agent societies. We need
a more general acceptability criterion.

Intuitively, agents operating according to egalitarian principles should
help any of their fellow agents that are worse off than they are themselves
(as long as they can afford to do so without themselves ending up even worse).
This means, the purpose of any exchange of resources should be to improve
the welfare of the weakest agent involved in the respective deal. We formalise
this idea by introducing the class of equitable deals.

Definition 16 (Equitable deals) A deal ffi = (A, A0) is called equitable
iff it satisfies the following criterion:

min{ui(A) | i 2 Affi} < min{ui(A0) | i 2 Affi} Recall that Affi = {i 2 A
| A(i) 6= A0(i)} denotes the set of agents involved in the deal ffi. Given
that for ffi = (A, A0) to be a deal we require A 6= A0, Affi can never be
the empty set (i.e. the minima referred to in above definition are well-defined).
Note that equitability is a local rationality criterion in the sense of Definition
6.

It is easy to see that any Pigou-Dalton transfer will also be an equitable
deal, because it will always result in an improvement for the weaker one
of the two agents concerned. The converse, however, does not hold (not even
if we restrict ourselves to deals involving only two agents). In fact, equitable
deals may even increase the inequality of the agents concerned, namely in
cases where the happier agent gains more utility than the weaker does.

In the literature on multiagent systems, the autonomy of an agent (one of
the central features distinguishing multiagent systems from other distributed
systems) is sometimes equated with pure selfishness. Under such an interpretation
of the agent paradigm, our

333

Endriss, Maudet, Sadri, & Toni notion of equitability would, of course, make
little sense. We believe, however, that it is useful to distinguish different
degrees of autonomy. An agent may well be autonomous in its decision in general,
but still be required to follow certain rules imposed by society (and agreed
to by the agent on entering that society).

5.2 Local Actions and their Global Effects We are now going to prove two
lemmas that provide the connection between the local acceptability criterion
given by the notion of equitability and the two egalitarian social welfare
orderings introduced in Section 2.3 (i.e. the maximin-ordering induced by
swe as well as the leximin-ordering).

The first lemma shows how global changes are reflected locally. If a deal
happens to increase (global) egalitarian social welfare, that is, if it results
in a rise with respect to the maximin-ordering, then that deal will in fact
be an equitable deal.

Lemma 2 (Maximin-rise implies equitability) If A and A0 are allocations with
swe(A) < swe(A0), then ffi = (A, A0) is an equitable deal.

Proof. Let A and A0 be allocations with swe(A) < swe(A0) and let ffi = (A,
A0). Any agent with minimal utility for allocation A must be involved in
ffi, because egalitarian social welfare, and thereby these agents' individual
utility, is higher for allocation A0. That is, we have min{ui(A) | i 2 Affi}
= swe(A). Furthermore, because Affi ` A, we certainly have swe(A0) <= min{ui(A0)
| i 2 Affi}. Given our original assumption of swe(A) < swe(A0), we now obtain
the inequation min{ui(A) | i 2 Affi} < min{ui(A0) | i 2 Affi}. This shows
that ffi will indeed be an equitable deal. 2

Observe that the converse does not hold; not every equitable deal will necessarily
increase egalitarian social welfare (although an equitable deal will never
decrease egalitarian social welfare either). This is, for instance, not the
case if only agents who are currently better off are involved in a deal.
In fact, as argued already at the end of Section 2.2, there can be no class
of deals characterisable by a local rationality criterion (see Definition
6) that would always result in an increase in egalitarian social welfare.

To be able to detect changes in welfare resulting from an equitable deal
we require the finer differentiation between alternative allocations of resources
given by the leximinordering. In fact, as we shall see next, any equitable
deal can be shown to result in a strict improvement with respect to the leximin-ordering.

Lemma 3 (Equitability implies leximin-rise) If ffi = (A, A0) is an equitable
deal, then A OE A0.

Proof. Let ffi = (A, A0) be a deal that satisfies the equitability criterion
and define ff = min{ui(A) | i 2 Affi}. The value ff may be considered as
partitioning the ordered utility vector ~u(A) into three subvectors: Firstly,
~u(A) has got a (possibly empty) prefix ~u(A)ff (which again may be empty) where all elements are strictly
greater than ff.

334

Negotiating Socially Optimal Allocations of Resources By definition of ff,
the deal ffi cannot affect agents whose utility values belong to ~u(A)= ui(A(j)) for all agents i, j 2 A.

Like egalitarian social welfare, this is related to the fair division of
resources amongst agents. Envy-freeness is desirable (though not always achievable)
in societies of self-interested agents in cases where agents have to collaborate
with each other over a longer period of time. In such a case, should an agent
believe that it has been ripped off, it would have an incentive to leave
the coalition which may be disadvantageous for other agents or the society
as a whole. In other words, envy-freeness plays an important role with respect
to the stability of a group. Unfortunately, envy-free allocations do not
always exist. A simple example would be a system with two agents and just
a single resource, which is valued by both of them. Then whichever agent
holds that single resource will be envied by the other agent.

Furthermore, aiming at agreeing on an envy-free allocation of resources is
not always compatible with, say, negotiating Pareto optimal outcomes. Consider
the following example of two agents with identical preferences over alternative
bundles of resources:

342

Negotiating Socially Optimal Allocations of Resources

u1({ }) = 0 u2({ }) = 0 u1({r1}) = 1 u2({r1}) = 1 u1({r2}) = 2 u2({r2}) =
2 u1({r1, r2}) = 0 u2({r1, r2}) = 0

For this example, either one of the two allocations where one agent owns
all resources and the other none would be envy-free (as no agent would prefer
the other one's bundle over its own). However, such an allocation would not
be Pareto optimal. On the other hand, an allocation where each agent owns
a single resource would be Pareto optimal, but not envy-free (because the
agent holding r1 would rather have r2).

We should stress that envy is defined on the sole basis of an agent's private
preferences, i.e. there is no need to take other agents' utility functions
into account. Still, whether an agent is envious does not just depend on
the resources it holds, but also on the resources it could hold and whether
any of the other agents currently hold a preferred bundle. This somewhat
paradoxical situation makes envy-freeness far less amenable to our methodology
than any of the other notions of social welfare we have discussed in this
paper.

To be able to measure different degrees of envy, we could, for example, count
the number of agents that are envious for a given allocation. Another option
would be to compute for each agent i that experiences any envy at all the
difference between ui(A(i)) and ui(A(j)) for the agent j that i envies the
most. Then the sum over all these differences would also provide an indication
of the degree of overall envy (and thereby of social welfare). In the spirit
of egalitarianism, a third option would be identify the degree of envy in
society with the degree of envy experienced by the agent that is the most
envious (Lipton, Markakis, Mossel, & Saberi, 2004). However, it is not possible
to define a local acceptability criterion in terms of the utility functions
of the agents involved in a deal (and only those) that indicates whether
the deal in question would reduce envy according to any such a metric. This
is a simple consequence of the fact that a deal may affect the degree of
envy experienced by an agent not involved in the deal at all (because it
could lead to one of the participating agents ending up with a bundle preferred
by the non-concerned agent in question).

8. Conclusion We have studied an abstract negotiation framework where members
of an agent society arrange multilateral deals to exchange bundles of indivisible
resources, and we have analysed how the resulting changes in resource distribution
affect society with respect to different social welfare orderings.

For scenarios where agents act rationally in the sense of never accepting
a deal that would (even temporarily) decrease their level of welfare, we
have seen that systems where side payments are possible can guarantee outcomes
with maximal utilitarian social welfare, while systems without side payments
allow, at least, for the negotiation of Pareto optimal allocations. We have
also considered two examples of special domains with restricted utility functions,
namely additive and 0-1 scenarios. In both cases, we have been able to prove
the convergence to a socially optimal allocation of resources also for negotiation
protocols that allow only for deals involving only a single resources and
a pair of agents each (so-called 1-deals). In the case of agent societies
where welfare is measured in terms of the egalitarian collective utility
function, we have put forward the class of equitable deals and shown that

343

Endriss, Maudet, Sadri, & Toni negotiation processes where agents use equitability
as an acceptability criterion will also converge towards an optimal state.
Another result states that, for the relatively simple 0-1 scenarios, Lorenz
optimal allocations can be achieved using one-to-one negotiation by implementing
1-deals that are either inequality-reducing or that increase the welfare
of both agents involved. We have also discussed the case of elitist agent
societies where social welfare is tied to the welfare of the most successful
agent. And finally, we have pointed out some of the difficulties associated
with designing agents that would be able to negotiate allocations of resources
where the degree of envy between the agents in a society is minimal. Specifically,
we have proved the following technical results:

* The class of individually rational deals14 is sufficient to negotiate allocations
with

maximal utilitarian social welfare (Theorem 1).

* In domains with additive utility functions, the class of individually rational
1-deals is

sufficient to negotiate allocations with maximal utilitarian social welfare
(Theorem 3).

* The class of cooperatively rational deals is sufficient to negotiate Pareto
optimal allocations (Theorem 4).

* In domains with 0-1 utility functions, the class of cooperatively rational
1-deals is

sufficient to negotiate allocations with maximal utilitarian social welfare
(Theorem 6).

* The class of equitable deals is sufficient to negotiate allocations with
maximal egalitarian social welfare (Theorem 7).

* In domains with 0-1 utility functions, the class of simple Pareto-Pigou-Dalton
deals

(which are 1-deals) is sufficient to negotiate Lorenz optimal allocations
(Theorem 9).

For each of the three convergence results that apply to deals without structural
restrictions (rather than to 1-deals), we have also proved corresponding
necessity results (Theorems 2, 5, and 8). These theorems show that any given
deal (defined as a pair of allocations) that is not independently decomposable
may be necessary to be able to negotiate an optimal allocation of resources
(with respect to the chosen notion of social welfare), if deals are required
to conform to the rationality criterion in question. As a consequence of
these results, no negotiation protocol that does not allow for the representation
of deals involving any number of agents and any number of resources could
ever enable agents (whose behaviour is constrained by our various rationality
criteria) to negotiate a socially optimal allocation in all cases. Rather
surprisingly, all three necessity results continue to apply even when agents
can only differentiate between resource bundles that they would be happy
with and those they they would not be happy with (using dichotomous utility
functions). Theorems 2 and 5 also apply in case all agents are required to
use monotonic utility functions.

A natural question that arises when considering our convergence results concerns
the complexity of the negotiation framework. How difficult is it for agents
to agree on a deal and how many deals are required before a system converges
to an optimal state? The latter of these questions has recently been addressed
by Endriss and Maudet (2005). The paper

14. Recall that individually rational deals may include monetary side payments.

344

Negotiating Socially Optimal Allocations of Resources establishes upper bounds
on the number of deals required to reach any of the optimal allocations of
resources referred to in the four convergence theorems for the model of rational
negotiation (i.e. Theorems 1, 3, 4, and 6). It also discusses the different
aspects of complexity involved at a more general level (such as the distinction
between the communication complexity of the system, i.e. the amount of information
that agents need to exchange to reach an optimal allocation, and the computational
complexity of the reasoning tasks faced by every single agent). Dunne (2005)
addresses a related problem and studies the number of deals meeting certain
structural requirements (in particular 1-deals) that are required to reach
a given target allocation (whenever this is possible at all --recall that
our necessity results show that excluding certain deal patterns will typically
bar agents from reaching optimal allocations).

In earlier work, Dunne et al. (2005) have studied the complexity of deciding
whether one-resource-at-a-time trading with side payments is sufficient to
reach a given allocation (with improved utilitarian social welfare). This
problem has been shown to be NP-hard. Other complexity results concern the
computational complexity of finding a socially optimal allocation, independently
from the concrete negotiation mechanism used. As mentioned earlier, such
results are closely related to the computational complexity of the winner
determination problem in combinatorial auctions (Rothkopf, Peke*c, & Harstad,
1998; Cramton et al., 2006). Recently, NP-completeness results for this optimisation
problem have been derived with respect to several different ways of representing
utility functions (Dunne et al., 2005; Chevaleyre et al., 2004). Bouveret
and Lang (2005) also address the computational complexity of deciding whether
an allocation exists that is both envy-free and Pareto optimal.

Besides presenting technical results, we have argued that a wide spectrum
of social welfare orderings (rather than just those induced by the well-known
utilitarian collective welfare function and the concept of Pareto optimality)
can be of interest to agent-based applications. In the context of a typical
electronic commerce application, where participating agents have no responsibilities
towards each other, a system designer may wish to ensure Pareto optimality
to guarantee that agents get maximal payoff whenever this is possible without
making any of the other agents worse off. In applications where a fair treatment
of all participants is vital (e.g. cases where the system infrastructure
is jointly owned by all the agents), an egalitarian approach to measuring
social welfare may be more appropriate. Many applications are in fact likely
to warrant a mixture of utilitarian and egalitarian principles. Here, systems
that enable Lorenz optimal agreements may turn out to be the technology of
choice. Other applications, however, may require social welfare to be measured
in ways not foreseen by the models typically studied in the social sciences.
Our proposed notion of elitist welfare would be such an example. Elitism
has little room in human society, where ethical considerations are paramount,
but for a particular computing application these considerations may well
be dropped or changed.

This discussion suggests an approach to multiagent systems design that we
call welfare engineering (Endriss & Maudet, 2004). It involves, firstly,
the application-driven choice (or possibly invention) of a suitable social
welfare ordering and, secondly, the design of agent behaviour profiles and
negotiation mechanisms that permit (or even guarantee) socially optimal outcomes
of interactions between the agents in a system. As discussed earlier, designing
agent behaviour profiles does not necessarily contradict the idea of the
autonomy

345

Endriss, Maudet, Sadri, & Toni of an agent, because autonomy always has to
be understood as being relative to the norms governing the society in which
the agent operates. We should stress that, while we have been studying a
distributed approach to multiagent resource allocation in this paper, the
general idea of exploring the full range of social welfare orderings when
developing agent-based applications also applies to centralised mechanisms
(such as combinatorial auctions).

We hope to develop this methodology of welfare engineering further in our
future work. Other possible directions of future work include the identification
of further social welfare orderings and the definition of corresponding deal
acceptability criteria; the continuation of the complexity-theoretic analysis
of our negotiation framework; and the design of practical trading mechanisms
(including both protocols and strategies) that would allow agents to agree
on multilateral deals involving more than just two agents at a time.

Acknowledgments We would like to thank J'er^ome Lang and various anonymous
referees for their valuable comments. This research has been partially supported
by the European Commission as part of the SOCS project (IST-2001-32530).

References Andersson, M., & Sandholm, T. W. (2000). Contract type sequencing
for reallocative negotiation. In Proceedings of the 20th International Conference
on Distributed Computing Systems (ICDCS-2000), pp. 154-160. IEEE.

Arrow, K. J., Sen, A. K., & Suzumura, K. (Eds.). (2002). Handbook of Social
Choice and

Welfare, Vol. 1. North-Holland.

Bouveret, S., & Lang, J. (2005). Efficiency and envy-freeness in fair division
of indivisible

goods: Logical representation and complexity. In Proceedings of the 19th
International Joint Conference on Artificial Intelligence (IJCAI-2005), pp.
935-940. Morgan Kaufmann Publishers.

Brams, S. J., & Taylor, A. D. (1996). Fair Division: From Cake-cutting to
Dispute Resolution. Cambridge University Press.

Chavez, A., Moukas, A., & Maes, P. (1997). Challenger: A multi-agent system
for distributed

resource allocation. In Proceedings of the 1st International Conference on
Autonomous Agents (Agents-1997), pp. 323-331. ACM Press.

Chevaleyre, Y., Endriss, U., Estivie, S., & Maudet, N. (2004). Multiagent
resource allocation

with k-additive utility functions. In Proceedings of the DIMACS-LAMSADE Workshop
on Computer Science and Decision Theory, Vol. 3 of Annales du LAMSADE, pp.
83-100.

Chevaleyre, Y., Endriss, U., Lang, J., & Maudet, N. (2005a). Negotiating
over small bundles

of resources. In Proceedings of the 4th International Joint Conference on
Autonomous Agents and Multiagent Systems (AAMAS-2005), pp. 296-302. ACM Press.

Chevaleyre, Y., Endriss, U., & Maudet, N. (2005b). On maximal classes of
utility functions

for efficient one-to-one negotiation. In Proceedings of the 19th International
Joint

346

Negotiating Socially Optimal Allocations of Resources Conference on Artificial
Intelligence (IJCAI-2005), pp. 941-946. Morgan Kaufmann Publishers.

Cramton, P., Shoham, Y., & Steinberg, R. (Eds.). (2006). Combinatorial Auctions.
MIT

Press.

Dunne, P. E. (2005). Extremal behaviour in multiagent contract negotiation.
Journal of

Artificial Intelligence Research, 23, 41-78.

Dunne, P. E., Wooldridge, M., & Laurence, M. (2005). The complexity of contract
negotiation. Artificial Intelligence, 164 (1-2), 23-46.

Dunne, P. E., Laurence, M., & Wooldridge, M. (2004). Tractability results
for automatic

contracting. In Proceedings of the 16th Eureopean Conference on Artificial
Intelligence (ECAI-2004), pp. 1003-1004. IOS Press.

Endriss, U., & Maudet, N. (2004). Welfare engineering in multiagent systems.
In Engineering

Societies in the Agents World IV, Vol. 3071 of LNAI, pp. 93-106. Springer-Verlag.

Endriss, U., & Maudet, N. (2005). On the communication complexity of multilateral
trading:

Extended report. Journal of Autonomous Agents and Multiagent Systems, 11
(1), 91- 107.

Endriss, U., Maudet, N., Sadri, F., & Toni, F. (2003a). On optimal outcomes
of negotiations over resources. In Proceedings of the 2nd International Joint
Conference on Autonomous Agents and Multiagent Systems (AAMAS-2003), pp.
177-184. ACM Press.

Endriss, U., Maudet, N., Sadri, F., & Toni, F. (2003b). Resource allocation
in egalitarian agent societies. In Secondes Journ'ees Francophones sur les
Mod`eles Formels d'Interaction (MFI-2003), pp. 101-110. C'epadu`es-'Editions.

Fatima, S. S., Wooldridge, M., & Jennings, N. R. (2004). An agenda-based
framework for

multi-issues negotiation. Artificial Intelligence, 152 (1), 1-45.

Fishburn, P. C. (1970). Utility Theory for Decision Making. John Wiley and
Sons. Fujishima, Y., Leyton-Brown, K., & Shoham, Y. (1999). Taming the computational
complexity of combinatorial auctions: Optimal and approximate approaches.
In Proceedings of the 16th International Joint Conference on Artificial Intelligence
(IJCAI1999), pp. 548-553. Morgan Kaufmann Publishers.

Kraus, S. (2001). Strategic Negotiation in Multiagent Environments. MIT Press.
Lema^itre, M., Verfaillie, G., & Bataille, N. (1999). Exploiting a common
property resource

under a fairness constraint: A case study. In Proceedings of the 16th International
Joint Conference on Artificial Intelligence (IJCAI-1999), pp. 206-211. Morgan
Kaufmann Publishers.

Lipton, R. J., Markakis, E., Mossel, E., & Saberi, A. (2004). On approximately
fair allocations of indivisible goods. In Proceedings of the 5th ACM Conference
on Electronic Commerce (EC-2004), pp. 125-131. ACM Press.

Moulin, H. (1988). Axioms of Cooperative Decision Making. Cambridge University
Press.

347

Endriss, Maudet, Sadri, & Toni Myerson, R. B., & Satterthwaite, M. A. (1983).
Efficient mechanisms for bilateral trading.

Journal of Economic Theory, 29 (2), 265-281.

Rawls, J. (1971). A Theory of Justice. Oxford University Press. Rosenschein,
J. S., & Zlotkin, G. (1994). Rules of Encounter. MIT Press. Rothkopf, M.
H., Peke*c, A., & Harstad, R. M. (1998). Computationally manageable combinational
auctions. Management Science, 44 (8), 1131-1147.

Sadri, F., Toni, F., & Torroni, P. (2001). Dialogues for negotiation: Agent
varieties and dialogue sequences. In Proceedings of the 8th International
Workshop on Agent Theories, Architectures, and Languages (ATAL-2001), pp.
405-421. Springer-Verlag.

Sandholm, T. W. (2002). Algorithm for optimal winner determination in combinatorial
au

ctions. Artificial Intelligence, 135, 1-54.

Sandholm, T. W. (1998). Contract types for satisficing task allocation: I
Theoretical results.

In Proceedings of the AAAI Spring Symposium: Satisficing Models.

Sandholm, T. W. (1999). Distributed rational decision making. In Weiss, G.
(Ed.), Multiagent Systems: A Modern Approach to Distributed Artificial Intelligence,
pp. 201-258. MIT Press.

Sen, A. K. (1970). Collective Choice and Social Welfare. Holden Day. Smith,
R. G. (1980). The contract net protocol: High-level communication and control
in a

distributed problem solver. IEEE Transactions on Computers, C-29 (12), 1104-1113.

Wooldridge, M. (2002). An Introduction to MultiAgent Systems. John Wiley
and Sons.

348