%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%  Extremal Behaviour in Multiagent Contract Negotiation
%
% Paul E. Dunne
% Version 1: 28/11/03
% Version 2: 11/12/03
% Version 3: 07/01/04 (Final submitted)
% Version 4: 16/04/04 (First revision pass re. Review comments)
% Version 5: 27/06/04 (further revisions: monotonicity results and M(k) proof)
% Version 6: 16/09/04 (Final revisions)
% Version 7  23/11/04 (Formatting and minor changes)
% Version 8  07/01/05 (pagination)
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\documentstyle[jair,itmath,theapa,11pt]{article}
\def\set#1{\{#1\}}              % \set{1, 2, 3} produces {1, 2, 3}
\def\seq#1{#1^{*}}              % \seq{S} produces S*
\def\tuple#1{\langle#1\rangle}  % \tuple{1, 2, 3} produces <1, 2, 3>
\def\to{\rightarrow}            % produces ->
\def\owr{\dagger}               % function overriding (a symbol from VDM)
% quantifiers
\def\A{\forall}                 % produces upside down A
\def\E{\exists}                 % produces upside down E
% logical connectives
\def\Not{\neg}                  % produces ~
\def\And{\wedge}                % produces ^
\def\AND{\bigwedge}             % produces big ^
\def\Or{\vee}                   % produces v
\def\OR{\bigvee}                % produces big v
\def\Implies{\Rightarrow}       % produces =>
\let\implies=\Rightarrow
\def\Iff{\Leftrightarrow}       % produces <=>
\let\biimplies=\Leftrightarrow
\def\true{\mbox{{\bf true}}}
\def\false{\mbox{{\bf false}}}
% set theory
\def\pset{\wp}                  % powerset
\def\union{\cup}                % set union
\def\inter{\cap}                % set intersection
\def\Union{\bigcup}             % big set union
\def\Inter{\bigcap}             % big set intersection
% domain & range
\def\dom{\mbox{dom\ }}
\def\ran{\mbox{ran\ }}
% standard sets
\def\Nat{I\!N}                  % natural numbers
\def\Real{I\!R}                 % reals
%\def\qsat2{\mbox{{\sc qsat}}_2}
\newtheorem{defn}{Definition}
\newtheorem{exam}{Example}
\newtheorem{thm}{Theorem}
\newtheorem{lem}{Lemma}
\newtheorem{cor}{Corollary}
\newtheorem{fct}{Fact}
\newtheorem{fact}{Fact}
\newtheorem{question}{Question}
\newtheorem{problem}{Problem}
\newtheorem{claim}{Claim}
\newenvironment{proof}{\par\vspace*{0.5ex}\noindent\rm {\em Proof.} }%
{{\hfill\tiny$\Box$}\par\vspace*{1ex}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%555
% Header Information
\jairheading{23}{2005}{41--78}{07/04}{01/05}
\firstpageno{41}
\ShortHeadings{Extremal Behaviour in Multiagent Contract Negotiation}{Dunne}
%\ShortHeadings{short title}{short authors}
\begin{document}
\title{Extremal Behaviour in Multiagent Contract Negotiation}
\author{\name Paul E. Dunne \email {ped@csc.liv.ac.uk} \\
        \addr Department of Computer Science\\
        The University of Liverpool, Liverpool, UK}
\researchnote
\maketitle

\begin{abstract}
We examine properties of a model of resource allocation in which several 
agents exchange resources in order to optimise their individual holdings.
The schemes discussed relate to well-known negotiation protocols proposed in earlier work 
and we consider a number of alternative notions of ``rationality'' covering both
quantitative measures, e.g. cooperative and individual rationality and more qualitative
forms, e.g. Pigou-Dalton transfers.
While it is known that imposing particular rationality and structural restrictions
may result in some reallocations of the resource set becoming unrealisable,
in this paper we address the issue
of the number of restricted rational deals that may be required to implement a
particular reallocation when it {\em is} possible to do so. We construct examples showing
that this number may be exponential (in the number of resources $m$), even when
all of the agent utility functions are monotonic. We further
show that $k$ agents may achieve in a single deal a reallocation
requiring exponentially many rational deals if at most $k-1$ agents can participate, this
same reallocation being unrealisable by any sequences of rational deals in which at most
$k-2$ agents are involved. 
\end{abstract}
\section{Introduction}
Mechanisms for negotiating allocation of resources within a group of agents form
an important body of work within the study of multiagent systems. Typical abstract
models derive from game-theoretic perspectives in economics and among the issues that
have been addressed are strategies that agents use to obtain a particular subset of the
resources available, e.g.  \cite{Kraus:2001,RZ:1994,sandholm:99a}, and protocols 
by which the process of settling upon some allocation of resources among the agents involved is agreed, e.g.
\shortcite{Dignum:2000,dunne:2003a,dunne:2003b,mcburney-et-al:2002}.

The setting we are concerned with is encapsulated in the following definition.
\begin{defn}\label{defn:setting}
A {\em resource allocation setting} is defined by a triple
$\tuple{{\mathcal A},{\mathcal R},{\mathcal U}}$ where
\[
{\mathcal A}=\set{A_1,A_2,\ldots,A_n}\ \ \ ;\ \ \ \
{\mathcal R}=\set{r_1,r_2,\ldots,r_m}
\]
are, respectively, a set of (at least two) agents and a collection of (non-shareable) resources.
A {\em utility function}, $u$, is a mapping from subsets of ${\mathcal R}$ to rational values.
Each agent $A_i\in{\mathcal A}$ has associated with it a particular utility function $u_i$,
so that ${\mathcal U}$ is $\tuple{u_1,u_2,\ldots,u_n}$.
An {\em allocation} $P$ of ${\mathcal R}$ to ${\mathcal A}$ is a partition
$\tuple{P_1,P_2,\ldots,P_n}$ of ${\mathcal R}$. The value $u_i(P_i)$ is called
the {\em utility} of the resources assigned to $A_i$.  A utility function, $u$, is {\em monotone}
if whenever $S\subseteq T$ it holds that $u(S)\leq u(T)$, i.e. the value assigned by $u$ to any
set of resources, $T$, is never less than the value $u$ attaches to any subset, $S$ of $T$.
\end{defn}
Two major applications in which the abstract view of Definition~\ref{defn:setting} has been
exploited are e-commerce and distributed task realisation. In the first ${\mathcal R}$ represents
some collection of commodities offered for sale and individual agents seek to 
acquire a subset of these, the ``value'' an agent attaches to a specific set  being described
by that agent's utility function. In task planning, the ``resource'' set describes
a collection of sub-tasks to be performed in order to realise some complex task, e.g.
the ``complex task'' may be to transport goods from a central warehouse to some set of cities. In this
example ${\mathcal R}$ describes the locations to which goods must be dispatched and a given allocation
defines those places to which an agent must arrange deliveries. The utility functions in such
cases model the cost an agent associates with carrying out its alloted sub-tasks.

Within the very general context of Definition~\ref{defn:setting}, a number of issues arise
stemming from the observation that it is unlikely that some {\em 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 {\em quantitative} or {\em qualitative} in nature.
As an example of the former we have the approach wherein the ``value'' of
an allocation $P$ is simply the sum of the values given
by the agents' utility functions to the subsets of ${\mathcal R}$ they have been apportioned within
$P$, i.e. $\sum_{i=1}^{n} u_i(P_i)$: 
this is the so-called {\em utilitarian social welfare}, which to avoid repetition
we will denote by $\sigma_u(P)$. A natural aim for agents within a commodity trading context
is to seek an allocation under which $\sigma_u$ is {\em maximised}. One example of a {\em qualitative}
criterion is ``{\em envy freeness}'': informally, an allocation, $P$, is envy-free if no agent assigns
greater utility to the resource set ($P_j$) held by another agent than it does with respect to
the resource set ($P_i$) it has actually been allocated,
i.e. for each distinct pair $\tuple{i,j}$, $u_i(P_i)\geq u_i(P_j)$.

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. 
\shortcite{dunne:2003,Endriss-et-al:2003,Endriss-et-al:2003a,Sandholm:1998,sandholm:99a} deriving
from the work of \citeA{Smith:1980}; and ``combinatorial auctions'', 
e.g.
\shortcite[amongst others]{Parkes-Ungar:2000a,Parkes-Ungar:2000b,Sandholm:2001,Sandholm:2002,Sandholm:2003,Tennenholz:2000,Yokoo-et-al:2004}.
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 {\em bids} -- pairs $\tuple{S_j,p_j}$ wherein
$S_j$ is some subset of the available resources and $p_j$ the price agent $A_j$ is prepared to
pay in order to acquire $S_j$. 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 {\em contract-net} (in its most general instantiation) for scenarios of $m$ resources
distributed among $n$ agents is the complete directed graph with $n^m$ vertices (each of which is associated
with a distinct allocation). In this way a possible deal $\tuple{P,Q}$ is represented as an
edge directed from the vertex labelled with $P$ to that labelled $Q$. 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 {\em immediate} improvement from its own perspective.
In such cases, the process of moving from the initial allocation, $P_{init}$, to the eventual
reallocation $P_{fin}$ is by a sequence of local {\em rational} deals, e.g. an agent might refuse
to accept deals which reduced $\sigma_u$ 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 $A_j$ offers a single resource to another agent $A_j$ then
the rational reallocation $\tuple{P_{init},P_{fin}}$ can {\em always} be implemented; if, however,
every single move must be ``rational'' then $\tuple{P_{init},P_{fin}}$ 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 $\tuple{P,Q}$ under they might incur a loss of utility)
despite the prospect of a ``long-term gain'' (assuming $\sigma_u(P_{fin})>\sigma_u(P_{init})$ 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.
\begin{quote}
A reallocation of resources is agreed over a sequence of stages, each of which involves communication
between two agents, $A_i$ and $A_j$. This communication consists of $A_i$ issuing a proposal to $A_j$
of the form $(buy,r,p)$, offering to purchase $r$ from $A_j$ for a payment of $p$; or
$(sell,r,p)$, offering to transfer $r$ to $A_j$ in return for a payment $p$.
The response from $A_j$ is simply $accept$ (following which the deal is implemented) or $reject$.
\end{quote}
This, of course, is a very simple negotiation structure, however consider its operation within
a two agent setting in which one agent, $A_1$ say, wishes to bring about an allocation $P_{fin}$
(and thus can devise a plan -- sequence of deals -- to realise this from an initial allocation $P_{init}$)
while the other agent, $A_2$, does {\em not} know $P_{fin}$. In addition, assume that $A_1$ is the
only agent that makes proposals and that a final allocation is fixed either when $A_1$
is ``satisfied'' or as soon as $A_2$ {\em rejects} any offer.
 
While $A_2$ {\em could} be better off if $P_{fin}$ is realised, it may be the case that
the only proposals $A_2$ will accept are those under which it does not lose, 
e.g. some agents may be sceptical about the {\em 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 $A_2$ may lose utility
but no further proposals are made by $A_1$ so that the loss is ``permanent''. We note that even if we enrich
the basic protocol so that $A_1$ can describe $P_{fin}$,
$A_2$ 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 $A_2$ 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, $A_2$ may reject a
proposal to accept some resource, $r$, since $r$ is only ``useful'' following a further
sequence of deals: if this number of further deals is ``small'' then $A_2$ could decide
to accept the proposed deal since it has sufficient computational power to determine that there is 
a context in which $r$ is of value; if this number is ``large'' however, then $A_2$ may lack
sufficient power to scan the search space of future possibilities that would allow it to
accept $r$. Notice that in the extreme case, $A_2$ makes its decision solely on whether
$r$ is of immediate use, i.e. $A_2$ is myopic. A more powerful $A_2$ may be able to consider
whether $r$ is useful should up to $k$ further deals take place: in this case,
$A_2$ could still refuse to accept $r$ since, although of use, $A_2$ cannot determine this
with a bounded look ahead.

In total for the scenario we have described, if $A_1$ wishes to bring about an allocation
$P_{fin}$ then faced with the view adopted by $A_2$ and the limitations imposed by the deal
protocol, the only ``effective plan'' that $A_1$ could adopt is to find a sequence of
{\em rational} deals to propose to $A_2$.

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
a reallocation $\tuple{P,Q}$ must involve exponentially many (in $|{\mathcal R}|$) separate
stages.
We refine these ideas in the next sub-section. 
\subsection{Preliminary Definitions}
To begin, we first formalise the concepts of
{\em deal} and {\em contract path}.
\begin{defn}\label{defn:deal}
Let $\tuple{{\mathcal A},{\mathcal R},{\mathcal U}}$ be a resource allocation setting.
A {\em deal} is a pair $\tuple{P,Q}$ where
$P=\tuple{P_1,\ldots,P_n}$ and $Q=\tuple{Q_1,\ldots,Q_n}$ are distinct partitions of ${\mathcal R}$.
The effect of implementing the deal $\tuple{P,Q}$ is that the allocation of resources
specified by $P$ is replaced with that specified by $Q$.
Following the notation of \shortcite{Endriss-et-al:2003a} for a deal $\delta=\tuple{P,Q}$, we use
${\mathcal A}^\delta$ to indicate the subset of ${\mathcal A}$ involved, i.e.
$A_k\in{\mathcal A}^\delta$ if and only if $P_k\not=Q_k$.
 
Let $\delta=\tuple{P,Q}$ be a deal. A {\em contract path realising} $\delta$ is a sequence of allocations\[
\Delta=\tuple{P^{(1)},\ P^{(2)}\ ,\ldots,\ P^{(t-1)},\ P^{(t)}}
\]
in which $P=P^{(1)}$ and $P^{(t)}=Q$.
The {\em length} of $\Delta$, denoted $|\Delta|$ is $t-1$, i.e. the number of {\em deals} in $\Delta$.
\end{defn}
There are two methods which we can use to reduce the number of deals that a single agent may
have to consider in seeking to move from some allocation to another, thereby avoiding the need
to choose from exponentially many alternatives: {\em structural} and {\em rationality} constraints.
Structural constraints limit the permitted deals to those which bound the number of resources and/or
the number of agents involved, but take no consideration of the view
any agent may have as to whether its allocation has improved. In contrast, rationality constraints
restrict deals $\tuple{P,Q}$ to those in which $Q$ ``improves'' upon $P$ according to particular
criteria. In this article we consider two classes of structural constraint: $O$-contracts, defined
and considered in \cite{Sandholm:1998}, and what we shall refer to as $M(k)$-contracts.
\begin{defn}\label{defn:con-types}
Let $\delta=\tuple{P,Q}$ be a deal involving a reallocation of ${\mathcal R}$ among ${\mathcal A}$.
\begin{enumerate}
\item[a.]
$\delta$ is a {\em one contract} ($O$-contract) if
\begin{enumerate}
\item[O1.]
${\mathcal A}^\delta=\set{i,j}$.
\item[O2.]
There is a unique resource $r\in P_i\cup P_j$ for which
$Q_i = P_i\cup \set{r}$ and $Q_j=P_j\setminus\set{r}$ (with $r\in P_j$)
or
$Q_j = P_j\cup \set{r}$ and $Q_i=P_i\setminus\set{r}$ (with $r\in P_i$)
\end{enumerate}
\item[b.]
For a value $k\geq2$,
the deal $\delta=\tuple{P,Q}$ is an $M(k)$-{\em contract} if $2\leq|{\mathcal A}^\delta|\leq k$ and
$\cup_{i\in{\mathcal A}^\delta}\ Q_i\ =\ \cup_{i\in{\mathcal A}^\delta}\ P_i$.
\end{enumerate}
\end{defn}
Thus, $O$-contracts involve the transfer of {\em exactly one} resource from a particular agent
to another, resulting in the number of deals compatible with any given allocation
being exactly $(n-1)m$: each of the $m$ resources can be reassigned from its current owner to any
of the other $n-1$ agents.
 
Rationality constraints arise in a number of different ways. For example,
from the standpoint of an individual agent $A_i$ a given deal $\tuple{P,Q}$ may have three different
outcomes: $u_i(P_i)<u_i(Q_i)$, i.e.
$A_i$ values the allocation $Q_i$ as superior to $P_i$; $u_i(P_i)=u_i(Q_i)$, i.e. $A_i$ is indifferent between $P_i$ and $Q_i$; and $u_i(P_i)>u_i(Q_i)$, i.e. $A_i$ is worse off after the deal.
When global optima such as utilitarian social welfare are to be maximised, there is the question of
what incentive there is for any agent to accept a deal $\tuple{P,Q}$ under which it is
left with a less valuable resource holding. The standard approach to this latter question
is to introduce the notion of a {\em pay-off} function, i.e.
in order for $A_i$ to accept a deal under which it suffers a reduction in utility,
$A_i$ receives some payment sufficient to compensate for its loss. Of course such compensation
must be made by other agents in the system who in providing it do not wish to pay
in excess of any gain. In defining notions of pay-off the interpretation
is that in any transaction each agent $A_i$ makes a payment, $\pi_i$: if $\pi_i<0$ then $A_i$
is given $-\pi_i$ in return for accepting a deal; if $\pi_i>0$ then $A_i$ contributes $\pi_i$
to the amount to be distributed among those agents whose pay-off is negative.
 
This notion of ``sensible transfer'' is captured by the concept of {\em individual rationality}, and
is often defined in terms of an appropriate pay-off vector existing. It is not difficult,
however, to show that such definitions are equivalent to the following.
\begin{defn}\label{defn:IR}
A deal $\tuple{P,Q}$ is {\em individually rational} (IR) if and only if $\sigma_u(Q)>\sigma_u(P)$.
\end{defn}
We shall consider alternative bases for rationality constraints later: these
are primarily of interest within so-called {\em money free} settings
(so that compensatory payment for a loss in utility is not an option).

The central issue of interest in this paper concerns the properties of the contract-net graph
when the allowed deals must satisfy both a structural {\em and} a rationality
constraint. Thus, if we consider arbitrary predicates $\Phi$ on deals $\tuple{P,Q}$ -- where the
cases of interest are $\Phi$ combining a structural and rationality condition -- we have,
\begin{defn}
For $\Phi$ a predicate over distinct pairs of allocations,
a contract path
\[
\tuple{P^{(1)},\ P^{(2)}\ ,\ldots,\ P^{(t-1)},\ P^{(t)}}
\]
realising $\tuple{P,Q}$ is a $\Phi$-{\em path}
if for each $1\leq i < t$, $\tuple{P^{(i)},P^{(i+1)}}$ is a $\Phi$-{\em deal}, that is
$\Phi(P^{(i)},P^{(i+1)})$ holds.
We say that $\Phi$ is {\em complete} if any deal $\delta$ may be realised by a $\Phi$-path.
We, further, say that $\Phi$ is {\em complete with respect to} $\Psi$-{\em deals} 
(where $\Psi$ is a predicate over distinct pairs of allocations) if any deal $\delta$ for which 
$\Psi(\delta)$ holds may be realised by a $\Phi$-path.
\end{defn}
The main interest in earlier studies of these ideas has been in areas such
as identifying necessary and/or sufficient conditions on deals to be complete with respect to particular
criteria, e.g. \cite{Sandholm:1998}; and in establishing ``convergence'' and termination
properties, e.g. \shortciteA{Endriss-et-al:2003,Endriss-et-al:2003a} consider deal types, $\Phi$, such that
every maximal\footnote{``Maximal'' in the sense that if $\tuple{P^{(1)},\ldots,P^{(t)}}$
is such a path, then for every allocation, $Q$, $\Phi(P^{(t)},Q)$ does not hold.} $\Phi$-path
ends in a Pareto optimal allocation, i.e. one in which any reallocation under which
some agent improves its utility will lead to another agent suffering a loss.
\citeA{Sandholm:1998} examines how restrictions
e.g. with $\Phi(P,Q)=\top$ if and only if $\tuple{P,Q}$ is an $O$-contract, may affect the existence
of contract paths to realise deals. Of particular interest, from the viewpoint of
heuristics for exploring the contract-net graph, are cases where $\Phi(P,Q)=\top$ if and only if
the deal $\tuple{P,Q}$ is individually rational. For the case of $O$-contracts the following are known:
\begin{thm}\label{thm:sandholm}
$\ \ \ $
\begin{enumerate}
\item[a.]
$O$-contracts are complete.
\item[b.]
IR $O$-contracts are {\em not} complete with respect to IR deals.
\end{enumerate}
\end{thm}
In the consideration of algorithmic and complexity issues
presented in \shortcite{dunne:2003} one difficulty with attempting to formulate reallocation
plans by rational $O$-contracts is already apparent, that is:
\begin{thm}\label{thm:dunne}
Even in the case $n=2$ and with monotone utility functions
the problem of deciding if an IR $O$-contract path exists to realise the IR deal
$\tuple{P,Q}$ is {\sc np}--hard.
\end{thm}
Thus deciding if any rational plan is possible is already computationally hard. In this article
we demonstrate that, even if an appropriate rational plan exists, in extreme cases, there may be
significant problems: the number of deals required could be exponential in the number
of resources, so affecting both the time it will take for the schema outlined to conclude and
the space that an agent will have to dedicate to storing it.
Thus in his proof of Theorem~\ref{thm:sandholm} (b), Sandholm observes that when an IR $O$-contract
path exists for a given IR deal, it may be the case that its length exceeds $m$, i.e. some
agent passes a resource to another and then accepts the same resource at a later stage.

The typical form of the results that we derive can be summarised as:
\begin{quote}
For $\Phi$ a structural constraint ($O$-contract or $M(k)$-contract) and
$\Psi$ a rationality constraint, e.g.  $\Psi(P,Q)$ holds if $\tuple{P,Q}$ is individually rational,
there are resource allocation settings $\tuple{{\mathcal A}_n,{\mathcal R}_m,{\mathcal U}}$ in which
there is a deal $\tuple{P,Q}$ satisfying all of the following.
\begin{enumerate}
\item[a.]
$\tuple{P,Q}$ is a $\Psi$-deal.
\item[b.]
$\tuple{P,Q}$ can be realised by a contract path on which every deal satisfies the structural
constraint $\Phi$ {\em and} the rationality constraint $\Psi$.
\item[c.]
Every such contract path has length at least $g(m)$.
\end{enumerate}
\end{quote}
For example, we show
that there are instances for which the shortest IR $O$-contract path has length exponential in
$m$.\footnote{\citeA{Sandholm:1998} gives an upper bound on the length of such paths which is also
exponential in $m$, but does not explicitly state any lower bound other than that already
referred to.}
In the next section we will be interested in lower bounds on the values of the following functions:
we introduce these in general terms to avoid unnecessary subsequent repetition.
\begin{defn}\label{defn:phi-psi-path}
Let $\tuple{{\mathcal A},{\mathcal R},{\mathcal U}}$ be a resource allocation setting.
Additionally let $\Phi$ and $\Psi$ be two predicates on deals. For a deal $\delta=\tuple{P,Q}$
the partial function $L^{{\rm opt}}(\delta,\tuple{{\mathcal A},{\mathcal R},{\mathcal U}},\Phi)$ 
is the length of the {\em shortest} $\Phi$-contract path realising $\tuple{P,Q}$ if such a
path exists (and is undefined if no such path is possible). The partial function 
$L^{\max}(\tuple{{\mathcal A},{\mathcal R},{\mathcal U}},\Phi,\Psi)$ is
\[
L^{\max}(\tuple{{\mathcal A},{\mathcal R},{\mathcal U}},\Phi,\Psi)\ =\ 
\max_{\mbox{$\Psi$-deals $\delta$}}\ L^{{\rm opt}}(\delta,\tuple{{\mathcal A},{\mathcal R},{\mathcal U}},\Phi)
\]
Finally, the partial function $\rho^{\max}(n,m,\Phi,\Psi)$ is
\[
\rho^{\max}(n,m,\Phi,\Psi)\ =\
\max_{{\mathcal U}=\tuple{u_1,u_2,\ldots,u_n}}\ \ 
L^{\max}(\tuple{{\mathcal A}_n,{\mathcal R}_m,{\mathcal U}},\Phi,\Psi)
\]
where consideration is restricted to those $\Psi$-deals $\delta=\tuple{P,Q}$ for which a realising
$\Phi$-path exists.
\end{defn}
The three measures, $L^{{\rm opt}}$, $L^{\max}$ and $\rho^{\max}$ distinguish different aspects
regarding the length of contract-paths. The function $L^{{\rm opt}}$ is concerned with $\Phi$-paths
realising a single deal
$\tuple{P,Q}$ in a given resource allocation setting $\tuple{{\mathcal A},{\mathcal R},{\mathcal U}}$: the
property of interest being the number of deals in the {\em shortest}, i.e. optimal length, $\Phi$-path. 
We stress that $L^{{\rm opt}}$ is a {\em partial} function whose value is undefined in the event
that $\tuple{P,Q}$ cannot be realised by a $\Phi$-path in the 
setting $\tuple{{\mathcal A},{\mathcal R},{\mathcal U}}$. 
The function $L^{\max}$ is defined in terms of $L^{{\rm opt}}$, again in the context of a specific
resource allocation setting. The behaviour of interest for $L^{\max}$, however, is not simply the length
of $\Phi$-paths realising a specific $\tuple{P,Q}$ but the ``worst-case'' value of $L^{{\rm opt}}$ for
deals which are $\Psi$-deals. 
We note the qualification that $L^{\max}$ is defined only for
$\Psi$-deals that {\em are} capable of being realised by $\Phi$-paths, 
and thus do not consider cases for which no appropriate
contract path exists. Thus, if it should be the case that no $\Psi$-deal in the setting
$\tuple{{\mathcal A},{\mathcal R},{\mathcal U}}$ can be realised by a $\Phi$-path then
the value $L^{\max}(\tuple{{\mathcal A},{\mathcal R},{\mathcal U}},\Phi,\Psi)$ is undefined, i.e. 
$L^{\max}$ is also a partial function. We may interpret any {\em upper} bound on $L^{\max}$
in the following terms: if $L^{\max}(\tuple{{\mathcal A},{\mathcal R},{\mathcal U}},\Phi,\Psi)\leq K$ then
any $\Psi$-deal {\em for which a} $\Phi$-{\em path exists} can be realised by a $\Phi$-path of length
at most $K$. 

Our main interest will centre on $\rho^{\max}$ which is concerned with the behaviour 
of $L^{\max}$ as a function of $n$ and $m$ and ranges over {\em all} $n$-tuples of utility
functions $\tuple{u\mbox{ : }2^{\mathcal R}\ \rightarrow\ {\bf Q}}^n$. Our approach to obtaining
lower bounds for this function is {\em constructive}, i.e. for each $\tuple{\Phi,\Psi}$ that is
considered, we show how the utility functions ${\mathcal U}$ may be defined in a setting with $m$ resources
so as to yield a lower bound on $\rho^{\max}(n,m,\Phi,\Psi)$. In contrast to the measures
$L^{{\rm opt}}$ and $L^{\max}$, the function $\rho^{\max}$ is not described in terms of a single fixed
resource allocation setting. It is, however, still a {\em partial} function: depending on $\tuple{n,m,\Phi,\Psi}$
it may be the case that in {\em every} $n$ agent, $m$ resource allocation setting, regardless of
which choice of utility functions is made, there is no $\Psi$-deal, $\tuple{P,Q}$ capable of
being realised by $\Phi$-path, and for such cases the value of 
$\rho^{\max}(n,m,\Phi,\Psi)$ will be undefined.\footnote{In recognising the {\em possibility} that
$\rho^{\max}(n,m,\Phi,\Psi)$ could be undefined, we are {\em not} claiming that such behaviour arises
with any of the instantiations of $\tuple{\Phi,\Psi}$ considered subsequently: in fact it will be
clear from the constructions that, denoting by $\rho_{\Phi,\Psi}^{\max}(n,m)$ the function
$\rho^{\max}(n,m,\Phi,\Psi)$ for a fixed instantiation of $\tuple{\Phi,\Psi}$, with the restricted deal types
and rationality conditions examined, the function
$\rho_{\Phi,\Psi}^{\max}(n,m)$ is a {\em total} function.
Whether it is possible to formulate ``sensible'' choices of $\tuple{\Phi,\Psi}$ with which 
$\rho_{\Phi,\Psi}^{\max}(n,m)$ is undefined for some values of $\tuple{n,m}$ (and, if so, demonstrating
examples of such) is, primarily, only a question of combinatorial interest, whose development is
not central to the concerns of the current article.}

It is noted, at this point, that the definition of $\rho^{\max}$ allows {\em arbitrary}
utility functions to be employed in constructing ``worst-case'' instances. While this is reasonable
in terms of general lower bound results, as will be apparent from the given constructions the utility
functions actually employed are highly artificial (and unlikely to feature in ``real'' application settings).
We shall attempt to address this objection by further considering bounds on the following variant of
$\rho^{\max}$: 
\[
\rho^{\max}_{{\rm mono}}(n,m,\Phi,\Psi)\ =\
\max_{{\mathcal U}=\tuple{u_1,u_2,\ldots,u_n}\mbox{ : each $u_i$ is monotone}}\ \ 
L^{\max}(\tuple{{\mathcal A}_n,{\mathcal R}_m,{\mathcal U}},\Phi,\Psi)
\]
Thus, $\rho^{\max}_{{\rm mono}}$ deals with resource allocation settings within which all of the
utility functions must satisfy a monotonicity constraint.

The main results of this article are presented in the next sections. We consider two general
classes of contract path: $O$-contract paths under various rationality conditions in
Section~\ref{section:o-contract}; and, similarly, 
$M(k)$-contract paths
for arbitrary values of $k\geq2$ in Section~\ref{section:mk-results}. 
Our results are concerned with the construction of
resource allocation settings $\tuple{{\mathcal A},{\mathcal R}_m,{\mathcal U}}$ for which given
some rationality requirement, e.g. that deals be individually rational, there is some deal $\tuple{P,Q}$
that satisfies the rationality condition, can be realised by a rational $O$-contract path (respectively,
$M(k)$-contract path), but with the number of deals required by such paths being exponential in $m$.
We additionally obtain slightly weaker (but still exponential) lower bounds for rational $O$-contract paths
within settings of monotone utility functions, i.e. for the measure $\rho^{\max}_{{\rm mono}}$, outlining how
similar results may be derived for $M(k)$-contract paths.

In the resource allocation settings constructed for demonstrating these properties 
with $M(k)$-contract paths, the constructed deal $\tuple{P,Q}$ is realisable with
a {\em single} $M(k+1)$-contract but unrealisable by any {\em rational} $M(k-1)$-contract path.
We discuss related work, in particular the recent study of \shortcite{Endriss-et-al:2004}
that addresses similar issues to those considered in the present article, in Section~\ref{section:related-work}.
Conclusions and some directions for further work are presented in the final section.
\section{Lower Bounds on Path Length -- $O$-contracts}\label{section:o-contract}
In this section we consider the issue of contract path length when the structural restriction
requires individual deals to be $O$-contracts. We first give an overview of the construction method, with
the following subsections analysing the cases of unrestricted utility functions and, subsequently,
{\em monotone} utility functions.
\subsection{Overview}\label{subsection:overview}
The strategy employed in proving our results involves two parts: for a given
class of restricted contract paths we proceed as follows in obtaining
lower bounds on $\rho^{\max}(n,m,\Phi,\Psi)$.
\begin{enumerate}
\item[a.]
For the contract-net graph partitioning $m$ resources among $n$ agents, construct a path, 
$\Delta_m=\tuple{P^{(1)},~P^{(2)}~,\ldots,~P^{(t)}}$
realising a deal $\tuple{P^{(1)},P^{(t)}}$. For the
{\em structural} constraint, $\Phi'$ influencing $\Phi$ it is then proved that:
\begin{enumerate}
\item[a1.]
The contract path $\Delta_m$ {\em is} a $\Phi'$-path, i.e. for each $1\leq i < t$, the deal
$\tuple{P^{(i)},P^{(i+1}}$ satisfies the structural constraint $\Phi'$.
\item[a2.]
For any pair of allocations $P^{(i)}$ and $P^{(i+j)}$ occurring in $\Delta_m$, if $j\geq 2$ then the
deal $\tuple{P^{(i)},P^{(i+j)}}$ is {\em not} a $\Phi'$-deal.
\end{enumerate}
Thus (a1) ensures that $\Delta_m$ is a suitable contract path, while (a2) will guarantee that there
is exactly one allocation, $P^{(i+1)}$, that can be reached {\em within} $\Delta_m$ from any given
allocation $P^{(i)}$ in $\Delta_m$ by means of a $\Phi'$-deal.
\item[b.]
Define utility functions ${\mathcal U}_n=\tuple{u_1,\ldots,u_n}$ with the following properties
\begin{enumerate}
\item[b1.]
The deal $\tuple{P^{(1)},P^{(t)}}$ is a $\Psi$-deal.
\item[b2.]
For the {\em rationality} constraint, $\Phi''$ influencing $\Phi$, every deal
$\tuple{P^{(i)},P^{(i+1)}}$ is a $\Phi''$-deal.
\item[b3.]
For every allocation $P^{(i)}$ in the contract path $\Delta$ and every allocation $Q$ other than
$P^{(i+1)}$ the deal $\tuple{P^{(i)},Q}$ is {\em not} a $\Phi$-deal, i.e. it violates either
the stuctural constraint $\Phi'$ or the rationality constraint $\Phi''$.
\end{enumerate}
Thus, (a1) and (b2) ensure that $\tuple{P^{(1)},P^{(t)}}$ has a defined value with respect to
the function $L^{{\rm opt}}$ for the $\Psi$-deal $\tuple{P^{(1)},P^{(t)}}$, 
i.e. a $\Phi$-path realising the deal is possible. The properties
given by (a2) and (b3) indicate that (within the constructed resource allocation setting) the path
$\Delta_m$ is the {\em unique} $\Phi$-path realising $\tuple{P^{(1)},P^{(t)}}$. It follows that
$t-1$, the length of this path, gives a {\em lower bound} on the value of $L^{\max}$ and hence a
lower bound on $\rho^{\max}(n,m,\Phi,\Psi)$.
\end{enumerate}
Before continuing it will be useful to fix some notational details.

We use ${\mathcal H}_m$ to denote the $m$-dimensional hypercube.
Interpreted as a directed
graph, ${\mathcal H}_m$ has $2^m$ vertices each of which is identified with a distinct $m$-bit
label. Using $\alpha=a_1a_2\ldots a_m$ to denote an arbitrary such label,
the edges of ${\mathcal H}_m$ are formed by
\[
\set{\ \tuple{\alpha,\beta}\mbox{ : $\alpha$ and $\beta$ differ in {\em exactly one} bit position}}
\]
We identify $m$-bit labels
$\alpha=a_1a_2\ldots a_m$ with subsets $S^{\alpha}$ of
${\mathcal R}_m$, via $r_i\in S^{\alpha}$ if and only if $a_i=1$.
Similarly, any subset $S$ of ${\mathcal R}$ can be described by a binary word, $\beta(S)$, of length $m$,
i.e. $\beta(S)=b_1b_2\ldots b_m$ with $b_i=1$ if and only if
$r_i\in S$. For a label $\alpha$ we use $|\alpha|$ to denote the number of bits with
value $1$, so that $|\alpha|$ is the size of the subset $S^{\alpha}$. If
$\alpha$ and $\beta$ are $m$-bit labels, then $\alpha\beta$ is a $2m$-bit
label, so that if ${\mathcal R}_m$ and ${\mathcal T}_m$ are disjoint sets, then $\alpha\beta$
describes the union of the subset $S^{\alpha}$ of ${\mathcal R}_m$ with the subset
$S^{\beta}$ of ${\mathcal T}_m$. Finally if $\alpha=a_1a_2\ldots a_m$ is an $m$-bit
label then $\overline{\alpha}$ denotes the label formed by changing all $0$ values in $\alpha$ to $1$
and {\em vice versa}. In this way, if $S^{\alpha}$ is the subset of ${\mathcal R}_m$ described
by $\alpha$ then $\overline{\alpha}$ describes the set ${\mathcal R}_m\setminus S^{\alpha}$.
To avoid an excess of superscripts we will, where no ambiguity arises, use $\alpha$ both to denote
the $m$-bit label and the subset of ${\mathcal R}_m$ described by it, e.g. we write
$\alpha\subset\beta$ rather than $S^{\alpha}\subset S^{\beta}$.

For $n=2$ the contract-net graph induced by $O$-contracts can be viewed as the $m$-dimensional
hypercube ${\mathcal H}_m$: the $m$-bit label, $\alpha$ associated with a vertex of ${\mathcal H}_m$
describing the allocation $\tuple{\alpha,\overline{\alpha}}$ to $\tuple{A_1,A_2}$. In this way the set of IR
$O$-contracts define a subgraph, 
${\mathcal G}_m$ of ${\mathcal H}_m$ with any directed path from $\beta(P)$ to $\beta(Q)$
in ${\mathcal G}_m$ corresponding to a possible IR $O$-contract path from the allocation
$\tuple{P,{\mathcal R}\setminus P}$ to the allocation $\tuple{Q,{\mathcal R}\setminus Q}$.

\subsection{$O$-contract Paths -- Unrestricted Utility Functions}\label{subsection:O-contracts}
Our first result clarifies one issue in the presentation of \cite[Proposition~2]{Sandholm:1998}: in this
an upper bound that is exponential in $m$ is proved on the length of IR $O$-contract paths, i.e.
in terms of our notation, \cite[Proposition~2]{Sandholm:1998} establishes an upper bound on 
$\rho^{\max}(n,m,\Phi,\Psi)$. We now prove a similar order {\em lower} bound.
\begin{thm}\label{thm:ir-o-bounds}
Let $\Phi(P,Q)$ be the predicate which holds whenever $\tuple{P,Q}$ is an IR $O$-contract and
$\Psi(P,Q)$ that which holds whenever $\tuple{P,Q}$ is IR. For $m\geq 7$
\[
\rho^{\max}(2,m,\Phi,\Psi)\ \geq \left({\frac{77}{256}}\right)\ 2^m\ -\ 2
\]
\end{thm}
\begin{proof}
Consider a path ${\mathcal C}=\tuple{\alpha_1, \alpha_2,\ldots,\alpha_t}$
in ${\mathcal H}_m$, 
with the following property\footnote{This defines the so-called ``snake-in-the-box'' codes 
introduced in \cite{Kautz:1958}.}
\[
\forall\ 1\leq i<j\leq t\ (j\geq i+2)\ \Rightarrow\ (\mbox{$\alpha_i$ and 
$\alpha_j$ differ in at least 2 positions) }\ \ \ \mbox{ (SC)}
\]
e.g. if $m=4$ then
\[
\emptyset,\set{r_1},\ \set{r_1,r_3},\set{r_1,r_2,r_3},\set{r_2,r_3},\set{r_2,r_3,r_4},\set{r_2,r_4},
\set{r_1,r_2,r_4}
\]
is such a path as it corresponds to the sequence $\tuple{0000,1000,1010,1110,0110,0111,0101,1101}$.

Choose ${\mathcal C}^{(m)}$ to be a {\em longest} such path with this property that could be formed
in ${\mathcal H}_m$, letting $\Delta_m=\tuple{P^{(1)},P^{(2)},\ldots,P^{(t)}}$ be the sequence of allocations
with $P^{(i)}=\tuple{\alpha_i,\overline{\alpha_i}}$.
We now define the utility functions $u_1$ and $u_2$ so that for $\gamma\subseteq{\mathcal R}_m$,
\[
u_1(\gamma)+u_2(\overline{\gamma})=
\left\{
{
\begin{array}{lcl}
k&\mbox{ if }&\gamma=\alpha_k\\
0&\mbox{ if }&\gamma\not\in\set{\alpha_1,\alpha_2,\ldots,\alpha_t}
\end{array}
}
\right.
\]
With this choice, the contract path $\Delta_m$ describes the {\em unique} IR $O$-contract path
realising the IR deal 
$\tuple{P^{(1)},P^{(t)}}$: that
$\Delta_m$ is an IR $O$-contract path is immediate, since 
\[
\sigma_u(P^{(i+1)})=i+1 > i=\sigma_u(P^{(i)})
\]
That it is unique follows from the fact that for all $1\leq i\leq t$ and $i+2\leq j\leq t$, the deal
$\tuple{P^{(i)},P^{(j)}}$ is not an $O$-contract
(hence there are no ``short-cuts'' possible), and for each $P^{(i)}$ there is
exactly one IR $O$-contract that can follow it,
i.e. $P^{(i+1)}$.\footnote{In our
example with $m=4$, the sequence $\tuple{0000,1000,1001,1101}$, although defining an $O$-contract path
gives rise to a deal which is not IR, namely that corresponding to $\tuple{1000,1001}$.}

From the preceding argument it follows that any lower bound on the length of ${\mathcal C}^{(m)}$, i.e. a
sequence satisfying the condition (SC), is a lower bound on $\rho^{\max}(2,m,\Phi,\Psi)$.
These paths in ${\mathcal H}_m$ were originally
studied by \citeA{Kautz:1958} in the context of coding theory and the lower bound
on their length of $(77/256)2^m-2$ established in \shortcite{AK:91}.
\end{proof}
\begin{exam}
Using the path 
\[
\begin{array}{lcl}
{\mathcal C}^{(4)}&\mbox{ $=$ }&\tuple{0000,1000,1010,1110,0110,0111,0101,1101}\\
&\mbox{ $=$ }&\tuple{\alpha_1,\alpha_2,\alpha_3,\alpha_4,\alpha_5,\alpha_6,\alpha_7,\alpha_8}
\end{array}
\]
in the resource allocation setting $\tuple{\set{a_1,a_2},\set{r_1,r_2,r_3,r_4},\tuple{u_1,u_2}}$, if the
utility functions are specified as in Table~\ref{tab:example-one} below then 
$\sigma_u(\tuple{\alpha_1,\overline{\alpha}_1})=1$ and $\sigma_u(\tuple{\alpha_8,\overline{\alpha}_8})=8$.
Furthermore, ${\mathcal C}^{(4)}$ describes the unique IR $O$-contract path realising the reallocation
$\tuple{\tuple{\alpha_1,\overline{\alpha}_1},~\tuple{\alpha_8,\overline{\alpha}_8}}$
{\small 
\begin{table}[h]
\begin{tabular}{|c|c|c|c|c|c||c|c|c|c|c|c|}\hline
$S$&${\mathcal R}\setminus S$& $u_1(S)$ & $u_2({\mathcal R}\setminus S)$ & $\sigma_u$ &&
$S$&${\mathcal R}\setminus S$& $u_1(S)$ & $u_2({\mathcal R}\setminus S)$ & $\sigma_u$ &\\ \hline
$0000$&$1111$ & $1$ & $0$ & $1$ & $\alpha_1$ & $1000$&$0111$ & $1$ & $1$ & $2$ & $\alpha_2$ \\ \hline
$0001$&$1110$ & $0$ & $0$ & $0$ & & $1001$&$0110$ & $0$ & $0$ & $0$ &\\ \hline
$0010$&$1101$ & $0$ & $0$ & $0$ & & $1010$&$0101$ & $2$ & $1$ & $3$ & $\alpha_3$ \\ \hline
$0011$&$1100$ & $0$ & $0$ & $0$ & & $1011$&$0100$ & $0$ & $0$ & $0$ &\\ \hline
$0100$&$1011$ & $0$ & $0$ & $0$ & & $1100$&$0011$ & $0$ & $0$ & $0$ &\\ \hline
$0101$&$1010$ & $4$ & $3$ & $7$ & $\alpha_7$ & $1101$&$0010$ & $4$ & $4$ & $8$ & $\alpha_8$ \\ \hline
$0110$&$1001$ & $3$ & $2$ & $5$ & $\alpha_5$ & $1110$&$0001$ & $2$ & $2$ & $4$ & $\alpha_4$ \\ \hline
$0111$&$1000$ & $3$ & $3$ & $6$ & $\alpha_6$ & $1111$&$0000$ & $0$ & $0$ & $0$ &\\ \hline
\end{tabular}
\caption{Utility function definitions for $m=4$ example.}\label{tab:example-one}
\end{table}
}
\end{exam}
There are a number of alternative formulations of ``rationality'' which can also be considered.
For example
\begin{defn}\label{defn:coop-etc}
Let $\delta=\tuple{P,Q}$ be a deal. 
\begin{enumerate}
\item[a.]
$\delta$ is {\em cooperatively rational} if for every agent, $A_i$, $u_i(Q_i)\geq u_i(P_i)$ and there
is at least one agent, $A_j$, for whom $u_j(Q_j)>u_j(P_j)$.
\item[b.]
$\delta$ is {\em equitable} if 
$\min_{i\in{\mathcal A}^\delta} u_i(Q_i) >\min_{i\in{\mathcal A}^\delta} u_i(P_i)$.
\item[c.]
$\delta$ is a {\em Pigou-Dalton deal} if ${\mathcal A}^\delta=\set{i,j}$,
$u_i(P_i)+u_j(P_j)=u_i(Q_i)+u_j(Q_j)$ and $|u_i(Q_i)-u_j(Q_j)|<|u_i(P_i)-u_j(P_j)|$ (where $|\ldots|$ is
absolute value). 
\end{enumerate}
\end{defn}
There are a number of views we can take concerning the rationality conditions
given in Definition~\ref{defn:coop-etc}. One shared feature is that, unlike the concept of
individual rationality for which some provision to compensate agents who suffer a loss in utility
is needed, i.e. individual rationality presumes a ``money-based'' system, the forms defined
in Definition~\ref{defn:coop-etc} allow concepts of ``rationality'' to be given in ``money-free''
enviroments. Thus, in a cooperatively rational deal, no agent involved suffers a loss in utility and
{\em at least one} is better off. It may be noted that given the characterisation of
Definition~\ref{defn:IR} it is immediate that any cooperatively rational deal is perforce
also individually rational; the converse, however, clearly does not hold in general. 
In some settings, an equitable deal may be neither cooperatively nor individually rational. One may
interpret such deals as one method of reducing inequality between the values agents
place on their allocations: for those involved in an equitable deal, it is
ensured that the agent who places least value on their current allocation will obtain
a resource set which is valued more highly. It may, of course, be the case that some agents
suffer a {\em loss} of utility: the condition for a deal to be equitable limits
how great such a loss could be. Finally the concept of Pigou-Dalton deal originates from and has
been studied in depth within the theory of exchange economies. This is one of many approaches
that have been proposed, again in order to describe deals which reduce inequality between
members of an agent society, e.g. \shortcite{Endriss-et-al:2003a}. 
In terms of the definition given, such deals encapsulate the so-called
Pigou-Dalton principle in economic theory: that any transfer of income from a wealthy individual to
a poorer one should reduce the disparity between them. 
We note that, in principle, we could define related rationality concepts based on
several extensions of this principle that have been suggested, e.g. \shortcite{Atkinson:1970,CGW:2002,Kolm:1976}.

Using the same $O$-contract path constructed in Theorem~\ref{thm:ir-o-bounds}, we need only vary the
definitions of the utility functions employed in order to obtain,
\begin{cor}\label{cor:other-rationals}
For each of the cases below,
\begin{enumerate}
\item[a.]
$\Phi(\delta)$ holds if and only if $\delta$ is a cooperatively rational $O$-contract.
\newline
$\Psi(\delta)$ holds if and only if $\delta$ is cooperatively rational.
\item[b.]
$\Phi(\delta)$ holds if and only if $\delta$ is an equitable $O$-contract.
\newline
$\Psi(\delta)$ holds if and only if $\delta$ is equitable.
\item[c.]
$\Phi(\delta)$ holds if and only if $\delta$ is a Pigou-Dalton $O$-contract.
\newline
$\Psi(\delta)$ holds if and only if $\delta$ is a Pigou-Dalton deal.
\end{enumerate}
\[
\rho^{\max}(2,m,\Phi,\Psi)\ \geq\ \left({\frac{77}{256}}\right)2^m\ -\ 2
\]
\end{cor}
\begin{proof}
We employ exactly the same sequence of allocations $\Delta_m$ described in the proof of
Theorem~\ref{thm:ir-o-bounds} but modify the utility functions $\tuple{u_1,u_2}$ for each case.
\begin{enumerate}
\item[a.]
Choose $\tuple{u_1,u_2}$ with $u_2(\gamma)=0$ for all $\gamma\subseteq{\mathcal R}$ and
\[
u_1(\gamma)=\left\{
{
\begin{array}{lcl}
k&\mbox{ if }&\gamma=\alpha_k\\
0&\mbox{ if }&\gamma\not\in\set{\alpha_1,\ldots,\alpha_t}
\end{array}
}
\right.
\]
The resulting $O$-contract path is cooperatively rational: the utility enjoyed by $A_2$ remains constant
while that enjoyed by $A_1$ increases by $1$ with each deal. Any deviation from this
contract path (employing an alternative $O$-contract) will result in a loss of utility for $A_1$.
\item[b.]
Choose $\tuple{u_1,u_2}$ with $u_2(\gamma)=u_1(\overline{\gamma})$ and
\[
u_1(\gamma)=\left\{
{
\begin{array}{lcl}
k&\mbox{ if }&\gamma=\alpha_k\\
0&\mbox{ if }&\gamma\not\in\set{\alpha_1,\ldots,\alpha_t}
\end{array}
}
\right.
\]
The $O$-contract path is equitable: both $A_1$ and $A_2$ increase their respective utility values
by $1$ with each deal. Again, any $O$-contract deviating from this will result in both agents
losing some utility.
\item[c.]
Choose $\tuple{u_1,u_2}$ as
\[
u_1(\gamma)=\left\{
{
\begin{array}{lcl}
k&\mbox{ if }&\gamma=\alpha_k\\
0&\mbox{ if }&\gamma\not\in\set{\alpha_1,\ldots,\alpha_t}
\end{array}
}
\right.\ \ \ ;\ \ \ 
u_2(\gamma)=\left\{
{
\begin{array}{lcl}
2^m-k&\mbox{ if }&\overline{\gamma}=\alpha_k\\
2^m&\mbox{ if }&\overline{\gamma}\not\in\set{\alpha_1,\ldots,\alpha_t}
\end{array}
}
\right.
\]
\end{enumerate} 
To see that the $O$-contract path consists of Pigou-Dalton deals, it suffices to
note that $u_1(\alpha_i)+u_2(\overline{\alpha_i})=2^m$ for each $1\leq i\leq t$. In addition,
$|u_2(\overline{\alpha_{i+1}})-u_1(\alpha_{i+1})|=2^m-2i-2$ which is strictly less than
$|u_2(\overline{\alpha_i})-u_1(\alpha_i)|=2^m-2i$. Finally, any $O$-contract $\tuple{P,Q}$ which deviates from
this sequence will not be a Pigou-Dalton deal since 
\[
|u_2(Q_2)-u_1(Q_1)| = 2^m\ >\ |u_2(P_2)-u_1(P_1)|
\]
which violates one of the conditions required of Pigou-Dalton deals.
\end{proof}
The construction for two agent settings, easily extends to
larger numbers.
\begin{cor}\label{cor:more-than-two}
For each of the choices of $\tuple{\Phi,\Psi}$ considered in Theorem~\ref{thm:ir-o-bounds} and
Corollary~\ref{cor:other-rationals}, and all $n\geq2$,
\[
\rho^{\max}(n,m,\Phi,\Psi)\ \geq\ \left({\frac{77}{256}}\right)2^m\ -\ 2
\]
\end{cor}
\begin{proof}
Fix allocations in which $A_1$ is given $\alpha_1$, $A_2$ allocated $\overline{\alpha_1}$, and $A_j$ assigned
$\emptyset$ for each $3\leq j\leq n$. Using identical utility functions $\tuple{u_1,u_2}$
as in each of the previous cases, we employ for $u_j$: $u_j(\emptyset)=1$, $u_j(S)=0$ whenever $S\not=\emptyset$
($\tuple{\Phi,\Psi}$ as in Theorem~\ref{thm:ir-o-bounds}); 
$u_j(S)=0$ for all $S$ (Corollary~\ref{cor:other-rationals}(a)); $u_j(\emptyset)=2^m$, $u_j(S)=0$ 
whenever $S\not=\emptyset$ (Corollary~\ref{cor:other-rationals}(b)); and, finally,
$u_j(S)=2^m$ for all $S$, (Corollary~\ref{cor:other-rationals}(c)). Considering a realisation
of the $\Psi$-deal $\tuple{P^{(1)},P^{(t)}}$ the only
$\Phi$-contract path admissible is the path $\Delta_m$ defined in the related proofs. This
gives the lower bound stated.
\end{proof}
We note, at this point, some other consequences of Corollary~\ref{cor:other-rationals} with respect to
\shortcite[Theorems~1,~3]{Endriss-et-al:2003a}, which state
\begin{fact}\label{fact:convergent}
We recall that a $\Phi$-path, $\tuple{P^{(1)},\ldots,P^{(t)}}$ is {\em maximal} if for each 
allocation $Q$, $\tuple{P^{(t)},Q}$ is {\em not} a $\Phi$-deal.
\begin{enumerate}
\item[a.]
If $\tuple{P^{(1)},\ldots,P^{(t)}}$ is {\em any} maximal path of {\em cooperatively rational} deals
then $P^{(t)}$ is Pareto optimal.
\item[b.]
If $\tuple{P^{(1)},\ldots,P^{(t)}}$ is {\em any} maximal path of {\em equitable} deals
then $P^{(t)}$ maximises the value $\sigma_e(P)=\min_{1\leq i\leq n} u_i(P_i)$, i.e. the so-called
{\em egalitarian social welfare}.
\end{enumerate}
\end{fact}
The sequence of cooperatively rational deals in Corollary~\ref{cor:other-rationals}(a) terminates
in the Pareto optimal allocation $P^{(t)}$: the allocation for $A_2$ always
has utility $0$ and there is no allocation to $A_1$ whose utility can exceed $t$. Similarly,
the sequence of equitable deals in Corollary~\ref{cor:other-rationals}(b) terminates in the
allocation $P^{(t)}$, for which $\sigma_e(P^{(t)})=t$
the maximum that can be attained for the instance defined. In both cases, however, the optima
are reached by sequences of exponentially many (in $m$) deals: thus, although Fact~\ref{fact:convergent}
guarantees convergence of particular deal sequences to optimal states it may be the
case, as illustrated in Corollary~\ref{cor:other-rationals}(a--b), that the process of convergence
takes considerable time.
\subsection{$O$-contract Paths -- Monotone Utility Functions}
We conclude our results concerning $O$-contracts by presenting a lower bound on $\rho_{{\rm mono}}^{\max}$,
i.e. the length of paths when the utility functions are required to be {\em monotone}.

In principle one could attempt to construct appropriate monotone utility functions that would
have the desired properties with respect to the path used in Theorem~\ref{thm:ir-o-bounds}. It is, however,
far from clear whether such a construction is possible. We do not attempt to resolve this
question here. Whether an exact translation could be 
accomplished is, ultimately, a question of purely combinatorial interest: since 
our aim is to demonstrate that exponential length contract paths are needed with monotone utility
functions we are not, primarily, concerned with obtaining an optimal bound.
\begin{thm}\label{thm:mono-ir-o}
With $\Phi(P,Q)$ and $\Psi(P,Q)$ be defined as in Theorem~\ref{thm:ir-o-bounds} and $m\geq 14$
\[
\rho^{\max}_{{\rm mono}}(2,m,\Phi,\Psi)
~\geq~
\left\{
{
\begin{array}{lcl}
\left({\frac{77}{128}}\right)\ 2^{m/2}~-~3&\mbox{ if }&\mbox{$m$ is even}\\
&&\\
\left({\frac{77}{128}}\right)\ 2^{(m-1)/2}~-~3&\mbox{ if }&\mbox{$m$ is odd}
\end{array}
}
\right.
\]
\end{thm}
\begin{proof}
We describe the details only for the case of $m$ being even: the result when $m$ is odd is obtained
by a simple modification which we shall merely provide in outline.

\noindent
Let $m=2s$ with $s\geq 7$. For any path
\[
\Delta_s~=~\tuple{\alpha_1,\alpha_2,\ldots,\alpha_t}
\]
in ${\mathcal H}_s$ (where $\alpha_i$ describes a subset of ${\mathcal R}_s$ by an $s$-bit label), 
the path $double(\Delta_s)$ in ${\mathcal H}_{2s}$ is defined by
\[
\begin{array}{lcl}
double(\Delta_s)&~=~&\tuple{~
\alpha_1\overline{\alpha_1},~\alpha_2\overline{\alpha_2}~,\ldots,~
\alpha_i\overline{\alpha_i},~\alpha_{i+1}\overline{\alpha_{i+1}}~,\ldots,~
\alpha_t\overline{\alpha_t}~}\\
&~=~&\tuple{\beta_1,\beta_3,\ldots,\beta_{2i-1},\beta_{2i+1},\ldots,\beta_{2t-1}}
\end{array}
\]
(The reason for successive indices of $\beta$ increasing by $2$ will become clear subsequently)

Of course, $double(\Delta_s)$ does not describe an $O$-contract path\footnote{In terms of the classification
described by \citeA{Sandholm:1998}, it contains only {\em swap} deals ($S$-contracts): each deal
swaps exactly one item in $\beta_{2i-1}$ with an item in $\overline{\beta_{2i-1}}$ in order to give
$\beta_{2i+1}$.}: it is, however, not difficult to interpolate appropriate allocations, $\beta_{2i}$, in
order to convert it to such a path. Consider the subsets $\beta_{2i}$ (with $1\leq i<t$) defined
as follows:
\[
\beta_{2i}~=~
\left\{
{
\begin{array}{lcl}
\alpha_{i+1}\overline{\alpha_i}&\mbox{ if }&\alpha_i\subset\alpha_{i+1}\\
\alpha_i\overline{\alpha_{i+1}}&\mbox{ if }&\alpha_i\supset\alpha_{i+1}
\end{array}
}
\right.
\]
If we now consider the path, $ext(\Delta_s)$, within ${\mathcal H}_{2s}$ given by
\[
ext(\Delta_s)~=~
\tuple{\beta_1,\beta_2,\beta_3~,\ldots,~\beta_{2(t-1)},\beta_{2t-1}}
\]
then this satisfies,
\begin{enumerate}
\item[a.]
If $\Delta_s$ has property (SC) of Theorem~\ref{thm:ir-o-bounds} in ${\mathcal H}_s$ then
$ext(\Delta_s)$ has property (SC) in ${\mathcal H}_{2s}$.
\item[b.]
If $j$ is odd then $|\beta_j|=s$.
\item[c.]
If $j$ is even then $|\beta_j|=s+1$.
\end{enumerate}
From (a) and the bounds proved in \shortcite{AK:91} we deduce that $ext(\Delta_s)$ can be chosen
so that with $P^{(i)}$ denoting the allocation $\tuple{\beta_i,\overline{\beta_i}}$
\begin{enumerate}
\item[d.]
$ext(\Delta_s)$ describes an $O$-contract path from $P^{(1)}$ to $P^{(2t-1)}$.
\item[e.]
For each pair $\tuple{i,j}$ with $j\geq i+2$, the deal
$\tuple{P^{(i)},P^{(j)}}$ is {\em not} an $O$-contract.
\item[f.]
If $\Delta_s$ is chosen as in the proof of Theorem~\ref{thm:ir-o-bounds} then the number of deals
in $ext(\Delta_s)$ is as given in the statement of the present theorem.
\end{enumerate}
We therefore fix $\Delta_s$ as the path from Theorem~\ref{thm:ir-o-bounds} so that 
in order to complete the proof we need to construct utility functions $\tuple{u_1,u_2}$
that are monotone and with which $ext(\Delta_s)$ defines the unique IR $O$-contract path
realising the reallocation $\tuple{P^{(1)},P^{(2t-1)}}$.

The choice for $u_2$ is relatively simple. Given $S\subseteq{\mathcal R}_{2s}$,
\[
u_2(S)~=~
\left\{
{
\begin{array}{lcl}
0&\mbox{ if }&|S|\leq s-2\\
2t+1&\mbox{ if }&|S|=s-1\\
2t+2&\mbox{ if }&|S|\geq s
\end{array}
}
\right.
\]
In this $t$ is the number of allocations in $\Delta_s$. The behaviour of $u_2$ is clearly monotone.

The construction for $u_1$ is rather more complicated. Its main idea is to make use of the fact
that the size of each set $\beta_i$ occurring in $ext(\Delta_s)$ is very tightly
constrained: $|\beta_i|$ is either $s$ or $s+1$ according to whether $i$ is odd or even.
We first demonstrate that
each set of size $s+1$  can have at most two strict subsets (of size $s$) occurring within $ext(\Delta_s)$:
thus, every $S$ of size $s+1$ has exactly $2$ or $1$ or $0$ subsets of size $s$ on $ext(\Delta_s)$.
To see this suppose the contrary.
Let $\gamma$, $\beta_{2i-1}$, $\beta_{2j-1}$, and $\beta_{2k-1}$ be such that $|\gamma|=s+1$ with
\[
\beta_{2i-1}\subset\gamma~~;~~\beta_{2j-1}\subset\gamma~~;~~\beta_{2k-1}\subset\gamma
\]
Noting that $\beta_{2i-1}=\alpha_i\overline{\alpha_i}$ and
that $\Delta_s$ has the property (SC) it must be the case that (at least) two of the $s$-bit
labels from $\set{\alpha_i,\alpha_j,\alpha_k}$ differ in at least two positions. Without loss of generality
suppose this is true of $\alpha_i$ and $\alpha_k$. As a result we deduce that the sets
$\beta_{2i-1}$ and $\beta_{2k-1}$ have at most $s-2$ elements in common, i.e. 
$|\beta_{2i-1}\cap\beta_{2k-1}|\leq s-2$: $\beta_{2i-1}=\alpha_i\overline{\alpha_i}$ and
$\beta_{2k-1}=\alpha_k\overline{\alpha_k}$ so in any position at which $\alpha_i$ differs from $\alpha_k$,
$\overline{\alpha_i}$ differs from $\overline{\alpha_k}$ at exactly the same position. In total
$|\beta_{2i-1}\setminus\beta_{2k-1}|\geq2$, i.e. there are
(at least) two elements of $\beta_{2i-1}$ that do not occur in $\beta_{2k-1}$; and
in the same way $|\beta_{2k-1}\setminus\beta_{2i-1}|\geq2$, i.e. there are
(at least) two elements of $\beta_{2k-1}$ that do not occur in $\beta_{2i-1}$.
The set $\gamma$, however, has only $s+1$ members and so cannot have {\em both} 
$\beta_{2i-1}$ and $\beta_{2k-1}$ as subsets: this would require 
\[
\beta_{2i-1}\cap\beta_{2k-1}~\cup~\beta_{2i-1}\setminus\beta_{2k-1}~\cup
~\beta_{2k-1}\setminus\beta_{2i-1}\subseteq\gamma
\]
but, as we have just seen,
\[
|~\beta_{2i-1}\cap\beta_{2k-1}~\cup~\beta_{2i-1}\setminus\beta_{2k-1}~\cup
~\beta_{2k-1}\setminus\beta_{2i-1}~|~~\geq~~s+2
\]
One immediate consequence of the argument just given is that for any set $\gamma$ of size $s+1$ there
are exactly two strict subsets of $\gamma$ occurring on $ext(\Delta_s)$ if and only if
$\gamma=\beta_{2i-1}\cup\beta_{2i+1}=\beta_{2i}$ for some value of $i$ with $1\leq i<t$.
We can now characterise each subset of ${\mathcal R}_{2s}$ of size $s+1$ as falling into one
of three categories.
\begin{enumerate}
\item[C1.]
{\em Good} sets, given by $\set{\gamma~:~\gamma=\beta_{2i}}$.
\item[C2.]
{\em Digressions}, consisting of
\[
\set{~\gamma~:~\beta_{2i-1}\subset\gamma\mbox{, }\gamma\not=\beta_{2i}\mbox{ and }i<t}
\]
\item[C3.]
{\em Inaccessible} sets, consisting of
\[
\set{~\gamma~:~\mbox{$\gamma$ is neither $Good$ nor a $Digression$}}
\]
\end{enumerate}
$Good$ sets are those describing allocations to $A_1$ within the path defined by
$ext(\Delta_s)$; $Digressions$ are the allocations that could
be reached using an $O$-contract from a set of size $s$ on $ext(\Delta_s)$, i.e. $\beta_{2i-1}$, but
differ from the set that actually occurs in $ext(\Delta_s)$, i.e. $\beta_{2i}$.
Finally, $Inaccessible$ sets are those that do not occur 
on $ext(\Delta_s)$ {\em and} cannot be reached via an $O$-contract from any set on $ext(\Delta_s)$.
We note that we view any set of size $s+1$ that {\em could} be reached by an $O$-contract from
$\beta_{2t-1}$ as being inaccessible: in principle it is possible to extend the $O$-contract path
beyond $\beta_{2t-1}$, however, we choose not complicate the construction in this way. 

We now define $u_1$ as
\[
u_1(\gamma)~=~
\left\{
{
\begin{array}{lcl}
2i-1&\mbox{ if }&\gamma=\beta_{2i-1}\\
2i+1&\mbox{ if }&\gamma=\beta_{2i}\\
2i&\mbox{ if }&\mbox{$|\gamma|=s+1$ and $\gamma$ is a $Digression$ from $\beta_{2i-1}$}\\
0&\mbox{ if }& |\gamma|\leq s-1\\
0&\mbox{ if }& |\gamma|=s\mbox{ and }\gamma\not\in ext(\Delta_s)\\
2t-1&\mbox{ if }&\mbox{$\gamma$ is $Inaccessible$ or $|\gamma|\geq s+2$}
\end{array}
}
\right.
\]
It remains only to prove for these choices of $\tuple{u_1,u_2}$ that the $O$-contract path
$\tuple{P^{(1)},\ldots,P^{(2t-1)}}$ defined from $ext(\Delta_s)$ is the unique IR $O$-contract path
realising the IR deal $\tuple{P^{(1)},P^{(2t-1)}}$ and that $u_1$ is monotone.

To show that $\tuple{P^{(1)},\ldots,P^{(2t-1)}}$ is IR we need to demonstrate
\[
\forall~1\leq j < 2t-1~~u_1(\beta_j)+u_2(\overline{\beta_j})~<~
u_1(\beta_{j+1})+u_2(\overline{\beta_{j+1}})
\]
We have via the definition of $\tuple{u_1,u_2}$
\[
\begin{array}{lcl}
u_1(\beta_{2i-1})+u_2(\overline{\beta_{2i-1}})&~=~&2(t+i)+1\\
&~<~&u_1(\beta_{2i})+u_2(\overline{\beta_{2i}})\\
&~=~&2(t+i)+2\\
&~<~&u_1(\beta_{2i+1})+u_2(\overline{\beta_{2i+1}})\\
&~=~&2(t+i)+3
\end{array}
\]
Thus, via Definition~\ref{defn:IR}, it follows that $ext(\Delta_s)$ gives rise to an IR $O$-contract path.

To see that this path is the unique IR $O$-contract path implementing $\tuple{P^{(1)},P^{(2t-1)}}$,
consider any position $P^{(j)}=\tuple{\beta_j,\overline{\beta_j}}$ and allocation $Q$ other than
$P^{(j+1)}$ or $P^{(j-1)}$. It may be assumed that the deal $\tuple{P^{(j)},Q}$ is an $O$-contract.
If $j=2i-1$ then 
$\sigma_u(P^{(2i-1)})=2(t+i)+1$ and $|\beta_j|=s$. Hence $|Q_1|\in\set{s-1,s+1}$. In the former
case, $u_1(Q_1)=0$ and $u_2(Q_2)=2t+2$ from which $\sigma_u(Q)=2t+2$ and thus $\tuple{P^{(j)},Q}$ is
not IR. In the latter case $u_1(Q_1)=2i$ since $Q_1$ is a $Digression$ from $\beta_{2i-1}$
and $u_2(Q_2)=2t+1$ giving $\sigma_u(Q)=2(t+i)+1$. Again $\tuple{P^{(j)},Q}$ fails to be IR since
$Q$ fails to give any increase in the value of $\sigma_u$. We are left with the case
$j=2i$ so that $\sigma_u(P^{(2i)})=2(t+i)+2$ and $|\beta_j|=s+1$. Since $\tuple{P^{(j)},Q}$ is
assumed to be an $O$-contract this gives $|Q_1|\in\set{s,s+2}$. For the first possibility
$Q_1$ could not be a set on $ext(\Delta_s)$: $\beta_{2i-1}$ and $\beta_{2i+1}$ are both subsets
of $\beta_{2i}$ and there can be at most two such subsets occurring on $ext(\Delta_s)$. It follows,
therefore, that $u_1(Q_1)=0$ giving $\sigma_u(Q)=2t+2$ so that $\tuple{P^{(j)},Q}$ is not IR.
In the second possibility, $u_1(Q_1)=2t-1$  but $u_2(Q_2)=0$ as $|Q_2|=s-2$ so
the deal would result in an overall loss.
We deduce that for each $P^{(j)}$ the only IR $O$-contract consistent with it is the
deal $\tuple{P^{(j)},P^{(j+1)}}$.

The final stage is to prove that the utility function $u_1$ is indeed a {\em monotone}
function. Suppose $S$ and $T$ are subsets of ${\mathcal R}_{2s}$ with $S\subset T$. We need to show
that $u_1(S)\leq u_1(T)$. We may assume that $|S|= s$, that $S$ occurs as some
set within $ext(\Delta_s)$, and that $|T|=s+1$. If $|S|<s$ or $|S|=s$ but does not occur on $ext(\Delta_s)$ we
have $u_1(S)=0$ and the required inequality holds; if $|S|\geq s+1$ then in order for
$S\subset T$ to be possible we would need $|T|\geq s+2$, which would give
$u_1(T)=2t-1$ and this is the maximum value that any subset is assigned by $u_1$. We are left with
only $|S|=s$, $|T|=s+1$ and $S$ on $ext(\Delta_s)$ to consider. 
It has already been shown that there are at most two subsets of $T$ that can occur on $ext(\Delta_s)$. 
Consider the different possibilities:
\begin{enumerate}
\item[a.]
$T=\beta_{2i}$ so that exactly two subsets of $T$ occur in $ext(\Delta_s)$: $\beta_{2i-1}$ and $\beta_{2i+1}$.
Since $u_1(\beta_{2i})=2i+1$ and this is at least $\max\set{u_1(\beta_{2i-1}),u_1(\beta_{2i+1})}$, should
$S$ be either of $\beta_{2i-1}$ or $\beta_{2i+1}$ then $u_1(S)\leq u_1(T)$ as required.
\item[b.]
$T$ is a $Digression$ from $S=\beta_{2i-1}$, so that $u_1(T)=2i$ and $u_1(S)=2i-1$ and, again,
$u_1(S)\leq u_1(T)$.
\end{enumerate}
We deduce that $u_1$ is monotone completing our lower bound proof for $\rho^{\max}_{{\rm mono}}$
for even values of $m$.

We conclude by observing that a similar construction can be used if $m=2s+1$ is odd: use the path
$ext(\Delta_s)$ described above but modifying it so that one resource ($r_m$) is always
held by $A_2$. Only minor modifications to the utility function definitions are needed.
\end{proof}
\begin{exam}
For $s=3$, we can choose
$\Delta_3~=~\tuple{000,001,101,111,110}$ so that $t=5$. This gives $double(\Delta_3)$ as
\[
\tuple{000111,001110,101010,111000,110001}
\]
with the $O$-contract path being defined from $ext(\Delta_3)$  which is
\[
\begin{array}{cl}
&\tuple{000111,001111,001110,101110,101010,111010,111000,111001,110001}\\
\mbox{ $=$ }&\tuple{\beta_1,\beta_2,\beta_3,\beta_4,\beta_5,\beta_6,\beta_7,\beta_8,\beta_9}
\end{array}
\]
Considering the 15 subsets of size $s+1=4$, gives 
\[
\begin{array}{lcl}
Good&\mbox{ $=$ }&\set{001111,~101110,~111010,~111001}\\
Digression&\mbox{ $=$ }&\set{010111,100111,101011,011110,111100}\\
Inaccessible&\mbox{ $=$ }&\set{011011,011101,101101,110110,110011,110101}
\end{array}
\]
Notice that both of the sets in $\set{110011,110101}$ are $Inaccessible$: in principle we
could continue from $\beta_9=110001$ using either, however, in order to simplify the construction
the path is halted at $\beta_9$.

Following the construction presented in Theorem~\ref{thm:mono-ir-o}, gives the following
utility function definitions with $S\subseteq{\mathcal R}=\set{r_1,r_2,r_3,r_4,r_5,r_6}$.
\[
u_2(S)~~=~~\left\{
{
\begin{array}{lcl}
0&\mbox{ {\rm if }}&|S|\leq 1\\
11&\mbox{ {\rm if }}&|S|=2\\
12&\mbox{ {\rm if }}&|S|\geq 3
\end{array}
}
\right.
\]
For $u_1$ we obtain
\[
u_1(S)~=~
\left\{
{
\begin{array}{lcl}
0&\mbox{ {\rm if} }&|S|\leq 2\\
0&\mbox{ {\rm if} }&|S|=3\mbox{ {\rm and} }S\not\in\set{000111,001110,101010,111000,110001}\\
1&\mbox{ {\rm if} }&S=000111~~(\beta_1)\\
2&\mbox{ {\rm if} }&S=010111\mbox{ ({\rm digression from $\beta_1$})}\\
2&\mbox{ {\rm if} }&S=100111\mbox{ ({\rm digression from $\beta_1$})}\\
3&\mbox{ {\rm if} }&S=001111~~(\beta_2)\\
3&\mbox{ {\rm if} }&S=001110~~(\beta_3)\\
4&\mbox{ {\rm if} }&S=011110\mbox{ ({\rm digression from $\beta_3$})}\\
5&\mbox{ {\rm if} }&S=101110~~(\beta_4)\\
5&\mbox{ {\rm if} }&S=101010~~(\beta_5)\\
6&\mbox{ {\rm if} }&S=101011\mbox{ ({\rm digression from $\beta_5$})}\\
7&\mbox{ {\rm if} }&S=111010~~(\beta_6)\\
7&\mbox{ {\rm if} }&S=111000~~(\beta_7)\\
8&\mbox{ {\rm if} }&S=111100\mbox{ ({\rm digression from $\beta_7$})}\\
9&\mbox{ {\rm if} }&S=111001~~(\beta_8)\\
9&\mbox{ {\rm if} }&S=110001~~(\beta_9)\\
9&\mbox{ {\rm if} }&|S|\geq5\mbox{ {\rm or }}S\in\set{011011,011101,101101,110110,110011,110101}
\end{array}
}
\right.
\]
\end{exam}
The monotone utility functions, $\tuple{u_1,u_2}$, employed in proving Theorem~\ref{thm:mono-ir-o}
are defined so that the path arising from $ext(\Delta_s)$ is IR: in the event of either agent
suffering a loss of utility the gain made by the other is sufficient to provide a compensatory
payment. A natural question that now arises is whether the bound obtained in Theorem~\ref{thm:mono-ir-o}
can be shown to apply when the rationality conditions preclude any monetary payment, e.g. for
cases where the concept of rationality is one of those given in Definition~\ref{defn:coop-etc}. Our next
result shows that if we set the rationality condition to enforce cooperatively rational
or equitable deals then the bound of Theorem~\ref{thm:mono-ir-o} still holds.
\begin{thm}\label{thm:mono-other-rational}
For each of the cases below and $m\geq 14$
\begin{enumerate}
\item[a.]
$\Phi(\delta)$ holds if and only if $\delta$ is a cooperatively rational $O$-contract.
\newline
$\Psi(\delta)$ holds if and only if $\delta$ is cooperatively rational.
\item[b.]
$\Phi(\delta)$ holds if and only if $\delta$ is an equitable $O$-contract.
\newline
$\Psi(\delta)$ holds if and only if $\delta$ is equitable.
\end{enumerate}
\[
\rho^{\max}_{{\rm mono}}(2,m,\Phi,\Psi)
~\geq~
\left\{
{
\begin{array}{lcl}
\left({\frac{77}{128}}\right)\ 2^{m/2}~-~3&\mbox{ if }&\mbox{$m$ is even}\\
&&\\
\left({\frac{77}{128}}\right)\ 2^{(m-1)/2}~-~3&\mbox{ if }&\mbox{$m$ is odd}
\end{array}
}
\right.
\]
\end{thm}
\begin{proof}
We again illustrate the constructions only for the case of $m$ being even, noting the
modification to deal with odd values of $m$ outlined at the end of the proof of Theorem~\ref{thm:mono-ir-o}.
The path $ext(\Delta_s)$ is used for both cases.

For (a), we require $\tuple{u_1,u_2}$ to be defined as monotone functions with which $ext(\Delta_{s})$
will be the unique cooperatively rational $O$-contract path to realise the cooperatively rational deal
$\tuple{P^{(1)},P^{(2t-1)}}$ where $P^{(j)}=\tuple{\beta_j,\overline{\beta_j}}$. In this
case we set $\tuple{u_1,u_2}$ to be,
\[
\tuple{u_1(\gamma),u_2(\overline{\gamma})}~=~
\left\{
{
\begin{array}{lcl}
\tuple{i,i}&\mbox{ if }&\gamma=\beta_{2i-1}\\
\tuple{i+1,i}&\mbox{ if }&\gamma=\beta_{2i}\\
\tuple{i,i-1}&\mbox{ if }&\mbox{$|\gamma|=s+1$ and $\gamma$ is a $Digression$ from $\beta_{2i-1}$}\\
\tuple{0,2t-1}&\mbox{ if }& |\gamma|\leq s-1\\
\tuple{0,2t-1}&\mbox{ if }& |\gamma|=s\mbox{ and }{\gamma}\not\in ext(\Delta_s)\\
\tuple{2t-1,0}&\mbox{ if }&\mbox{$\gamma$ is $Inaccessible$ or $|\gamma|\geq s+2$}
\end{array}
}
\right.
\]
Since,
\[
\begin{array}{lcl}
\tuple{u_1(\beta_{2i-1}),u_2(\overline{\beta_{2i-1}})}&\mbox{ $=$ }&\tuple{i,i}\\
\tuple{u_1(\beta_{2i}),u_2(\overline{\beta_{2i}})}&\mbox{ $=$ }&\tuple{i+1,i}\\
\tuple{u_1(\beta_{2i+1}),u_2(\overline{\beta_{2i+1}})}&\mbox{ $=$ }&\tuple{i+1,i+1}
\end{array}
\]
it is certainly the case that $\tuple{P^{(1)},P^{(2t-1)}}$ and 
all deals on the $O$-contract path defined by $ext(\Delta_s)$ are cooperatively rational.
Furthermore if $Q=\tuple{\gamma,{\overline{\gamma}}}$ is any allocation other than $P^{(j+1)}$ then
the deal $\tuple{P^{(j)},Q}$ will fail to be a cooperatively rational $O$-contract. For suppose
the contrary letting $\tuple{P^{(j)},Q}$ without loss of generality be an $O$-contract, with
$Q\not\in\set{P^{(j-1)},P^{(j+1)}}$ -- we can rule out the former case since we have already shown such an
deal is not cooperatively rational. If $j=2i-1$ so that
$\tuple{u_1(\beta_j),u_2(\overline{\beta_j})}=\tuple{i,i}$ then $|\gamma|\in\set{s-1,s+1}$: the former
case leads to a loss in utility for $A_1$; the latter, (since $\gamma$ is a $Digression$ from $\beta_{2i-1}$)
a loss in utility
for $A_2$. Similarly, if $j=2i$ so that $\tuple{u_1(\beta_j),u_2(\overline{\beta_j})}=\tuple{i+1,i}$ then
$|\gamma|\in\set{s,s+2}$: for the first $\gamma\not\in ext(\Delta_s)$ leading to a loss of utility
for $A_1$; the second results in a loss of utility for $A_2$.
It follows that the path defined by $ext(\Delta_s)$ is the unique cooperatively rational $O$-contract
path that realises $\tuple{P^{(1)},P^{(2t-1)}}$.

It remains only to show that these choices for $\tuple{u_1,u_2}$ define monotone utility functions.

Consider $u_1$ and
suppose $S$ and $T$ are subsets of ${\mathcal R}_{2s}$ with $S\subset T$. If $|S|\leq s-1$, or $S$
does not occur on $ext(\Delta_s)$ then $u_1(S)=0$. If $|T|\geq s+2$ or is $Inaccessible$
then $u_1(T)=2t-1$ which is the maximum value attainable by $u_1$. 
So we may assume that $|S|=s$, occurs on $ext(\Delta_s)$, i.e.
$S=\beta_{2i-1},$ for some $i$, and that $|T|=s+1$ and is either a $Good$ set or a $Digression$. 
From the definition of $u_1$, $u_1(S)=i$: if $T\in\set{\beta_{2i},\beta_{2i-2}}$ then $u_1(T)\geq i = u_1(S)$; 
if $T$ is a $Digression$ from $\beta_{2i-1}$ then $u_1(T)=i=u_1(S)$. 
We deduce that if $S\subseteq T$ then $u_1(S)\leq u_1(T)$, i.e.
the utility function is monotone.

Now consider $u_2$ with $S$ and $T$ subsets of ${\mathcal R}_{2s}$ having $S\subset T$. If $|T|\geq s+1$
or ${\mathcal R}_{2s}\setminus T$ does not occur in $ext(\Delta_s)$ then $u_2(T)=2t-1$ its maximal value.
If $|S|\leq s-2$ or ${\mathcal R}_{2s}\setminus S$ is $Inaccessible$ then $u_2(S)=0$. Thus we may
assume that $T=\overline{\beta_{2i-1}}$ giving $u_2(T)=i$ and $|S|=s-1$, 
so that ${\mathcal R}_{2s}\setminus S$ is either a
$Digression$ or one of the $Good$ sets $\set{\beta_{2i},\beta_{2i-2}}$. If ${\mathcal R}_{2s}\setminus S$ is
a $Digression$ then $u_2(S)=i-1$; if it is the $Good$ set $\beta_{2i-2}$ then $u_2(S)=i-1~<~u_2(T)$; if it
is the $Good$ set $\beta_{2i}$ then $u_2(S)=i=u_2(T)$. It follows that $u_2$ is monotone completing
the proof of part (a).

For (b) we use,
\[
\begin{array}{lcl}
\tuple{u_1(\gamma),u_2(\overline{\gamma})}~=~
\left\{
{
\begin{array}{lcl}
\tuple{2i-1,2i}&\mbox{ if }&\gamma=\beta_{2i-1}\\
\tuple{2i+1,2i}&\mbox{ if }&\gamma=\beta_{2i}\\
\tuple{2i,2i-1}&\mbox{ if }&\mbox{$|\gamma|=s+1$ and $\gamma$ is a $Digression$ from $\beta_{2i-1}$}\\
\tuple{0,2t-1}&\mbox{ if }& |\gamma|\leq s-1\\
\tuple{0,2t-1}&\mbox{ if }& |\gamma|=s\mbox{ and }{\gamma}\not\in ext(\Delta_s)\\
\tuple{2t-1,0}&\mbox{ if }&\mbox{$\gamma$ is $Inaccessible$ or $|\gamma|\geq s+2$}
\end{array}
}
\right.
\end{array}
\]
These choices give $ext(\Delta_s)$ as the unique equitable $O$-contract path
to realise the equitable deal $\tuple{P^{(1)},P^{(2t-1)}}$, since
\[
\begin{array}{lcl}
\min\set{u_1(\beta_{2i-1}),u_2(\overline{\beta_{2i-1}})}&\mbox{ $=$ }&2i-1\\
\min\set{u_1(\beta_{2i}),u_2(\overline{\beta_{2i}})}&\mbox{ $=$ }&2i\\
\min\set{u_1(\beta_{2i+1}),u_2(\overline{\beta_{2i+1}})}&\mbox{ $=$ }&2i+1
\end{array}
\]
each deal $\tuple{P^{(j)},P^{(j+1)}}$ is equitable. 
If $Q=\tuple{\gamma,\overline{\gamma}}$ is any allocation other than $P^{(j+1)}$
then the deal $\tuple{P^{(j)},Q}$ is not an equitable $O$-contract. Assume that $\tuple{P^{(j)},Q}$ is
an $O$-contract, and that $Q\not\in\set{P^{(j-1)},P^{(j+1)}}$. 
If $j=2i-1$, so that $P^{(j)}=\tuple{\beta_{2i-1},\overline{\beta_{2i-1}}}$ and
$\min\set{u_1(\beta_{2i-1}),u_2(\overline{\beta_{2i-1}})}=2i-1$ then
$|\gamma|\in\set{s-1,s+1}$. In the first of these $\min\set{u_1(\gamma),u_2(\overline{\gamma})}=0$;
in the second $\min\set{u_1(\gamma),u_2(\overline{\gamma})}=2i-1$ since $\gamma$ must be a $Digression$.
This leaves only $j=2i$ with $P^{(j)}=\tuple{\beta_{2i},\overline{\beta_{2i}}}$
and $\min\set{u_1(\beta_{2i}),u_2(\overline{\beta_{2i}})}=2i$. 
For this, $|\gamma|\in\set{s,s+2}$: if $|\gamma|=s$
then $\min\set{u_1(\gamma),u_2(\overline{\gamma})}\leq 2i-1$ (with equality when $\gamma=\beta_{2i-1}$); if
$|\gamma|=s+2$ then $\min\set{u_1(\gamma),u_2(\overline{\gamma})}=0$. In total these
establish that $ext(\Delta_s)$ is the unique equitable $O$-contract path realising the equitable deal
$\tuple{P^{(1)},P^{(2t-1)}}$.

That the choices for $\tuple{u_1,u_2}$ describe monotone utility 
functions can be shown by a similar argument to that of part (a).
\end{proof}
\begin{exam}
For $s=3$ using the same $O$-contract path $ext(\Delta_3)$ as the previous example,
i.e.
\[
\begin{array}{cl}
&\tuple{000111,001111,001110,101110,101010,111010,111000,111001,110001}\\
\mbox{ $=$ }&\tuple{\beta_1,\beta_2,\beta_3,\beta_4,\beta_5,\beta_6,\beta_7,\beta_8,\beta_9}
\end{array}
\]
For $\tuple{u_1,u_2}$  in (a) we obtain
{\scriptsize
\[
\tuple{u_1(S),u_2({\mathcal R}\setminus S)}~=~
\left\{
{
\begin{array}{lcl}
\tuple{0,9}&\mbox{ {\rm if} }&|S|\leq 2\\
\tuple{0,9}&\mbox{ {\rm if} }&|S|=3\mbox{ {\rm and} }S\not\in\set{000111,001110,101010,111000,110001}\\
\tuple{1,1}&\mbox{ {\rm if} }&S=000111~~(\beta_1)\\
\tuple{1,0}&\mbox{ {\rm if} }&S=010111\mbox{ {\rm digression from $\beta_1$}}\\
\tuple{1,0}&\mbox{ {\rm if} }&S=100111\mbox{ {\rm digression from $\beta_1$}}\\
\tuple{2,1}&\mbox{ {\rm if} }&S=001111~~(\beta_2)\\
\tuple{2,2}&\mbox{ {\rm if} }&S=001110~~(\beta_3)\\
\tuple{2,1}&\mbox{ {\rm if} }&S=011110\mbox{ {\rm digression from $\beta_3$}}\\
\tuple{3,2}&\mbox{ {\rm if} }&S=101110~~(\beta_4)\\
\tuple{3,3}&\mbox{ {\rm if} }&S=101010~~(\beta_5)\\
\tuple{3,2}&\mbox{ {\rm if} }&S=101011\mbox{ {\rm digression from $\beta_5$}}\\
\tuple{4,3}&\mbox{ {\rm if} }&S=111010~~(\beta_6)\\
\tuple{4,4}&\mbox{ {\rm if} }&S=111000~~(\beta_7)\\
\tuple{4,3}&\mbox{ {\rm if} }&S=111100\mbox{ {\rm digression from $\beta_7$}}\\
\tuple{5,4}&\mbox{ {\rm if} }&S=111001~~(\beta_8)\\
\tuple{5,5}&\mbox{ {\rm if} }&S=110001~~(\beta_9)\\
\tuple{9,0}&\mbox{ {\rm if} }&|S|\geq5\mbox{ {\rm or }}S\in\set{011011,011101,101101,110110,110011,110101}
\end{array}
}
\right.
\]
}
Similarly, in (b)
{\scriptsize
\[
\tuple{u_1(S),u_2({\mathcal R}\setminus S)}~=~
\left\{
{
\begin{array}{lcl}
\tuple{0,9}&\mbox{ {\rm if} }&|S|\leq 2\\
\tuple{0,9}&\mbox{ {\rm if} }&|S|=3\mbox{ {\rm and} }S\not\in\set{000111,001110,101010,111000,110001}\\
\tuple{1,2}&\mbox{ {\rm if} }&S=000111~~(\beta_1)\\
\tuple{2,1}&\mbox{ {\rm if} }&S=010111\mbox{ {\rm digression from $\beta_1$}}\\
\tuple{2,1}&\mbox{ {\rm if} }&S=100111\mbox{ {\rm digression from $\beta_1$}}\\
\tuple{3,2}&\mbox{ {\rm if} }&S=001111~~(\beta_2)\\
\tuple{3,4}&\mbox{ {\rm if} }&S=001110~~(\beta_3)\\
\tuple{4,3}&\mbox{ {\rm if} }&S=011110\mbox{ {\rm digression from $\beta_3$}}\\
\tuple{5,4}&\mbox{ {\rm if} }&S=101110~~(\beta_4)\\
\tuple{5,6}&\mbox{ {\rm if} }&S=101010~~(\beta_5)\\
\tuple{6,5}&\mbox{ {\rm if} }&S=101011\mbox{ {\rm digression from $\beta_5$}}\\
\tuple{7,6}&\mbox{ {\rm if} }&S=111010~~(\beta_6)\\
\tuple{7,8}&\mbox{ {\rm if} }&S=111000~~(\beta_7)\\
\tuple{8,7}&\mbox{ {\rm if} }&S=111100\mbox{ {\rm digression from $\beta_7$}}\\
\tuple{9,8}&\mbox{ {\rm if} }&S=111001~~(\beta_8)\\
\tuple{9,10}&\mbox{ {\rm if} }&S=110001~~(\beta_9)\\
\tuple{9,0}&\mbox{ {\rm if} }&|S|\geq5\mbox{ {\rm or }}S\in\set{011011,011101,101101,110110,110011,110101}
\end{array}
}
\right.
\]
}
\end{exam}

That we can demonstrate similar extremal behaviours for contract path length with rationality
constraints in both money-based (individual rationality) and money-free (cooperative rationality,
equitable) settings irrespective of whether monotonicity properties are assumed, has some interesting
parallels with other contexts in which monotonicity is relevant. In particular we can
observe that in common with the complexity results already noted from 
\shortcite{dunne:2003} -- deciding if an allocation is Pareto optimal, if an allocation maximises $\sigma_u$, 
or if an IR $O$-contract path exists -- requiring utility functions to be monotone does not result
in a setting which is computationally more tractable.
\section{$M(k)$-contract paths}~\label{section:mk-results}
We now turn to similar issues with respect to $M(k)$-contracts, recalling that in
one respect these offer a form of deal that does not fit into the classification
of \citeA{Sandholm:1998}. This classification defines four forms of contract type: 
$O$-contracts, as considered in the previous section; 
$S$-contracts, that involve exactly 2 agents swapping single resources; 
$C$-contracts, in which one agent tranfers {\em at least} two of its resources to
another; and $M$-contracts in which {\em three or more} agents reallocate their resource holding amongst
themselves. Our definition of $M(k)$-contracts permits {\em two} agents to
exchange resources (thus are not $M$-contracts in \citeS{Sandholm:1998} scheme)
and the deals permitted are not restricted to $O$, $S$, and $C$-contracts. In one regard, however,
$M(k)$-contracts are not as general as $M$-contracts
since a preset bound ($k$) is specified for the number of agents involved.

Our main result on $M(k)$-contract paths is the following development of Theorem~\ref{thm:ir-o-bounds}.
\begin{thm}\label{thm:mk-hierarchy-ir}
Let $\Phi_k(P,Q)$ be the predicate which holds whenever $\tuple{P,Q}$ is an IR $M(k)$-contract.
For all $k\geq 3$, $n\geq k$ and $m\geq\mbox{{\scriptsize $\left({\begin{array}{c}k\\2\end{array}}\right)$}}$,
there is
a resource allocation setting $\tuple{{\mathcal A},{\mathcal R},{\mathcal U}}$ and an
IR deal $\delta=\tuple{P,Q}$ for which,
\[
\begin{array}{lcclr}
L^{{\rm opt}}(\delta,\tuple{{\mathcal A},{\mathcal R},{\mathcal U}},\Phi_k)&\mbox{ $=$ }&1&\mbox{ }&(a)\\
L^{{\rm opt}}(\delta,\tuple{{\mathcal A},{\mathcal R},{\mathcal U}},\Phi_{k-1})&\mbox{ $\geq$ }&
2^{\lfloor{2m/k(k-1)}\rfloor} -1&\mbox{ }&(b)\\
L^{{\rm opt}}(\delta,\tuple{{\mathcal A},{\mathcal R},{\mathcal U}},\Phi_{k-2})&&\mbox{ {\rm is undefined}}&
\mbox{ }&(c)
\end{array}
\]
\end{thm}
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 $L^{{\rm opt}}$ as opposed to $\rho^{\max}$
used in the various results on $O$-contract paths in Section~\ref{subsection:O-contracts}. It is, of course,
the case that the bound claimed for 
$L^{{\rm opt}}(\delta,\tuple{{\mathcal A},{\mathcal R},{\mathcal U}},\Phi_{k-1})$ will also be a lower
bound on $\rho^{\max}(n,m,\Phi_{k-1},\Psi)$ when $n\geq k$ and $\Psi(P,Q)$ holds whenever the deal
$\tuple{P,Q}$ is IR. The statement of Theorem~\ref{thm:mk-hierarchy-ir}, however, claims rather
more than this, namely that a {\em specific} resource allocation setting 
$\tuple{{\mathcal A},{\mathcal R},{\mathcal U}}$ can be defined for each $n\geq k$ and each $m$, together
with an IR deal $\tuple{P,Q}$ in such a way that: $\tuple{P,Q}$ can be achieved by a {\em single}
$M(k)$-contract and {\em cannot} be realised by an IR $M(k-2)$-contract path. Recalling that 
$L^{{\rm opt}}$ is a {\em partial} function, the latter property is equivalent to the
claim made in part (c) for the
deal $\tuple{P,Q}$ of the theorem statement.
Furthermore, this same deal although achievable by an IR 
$M(k-1)$-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 $m$ -- the size of the resource set ${\mathcal R}$ -- and $k$ -- the number of agents
which are needed to realise $\tuple{P,Q}$ in a {\em single} IR deal. In particular, we shall
assume that $m$ is an exact multiple of {\scriptsize  $\left({\begin{array}{c}k\\2\end{array}}\right)$}. 
We observe that by employing a similar device
to that used in the proof of Theorem~\ref{thm:mono-ir-o} we can
deal with cases for which $m$ does not have this property: if
$m~=~s\mbox{{\scriptsize $\left({\begin{array}{c}k\\2\end{array}}\right)$}}+q$ 
for integer values $s\geq 1$ and $1\leq q<\mbox{{\scriptsize $\left({\begin{array}{c}k\\2\end{array}}\right)$}}$, 
we simply employ exactly the
same construction using $m-q$ resources with the ``missing'' $q$ resources from ${\mathcal R}_m$ being
allocated to $A_1$ and never being reallocated within the $M(k-1)$-contract path. This approach accounts
for the rounding operation ($\lfloor{\ldots}\rfloor$) in the exponent term of the lower bound.
We shall also assume that the number of agents in ${\mathcal A}$ is exactly $k$.
Within the proof we use a running example for which $k=4$ and $m=18=3\times6$ to illustrate specific features.

We first give an outline of its structure.

Given $\tuple{{\mathcal A},{\mathcal R},{\mathcal U}}$ a resource allocation setting
involving $k$ agents and $m$ resources, our aim is to define an IR $M(k-1)$-contract path
\[
\Delta\ =\ \tuple{P^{(1)},P^{(2)},\ldots,P^{(t)}}
\]
that realises the IR $M(k)$ deal $\tuple{P^{(1)},P^{(t)}}$.
We will use $d$ to index particular allocations within $\Delta$, so that $1\leq d\leq t$.

In order to simplify the presentation we employ a setting in
which the $k$ agents are ${\mathcal A}=\set{A_0,A_1,\ldots,A_{k-1}}$. 
Recalling that $m=s\mbox{{\scriptsize $\left({\begin{array}{c}k\\2\end{array}}\right)$}}$, the resource
set ${\mathcal R}_m$ is formed by the union of {\scriptsize $\left({\begin{array}{c}k\\2\end{array}}\right)$} 
pairwise disjoint sets of size $s$. Given distinct
values $i$ and $j$ with $0\leq i<j\leq k-1$, we use ${\mathcal R}^{i,j}$ to denote one of these
subsets with $\set{r_{1}^{\set{i,j}},~r_{2}^{\set{i,j}}~,\ldots,~r_{s}^{\set{i,j}}}$ the $s$ resources
that form ${\mathcal R}^{\set{i,j}}$.

There are two main ideas underpinning the structure of each $M(k-1)$-contract in $\Delta$. 

Firstly, in the initial and subsequent allocations, the resource set ${\mathcal R}^{\set{i,j}}$
is partitioned between $A_i$ and $A_j$ and any reallocation of resources between $A_i$ and $A_j$ 
that takes place within the deal $\tuple{P^{(d)},P^{(d+1)}}$ will involve {\em only} 
resources in this set. Thus, for every allocation $P^{(d)}$ and each pair $\set{i,j}$,
if $h\not\in\set{i,j}$ then $P_{h}^{(d)}\cap{\mathcal R}^{\set{i,j}}=\emptyset$. Furthermore, 
for $\delta=\tuple{P^{(d)},P^{(d+1)}}$ should {\em both} $A_i$ and $A_j$ be involved, i.e.
$\set{A_i,A_j}\subseteq{\mathcal A}^\delta$, then this reallocation of ${\mathcal R}^{\set{i,j}}$ between
$A_i$ and $A_j$ will be an $O$-contract. That is, either exactly one element of ${\mathcal R}^{\set{i,j}}$ will
be moved from $P^{(d)}_{i}$ to become a member of the allocation $P^{(d+1)}_{j}$ or 
exactly one element of ${\mathcal R}^{\set{i,j}}$ will be moved from $P^{(d)}_{j}$
to become a member of the allocation $P^{(d+1)}_{i}$. 
In total, every $M(k-1)$-contract $\delta$ in $\Delta$ consists of
a {\em simultaneous} implementation of {\scriptsize $\left({\begin{array}{c}k-1\\2\end{array}}\right)$}
$O$-contracts: a single $O$-contract for each of the
distinct pairs $\set{A_i,A_j}$ of agents from the $k-1$ agents in ${\mathcal A}^{\delta}$.

The second key idea is to exploit one well-known property
of the $s$-dimensional hypercube network:
for every $s\geq 2$, ${\mathcal H}_s$ contains a
{\em Hamiltonian cycle}, i.e. a simple directed cycle formed using only the edges
of ${\mathcal H}_s$ and containing all $2^s$ vertices.\footnote{This can be shown by
an easy inductive argument. For $s=2$, the sequence $\tuple{00,01,11,10,00}$ defines a Hamiltonian
cycle in ${\mathcal H}_2$. Inductively assume that $\tuple{\alpha_1,\alpha_2,\ldots,\alpha_p,\alpha_1}$
(with $p=2^s$) is such a cycle in ${\mathcal H}_s$ then
$\tuple{0\alpha_1,1\alpha_1,1\alpha_p,1\alpha_{p-1},\ldots,1\alpha_2,0\alpha_2\ldots,0\alpha_p,0\alpha_1}$
defines a Hamiltonian cycle in ${\mathcal H}_{s+1}$.}
Now, suppose
\[
{\mathcal S}^{(v)}=\underline{v}^{(0)},\underline{v}^{(1)},\ldots,
                   \underline{v}^{(i)},\ldots,\underline{v}^{(2^s-1)}, \underline{v}^{(0)}
\]
is a Hamiltonian cycle in the hypercube ${\mathcal H}_s$ and
\[
{\mathcal S}^{(w)}=\underline{w}^{(0)},\underline{w}^{(1)},\ldots,\underline{w}^{(i)},\ldots,
                   \underline{w}^{(2^s-1)}, \underline{w}^{(0)}
\]
the Hamiltonian cycle in which $\underline{w}^{(i)}$ is obtained by complementing each bit
in $\underline{v}^{(i)}$.  As we have described in the overview of
Section~\ref{subsection:overview} 
we can interpret the $s$-bit label $\underline{v}=v_1v_2\ldots v_s$ as describing
a particular subset of ${\mathcal R}^{\set{i,j}}$, i.e. that subset in which $r_{k}^{\set{i,j}}$
occurs if and only if $v_k=1$. Similarly from any subset of ${\mathcal R}^{\set{i,j}}$
we may define a unique $s$-bit word. Now suppose that $P_{i}^{(d)}$ is the allocation held
by $A_i$ in the allocation $P^{(d)}$ of $\Delta$. The deal $\delta=\tuple{P^{(d)},P^{(d+1)}}$
will affect $P_{i}^{(d)}\cap{\mathcal R}^{\set{i,j}}$ in the following way:
if $i\not\in{\mathcal A}^{\delta}$ or $j\not\in{\mathcal A}^{\delta}$ then 
$P_{i}^{(d+1)}\cap{\mathcal R}^{\set{i,j}}=P_{i}^{(d)}\cap{\mathcal R}^{\set{i,j}}$
and $P_{j}^{(d+1)}\cap{\mathcal R}^{\set{i,j}}=P_{j}^{(d)}\cap{\mathcal R}^{\set{i,j}}$. Otherwise
we have $\set{i,j}\subseteq{\mathcal A}^{\delta}$ and the (complementary) holdings 
$P_{i}^{(d)}\cap{\mathcal R}^{\set{i,j}}$ and $P_{j}^{(d)}\cap{\mathcal R}^{\set{i,j}}$ define
(complementary) $s$-bit labels of vertices in ${\mathcal H}_s$: if these correspond
to places $\tuple{\underline{v}^{(h)},\underline{w}^{(h)}}$ in the Hamiltonian cycles, then
in $P_{i}^{(d+1)}$ and $P_{j}^{(d+1)}$ the $s$-bit labels defined from
$P_{i}^{(d+1)}\cap{\mathcal R}^{\set{i,j}}$ and $P_{j}^{(d+1)}\cap{\mathcal R}^{\set{i,j}}$
produce the $s$-bit labels $\underline{v}^{(h+1)}$ and $\underline{w}^{(h+1)}$, i.e. the vertices that
succeed $\underline{v}^{(h)}$ and $\underline{w}^{(h)}$ in the Hamiltonian cycles. In total, for each $j$, $A_i$
initially holds either the subset of ${\mathcal R}^{\set{i,j}}$ that maps to $\underline{v}^{(0)}$ or that
maps to $\underline{w}^{(0)}$ and, at the conclusion of the $M(k-1)$-path, holds
the subset that maps to $\underline{v}^{(2^s-1)}$ (or $\underline{w}^{(2^s-1)}$). The final
detail is that the progression through the Hamiltonian cycles is conducted over a series
of {\em rounds} each round comprising $k$ $M(k-1)$-deals.

We have noted that each $M(k-1)$-contract, $\tuple{P^{(d)},P^{(d+1)}}$
that occurs in this path $\Delta$ can be interpreted
as a set of {\scriptsize $\left({\begin{array}{c}k-1\\2\end{array}}\right)$} 
distinct $O$-contracts. An important property
of the utility functions employed is that unless $p\geq k-1$ there will be {\em no individually rational} 
$M(p)$-contract path that realises the deal $\tuple{P^{(d)},P^{(d+1)}}$, i.e. the 
{\scriptsize $\left({\begin{array}{c}k-1\\2\end{array}}\right)$}
$O$-contract deals must occur {\em simultaneously} in order for the progression
from $P^{(d)}$ to $P^{(d+1)}$ to be IR. 
Although the required deal could
be realised by a sequence of $O$-contracts (or, more generally, any suitable $M(k-2)$-contract path), 
such realisations will {\em 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 $\tuple{P^{(1)},P^{(t)}}$ cannot be realised with an IR $M(k-2)$-contract path: if $Q$ is
{\em any} allocation for which $\tuple{P^{(1)},Q}$ is an $M(k-2)$-contract then $\tuple{P^{(1)},Q}$ is not IR.

We now proceed with the proof of Theorem~\ref{thm:mk-hierarchy-ir}.

\begin{proof}
(of Theorem~\ref{thm:mk-hierarchy-ir})
Fix ${\mathcal A}=\set{A_0,A_1,\ldots,A_{k-1}}$. ${\mathcal R}$ consists of
{\scriptsize $\left({\begin{array}{c}k\\2\end{array}}\right)$} pairwise disjoint sets of $s$ resources
\[
{\mathcal R}^{\set{i,j}}=\set{r_{1}^{\set{i,j}},r_{2}^{\set{i,j}},\ldots,r_{s}^{\set{i,j}}}
\]

For $k=4$ and $s=3$ these yield ${\mathcal A}=\set{A_0,A_1,A_2,A_3}$ and
\[
\begin{array}{lcl}
{\mathcal R}^{\set{0,1}}&=&\set{r_{1}^{\set{0,1}},r_{2}^{\set{0,1}},r_{3}^{\set{0,1}}}\\
{\mathcal R}^{\set{0,2}}&=&\set{r_{1}^{\set{0,2}},r_{2}^{\set{0,2}},r_{3}^{\set{0,2}}}\\
{\mathcal R}^{\set{0,3}}&=&\set{r_{1}^{\set{0,3}},r_{2}^{\set{0,3}},r_{3}^{\set{0,3}}}\\
{\mathcal R}^{\set{1,2}}&=&\set{r_{1}^{\set{1,2}},r_{2}^{\set{1,2}},r_{3}^{\set{1,2}}}\\
{\mathcal R}^{\set{1,3}}&=&\set{r_{1}^{\set{1,3}},r_{2}^{\set{1,3}},r_{3}^{\set{1,3}}}\\
{\mathcal R}^{\set{2,3}}&=&\set{r_{1}^{\set{2,3}},r_{2}^{\set{2,3}},r_{3}^{\set{2,3}}}
\end{array}
\]
We use two ordering structures in defining the $M(k-1)$-contract path.
\begin{enumerate}
\item[a.]
\[
{\mathcal S}^{(v)}=\underline{v}^{(0)},\underline{v}^{(1)},\ldots,
                   \underline{v}^{(i)},\ldots,\underline{v}^{(2^s-1)}, \underline{v}^{(0)}
\]
a Hamiltonian cycle in ${\mathcal H}_s$, where without loss of generality,
$\underline{v}^{(0)}=111\ldots11$.
\item[b.]
\[
{\mathcal S}^{(w)}=\underline{w}^{(0)},\underline{w}^{(1)},\ldots,
                   \underline{w}^{(i)},\ldots,\underline{w}^{(2^s-1)}, \underline{w}^{(0)}
\]
the complementary Hamiltonian cycle to this, so that $\underline{w}^{(0)}=000\ldots00$.
\end{enumerate}
Thus for $k=4$ and $s=3$ we obtain
\[
\begin{array}{llcl}
\mbox{a. }&{\mathcal S}^{(v)}&=&\tuple{111,110,010,011,001,000,100,101}\\
\mbox{b. }&{\mathcal S}^{(w)}&=&\tuple{000,001,101,100,110,111,011,010}
\end{array}
\]
We can now describe the $M(k-1)$-contract path.
\[
\Delta\ =\ \tuple{P^{(1)},P^{(2)},\ldots,P^{(t)}}
\]
\newline
$\ \ \ $
\newline
{\bf Initial Allocation}: $P^{(1)}$.
\newline
Define the $k\times k$ Boolean matrix, $B=[b_{i,j}]$ (with $0\leq i,j\leq k-1$) by
\[
b_{i,j}\ =\ \left\{
{
\begin{array}{lcl}
\bot&\mbox{ if }&i=j\\
\neg b_{j,i}&\mbox{ if }&i>j\\
\neg b_{i,j-1}&\mbox{ if }&i<j
\end{array}
}
\right.
\]
We then have for each $1\leq i\leq k$,
\[
P_{i}^{(1)}\ =\ \bigcup_{j=0}^{i-1}\set{\ R^{\set{j,i}}\mbox{ : }b_{i,j}=\top}\ \cup
                \bigcup_{j=i+1}^{k-1}\set{\ R^{\set{i,j}}\mbox{ : }b_{i,j}=\top}
\]
Thus, in our example,
\[
B\ =\ 
\left[
{
\begin{array}{cccc}
\bot&\top&\bot&\top\\
\bot&\bot&\top&\bot\\
\top&\bot&\bot&\top\\
\bot&\top&\bot&\bot
\end{array}
}
\right]
\]
Yielding the starting allocation
\[
\begin{array}{lclclcl}
P_0^{(1)}&=&{\mathcal R}^{\set{0,1}}\cup{\mathcal R}^{\set{0,3}}&\mbox{ $=$ }&\tuple{111,000,111}&
\mbox{ $\subseteq$ }&{\mathcal R}^{\set{0,1}}\cup{\mathcal R}^{\set{0,2}}\cup{\mathcal R}^{\set{0,3}}\\
P_1^{(1)}&=&{\mathcal R}^{\set{1,2}}&\mbox{ $=$ }&\tuple{000,111,000}&
\mbox{ $\subseteq$ }&{\mathcal R}^{\set{0,1}}\cup{\mathcal R}^{\set{1,2}}\cup{\mathcal R}^{\set{1,3}}\\
P_2^{(1)}&=&{\mathcal R}^{\set{0,2}}\cup{\mathcal R}^{\set{2,3}}&\mbox{ $=$ }&\tuple{111,000,111}&
\mbox{ $\subseteq$ }&{\mathcal R}^{\set{0,2}}\cup{\mathcal R}^{\set{1,2}}\cup{\mathcal R}^{\set{2,3}}\\
P_3^{(1)}&=&{\mathcal R}^{\set{1,3}}&\mbox{ $=$ }&\tuple{000,111,000}&
\mbox{ $\subseteq$ }&{\mathcal R}^{\set{0,3}}\cup{\mathcal R}^{\set{1,3}}\cup{\mathcal R}^{\set{2,3}}
\end{array}
\]
The third column in $P_{i}^{(1)}$ indicating the $3$-bit labels characterising each of the
subsets of ${\mathcal R}^{\set{i,j}}$ for the three values that $j$ can assume.
\newline
$\ \ \ $
\newline
{\bf Rounds:}
The initial allocation is changed over a series of {\em rounds}
\[
Q^1,Q^2,\ldots,Q^z
\]
each of which involves exactly $k$ distinct $M(k-1)$-contracts. We use $Q^{x,p}$
to indicate the allocation resulting after stage $p$ in round $x$ where $0\leq p\leq k-1$.
We note
the following:
\begin{enumerate}
\item[a.]
The initial allocation, $P^{(1)}$ will be denoted by $Q^{0,k-1}$.
\item[b.]
$Q^{x,0}$ is obtained using a single $M(k-1)$-contract from $Q^{x-1,k-1}$ (when $x\geq1$).
\item[c.]
$Q^{x,p}$ is obtained using a single $M(k-1)$-contract from $Q^{x,p-1}$ (when $0<p\leq k-1$).
\end{enumerate}
Our final item of notation is that of the {\em cube position of} $i$ {\em with respect to} $j$ {\em in an
allocation} $P$, denoted
$\chi(i,j,P)$. Letting $\underline{u}$ be the $s$-bit string describing $P_i\cap{\mathcal R}^{\set{i,j}}$
in some allocation $P$, $\chi(i,j,P)$ is the {\em index} of $\underline{u}$ in the Hamiltonian cycle
$S^{(v)}$ (when ${\mathcal R}^{\set{i,j}}\subseteq P_{i}^{(1)}$) or the Hamiltonian cycle
$S^{(w)}$ (when ${\mathcal R}^{\set{i,j}}\subseteq P_{j}^{(1)}$). When $P=Q^{x,p}$ for some
allocation in the sequence under construction we employ the notation $\chi(i,j,x,p)$, noting
that one invariant
of our path will be $\chi(i,j,x,p)=\chi(j,i,x,p)$, a property that certainly holds true of
$P^{(1)}=Q^{0,k-1}$ since $\chi(i,j,0,k-1)=\chi(j,i,0,k-1)=0$.

The sequence of allocations in $\Delta$ is built as follows.
Since $Q^{1,0}$ is the immediate successor of the initial allocation
$Q^{0,k-1}$, it suffices to describe how $Q^{x,p}$ is formed from $Q^{x,p-1}$
(when $p>0$) and $Q^{x+1,0}$ from $Q^{x,k-1}$.
Let $Q^{y,q}$ be the allocation to be formed from $Q^{x,p}$. The deal
$\delta=\tuple{Q^{x,p},Q^{y,q}}$ will be an $M(k-1)$ contract in which
${\mathcal A}^{\delta}={\mathcal A}\setminus \set{A_q}$. For each pair
$\set{i,j}\subseteq{\mathcal A}^{\delta}$ we have $\chi(i,j,x,p)=\chi(j,i,x,p)$
in the allocation $Q^{x,p}$. In moving to $Q^{y,q}$ exactly one element of 
${\mathcal R}^{\set{i,j}}$ is reallocated between
$A_i$ and $A_j$ in such a way that in $Q^{y,q}$, $\chi(i,j,y,q)=\chi(i,j,x,p)+1$, since $A_i$
and $A_j$ are tracing complementary Hamiltonian cycles with respect to ${\mathcal R}^{\set{i,j}}$
this ensures that $\chi(j,i,y,q)=\chi(j,i,x,p)+1$, thereby maintaining the invariant property.

Noting that for each distinct pair $\tuple{i,j}$, we either have ${\mathcal R}^{\set{i,j}}$
allocated to $A_i$ in $P^{(1)}$ or ${\mathcal R}^{\set{i,j}}$ allocated to $A_j$ in $P^{(1)}$,
the description just outlined indicates that the allocation $P^{(d)}=Q^{x,p}$ is completely specified
as follows. 
\begin{quote}
The cube position, $\chi(i,j,x,p)$, satisfies,
\[
\chi(i,j,x,p)~=~
\left\{
{
\begin{array}{lcl}
0&\mbox{ if }&x=0\mbox{ and }p=k-1\\
1~+~\chi(i,j,x-1,k-1)&\mbox{ if }&\mbox{$x\geq 1$, $p=0$, and $p\not\in\set{i,j}$}\\
\chi(i,j,x-1,k-1)&\mbox{ if }&\mbox{$x\geq 1$, $p=0$, and $p\in\set{i,j}$}\\
1~+~\chi(i,j,x,p-1)&\mbox{ if }&\mbox{$1\leq p\leq k-1$, and $p\not\in\set{i,j}$}\\
\chi(i,j,x,p-1)&\mbox{ if }&\mbox{$1\leq p\leq k-1$, and $p\in\set{i,j}$}
\end{array}
}
\right.
\]
For each $i$, the subset of ${\mathcal R}^{\set{i,j}}$ that is held by $A_i$ in the allocation 
$Q^{x,p}$ is,
\[
\begin{array}{lcl}
\mbox{{
\large $\underline{v}^{(\chi(i,j,x,p))}$}}&\mbox{ {\rm if} }&{\mathcal R}^{\set{i,j}}\subseteq P_{i}^{(1)}\\
\mbox{{
\large $\underline{w}^{(\chi(i,j,x,p))}$}}&\mbox{ {\rm if} }&{\mathcal R}^{\set{i,j}}\subseteq P_{j}^{(1)}
\end{array}
\]
(where we recall that $s$-bit labels in the hypercube ${\mathcal H}_s$ are identified with subsets
of ${\mathcal R}^{\set{i,j}}$.)
\end{quote}
The tables below illustrates this process for our example.
{\small 
\[
\begin{array}{c}
\begin{array}{c|ll|ccc|ccc|ccc|ccc|c}
& & & &A_0& & &A_1& & &A_2& & &A_3& &\\
& & &i~j&i~j&i~j&i~j&i~j&i~j&i~j&i~j&i~j&i~j&i~j&i~j&\mbox{{\small ${\mathcal A}^{\tuple{P^{(d-1)},P^{(d)}}}$}}\\
d&x&p&0~1&0~2&0~3&1~0&1~2&1~3&2~0&2~1&2~3&3~0&3~1&3~2&\\ \hline
1&0&3&111&000&111&000&111&000&111&000&111&000&111&000&\mbox{--}\\ \hline
2&1&0&111&000&111&000&110&001&111&001&110&000&110&001&\mbox{{\small $\set{A_1,A_2,A_3}$}}\\
3&1&1&111&001&110&000&110&001&110&001&010&001&110&101&\mbox{{\small $\set{A_0,A_2,A_3}$}}\\
4&1&2&110&001&010&001&110&101&110&001&010&101&010&101&\mbox{{\small $\set{A_0,A_1,A_3}$}}\\
5&1&3&010&101&010&101&010&101&010&101&010&101&010&101&\mbox{{\small $\set{A_0,A_1,A_2}$}}\\ \hline
6&2&0&010&101&011&101&011&100&010&100&011&101&011&100&\mbox{{\small $\set{A_1,A_2,A_3}$}}\\
7&2&1&010&100&001&101&011&100&011&100&001&100&011&110&\mbox{{\small $\set{A_0,A_2,A_3}$}}\\
8&2&2&011&100&001&100&011&110&011&100&001&110&001&110&\mbox{{\small $\set{A_0,A_1,A_3}$}}\\
9&2&3&001&110&001&110&001&110&001&110&001&110&001&110&\mbox{{\small $\set{A_0,A_1,A_2}$}}\\ \hline
\vdots&\vdots&\vdots& &\vdots& & &\vdots& & &\vdots& & &\vdots& &\vdots
\end{array}\\
\mbox{{\bf Subsets of ${\mathcal R}^{\set{i,j}}$ held by $A_i$ in $Q^{x,p}$ ($k=4$, $s=3$)}}
\end{array}
\]
}
\[
\begin{array}{c}
\begin{array}{c|ll|ccc|ccc|ccc|ccc|c}
& & & &A_0& & &A_1& & &A_2& & &A_3& &\\
& & &i~j&i~j&i~j&i~j&i~j&i~j&i~j&i~j&i~j&i~j&i~j&i~j&{\mathcal A}^{\tuple{P^{(d-1)},P^{(d)}}}\\
d&x&p&0~1&0~2&0~3&1~0&1~2&1~3&2~0&2~1&2~3&3~0&3~1&3~2&\\ \hline
1&0&3&0 &0 &0 &0 &0 &0 &0 &0 &0 &0 &0 &0&\mbox{--}\\ \hline
2&1&0&0 &0 &0 &0 &1 &1 &0 &1 &1 &0 &1 &1&\set{A_1,A_2,A_3}\\
3&1&1&0 &1 &1 &0 &1 &1 &1 &1 &2 &1 &1 &2&\set{A_0,A_2,A_3}\\
4&1&2&1 &1 &2 &1 &1 &2 &1 &1 &2 &2 &2 &2&\set{A_0,A_1,A_3}\\
5&1&3&2 &2 &2 &2 &2 &2 &2 &2 &2 &2 &2 &2&\set{A_0,A_1,A_2}\\ \hline
6&2&0&2 &2 &2 &2 &3 &3 &2 &3 &3 &2 &3 &3&\set{A_1,A_2,A_3}\\
7&2&1&2 &3 &3 &2 &3 &3 &3 &3 &4 &3 &3 &4&\set{A_0,A_2,A_3}\\
8&2&2&3 &3 &4 &3 &3 &4 &3 &3 &4 &4 &4 &4&\set{A_0,A_1,A_3}\\
9&2&3&4 &4 &4 &4 &4 &4 &4 &4 &4 &4 &4 &4&\set{A_0,A_1,A_2}\\ \hline
\vdots&\vdots&\vdots& &\vdots& & &\vdots& & &\vdots& & &\vdots& &\vdots
\end{array}\\
\mbox{{\bf Cube Positions $\chi(i,j,x,p)$ ($k=4$, $s=3$)}}
\end{array}
\]
It is certainly the case that this process of applying successive rounds of $k$ deals could
be continued, however, we wish to do this only so long as it is not possible to go from
some allocation $P^{(d)}$ in the sequence to another $P^{(d+r)}$ for some $r\geq 2$ via
an $M(k-1)$-contract.

Now if $Q^{x,p}$ and $Q^{y,q}$ are distinct allocations generated by the process above then the
deal $\delta=\tuple{Q^{x,p},Q^{y,q}}$ is an $M(k-1)$-contract if and only if for some
$A_i$, $Q^{x,p}_i=Q^{y,q}_i$. It follows that if $\tuple{P^{(d)},P^{(d+r)}}$ is an $M(k-1)$-contract
for some $r>1$, then for some $i$ and all $j\not=i$,
$P_{i}^{(d+r)}\cap{\mathcal R}^{\set{i,j}}=P_{i}^{(d)}\cap{\mathcal R}^{\set{i,j}}$. 

To determine the minimum value of $r>1$ with which $P_{i}^{(d+r)}=P_{i}^{(d)}$, we observe that
without loss of generality we need consider only the case $d=i=0$, i.e. we determine the minimum number
of deals before $P_{0}^{(1)}$ reappears. First note that in each round, $Q^{x}$, if 
$\chi(0,j,x-1,k-1)=p$ then $\chi(0,j,x,k-1)=p+k-2$, i.e. each round advances the cube position
$k-2$ places: $\chi(0,j,x-1,k-1)=\chi(0,j,x,0)$ and $\chi(0,j,x,j)=\chi(0,j,x,j-1)$.
We can also observe that $P_{0}^{(1)}=Q_{0}^{0,k-1}\not=Q_{0}^{x,p}$ for any $p$ with $0<p<k-1$, since
\[
\chi(0,1,x,p)=\chi(0,2,x,p)=\ldots=\chi(0,k-1,x,p)
\]
only in the cases $p=0$ and $p=k-1$.
It follows that our value $r>1$ must be of the form $qk$ where
$q$ must be such that $q(k-2)$ is an {\em exact multiple} of $2^s$. From this observation we see that,
\[
\min\set{\mbox{ $r>1$ : $P_{0}^{(1)}=P_{0}^{(1+r)}$ }}\ =\ 
\min\set{\mbox{ $qk$ : $q(k-2)$ is a multiple of $2^s$}}
\]
Now, if $k$ is {\em odd} then $q=2^s$ is the minimal such value, so that $r=k2^s$.
If $k$ is even then it may be uniquely written in the form $z2^l+2$ where $z$ is {\em odd} so giving
$q$ as $1$ (if $l\geq s$) or $2^{s-l}$ (if $l\leq s$), so that these give
$r=k$ and $r=z2^s+2^{s-l+1}$, e.g. for $k=4$ and $s=3$, we get
$k=1\times2^1+2$ so that $r=2^3+2^{3-1+1}=16$ and in our example $P_{0}^{(1)}=P_{0}^{(17)}$ may be
easily verified. In total,
\[
r\geq\left\{
{
\begin{array}{lcl}
k2^s&\mbox{ if }&\mbox{$k$ is odd}\\
k&\mbox{ if }&\mbox{$k=z2^l+2$, $z$ is odd, and $l\geq s$}\\
2^s&\mbox{ if }&\mbox{$k=z2^l+2$, $z$ is odd and $l\leq s$}
\end{array}
}
\right.
\]
All of which immediately give $r\geq 2^s$ (in the second case $k\geq2^s$, so the inequality
holds trivially), and thus we can continue the chain of $M(k-1)$ contracts for at least $2^s$ moves.
Recalling that $m=s\mbox{{\scriptsize $\left({\begin{array}{c}k\\2\end{array}}\right)$}}$, this gives the
length of the $M(k-1)$-contract path 
\[
\Delta\ =\ \tuple{P^{(1)},P^{(2)},\ldots,P^{(t)}}
\]
written in terms of $m$ and $k$ as at 
least\footnote{We omit the rounding operation $\lfloor{\ldots}\rfloor$ in the exponent, which is
significant only if $m$ is not an exact multiple of 
{\scriptsize $\left({\begin{array}{c}k\\2\end{array}}\right)$},
in which event the device described in our overview of the proof is applied.}
\[
2^{m/\mbox{{\scriptsize $\left({\begin{array}{c}k\\2\end{array}}\right)$}}}\ -1\ =\ 
2^{\frac{2m}{k(k-1)}}~-~1
\]
It remains to define appropriate utility functions ${\mathcal U}=\tuple{u_0,\ldots,u_{k-1}}$ in order
to ensure that $\Delta$ is the unique IR $M(k-1)$-contract path realising the IR $M(k)$-deal
$\tuple{P^{(1)},P^{(t)}}$. In defining ${\mathcal U}$ it will be convenient to denote $\Delta$ as the path
\[
\Delta=\tuple{Q^{0,k-1},Q^{1,0},Q^{1,1},\ldots,Q^{1,k-1},\ldots,Q^{x,p},\ldots,Q^{r,k-1}}
\]
and, since $rk\geq2^s$, we may without loss of generality, focus on the first $2^s$ allocations
in this contract path.

Recalling that $\chi(i,j,x,p)$ is the index of the $s$-bit label $\underline{u}$ corresponding
to $Q_{i}^{x,p}\cap{\mathcal R}^{\set{i,j}}$ in the relevant Hamiltonian cycle -- i.e. ${\mathcal S}^{(v)}$
if ${\mathcal R}^{\set{i,j}}\subseteq Q_{i}^{0,k}$, ${\mathcal S}^{(w)}$ if
${\mathcal R}^{\set{i,j}}\subseteq Q_{j}^{0,k-1}$ -- we note the following properties of
the sequence of allocations defined by $\Delta$ that hold for each distinct $i$ and $j$.
\begin{enumerate}
\item[P1.]
$\forall~x,p\ \chi(i,j,x,p)=\chi(j,i,x,p)$
\item[P2.]
If $Q^{y,q}$ is the immediate successor of $Q^{x,p}$ in $\Delta$ then
$\chi(i,j,y,q)\leq \chi(i,j,x,p)+1$ with equality if and only if $q\not\in\set{i,j}$.
\item[P3.]
$\forall~i',j'$ with $0\leq i',j'\leq k-1$, $\chi(i,j,x,k-1)=\chi(i',j',x,k-1)$.
\end{enumerate}
The first two properties have already been established in our description of $\Delta$. The third
follows from the observation that within each round $Q^{x}$, each cube position is advanced
by exactly $k-2$ in progressing from $Q^{x-1,0}$ to $Q^{x,k-1}$.

The utility function $u_i$ is now given, for $S\subseteq{\mathcal R}_m$, by
\[
u_i(S)=
\left\{
{
\begin{array}{ll}
\sum_{j\not=i}~\chi(i,j,x,p)&\mbox{ if }S=Q_{i}^{x,p}\mbox{ for some $0\leq x\leq r$, $0\leq p\leq k-1$}\\
-2^{km}&\mbox{ otherwise}
\end{array}
}
\right.
\]
We claim that, with these choices, 
\[
\Delta=\tuple{Q^{0,k-1},Q^{1,0},Q^{1,1},\ldots,Q^{1,k-1},\ldots,Q^{x,p},\ldots,Q^{r,k-1}}
\]
is the unique IR $M(k-1)$-contract path realising the IR $M(k)$-deal $\tuple{Q^{0,k-1},Q^{r,k-1}}$.
Certainly, $\Delta$ {\em is} an IR $M(k-1)$-contract path: each deal $\delta=\tuple{Q^{x,p},Q^{y,q}}$
on this path has $|{\mathcal A}^\delta|=k-1$ and since for each agent $A_i$ in 
${\mathcal A}^\delta={\mathcal A}\setminus \set{A_q}$ the utility of $Q_{i}^{y,q}$ has increased by exactly
$k-2$, i.e. each cube position of $i$ with respect to $j$ whenever $q\not\in\set{i,j}$ has increased,
it follows that $\sigma_u(Q^{y,q})>\sigma_u(Q^{x,p})$ and hence $\tuple{Q^{x,p},Q^{y,q}}$ is IR.

We now show that $\Delta$ is the {\em unique} IR $M(k-1)$-contract path continuation of $Q^{0,k-1}$
Suppose $\delta=\tuple{Q^{x,p},P}$ is a deal that deviates from the contract
path $\Delta$ (having followed it through to the allocation $Q^{x,p}$). Certainly both of the following
must hold of $P$: for each $i$, $P_i\subseteq\cup_{j\not=i}{\mathcal R}^{\set{i,j}}$; and there
is a $k$-tuple of pairs $\tuple{(x_0,p_0),\ldots,(x_{k-1},p_{k-1})}$ with which
$P_i=Q_{i}^{x_{i},p_{i}}$, for if either fail to be the case for some $i$, then
$u_i(P_i)=-2^{km}$ with the consequent effect that $\sigma_u(P)<0$ and thence not IR. Now, if
$Q^{y,q}$ is the allocation that would succeed $Q^{x,p}$ in $\Delta$ then $P\not=Q^{y,q}$, and
thus for at least one agent, $Q_{i}^{{x_i},p_{i}}\not=Q_{i}^{y,q}$. It cannot be the
case that $Q_{i}^{{x_i},p_{i}}$ corresponds to an allocation occurring {\em strictly later}
than $Q_{i}^{y,q}$ in $\Delta$ since such allocations could not be realised by an $M(k-1)$-contract.
In addition, since $P_i=Q_{i}^{{x_i},p_{i}}$ it must be the case that $|{\mathcal A}^\delta|=k-1$
since exactly $k-1$ cube positions in the holding of $A_i$ must change. It follows that there
are only two possibilities for $(y_i,p_i)$: $P_i$ reverts to the allocation immediately
preceding $Q_{i}^{x,p}$ or advances to the holding $Q_{i}^{y,q}$. 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 $M(k-1)$-contract. On the other hand if $P$ corresponds to the allocation
preceding $Q^{x,p}$ then $\delta$ is not IR. We deduce, therefore, that the {\em only} IR $M(k-1)$ deal
that is consistent with $Q^{x,p}$ is that prescribed by $Q^{y,q}$.

This completes the analysis needed for the proof of part (b) of the theorem. It is clear that since the system
contains only $k$ agents, any deal $\tuple{P,Q}$ can be effected with a single $M(k)$-contract, thereby
establishing part (a). For part (c) -- that the IR deal $\tuple{P^{(1)},P^{(t)}}$ cannot be
realised using an {\em individually rational} $M(k-2)$-contract path, it suffices to observe that
since the class of IR $M(k-2)$-contracts are a subset of the class of IR $M(k-1)$-contracts, were it the
case that an IR $M(k-2)$-contract path existed to implement $\tuple{P^{(1)},P^{(t)}}$, this would
imply that $\Delta$ was not the {\em unique} IR $M(k-1)$-contract path. We have, however, proved that
$\Delta$ {\em is} unique, and part (c) of the theorem follows.
\end{proof}
We obtain a similar development of Corollary~\ref{cor:other-rationals} in
\begin{cor}\label{cor:mk-other-rational}
For all $k\geq 3$, $n\geq k$, $m\geq\mbox{{\scriptsize $\left({\begin{array}{c}k\\2\end{array}}\right)$}}$
and each of the cases below,
\begin{enumerate}
\item[a.]
$\Phi_k(\delta)$ holds if and only if $\delta$ is a cooperatively rational $M(k)$-contract.
\newline
$\Psi(\delta)$ holds if and only if $\delta$ is cooperatively rational.
\item[b.]
$\Phi_k(\delta)$ holds if and only if $\delta$ is $\delta$ is an equitable $M(k)$-contract.
\newline
$\Psi(\delta)$ holds if and only if $\delta$ is is equitable.
\end{enumerate}
there is a resource allocation setting $\tuple{{\mathcal A},{\mathcal R},{\mathcal U}}$ and
a $\Psi$-deal $\delta=\tuple{P,Q}$ for which
\[
\begin{array}{lcclr}
L^{{\rm opt}}(\delta,\tuple{{\mathcal A},{\mathcal R},{\mathcal U}},\Phi_k)&\mbox{ $=$ }&1&\mbox{ }&(a)\\
L^{{\rm opt}}(\delta,\tuple{{\mathcal A},{\mathcal R},{\mathcal U}},\Phi_{k-1})&\mbox{ $\geq$ }&
2^{\lfloor{2m/k(k-1)}\rfloor} -1&\mbox{ }&(b)\\
L^{{\rm opt}}(\delta,\tuple{{\mathcal A},{\mathcal R},{\mathcal U}},\Phi_{k-2})&&\mbox{ {\rm is undefined}}&
\mbox{ }&(c)
\end{array}
\]
\end{cor}
\begin{proof}
As with the proof of Corollary~\ref{cor:other-rationals} in relation to
Theorem~\ref{thm:ir-o-bounds}, in each case we employ the
contract path from the proof of Theorem~\ref{thm:mk-hierarchy-ir}, varying the definition
of ${\mathcal U}=\tuple{u_1,u_2,\ldots,u_k}$ in order to establish each result.
Thus let
\[
\begin{array}{lcl}
\Delta_m&\mbox{ $=$ }&\tuple{P^{(1)},P^{(2)},\ldots,P^{(r)},\ldots,P^{(t)}}\\
        &\mbox{ $=$ }&\tuple{Q^{0,k-1},Q^{1,0},\ldots,Q^{x,p},\ldots,Q^{z,r}}
\end{array}
\]
be the $M(k-1)$-contract path realising the $M(k)$-deal $\tuple{P^{(1)},P^{(t)}}$ described
in the proof of Theorem~\ref{thm:mk-hierarchy-ir}, this path having length
$t\geq 2^{\mbox{{\scriptsize $\lfloor{2m/k(k-1)}$}}}-1$.
\begin{enumerate}
\item[a.]
The utility functions ${\mathcal U}=\tuple{u_0,\ldots,u_{k-1}}$ of Theorem~\ref{thm:mk-hierarchy-ir}
ensure that $\tuple{P^{(1)},P^{(t)}}$ is cooperatively rational and that $\Delta_m$ is
a cooperatively rational $M(k-1)$-contract path realising $\tuple{P^{(1)},P^{(t)}}$: the utility held
by $A_i$ never decreases in value and there is at least one agent (in fact exactly $k-1$) whose
utility increases in value. Furthermore $\Delta_m$ is the unique cooperatively rational $M(k-1)$-contract
path realising $\tuple{P^{(1)},P^{(t)}}$ since, by the same argument used in Theorem~\ref{thm:mk-hierarchy-ir},
any deviation will result in some agent suffering a loss of utility.
\item[b.]
Set the utility functions ${\mathcal U}=\tuple{u_0,\ldots,u_{k-1}}$ as,
\[
u_i(S)=\left\{
{
\begin{array}{lcl}
-1&\mbox{ if }&S\not=Q_{i}^{x,p}\mbox{ for any $Q^{x,p}\in\Delta_m$}\\
xk^2+k-i&\mbox{ if }&S=Q_{i}^{x,k-1}\\
(x-1)k^2+k+p&\mbox{ if }&\mbox{$S=Q_{0}^{x,p}$, $p<k-1$ and $i=0$}\\
(x-1)k^2+k-i+p+1&\mbox{ if }&\mbox{$S=Q_{i}^{x,p}$, $p<i-1$ and $i\not=0$.}\\
xk^2+1&\mbox{ if }&\mbox{$S=Q_{i}^{x,i-1}=Q_{i}^{x,i}$ and $i\not=0$.}\\
xk^2+1+p-i&\mbox{ if }&\mbox{$S=Q_{i}^{x,p}$, $p>i$ and $i\not=0$}
\end{array}
}
\right.
\]
To see that these choices admit $\Delta_m$ as an equitable $M(k-1)$-contract path
realising the equitable deal $\tuple{Q^{0,k-1},Q^{z,r}}$, we first note that
\[
\min_{0\leq i\leq k-1}~~\set{u_i(Q_{i}^{z,r})}~>~1~=~\min_{0\leq i\leq k-1}~~\set{u_{i}(Q_{i}^{0,k-1})}
\]
thus, $\tuple{Q^{0,k-1},Q^{z,r}}$ is indeed equitable. Consider any deal $\delta=\tuple{Q^{x,p},Q^{y,q}}$
occurring within $\Delta_m$. It suffices to show that
\[
\min_{0\leq i\leq k-1}~~\set{u_i(Q_{i}^{x,p})}~\not=~u_q(Q_{q}^{x,p})
\]
since $A_q\not\in{\mathcal A}^\delta$, and for all other agents $u_i(Q_{i}^{y,q})>u_i(Q_{i}^{x,p})$.
We have two possibilities: $q=0$ (in which case $p=k-1$ and $y=x+1$); $q>0$ (in which case $p=q-1$). 
Consider the first of these: $u_0(Q_{0}^{x,k-1})=xk^2+k$, however, 
\[
\min\set{u_i(Q_{i}^{x,k-1})}=xk^2+1=u_{k-1}(Q_{k-1}^{x,k-1})
\]
and hence every deal $\tuple{Q^{x,k-1},Q^{x+1,0}}$ forming part of $\Delta_m$ is equitable.

In the remaining case, $u_q(Q_{q}^{x,q-1})=xk^2+1$ and
\[
\begin{array}{lcl}
\min\set{u_i(Q_{i}^{x,q-1})}&\mbox{ $\leq$ }&u_0(Q_{0}^{x,q-1})\\
&\mbox{ $=$ }&(x-1)k^2+k+q-1\\
&\mbox{ $<$ }&xk^2-(k^2-2k+1)\\
&\mbox{ $=$ }&xk^2-(k-1)^2\\
&\mbox{ $<$ }&xk^2+1\\
&\mbox{ $=$ }&u_{q}(Q_{q}^{x,q-1})
\end{array}
\]
and thus the remaining deals $\tuple{Q^{x,q-1},Q^{x,q}}$ within $\Delta_m$ are equitable.
By a similar argument to that employed in Theorem~\ref{thm:mk-hierarchy-ir} it follows that $\Delta_m$ is
the unique equitable $M(k-1)$-contract path realising $\tuple{Q^{0,k-1},Q^{z,r}}$.
\end{enumerate}
\end{proof}
\subsection*{Monotone Utility Functions and $M(k)$-contract paths}
The device used to develop Theorem~\ref{thm:ir-o-bounds} to obtain the path
of Theorem~\ref{thm:mono-ir-o} can be
applied to the rather more intricate construction of Theorem~\ref{thm:mk-hierarchy-ir}, thereby
allowing exponential lower bounds on $\rho^{\max}_{{\rm mono}}(n,m,\Phi_k,\Psi)$ to be derived.
We will merely outline the approach rather than present a detailed technical exposition.
We recall that it became relatively straightforward to define suitable monotone utility functions
once it was ensured that the subset sizes of interest -- i.e. those for allocations
arising in the $O$-contract path -- were forced to fall into a quite restricted range. The main
difficulty that arises in applying similar methods to the path $\Delta$ of Theorem~\ref{thm:mk-hierarchy-ir}
is the following: in the proof of Theorem~\ref{thm:mono-ir-o} we consider two agents
so that converting $\Delta_s$ from a setting with $s$ resources
in Theorem~\ref{thm:ir-o-bounds} to $ext(\Delta_s)$ with $2s$ resources in Theorem~\ref{thm:mono-ir-o}
is achieved by combining ``complementary'' allocations, i.e. $\alpha\subseteq{\mathcal R}_s$ with 
$\overline{\alpha}\subseteq{\mathcal T}_s$. We can exploit
two facts, however, to develop a path $multi(\Delta)$ for which monotone
utility functions could be defined: the resource set ${\mathcal R}_m$
in Theorem~\ref{thm:mk-hierarchy-ir} consists of {\scriptsize $\left({\begin{array}{c}k\\2\end{array}}\right)$}
disjoint sets of size $s$; and any deal $\delta$ on the path $\Delta$ involves a reallocation
of ${\mathcal R}^{\set{i,j}}$ between $A_i$ and $A_j$ when $\set{i,j}\subseteq{\mathcal A}^\delta$.
Thus letting ${\mathcal T}_m$ be formed by {\scriptsize $\left({\begin{array}{c}k\\2\end{array}}\right)$}
disjoint sets, ${\mathcal T}^{\set{i,j}}$ each of size $s$, suppose that $P^{(d)}_{i}$ is described
by
\[
\alpha^{(d)}_{i,0}~\alpha^{(d)}_{i,1}~\cdots~\alpha^{(d)}_{i,i-1}~\alpha^{(d)}_{i,i+1}~\cdots~
\alpha^{(d)}_{i,k-1}
\]
with $\alpha_{i,j}^{(d)}$ the $s$-bit label corresponding to the subset of $R^{\set{i,j}}$ that is
held by $A_i$ in $P^{(d)}$. Consider the sequence of allocations,
\[
multi(\Delta)~=~\tuple{C^{(1)},C^{(2)},\ldots,C^{(t)}}
\]
in a resource allocation setting have $k$ agents and $2m$ resources -- ${\mathcal R}_m\cup{\mathcal T}_m$
for which $C^{(d)}_{i}$ is characterised by
\[
\beta^{(d)}_{i,0}~\beta^{(d)}_{i,1}~\cdots~\beta^{(d)}_{i,i-1}~\beta^{(d)}_{i,i+1}~\cdots~
\beta^{(d)}_{i,k-1}
\]
In this, $\beta_{i,j}^{(d)}$, indicates the subset of ${\mathcal R}^{\set{i,j}}\cup{\mathcal T}^{\set{i,j}}$
described by the $2s$-bit label,
\[
\beta^{(d)}_{i,j}~~=~~\alpha_{i,j}^{(d)}~\overline{\alpha_{i,j}^{(d)}}
\]
i.e. $\alpha_{i,j}^{(d)}$ selects a subset of ${\mathcal R}^{\set{i,j}}$ while 
$\overline{\alpha_{i,j}^{(d)}}$ a subset of ${\mathcal T}^{\set{i,j}}$. 

It is immediate from this construction that for each allocation $C^{(d)}$ in $multi(\Delta)$ and
each $A_i$, it is always the case that $|C^{(d)}_{i}|=(k-1)s$. It follows, therefore, that the
only subsets that are relevant to the definition of {\em monotone} utility functions with which
an analogous result to Theorem~\ref{thm:mk-hierarchy-ir} for the path $multi(\Delta)$ could
be derived, are those of
size $(k-1)s$: if $S\subseteq{\mathcal R}_m\cup{\mathcal T}_m$ has $|S|<(k-1)s$, we can fix
$u_i(S)$ as a small enough negative value; similarly if $|S|>(k-1)s$ then $u_i(S)$ can be set to
a large enough positive 
value.\footnote{It is worth noting that the ``interpolation'' stage used in
Theorem~\ref{thm:mono-ir-o} is not needed in forming $multi(\Delta)$: 
the deal $\tuple{C^{(d)},C^{(d+1)}}$ is an
$M(k-1)$-contract. We recall that in going from $\Delta_s$ of Theorem~\ref{thm:ir-o-bounds}
to $ext(\Delta_s)$ the intermediate stage -- $double(\Delta_s)$ -- was not an
$O$-contract path.}

Our description in the preceding paragraphs, can be summarised in the following
result, whose proof is omitted: extending
the outline given above to a formal lower bound proof, is largely a technical exercise employing much
of the analysis already introduced, and since nothing signifcantly new is required for such
an analysis we shall not give a detailed presentation of it.
\begin{thm}\label{thm:mono-mk-hierarchy-ir}
Let $\Phi_k(P,Q)$ be the predicate which holds whenever $\tuple{P,Q}$ is an IR $M(k)$-contract.
For all $k\geq 3$, $n\geq k$ and $m\geq\mbox{{\scriptsize $2\left({\begin{array}{c}k\\2\end{array}}\right)$}}$,
there is
a resource allocation setting $\tuple{{\mathcal A},{\mathcal R},{\mathcal U}}$ in which every $u\in{\mathcal U}$
is {\em monotone}, and an
IR deal $\delta=\tuple{P,Q}$ for which,
\[
\begin{array}{lcclr}
L^{{\rm opt}}(\delta,\tuple{{\mathcal A},{\mathcal R},{\mathcal U}},\Phi_k)&\mbox{ $=$ }&1&\mbox{ }&(a)\\
L^{{\rm opt}}(\delta,\tuple{{\mathcal A},{\mathcal R},{\mathcal U}},\Phi_{k-1})&\mbox{ $\geq$ }&
2^{\lfloor{m/k(k-1)}\rfloor} -1&\mbox{ }&(b)\\
L^{{\rm opt}}(\delta,\tuple{{\mathcal A},{\mathcal R},{\mathcal U}},\Phi_{k-2})&&\mbox{ {\rm is undefined}}&
\mbox{ }&(c)
\end{array}
\]
\end{thm}
\section{Related Work}\label{section:related-work}
The principal focus of this article has considered a property of contract paths
realising rational reallocations $\tuple{P,Q}$ when the constituent deals are required
to conform to a structural restriction and satisfy a rationality constraint. In
Section~\ref{section:o-contract} the structural restriction limited deals to those
involving a single resource, i.e. $O$-contracts. For the rationality constraint forcing
deals strictly to improve utilitarian social welfare, i.e. to be individually rational (IR)
we have the following properties.
\begin{enumerate}
\item[a.]
There are resource allocation settings $\tuple{{\mathcal A},{\mathcal R},{\mathcal U}}$ within which
there are IR reallocations $\tuple{P,Q}$ that {\em cannot} be realised by a sequence of IR $O$-contracts.
\cite[Proposition~2]{Sandholm:1998}
\item[b.]
Every IR reallocation, $\tuple{P,Q}$, that {\em can} be realised by an IR $O$-contract path,
can be realised by an IR $O$-contract path of length at most $n^m - (n-1)m$.
\cite[Proposition~2]{Sandholm:1998}
\item[c.]
Given $\tuple{{\mathcal A},{\mathcal R},{\mathcal U}}$ together with an IR reallocation $\tuple{P,Q}$
the problem of deciding if $\tuple{P,Q}$ can be implemented by an IR $O$-contract path
is {\sc np}--hard, even if $|{\mathcal A}|=2$ and both utility functions are monotone.
\shortcite[Theorem~11]{dunne:2003}.
\item[d.]
There are resource allocation settings $\tuple{{\mathcal A},{\mathcal R},{\mathcal U}}$ within which
there are IR reallocations $\tuple{P,Q}$ that {\em can} be realised by an IR $O$-contract path, but
with any such path having length exponential in $m$. This holds even in the case $|{\mathcal A}|=2$
and both utility functions are monotone.
(Theorem~\ref{thm:ir-o-bounds} and Theorem~\ref{thm:mono-ir-o} of Section~\ref{section:o-contract})
\end{enumerate}
In a recent article \shortciteA{Endriss-et-al:2004} analyse contract path length
also considering $O$-contracts with various rationality constraints. Although the approach
is from a rather different perspective, the central question addressed --
``How many rational deals are required to reach an optimal allocation?'',
\shortcite[Table~1,~p.~629]{Endriss-et-al:2004} -- is closely related to the issues discussed above.
One significant difference in the analysis of rational $O$-contracts
from \citeS{Sandholm:1998} treatment and the results in Section~\ref{section:o-contract}
is that in \shortcite{Endriss-et-al:2004} the utility functions are restricted so that {\em every}
rational reallocation $\tuple{P,Q}$ {\em can} be realised by a rational $O$-contract path. The
two main restrictions examined are requiring utility functions to be {\em additive}, i.e.
for every $S\subseteq{\mathcal R}$, $u(S)=\sum_{r\in S} u(r)$; and, requiring the value returned
to be either $0$ or $1$, so-called $0-1$ utility functions. Additive utility functions are considered
in the case of IR $O$-contracts \shortcite[Theorems~3,~9]{Endriss-et-al:2004}, whereas $0-1$
utility functions for cooperatively rational $O$-contracts \shortcite[Theorems~4,~11]{Endriss-et-al:2004}.
Using $\rho^{\max}_{{\rm add}}(n,m,\Phi,\Psi)$ and $\rho^{\max}_{{\rm 0-1}}(n,m,\Phi,\Psi)$ to
denote the functions introduced in Definition~\ref{defn:phi-psi-path} where
all utility functions are additive (respectively $0-1$), cf. the definition of $\rho^{\max}_{{\rm mono}}$,
then with $\Phi_1(P,Q)$ holding if $\tuple{P,Q}$ is an IR $O$-contract; $\Phi_2(P,Q)$ holding
if $\tuple{P,Q}$ is a cooperatively rational $O$-contract and $\Psi(P,Q)$ true when
$\tuple{P,Q}$ is IR, we may formulate Theorems 9 and 11 of \shortcite{Endriss-et-al:2004} in terms
of the framework used in Definition~\ref{defn:phi-psi-path}, as
\[
\begin{array}{lclcr}
\rho^{\max}_{{\rm add}}(n,m,\Phi_1,\Psi)&\mbox{ $=$ }&m&\mbox{ $~$ }&\shortcite[Theorem~9]{Endriss-et-al:2004}\\
\rho^{\max}_{{\rm 0-1}}(n,m,\Phi_2,\Psi)&\mbox{ $=$ }&m&\mbox{ $~$ }&\shortcite[Theorem~11]{Endriss-et-al:2004}
\end{array}
\]
We can, of course, equally couch Theorems~\ref{thm:ir-o-bounds} and \ref{thm:mono-ir-o} of
Section~\ref{section:o-contract} in terms of the ``shortest-path'' convention adopted in
\shortcite{Endriss-et-al:2004}, provided that the domains of utility and reallocation instances are restricted
to those for which an appropriate $O$-contract path exists. Thus, we can obtain the following development
of \shortcite[Table~1]{Endriss-et-al:2004} in the case of $O$-contracts.
{\scriptsize
\begin{table}[h]
\begin{tabular}{ccccccc}
Utility Functions & Additive & 0-1 & Unrestricted & Monotone & Unrestricted & Monotone \\
Rationality & IR & CR & IR & IR & CR & CR \\
Shortest Path & $m$ & $m$ & $\Omega(2^m)$ & $\Omega(2^{m/2})$ & $\Omega(2^m)$ & $\Omega(2^{m/2})$\\
Complete & Yes & Yes & No & No & No & No
%\\
%Reference & \shortcite[Thm.~9]{Endriss-et-al:2004} & \shortciteA[Thm.~11]{Endriss-et-al:2004} &
%Theorem~\ref{thm:ir-o-bounds} & Theorem~\ref{thm:mono-ir-o} & Corollary~\ref{cor:other-rationals}(a) &
%Theorem~\ref{thm:mono-other-rational} (a)
\end{tabular}
\caption{How many $O$-contract rational deals are required to reach an allocation?
\newline
Extension of Table~1 from \shortcite[p.~629]{Endriss-et-al:2004}}\label{tab:o-contract-length}
\end{table}
}
\section{Conclusions and Further Work}
Our aim in this article has been to develop the earlier studies of \citeA{Sandholm:1998} concerning
the scope and limits of particular ``practical'' contract forms. While \citeA{Sandholm:1998} has established
that insisting on individual rationality in addition to the structural restriction prescribed
by $O$-contracts leads to scenarios which are incomplete (in the sense that there are individually
rational deals that cannot be realised by individually rational $O$-contracts) our focus has
been with respect to deals which can be realised by restricted contract paths, with the
intention of determining to what extent the combination of structural and rationality conditions increases
the number of deals required. We have shown that, using a number of natural definitions
of rationality, for settings involving $m$ resources, {\em rational} $O$-contract paths of length $\Omega(2^m)$ 
are needed, whereas without the rationality restriction on individual deals, at most $m$
$O$-contracts suffice to realise any deal. We have also considered a class of deals -- $M(k)$-contracts --
that were not examined in \cite{Sandholm:1998}, establishing for these cases that, when
particular rationality conditions are imposed, $M(k-1)$-contract paths of length $\Omega(2^{2m/k^2})$
are needed to realise a deal that can be achieved by a single $M(k)$-contract.

We note that our analyses have primarily been focused on worst-case lower bounds on path length when
appropriate paths exist, and as such there are several questions of practical interest that
merit further discussion. It may be noted that the path structures and associated utility functions
are rather artificial, being directed to attaining a path of a specific length meeting a given
rationality criterion. We have seen, however, in Theorems~\ref{thm:mono-ir-o} and \ref{thm:mono-other-rational}
as outlined in our discussion concluding Section~\ref{section:mk-results} that the issue of
exponential length contract paths continues to arise even when we require the utility functions to
satisfy a monotonicity condition. We can identify two classes of open question that arise
from these results.

Firstly, focusing on IR $O$-contract paths, it would be of interest to identify ``natural'' restrictions
on utility functions which would ensure that, {\em if} a deal $\tuple{P,Q}$ can be implemented
by an IR $O$-contract path, then it can be realised by one whose length is polynomially bounded in $m$, e.g. such as additivity mentioned in the preceding section.
We can interpret Theorem~\ref{thm:mono-ir-o}, as indicating that monotonicity does {\em not} guarantee ``short''
IR contract paths. We note, however, that there {\em are} 
some restrictions that suffice. To use a rather trivial example, if the number of {\em distinct} values that 
$\sigma_u$ can assume is at most $m^p$ for some {\em constant} $p$ then no IR $O$-contract path can
have length exceeding $m^p$: successive deals must strictly increase $\sigma_u$ and if this can
take at most $K$ different values then no IR contract path can have length exceeding $K$. As well as being
of practical interest, classes of utility function with the property being considered would also
be of some interest regarding one complexity issue. The result proved in \shortcite{dunne:2003} establishing
that deciding if an IR $O$-contract path exists is {\sc np}-hard, gives a {\em lower bound} on the
computational complexity of this problem. At present, no (non-trivial) {\em upper bound} on
this problem's complexity has been demonstrated. Our results in
Theorems~\ref{thm:ir-o-bounds} and \ref{thm:mono-ir-o} indicate that {\em if} this decision problem
is in {\sc np} (thus its complexity would be {\sc np}--complete rather than {\sc np}--hard) then the
required polynomial length existence certificate {\em may} have to be something other than the
path itself.\footnote{The use of ``may'' rather than ``must'' is 
needed because of the convention for representing utility functions employed in
\shortcite{dunne:2003}.}
We note that
the proof of {\sc np}--hardness in \shortcite{dunne:2003} constructs an instance in which $\sigma_u$
can take at most $O(m)$ distinct values: thus, from our example of a restriction
ensuring that if such are present then IR $O$-contract paths are ``short'', this result
of \shortcite{dunne:2003} indicates that the question of {\em deciding} their existence might remain
computationally hard.

Considering restrictions on the form of utility functions is one approach that could be taken regarding
finding ``tractable'' cases. An alternative
would be
to gain some insight into what the ``average'' path length is likely to be. In attempting to
address this question, however, a number of challenging issues arise. The most immediate of these concerns,
of course, the notion of modeling a distribution on utility function given our
definitions of rationality in terms of the value agents attach to their resource holdings. In principle
an average-case analysis of scenarios involving exactly {\em two} agents could be carried out
in purely graph-theoretic terms, i.e. without the complication of considering utility functions directly.
It is unclear, however, whether such a graph-theoretic analysis 
obviating the need for consideration of literal utility functions, can be extended beyond settings
involving exactly two agents. One difficulty arising with three or more agents is that
our utility functions have no allocative externalities, i.e. given an allocation $\tuple{X,Y,Z}$ to
three agents, $u_1(X)$ is unchanged should $Y\cup Z$ be redistributed among $A_2$ 
and $A_3$.\footnote{A very preliminary investigation of complexity-theoretic questions arising
in settings with allocative externalities is presented in  \cite{dunne:2004} where these are referred
to as ``context--dependent'': such
utility functions appear to have been neglected in the computational and algorithmic
analysis of resource allocation problems, although the idea is well-known to game-theoretic models in
economics from which the term  ``allocative externality'' originates.}

As one final set of issues that may merit further study we raise the following. In our constructions,
the individual deals on a contract path must satisfy both a {\em structural} condition (be an $O$-contract
or involve at most $k$ agents), and a {\em rationality} constraint. Focusing on $O$-contracts we
have the following extremes: from \cite{Sandholm:1998}, 
at most $m$ $O$-contracts suffice to realise any rational deal; from our results above,
$\Omega(2^m)$ {\em rational} $O$-contracts are needed to realise some rational deals. There are
a number of mechanisms we can employ to relax
the condition that every single deal be an $O$-contract and be rational. For example, allow
a path to contain some number of deals which are not $O$-contracts (but must still be IR)
or insist that all deals are $O$-contracts but allow some to be irrational. Thus, in the latter
case, if we go to
the extent of allowing up to $m$ irrational $O$-contracts, then any rational deal can be
realised efficiently. It would be of some interest to examine issues such as the effect of allowing
a {\em constant} number, $t$, of irrational deals and questions such as whether there are situations
in which $t$ irrational contracts yield a `short' contract path but $t-1$ force one of
exponential length. Of particular interest, from an application viewpoint, is the following: 
define a $(\gamma(m),O)$-path as
an $O$-contract path containing at most $\gamma(m)$ $O$-contracts which are
not individually rational. We know that if $\gamma(m)=0$ then individually rational
$(0,O)$-paths are not complete with respect to individually rational deals; similarly if $\gamma(m)=m$
then  $(m,O)$-paths {\em are} complete with respect to individually rational deals. A question
of some interest would be to establish if there is some $\gamma(m)=o(m)$ for which
$(\gamma(m),O)$-paths are complete with respect to individually rational deals {\em and}
with the maximum length of such a contract path bounded by a polynomial function of $m$.
\section*{Acknowledgements}
The author thanks the reviewers of an earlier version of this article for their valuable comments and
suggestions which have contributed significantly to its content and organisation.
The work reported in this article was carried out under the support of EPSRC Grant GR/R60836/01.

\bibliography{dunne05a}
\bibliographystyle{theapa}
%\end{thebibliography}
\end{document}
