Maximizing Social Welfare Among EF1 Allocations at the Presence of Two Types of Agents

Ma, Jiaxuan; Chen, Yong; Chen, Guangting; Gong, Mingyang; Lin, Guohui; Zhang, An

doi:10.4230/LIPIcs.ISAAC.2025.49

Maximizing Social Welfare Among EF1 Allocations at the Presence of Two Types of Agents

Jiaxuan Ma Hangzhou Dianzi University, China Yong Chen

Hangzhou Dianzi University, China Guangting Chen

Zhejiang University of Water Resources and Electric Power, Hangzhou, China Mingyang Gong

University of Alberta, Edmonton, Canada Guohui Lin

University of Alberta, Edmonton, Canada An Zhang

Hangzhou Dianzi University, China

Abstract

We study the fair allocation of indivisible items to $n$ agents to maximize the utilitarian social welfare, where the fairness criterion is envy-free up to one item and there are only two different utility functions shared by the agents. We present a $2$ -approximation algorithm when the two utility functions are normalized, improving the previous best ratio of $16\sqrt{n}$ shown for general normalized utility functions; thus this constant ratio approximation algorithm confirms the APX-completeness in this special case previously shown APX-hard. When there are only three agents, i.e., $n=3$ , the previous best ratio is $3$ shown for general utility functions, and we present an improved and tight $\frac{5}{3}$ -approximation algorithm when the two utility functions are normalized, and a best possible and tight $2$ -approximation algorithm when the two utility functions are unnormalized.

Keywords and phrases:

Fair allocation, utilitarian social welfare, envy-free up to one item, envy-cycle elimination, round robin, approximation algorithm

Copyright and License:

2012 ACM Subject Classification:

Theory of computation

\rightarrow

Design and analysis of algorithms

Funding:

Supported by the NSERC Canada, the NNSF of China (Grants 12471301, 12371316), the PNSF of Zhejiang China (Grant LZ25A010001), and the China Scholarship Council (Grant No. 202508330173).

DOI:

10.4230/LIPIcs.ISAAC.2025.49

Event:

36th International Symposium on Algorithms and Computation (ISAAC 2025)

Editors:

Ho-Lin Chen, Wing-Kai Hon, and Meng-Tsung Tsai

Series and Publisher:

Leibniz International Proceedings in Informatics, Schloss Dagstuhl – Leibniz-Zentrum für Informatik

1 Introduction

We study a special case of the fair allocation of indivisible items to a number of agents to maximize their utilitarian social welfare, where the agents fall into two types and the fairness criterion is envy-free up to one item. We present a set of approximation algorithms that each improves the previous best one when reduced to this special case, or is the best possible for this special case.

Throughout this paper, we denote by $\{a_{1},a_{2},\ldots,a_{n}\}$ the set of $n$ agents and by $M=\{g_{1},g_{2},\ldots,g_{m}\}$ the set of $m$ indivisible items or goods. An allocation of items is an $n$ -tuple $\mathcal{A}=(A_{1},A_{2},\ldots,A_{n})$ , where $A_{i}$ is the pair-wise disjoint bundle/subset of items allocated/assigned to $a_{i}$ . The allocation is complete if $\cup_{i=1}^{n}A_{i}=M$ , i.e., every item is allocated, or otherwise it is partial. Each agent $a_{i}$ has a non-negative additive utility (or valuation) function $u_{i}:M\to\mathbb{R}_{\geq 0}$ . Extending to $2^{M}$ , for any subset $S\subseteq M$ , $u_{i}(S)=\sum_{g\in S}u_{i}(g)$ . If $u_{i}(M)=1$ for all $i$ , then the utility functions are said normalized; otherwise, they are unnormalized. The utilitarian social welfare of the allocation $\mathcal{A}=(A_{1},A_{2},\ldots,A_{n})$ is defined as $\sum_{i=1}^{n}u_{i}(A_{i})$ .

The allocation $\mathcal{A}=(A_{1},A_{2},\ldots,A_{n})$ is envy-free up to one item (EF1), if for any $i\neq j$ , $u_{i}(A_{i})\geq u_{i}(A_{j}\setminus g)$ holds for some item $g\in A_{j}$ . Between two agents $a_{i}$ and $a_{j}$ , if $u_{i}(A_{i})\geq u_{i}(A_{j})$ , then $a_{i}$ does not envy $a_{j}$ ; otherwise, $a_{i}$ envies $a_{j}$ . Similarly, if $u_{i}(A_{i})\geq u_{i}(A_{j}\setminus g)$ for some $g\in A_{j}$ , then $a_{i}$ does not strongly envy $a_{j}$ ; otherwise, $a_{i}$ strongly envies $a_{j}$ .

In this paper, we study the optimization problem to find an EF1 allocation with the maximum utilitarian social welfare, denoted as USW-EF1, and we focus on the special case where there are only two types of agents, or equivalently speaking only two distinct utility functions shared by the agents. W.l.o.g., we assume that the first $j$ agents $a_{1},a_{2},\ldots,a_{j}$ use the utility function $u_{1}$ , referred to as the first type of agents, and the last $n-j$ agents $a_{j+1},a_{j+2},\ldots,a_{n}$ use the second utility function $u_{n}$ , for some $1\leq j<n$ . Let $\mathcal{A}$ be the allocation produced by an approximation algorithm and $\mathcal{A}^{*}$ be an optimal allocation. We denote by $SOL=\sum_{i=1}^{n}u_{i}(A_{i})$ and $OPT=\sum_{i=1}^{n}u_{i}(A^{*}_{i})$ their objective values, respectively. The algorithm is an $\alpha$ -approximation if the ratio $OPT/SOL\leq\alpha$ for all instances. We remark that this two-types-of-agents special case is important for several reasons, for example, most hardness and inapproximability results are proven for this special case, and this special case also models some real application scenarios such as individual versus business investors and faculty members versus administration staff.

1.1 Related work

Discrete fair division aims to allocate a set of indivisible items to a set of agents so that all the agents feel “fair” with respect to their heterogeneous preferences over the items. Typical fairness criteria include envy-freeness (EF) [12] and proportionality [11]. By an EF allocation, each agent $a_{i}$ does not envy any other agent $a_{j}$ . Since an EF allocation does not always exist, one relaxation of EF is envy-freeness up to one item (EF1) proposed in [9, 7]. Formally speaking, for each pair of agents $a_{i},a_{j}$ , agent $a_{i}$ does not envy $a_{j}$ after the removal of some item from the bundle allocated to $a_{j}$ . Replacing the quantifier “for some” by “for any” leads to another more restricted relaxation envy-freeness up to any item (EFX) [8].

A complete EF1 allocation can be computed in polynomial time by the envy-cycle elimination (ECE) algorithm proposed by Lipton et al. [9] or by the round-robin (RR) algorithm proposed by Caragiannis et al. [8]. In brief, in the ECE algorithm, an envy digraph is constructed on the agents where agent $a_{i}$ points to agent $a_{j}$ (i.e., the arc $(a_{i},a_{j})$ exists) if $a_{i}$ envies $a_{j}$ ; whenever there is a cycle in the digraph, the bundles allocated to the agents on the cycle are rotated to eliminate the cycle; afterwards the algorithm assigns an unallocated item to an agent not envied by anyone else, and the iteration goes on. In the RR algorithm, the agents are ordered cyclically and the agent at the head of the order picks its most preferred item from the pool of unassigned items and then lines up at the back of the order, until no item is left.

Besides the existence of EF1 allocations, the price of such fair allocations is an interesting concern in economics and social science. Given that the utilitarian social welfare measures the efficiency of an allocation, the price of EF1 is defined as the ratio between the maximum utilitarian social welfare across all allocations and the maximum utilitarian social welfare among only EF1 allocations. The price of EF1 for normalized utility functions is $\Theta(\sqrt{n})$ : Barman et al. [4] first showed that the price is at most $O(\sqrt{n})$ , and later Bei et al. [5] showed that the price is at least $\Omega(\sqrt{n})$ . The price of EF1 for unnormalized utility functions is $n$ : Barman et al. [4] showed that the price is $\Theta(n)$ , and later Bu et al. [6] constructed an instance to show that it is at least $n$ .

For the optimization problem USW-EF1, Barman et al. [4] proved that it is already NP-hard for two agents even when the valuation function of an agent is a scaled version of that of the other, and it is NP-hard to approximate within a factor of $m^{1-\epsilon}$ for any $\epsilon>0$ for $n$ agents and $m$ items when both $n$ and $m$ are part of the input. When the utility functions are normalized, the problem remains NP-hard for $n$ agents when $n\geq 2$ is a fixed integer [3, 6]. Moreover, Bu et al. [6] showed several hardness results when $n\geq 3$ that, firstly the problem is NP-hard to approximate within the factor $\frac{4n}{3n+1}$ for normalized functions when one agent uses a utility function and the other agents use a common second utility function; secondly it is NP-hard to approximate within the factor $\frac{1+\sqrt{4n-3}}{2}$ for unnormalized functions when one agent uses a utility function, two other agents use a common second utility function, and all the other agents (if any) use a common third utility function; and thirdly it is NP-hard to approximate within the factor $m^{\frac{1}{2}-\epsilon}$ or within the factor $n^{\frac{1}{3}-\epsilon}$ , for any $\epsilon>0$ , for normalized utility functions when both $n$ and $m$ are part of the input.

On the positive side, Barman et al. [4] presented a $16\sqrt{n}$ -approximation algorithm when $n$ is a fixed integer and the utility functions are normalized. Aziz et al. [3] proposed a pseudo-polynomial time exact algorithm for the same variant. Bu et al. [6] gave a fully polynomial-time approximation scheme (FPTAS) for two agents and an $n$ -approximation algorithm for $n\geq 3$ agents with unnormalized utility functions.

We remark that we reviewed in the above only those directly related work, but not the entire body of the literature on fair division of indivisible goods. For example, the Nash social welfare (NSW) objective, the geometric mean of the agents’ utilities, has been extensively studied, and it is known that an allocation which maximizes NSW is EF1 [8] though approximate solutions are not necessarily EF1. One may refer to [2, 1] for an excellent survey on recent progress and open questions.

1.2 Our contribution and organization of the paper

In this paper, we aim to design approximation algorithms for the special case of USW-EF1 where there are only two distinct utility functions shared by the agents, i.e., there are two types of agents. Note that when all agents share the same utility function, a complete EF1 allocation returned by the ECE or RR algorithm is optimal. Also, given that the above two lower bounds on the approximation ratios [6] are proven for two or three utility functions, our study on the special case may shed lights on the general case. In particular, we demonstrate the use of the item preference order in all our three approximation algorithms.

We first present in the next section a $2$ -approximation algorithm for any number of agents with normalized utility functions. Then, in Section 3, we present a tight $2$ -approximation algorithm for three agents with unnormalized utility functions, which is the best possible by the lower bound $\frac{1+\sqrt{4n-3}}{2}$ [6]. Section 4 contains an improved and tight $\frac{5}{3}$ -approximation algorithm for three agents with normalized utility functions. Due to page limit, we leave the third case for three agents with unnormalized utility functions to the full arXiv version [10]. We conclude our paper in Section 5.

In all our three algorithms, the items are firstly sorted, and thus we assume w.l.o.g. that they are given, in the non-increasing order of their preferences, where the preference of an item $g$ is defined as $u_{1}(g)/u_{n}(g)$ (Definition 1) that measures the extent of preference of the first type of agents over the second type of agents. Intuitively, in an efficient allocation, items at the front of this order should be allocated to the first type of agents, while items at the back should be allocated to the second type of agents. This is exactly the main design idea.

2 A $2$ -approximation for normalized functions

Recall that agents $a_{1},\ldots,a_{j}$ share the first utility function $u_{1}(\cdot)$ and agents $a_{j+1},\ldots,a_{n}$ share the second utility function $u_{n}(\cdot)$ . For each item $g\in M$ , we assume w.l.o.g. that its two values $u_{1}(g),u_{n}(g)$ are not both $0$ .

Definition 1.

The preference of item $g$ is defined as $\rho(g)=u_{1}(g)/u_{n}(g)$ , where if $u_{n}(g)=0$ then $\rho(g)=\infty$ .

Extending to a non-empty set of items $S\subseteq M$ , the preference of $S$ is defined as $\rho(S)=u_{1}(S)/u_{n}(S)$ , where if $u_{n}(S)=0$ then $\rho(S)=\infty$ .

Specially, the preference of an empty set is $\pm\infty$ , indicating that it is less than but also greater than any real value.

We assume w.l.o.g. that $\rho(g_{1})\geq\rho(g_{2})\geq\ldots\geq\rho(g_{m})$ , i.e., the items are given in the non-decreasing preference order. Our algorithm, denoted as Approx1, uses two variables $k_{1}$ and $k_{2}$ to store the smallest and the largest indices of the unassigned items, which are initialized to $1$ and $m$ , respectively. In each iteration, the algorithm finds the agent $a_{s}$ ( $a_{t}$ , resp.) having the minimum utility among the first (second, resp.) type of agents. (Comment: These two agents $a_{s}$ and $a_{t}$ will be proven not to envy each other.) If $a_{s}$ is not envied by $a_{t}$ , then $a_{s}$ takes the item $g_{k_{1}}$ and $k_{1}$ is incremented by $1$ ; otherwise, $a_{t}$ is not envied by $a_{s}$ , $a_{t}$ takes $g_{k_{2}}$ and $k_{2}$ is decremented by $1$ . The algorithm terminates when all items are assigned (i.e., $k_{1}>k_{2}$ ), of which a high-level description is depicted in Algorithm 1.

Algorithm 1 Approx1 for normalized utility functions.

Input: $n\geq 3$ agents of two types and a set of $m$ indivisible items $\rho(g_{1})\geq\rho(g_{2})\geq\ldots\geq\rho(g_{m})$ .

Output: A complete EF1 allocation.

We next prove that inside each iteration, the found two agents $a_{s}$ and $a_{t}$ do not envy each other, and thus Approx1 produces a complete EF1 allocation. To this purpose, we introduce the following definition.

Definition 2.

For two item sets $A,B\subseteq M$ , if $\min_{g\in A\setminus B}\rho(g)\geq\max_{g\in B\setminus A}\rho(g)$ , then we say $A$ precedes $B$ and denote it as $A\prec B$ . That is, excluding the common items, every item of $A$ (if any) comes before any item of $B$ (if any) in the item preference order.

An allocation $\mathcal{A}$ is good if $A_{s}\prec A_{t}$ for every pair $(s,t)$ with $s\leq j<t$ . (Comment: Since $A_{s}\cap A_{t}=\emptyset$ , this implies $\rho(A_{s})\geq\rho(A_{t})$ .)

Recall that $\rho(\emptyset)=\pm\infty$ , if $A_{s}=\emptyset$ then both $A_{s}\prec A_{t}$ and $A_{t}\prec A_{s}$ hold.

Lemma 3.

Given a good allocation $\mathcal{A}$ , two agents of different types do not mutually envy each other.

Proof.

Assume to the contrary that for a pair $(s,t)$ with $s\leq j<t$ , $a_{s}$ and $a_{t}$ envy each other, that is, $u_{1}(A_{s})<u_{1}(A_{t})$ and $u_{n}(A_{t})<u_{n}(A_{s})$ . It follows that none of $A_{s}$ and $A_{t}$ is $\emptyset$ and $\rho(A_{s})=u_{1}(A_{s})/u_{n}(A_{s})<u_{1}(A_{t})/u_{n}(A_{t})=\rho(A_{t})$ , which contradicts the definition of a good allocation. $\hfill\blacktriangleleft$

Note that there are exactly $m$ iterations inside the algorithm Approx1, and we let $\mathcal{A}^{0}=(\emptyset,\ldots,\emptyset)$ and let $\mathcal{A}^{i}=(A_{1}^{i},\ldots,A_{n}^{i})$ denote the allocation at the end of the $i$ -th iteration. The final produced allocation is $\mathcal{A}=\mathcal{A}^{m}$ .

Lemma 4.

The allocation $\mathcal{A}^{i}$ is good and EF1, for each $i=0,1,\ldots,m$ .

Proof.

We prove by induction.

The initial empty allocation $\mathcal{A}^{0}$ is clearly good and EF1. Assume $\mathcal{A}^{i}$ is good and EF1 for some $i<m$ , and let $a_{s}$ and $a_{t}$ be the agents found in the $(i+1)$ -st iteration.

Consider the case where $a_{s}$ is not envied by $a_{t}$ (the other case is symmetric), in which the algorithm updates $A_{s}$ to $A_{s}\cup\{g_{k_{1}}\}$ . By the description of Approx1, $A_{s}\cup\{g_{k_{1}}\}$ is a non-empty subset of $\{g_{1},\ldots,g_{k_{1}}\}$ and $A_{i}\subseteq\{g_{k_{2}+1},\ldots,g_{m}\}$ for every $i\geq j+1$ . By Definitions 1 and 2 and $k_{1}\leq k_{2}$ , $A_{s}\cup\{g_{k_{1}}\}\prec A_{i}$ for every $i\geq j+1$ , and thus $\mathcal{A}^{i+1}$ is good.

Since at the beginning of the iteration $a_{s}$ is not envied by $a_{t}$ , $u_{n}(A_{t})\geq u_{n}(A_{s})$ . Also, by the definition of $s$ and $t$ , $u_{1}(A_{i})\geq u_{1}(A_{s})$ for every $i\leq j$ and $u_{n}(A_{i})\geq u_{n}(A_{t})\geq u_{n}(A_{s})$ for every $i\geq j+1$ . That is, no agent envies $a_{s}$ in the allocation $\mathcal{A}^{i}$ , and thus does not strongly envy $a_{s}$ in the allocation $\mathcal{A}^{i+1}$ (by removing the item $g_{k_{1}}$ ). Note that in this iteration only $a_{s}$ gets an item. Therefore, $\mathcal{A}^{i+1}$ is EF1 as $\mathcal{A}^{i}$ is EF1. $\hfill\blacktriangleleft$

Theorem 5.

Approx1 is a $2$ -approximation algorithm.

Proof.

For the optimal allocation $\mathcal{A}^{*}$ , we have

OPT=\sum_{i=1}^{n}u_{i}(A^{*}_{i})=u_{1}(\cup_{i=1}^{j}A^{*}_{i})+u_{n}(\cup_{% i=j+1}^{n}A^{*}_{i})\leq u_{1}(M)+u_{n}(M)=2.

Note from Lemma 4 that the final allocation $\mathcal{A}$ produced by Approx1 is complete, good and EF1. By Definition 2, we have $\rho(\cup_{i=1}^{j}A_{i})\geq\rho(\cup_{i=j+1}^{n}A_{i})$ . Therefore, either $\rho(\cup_{i=1}^{j}A_{i})\geq 1$ or $\rho(\cup_{i=j+1}^{n}A_{i})<1$ ; or equivalently, either $u_{1}(\cup_{i=1}^{j}A_{i})\geq u_{n}(\cup_{i=1}^{j}A_{i})$ or $u_{1}(\cup_{i=j+1}^{n}A_{i})<u_{n}(\cup_{i=j+1}^{n}A_{i})$ . In the first case, we have

SOL=\sum_{i=1}^{n}u_{i}(A_{i})=u_{1}(\cup_{i=1}^{j}A_{i})+u_{n}(\cup_{i=j+1}^{% n}A_{i})=u_{1}(\cup_{i=1}^{j}A_{i})-u_{n}(\cup_{i=1}^{j}A_{i})+u_{n}(M)\geq 1.

In the second case, we have

SOL=u_{1}(\cup_{i=1}^{j}A_{i})+u_{n}(\cup_{i=j+1}^{n}A_{i})=u_{1}(M)-u_{1}(% \cup_{i=j+1}^{n}A_{i})+u_{n}(\cup_{i=j+1}^{n}A_{i})>1.

Therefore, $SOL\geq\frac{1}{2}OPT$ always holds. $\hfill\blacktriangleleft$

3 A $2$ -approximation for three agents with unnormalized functions

We continue to assume w.l.o.g. that the items are given in their preference order, that is, $\rho(g_{1})\geq\rho(g_{2})\geq\ldots\geq\rho(g_{m})$ , and use the definitions of precedence and good allocation in Definition 2. Since there are only three agents categorized into two types, we assume w.l.o.g. that $j=1$ , i.e., agent $a_{1}$ is of the first type and agents $a_{2}$ and $a_{3}$ are of the second type.

For ease of presentation we partition the items into two sets based on their preference:

X=\{g\in M:u_{1}(g)\geq u_{3}(g)\},\ \ Y=\{g\in M:u_{1}(g)<u_{3}(g)\}.

(1)

We first examine the structure of a fixed optimal EF1 allocation, denoted as $(A^{*}_{1},A^{*}_{2},A^{*}_{3})$ . Denote the item $g^{*}=\arg\max_{g\in A^{*}_{1}}u_{3}(g)$ , i.e., the most valuable to $a_{2}$ and $a_{3}$ among those items allocated to $a_{1}$ . The following lemma establishes an important upper bound on $u_{3}(A^{*}_{1}\setminus g^{*})$ .

Lemma 6.

$u_{3}(A^{*}_{1}\setminus g^{*})\leq\frac{1}{3}u_{3}(M\setminus g^{*})$ .

Proof.

Suppose to the contrary that $u_{3}(A^{*}_{1}\setminus g^{*})>\frac{1}{3}u_{3}(M\setminus g^{*})$ . Then we have

u_{3}(A^{*}_{2}\cup A^{*}_{3})=u_{3}(M)-u_{3}(A_{1}^{*})=u_{3}(M\setminus g^{*% })-u_{3}(A_{1}^{*}\setminus g^{*})<2u_{3}(A_{1}^{*}\setminus g^{*}).

It follows that at least one of $u_{3}(A^{*}_{2})$ and $u_{3}(A^{*}_{3})$ is less than $u_{3}(A^{*}_{1}\setminus g^{*})$ . W.l.o.g., we assume $u_{3}(A^{*}_{2})<u_{3}(A^{*}_{1}\setminus g^{*})$ , and thus by the definition of $g^{*}$ agent $a_{2}$ strongly envies $a_{1}$ , a contradiction to EF1. $\hfill\blacktriangleleft$

We next present an upper bound on the optimal total utility $O P T$ . To this purpose, we define what a critical set is below. We remark that although the definition relies on the fixed optimal EF1 allocation $\mathcal{A}^{*}$ , we can actually compute a critical set for any item, by the procedure Algo2 presented in Subsection 3.1.

Definition 7.

An item set $K$ is critical for an item $g$ if the following three conditions are satisfied:

1.

$g\in K$ and $K\setminus g\subseteq X$ ;
2.

$K\setminus g$ $\prec$ $A^{*}_{1}\setminus g$ ;
3.

$u_{3}(K\setminus g)\geq\min\{u_{3}(X\setminus g),\frac{1}{3}u_{3}(M\setminus g)\}$ .

Lemma 8.

For any critical set $K$ for $g^{*}$ , we have $OPT\leq u_{1}(K)+u_{3}(M\setminus K)$ .

Proof.

We partition the items of $A^{*}_{1}\setminus g^{*}$ into two sets according to Eq. (1):

B_{1}=(A_{1}^{*}\setminus g^{*})\cap X,\ \ B_{2}=(A^{*}_{1}\setminus g^{*})% \cap Y.

One sees from $B_{2}\subseteq Y$ that $u_{1}(B_{2})\leq u_{3}(B_{2})$ . Since $K\setminus g^{*}\prec A^{*}_{1}\setminus g^{*}$ and $B_{1}\subseteq A^{*}_{1}\setminus g^{*}$ , $K\setminus g^{*}\prec B_{1}$ too. Let $C=(K\setminus g^{*})\cap B_{1}$ ; then $\rho(K\setminus\{g^{*}\cup C\})\geq\rho(B_{1}\setminus C)$ . Since $K\setminus g^{*}\subseteq X$ , $\rho(K\setminus g^{*})\geq 1$ . In summary, we have

\rho(K\setminus\{g^{*}\cup C\})\geq\max\{\rho(B_{1}\setminus C),1\}.

By the third condition in Definition 7 and Lemma 6, we have

$\displaystyle u_{3}(K\setminus\{g^{*}\cup C\})$	$\displaystyle\geq$	$\displaystyle\min\{u_{3}(X\setminus g^{}),\frac{1}{3}u_{3}(M\setminus g^{})% \}-u_{3}(C)$
	$\displaystyle\geq$	$\displaystyle\min\{u_{3}(X\setminus g^{}),u_{3}(A^{}_{1}\setminus g^{*})\}-u% _{3}(C)$
	$\displaystyle\geq$	$\displaystyle u_{3}(B_{1}\setminus C).$

The above inequalities together give rise to

$\displaystyle u_{1}(A_{1}^{}\setminus g^{})-u_{3}(A_{1}^{}\setminus g^{})$	$\displaystyle\leq$	$\displaystyle u_{1}(B_{1})-u_{3}(B_{1})$	(2)
	$\displaystyle=$	$\displaystyle u_{1}(C)-u_{3}(C)+u_{1}(B_{1}\setminus C)-u_{3}(B_{1}\setminus C)$
	$\displaystyle=$	$\displaystyle u_{1}(C)-u_{3}(C)+u_{3}(B_{1}\setminus C)(\rho(B_{1}\setminus C)% -1)$
	$\displaystyle\leq$	$\displaystyle u_{1}(C)-u_{3}(C)+u_{3}(K\setminus\{g^{}\cup C\})(\rho(K% \setminus\{g^{}\cup C\})-1)$
	$\displaystyle=$	$\displaystyle u_{1}(K\setminus g^{})-u_{3}(K\setminus g^{}).$

It follows from the above Eq. (2) that

$\displaystyle OPT$	$\displaystyle=$	$\displaystyle u_{1}(g^{})+u_{1}(A_{1}^{}\setminus g^{})+u_{3}(A_{2}^{}\cup A% _{3}^{*})$
	$\displaystyle\leq$	$\displaystyle u_{1}(g^{})+u_{3}(A_{1}^{}\setminus g^{})+u_{1}(K\setminus g^% {})-u_{3}(K\setminus g^{})+u_{3}(A_{2}^{}\cup A_{3}^{*})$
	$\displaystyle=$	$\displaystyle u_{1}(K)+u_{3}(M\setminus K).$

This proves the lemma. $\hfill\blacktriangleleft$

The next lemma states an important property for any allocation in which agent $a_{1}$ is envied, by the fact that $a_{2}$ and $a_{3}$ share the same utility function $u_{3}$ .

Lemma 9.

Suppose $\mathcal{A}$ is an allocation in which agent $a_{1}$ is envied. If $a_{2}$ ( $a_{3}$ , resp.) is not envied by $a_{3}$ ( $a_{2}$ , resp.), then $a_{2}$ envies $a_{1}$ , i.e., $u_{3}(A_{2})<u_{3}(A_{1})$ ( $a_{3}$ envies $a_{1}$ , i.e., $u_{3}(A_{3})<u_{3}(A_{1})$ , resp.).

Proof.

We prove the lemma for $a_{2}$ (for $a_{3}$ it is symmetric), that is, agent $a_{2}$ is not envied by $a_{3}$ , but $a_{1}$ is envied by at least one of $a_{2}$ and $a_{3}$ .

If $a_{2}$ does not envy $a_{1}$ , then $a_{3}$ envies $a_{1}$ , i.e., $u_{3}(A_{2})\geq u_{3}(A_{1})>u_{3}(A_{3})$ , a contradiction to $a_{2}$ not envied by $a_{3}$ . $\hfill\blacktriangleleft$

3.1 Producing a critical set for every item

Recall that the items are given in the preference order $\rho(g_{1})\geq\rho(g_{2})\geq\ldots\geq\rho(g_{m})$ ; and we see from Eq. (1) that $X\prec Y$ . For any ordered item set, if the order inherits the given preference order, then it is regular.

Note from Lemma 8 that a critical set for the item $g^{*}$ plays an important role, but we have no knowledge of $A^{*}_{1}$ or $g^{*}$ . Below we construct a critical set for every item $g_{i}\in M$ , in the procedure Algo2 depicted in Algorithm 2. The key idea is, excluding $g_{i}$ , the critical set matches a prefix of the item preference order.

Algorithm 2 Algo2 for computing a critical set.

Input: The item preference order $S=\langle g_{1},\ldots,g_{m}\rangle$ and an item $g_{i}\in M$ .

Output: A critical set $K$ for $g_{i}$ .

Lemma 10.

Algo2 produces a critical set $K$ for the item $g_{i}$ .

Proof.

Consider the index $t$ in Line 1 of the procedure Algo2. Clearly, $t\leq|X|$ . If $t<i$ , then $g_{i}\in K$ and $K\setminus g_{i}=\{g_{1},\ldots,g_{t}\}$ . Therefore, $K\setminus g_{i}\subseteq X$ and $K\setminus g_{i}\prec A_{1}^{*}\setminus g_{i}$ . Lastly, $u_{3}(K\setminus g_{i})=\sum_{j=1}^{t}u_{3}(g_{j})\geq\min\{u_{3}(X\setminus g% _{i}),\frac{1}{3}u_{3}(M\setminus g_{i})\}$ . All the three conditions in Definition 7 are satisfied and thus $K$ is a critical set for $g_{i}$ .

If $t\geq i$ , then $t^{\prime}$ in Line 5 exists and $|X|\geq t^{\prime}\geq t\geq i$ . Therefore, $g_{i}\in K$ , $K\subseteq X$ and $K\setminus g_{i}\prec A_{1}^{*}\setminus g_{i}$ . Lastly, $u_{3}(K\setminus g_{i})=\sum_{j=1}^{t^{\prime}}u_{3}(g_{j})-u_{3}(g_{i})\geq% \min\{u_{3}(X\setminus g_{i}),\frac{1}{3}u_{3}(M\setminus g_{i})\}$ . All the three conditions in Definition 7 are satisfied and thus $K$ is a critical set for $g_{i}$ . $\hfill\blacktriangleleft$

Given that the procedure Algo2 is able to produce a critical set for any item, by enumerating the items we will have a critical set $K$ for the item $g^{*}$ , and thus by Lemma 8 to bound the $O P T$ . From $K$ , we will also design algorithms to return a complete EF1 allocation of total utility at least half of this bound and thus at least $\frac{1}{2}\cdot OPT$ .

In the next three subsections, we deal with the critical set $K$ produced by Algo2 for an item $g_{i}$ , separately for three possible cases. Let $k=|K|$ . When $\max_{g\in K}u_{1}(g)<\frac{1}{2}u_{1}(K)$ , $K$ contains at least three items, i.e., $k\geq 3$ ; if the index of the item $g_{i}$ is $i\geq k$ , then we modify the item order $S$ by moving the item $g_{i}$ to the $(k-1)$ -st position, and denote the new order as $S^{\prime}=\langle g^{\prime}_{1},\ldots,g^{\prime}_{m}\rangle$ . Note that the net effect is, if $i\geq k$ , then the items $g_{k-1},\ldots,g_{i-1}$ are moved one position forward to become $g^{\prime}_{k},\ldots,g^{\prime}_{i}$ ; otherwise $S^{\prime}$ is identical to $S$ . In either case, $S^{\prime}\setminus g^{\prime}_{k-1}$ is regular and $K$ contains the first $k$ items in the order $S^{\prime}$ , summarized in Remark 11.

The three distinguished cases are (due to space limit, Case 3 is dealt with in detail in the full arXiv version [10]):

1.

$\max_{g\in K}u_{1}(g)\geq\frac{1}{2}u_{1}(K)$ ;
2.

$\max_{g\in K}u_{1}(g)<\frac{1}{2}u_{1}(K)$ and $u_{3}(g^{\prime}_{k})>u_{3}(M\setminus K)$ ;
3.

$\max_{g\in K}u_{1}(g)<\frac{1}{2}u_{1}(K)$ and $u_{3}(g^{\prime}_{k})\leq u_{3}(M\setminus K)$ .

$\blacktriangleright$ Remark 11.

In Cases 2 and 3, i.e., $\max_{g\in K}u_{1}(g)<\frac{1}{2}u_{1}(K)$ and thus $k=|K|\geq 3$ , for the new item order $S^{\prime}$ , $g^{\prime}_{k}\neq g_{i}$ , $S^{\prime}\setminus g^{\prime}_{k-1}$ is regular, $K=\{g^{\prime}_{1},g^{\prime}_{2},\ldots,g^{\prime}_{k}\}$ , and $\sum_{j=1}^{k-1}u_{3}(g^{\prime}_{j})<\frac{1}{3}u_{3}(M\setminus g_{i})+u_{3}% (g_{i})$ .

Proof.

We only need to prove the last inequality $\sum_{j=1}^{k-1}u_{3}(g^{\prime}_{j})<\frac{1}{3}u_{3}(M\setminus g_{i})+u_{3}% (g_{i})$ .

If $K$ is outputted in Line 3 of the algorithm Algo2, then $k=t+1$ and $\sum_{j=1}^{k-1}u_{3}(g^{\prime}_{j})=\sum_{j=1}^{t-1}u_{3}(g_{j})+u_{3}(g_{i}% )<\frac{1}{3}u_{3}(M\setminus g_{i})+u_{3}(g_{i})$ , i.e., the inequality holds. If $K$ is outputted in Line 6 of the algorithm Algo2 and $i<t^{\prime}=k$ , then $\sum_{j=1}^{k-1}u_{3}(g^{\prime}_{j})=\sum_{j=1}^{t^{\prime}-1}u_{3}(g_{j})<% \frac{1}{3}u_{3}(M\setminus g_{i})+u_{3}(g_{i})$ , i.e., the inequality holds. If $K$ is outputted in Line 6 of the algorithm Algo2 and $i=t=t^{\prime}=k$ , then $\sum_{j=1}^{k-1}u_{3}(g^{\prime}_{j})\leq\sum_{j=1}^{t-1}u_{3}(g_{j})+u_{3}(g_% {i})<\frac{1}{3}u_{3}(M\setminus g_{i})+u_{3}(g_{i})$ , i.e., the inequality holds. This proves the last inequality. $\hfill\blacktriangleleft$

3.2 Case 1: $\max_{g\in K}u_{1}(g)\geq\frac{1}{2}u_{1}(K)$

Recall that $K$ is the critical set for the item $g_{i}$ produced by the procedure Algo2. This case where $\max_{g\in K}u_{1}(g)\geq\frac{1}{2}u_{1}(K)$ is considered easy, and we present an algorithm Approx3 to produce a complete EF1 allocation.

The algorithm starts with the allocation $\mathcal{A}=(\{g\},\emptyset,\emptyset)$ , where the item $g$ is one such that $u_{1}(g)\geq\frac{1}{2}u_{1}(K)$ . $\mathcal{A}$ is trivially EF1 and $u_{1}(A_{1})\geq\frac{1}{2}u_{1}(K)$ . In fact, $\mathcal{A}$ is well-defined with permutation $(1,2,3)$ , formally defined below.

Definition 12.

An allocation $\mathcal{A}$ is well-defined with permutation $(i_{1},i_{2},i_{3})$ if

1.

$\mathcal{A}$ is EF1;
2.

$u_{1}(A_{1})\geq\frac{1}{2}u_{1}(K)$ and $u_{3}(A_{1})\leq u_{3}(K)$ ;
3.

$(i_{1},i_{2},i_{3})\in\{(1,2,3),(3,1,2)\}$ such that agent $a_{i_{1}}$ does not envy $a_{i_{2}}$ or $a_{i_{3}}$ , and $a_{i_{2}}$ does not envy $a_{i_{3}}$ .

Given the well-defined allocation $\mathcal{A}=(\{g\},\emptyset,\emptyset)$ with permutation $(1,2,3)$ , let $U=M\setminus(A_{1}\cup A_{2}\cup A_{3})$ be the unassigned item set. The algorithm Approx3 fixes the agent order $\langle a_{3},a_{2},a_{1}\rangle$ to apply the Round-Robin (RR) algorithm to distribute the items of $U$ . A high-level description of the algorithm is depicted in Algorithm 3, which accepts a general well-defined allocation.

Algorithm 3 Approx3 for a complete EF1 allocation.

Input: A well-defined allocation $\mathcal{A}=(A_{1},A_{2},A_{3})$ with permutation $(i_{1},i_{2},i_{3})$ .

Output: A complete EF1 allocation.

Lemma 13.

Given a well-defined allocation $\mathcal{A}=(A_{1},A_{2},A_{3})$ with permutation $(i_{1},i_{2},i_{3})$ , Approx3 produces a complete EF1 allocation with total utility at least $\frac{1}{2}u_{1}(K)+\frac{1}{2}u_{3}(M\setminus K)$ .

Proof.

Note from the RR algorithm that the returned allocation $(A_{1}\cup U_{1},A_{2}\cup U_{2},A_{3}\cup U_{3})$ is complete.

The initial allocation $\mathcal{A}=(A_{1},A_{2},A_{3})$ is EF1 by Definition 12. Consider any two agents $a_{s}$ and $a_{t}$ , where $s$ precedes $t$ in the permutation $(i_{1},i_{2},i_{3})$ . That is, $a_{s}$ does not envy $a_{t}$ , and thus $u_{s}(A_{s})\geq u_{s}(A_{t})$ . Since the RR algorithm uses the agent order $\langle a_{i_{3}},a_{i_{2}},a_{i_{1}}\rangle$ , we have $u_{s}(U_{s})\geq u_{s}(U_{t})-u_{s}(g)$ , where $g$ is the first item picked by agent $a_{t}$ ; and thus $u_{s}(A_{s}\cup U_{s})\geq u_{s}(A_{t}\cup U_{t})-u_{s}(g)$ for the same $g\in U_{t}$ . That is, $a_{s}$ does not strongly envy $a_{t}$ . Similarly, since $\mathcal{A}$ is EF1, $u_{t}(A_{t})\geq u_{t}(A_{s})-u_{t}(g)$ for some $g\in A_{s}$ ; we have $u_{t}(U_{t})\geq u_{t}(U_{s})$ by the RR algorithm. Thus $u_{t}(A_{t}\cup U_{t})\geq u_{t}(A_{s}\cup U_{s})-u_{t}(g)$ for the same $g\in A_{s}$ , that is, $a_{t}$ does not strongly envy $a_{s}$ . Therefore, the returned allocation is EF1.

We estimate the total utility of the returned allocation as follows. Since the agent index $1$ precedes $2$ in the permutation $(i_{1},i_{2},i_{3})\in\{(1,2,3),(3,1,2)\}$ , we have $u_{3}(U_{2})\geq u_{3}(U_{1})$ from the RR algorithm; we also have $u_{1}(A_{1})\geq\frac{1}{2}u_{1}(K)$ and $u_{3}(A_{1})\leq u_{3}(K)$ from Definition 12 of well-defined allocation, the total utility of the returned allocation is $u_{1}(A_{1}\cup U_{1})+u_{3}(A_{2}\cup A_{3}\cup U_{2}\cup U_{3})$ , which is at least

\frac{1}{2}u_{1}(K)+\frac{1}{2}u_{3}(M\setminus A_{1})=\frac{1}{2}u_{1}(K)+% \frac{1}{2}u_{3}(M)-\frac{1}{2}u_{3}(A_{1})\geq\frac{1}{2}u_{1}(K)+\frac{1}{2}% u_{3}(M\setminus K).

This proves the lemma. $\hfill\blacktriangleleft$

Theorem 14.

Let $K$ be the critical set of the item $g^{*}$ produced by the procedure Algo2. If $\max_{g\in K}u_{1}(g)\geq\frac{1}{2}u_{1}(K)$ , then Approx3 returns a complete EF1 allocation with its total utility at least $\frac{1}{2}OPT$ .

Proof.

For this set $K$ , the allocation $\mathcal{A}=(\{g\},\emptyset,\emptyset)$ is well-defined with the permutation $(1,2,3)$ , where $g=\arg\max_{g\in K}u_{1}(g)$ . The theorem follows from Lemmas 13 and 8. $\hfill\blacktriangleleft$

3.3 Case 2: $\max_{g\in K}u_{1}(g)<\frac{1}{2}u_{1}(K)$ and $u_{3}(g^{\prime}_{k})>u_{3}(M\setminus K)$

Recall that $K$ is the critical set of an item $g_{i}$ produced by the procedure Algo2. In this case, $k=|K|\geq 3$ and we work with the new item order $S^{\prime}$ such that $S^{\prime}\setminus g^{\prime}_{k-1}$ is regular, and $g^{\prime}_{k}\neq g_{i}$ . Adding the last inequality $\sum_{j=1}^{k-1}u_{3}(g^{\prime}_{j})<\frac{1}{3}u_{3}(M\setminus g_{i})+u_{3}% (g_{i})$ from Remark 11 and $u_{3}(g^{\prime}_{k})>u_{3}(M\setminus K)$ together gives

u_{3}(g^{\prime}_{k})>\frac{1}{3}u_{3}(M\setminus g_{i})\geq u_{3}(K\setminus% \{g^{\prime}_{k},g_{i}\}),\mbox{ and thus }u_{3}(g^{\prime}_{k})>\frac{1}{2}u_% {3}(K\setminus g_{i}).

(3)

One sees from the above three lower bounds on $u_{3}(g^{\prime}_{k})$ that the item $g^{\prime}_{k}$ is very valuable to agents $a_{2}$ and $a_{3}$ . We design another algorithm called Approx7 for this case to construct a complete EF1 allocation, in which $g^{\prime}_{k}$ is the only item assigned to $a_{3}$ .

Inside the algorithm Approx7, the first procedure Algo4 produces a partial EF1 and good allocation. It starts with the allocation $\mathcal{A}=(\{g^{\prime}_{1}\},\emptyset,\{g^{\prime}_{k}\})$ , which is EF1 and good (see Definition 2), and uses the order $S^{\prime}$ to allocate the items in the two sets $K\setminus\{g^{\prime}_{1}\cup g^{\prime}_{k}\}$ and $M\setminus K$ to the agents $a_{1}$ and $a_{2}$ , respectively, till exactly one of them becomes empty. A detailed description of the procedure is depicted in Algorithm 4.

Algorithm 4 Algo4 for a partial EF1 and good allocation.

Input: The critical set $K$ for item $g_{i}$ satisfying $\max_{g\in K}u_{1}(g)<\frac{1}{2}u_{1}(K)$ , the new item order $S^{\prime}$ in which $g^{\prime}_{k}\neq g_{i}$ , and $u_{3}(g^{\prime}_{k})>u_{3}(M\setminus K)$ .

Output: A partial EF1 allocation $\mathcal{A}$ .

Lemma 15.

Given the critical set $K$ for item $g_{i}$ produced by the procedure Algo2 satisfying $\max_{g\in K}u_{1}(g)<\frac{1}{2}u_{1}(K)$ , $k=|K|$ , the new item order $S^{\prime}$ in which $g^{\prime}_{k}\neq g_{i}$ , and $u_{3}(g^{\prime}_{k})>u_{3}(M\setminus K)$ , Algo4 produces a partial EF1 and good allocation.

Proof.

Note from the description that when Algo4 terminates, either $k_{1}=k<k_{2}$ or $k_{1}<k=k_{2}$ , i.e., at least one item remains unassigned, and thus the returned allocation $\mathcal{A}$ is incomplete.

We remark that since the procedure starts with the allocation $(\{g^{\prime}_{1}\},\emptyset,\{g^{\prime}_{k}\})$ , and allocates the items in the two sets $K\setminus\{g^{\prime}_{1}\cup g^{\prime}_{k}\}$ and $M\setminus K$ to the agents $a_{1}$ and $a_{2}$ , respectively, the bundle $A_{1}\prec A_{2}$ and $A_{1}\prec A_{3}$ throughout the procedure, and thus the allocation maintains good (see Definition 2). Also throughout the procedure, since $A_{3}=\{g^{\prime}_{k}\}$ contains a single item, no one strongly envies $a_{3}$ ; since $u_{3}(g^{\prime}_{k})>u_{3}(M\setminus K)$ and Eq. (3), agent $a_{3}$ does not strongly envy any of $a_{1}$ or $a_{2}$ .

We show next that throughout the procedure, between $a_{1}$ and $a_{2}$ , no one strongly envies the other, and thus the final allocation is EF1. This is true for the starting allocation $(\{g^{\prime}_{1}\},\emptyset,\{g^{\prime}_{k}\})$ . Assume this is true for the allocation at the beginning of an iteration of the while-loop; since the allocation is good, by Lemma 3 $a_{1}$ and $a_{2}$ do not envy each other. If $a_{1}$ is not envied by $a_{2}$ , then the item $g^{\prime}_{k_{1}}\in K\setminus g^{\prime}_{k}$ is assigned to $a_{1}$ , and thus $a_{2}$ does not strongly envy $a_{1}$ due to $g^{\prime}_{k_{1}}$ at the end of the iteration; $a_{1}$ remains not strongly envy $a_{2}$ , also due to $g^{\prime}_{k_{1}}$ at the end of the iteration. If $a_{2}$ is not envied by $a_{1}$ , then the item $g^{\prime}_{k_{2}}\in M\setminus K$ is assigned to $a_{2}$ , and thus $a_{1}$ does not strongly envy $a_{2}$ due to $g^{\prime}_{k_{2}}$ at the end of the iteration; $a_{2}$ remains not strongly envy $a_{1}$ , also due to $g^{\prime}_{k_{2}}$ at the end of the iteration. $\hfill\blacktriangleleft$

If the procedure Algo4 terminates at $k_{1}<k=k_{2}$ , then the returned allocation is $\mathcal{A}=(\{g^{\prime}_{1},\ldots,g^{\prime}_{k_{1}-1}\},M\setminus K,\{g^{% \prime}_{k}\})$ and the unassigned item set is $U=\{g^{\prime}_{k_{1}},\ldots,g^{\prime}_{k-1}\}$ . The next procedure Algo5 continues on to assign the items of $U$ to produce a complete EF1 allocation, by re-setting $k_{2}=k-1$ . A detailed description of Algo5 is depicted in Algorithm 5. Basically, if at least one of $a_{1}$ and $a_{2}$ is not envied by any of the other two agents, then the procedure allocates an unassigned item to such a non-envied agent; otherwise, both $a_{1}$ and $a_{2}$ are envied by some agent and the procedure allocates all the remaining unassigned items to $a_{1}$ . That is, either $g^{\prime}_{k_{1}}$ is assigned to $a_{1}$ , or $g^{\prime}_{k_{2}}$ is assigned to $a_{2}$ , or all of the items of $U=\{g^{\prime}_{k_{1}},\ldots,g^{\prime}_{k_{2}}\}$ are assigned to $a_{1}$ , respectively. One sees that the allocation $\mathcal{A}$ remains good before the last item is assigned (in fact, the allocation loses being good only if the last item is $g^{\prime}_{k-1}=g_{i}$ and it is assigned to $a_{1}$ ) in the procedure Algo5, and consequently $a_{1}$ and $a_{2}$ do not envy each other by Lemma 3 before the last item is assigned.

Algorithm 5 Algo5 for a complete EF1 allocation.

Input: The critical set $K$ for item $g_{i}$ satisfying $\max_{g\in K}u_{1}(g)<\frac{1}{2}u_{1}(K)$ , the new item order $S^{\prime}$ in which $g^{\prime}_{k-1}=g_{i}$ , and $u_{3}(g^{\prime}_{k})>u_{3}(M\setminus K)$ ; the EF1 and good allocation $\mathcal{A}=(\{g^{\prime}_{1},\ldots,g^{\prime}_{k_{1}-1}\},M\setminus K,\{g^{% \prime}_{k}\})$ returned by Algo4, where $k_{1}<k$ .

Output: A complete EF1 allocation $\mathcal{A}$ .

Lemma 16.

Algo5 produces a complete EF1 allocation.

Proof.

Since there will not be any unassigned item at the end of the procedure, the returned allocation is complete. We remind the readers that during the execution of Algo5, the allocation $\mathcal{A}$ remains good before the last item is assigned.

The starting allocation $\mathcal{A}=(\{g^{\prime}_{1},\ldots,g^{\prime}_{k_{1}-1}\},M\setminus K,\{g^{% \prime}_{k}\})$ , which is returned by Algo4, is EF1 and good. At the beginning of an iteration of the while-loop, if $a_{1}$ is not envied by any other agent (the case where $a_{2}$ is not envied by any other agent is symmetric), then after $g^{\prime}_{k_{1}}$ is allocated to $a_{1}$ no agent will strongly envy $a_{1}$ . That is, the updated allocation is EF1 too.

Consider the last case of the while-loop, i.e., at the beginning of the last iteration $\mathcal{A}=(A_{1},A_{2},\{g^{\prime}_{k}\})$ is the EF1 and good allocation in which both $a_{1}$ and $a_{2}$ are envied by some agent.

We claim that $a_{3}$ envies $a_{2}$ . If not, i.e., $u_{3}(g^{\prime}_{k})\geq u_{3}(A_{2})$ , then $a_{2}$ is envied by $a_{1}$ , and thus by Lemma 3, $a_{2}$ does not envy $a_{1}$ , i.e., $u_{3}(A_{2})\geq u_{3}(A_{1})$ . It follows that $a_{3}$ does not envy $a_{1}$ . That is, $a_{1}$ is not envied by any agent, a contradiction.

In the final allocation $\mathcal{A}^{\prime}=(A_{1}\cup U,A_{2},\{g^{\prime}_{k}\})$ , $a_{1}$ does not strongly envy any of $a_{2}$ or $a_{3}$ for sure, and none of $a_{2}$ and $a_{3}$ strongly envies the other. From Eq. (3) $a_{3}$ does not strongly envy $a_{1}$ . Since $a_{3}$ envies $a_{2}$ , $a_{2}$ does not strongly envy $a_{1}$ either.

In summary, no agent strongly envies another agent in the final allocation $\mathcal{A}^{\prime}$ . $\hfill\blacktriangleleft$

The allocation returned by the procedure Algo5 is complete and EF1. The next procedure Algo6 takes in a complete EF1 allocation $\mathcal{A}=(A_{1},A_{2},A_{3})$ , and if in which agent $a_{1}$ envies $a_{2}$ , i.e., $u_{1}(A_{1})<u_{1}(A_{2})$ , then outputs the allocation between $\mathcal{A}$ and $(A_{2},A_{1},A_{3})$ with a larger total utility. In general, for a complete EF1 allocation $\mathcal{A}=(A_{1},A_{2},A_{3})$ , the allocation $(A_{2},A_{1},A_{3})$ after bundle swapping might not be EF1. We nevertheless show in the next lemma that the allocation returned by the procedure Algo6 is EF1.

Algorithm 6 Algo6 for a larger total utility.

Input: The complete EF1 allocation $\mathcal{A}=(A_{1},A_{2},A_{3})$ returned by Algo5.

Output: A complete EF1 allocation.

Lemma 17.

Algo6 produces a complete EF1 allocation.

Proof.

Note that $\mathcal{A}=(A_{2},A_{1},\{g^{\prime}_{k}\})$ can be returned only if $u_{1}(A_{1})<u_{1}(A_{2})$ . We show that in such a case, none of $a_{1}$ and $a_{2}$ strongly envies the other in $(A_{2},A_{1},\{g^{\prime}_{k}\})$ (noting that $a_{3}$ does not strongly envy $a_{1}$ or $a_{2}$ , the same as in $\mathcal{A}$ , and none of $a_{1}$ and $a_{2}$ strongly envies $a_{3}$ who is allocated with the single item $g^{\prime}_{k}$ ). Because $u_{1}(A_{2})>u_{1}(A_{1})$ , $a_{1}$ does not envy $a_{2}$ in the allocation $(A_{2},A_{1},\{g^{\prime}_{k}\})$ .

Let $g$ be the last item allocated to $A_{2}$ , done either by Algo4 or by Algo5. If this is done by Algo4, then ( $g$ is $g^{\prime}_{k+1}$ and) by Lines 6–7 in the description at that moment $a_{2}$ envies $a_{1}$ , and thus $u_{3}(A_{2}\setminus g)<u_{3}(\{g^{\prime}_{1},\ldots,g^{\prime}_{k_{1}-1}\}% \leq u_{3}(A_{1})$ . If $g$ is allocated by Algo5, then by Lines 5–6 in the description at that moment $a_{1}$ is envied by some agent and $a_{2}$ is not envied by any agent, and thus by Lemma 9 $u_{3}(A_{2}\setminus g)<u_{3}(\{g^{\prime}_{1},\ldots,g^{\prime}_{k_{1}-1}\}% \leq u_{3}(A_{1})$ . Therefore, we always have $u_{3}(A_{1})>u_{3}(A_{2}\setminus g)$ , i.e., $a_{2}$ does not strongly envy $a_{1}$ in the allocation $(A_{2},A_{1},\{g^{\prime}_{k}\})$ . This proves the lemma. $\hfill\blacktriangleleft$

The algorithm, denoted as Approx7, for producing a complete EF1 allocation for Case 2, is depicted in Algorithm 7, which utilizes the three procedures introduced in the above. When Algo4 terminates at $k_{1}=k<k_{2}$ , the returned partial allocation is $\mathcal{A}=(K\setminus g^{\prime}_{k},A_{2},\{g^{\prime}_{k}\})$ where $A_{2}\subset M\setminus K$ , which is completed by calling the Envy Cycle Elimination (ECE) algorithm to assign the rest of the items, i.e., $g^{\prime}_{k+1},\ldots,g^{\prime}_{k_{2}}$ .

Algorithm 7 Approx7 for a complete EF1 allocation.

Input: The critical set $K$ for item $g_{i}$ satisfying $\max_{g\in K}u_{1}(g)<\frac{1}{2}u_{1}(K)$ , the new item order $S^{\prime}$ in which $g^{\prime}_{k}\neq g_{i}$ , and $u_{3}(g^{\prime}_{k})>u_{3}(M\setminus K)$ .

Output: A complete EF1 allocation.

Lemma 18.

Approx7 produces a complete EF1 allocation.

Proof.

If the procedure Algo4 terminates at $k_{1}=k<k_{2}$ , then since the returned partial allocation is EF1 by Lemma 15, the ECE algorithm continues from there to produce a complete EF1 allocation [9].

If the procedure Algo4 terminates at $k_{1}<k=k_{2}$ , then the final allocation is returned by Algo6 and by Lemma 17 is complete and EF1. $\hfill\blacktriangleleft$

Theorem 19.

Given the critical set $K$ for the item $g^{*}$ produced by the procedure Algo2 satisfying $\max_{g\in K}u_{1}(g)<\frac{1}{2}u_{1}(K)$ , $k=|K|$ , the new item order $S^{\prime}$ in which $g^{\prime}_{k}\neq g^{*}$ , and $u_{3}(g^{\prime}_{k})>u_{3}(M\setminus K)$ , Approx7 constructs a complete EF1 allocation with its total utility at least $\frac{1}{2}OPT$ .

Proof.

By Lemma 18 the final allocation is complete and EF1.

If the procedure Algo4 terminates at $k_{1}=k<k_{2}$ , then $SOL\geq u_{1}(K\setminus g^{\prime}_{k})+u_{3}(g^{\prime}_{k})$ . Since $u_{1}(g^{\prime}_{k})<\frac{1}{2}u_{1}(K)$ and $u_{3}(g^{\prime}_{k})>u_{3}(M\setminus K)$ , the total utility is greater than $\frac{1}{2}u_{1}(K)+u_{3}(M\setminus K)\geq\frac{1}{2}OPT$ where the last inequality holds by Lemma 8.

If the procedure Algo4 terminates at $k_{1}<k=k_{2}$ , then let $\mathcal{A}=(A_{1},A_{2},\{g^{\prime}_{k}\})$ denote the allocation returned by the procedure Algo5, in which $A_{1}\subseteq K\setminus g^{\prime}_{k}$ and $A_{2}\subset M\setminus g^{\prime}_{k}$ . We distinguish to whom $g^{\prime}_{k-1}$ is allocated.

If $g^{\prime}_{k-1}\in A_{1}$ , then $A_{1}=K\setminus g^{\prime}_{k}$ , and the above argument for the first termination condition applies too, so that $SOL>\frac{1}{2}OPT$ , by noting that the procedure Algo6 never reduces the total utility.

If $g^{\prime}_{k-1}\in A_{2}$ , then $(M\setminus K)\cup\{g^{\prime}_{k-1},g^{\prime}_{k}\}\subseteq A_{2}\cup A_{3}$ . By $\sum_{j=1}^{k-1}u_{3}(g^{\prime}_{j})<\frac{1}{3}u_{3}(M\setminus g^{*})+u_{3}% (g^{*})$ from Remark 11, $u_{3}(A_{2})+u_{3}(A_{3})>\frac{2}{3}u_{3}(M\setminus g^{*})$ . When $u_{1}(A_{1})<u_{1}(A_{2})$ , the procedure Algo6 outputs $\mathcal{A}$ or $(A_{2},A_{1},A_{3})$ with a larger total utility, which is

SOL\geq\frac{1}{2}u_{1}(A_{1}\cup A_{2})+\frac{1}{2}u_{3}(A_{1}\cup A_{2})+u_{% 3}(A_{3})\geq\frac{1}{2}u_{1}(M\setminus g^{\prime}_{k})+\frac{1}{2}u_{3}(M).

When $u_{1}(A_{1})\geq u_{1}(A_{2})$ , $\mathcal{A}$ is the final allocation with its total utility

SOL\geq\frac{1}{2}u_{1}(A_{1}\cup A_{2})+u_{3}(A_{2})+u_{3}(A_{3})>\frac{1}{2}% u_{1}(M\setminus g^{\prime}_{k})+\frac{2}{3}u_{3}(M\setminus g^{*}).

Noting from $g^{\prime}_{k}\neq g^{*}$ , $u_{3}(g^{\prime}_{k})>\frac{1}{3}u_{3}(M\setminus g^{*})$ in Eq. (3), and $u_{3}(A^{*}_{1}\setminus g^{*})\leq\frac{1}{3}u_{3}(M\setminus g^{*})$ in Lemma 6, we have $g^{\prime}_{k}\notin A^{*}_{1}$ . Therefore, $u_{1}(A^{*}_{1})\leq u_{1}(M\setminus g^{\prime}_{k})$ and then since $g^{*}\in A^{*}_{1}$ ,

SOL\geq\frac{1}{2}u_{1}(M\setminus g^{\prime}_{k})+\min\{\frac{1}{2}u_{3}(M),% \frac{2}{3}u_{3}(M\setminus g^{*})\}\geq\frac{1}{2}u_{1}(A^{*}_{1})+\frac{1}{2% }u_{3}(A^{*}_{2}\cup A^{*}_{3})=\frac{1}{2}OPT.

This proves the theorem. $\hfill\blacktriangleleft$

3.4 Case 3: $\max_{g\in K}u_{1}(g)<\frac{1}{2}u_{1}(K)$ and $u_{3}(g^{\prime}_{k})\leq u_{3}(M\setminus K)$

Recall that $K$ is the critical set of item $g_{i}$ produced by the procedure Algo2. The same as in Case 2, here we also have $k=|K|\geq 3$ and we work with the new item order $S^{\prime}$ such that $K=\{g^{\prime}_{1},\ldots,g^{\prime}_{k}\}$ , $S^{\prime}\setminus g^{\prime}_{k-1}$ is regular, and $g^{\prime}_{k}\neq g_{i}$ . Note the difference from Case 2 that, here we have $u_{3}(g^{\prime}_{k})\leq u_{3}(M\setminus K)$ . We design an algorithm denoted Approx9 for this case to construct a complete EF1 allocation, summarized in the following. Due to space limit, the complete design and analysis for Case 3 is in the full arXiv version [10].

Theorem 20.

Given the critical set $K$ for the item $g^{*}$ produced by the procedure Algo2 satisfying $\max_{g\in K}u_{1}(g)<\frac{1}{2}u_{1}(K)$ , $k=|K|$ , the new item order $S^{\prime}$ in which $g^{\prime}_{k}\neq g^{*}$ , and $u_{3}(g^{\prime}_{k})\leq u_{3}(M\setminus K)$ , Approx9 constructs a complete EF1 allocation with its total utility at least $\frac{1}{2}OPT$ .

3.5 An instance to show the tightness of ratio $2$

We provide an instance below to show that the approximation ratio $2$ of the combination of the three algorithms, Approx3, Approx7 and Approx9, for the case of three agents with two unnormalized utility functions is tight. In this instance there are only five items in the order $\rho(g_{1})>\rho(g_{2})>\rho(g_{3})>1>\rho(g_{4})=\rho(g_{5})$ , with their values to the three agents listed as follows, where $\epsilon>0$ is a small value:

	$g_{1}$	$g_{2}$	$g_{3}$	$g_{4}$	$g_{5}$
$a_{1}$	$\epsilon$	$1$	$1$	$0$	$0$
$a_{2},a_{3}$	$0$	$\epsilon$	$2\epsilon$	$\epsilon$	$\epsilon$

We continue to use the same notations introduced in Section 3. One sees that $X=\{g_{1},g_{2},g_{3}\}$ , and thus $\mathcal{A}^{*}=(\{g_{1},g_{2},g_{3}\},\{g_{4}\},\{g_{5}\})$ is an optimal EF1 allocation of total utility $2+3\epsilon$ .

For each of $g_{1}$ and $g_{2}$ , $u_{3}(X\setminus g_{i})>\frac{1}{3}u_{3}(M\setminus g_{i})\geq\frac{4}{3}\epsilon$ ; the critical set produced by Algo2 is $K=\{g_{1},g_{2},g_{3}\}$ . One can verify that $\max_{g\in K}u_{1}(g)<\frac{1}{2}u_{1}(K)$ , and the new item order is the same as the original preference order. Since $u_{3}(g_{3})=u_{3}(M\setminus K)$ , it falls into Case 3. In this case, Algo8 starts with the allocation $(\{g_{1}\},\{g_{3}\},\emptyset)$ : In the first iteration, $a_{1}$ is not envied by $a_{2}$ or $a_{3}$ , the allocation is updated to $(\{g_{1},g_{2}\},\{g_{3}\},\emptyset)$ and the procedure terminates with $k_{1}>k_{2}$ . Since $(\{g_{1},g_{2}\},\{g_{3}\},\emptyset)$ is well-defined with permutation $(1,2,3)$ , Approx3 calls the RR algorithm that assigns $g_{4}$ and $g_{5}$ one to each of $a_{3}$ and $a_{2}$ , achieving the final allocation either $(\{g_{1},g_{2}\},\{g_{3},g_{5}\},\{g_{4}\})$ or $(\{g_{1},g_{2}\},\{g_{3},g_{4}\},\{g_{5}\})$ of total utility $1+5\epsilon$ .

For $g_{3}$ , $u_{3}(X\setminus g_{3})=\frac{1}{3}u_{3}(M\setminus g_{3})=\epsilon$ ; the critical set produced by Algo2 is also $K=\{g_{1},g_{2},g_{3}\}$ , and the new item order is $S^{\prime}=\langle g_{1},g_{3},g_{2},g_{4},g_{5}\rangle$ . Since $u_{3}(g_{2})<u_{3}(M\setminus K)$ , it falls into Case 3 too. In this case, Algo8 starts with the allocation $(\{g_{1}\},\{g_{2}\},\emptyset)$ : In the first iteration, $a_{1}$ is not envied by $a_{2}$ or $a_{3}$ , the allocation is updated to $(\{g_{1},g_{3}\},\{g_{2}\},\emptyset)$ and the procedure terminates with $k_{1}>k_{2}$ . Since $(\{g_{1},g_{3}\},\{g_{2}\},\emptyset)$ is well-defined with permutation $(1,2,3)$ , Approx3 calls the RR algorithm that assigns $g_{4}$ and $g_{5}$ one to each of $a_{3}$ and $a_{2}$ , achieving the final allocation either $(\{g_{1},g_{3}\},\{g_{2},g_{5}\},\{g_{4}\})$ or $(\{g_{1},g_{3}\},\{g_{2},g_{4}\},\{g_{5}\})$ of total utility $1+4\epsilon$ .

For $g_{4}$ ( $g_{5}$ can be identically discussed), $u_{3}(X\setminus g_{4})=3\epsilon>\frac{1}{3}u_{3}(M\setminus g_{4})=\frac{4}{% 3}\epsilon$ ; the critical set produced by Algo2 is $K=\{g_{1},g_{2},g_{3},g_{4}\}$ , and the new item order is $S^{\prime}=\langle g_{1},g_{2},g_{4},g_{3},g_{5}\rangle$ . Since $u_{3}(g_{3})>u_{3}(M\setminus K)$ , it falls into Case 2. In this case, Algo4 starts with the allocation $(\{g_{1}\},\emptyset,\{g_{3}\})$ : In the first iteration, $a_{1}$ is not envied by $a_{2}$ , the allocation is updated to $(\{g_{1},g_{2}\},\emptyset,\{g_{3}\})$ ; in the second iteration, $a_{1}$ is envied by $a_{2}$ , the allocation is updated to $(\{g_{1},g_{2}\},\{g_{5}\},\{g_{3}\})$ , and the procedure terminates with $k_{1}<k=k_{2}$ . Since in $(\{g_{1},g_{2}\},\{g_{5}\},\{g_{3}\})$ $a_{1}$ is not envied, Algo5 assigned $g_{4}$ to $a_{1}$ , achieving the complete allocation $(\{g_{1},g_{2},g_{4}\},\{g_{5}\},\{g_{3}\})$ . Lastly, Algo6 confirms the final allocation is $(\{g_{1},g_{2},g_{4}\},\{g_{5}\},\{g_{3}\})$ , of total utility $1+4\epsilon$ .

Therefore, we have $SOL\leq\max\{1+4\epsilon,1+5\epsilon\}=1+5\epsilon$ . It follows that $OPT/SOL\geq(2+3\epsilon)/(1+5\epsilon)=2-7\epsilon/(1+5\epsilon)\to 2$ , when $\epsilon$ tends to $0$ .

4 A $\frac{5}{3}$ -approximation for three agents with normalized functions

Recall that the algorithm Approx1 is a $2$ -approximation for $n$ agents with normalized functions. In this section, we consider the special case where $n=3$ , and again assume w.l.o.g. that agent $a_{1}$ uses the utility function $u_{1}(\cdot)$ and $a_{2}$ and $a_{3}$ use $u_{3}(\cdot)$ . We continue to assume the items are given in the preference order $\rho(g_{1})\geq\rho(g_{2})\geq\ldots\geq\rho(g_{m})$ .

We also continue to use some notations and definitions introduced earlier, such as the sets $X=\{g\in M:u_{1}(g)\geq u_{3}(g)\}$ and $Y=M\setminus X$ defined in Eq. (1), a good allocation defined in Definition 2, and so on. Additionally, for any subset $A\subseteq M$ , we define the quantity

\Delta(A)=u_{1}(A)-u_{3}(A).

(4)

Since now $u_{1}(M)=u_{3}(M)=1$ , we have $\Delta(X)+\Delta(Y)=0$ and

OPT\leq u_{1}(X)+u_{3}(Y)=u_{1}(X)-u_{3}(X)+u_{3}(M)=\Delta(X)+1=1-\Delta(Y).

(5)

In the rest of the section we distinguish two cases on $\max_{g\in X}u_{1}(g)$ , the most value of a single item in $X$ to agent $a_{1}$ , and we design two different, but similar, algorithms, respectively.

4.1 Case 1: $\max_{g\in X}u_{1}(g)\leq\frac{1}{3}$

The design idea of our algorithm Approx10 is similar to Approx1, with a change that, after all the items of $X$ have been allocated, i.e., both to-be-allocated items $g_{k_{1}}$ and $g_{k_{2}}$ are in $Y$ , agent $a_{t}$ has the priority to receive $g_{k_{2}}$ if it is not envied by $a_{1}$ . The detailed description of the algorithm Approx10 is presented in Algorithm 8.

Algorithm 8 Approx10 for three agents with normalized utility functions.

Input: Three agents of two types and a set of $m$ indivisible items $\rho(g_{1})\geq\rho(g_{2})\geq\ldots\geq\rho(g_{m})$ , where $\max_{g\in X}u_{1}(g)\leq\frac{1}{3}$ .

Output: A complete EF1 allocation.

Lemma 21.

Approx10 produces a good, complete and EF1 allocation.

Proof.

The returned allocation by Approx10 is clearly complete from the while-loop termination condition. We prove that at the end of each iteration of the while-loop in the algorithm, the updated allocation is good and EF1, similar to Lemma 4. Note that the initial empty allocation is trivially good and EF1.

Assume that at the beginning of the iteration the allocation denoted as $\mathcal{A}=(A_{1},A_{2},A_{3})$ is good and EF1; note that the to-be-allocated items are $g_{k_{1}}$ and $g_{k_{2}}$ with $k_{1}\leq k_{2}$ .

Consider the case where $k_{1}>|X|$ and $a_{t}$ is not envied by $a_{1}$ (we intentionally pick this case to prove, the other three cases are symmetric), in which the algorithm updates $A_{1}$ to $A_{t}\cup\{g_{k_{2}}\}$ . By the description of Approx10, $A_{1}=\{g_{1},\ldots,g_{k_{1}-1}\}$ and $A_{i}\subseteq\{g_{k_{2}+1},\ldots,g_{m}\}$ for $i=2,3$ . By Definitions 1 and 2 and $k_{1}\leq k_{2}$ , $A_{1}\prec A_{i}\cup\{g_{k_{2}}\}$ for $i=2,3$ , and thus the updated allocation is good.

Since at the beginning of the iteration $a_{t}$ is not envied by $a_{1}$ , $u_{1}(A_{1})\geq u_{3}(A_{t})$ . Also, by the definition of $t$ , $u_{3}(A_{i})\geq u_{3}(A_{t})$ for the third agent $a_{i}$ . That is, no agent envies $a_{t}$ in the allocation $\mathcal{A}$ , and thus does not strongly envy $a_{t}$ in the updated allocation (by removing the item $g_{k_{2}}$ , if necessary). Note that in this iteration only $a_{t}$ gets the item $g_{k_{2}}$ . Therefore, the updated allocation is EF1. $\hfill\blacktriangleleft$

Let us examine one scenario of the final allocation returned by Approx10 in the next lemma, and leave the other to the main Theorem 23.

Lemma 22.

In the final allocation $\mathcal{A}=(A_{1},A_{2},A_{3})$ returned by Approx10, if $X\subseteq A_{1}$ , then $SOL\geq\frac{2}{3}OPT$ .

Proof.

If $A_{1}=X$ , then $\mathcal{A}$ is optimal, i.e., $SOL=OPT$ .

Below we consider the scenario where $a_{1}$ receives some items from $Y$ . This means when Approx10 terminates, $k_{1}>|X|+1$ and $A_{1}=\{g_{1},\ldots,g_{k_{1}-1}\}$ . Let $Y_{1}=\{g_{|X|+1},\ldots,g_{k_{1}-1}\}$ , that is, $A_{1}=X\cup Y_{1}$ .

We claim $\min\{\Delta(X),-\Delta(Y_{1})\}\leq\frac{1}{2}$ . Assume to the contrary, then $u_{1}(X)\geq\Delta(X)>\frac{1}{2}$ and $u_{3}(Y_{1})\geq-\Delta(Y_{1})>\frac{1}{2}$ . Consider the iteration where $a_{1}$ is allocated with the last item $g_{k_{1}-1}$ . Since at the beginning of the iteration the allocation is good, by Lemma 3, $a_{1}$ and $a_{2}$ do not envy each other, so do $a_{1}$ and $a_{3}$ . From $g_{k_{1}-1}\in Y$ and Lines 9–13 in the algorithm description, $a_{t}$ is envied by $a_{1}$ , and thus $u_{1}(A_{1}\setminus g_{k_{1}-1})<u_{1}(A_{2}\cup A_{3})$ . It follows from $A_{2}\cup A_{3}=Y\setminus Y_{1}$ and Eq. (1) that

u_{1}(X)<u_{1}(A_{2}\cup A_{3})<u_{3}(A_{2}\cup A_{3})=u_{3}(Y)-u_{3}(Y_{1})<1% -\frac{1}{2}=\frac{1}{2},\mbox{ a contradiction.}

Since $A_{2}\cup A_{3}\subset Y$ , we have $u_{1}(A_{2}\cup A_{3})<u_{3}(A_{2}\cup A_{3})$ , and therefore $SOL=u_{1}(A_{1})+u_{3}(A_{2}\cup A_{3})>u_{1}(A_{1})+u_{1}(A_{2}\cup A_{3})=1$ .

Using the claimed $\min\{\Delta(X),-\Delta(Y_{1})\}\leq\frac{1}{2}$ , if $\Delta(X)\leq\frac{1}{2}$ , then by Eq. (5), $OPT\leq\frac{3}{2}\leq\frac{3}{2}\cdot SOL$ ; if $\Delta(X)>\frac{1}{2}$ , then $-\Delta(Y_{1})\leq\frac{1}{2}<\Delta(X)$ , and thus $SOL=u_{1}(A_{1})-u_{3}(A_{1})+u_{3}(M)=\Delta(X)+\Delta(Y_{1})+1>\frac{2}{3}(% \Delta(X)+1)\geq\frac{2}{3}OPT$ , where the last inequality is by Eq. (5). This proves the lemma. $\hfill\blacktriangleleft$

Theorem 23.

If $\max_{g\in X}u_{1}(g)\leq\frac{1}{3}$ , then Approx10 produces a complete EF1 allocation with its total utility $SOL\geq\frac{3}{5}OPT$ .

Proof.

Lemma 21 states that the final allocation $\mathcal{A}=(A_{1},A_{2},A_{3})$ returned by the algorithm is complete and EF1. If $X\subseteq A_{1}$ , then by Lemma 22 the total utility of $\mathcal{A}$ is at least $\frac{2}{3}OPT$ .

We next consider the other scenario where $A_{1}\subset X$ , i.e., the algorithm Approx10 terminates with $k_{1}\leq|X|$ . Let $X_{1}=\{g_{k_{1}},\ldots,g_{|X|}\}$ , then $A_{1}=\{g_{1},\ldots,g_{k_{1}-1}\}=X\setminus X_{1}$ and $A_{2}\cup A_{3}=X_{1}\cup Y$ .

We claim that $\Delta(X_{1})\leq\frac{2}{3}$ , and prove it by contradiction to assume $\Delta(X_{1})>\frac{2}{3}$ . It follows that $u_{1}(X_{1})>\frac{2}{3}$ and thus $u_{1}(A_{1})\leq u_{1}(M\setminus X_{1})<\frac{1}{3}$ .

From Lines 4–8 in the description of the algorithm, the item $g_{k_{1}}$ is assigned to agent $a_{t}$ in the last iteration of the while-loop (in which $k_{2}=k_{1}$ at the beginning of the iteration and $k_{2}$ is decremented afterwards leading to the termination condition $k_{2}<k_{1}$ ). That is, $g_{k_{1}}$ is the last item received by $a_{t}$ . Denote the other agent as $a_{i}$ , i.e., $\{t,i\}=\{2,3\}$ . Since $a_{1}$ is envied at the beginning of the iteration, $a_{1}$ is envied by $a_{t}$ ; further because the allocation is good, $a_{1}$ does not envy $a_{t}$ . To summarize,

u_{3}(A_{t}\setminus g_{k_{1}})\leq u_{3}(A_{i}),\mbox{ }u_{3}(A_{t}\setminus g% _{k_{1}})<u_{3}(A_{1}),\mbox{ and }u_{1}(A_{1})\geq u_{1}(A_{t}\setminus g_{k_% {1}}).

(6)

It follows from $A_{1}\subseteq X$ that

u_{3}(A_{t}\setminus g_{k_{1}})<u_{3}(A_{1})\leq u_{1}(A_{1})<\frac{1}{3}.

(7)

One sees that if agent $a_{i}$ also receives some items from $X_{1}$ , then the above argument applies too for the last item $a_{i}$ receives, denoted as $g_{\ell}$ , such that Eq. (7) holds, i.e., $u_{3}(A_{i}\setminus g_{\ell})<\frac{1}{3}$ .

Subsequently, if $A_{2}\cap X_{1}\neq\emptyset$ and $A_{3}\cap X_{1}\neq\emptyset$ , then

\Delta(X_{1})\leq\Delta(X)=-\Delta(Y)\leq u_{3}(A_{t}\setminus g_{k_{1}})+u_{3% }(A_{i}\setminus g_{\ell})<\frac{2}{3},\mbox{ a contradiction.}

If $X_{1}\subseteq A_{t}$ , then by Eq. (6),

u_{1}(g_{k_{1}})\geq u_{1}(A_{t})-u_{1}(A_{1})\geq u_{1}(X_{1})-u_{1}(A_{1})>% \frac{1}{3},\mbox{ contradicting to $\max_{g\in X}u_{1}(g)\leq\frac{1}{3}$.}

We have thus proved the claim that $\Delta(X_{1})\leq\frac{2}{3}$ .

We linearly combine $\Delta(X_{1})\leq\frac{2}{3}$ and $\Delta(X_{1})\leq\Delta(X)$ to have $\Delta(X_{1})\leq\frac{3}{5}\cdot\frac{2}{3}+\frac{2}{5}\cdot\Delta(X)=\frac{2% }{5}+\frac{2}{5}\Delta(X)$ , and thus by Eq. (5)

SOL=u_{1}(X\setminus X_{1})+u_{3}(X_{1}\cup Y)=1+\Delta(X)-\Delta(X_{1})\geq% \frac{3}{5}(1+\Delta(X))\geq\frac{3}{5}OPT.

This proves the theorem. $\hfill\blacktriangleleft$

4.2 Case 2: $\max_{g\in X}u_{1}(g)>\frac{1}{3}$

In this case, we let $g^{*}=\arg\max_{g\in X}u_{1}(g)$ ; thus $u_{1}(g^{*})>\frac{1}{3}$ , which is so big that it is assigned to agent $a_{1}$ immediately. On the other hand, we can use $g^{*}$ to bound $O P T$ as follows:

OPT\leq u_{1}(X)+u_{3}(Y)\leq u_{1}(X)+u_{3}(M)-u_{3}(g^{*})\leq 2-u_{3}(g^{*}% )<\frac{5}{3}+\Delta(g^{*}).

(8)

Our algorithm for this case is very similar to Approx10, with two changes: One is the starting allocation set to be $(\{g^{*}\},\emptyset,\emptyset)$ , and the other is, when $k_{2}=|X|$ , the while-loop terminates and the algorithm switches to the Envy-Cycle Elimination (ECE) algorithm to assign the rest of items. The detailed description of the algorithm, denoted as Approx11, is presented in Algorithm 9.

Algorithm 9 Approx11 for three agents with normalized utility functions.

Input: Three agents of two types and a set of $m$ indivisible items $\rho(g_{1})\geq\rho(g_{2})\geq\ldots\geq\rho(g_{m})$ , where $g^{*}=\arg\max_{g\in X}u_{1}(g)$ and $u_{1}(g^{*})>\frac{1}{3}$ .

Output: A complete EF1 allocation.

Theorem 24.

If $\max_{g\in X}u_{1}(g)>\frac{1}{3}$ , then Approx11 produces a complete EF1 allocation with its total utility $SOL\geq\frac{3}{5}OPT$ , and the approximation ratio $\frac{3}{5}$ is tight.

Proof.

We distinguish the two termination condition of the while-loop in Approx11.

In the first scenario, the while-loop terminates at $k_{1}>k_{2}$ , that is, all the items are assigned and $k_{2}\geq|X|$ implying $X\subseteq A_{1}$ in the returned allocation $\mathcal{A}=(A_{1},A_{2},A_{3})$ . Note that the while-loop body is the same as the while-loop body in Approx10. It follows from Lemma 21 that $\mathcal{A}$ is good, complete and EF1, and from Lemma 22 that its total utility is $SOL\geq\frac{2}{3}OPT$ .

In the other scenario, the while-loop terminates at $k_{1}\leq k_{2}=|X|$ , that is, all the items of $Y$ have been assigned to $a_{2}$ and $a_{3}$ (i.e., $Y\subseteq A_{2}\cup A_{3}$ ), and the unassigned items are $g_{k_{1}},\ldots,g_{k_{2}}$ excluding $g^{*}$ . By Lemma 21, the achieved allocation $\mathcal{A}$ is good and EF1. Since $g^{*}\in A_{1}$ , we have $\Delta(A_{1})\geq\Delta(g^{*})$ .

We claim that the ECE algorithm does not decrease $\Delta(A_{1})$ . To prove the claim, we assume in an iteration of the ECE algorithm, with the allocation $\mathcal{A}=(A_{1},A_{2},A_{3})$ at the beginning, agent $a_{1}$ gets the bundle $A_{2}$ or $A_{3}$ due to the existence of an envy cycle. Further assume w.l.o.g. that $a_{1}$ gets bundle $A_{2}$ , which means $a_{1}$ envies $a_{2}$ and the envy cycle is either $(1\to 2\to 3\to 1)$ or $(1\to 2\to 1)$ . Either way, $u_{1}(A_{1})<u_{1}(A_{2})$ and $u_{3}(A_{2})(<u_{3}(A_{3}))<u_{3}(A_{1})$ . Therefore, $\Delta(A_{1})<\Delta(A_{2})$ . This proves the claim.

The final allocation $\mathcal{A}=(A_{1},A_{2},A_{3})$ returned from the ECE algorithm has its total utility

SOL=u_{1}(A_{1})+u_{3}(A_{2}\cup A_{3})\geq\Delta(A_{1})+u_{3}(M)\geq\Delta(g^% {*})+1>\frac{3}{5}OPT,

where the last inequality is by Eq. (8). We thus prove that the approximation ratio of Approx11 is at least $\frac{3}{5}$ .

We next provide an instance below to show that this approximation ratio is tight. In this instance, there are five items given in the order $\rho(g_{1})>\rho(g_{2})>\rho(g_{3})>1>\rho(g_{4})=\rho(g_{5})$ , with their values to the three agents listed as follows, where $\epsilon>0$ is a small value:

	$g_{1}$	$g_{2}$	$g_{3}$	$g_{4}$	$g_{5}$
$a_{1}$	$\frac{1}{3}$	$\frac{1}{3}-\epsilon$	$\frac{1}{3}+\epsilon$	$0$	$0$
$a_{2},a_{3}$	$\epsilon$	$\epsilon$	$\frac{1}{3}$	$\frac{1}{3}-\epsilon$	$\frac{1}{3}-\epsilon$

One sees that the instance is normalized, $X=\{g_{1},g_{2},g_{3}\}$ , and $A^{*}=(\{g_{1},g_{2}\},\{g_{3},g_{4}\},\{g_{5}\})$ is an optimal EF1 allocation of total utility $\frac{5}{3}-3\epsilon$ .

Since $u_{1}(g_{3})>\frac{1}{3}$ , Approx11 is executed which starts with the allocation $(\{g_{3}\},\emptyset,\emptyset)$ : In the first iteration, $a_{1}$ is envied by $a_{2}$ and $a_{3}$ , and the allocation is updated to $(\{g_{3}\},\emptyset,\{g_{5}\})$ or $(\{g_{3}\},\{g_{5}\},\emptyset)$ ; in the second iteration, $a_{1}$ and $a_{3}$ (resp., $a_{1}$ and $a_{2}$ ) are envied by $a_{2}$ (resp., $a_{3}$ ), and the allocation is updated to $\mathcal{A}=(\{g_{3}\},\{g_{4}\},\{g_{5}\})$ ; the procedure terminates with $k_{2}=|X|=3$ .

Next, the ECE algorithm is called on $\mathcal{A}$ to continue to assign the items $g_{1}$ and $g_{2}$ : In the first iteration, since in $(\{g_{3}\},\{g_{4}\},\{g_{5}\})$ only $a_{1}$ is still envied by $a_{2}$ and $a_{3}$ , $a_{2}$ and $a_{3}$ are not envied, the ECE algorithm assigns $g_{1}$ to $a_{2}$ (or to $a_{3}$ , symmetrically) resulting in the updated allocation $(\{g_{3}\},\{g_{1},g_{4}\},\{g_{5}\})$ ; in the second iteration, the ECE algorithm assigns the last item $g_{2}$ to $a_{3}$ , ending at the complete allocation $\mathcal{A}=(\{g_{3}\},\{g_{1},g_{4}\},\{g_{2},g_{5}\})$ . This final allocation $\mathcal{A}=(\{g_{3}\},\{g_{1},g_{4}\},\{g_{2},g_{5}\})$ has total utility $1$ . Therefore, we have $OPT/SOL=(\frac{5}{3}-3\epsilon)/1\to\frac{5}{3}$ , when $\epsilon$ tends to $0$ . $\hfill\blacktriangleleft$

5 Conclusion

Fair division of indivisible goods is an interesting problem which has received a lot of studies, from multiple research communities including artificial intelligence and theoretical computer science. Finding an EF1 allocation to maximize the utilitarian social welfare from the perspective of approximation algorithms emerges most recently. Despite EF1 being one of the most simplest fairness criteria, the design and analysis of approximation algorithms for this problem in the general case seems challenging [4, 6]. In this paper, we focused on the special case where agents are of only two types, and we hope our work may shed lights on and inspire more studies for the general case. For this special case, we presented a $2$ -approximation algorithm for any number of agents with normalized utility functions; by the lower bound of $\frac{4n}{3n+1}$ from [6], our result shows the problem in this special case is APX-complete. When there are only three agents, we presented an improved $\frac{5}{3}$ -approximation algorithm. When there are only three agents but the utility functions are unnormalized, we presented a tight $2$ -approximation algorithm which is the best possible by the lower bound of $\frac{1+\sqrt{4n-3}}{2}$ from [6]. In all three algorithms, we demonstrate the use of the item preference (Definition 1) order, which can be explored further for improved algorithms.

We remark that the lower bound of $\frac{4n}{3n+1}$ on the approximability in [6] is proven for a more restricted case where the two utility functions are normalized, agent $a_{1}$ uses a utility function and all the other agents use the other function. It would be interesting to narrow the gap for either the special case we study or this more restricted case; we expect some improved lower bounds or some approximation ratios as functions in $n_{1}$ and $n_{2}$ , where $n_{1}$ agents use a common utility function and the other $n_{2}=n-n_{1}$ use the second utility function.

References

[1] G. Amanatidis, H. Aziz, G. Birmpas, A. Filos-Ratsikas, B. Li, H. Moulin, A. A. Voudouris, and X. Wu. Fair division of indivisible goods: Recent progress and open questions. Artificial Intelligence, 322:Article 103965, 2023.
[2] G. Amanatidis, G. Birmpas, A. Filos-Ratsikas, and A. Voudouris. Fair division of indivisible goods: A survey. In Proceedings of IJCAI 2022, pages 5385–5393, 2022.
[3] H. Aziz, X. Huang, N. Mattei, and E. Segal-Halevi. Computing welfare-maximizing fair allocations of indivisible goods. European Journal of Operational Research, 307:773–784, 2023. doi:10.1016/J.EJOR.2022.10.013.
[4] S. Barman, U. Bhaskar, and N. Shah. Optimal bounds on the price of fairness for indivisible goods. In Proceedings of WINE 2020, pages 356–369, 2020.
[5] X. Bei, X. Lu, P. Manurangesi, and W. Suksompong. The price of fairness for indivisible goods. Theory of Computing Systems, 65:1069–1093, 2021. doi:10.1007/S00224-021-10039-8.
[6] X. Bu, Z. Li, S. Liu, J. Song, and B. Tao. Approximability landscape of welfare maximization within fair allocations. In Proceedings of EC 2025, pages 412–440, 2025.
[7] E. Budish. The combinatorial assignment problem: Approximate competitive equilibrium from equal incomes. Journal of Political Economy, 119:1061–1103, 2011.
[8] I. Caragiannis, D. Kurokawa, H. Moulin, A. Procaccia, N. Shah, and J. Wang. The unreasonable fairness of maximum Nash welfare. ACM Transactions on Economics and Computation, 7:12:1–12:32, 2019. doi:10.1145/3355902.
[9] R. Lipton, E. Markakis, E. Mossel, and A. Saberi. On approximately fair allocations of indivisible goods. In Proceedings of EC 2004, pages 125–131, 2004.
[10] J. Ma, Y. Chen, G. Chen, M. Gong, G. Lin, and A. Zhang. Maximizing social welfare among EF1 allocations at the presence of two types of agents. CoRR, 2025. arXiv:2509.09641.
[11] H. Steinhaus. Sur la division pragmatique. Econometrica, 17:315–319, 1949.
[12] H. Varian. Equity, envy and efficiency. Journal of Economic Theory, 9:63–91, 1974.

[bib.bib1] [1] G. Amanatidis, H. Aziz, G. Birmpas, A. Filos-Ratsikas, B. Li, H. Moulin, A. A. Voudouris, and X. Wu. Fair division of indivisible goods: Recent progress and open questions. Artificial Intelligence, 322:Article 103965, 2023.

[bib.bib2] [2] G. Amanatidis, G. Birmpas, A. Filos-Ratsikas, and A. Voudouris. Fair division of indivisible goods: A survey. In Proceedings of IJCAI 2022, pages 5385–5393, 2022.

[bib.bib3] [3] H. Aziz, X. Huang, N. Mattei, and E. Segal-Halevi. Computing welfare-maximizing fair allocations of indivisible goods. European Journal of Operational Research, 307:773–784, 2023. doi:10.1016/J.EJOR.2022.10.013.

[bib.bib4] [4] S. Barman, U. Bhaskar, and N. Shah. Optimal bounds on the price of fairness for indivisible goods. In Proceedings of WINE 2020, pages 356–369, 2020.

[bib.bib5] [5] X. Bei, X. Lu, P. Manurangesi, and W. Suksompong. The price of fairness for indivisible goods. Theory of Computing Systems, 65:1069–1093, 2021. doi:10.1007/S00224-021-10039-8.

[bib.bib6] [6] X. Bu, Z. Li, S. Liu, J. Song, and B. Tao. Approximability landscape of welfare maximization within fair allocations. In Proceedings of EC 2025, pages 412–440, 2025.

[bib.bib7] [7] E. Budish. The combinatorial assignment problem: Approximate competitive equilibrium from equal incomes. Journal of Political Economy, 119:1061–1103, 2011.

[bib.bib8] [8] I. Caragiannis, D. Kurokawa, H. Moulin, A. Procaccia, N. Shah, and J. Wang. The unreasonable fairness of maximum Nash welfare. ACM Transactions on Economics and Computation, 7:12:1–12:32, 2019. doi:10.1145/3355902.

[bib.bib9] [9] R. Lipton, E. Markakis, E. Mossel, and A. Saberi. On approximately fair allocations of indivisible goods. In Proceedings of EC 2004, pages 125–131, 2004.

[bib.bib10] [10] J. Ma, Y. Chen, G. Chen, M. Gong, G. Lin, and A. Zhang. Maximizing social welfare among EF1 allocations at the presence of two types of agents. CoRR, 2025. arXiv:2509.09641.

[bib.bib11] [11] H. Steinhaus. Sur la division pragmatique. Econometrica, 17:315–319, 1949.

[bib.bib12] [12] H. Varian. Equity, envy and efficiency. Journal of Economic Theory, 9:63–91, 1974.

Maximizing Social Welfare Among EF1 Allocations at the Presence of Two Types of Agents

Abstract

Keywords and phrases:

Copyright and License:

2012 ACM Subject Classification:

Funding:

Related Version:

DOI:

Event:

Editors:

Series and Publisher:

1 Introduction

1.1 Related work

1.2 Our contribution and organization of the paper

2 A 𝟐-approximation for normalized functions

Definition 1.

Definition 2.

Lemma 3.

Proof.

Lemma 4.

Proof.

Theorem 5.

Proof.

3 A 𝟐-approximation for three agents with unnormalized functions

Lemma 6.

Proof.

Definition 7.

Lemma 8.

Proof.

Lemma 9.

Proof.

3.1 Producing a critical set for every item

Lemma 10.

Proof.

▶ Remark 11.

Proof.

3.2 Case 1: 𝐦𝐚𝐱𝒈∈𝑲⁡𝒖𝟏⁢(𝒈)≥𝟏𝟐⁢𝒖𝟏⁢(𝑲)

Definition 12.

Lemma 13.

Proof.

Theorem 14.

Proof.

3.3 Case 2: 𝐦𝐚𝐱𝒈∈𝑲⁡𝒖𝟏⁢(𝒈)<𝟏𝟐⁢𝒖𝟏⁢(𝑲) and 𝒖𝟑⁢(𝒈𝒌′)>𝒖𝟑⁢(𝑴∖𝑲)

Lemma 15.

Proof.

Lemma 16.

Proof.

Lemma 17.

Proof.

Lemma 18.

Proof.

Theorem 19.

Proof.

3.4 Case 3: 𝐦𝐚𝐱𝒈∈𝑲⁡𝒖𝟏⁢(𝒈)<𝟏𝟐⁢𝒖𝟏⁢(𝑲) and 𝒖𝟑⁢(𝒈𝒌′)≤𝒖𝟑⁢(𝑴∖𝑲)

Theorem 20.

3.5 An instance to show the tightness of ratio 𝟐

4 A 𝟓𝟑-approximation for three agents with normalized functions

4.1 Case 1: 𝐦𝐚𝐱𝒈∈𝑿⁡𝒖𝟏⁢(𝒈)≤𝟏𝟑

Lemma 21.

Proof.

Lemma 22.

Proof.

Theorem 23.

Proof.

4.2 Case 2: 𝐦𝐚𝐱𝒈∈𝑿⁡𝒖𝟏⁢(𝒈)>𝟏𝟑

Theorem 24.

Proof.

5 Conclusion

References

2 A $2$ -approximation for normalized functions

3 A $2$ -approximation for three agents with unnormalized functions

$\blacktriangleright$ Remark 11.

3.2 Case 1: $\max_{g\in K}u_{1}(g)\geq\frac{1}{2}u_{1}(K)$

3.3 Case 2: $\max_{g\in K}u_{1}(g)<\frac{1}{2}u_{1}(K)$ and $u_{3}(g^{\prime}_{k})>u_{3}(M\setminus K)$

3.4 Case 3: $\max_{g\in K}u_{1}(g)<\frac{1}{2}u_{1}(K)$ and $u_{3}(g^{\prime}_{k})\leq u_{3}(M\setminus K)$

3.5 An instance to show the tightness of ratio $2$

4 A $\frac{5}{3}$ -approximation for three agents with normalized functions

4.1 Case 1: $\max_{g\in X}u_{1}(g)\leq\frac{1}{3}$

4.2 Case 2: $\max_{g\in X}u_{1}(g)>\frac{1}{3}$