On Maximum Weighted Nash Welfare for
Binary Valuations

Suppose, for a contradiction, that there exists a good $g\in A_{i}$ such that $v_{i}(g)=0$. Since any MWNW${}^{\text{tie}}$ allocation $\mathcal{A}$ is minimally complete, some agent $j\in N$ must have positive value for it: $v_{j}(g)=1$. If the weighted Nash welfare of $\mathcal{A}$ is greater than $0$, we can strictly improve the weighted Nash welfare by assigning $g$ to $j$ instead of $i$. On the other hand, if the weighted Nash welfare of $\mathcal{A}$ is 0, we can increase the number of agents receiving positive utility or increase the product of positive utilities by assigning $g$ to $j$. Both cases contradict the assumption that $\mathcal{A}$ is an MWNW${}^{\text{tie}}$ allocation. $\square$

Suppose, for a contradiction, that $\mathcal{A}_{S}$ is not an MWNW${}^{\text{tie}}$ allocation. This means that there exists another allocation $\mathcal{A}_{S}^{\prime}$ of the goods in $\mathcal{A}_{S}$ to the agents in $S$ such that

1. (i)

   strictly more agents receive positive utility, or

2. (ii)

   the same number of agents receive positive utility, but the weighted Nash welfare of these agents is strictly higher, or

3. (iii)

   the same number of agents receive positive utility, with the same weighted Nash welfare for these agents, but the weighted utility vector of $\mathcal{A}_{S}^{\prime}$ is lexicographically preferred to that of $\mathcal{A}_{S}$.

Case (i) means that the number of agents receiving positive utility in $\mathcal{A}$ is not maximized, a contradiction. In case (ii), if we retain the allocation for agents in $N\setminus S$ as in $\mathcal{A}$ while using the allocation $\mathcal{A}_{S}^{\prime}$ for agents in $S$, then in the new allocation, the same number of agents receive positive utility as in $\mathcal{A}$, but the weighted Nash welfare of these agents is strictly higher, a contradiction. Finally, in case (iii), this means that $\mathcal{A}$ is not lexicographically dominating, yielding yet another contradiction. $\square$

Let $\mathcal{I}$ and $\mathcal{I^{\prime}}$ be instances such that $\mathcal{I^{\prime}}$ can be obtained from $\mathcal{I}$ by adding one extra good $g^{*}$. Suppose that MWNW${}^{\text{tie}}$ returns $\mathcal{A}$ on $\mathcal{I}$ and $\mathcal{A^{\prime}}$ on $\mathcal{I^{\prime}}$.²²2Recall that for each instance, all MWNW${}^{\text{tie}}$ allocations induce the same (weighted) utility vector. By Lemma 1, in both $\mathcal{A}$ and $\mathcal{A^{\prime}}$, every agent values every good that she receives. Let $\mathcal{A^{\prime\prime}}$ be the allocation that is equivalent to $\mathcal{A^{\prime}}$ except that $g^{*}$ is excluded.

Suppose, for a contradiction, that $|A_{i}|>|A^{\prime}_{i}|$ for some agent $i\in N$. Construct the transformation graph $T=\mathcal{G}(\mathcal{A},\mathcal{A^{\prime\prime}})$. If $T$ contains at least one cycle, pick one of them arbitrarily and remove it—we remove the edges of the cycle from the graph without changing the allocations, so the resulting graph may no longer be the transformation graph of the same allocations. Repeat this process until $T$ becomes acyclic. Note that this procedure does not change the difference between the indegree and the outdegree of any node.

Since $|A_{i}|>|A_{i}^{\prime}|\geq|A_{i}^{\prime\prime}|$, there must be at least one outgoing edge from $i$. As the graph is finite and has no cycle, by starting from $i$ and following an outgoing edge, we must eventually reach a node $j$ with no outgoing edge. In particular, it holds that $|A_{j}|<|A^{\prime\prime}_{j}|$. From $\mathcal{A}$, we can transfer goods along the path from $i$ to $j$; denote the allocation after this sequence of transfers by $\widehat{\mathcal{A}}$. Since $\mathcal{A}$ is an MWNW${}^{\text{tie}}$ allocation, it is preferred to $\widehat{\mathcal{A}}$ by the MWNW${}^{\text{tie}}$ rule. Note that $|\widehat{A}_{i}|=|A_{i}|-1$, $|\widehat{A}_{j}|=|A_{j}|+1$, and $|\widehat{A}_{k}|=|A_{k}|$ for all $k\in N\setminus~{}\{i,j\}$. Consequently, the weighted utility vector $(|A_{i}|^{w_{i}},|A_{j}|^{w_{j}})$ is preferred to the weighted utility vector $((|A_{i}|-1)^{w_{i}},(|A_{j}|+1)^{w_{j}})$ by the MWNW${}^{\text{tie}}$ rule.³³3Even though we write agent $i$’s weighted utility before agent $j$’s in the weighted utility vectors, the actual order would be reversed if $j<i$.

Similarly, from $\mathcal{A^{\prime\prime}}$, we can transfer goods along the path from $j$ to $i$ in the “reverse” graph $\mathcal{G}(\mathcal{A^{\prime\prime}},\mathcal{A})$. Since the allocation $\mathcal{A^{\prime\prime}}$ is simply the allocation $\mathcal{A^{\prime}}$ without the good $g^{*}$, the same sequence of transfers is also feasible in $\mathcal{A^{\prime}}$. Let the allocation after this sequence of transfers be $\widehat{\mathcal{A}}^{\prime}$. Since $\mathcal{A^{\prime}}$ is an MWNW${}^{\text{tie}}$ allocation, it is preferred to $\widehat{\mathcal{A}}^{\prime}$ by the MWNW${}^{\text{tie}}$ rule. Note that $|\widehat{A}^{\prime}_{i}|=|A^{\prime}_{i}|+1$, $|\widehat{A}^{\prime}_{j}|=|A^{\prime}_{j}|-1$, and $|\widehat{A}^{\prime}_{k}|=|A^{\prime}_{k}|$ for all $k\in N\setminus\{i,j\}$. Hence, the weighted utility vector $(|A^{\prime}_{i}|^{w_{i}},|A^{\prime}_{j}|^{w_{j}})$ is preferred to the weighted utility vector $((|A^{\prime}_{i}|+1)^{w_{i}},(|A^{\prime}_{j}|-~{}1)^{w_{j}})$ by the MWNW${}^{\text{tie}}$ rule.

Now, recall that we have

Since bundle sizes are integers, we get

In particular, $|A_{i}|\geq 1$ and $|A^{\prime}_{j}|\geq|A^{\prime\prime}_{j}|\geq 1$. We consider the following two cases based on whether $A_{j}$ is empty.

Case 1: $|A_{j}|=0$.

If $|A_{i}|>1$, then the allocation $\widehat{\mathcal{A}}$, with weighted utility vector $((|A_{i}|-1)^{w_{i}},(|A_{j}|+1)^{w_{j}})$ for agents $i$ and $j$, has strictly more agents receiving positive utility, thereby contradicting the fact that $\mathcal{A}$ is an MWNW${}^{\text{tie}}$ allocation. Thus, $|A_{i}|=1$, which by (1) means that $|A_{i}^{\prime}|=0$. In particular, $g^{*}\not\in A_{i}^{\prime}$. Since $(|A_{i}|^{w_{i}},|A_{j}|^{w_{j}})$ is preferred to $((|A_{i}|-1)^{w_{i}},(|A_{j}|+1)^{w_{j}})$, it must be that $i<j$.

We know from (1) that $|A_{j}^{\prime}|\geq 1$. If $|A^{\prime}_{j}|>1$, then the allocation $\widehat{\mathcal{A}}^{\prime}$, with weighted utility vector $((|A^{\prime}_{i}|+1)^{w_{i}},(|A^{\prime}_{j}|-1)^{w_{j}})$ for agents $i$ and $j$, has strictly more agents receiving positive utility, thereby contradicting the fact that $\mathcal{A}^{\prime}$ is an MWNW${}^{\text{tie}}$ allocation. Thus, $|A^{\prime}_{j}|=1$. However, since the weighted utility vector $(|A^{\prime}_{i}|^{w_{i}},|A^{\prime}_{j}|^{w_{j}})$ is preferred to $((|A^{\prime}_{i}|+1)^{w_{i}},(|A^{\prime}_{j}|-~{}1)^{w_{j}})$, we must have $j<i$, a contradiction with the previous paragraph.

Case 2: $|A_{j}|>0$.

Then, by (1), we have $|A^{\prime}_{j}|\geq|A^{\prime\prime}_{j}|>1$. Since $(|A_{i}|^{w_{i}},|A_{j}|^{w_{j}})$ is preferred to $((|A_{i}|-1)^{w_{i}},(|A_{j}|+1)^{w_{j}})$, we have

$$\frac{(|A_{i}|-1)^{w_{i}}(|A_{j}|+1)^{w_{j}}}{|A_{i}|^{w_{i}}|A_{j}|^{w_{j}}}\leq 1,$$

(2)

where the denominator is nonzero as $|A_{i}|\geq 1$ and $|A_{j}|>0$. From (1), we have $|A_{i}|\geq|A_{i}^{\prime}|+1$ and $|A^{\prime}_{j}|-1\geq|A_{j}|$, which give us

$$-\frac{1}{|A^{\prime}_{i}|+1}\leq-\frac{1}{|A_{i}|}\quad\text{ and }\quad\frac{1}{|A^{\prime}_{j}|-1}\leq\frac{1}{|A_{j}|}.$$

(3)

All the denominators in the above inequalities are nonzero as $|A_{i}|\geq 1$, $|A_{j}|>0$, and $|A^{\prime}_{j}|>1$. Also, since $(|A^{\prime}_{i}|^{w_{i}},|A^{\prime}_{j}|^{w_{j}})$ is preferred to $((|A^{\prime}_{i}|+~{}1)^{w_{i}},(|A^{\prime}_{j}|-1)^{w_{j}})$, we get

$$\frac{|A^{\prime}_{i}|^{w_{i}}|A^{\prime}_{j}|^{w_{j}}}{(|A^{\prime}_{i}|+1)^{w_{i}}(|A^{\prime}_{j}|-1)^{w_{j}}}\geq 1,$$

(4)

where the denominator is nonzero as $|A^{\prime}_{j}|>1$. Now,

	$\displaystyle\frac{|A^{\prime}_{i}|^{w_{i}}|A^{\prime}_{j}|^{w_{j}}}{(|A^{\prime}_{i}|+1)^{w_{i}}(|A^{\prime}_{j}|-1)^{w_{j}}}$	$\displaystyle=\left(1-\frac{1}{|A^{\prime}_{i}|+1}\right)^{w_{i}}\left(1+\frac{1}{|A^{\prime}_{j}|-1}\right)^{w_{j}}$
		$\displaystyle\leq\left(1-\frac{1}{|A_{i}|}\right)^{w_{i}}\left(1+\frac{1}{|A_{j}|}\right)^{w_{j}}$
		$\displaystyle=\frac{(|A_{i}|-1)^{w_{i}}(|A_{j}|+1)^{w_{j}}}{|A_{i}|^{w_{i}}|A_{j}|^{w_{j}}}$		(5)
		$\displaystyle\leq 1,$

where the second line is derived using (3) and last line is as a result of (2). Since MWNW${}^{\text{tie}}$ chooses a lexicographically dominating allocation among all MWNW allocations, (2) can be an equality only if $i<j$, and (4) can be an equality only if $j<i$. Combining (2), (4), and (Case 2: $|A_{j}|>0$.) yields

$$1\leq\frac{|A^{\prime}_{i}|^{w_{i}}|A^{\prime}_{j}|^{w_{j}}}{(|A^{\prime}_{i}|+1)^{w_{i}}(|A^{\prime}_{j}|-1)^{w_{j}}}\leq\frac{(|A_{i}|-1)^{w_{i}}(|A_{j}|+1)^{w_{j}}}{|A_{i}|^{w_{i}}|A_{j}|^{w_{j}}}\leq 1,$$

where either the leftmost or the rightmost inequality has to be strict, thereby giving us a contradiction.

In both cases, we have arrived at a contradiction, completing the proof. $\square$

To prove that the allocation returned by Algorithm 1 is an MWNW${}^{\text{tie}}$ allocation, we show that after every iteration, the allocation returned by the subroutine AddOneGood is MWNW${}^{\text{tie}}$ with respect to the goods that are already allocated.

Let $t\in\{1,\dots,m\}$ be some iteration of the for loop of Algorithm 1, and let $g$ be the good added during this iteration. If $g$ is unvalued, clearly the allocation $\mathcal{A}^{t-1}$ with $g$ not assigned to any agent is MWNW${}^{\text{tie}}$ with respect to the first $t$ goods. Assume therefore that $g$ is valued. Hence, in the graph $\mathcal{H}$, there is an edge $d\rightarrow i$ for some $i\in N$. This means that at least one tuple is added to $\mathcal{P}$, and this iteration terminates with an allocation $\mathcal{A}^{t}$.

Let $\widehat{\mathcal{A}}^{t}$ be an MWNW${}^{\text{tie}}$ allocation of the $t$ goods. By Corollary 1, exactly one agent $z$ has $v_{z}(\widehat{A}^{t}_{z})=v_{z}(A_{z}^{t-1})+1$, while all other agents $y\neq z$ have $v_{y}(\widehat{A}^{t}_{y})=v_{y}(A_{y}^{t-1})$. Let $\widehat{\mathcal{A}}^{t-1}$ be the allocation obtained by adding a dummy agent $d$ and the good $g$ to $\mathcal{A}^{t-1}$, so that $\widehat{A}_{d}^{t-1}=\{g\}$. Consider the transformation graph $\mathcal{G}(\widehat{\mathcal{A}}^{t-1},\widehat{\mathcal{A}}^{t})$, where we assume that $\widehat{A}_{d}^{t}=\emptyset$. As in the proof of Theorem 3.1, we can eliminate all cycles from this graph. Node $d$ has one outgoing edge and no incoming edge, while every other node except $z$ has the same number of outgoing and incoming edges (in particular, if such a node has an incoming edge, it must also have an outgoing edge). Since the graph is finite and has no cycle, by starting from $d$ and iteratively following an outgoing edge, we must eventually reach $z$. In other words, there is a path from $d$ to $z$ in $\mathcal{G}(\widehat{\mathcal{A}}^{t-1},\widehat{\mathcal{A}}^{t})$. Let this path be $d\rightarrow b_{1}\rightarrow b_{2}\rightarrow\dots\rightarrow z$.

By construction of the path, agent $b_{1}$ values some good in agent $d$’s bundle, agent $b_{2}$ values some good in agent $b_{1}$’s bundle, and so on. This means that the path $d\rightarrow b_{1}\rightarrow b_{2}\rightarrow\dots\rightarrow z$ also exists in the graph $\mathcal{H}$ in Algorithm 2. Hence, a tuple $(z,P_{d,z},\mathbf{u}_{d,z})$ is added to $\mathcal{P}$, where $P_{d,z}$ is a path from $d$ to $z$ (which may be different from the aforementioned path). Since the weighted utility vector $\mathbf{u}_{d,z}$ is the same as the weighted utility vector of $\widehat{\mathcal{A}}^{t}$, and by the selection method in line 12 of Algorithm 2, the allocation $\mathcal{A}^{t}$ returned by AddOneGood is also an MWNW${}^{\text{tie}}$ allocation. This completes the proof of correctness.

Finally, we analyze the time complexity of Algorithm 1. In the main algorithm, there are $\mathcal{O}(m)$ iterations of the for loop. In the AddOneGood subroutine, checking whether $g$ is unvalued takes $\mathcal{O}(n)$ time, constructing the graph $\mathcal{H}$ takes $\mathcal{O}(mn)$ time, and there are $\mathcal{O}(n)$ iterations of the for loop. Within each iteration, finding if a path exists can be done using breadth-first search or depth-first search, which takes $\mathcal{O}(n^{2})$ time [16]. In the last step, selecting the tuple in $\mathcal{P}$ takes $\mathcal{O}(n)$ time and allocating along the path also takes $\mathcal{O}(n)$ time. Putting everything together, Algorithm 1 terminates in $\mathcal{O}(mn(m+n^{2}))$ time. $\square$

Consider an MWNW${}^{\text{tie}}$ allocation $\mathcal{A}$ for $n+1$ agents. Let $S$ be any subset of $n$ agents, and let $i$ be the agent not in $S$. By Lemma 2, $\mathcal{A}_{S}$ is an MWNW${}^{\text{tie}}$ allocation for the agents in $S$. Then, with the bundle of goods remaining to be allocated being that of agent $i$, iteratively make use of the subroutine AddOneGood to allocate all of these goods, giving us an MWNW${}^{\text{tie}}$ allocation of the original set of goods. Since AddOneGood never decreases the size of any agent’s bundle, which is equal to the agent’s utility by Lemma 1, population-monotonicity is satisfied. $\square$

Let $\mathcal{A}^{\texttt{truth}}$ be an MWNW${}^{\text{tie}}$ allocation under a truthful valuation profile $\mathbf{v}$, with the unallocated (and truthfully unvalued) goods put into $A^{\texttt{truth}}_{\text{unvalued}}$.

Similarly, let $\mathcal{A}^{\texttt{lie}}$ be an MWNW${}^{\text{tie}}$ allocation under the same truthful valuations for all agents except possibly those in $S\subseteq N$—call this valuation profile $\mathbf{v}^{\prime}$—with the unallocated goods put into $A^{\texttt{lie}}_{\text{unvalued}}$. Note that $A^{\texttt{lie}}_{\text{unvalued}}$ contains goods that agents in $N\setminus S$ truthfully do not value, and that agents in $S$ declare they do not value (even though some of them may actually value some goods here).

Suppose, for a contradiction, that there exist such valuation profiles $\mathbf{v}$ and $\mathbf{v^{\prime}}$ and a set of agents $S\subseteq N$ such that

1. (i)

   $v_{i}(A_{i}^{\texttt{lie}})>v_{i}(A_{i}^{\texttt{truth}})\text{ for all }i\in S$,

2. (ii)

   $v_{j}=v^{\prime}_{j}$ for all $j\in N\setminus S$.

Under truthful valuations, Lemma 1 tells us that every agent values every good in his own bundle. However, because agents in $S$ may not be truthful, they may receive goods they do not actually value. For every $i\in S$, we can write

where $A_{i}^{\texttt{lie,valued}}$ consists of the goods in $A_{i}^{\texttt{lie}}$ that $i$ values, and $A_{i}^{\texttt{lie,unvalued}}$ consists of the goods in $A_{i}^{\texttt{lie}}$ that $i$ does not value (but declares as valued in $\mathbf{v}^{\prime}$). So we have that

Combining this with condition (i), we get that, for all $i\in S$,

where the last equality follows from Lemma 1. Let $\mathcal{A}^{\texttt{*lie}}$ be the allocation that results from excluding the set of goods $\bigcup_{i\in S}A_{i}^{\texttt{lie,unvalued}}$ from $\mathcal{A}^{\texttt{lie}}$. Also, let $A_{\text{unvalued}}^{\texttt{*lie}}=A_{\text{unvalued}}^{\texttt{lie}}$.

Construct the graph $T=\mathcal{G}(\mathcal{A}^{\texttt{truth}}\cup\{A_{\text{unvalued}}^{\texttt{truth}}\},\mathcal{A}^{\texttt{*lie}}\cup\{A_{\text{unvalued}}^{\texttt{*lie}}\})$, where we use the notation $\mathcal{A}^{\texttt{truth}}\cup\{A_{\text{unvalued}}^{\texttt{truth}}\}$ to mean the allocation $\mathcal{A}^{\texttt{truth}}$ with the bundle $A_{\text{unvalued}}^{\texttt{truth}}$ added to it, and similarly for $\mathcal{A}^{\texttt{*lie}}\cup\{A_{\text{unvalued}}^{\texttt{*lie}}\}$. Note that there are $n+1$ nodes in $T$: each of the first $n$ nodes represents an agent in $N$, while the last node represents the dummy agent unvalued. We make the following claim:

Claim

There are no edges emerging from the dummy agent unvalued.

To see why the Claim holds, recall that none of the $n$ agents truthfully values any good in $A_{\text{unvalued}}^{\texttt{truth}}$. This means that any edge emerging from the node unvalued can only be as a result of some agent $i\in S$ misreporting that he values it (when in fact he does not). However, such a good would go into $A_{i}^{\texttt{lie,unvalued}}$, which is explicitly excluded in our transformation graph $T$.

The rest of the proof proceeds using similar ideas as the proof of Theorem 3.1. First, we can eliminate all cycles from $T$. Let $\ell\in S$. Since $|A_{\ell}^{\texttt{lie,valued}}|>|A_{\ell}^{\texttt{truth}}|$ by (6), there must be an incoming edge to node $\ell$, and this edge cannot come from the node unvalued by our Claim. Since the graph is finite and all cycles have been eliminated, by starting from $\ell$ and iteratively following an incoming edge, we must eventually reach a node $j$ with no incoming edge. In particular, it holds that $|A_{j}^{\texttt{*lie}}|<|A_{j}^{\texttt{truth}}|$. By condition (i), we have $j\not\in S$, and by the Claim, no node on the path from $j$ to $\ell$ is the node unvalued.

Traverse the path from $j$ to $\ell$, and let $i$ be the first agent belonging to $S$. Then, on the path from $j$ to $i$, all agents (except $i$) belong to $N\setminus S$. From $\mathcal{A}^{\texttt{truth}}$, we can transfer goods along the path from $j$ to $i$; let the allocation after this sequence of transfers be $\widehat{\mathcal{A}}^{\texttt{truth}}$. Since $\mathcal{A}^{\texttt{truth}}$ is an MWNW${}^{\text{tie}}$ allocation, it is preferred to $\widehat{\mathcal{A}}^{\texttt{truth}}$ by the MWNW${}^{\text{tie}}$ rule. Note that $|\widehat{A}^{\texttt{truth}}_{i}|=|A^{\texttt{truth}}_{i}|+1$, $|\widehat{A}^{\texttt{truth}}_{j}|=|A^{\texttt{truth}}_{j}|-1$, and $|\widehat{A}^{\texttt{truth}}_{k}|=|A^{\texttt{truth}}_{k}|$ for all $k\in N\setminus\{i,j\}$, and observe that every transferred good in $T$ is transferred from an agent who truthfully values it to another agent who truthfully values it. Consequently, the weighted utility vector $(|A_{i}^{\texttt{truth}}|^{w_{i}},|A_{j}^{\texttt{truth}}|^{w_{j}})$ is preferred to the weighted utility vector $((|A_{i}^{\texttt{truth}}|+1)^{w_{i}},(|A_{j}^{\texttt{truth}}|-1)^{w_{j}})$ by the MWNW${}^{\text{tie}}$ rule.⁴⁴4Even though we write agent $i$’s weighted utility before agent $j$’s in the weighted utility vectors, the actual order would be reversed if $j<i$.

Similarly, from $\mathcal{A}^{\texttt{*lie}}$, we can transfer a good along the reverse path from $i$ to $j$. Observe that in this transfer, every agent values (under $\mathbf{v^{\prime}}$) the good that he receives, because for every agent $h$ receiving a good along this path, $h\in N\setminus S$, which implies $v_{h}=v^{\prime}_{h}$ by condition (ii). As a result, this path from $i$ to $j$ also exists when going from $\mathcal{A}^{\texttt{lie}}$ to $\mathcal{A}^{\texttt{truth}}$. Let the allocation after such a transfer be $\widehat{\mathcal{A}}^{\texttt{lie}}$. Since $\mathcal{A}^{\texttt{lie}}$ is an MWNW${}^{\text{tie}}$ allocation, it is preferred to $\widehat{\mathcal{A}}^{\texttt{lie}}$ by the MWNW${}^{\text{tie}}$ rule according to the valuation profile $\mathbf{v^{\prime}}$. Note that $|\widehat{A}^{\texttt{lie}}_{i}|=|A^{\texttt{lie}}_{i}|-~{}1$, $|\widehat{A}^{\texttt{lie}}_{j}|=|A^{\texttt{lie}}_{j}|+1$, and $|\widehat{A}^{\texttt{lie}}_{k}|=|A^{\texttt{lie}}_{k}|$ for all $k\in N\setminus\{i,j\}$. Hence, the weighted utility vector $(|A_{i}^{\texttt{lie}}|^{w_{i}},|A_{j}^{\texttt{lie}}|^{w_{j}})$ is preferred to the weighted utility vector $((|A_{i}^{\texttt{lie}}|-1)^{w_{i}},(|A_{j}^{\texttt{lie}}|+1)^{w_{j}})$ by the MWNW${}^{\text{tie}}$ rule.

Now, recall that we have

where the last equality holds since $j\not\in S$. Since bundle sizes are integers, we get

In particular, $|A_{i}^{\texttt{lie}}|\geq|A_{i}^{\texttt{*lie}}|\geq 1$ and $|A_{j}^{\texttt{truth}}|\geq 1$. We consider the following two cases based on the size of $|A_{j}^{\texttt{truth}}|$.

Case 1: $|A_{j}^{\texttt{truth}}|=1$.

Then $|A_{j}^{\texttt{lie}}|=0$. If $|A_{i}^{\texttt{lie}}|>1$, then the allocation $\widehat{\mathcal{A}}^{\texttt{lie}}$, with weighted utility vector $((|A_{i}^{\texttt{lie}}|-1)^{w_{i}},(|A_{j}^{\texttt{lie}}|+1)^{w_{j}})$ for agents $i$ and $j$, has strictly more agents receiving positive utility, thereby contradicting the fact that $\mathcal{A}^{\texttt{lie}}$ is an MWNW${}^{\text{tie}}$ allocation. Thus, $|A_{i}^{\texttt{lie}}|=1$, which by (7) means that $|A_{i}^{\texttt{truth}}|=0$. Since $(|A_{i}^{\texttt{lie}}|^{w_{i}},|A_{j}^{\texttt{lie}}|^{w_{j}})$ is preferred to $((|A_{i}^{\texttt{lie}}|-~{}1)^{w_{i}},(|A_{j}^{\texttt{lie}}|+1)^{w_{j}})$, it must be that $i<j$. However, since the weighted utility vector $(|A_{i}^{\texttt{truth}}|^{w_{i}},|A_{j}^{\texttt{truth}}|^{w_{j}})$ is preferred to $((|A_{i}^{\texttt{truth}}|+1)^{w_{i}},(|A_{j}^{\texttt{truth}}|-1)^{w_{j}})$, we must have $j<i$, a contradiction.

Case 2: $|A_{j}^{\texttt{truth}}|>1$.

If $|A_{i}^{\texttt{truth}}|=0$, then the allocation $\mathcal{A}^{\texttt{truth}}$, with weighted utility vector $((|A_{i}^{\texttt{truth}}|+1)^{w_{i}},(|A_{j}^{\texttt{truth}}|-1)^{w_{j}})$ for agents $i$ and $j$, has strictly more agents receiving positive utility, thereby contradicting the fact that $\mathcal{A}^{\texttt{truth}}$ is an MWNW${}^{\text{tie}}$ allocation. Thus, $|A_{i}^{\texttt{truth}}|>~{}0$, which by (7) means that $|A_{i}^{\texttt{lie}}|>1$. If $|A_{j}^{\texttt{lie}}|=0$, then we arrive at the same contradiction as we did at the beginning of Case 1. Thus, $|A_{j}^{\texttt{lie}}|>0$, which by (7) means that $|A_{j}^{\texttt{truth}}|>1$. Since $(|A_{i}^{\texttt{truth}}|^{w_{i}},|A_{j}^{\texttt{truth}}|^{w_{j}})$ is preferred to $((|A_{i}^{\texttt{truth}}|+1)^{w_{i}},(|A_{j}^{\texttt{truth}}|-1)^{w_{j}})$, we have

$$\frac{|A_{i}^{\texttt{truth}}|^{w_{i}}|A_{j}^{\texttt{truth}}|^{w_{j}}}{(|A_{i}^{\texttt{truth}}|+1)^{w_{i}}(|A_{j}^{\texttt{truth}}|-1)^{w_{j}}}\geq 1,$$

(8)

where the denominator is nonzero as $|A_{j}^{\texttt{truth}}|>1$. From (7), we have $|A_{i}^{\texttt{lie}}|\geq|A_{i}^{\texttt{truth}}|+1$ and $|A_{j}^{\texttt{truth}}|-1\geq|A_{j}^{\texttt{lie}}|$, which give us

$$-\frac{1}{|A_{i}^{\texttt{lie}}|}\geq-\frac{1}{|A_{i}^{\texttt{truth}}|+1}\quad\text{ and }\quad\frac{1}{|A_{j}^{\texttt{lie}}|}\geq\frac{1}{|A_{j}^{\texttt{truth}}|-1}.$$

(9)

All the denominators in the above inequalities are nonzero as $|A_{i}^{\texttt{lie}}|>1$, $|A_{j}^{\texttt{lie}}|>0$, and $|A_{j}^{\texttt{truth}}|>1$. Also, since $(|A_{i}^{\texttt{lie}}|^{w_{i}},|A_{j}^{\texttt{lie}}|^{w_{j}})$ is preferred to $((|A_{i}^{\texttt{lie}}|-1)^{w_{i}},(|A_{j}^{\texttt{lie}}|+1)^{w_{j}})$, we get

$$\frac{(|A_{i}^{\texttt{lie}}|-1)^{w_{i}}(|A_{j}^{\texttt{lie}}|+1)^{w_{j}}}{|A_{i}^{\texttt{lie}}|^{w_{i}}|A_{j}^{\texttt{lie}}|^{w_{j}}}\leq 1,$$

(10)

where the denominator is nonzero as $|A_{i}^{\texttt{lie}}|>1$ and $|A_{j}^{\texttt{lie}}|>0$. Now,

	$\displaystyle\frac{(|A_{i}^{\texttt{lie}}|-1)^{w_{i}}(|A_{j}^{\texttt{lie}}|+1)^{w_{j}}}{|A_{i}^{\texttt{lie}}|^{w_{i}}|A_{j}^{\texttt{lie}}|^{w_{j}}}$	$\displaystyle=\left(1-\frac{1}{|A_{i}^{\texttt{lie}}|}\right)^{w_{i}}\left(1+\frac{1}{|A_{j}^{\texttt{lie}}|}\right)^{w_{j}}$
		$\displaystyle\geq\left(1-\frac{1}{|A_{i}^{\texttt{truth}}|+1}\right)^{w_{i}}\left(1+\frac{1}{|A_{j}^{\texttt{truth}}|-1}\right)^{w_{j}}$
		$\displaystyle=\frac{|A_{i}^{\texttt{truth}}|^{w_{i}}|A_{j}^{\texttt{truth}}|^{w_{j}}}{(|A_{i}^{\texttt{truth}}|+1)^{w_{i}}(|A_{j}^{\texttt{truth}}|-1)^{w_{j}}}$		(11)
		$\displaystyle\geq 1,$

where the second line follows from (9) and the last line is as a result of (8). Since MWNW${}^{\text{tie}}$ chooses a lexicographically dominating allocation among all MWNW allocations, (8) can be an equality only if $j<i$, and (10) can be an equality only if $i<j$. Combining (8), (10), and (Case 2: $|A_{j}^{\texttt{truth}}|>1$.) yields

$\displaystyle 1$

$\displaystyle\geq\frac{(|A_{i}^{\texttt{lie}}|-1)^{w_{i}}(|A_{j}^{\texttt{lie}}|+1)^{w_{j}}}{|A_{i}^{\texttt{lie}}|^{w_{i}}|A_{j}^{\texttt{lie}}|^{w_{j}}}\geq\frac{|A_{i}^{\texttt{truth}}|^{w_{i}}|A_{j}^{\texttt{truth}}|^{w_{j}}}{(|A_{i}^{\texttt{truth}}|+1)^{w_{i}}(|A_{j}^{\texttt{truth}}|-1)^{w_{j}}}\geq 1,$

where either the leftmost or the rightmost inequality has to be strict, thereby giving us a contradiction.