Monotone Utility Functions and $M(k)$-contract paths

The device used to develop Theorem 3 to obtain the path of Theorem 4 can be applied to the rather more intricate construction of Theorem 6, 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 6 is the following: in the proof of Theorem 4 we consider two agents so that converting $\Delta_s$ from a setting with $s$ resources in Theorem 3 to $ext(\Delta_s)$ with $2s$ resources in Theorem 4 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 6 consists of $\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}^{\{i,j\}}$ between $A_i$ and $A_j$ when $\{i,j\}\subseteq{\mathcal A}^\delta$. Thus letting ${\mathcal T}_m$ be formed by $\left({\begin{array}{c}k\ 2\end{array}}\right)$ disjoint sets, ${\mathcal T}^{\{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^{\{i,j\}}$ that is held by $A_i$ in $P^{(d)}$. Consider the sequence of allocations,

$$multi(\Delta)=\langle C^{(1)},C^{(2)},\ldots,C^{(t)}\rangle$$

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}^{\{i,j\}}\cup{\mathcal T}^{\{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}^{\{i,j\}}$ while $\overline{\alpha_{i,j}^{(d)}}$ a subset of ${\mathcal T}^{\{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 $\vert C^{(d)}_{i}\vert=(k-1)s$. It follows, therefore, that the only subsets that are relevant to the definition of monotone utility functions with which an analogous result to Theorem 6 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 $\vert S\vert<(k-1)s$, we can fix $u_i(S)$ as a small enough negative value; similarly if $\vert S\vert>(k-1)s$ then $u_i(S)$ can be set to a large enough positive value.⁹

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.

Theorem 7   Let $\Phi_k(P,Q)$ be the predicate which holds whenever $\langle P,Q\rangle$ 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 $\langle{\mathcal A},{\mathcal R},{\mathcal U}\rangle$ in which every $u\in{\mathcal U}$ is monotone, and an IR deal $\delta=\langle P,Q\rangle$ for which,

$$\begin{array}{lcclr} L^{{\rm opt}}(\delta,\langle{\mathcal A... ...hi_{k-2})&&\mbox{ {\rm is undefined}}& \mbox{ }&(c) \end{array}$$