Average Envy-freeness for Indivisible Items

An instance of fair division problem $\mathcal{I}=\langle N,M,V\rangle$ is defined by a set of $n$ agents $N=[n]$, a set of $m$ items $M$, and a valuation profile $V=\{v_{1},v_{2},\cdots,v_{n}\}$. We use $i$ to denote a generic agent in $N$ and $g$ to denote a generic item in $M$.

Valuation functions represent the preferences of agents among the items. For each agent $i$, $v_{i}$ a mapping to a subset of $M$ to a non-negative value $v_{i}:2^{M}\to\mathbb{R}_{\geq 0}$. We follow the convention to assume additive valuation, i.e for any $i\in N$ and $M^{\prime}\subseteq M$, $v_{i}(M^{\prime})=\sum_{g\in M^{\prime}}v_{i}(g)$. We say that an instance has binary valuation if for any $i\in N$ and $g\in M$, $v_{i}(g)\in\{0,1\}$, and an instance has identical valuation if $v_{1}=v_{2}=\cdots=v_{n}$. We also define the average value of a subset of item $M^{\prime}$ as $u_{i}(M^{\prime})=\frac{v_{i}(M^{\prime})}{|M^{\prime}|}$, i.e. the average value of the items in the subset. Specifically, $u_{i}(\emptyset)=0$.

An allocation $A=(A_{1},A_{2},\cdots,A_{n})$ is a $n$-partition of the set of items $M$, where $A_{i}\subseteq M$ is the bundle allocated to agent $i$. We sometimes abuse the notation and use $A$ to denote a partial allocation, where there are items unallocated to any agent.

A quota $Q$ is a constraint on allocations. For each agent $i$, $Q$ imposes an upper bound and a lower bound for the size of the bundle $A_{i}$. An allocation $A$ satisfies a quota $Q$ if all agents satisfy the constraint. A quota is said to be exact if the upper bound equals to the lower bound for every agent. An exact quota regulates the exact number of items in each bundle.

By the definition of AEF-1, agents can remove an item from either bundle under comparison. This is because agents can increase the average value of their own bundle by removing the least preferred item (if it’s not the only item). It follows from the definition that an AEF allocation is always AEF-1.

We introduce the computational problems related to AEF and AEF-1.

If $i\leq m$, then $i$ does not envy any $h>i$ because $h$ gets either no item or an item inferior to $i$’s item under $i$’s valuation. If $h<i$, then $i$ and does not envy $h$ by removing $h$’s only item. If $i>m$, then $i$ does not envy any other $h$ after removing $h$’s item (if exists).

If $h\neq n$, $i$ does not envy $h$ after removing $h$’s only item. If $h=n$, note that $i$ picks their favorite item among all the rest of the items, including all $h$’s items. Therefore, for any $g\in A_{h}$, $v_{i}(A_{i})\geq v_{i}(g)$. Therefore, $u_{i}(A_{i})\geq u_{i}(A_{h})$, and $i$ does not envy $h$. ∎

A state in Algorithm 1 is a triplet $(W,H,k)$. Suppose $A$ is a partial allocation of $M=\{g_{1},g_{2},\cdots,g_{m}\}$ where $g_{1},g_{2},\cdots,g_{k}$ has been allocated. $W$ is a $n$-vector that records the number of items each agent is allocated, i.e. $W_{i}=|A_{i}|$ for each $i$. $H$ is a $n\times n$-matrix that records the additive value of each agent toward each bundle, i.e. $H(i,h)=v_{i}(A_{h})$. $W$ and $H$ together record each agent’s average value on each bundle. For any pair of agents $i,h$, $u_{i}(A_{h})=\frac{H(i,h)}{W_{h}}$. $k=0,1,2\cdots,m$ indicates that item $g_{1},g_{2},\cdots,g_{k}$ has been allocated while other items are not. $k=0$ means no item has been allocated yet. For each state, we maintain two values. $Vld(W,H,k)\in\{0,1\}$ indicates whether this state is reached, which stands for there exists a partial allocation of whom the state is $(W,H,k)$. $Prev(W,H,k)\in N$ records the agent that item $g_{k}$ is allocated to reach the current state. For any allocation, it is sufficient to judge whether it is AEF-1 and satisfies $Q$ from its corresponding state.

For a given state $(W,H,k)$ with $k<m$ and $Vld(W,H,k)=1$, we enumerate the agent to whom item $g_{k+1}$ is allocated. For each agent $i$, we find the updated state $(W^{\prime},H^{\prime},k+1)$ after $g_{k+1}$ is allocated to $i$ and set $Vld(W^{\prime},H^{\prime},k+1)=1$ and $Prev(W^{\prime},H^{\prime},k+1)=i$. The algorithm start from $(\mathbf{0}^{n},\mathbf{0^{n\times n}},0)$ and iterated for $k=0,1,\cdots,m-1$. The search space of $W$ is $\mathcal{W}=\{0,1,\cdots,m\}^{n}$, and the search space $H$ is $\mathcal{H}=\{0,1,\cdots,m\}^{n\times n}$. Finally, the algorithm finds if there is a state $Vld(W,H,m)=1$ that is AEF-1 and satisfies $Q$. If so, the algorithm outputs YES and constructs the allocation backward with $Prev$. Otherwise, the algorithm outputs NO.

The technique of enumerating all possible values in Algorithm 1 can be extended to valuations where a bundle has at most $Poly(m)$ different values. However, for general valuation, a bundle can have exponentially many values. In fact, we show that AEF-1-Existence with a quota with fixed $n\geq 3$ is NP-complete.

Given the rounding parameter $r\in\mathbb{N}^{+}$ and an upper bound $a>0$, we divide $[0,a]$ into $r+1$ intervals $\{0\},(0,\frac{a}{r}],(\frac{a}{r},\frac{2a}{r}],\cdots,$ $(\frac{(r-1)a}{r},a]$. For $k=1,2,\cdots r$, a positive value $\frac{(k-1)a}{r}<x\leq\frac{ka}{r}$ is rounded to $\frac{ka}{r}$. $0$ is rounded to $0$.

If we apply the same rounding scheme to each $v_{i}(g)$ and directly apply Algorithm 1, we will be able to find an $\frac{2a}{r}\text{-error }\text{\rm AEF-1}$ allocation, because an AEF-1 allocation in the original valuations implies an $\frac{a}{r}\text{-error }\text{\rm AEF-1}$ allocation in the rounded valuations, and an $\frac{a}{r}\text{-error }\text{\rm AEF-1}$ allocation in the rounded valuations in turn implies an $\frac{2a}{r}\text{-error }\text{\rm AEF-1}$ allocation in the original valuations. However, there is no guarantee on $\alpha\text{-}\text{\rm AEF-1}$, because the value of an item can be rounded from arbitrarily small to $\frac{a}{r}$. Example 2 shows a case where an AEF-1 allocation in the rounded valuation turns out to be a poor approximation in the original valuation.

Therefore, we need a more refined rounding and searching scheme that can distinguish between $A$ and $A^{\prime}$ to ensure a closer approximation ratio between the original and the rounded valuation. The rounding of each agent should be proportional to their valuations so that the rounding error is not too large compared with the value of their own bundles. Bu et al. (2022) proposes a bi-criteria approximation algorithm to maximize EF-1 ratio and social welfare simultaneously. We follow their techniques to enumerate all items being removed in the envy comparisons, i.e. the “1” in “AEF-1”.

A removing matrix $R$ is a matrix recording the items to remove when agents compare bundles with each other. For every pair of agents $i,h$, $R(i,h)=(g,l)\in(M\cup\{\emptyset\})\times\{i,h\}$. The first value $g$ is the item to remove when agent $i$ compares their bundle with $h$’s bundle, and the second value $l$ indicates whether $g$ belongs to $i$ or $h$. $g=\emptyset$ means $i$ does not remove any item when comparing with $h$. In this case, $l$ makes no difference. Specifically, $R(i,i)=(\emptyset,i)$ for each agent $i$. A removing matrix is valid if it derives a partial allocation of $M$. That is, it does not contain two entries $(g,l_{1})$ and $(g,l_{2})$ such that $l_{1}\neq l_{2}$.

Our algorithm runs in four steps. We enumerate on all valid removing matrix $R$. For each $R$, we first allocate the items that have been pre-allocated by $R$. Next, we round the values of the unallocated items based on each agent’s valuation. Then, we run the dynamic programming search on the unallocated items under the rounded valuation to validate all possible states. Finally, we search states where an agent will not envy another agent by their rounding error under the rounded valuation after removing one item. If such a state exists, the algorithm returns the corresponding allocation. Otherwise, the algorithm returns NO. A detailed description of the algorithm is in Appendix B.

Given an removing matrix $R$, let $M^{R}$ be the set of item $g$ such there there exists an entry $(g,i)\in R$. We allocate items in $M^{R}$ according to $R$. Let $W_{0}^{R}$ and $H_{0}^{R}$ be the vector of bundle sizes and the valuation matrix after $M^{R}$ has been allocated.

For each agent $i$, let $M^{R}_{i}$ be the set of $i$’s removing items, and Let $M^{\prime}_{i}=M\setminus M^{R}_{i}$. For each agent $i$, we set the rounding upper-bound $a=\max_{g\in M^{\prime}_{i}}v_{i}(g)$. $r=m^{2}n^{2}$ is the same for all agents. We create the rounded valuation $v^{R}_{i}$ by rounding the values for all items in $M^{\prime}_{i}$. That is, for any agent $i$, $v_{i}^{R}(g)=v_{i}(g)$ if $g\in M^{R}_{i}$, and $v_{i}^{R}(g)$ is rounded to the closest larger $\frac{ka_{i}}{r}$ if $g\in M^{\prime}_{i}$. Let $u^{R}_{i}$ be the average value function of $v^{R}_{i}$. Given a fixed $M^{R}_{i}$, each bundle will have at most $Poly(m)$ possible values. Precisely, $v^{R}_{i}$ takes value from $\{0,\frac{a_{i}}{r},\frac{2a_{i}}{r},\cdots,|M^{\prime}_{i}|\cdot a_{i}\}$.

The dynamic programming follows the same procedure of Algorithm 1 that enumerates and iteratively validates states. The difference is that we run the dynamic programming only on $M^{\prime}=M\setminus M^{R}$, i.e. the unallocated items in step 1. The start state is $(W_{0}^{R},H_{0}^{R},0)$ which represent the state where all items in $M^{R}$ and no items in $M^{\prime}$ has been allocated.

Finally, we search if there is a state that satisfies two conditions. (1) The state satisfies the quota $Q$. (2) For any agent $i$ and $h$, $i$ does not envy $h$ by more than $\frac{a_{i}}{r}$ under the rounded valuation $u_{i}^{R}$, after removing one item, i.e. $u(A_{i}\setminus\{g\})\geq u(A_{i}\setminus\{g\})-\frac{a_{i}}{r}$ for some $g$. If such a state exists, the algorithm constructs the allocation backward and returns it. If such allocation does not exist for any state and any $R$, the algorithm returns NO. The reason for searching a bounded envy allocation rather than an AEF-1 allocation is to guarantee that the algorithm will always return NO if there does not exist an AEF-1 allocation (Theorem 5).

The following lemma shows that, by rounding the value function of each agent based on the most valuable item in $M^{\prime}_{i}$, the average value of an agent’s bundle is lower bound by the average value of $M^{\prime}_{i}$.

Lemma 2 guarantees that the rounding error is small compared with the bundle’s average value. Note that $M^{\prime}_{i}$ contains at most $m$ items, and the largest item has a value of $a_{i}$. Therefore, (in $i$’s valuation,) the average value of $M^{\prime}_{i}$ is at least $\frac{a_{i}}{m}$, and the average value of $A_{i}$ is at least $\frac{a_{i}}{mn}-\varepsilon$. On the other hand, the rounding error is $\frac{a_{i}}{r}=\frac{a_{i}}{m^{2}n^{2}}$. With a lower bound of average value and a bounded error, a reasonably good approximation ratio can be guaranteed, as shown in Theorem 5.