The setting we are concerned with is encapsulated in the following definition.
Within the very general context of Definition 1, a number of issues arise stemming from the observation that it is unlikely that some initial allocation will be seen as satisfactory either with respect to the views of all agents in the system or with respect to divers global considerations. Thus, by proposing changes to the initial assignment individual agents seek to obtain a ``better'' allocation. This scenario raises two immediate questions: how to evaluate a given partition and thus have a basis for forming improved or optimal allocations; and, the issue underlying the main results of this paper, what restrictions should be imposed on the form that proposed deals may take.
We shall subsequently review some of the more widely studied approaches to defining conditions under which some allocations are seen as ``better'' than others. For the purposes of this introduction we simply observe that such criteria may be either quantitative or qualitative in nature. As an example of the former we have the approach wherein the ``value'' of an allocation is simply the sum of the values given by the agents' utility functions to the subsets of they have been apportioned within , i.e. : this is the so-called utilitarian social welfare, which to avoid repetition we will denote by . A natural aim for agents within a commodity trading context is to seek an allocation under which is maximised. One example of a qualitative criterion is ``envy freeness'': informally, an allocation, , is envy-free if no agent assigns greater utility to the resource set () held by another agent than it does with respect to the resource set () it has actually been allocated, i.e. for each distinct pair , .
In very general terms there are two approaches that have been considered in treating the question of how a finite collection of resources might be distributed among a set of agents in order to optimise some criterion of interest: ``contract-net'' based methods, e.g. [Dunne et al., 2003; Endriss et al., 2003; Endriss & Maudet, 2004b; Sandholm, 1998, 1999] deriving from the work of [Smith, 1980]; and ``combinatorial auctions'', e.g. [ Parkes & Ungar, 2000a; Parkes & Ungar, 2003b; Sandholm et al., 2001; Sandholm, 2002; Sandholm & Suri, 2003; Tennenholz, 2000; Yokoo et al., 2004 amongst others] The significant difference between these is in the extent to which a centralized controlling agent determines the eventual distribution of resources among agents.
One may view the strategy underlying combinatorial auctions as investing the computational effort into a ``pre-processing'' stage following which a given allocation is determined. Thus a controlling agent (the ``auctioneer'') is supplied with a set of bids - pairs wherein is some subset of the available resources and the price agent is prepared to pay in order to acquire . The problem faced by the auctioneer is to decide which bids to accept in order to maximise the overall profit subject to the constraint that each item can be obtained by at most one agent.
What we shall refer to as ``contract-net schemes'' typically eschew the precomputation stage and subordination to a controlling arbiter employed in auction mechanisms, seeking instead to realise a suitable allocation by an agreed sequence of deals. The contract-net (in its most general instantiation) for scenarios of resources distributed among agents, is the complete directed graph with vertices (each of which is associated with a distinct allocation). In this way a possible deal is represented as an edge directed from the vertex labelled with to that labelled . Viewed thus, identifying a sequence of deals can be interpreted as a search process which, in principle, individual agents may conduct in an autonomous fashion.
Centralized schemes can be effective in contexts where the participants cooperate (in the sense of accepting the auctioneer's arbritration). In environments within which agents are highly self-interested to the extent that their aims conflict with the auction process or in which there is a high degree of ``uncertainty'' about the outcome, in working towards a final allocation, the agents involved may only be prepared to proceed ``cautiously'': that is, an agent will only accept a proposed reallocation if satisfied that such would result in an immediate improvement from its own perspective. In such cases, the process of moving from the initial allocation, , to the eventual reallocation is by a sequence of local rational deals, e.g. an agent might refuse to accept deals which reduced because of the possibility that it suffers an uncompensated loss in utility. A key issue here is the following: if the deal protocol allows only moves in which at each stage some agent offers a single resource to another agent then the rational reallocation can always be implemented; if, however, every single move must be ``rational'' then may not be realisable.
We may, informally, regard the view of such agents as ``myopic'', in the sense that they are unwilling to accept a ``short-term loss'' (a deal under they might incur a loss of utility) despite the prospect of a ``long-term gain'' (assuming holds).
There are a number of reasons why an agent may adopt such views, e.g. consider the following simple protocol for agreeing a reallocation.
A reallocation of resources is agreed over a sequence of stages, each of which involves communication between two agents, and . This communication consists of issuing a proposal to of the form , offering to purchase from for a payment of ; or , offering to transfer to in return for a payment . The response from is simply (following which the deal is implemented) or .This, of course, is a very simple negotiation structure, however consider its operation within a two agent setting in which one agent, say, wishes to bring about an allocation (and thus can devise a plan - sequence of deals - to realise this from an initial allocation ) while the other agent, , does not know . In addition, assume that is the only agent that makes proposals and that a final allocation is fixed either when is ``satisfied'' or as soon as rejects any offer.
While could be better off if is realised, it may be the case that the only proposals will accept are those under which it does not lose, e.g. some agents may be sceptical about the bona fides of others and will accept only deals from which they can perceive an immediate benefit. There are several reasons why an agent may embrace such attitudes within the schema outlined: once a deal has been implemented may lose utility but no further proposals are made by so that the loss is ``permanent''. We note that even if we enrich the basic protocol so that can describe , may still reject offers under which it suffers a loss, since it is unwilling to rely on the subsequent deals that would ameliorate its loss actually being proposed. Although the position taken by in the setting just described may appear unduly cautious, we would claim that it does reflect ``real'' behaviour in certain contexts. Outside the arena of automated allocation and negotiation in multiagent systems, there are many examples of actions by individuals where promised long-term gains are insufficient to engender the acceptance of short term loss. Consider ``chain letter'' schemes (or their more subtle manifestation as ``pyramid selling'' enterprises): such have a natural lifetime bounded by the size of the population in which they circulate, but may break down before this is reached. Faced with a request to ``send $10 to the five names at the head of the list and forward the letter to ten others after adding your name'' despite the possibility of significant gain after a temporary loss of $50, to ignore such blandishments is not seen as overly sceptical and cautious: there may be reluctance to accept that one will eventually receive sufficient recompense in return and suspicion that the name order has been manipulated.
In summary, we can identify two important influences that lead to contexts in which agents prefer to move towards a reallocation via a sequence of ``rational'' deals. Firstly, the agents are self-interested but operating in an unstable environment, e.g. in the ``chain letter'' setting, an agent cannot reliably predict the exact point at which the chain will fail. The second factor is that computational restrictions may limit the decisions an individual agent can make about whether or not to accept a proposed deal. For example in settings where all deals involve one resource at a time, may reject a proposal to accept some resource, , since is only ``useful'' following a further sequence of deals: if this number of further deals is ``small'' then could decide to accept the proposed deal since it has sufficient computational power to determine that there is a context in which is of value; if this number is ``large'' however, then may lack sufficient power to scan the search space of future possibilities that would allow it to accept . Notice that in the extreme case, makes its decision solely on whether is of immediate use, i.e. is myopic. A more powerful may be able to consider whether is useful should up to further deals take place: in this case, could still refuse to accept since, although of use, cannot determine this with a bounded look ahead.
In total for the scenario we have described, if wishes to bring about an allocation then faced with the view adopted by and the limitations imposed by the deal protocol, the only ``effective plan'' that could adopt is to find a sequence of rational deals to propose to .
Our aim in this article is to show that combining ``structural'' restrictions
(e.g. only one resource at a time is involved in a local reallocation) with
rationality restrictions can result in settings in which any sequence to realise
must involve exponentially many (in
We refine these ideas in the next sub-section.