Next: Monotone Utility Functions and M(k)-contract paths Up: Extremal Behaviour in Multiagent Contract Negotiation Previous: O-contract Paths - Monotone

# -contract paths

We now turn to similar issues with respect to -contracts, recalling that in one respect these offer a form of deal that does not fit into the classification of [Sandholm, 1998]. This classification defines four forms of contract type: -contracts, as considered in the previous section; -contracts, that involve exactly 2 agents swapping single resources; -contracts, in which one agent tranfers at least two of its resources to another; and -contracts in which three or more agents reallocate their resource holding amongst themselves. Our definition of -contracts permits two agents to exchange resources (thus are not -contracts in Sandholm's[1998] scheme) and the deals permitted are not restricted to , , and -contracts. In one regard, however, -contracts are not as general as -contracts since a preset bound () is specified for the number of agents involved.

Our main result on -contract paths is the following development of Theorem 3.

Theorem 6   Let be the predicate which holds whenever is an IR -contract. For all , and , there is a resource allocation setting and an IR deal for which,

Before presenting the proof, we comment about the formulation of the theorem statement and give an overview of the proof structure.

We first note that the lower bounds (where defined) have been phrased in terms of the function as opposed to used in the various results on -contract paths in Section 2.2. It is, of course, the case that the bound claimed for will also be a lower bound on when and holds whenever the deal is IR. The statement of Theorem 6, however, claims rather more than this, namely that a specific resource allocation setting can be defined for each and each , together with an IR deal in such a way that: can be achieved by a single -contract and cannot be realised by an IR -contract path. Recalling that is a partial function, the latter property is equivalent to the claim made in part (c) for the deal of the theorem statement. Furthermore, this same deal although achievable by an IR -contract path can be so realised only by one whose length is as given in part (b) of the theorem statement.

Regarding the proof itself, there are a number of notational complexities which we have attempted to ameliorate by making some simplifying assumptions concerning the relationship between - the size of the resource set - and - the number of agents which are needed to realise in a single IR deal. In particular, we shall assume that is an exact multiple of . We observe that by employing a similar device to that used in the proof of Theorem 4 we can deal with cases for which does not have this property: if for integer values and , we simply employ exactly the same construction using resources with the missing'' resources from being allocated to and never being reallocated within the -contract path. This approach accounts for the rounding operation ( ) in the exponent term of the lower bound. We shall also assume that the number of agents in is exactly . Within the proof we use a running example for which and to illustrate specific features.

We first give an outline of its structure.

Given a resource allocation setting involving agents and resources, our aim is to define an IR -contract path

that realises the IR deal . We will use to index particular allocations within , so that .

In order to simplify the presentation we employ a setting in which the agents are . Recalling that , the resource set is formed by the union of pairwise disjoint sets of size . Given distinct values and with , we use to denote one of these subsets with the resources that form .

There are two main ideas underpinning the structure of each -contract in .

Firstly, in the initial and subsequent allocations, the resource set is partitioned between and and any reallocation of resources between and that takes place within the deal will involve only resources in this set. Thus, for every allocation and each pair , if then . Furthermore, for should both and be involved, i.e. , then this reallocation of between and will be an -contract. That is, either exactly one element of will be moved from to become a member of the allocation or exactly one element of will be moved from to become a member of the allocation . In total, every -contract in consists of a simultaneous implementation of -contracts: a single -contract for each of the distinct pairs of agents from the agents in .

The second key idea is to exploit one well-known property of the -dimensional hypercube network: for every , contains a Hamiltonian cycle, i.e. a simple directed cycle formed using only the edges of and containing all vertices.7 Now, suppose

is a Hamiltonian cycle in the hypercube and

the Hamiltonian cycle in which is obtained by complementing each bit in . As we have described in the overview of Section 2.1 we can interpret the -bit label as describing a particular subset of , i.e. that subset in which occurs if and only if . Similarly from any subset of we may define a unique -bit word. Now suppose that is the allocation held by in the allocation of . The deal will affect in the following way: if or then and . Otherwise we have and the (complementary) holdings and define (complementary) -bit labels of vertices in : if these correspond to places in the Hamiltonian cycles, then in and the -bit labels defined from and produce the -bit labels and , i.e. the vertices that succeed and in the Hamiltonian cycles. In total, for each , initially holds either the subset of that maps to or that maps to and, at the conclusion of the -path, holds the subset that maps to (or ). The final detail is that the progression through the Hamiltonian cycles is conducted over a series of rounds each round comprising -deals.

We have noted that each -contract, that occurs in this path can be interpreted as a set of distinct -contracts. An important property of the utility functions employed is that unless there will be no individually rational -contract path that realises the deal , i.e. the -contract deals must occur simultaneously in order for the progression from to to be IR. Although the required deal could be realised by a sequence of -contracts (or, more generally, any suitable -contract path), such realisations will not describe an IR contract path. The construction of utility functions to guarantee such behaviour provides the principal component in showing that the IR deal cannot be realised with an IR -contract path: if is any allocation for which is an -contract then is not IR.

We now proceed with the proof of Theorem 6.

Proof. (of Theorem 6) Fix . consists of pairwise disjoint sets of resources

For and these yield and

We use two ordering structures in defining the -contract path.
a.

a Hamiltonian cycle in , where without loss of generality, .
b.

the complementary Hamiltonian cycle to this, so that .
Thus for and we obtain

We can now describe the -contract path.

Initial Allocation: .
Define the Boolean matrix, (with ) by

We then have for each ,

Thus, in our example,

Yielding the starting allocation

The third column in indicating the -bit labels characterising each of the subsets of for the three values that can assume.

Rounds: The initial allocation is changed over a series of rounds

each of which involves exactly distinct -contracts. We use to indicate the allocation resulting after stage in round where . We note the following:
a.
The initial allocation, will be denoted by .
b.
is obtained using a single -contract from (when ).
c.
is obtained using a single -contract from (when ).
Our final item of notation is that of the cube position of with respect to in an allocation , denoted . Letting be the -bit string describing in some allocation , is the index of in the Hamiltonian cycle (when ) or the Hamiltonian cycle (when ). When for some allocation in the sequence under construction we employ the notation , noting that one invariant of our path will be , a property that certainly holds true of since .

The sequence of allocations in is built as follows. Since is the immediate successor of the initial allocation , it suffices to describe how is formed from (when ) and from . Let be the allocation to be formed from . The deal will be an contract in which . For each pair we have in the allocation . In moving to exactly one element of is reallocated between and in such a way that in , , since and are tracing complementary Hamiltonian cycles with respect to this ensures that , thereby maintaining the invariant property.

Noting that for each distinct pair , we either have allocated to in or allocated to in , the description just outlined indicates that the allocation is completely specified as follows.

The cube position, , satisfies,

For each , the subset of that is held by in the allocation is,

(where we recall that -bit labels in the hypercube are identified with subsets of .)
The tables below illustrates this process for our example.

It is certainly the case that this process of applying successive rounds of deals could be continued, however, we wish to do this only so long as it is not possible to go from some allocation in the sequence to another for some via an -contract.

Now if and are distinct allocations generated by the process above then the deal is an -contract if and only if for some , . It follows that if is an -contract for some , then for some and all , .

To determine the minimum value of with which , we observe that without loss of generality we need consider only the case , i.e. we determine the minimum number of deals before reappears. First note that in each round, , if then , i.e. each round advances the cube position places: and . We can also observe that for any with , since

only in the cases and . It follows that our value must be of the form where must be such that is an exact multiple of . From this observation we see that,

Now, if is odd then is the minimal such value, so that . If is even then it may be uniquely written in the form where is odd so giving as (if ) or (if ), so that these give and , e.g. for and , we get so that and in our example may be easily verified. In total,

All of which immediately give (in the second case , so the inequality holds trivially), and thus we can continue the chain of contracts for at least moves. Recalling that , this gives the length of the -contract path

written in terms of and as at least8

It remains to define appropriate utility functions in order to ensure that is the unique IR -contract path realising the IR -deal . In defining it will be convenient to denote as the path

and, since , we may without loss of generality, focus on the first allocations in this contract path.

Recalling that is the index of the -bit label corresponding to in the relevant Hamiltonian cycle - i.e. if , if - we note the following properties of the sequence of allocations defined by that hold for each distinct and .

P1.
P2.
If is the immediate successor of in then with equality if and only if .
P3.
with , .
The first two properties have already been established in our description of . The third follows from the observation that within each round , each cube position is advanced by exactly in progressing from to .

The utility function is now given, for , by

We claim that, with these choices,

is the unique IR -contract path realising the IR -deal . Certainly, is an IR -contract path: each deal on this path has and since for each agent in the utility of has increased by exactly , i.e. each cube position of with respect to whenever has increased, it follows that and hence is IR.

We now show that is the unique IR -contract path continuation of Suppose is a deal that deviates from the contract path (having followed it through to the allocation ). Certainly both of the following must hold of : for each , ; and there is a -tuple of pairs with which , for if either fail to be the case for some , then with the consequent effect that and thence not IR. Now, if is the allocation that would succeed in then , and thus for at least one agent, . It cannot be the case that corresponds to an allocation occurring strictly later than in since such allocations could not be realised by an -contract. In addition, since it must be the case that since exactly cube positions in the holding of must change. It follows that there are only two possibilities for : reverts to the allocation immediately preceding or advances to the holding . It now suffices to observe that a deal in which some agents satisfy the first of these while the remainder proceed in accordance with the second either does not give rise to a valid allocation or cannot be realised by an -contract. On the other hand if corresponds to the allocation preceding then is not IR. We deduce, therefore, that the only IR deal that is consistent with is that prescribed by .

This completes the analysis needed for the proof of part (b) of the theorem. It is clear that since the system contains only agents, any deal can be effected with a single -contract, thereby establishing part (a). For part (c) - that the IR deal cannot be realised using an individually rational -contract path, it suffices to observe that since the class of IR -contracts are a subset of the class of IR -contracts, were it the case that an IR -contract path existed to implement , this would imply that was not the unique IR -contract path. We have, however, proved that is unique, and part (c) of the theorem follows.

We obtain a similar development of Corollary 1 in

Corollary 3   For all , , and each of the cases below,
a.
holds if and only if is a cooperatively rational -contract.
holds if and only if is cooperatively rational.
b.
holds if and only if is is an equitable -contract.
holds if and only if is is equitable.
there is a resource allocation setting and a -deal for which

Proof. As with the proof of Corollary 1 in relation to Theorem 3, in each case we employ the contract path from the proof of Theorem 6, varying the definition of in order to establish each result. Thus let

be the -contract path realising the -deal described in the proof of Theorem 6, this path having length .
a.
The utility functions of Theorem 6 ensure that is cooperatively rational and that is a cooperatively rational -contract path realising : the utility held by never decreases in value and there is at least one agent (in fact exactly ) whose utility increases in value. Furthermore is the unique cooperatively rational -contract path realising since, by the same argument used in Theorem 6, any deviation will result in some agent suffering a loss of utility.
b.
Set the utility functions as,

To see that these choices admit as an equitable -contract path realising the equitable deal , we first note that

thus, is indeed equitable. Consider any deal occurring within . It suffices to show that

since , and for all other agents . We have two possibilities: (in which case and ); (in which case ). Consider the first of these: , however,

and hence every deal forming part of is equitable.

In the remaining case, and

and thus the remaining deals within are equitable. By a similar argument to that employed in Theorem 6 it follows that is the unique equitable -contract path realising .

Subsections

Next: Monotone Utility Functions and M(k)-contract paths Up: Extremal Behaviour in Multiagent Contract Negotiation Previous: O-contract Paths - Monotone
Paul Dunne 2004-11-26