Our main result on -contract paths is the following development of Theorem 3.
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
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
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
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.
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
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 .
The utility function is now given, for
, by
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
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
In the remaining case,
and