The Fairness of Leximin in Allocation of Indivisible Chores

PO comes directly from the property of the leximin solution. If we can find an allocation $B$ which is a Pareto-improvement of $A$, then $v_{i}(B_{i})\geq v_{i}(A_{i})$ for all $i\in\mathcal{N}$ and $v_{j}(B_{j})>v_{j}(A_{j})$ for some $j\in\mathcal{N}$ and so $A\prec B$. Thus $A$ cannot be the leximin allocation.

Suppose $A$ is not PROP1. According to our definition of PROP1, there must exist an agent $i$ such that

Since the leximin allocation $A$ is PO, there must exist an agent $j$ who does not envy anyone. To see this, we can look at the envy graph generated by allocation $A$. The envy graph contains a directed edge $e=(u,v)$ if agent $u$ envies agent $v$. Suppose for contradiction that every agent $j$ envies some other agent. Then starting at an arbitrary agent $s$, since every agent envies someone else, we can repeatedly follow an arbitrary outgoing edge from the current agent until we find an envy cycle. For agents in the envy cycle, we can reassign to each agent the bundle she envies. This reassignment will increase the utilities of all agents in the cycle without affecting other agents, which contradicts with PO.

Now consider this agent $j$ who doesn’t envy any other agent. Since agent $j$ doesn’t envy any other agent, we must have,

Let $A_{i}^{-}=\{c|c\in A_{i},v_{i}(c)<0\}$ and $|A_{i}^{-}|=a$. Clearly by Equation 1, $a\geq 2$. Note also $v_{i}(A_{i}^{-})=v_{i}(A_{i})$.

Consider the chore $c_{1}$ in $A_{i}^{-}$ that agent $j$ dislikes the least, i.e. $c_{1}={\arg\max}_{c\in A_{i}^{-}}v_{j}(c)$. Suppose for contradiction that $v_{j}(A_{j})+v_{j}(c_{1})>v_{i}(A_{i})$, we can construct $A^{\prime}$ by giving $(A_{i}\setminus\{c_{1}\})$ to agent $i$ and $(A_{j}\cup\{c_{1}\})$ to agent $j$. Since

we have $A\prec A^{\prime}$. This contradicts with the fact that $A$ is the leximin allocation with respect to $\boldsymbol{f}$. So it must be the case that

Consider the chore $c_{2}$ in agent $i$’s bundle that agent $i$ dislikes the most, i.e. $c_{2}=\arg\min_{c\in A_{i}}v_{i}(c)$. According to the definition of PROP1, for all $c$ in agent $i$’s bundle, we know $v_{i}(A_{i})-v_{i}(c)<\frac{U}{n}$. In particular, we have $v_{i}(A_{i})-v_{i}(c_{2})<\frac{U}{n}$. Suppose $v_{i}(A_{i})=(1+\epsilon_{1})\frac{U}{n}+v_{i}(c_{2})$ where $\epsilon_{1}>0$. Since $c_{2}$ is the most disliked item in agent $i$’s bundle, we have,

After some simplification, we have,

Therefore,

Suppose $v_{i}(A_{i})=\left(1+\frac{1}{a-1}+\frac{a\epsilon_{2}}{a-1}\right)\frac{U}{n}$ where $\epsilon_{2}\geq\epsilon_{1}>0$. According to Equation 2, we can suppose $v_{j}(A_{j})=(1-\epsilon_{3})\frac{U}{n}$ where $0\leq\epsilon_{3}\leq 1$. Then from Equation 3 and Equation 4, we have,

Summing agent $j$’s valuation of agent $i$’s bundle and her own bundle, we have,

Therefore, there must exists an agent $k\neq i,j$ such that,

Since agent $j$ doesn’t envy any other agent, her valuation of any other agent’s bundle cannot be larger than her valuation of her own bundle. However,

Therefore,

So $v_{j}(A_{k})>v_{j}(A_{j})$ when $n=3\text{ or }4$, which contradicts the assumption that agent $j$ does not envy anyone. So when $n=3\text{ or }4$, there can’t exist an agent $i$ such that

In conclusion, when there are 3 or 4 agents, the allocation found by the leximin solution with respect to $\boldsymbol{f}$ is PROP1 and PO. ∎

Let $A$ be an allocation that is not EFX. We will show that $A$ cannot be the leximin allocation with respect to $\boldsymbol{f}$.

Since $A$ is not EFX, there exists a pair of agents $i,j$ such that either

or

Case 1: There exist agents $i,j$ and a good $g\in A_{j}\cap G$ such that $v(A_{i})<v(A_{j}\backslash\{g\})$.

Let $i$ be any agent with utility $\min_{k}v(A_{k})$, the above condition must be true, so we assume without loss of generality that $i=\arg\min_{k}v(A_{k})$. If there are multiple agents with minimum utility in $A$, let $i$ be the one considered last in the ordering $X^{A}$. Recall that according to Algorithm 1, $X^{A}$ is obtained by ordering agents by increasing objective tuple $f(A_{i})$ and then by some arbitrary but consistent tiebreak method.

Define a new allocation $B$ where $B_{i}=A_{i}\cup\{g\}$, $B_{j}=A_{j}\backslash\{g\}$, and $B_{k}=A_{k}$ for all $k\notin\{i,j\}$. Let $S$ be the set of agents appearing before $i$ in $X^{A}$. The only bundles that differ between allocations $A$ and $B$ are those of $i$ and $j$, so we have $A_{k}=B_{k}$ for all $k\in S$. Thus for all $k\in S$, $v(B_{k})=v(A_{k})=v(A_{i})$. Since $v(B_{j})=v(A_{j}\backslash\{g\})>v(A_{i})$, $j$ must occur after every agent in $S$ in $X^{B}$.

Since $g\in G$, $v(B_{i})=v(A_{i}\cup\{g\})\geq v(A_{i})$. If $v(B_{i})>v(A_{i})$, $i$ must occur after every agent in $S$, since $v(B_{i})>v(A_{i})=v(B_{k})$. If $v(B_{i})=v(A_{i})$, $i$ must still occur after every agent in $S$, since we sort by increasing number of goods if both agents have the same utility.

The utility of every agent besides $i$ and $j$ are the same in $A$ and $B$. We also proved that $i$ and $j$ will still be after $S$ in $X^{B}$. This means that the first $|S|$ agents in both $X^{A}$ and $X^{B}$ are the same, so the leximin comparison won’t terminate before position $|S|+1$ in the orderings.

Let $T$ be the set of agents appearing after $i$ in $X^{A}$. Since $i$ is the last agent with minimum utility, we know

Now consider the $(|S|+1)$th agent. We know $X^{A}_{|S|+1}=i$. If $X^{B}_{|S|+1}=i$, we know $|A_{i}\cap G|<|B_{i}\cap G|$, so $A\prec B$. If $X^{B}_{|S|+1}=k$ for some $k\neq i$, we know $v(A_{i})<v(B_{k})$, so $A\prec B$ as well.
 
Case 2: There exist agents $i,j$ and a chore $c\in A_{i}\cap C$ such that $v(A_{i})<v(A_{j}\cup\{c\})$.

Define a new allocation $B$ where $B_{i}=A_{i}\backslash\{c\}$, $B_{j}=A_{j}\cup\{c\}$, and $B_{k}=A_{k}$ for all $k\notin\{i,j\}$. Let $S$ be the set of agents appearing before $i$ in $X^{A}$, $T$ be the set of agents with the same utility, number of goods and number of chores as $i$ in $A$ and $U=S\cup T\setminus\{i\}$. The only bundles that differ between allocations $A$ and $B$ are those of $i$ and $j$, so we have $A_{k}=B_{k}$ for all $k\in U$. Thus for all $k\in U$, $v(B_{k})=v(A_{k})\leq v(A_{i})$. Since $v(B_{j})=v(A_{j}\cup\{c\})>v(A_{i})$, $j$ must occur after every agent in $U$ in $X^{B}$.

Since $c\in C$, $v(B_{i})=v(A_{i}\backslash\{c\})\geq v(A_{i})$. If $v(B_{i})>v(A_{i})$, $i$ must occur after every agent in $U$, since $v(B_{i})>v(A_{i})\geq v(B_{k})$ for all $k\in U$. If $v(B_{i})=v(A_{i})$, $i$ must still occur after every agent in $U$, since we sort by decreasing number of chores if two bundles have the same utility and the same number of goods.

The utility of every agent besides $i$ and $j$ are the same in $A$ and $B$. We also proved that $i$ and $j$ will both be after $U$ in $X^{B}$. This means that the first $|U|$ agents in $X^{A}$ and $X^{B}$ have the same utility, number of goods and number of chores pairwise. The leximin comparison won’t terminate before position $|U|+1$ in the orderings.

Now consider the $(|U|+1)$th agent. Suppose $X^{A}_{|U|+1}=l$. We know $l$ is the last agent with the same utility, number of goods and number of chores as $i$ in $X^{A}$. If $X^{B}_{|U|+1}=i$, we know $v(A_{l})\leq v(B_{i})$, $|A_{l}\cap G|=|B_{i}\cap G|$ and $|A_{l}\cap C|>|B_{i}\cap C|$, so $A\prec B$. If $X^{B}_{|U|+1}=k$ for some $k\neq i$, there are three possibilities since $k$ appears after $l$ in $X^{A}$,

1. 1.

   $v(A_{l})<v(B_{k})$

2. 2.

   $v(A_{l})=v(B_{k})$ and $|A_{l}\cap G|<|B_{k}\cap G|$

3. 3.

   $v(A_{i})=v(B_{k})$ and $|A_{l}\cap G|=|B_{k}\cap G|$ and $|A_{l}\cap C|>|B_{k}\cap C|$.

In all three possibilities, we have $A\prec B$.

Since $A\prec B$ in both cases, $A$ cannot be the leximin allocation with respect to f. Therefore, the leximin allocation with respect to f must be EFX. ∎