Extending the Characterization of Maximum Nash Welfare

Suppose that $f_{n}$ fulfills assumption (1). First, we show that $f_{n}$ satisfies

$\displaystyle f_{n}(x,x_{2},\ldots,x_{i-1},z/x,x_{i+1},\ldots,x_{n})=f_{n}(y,x_{2},\ldots,x_{i-1},z/y,x_{i+1},\ldots,x_{n})$

(2)

for all $i\in N\setminus\{1\}$ and $x_{2},\ldots,x_{i-1},x_{i+1},\ldots,x_{n},x,y,z>0$. Assume without loss of generality that $i=2$; the proof for any other $i\in\{3,\ldots,n\}$ is analogous. Let $x_{3},\ldots,x_{n},z>0$ be fixed throughout. Define $h:(0,\infty)\to[-\infty,\infty)$ by $h(x):=f_{n}(x,z/x,x_{3},\ldots,x_{n})$ for all $x>0$. Note that $h$ is continuous due to the continuity of $f_{n}$ on $(0,\infty)^{n}$. For any positive integer $k$ and any $x>0$, we have

	$\displaystyle h\left(\frac{k+1}{k}\cdot x\right)$	$\displaystyle=f_{n}\left((k+1)\cdot\frac{x}{k},\,k\cdot\frac{z}{(k+1)x},\,x_{3},\ldots,x_{n}\right)$
		$\displaystyle=f_{n}\left(k\cdot\frac{x}{k},\,(k+1)\cdot\frac{z}{(k+1)x},\,x_{3},\ldots,x_{n}\right)$		(by (1))
		$\displaystyle=f_{n}(x,z/x,x_{3},\ldots,x_{n})$
		$\displaystyle=h(x),$

so for any rational number $r=a/b>1$, we have

$\displaystyle h(rx)=h\left(\frac{a}{a-1}\cdot\frac{a-1}{a-2}\cdot\;\cdots\;\cdot\frac{b+1}{b}\cdot x\right)=h\left(\frac{a-1}{a-2}\cdot\;\cdots\;\cdot\frac{b+1}{b}\cdot x\right)=\cdots=h(x).$

Similarly, we have $h(rx)=h(x)$ for any rational number $0<r<1$, hence the same equation is true for all positive rational numbers $r$. Since $h$ is continuous and the positive rational numbers are dense in $(0,\infty)$, we can conclude that $h$ is constant, and thus, $f_{n}(x,z/x,x_{3},\ldots,x_{n})=f_{n}(y,z/y,x_{3},\ldots,x_{n})$ for all $x,y>0$. Hence, (2) is true for all $i\in N\setminus\{1\}$ and $x_{2},\ldots,x_{i-1},x_{i+1},\ldots,x_{n},x,y,z>0$.

Next, we prove by backward induction that for all integers $1\leq k\leq n$, there exists a continuous function $q_{k}:(0,\infty)^{k}\to[-\infty,\infty)$ such that $f_{n}(x_{1},\ldots,x_{n})=q_{k}(x_{1}x_{k+1}\cdots x_{n},x_{2},\ldots,x_{k})$ for all $x_{1},\ldots,x_{n}>0$. Then, $q:=q_{1}$ gives the desired conclusion.

For the base case $k=n$, we have $q_{n}:=f_{n}|_{(0,\infty)^{n}}$. For the inductive step, let $2\leq k\leq n$ be given, and assume that such a function $q_{k}$ exists; we shall prove that $q_{k-1}$ exists as well. Define $q_{k-1}$ by $q_{k-1}(y_{1},\ldots,y_{k-1}):=q_{k}(y_{1},\ldots,y_{k-1},1)$ for all $y_{1},\ldots,y_{k-1}>0$. Note that $q_{k-1}$ is continuous on $(0,\infty)^{k-1}$ due to the continuity of $q_{k}$ on $(0,\infty)^{k}$. Let $x_{1},\ldots,x_{n}>0$ be given. Then, by setting $x:=x_{1}$ and $y:=z:=x_{1}x_{k}$, we have

	$\displaystyle f_{n}(x_{1},\ldots,x_{n})$	$\displaystyle=f_{n}(x,x_{2},\ldots,x_{k-1},z/x,x_{k+1},\ldots,x_{n})$
		$\displaystyle=f_{n}(y,x_{2},\ldots,x_{k-1},z/y,x_{k+1},\ldots,x_{n})$		(by (2))
		$\displaystyle=f_{n}(x_{1}x_{k},x_{2},\ldots,x_{k-1},1,x_{k+1},\ldots,x_{n})$
		$\displaystyle=q_{k}(x_{1}x_{k}x_{k+1}\cdots x_{n},x_{2},\ldots,x_{k-1},1)$		(by the inductive hypothesis)
		$\displaystyle=q_{k-1}(x_{1}x_{k}\cdots x_{n},x_{2},\ldots,x_{k-1}),$

establishing the inductive step and therefore the lemma. ∎

The implication (a) $\Rightarrow$ (b) is trivial. For the implication (c) $\Rightarrow$ (a), if $f_{n}$ satisfies (c), then given a profile that admits an allocation where every agent receives positive utility, every allocation that can be chosen by the welfarist rule with function $f_{n}$ is also an allocation that can be chosen by MNW, which is known to be EF1 (Caragiannis et al., 2019); hence, $f_{n}$ also satisfies (a). It therefore remains to prove the implication (b) $\Rightarrow$ (c). Assume that $f_{n}$ satisfies (b); we will show that both statements (i) and (ii) of (c) hold.

To prove (i), it suffices to show that $f_{n}$ satisfies (1) for all $x_{1},\ldots,x_{n}>0$, positive integers $k$, and $i\in N\setminus\{1\}$. Indeed, once this is shown, Lemma 1 provides a continuous function $q:(0,\infty)\to[-\infty,\infty)$ satisfying $f_{n}(x_{1},x_{2},\ldots,x_{n})=q(x_{1}x_{2}\cdots x_{n})$ for all $x_{1},\ldots,x_{n}>0$. Note that $q$ must be strictly increasing because $f_{n}$ is strictly increasing on $(0,\infty)^{n}$, and $-\infty$ cannot be in the range of $q$ since $q$ is strictly increasing and its domain is an open set in $\mathbb{R}$.

To show (1), suppose on the contrary that (1) is false for some $x_{1},\ldots,x_{n}>0$, positive integer $k$, and $i\in N\setminus\{1\}$; assume without loss of generality that $i=2$, which means that

$\displaystyle f_{n}((k+1)x_{1},kx_{2},x_{3},\ldots,x_{n})\neq f_{n}(kx_{1},(k+1)x_{2},x_{3},\ldots,x_{n}).$

Suppose that

$\displaystyle f_{n}((k+1)x_{1},kx_{2},x_{3},\ldots,x_{n})<f_{n}(kx_{1},(k+1)x_{2},x_{3},\ldots,x_{n});$

the case where the inequality goes in the opposite direction can be handled similarly. By the continuity of $f_{n}$, there exists $\epsilon\in(0,x_{1})$ such that

$\displaystyle f_{n}((k+1)x_{1}-\epsilon,kx_{2},x_{3}\ldots,x_{n})<f_{n}(kx_{1}-\epsilon,(k+1)x_{2},x_{3},\ldots,x_{n}).$

(3)

Consider a profile with $m=kn+1$ goods, where $G^{\prime}:=\{g_{1},\ldots,g_{kn}\}=G\setminus\{g_{m}\}$, such that

• •

  for each $g\in G^{\prime}$, we have $u_{j}(g)=x_{j}$ for $j\in\{1,2\}$ and $u_{j}(g)=x_{j}/k$ for $j\in N\setminus\{1,2\}$;

• •

  $u_{1}(g_{m})=x_{1}-\epsilon$, and $u_{j}(g_{m})=0$ for $j\in N\setminus\{1\}$.

Clearly, this profile admits an allocation where every agent receives positive utility. Let $A$ be an EF1 allocation chosen by the welfarist rule with function $f_{n}$ on this profile. Regardless of whom $g_{m}$ is allocated to, each agent receives at most $k$ goods from $G^{\prime}$ in $A$—otherwise, if some agent $j$ receives more than $k$ goods from $G^{\prime}$, then some other agent receives fewer than $k$ goods from $G^{\prime}$ by the pigeonhole principle and therefore envies $j$ by more than one good, meaning that $A$ is not EF1. Since $|G^{\prime}|=kn$, every agent receives exactly $k$ goods from $G^{\prime}$. Furthermore, $g_{m}$ must be allocated to agent $1$; otherwise, the allocation where $g_{m}$ is allocated to agent $1$ (and all other goods are allocated as in $A$) has a higher welfare than $A$, contradicting the fact that $A$ is chosen by the welfarist rule with function $f_{n}$. The welfare of $A$ must not be smaller than that of another allocation where agent $1$ receives $g_{m}$ along with $k-1$ goods from $G^{\prime}$, agent $2$ receives $k+1$ goods from $G^{\prime}$, and every other agent receives $k$ goods from $G^{\prime}$ each. This means that

$\displaystyle f_{n}((k+1)x_{1}-\epsilon,kx_{2},x_{3}\ldots,x_{n})\geq f_{n}(kx_{1}-\epsilon,(k+1)x_{2},x_{3},\ldots,x_{n}),$

contradicting (3). This establishes (i).

It remains to prove (ii). Consider any $x_{1},\ldots,x_{n}>0$ and $y_{1},\ldots,y_{n}\geq 0$ satisfying $\prod_{i=1}^{n}y_{i}=0$. Let $X:=\prod_{i=1}^{n}x_{i}>0$. Without loss of generality, assume that $y_{1}=\cdots=y_{k}=0$ and $Y:=\prod_{i=k+1}^{n}y_{i}>0$ for some $k\in\{1,\ldots,n\}$ (if $k=n$, the empty product $\prod_{i=k+1}^{n}y_{i}$ is taken to be $1$). Define $z_{1},\ldots,z_{n}$ by $z_{i}:=(X/2Y)^{1/k}$ for all $i\in\{1,\ldots,k\}$ and $z_{i}:=y_{i}$ for all $i\in\{k+1,\ldots,n\}$. Then,

	$\displaystyle f_{n}(y_{1},\ldots,y_{n})$	$\displaystyle\leq f_{n}(z_{1},\ldots,z_{n})$		(since $f_{n}$ is non-decreasing)
		$\displaystyle=q(z_{1}\cdots z_{k}\cdot z_{k+1}\cdots z_{n})$		(by (i) and since all $z_{i}$’s are positive)
		$\displaystyle=q((X/2Y)\cdot y_{k+1}\cdots y_{n})$
		$\displaystyle=q(X/2)$
		$\displaystyle<q(X)$		(since $q$ is strictly increasing)
		$\displaystyle=q(x_{1}\cdots x_{n})$
		$\displaystyle=f_{n}(x_{1},\ldots,x_{n}),$		(by (i) and since all $x_{i}$’s are positive)

completing the proof of the theorem. ∎