-contract Paths - Unrestricted Utility Functions

*Proof.* Consider a path
in
,
with the following property^{4}

e.g. if then

is such a path as it corresponds to the sequence .

Choose
to be a *longest* such path with this property that could be formed
in
, letting
be the sequence of allocations
with
.
We now define the utility functions and so that for
,

With this choice, the contract path describes the

That it is unique follows from the fact that for all and , the deal is not an -contract (hence there are no ``short-cuts'' possible), and for each there is exactly one IR -contract that can follow it, i.e. .

From the preceding argument it follows that any lower bound on the length of , i.e. a sequence satisfying the condition (SC), is a lower bound on . These paths in were originally studied in [Kautz, 1958] in the context of coding theory and the lower bound on their length of established in [Abbott & Katchalski, 1991].

in the resource allocation setting , if the utility functions are specified as in Table 1 below then and . Furthermore, describes the unique IR -contract path realising the reallocation

- a.
- is
*cooperatively rational*if for every agent, , and there is at least one agent, , for whom . - b.
- is
*equitable*if . - c.
- is a
*Pigou-Dalton deal*if , and (where is absolute value).

Using the same -contract path constructed in Theorem 3, we need only vary the definitions of the utility functions employed in order to obtain,

- 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 an equitable -contract.

holds if and only if is equitable. - c.
- holds if and only if is a Pigou-Dalton -contract.

holds if and only if is a Pigou-Dalton deal.

*Proof.* We employ exactly the same sequence of allocations described in the proof of
Theorem 3 but modify the utility functions
for each case.

- a.
- Choose
with for all
and

The resulting -contract path is cooperatively rational: the utility enjoyed by remains constant while that enjoyed by increases by with each deal. Any deviation from this contract path (employing an alternative -contract) will result in a loss of utility for . - b.
- Choose
with
and

The -contract path is equitable: both and increase their respective utility values by with each deal. Again, any -contract deviating from this will result in both agents losing some utility. - c.
- Choose
as

which violates one of the conditions required of Pigou-Dalton deals.

The construction for two agent settings, easily extends to
larger numbers.

*Proof.* Fix allocations in which is given , allocated
, and assigned
for each . Using identical utility functions
as in each of the previous cases, we employ for :
, whenever
(
as in Theorem 3);
for all (Corollary 1(a));
,
whenever
(Corollary 1(b)); and, finally,
for all , (Corollary 1(c)). Considering a realisation
of the -deal
the only
-contract path admissible is the path defined in the related proofs. This
gives the lower bound stated.

We note, at this point, some other consequences of Corollary 1 with respect to
[Endriss & Maudet, 2004b, Theorems 1, 3], which state

- a.
- If
is
*any*maximal path of*cooperatively rational*deals then is Pareto optimal. - b.
- If
is
*any*maximal path of*equitable*deals then maximises the value , i.e. the so-called*egalitarian social welfare*.