Allocating Mixed Goods with Customized Fairness and Indivisibility Ratio

The polynomial-time algorithm for finding an EFM allocation with two agents is also capable of finding an EF$\alpha$ allocation with two agents (Bei et al. (2021a)): “We begin with an EF1 allocation $(M_{1},M_{2})$ of all indivisible goods. Assume without loss of generality that $u_{1}(M_{1})\geq u_{1}(M_{2})$. Next agent 1 adds the cake into $M_{1}$ and $M_{2}$ so that the two bundles are as close to each other as possible. Note that if $u_{1}(M_{1})>u_{1}(M_{2}\cup C)$, agent 1 would add all cake to $M_{2}$. If $u_{1}(M_{1})\leq u_{1}(M_{2}\cup C)$, agent 1 has a way to make the two bundles equal. We then give agent 2 her preferred bundle and leave to agent 1 the remaining bundle.” It is easy to see that we only need to analyze the case when $u_{1}(M_{1})>u_{1}(M_{2}\cup C)$ holds and agent 1 gets $M_{2}\cup C$. Since there exists some good $g$ in $M_{1}$ such that $u_{1}(M_{2})\geq u_{1}(M_{1}\setminus\{g\})$, we have

which completes the proof. ∎

Let agent 1 partition the goods into two bundles $A_{x}$ and $A_{y}$ such that her values for the bundles are as equal as possible. Formally, let $u_{1}(A_{x})=x$ and $u_{1}(A_{y})=y$, and assume that $x\leq y$. We consider the partition that minimize $y-x$. If there are multiple such partitions, we only focus on the partition for which $u_{2}(A_{y})$ is maximized. Let agent 2 choose the bundle that she prefers, giving the other bundle to agent 1. We will show that the partition can be utilized to return an EF$\alpha$ and PO allocation.

If (1) agent 2 chooses $A_{x}$ or (2) agent 2 chooses $A_{y}$ and $x=y$, then the final allocation is EF and hence PROP. Any Pareto improvement maintains PROP which proves the existence of PROP (thus EF and EF$\alpha$) and PO.

The remaining case is that agent 2 chooses $A_{y}$ and $x<y$. We consider the Pareto optimality of the current allocation $(A_{x},A_{y})$. Suppose to the contrary that there is another allocation $(A_{x}^{\prime},A_{y}^{\prime})$ that is Pareto-dominating $(A_{x},A_{y})$. If this allocation $(A_{x}^{\prime},A_{y}^{\prime})$ is PROP (and thus EF and EF$\alpha$), we can utilize it to obtain an EF$\alpha$ and PO allocation from the same analysis as above. Otherwise, since $u_{2}(A_{y}^{\prime})\geq u_{2}(A_{y})\geq\frac{1}{2}$, we have: either (1) $\frac{1}{2}>u_{1}(A_{x}^{\prime})>u_{1}(A_{x})$ or (2) $\frac{1}{2}>u_{1}(A_{x}^{\prime})=u_{1}(A_{x})$ and $u_{2}(A_{y}^{\prime})>u_{2}(A_{y})$. Both cases lead to a contradiction with the construction of the partition $(A_{x},A_{y})$. It suffices to show $(A_{x},A_{y})$ is an EF$\alpha$ allocation. As agent 2 is clearly EF, we only need to show that agent 1 in this case is EF$\alpha$.

Assume to the contrary that we have $x<y-\alpha_{1}\cdot u_{1}(g)$ for all $g\in A_{y}$. Thus we have $x-y<-\alpha_{1}\cdot u_{1}(g)$ and $y-x>\alpha_{1}\cdot u_{1}(g)$. Observing that $A_{y}$ does not contain any pieces of cake with positive value, otherwise moving some pieces of cake to $A_{x}$ would create a more equal partition, which leads to a contradiction. Moreover, by definition of $\alpha_{1}$, we have $u_{1}(C)=\frac{1-\alpha_{1}}{\alpha_{1}}u_{1}(M)\geq(1-\alpha_{1})u_{1}(M)$. This implies that we can move some indivisible good $g\in A_{y}$ to $A_{x}$ and move some pieces of cake with value $(1-\alpha_{1})\cdot u_{1}(g)$ to $A_{y}$. Denote the resulting allocations as $A_{x}^{\prime}$ and $A_{y}^{\prime}$. Now, agent 1 has value $x^{\prime}=x+u_{1}(g)-(1-\alpha_{1})\cdot u_{1}(g)=x+\alpha_{1}\cdot u_{1}(g)$ for $A_{x}^{\prime}$ and $y^{\prime}=y-u_{1}(g)+(1-\alpha_{1})\cdot u_{1}(g)=y-\alpha_{1}\cdot u_{1}(g)$ for $A_{y}^{\prime}$. If we still have $x^{\prime}\leq y^{\prime}$, it is clear that $y^{\prime}-x^{\prime}<y-x$; otherwise, we have $x^{\prime}-y^{\prime}=x-y+2\alpha_{1}\cdot u_{1}(g)<\alpha_{1}\cdot u_{1}(g)<y-x$. It means that in either case we are able to create a more equal partition, a contradiction. This completes the proof. ∎

The proof is derived from the following counterexample where we have $n$ identical agents, one indivisible good $o$, and one homogeneous cake $C$.

Suppose the indivisible good $o$ is allocated to agent $n$. Then there must exist one agent $i\in[n-1]$ such that $u_{i}(A_{i})\leq\frac{n-2}{n(n-1)}$. For this agent $i$,

When $n\geq 3$, we have $\frac{2}{n}>\frac{1}{n-1}$, and thus $\frac{2(n-2)}{n^{2}}>\frac{n-2}{n(n-1)}$ which implies that agent $i$ fails to achieve EF$\alpha$.

The above analysis can be tighter, and we have

which implies agent $i$ fails to achieve EF$(\frac{n^{2}}{4(n-1)}-\varepsilon)\alpha$. ∎

As described after the statement of Theorem 3.4, we adopt an algorithm which finds an EF1 allocation for indivisible goods first and then utilizes the water-filling procedure to allocate the cake, where the cake will be always allocated to the agents with the smallest utility.

Based on the form $f(\alpha)=g(n)\cdot\alpha$, we then prove that for an arbitrary integer $n\geq 3$, via this algorithm, each instance that admits a function $g(n)$ can be modified to an instance with only one indivisible good and a cake that also admits a function lower bounded by $g(n)$.

Under the instance $I_{1}$ that admits a function $g(n)$, we assume the envy of $g(n)\cdot\alpha$ occurs from agent $i$ to agent $j$. Since when $j$ is fixed, the smaller $u(i)$ can lead to a larger $g(n)$, we can assume the bundle $i$ has the smallest utility among all bundles, which always receives divisible goods during the whole water-filling process and has exactly the utility at the water level (the utility of all agents receiving some cake).

Since the allocation is EF1 before allocating the cake, the difference between the utilities of bundle $j$ and bundle $i$ before allocating the divisible goods is upper bounded by some good $g\in M_{j}$. We then assume $g^{\prime}$ is the good with the largest utility in $M_{j}$, which is the corresponding $o$ used in the condition of EF$f(\alpha)$. We can then compare to the instance $I_{2}$ where only one indivisible good with utility $g^{\prime}$ is given to agent $j$. In both instances, the $g^{\prime}$s corresponding to the $o$ used in the condition of EF$f(\alpha)$ are the same but the initial difference between the utilities of agent $j$ and $i$ is larger under $I_{2}$, which is from a value weakly less than $u(g)\leq u(g^{\prime})$ to exactly $u(g^{\prime})$. Further, the divisible goods are required to be allocated to exactly $n-1$ agents from the beginning in $I_{2}$, which can makes a lower water level and a larger difference after terminating the water-filling procedure. With the decrease of $\alpha$ since there exists only one indivisible good $g^{\prime}$ in $I_{2}$, instance $I_{2}$ admits a larger $g(n)$ than that in $I_{1}$.

We can then focus on the case where there is only one indivisible good and a cake. We assume the value over the indivisible good is $x$ and the value over the cake is $1-x$, where $\alpha$ here is exactly $x$. Without loss of generality, we assume $x\geq\frac{1-x}{n-1}$ otherwise we can directly reach a PROP allocation. We then need to find an $x$ which minimizes the $g(n)$ in the inequality $x-g(n)\cdot x^{2}\leq\frac{1-x}{n-1}$, which is the condition for EF$f(\alpha)$. By some calculus, the optimal $x$ is exactly $\frac{2}{n}$, corresponding to the counterexample in Theorem 3.3. ∎

Fix an agent $i>k$. According to the definition of $k$, each agent $j$ in $\{1,\dots,k-1\}$ will be assigned a bundle with some pieces of cake $C_{j}$. It is clear to see that agent $i$’s valuation on each $C_{j}$ is at most $1/n$ since otherwise agent $i$ will be an agent that receives a bundle before agent $k$.

Next, we focus on the remaining cake. Note that if the condition in Step 1 is true, i.e., $u_{i}(B\cup\hat{C})<1/n-\alpha_{i}\cdot u_{i}(g)$ for all goods $g\in M\setminus B$, this also means that the remaining cake $\hat{C}$ worth at most $1/n$ to agent $i$.

Combined the above arguments, we have $u_{i}(C)\leq k/n$ which completes the proof. ∎

For the first case when $p>i$, because $o_{p}$ exists in round $p$, we have $o_{p}\notin A_{i}$ and then verify the case from the definitions of $g_{ij}$.

When $p<i$, since $o_{p}\neq o_{i-1}$, $o_{p}$ is not observed at round $i$ and we can prove the statement by the definitions of $g_{ij}$.

When $p=i$, the statement obviously holds. ∎

We first look at the case with $j\leq k$. By definition of $k$, each agent in $\{1,\dots,k-1\}$ is assigned her bundle in Steps 1 to 1. In other words, from the viewpoint of $j$, the value of each bundle $A_{i}$ with $i\in\{1,\dots,j-1\}$ is less than $1/n-\alpha_{j}\cdot u_{j}(g)\leq 1/n$ for some $g\not\in A_{i}$ since, otherwise, agent $j$ will be assigned before agent $i$. This means that, agent $j$’s value on the remaining goods is at least

We note that $k=n$ belongs to this case as the analysis only focus on the fact that each agent in $\{1,\dots,k-1\}$ is assigned her bundle in Steps 1 to 1.

We next consider the case with $j>k$. Similar to the above case, we can show that agent $j$’s value on each bundle $A_{i}$ with $i\in\{1,\dots,k-1\}$ is weakly less than $1/n-\alpha_{j}\cdot u_{j}(g_{ij})$. We then focus on the $k$-th assignment to the $(j-1)$-st assignment which can either be implemented in Steps 1 to 1 or in Steps 1 to 1. If the $i$-th assignment, where $k\leq i\leq j-1$, is executed by Steps 1 to 1, we can similarly obtain that $u_{j}(A_{i})\leq 1/n-\alpha_{j}\cdot u_{j}(g_{ij})$. For the situation with Steps 1 to 1, we can also have $u_{j}(A_{i})\leq 1/n-\alpha_{j}\cdot u_{j}(g_{ij})+u_{j}(o_{i})$. Now we are ready to compute agent $j$’s value over the remaining goods. Our discussion is divided into two parts: (a) $\arg\max_{k\leq p\leq j-1}u_{j}(o_{p})=\{o_{j-1}\}$ and $o_{j-1}\in A_{j}$; (b) other situations, i.e., either (i) $\arg\max_{k\leq p\leq j-1}u_{j}(o_{p})\neq\{o_{j-1}\}$ or (ii) $\arg\max_{k\leq p\leq j-1}u_{j}(o_{p})=\{o_{j-1}\}$ but $o_{j-1}\not\in A_{j}$.

We first consider Part (b), we can get:

Here, for the second inequality, we can first observe that $u_{j}(g_{ij})\geq\max_{k\leq p\leq j-1}u_{j}(o_{p})$ for each $1\leq i\leq k-1$ from Claim 4.3. For the third term in this inequality, we achieve this by presenting the fact that $\alpha_{j}\cdot u_{j}(g_{ij})-u_{j}(o_{i})\geq(\alpha_{j}-1)\max_{k\leq p\leq j-1}u_{j}(o_{p})$ is satisfied for each $k\leq i\leq j-1$. We can utilize $u_{j}(o_{i})\leq\max_{k\leq p\leq j-1}u_{j}(o_{p})$ under the case that $u_{j}(g_{ij})\geq\max_{k\leq p\leq j-1}u_{j}(o_{p})$ and apply $u_{j}(o_{i})\leq u_{j}(g_{ij})$ under the case that $u_{j}(g_{ij})<\max_{k\leq p\leq j-1}u_{j}(o_{p})$ to show this. By rearranging the terms, this is equivalent to:

The first and third inequalities are from Claim 4.2, while the fourth inequality is from the assumption of Part (b). From the assumptions of Part (b), we can conclude that $\arg\max_{k\leq p\leq j-1}u_{j}(o_{p})$ is not in the bundle $A_{j}$ so $u_{j}(g_{jj})\geq\max_{k\leq p\leq j-1}u_{j}(o_{p})$.

We next consider Part (a). We first define a term $r$ which is the largest value between $k$ and $j-1$ such that $o_{r}\neq o_{j-1}$. Since $o_{k}\in A_{k}$ which cannot be $o_{j-1}$, such $r$ must exist. We observe that each agent $i$ from $r+1$ to $j-1$ gets her bundle with mixed goods in Steps 1 to 1 since $o_{i}=o_{j-1}\in A_{j}$. The analysis of Part (a) is similar to the one of Part (b) with some mild modifications.