$O$-contract Paths - Unrestricted Utility Functions

Our first result clarifies one issue in the presentation of [Sandholm, 1998, Proposition 2]: 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, [Sandholm, 1998, Proposition 2] establishes an upper bound on $\rho^{\max}(n,m,\Phi,\Psi)$. We now prove a similar order lower bound.

Theorem 3   Let $\Phi(P,Q)$ be the predicate which holds whenever $\langle P,Q\rangle$ is an IR $O$-contract and $\Psi(P,Q)$ that which holds whenever $\langle P,Q\rangle$ is IR. For $m\geq 7$

$$\rho^{\max}(2,m,\Phi,\Psi) \geq \left({\frac{77}{256}}\right) 2^m - 2$$

Proof. Consider a path ${\mathcal C}=\langle\alpha_1, \alpha_2,\ldots,\alpha_t\rangle$ in ${\mathcal H}_m$, with the following property⁴

$$\forall 1\leq i<j\leq t (j\geq i+2) \Rightarrow (\mbox{$... ...\alpha_j$ differ in at least 2 positions) } \mbox{ (SC)}$$

e.g. if $m=4$ then

$$\emptyset,\{r_1\}, \{r_1,r_3\},\{r_1,r_2,r_3\},\{r_2,r_3\},\{r_2,r_3,r_4\},\{r_2,r_4\}, \{r_1,r_2,r_4\}$$

is such a path as it corresponds to the sequence $\langle 0000,1000,1010,1110,0110,0111,0101,1101\rangle$.

Choose ${\mathcal C}^{(m)}$ to be a longest such path with this property that could be formed in ${\mathcal H}_m$, letting $\Delta_m=\langle P^{(1)},P^{(2)},\ldots,P^{(t)}\rangle$ be the sequence of allocations with $P^{(i)}=\langle\alpha_i,\overline{\alpha_i}\rangle$. 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}{... ...t\in\{\alpha_1,\alpha_2,\ldots,\alpha_t\} \end{array}} \right.$$

With this choice, the contract path $\Delta_m$ describes the unique IR $O$-contract path realising the IR deal $\langle P^{(1)},P^{(t)}\rangle$: 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 $\langle P^{(i)},P^{(j)}\rangle$ 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)}$.⁵

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 in [Kautz, 1958] in the context of coding theory and the lower bound on their length of $(77/256)2^m-2$ established in [Abbott & Katchalski, 1991].$\Box$

Example 1   Using the path

$$\begin{array}{lcl} {\mathcal C}^{(4)}&\mbox{ $=$ }&\langle ... ...alpha_4,\alpha_5,\alpha_6,\alpha_7,\alpha_8\rangle \end{array}$$

in the resource allocation setting $\langle\{a_1,a_2\},\{r_1,r_2,r_3,r_4\},\langle u_1,u_2\rangle \rangle$, if the utility functions are specified as in Table 1 below then $\sigma_u(\langle\alpha_1,\overline{\alpha}_1\rangle )=1$ and $\sigma_u(\langle\alpha_8,\overline{\alpha}_8\rangle )=8$. Furthermore, ${\mathcal C}^{(4)}$ describes the unique IR $O$-contract path realising the reallocation $\langle\langle\alpha_1,\overline{\alpha}_1\rangle , \langle\alpha_8,\overline{\alpha}_8\rangle \rangle$

Table 1: Utility function definitions for $m=4$ example.

$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$
$0000$	$1111$	$1$	$0$	$1$	$\alpha_1$	$1000$	$0111$	$1$	$1$	$2$	$\alpha_2$
$0001$	$1110$	$0$	$0$	$0$		$1001$	$0110$	$0$	$0$	$0$
$0010$	$1101$	$0$	$0$	$0$		$1010$	$0101$	$2$	$1$	$3$	$\alpha_3$
$0011$	$1100$	$0$	$0$	$0$		$1011$	$0100$	$0$	$0$	$0$
$0100$	$1011$	$0$	$0$	$0$		$1100$	$0011$	$0$	$0$	$0$
$0101$	$1010$	$4$	$3$	$7$	$\alpha_7$	$1101$	$0010$	$4$	$4$	$8$	$\alpha_8$
$0110$	$1001$	$3$	$2$	$5$	$\alpha_5$	$1110$	$0001$	$2$	$2$	$4$	$\alpha_4$
$0111$	$1000$	$3$	$3$	$6$	$\alpha_6$	$1111$	$0000$	$0$	$0$	$0$

There are a number of alternative formulations of ``rationality'' which can also be considered. For example

Definition 7   Let $\delta=\langle P,Q\rangle$ be a deal.

a.

$\delta$ is 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)$.

b.

$\delta$ is equitable if $\min_{i\in{\mathcal A}^\delta} u_i(Q_i) >\min_{i\in{\mathcal A}^\delta} u_i(P_i)$.

c.

$\delta$ is a Pigou-Dalton deal if ${\mathcal A}^\delta=\{i,j\}$, $u_i(P_i)+u_j(P_j)=u_i(Q_i)+u_j(Q_j)$ and $\vert u_i(Q_i)-u_j(Q_j)\vert<\vert u_i(P_i)-u_j(P_j)\vert$ (where $\vert\ldots\vert$ is absolute value).

There are a number of views we can take concerning the rationality conditions given in Definition 7. 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 7 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 at least one is better off. It may be noted that given the characterisation of Definition 4 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 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. [Endriss & Maudet, 2004b]. 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. [Atkinson, 1970; Chateauneuf et al., 2002; Kolm, 1976]

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

Corollary 1   For each of the cases below,

a.

$\Phi(\delta)$ holds if and only if $\delta$ is a cooperatively rational $O$-contract.
$\Psi(\delta)$ holds if and only if $\delta$ is cooperatively rational.

b.

$\Phi(\delta)$ holds if and only if $\delta$ is an equitable $O$-contract.
$\Psi(\delta)$ holds if and only if $\delta$ is equitable.

c.

$\Phi(\delta)$ holds if and only if $\delta$ is a Pigou-Dalton $O$-contract.
$\Psi(\delta)$ holds if and only if $\delta$ is a Pigou-Dalton deal.

$$\rho^{\max}(2,m,\Phi,\Psi) \geq \left({\frac{77}{256}}\right) 2^m - 2$$

Proof. We employ exactly the same sequence of allocations $\Delta_m$ described in the proof of Theorem 3 but modify the utility functions $\langle u_1,u_2\rangle$ for each case.

a.

Choose $\langle u_1,u_2\rangle$ with $u_2(\gamma)=0$ for all $\gamma\subseteq{\mathcal R}$ and

$$u_1(\gamma)=\left\{ { \begin{array}{lcl} k&\mbox{ if }&\gamm... ...\gamma\not\in\{\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$.

b.

Choose $\langle u_1,u_2\rangle$ with $u_2(\gamma)=u_1(\overline{\gamma})$ and

$$u_1(\gamma)=\left\{ { \begin{array}{lcl} k&\mbox{ if }&\gamm... ...\gamma\not\in\{\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.

c.

Choose $\langle u_1,u_2\rangle$ as

$$u_1(\gamma)=\left\{ { \begin{array}{lcl} k&\mbox{ if }&\gamm... ...gamma}\not\in\{\alpha_1,\ldots,\alpha_t\} \end{array}} \right.$$

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, $\vert u_2(\overline{\alpha_{i+1}})-u_1(\alpha_{i+1})\vert=2^m-2i-2$ which is strictly less than $\vert u_2(\overline{\alpha_i})-u_1(\alpha_i)\vert=2^m-2i$. Finally, any $O$-contract $\langle P,Q\rangle$ which deviates from this sequence will not be a Pigou-Dalton deal since

$$\vert u_2(Q_2)-u_1(Q_1)\vert = 2^m > \vert u_2(P_2)-u_1(P_1)\vert$$

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

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

Corollary 2   For each of the choices of $\langle\Phi,\Psi\rangle$ considered in Theorem 3 and Corollary 1, and all $n\geq2$,

$$\rho^{\max}(n,m,\Phi,\Psi) \geq \left({\frac{77}{256}}\right)2^m - 2$$

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 $\langle u_1,u_2\rangle$ as in each of the previous cases, we employ for $u_j$: $u_j(\emptyset)=1$, $u_j(S)=0$ whenever $S\not=\emptyset$ ( $\langle\Phi,\Psi\rangle$ as in Theorem 3); $u_j(S)=0$ for all $S$ (Corollary 1(a)); $u_j(\emptyset)=2^m$, $u_j(S)=0$ whenever $S\not=\emptyset$ (Corollary 1(b)); and, finally, $u_j(S)=2^m$ for all $S$, (Corollary 1(c)). Considering a realisation of the $\Psi$-deal $\langle P^{(1)},P^{(t)}\rangle$ the only $\Phi$-contract path admissible is the path $\Delta_m$ defined in the related proofs. This gives the lower bound stated.$\Box$

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

Fact 1   We recall that a $\Phi$-path, $\langle P^{(1)},\ldots,P^{(t)}\rangle$ is maximal if for each allocation $Q$, $\langle P^{(t)},Q\rangle$ is not a $\Phi$-deal.

a.

If $\langle P^{(1)},\ldots,P^{(t)}\rangle$ is any maximal path of cooperatively rational deals then $P^{(t)}$ is Pareto optimal.

b.

If $\langle P^{(1)},\ldots,P^{(t)}\rangle$ is any maximal path of 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 egalitarian social welfare.

The sequence of cooperatively rational deals in Corollary 1(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 1(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 1 guarantees convergence of particular deal sequences to optimal states it may be the case, as illustrated in Corollary 1(a-b), that the process of convergence takes considerable time.