Fair Division with Allocator’s Preference

Abstract

We consider the problem of fairly allocating indivisible resources to agents, which has been studied for years. Most previous work focuses on fairness and/or efficiency among agents given agents’ preferences. However, besides the agents, the allocator as the resource owner may also be involved in many real-world scenarios (e.g., government resource allocation, heritage division, company personnel assignment, etc.). The allocator has the inclination to obtain a fair or efficient allocation based on her own preference over the items and to whom each item is allocated. In this paper, we propose a new model and focus on the following two problems concerning the allocator’s fairness and efficiency:

• 1. Is it possible to find an allocation that is fair for both the agents and the allocator?

• 2. What is the complexity of maximizing the allocator’s social welfare while satisfying the agents’ fairness?

We consider the two fundamental fairness criteria: envy-freeness and proportionality. For the first problem, we study the existence of an allocation that is envy-free up to c goods (EF-c) or proportional up to c goods (PROP-c) from both the agents’ and the allocator’s perspectives, in which such an allocation is called doubly EF-c or doubly PROP-c respectively. When the allocator’s utility depends exclusively on the items (but not to whom an item is allocated), we prove that a doubly EF-1 allocation always exists. For the general setting where the allocator has a preference over the items and to whom each item is allocated, we prove that a doubly EF-1 allocation always exists for two agents, a doubly PROP-2 allocation always exists for binary valuations, and a doubly PROP-$O(\log n)$ allocation always exists in general.

For the second problem, we provide various (in)approximability results in which the gaps between approximation and inapproximation ratios are asymptotically closed under most settings.

Most of our results are based on some novel technical tools including the chromatic numbers of the Kneser graphs and linear programming-based analysis.

The full version of this paper is available on arXiv [11]. Due to the space limit, many technical details are omitted in this version.

1 Introduction

Fair division studies how to fairly allocate a set of resources to a set of agents with heterogeneous preferences. It is becoming a valuable instrument in solving real-world problems, e.g., Course Match for course allocation at the Wharton School [13], and the website Spliddit (spliddit.org) for fair division of rent, goods, credit, and so on [20]. The construct of fair division was first articulated by Steinhaus [41, 42] in the 1940s, and has become an attractive topic of interest in wide range of fields, such as mathematics, economics, computer science, and so on (see, e.g., [1, 2, 9, 29, 35, 37, 38, 44] for a survey).

The classic fair division problem mainly focuses on finding fair and/or efficient allocations among agents given agents’ preferences. However, in many real-world scenarios, the allocator as the resource owner may also be involved, and, particularly, may have the inclination to obtain a fair or efficient allocation based on her own preference. For example, consider the division of inheritances, e.g., multiple companies and multiple houses, from the parent to two children. Both children would prefer the companies as they believe the market value of the companies will be increased more than the houses in the future. At the same time, the parent may want to allocate the companies to the elder child since the parent thinks the elder child has a better ability to run the companies. The final allocation should be fair for children and may also need to incorporate the parent’s ideas about the allocation. Another example is the government distributing educational resources (e.g., land, funding, experienced teachers or principals) among different schools. Some well-established schools may prefer land to build a new campus, while some new schools may need experienced teachers. On the other hand, the government may also have a preference (over the resources and to whom each resource is allocated) based on macroeconomic policy and may want the resulting distribution to be efficient on top of each school feels that it gets a fair share. Other examples abound: a company allocates resources to multiple departments, an advisor allocates tasks/projects to students, a conference reviewer assignment system allocates papers to reviewers, etc.

We focus on the allocation of indivisible goods in this work. To measure fairness, the two most fundamental criteria in the literature are envy-freeness and proportionality, respectively [18, 41, 42, 45]. In particular, an allocation is said to be envy-free if each agent weakly prefers her bundle over any other agent’s based on her own preference, and proportional if each agent values her bundle at least 1/n of her value for the whole resources, where n is the number of agents. Both fairness criteria can always be achieved in divisible resource allocation but it is not the case for indivisible resources (say, a simple example with two agents and one good). This triggers an increasing number of research work to consider relaxing exact fairness notions of envy-freeness and proportionality to envy-freeness up to c goods (EF-c) and proportionality up to c goods (PROP-c) (see, e.g., [12, 16, 28]). Specifically, an allocation is said to be EF-c if any agent’s envy towards another agent could be eliminated by (hypothetically) removing at most c goods in the latter’s bundle, and PROP-c if any agent’s fair share of 1/n could be guaranteed by (hypothetically) adding at most c goods that are allocated to other agents, where c is a positive integer. Besides fairness, another important issue of fair division is (economic) efficiency (e.g., social welfare), which is used to measure the total happiness of the agents [3, 6, 8, 15].

The fair division problem with allocator’s preference presents new challenges compared to the classic fair division problems. With indivisible goods, it is well known that the round-robin algorithm¹ can return a fair, i.e., EF-1, allocation from the agents’ perspective. However, this algorithm cannot be easily adapted to the problem where both agents and the allocator have preferences over items. Specifically, an agent’s preference describes how much this agent values each item, while the allocator’s preference describes how much the allocator regards each item values for each agent. Consider the instance with both agents’ and the allocator’s preferences shown in Tables 1 and 2.

Table 1. Agents’ Preferences

Table 2. Allocator’s Preferences

Suppose, w.l.o.g, agent 1 is before agent 2 in the ordering of the round-robin algorithm. When performing the algorithm without considering the allocator’s preference, agent 1 gets a bundle of items 1 and 2 while agent 2 gets item 3. From the allocator’s perspective, this allocation is not EF-1 since the allocator thinks agent 2 will envy agent 1 even when an arbitrary item is removed from agent 1’s bundle. One can also verify that the above allocation is not social welfare maximizing based on the allocator’s viewpoint, i.e., the allocator thinks there is another allocation such that the total happiness of the agents is larger. On the other hand, performing the round-robin algorithm based solely on the allocator’s preference will return an allocation where agent 1 gets items 2 and 3 while agent 2 gets item 1 (assuming agent 1 has a higher priority in the ordering). Specifically, we want to answer the following two questions in this paper.

• Question 1: Is it possible to find an allocation that guarantees both the allocator’s and agents’ fairness?

• Question 2: What is the complexity of maximizing the allocator’s efficiency while ensuring agents’ fairness?

1.1 Our Results

We initiate the study of fair division with allocator’s preference and address the two research questions above in this paper. We focus on the allocation of indivisible resources and discuss the divisible resources in the full version of our paper [11].

For the first problem, we propose new fairness notions doubly EF-c and doubly PROP-c that extend EF-c and PROP-c to our setting with regard to the allocator’s preference. We first consider the setting where the allocator’s utility only depends on the items (but not to whom an item is allocated), and we show that a doubly EF-1 allocation always exists. We then consider the general setting where the allocator’s utility depends on both the items and the allocation. For two agents, we show that 1) a doubly EF-1 allocation always exists, and 2) a doubly EF-2 allocation and a doubly PROP-1 allocation can be computed in polynomial time. For a general number of agents, we show that a doubly PROP-$\log _2n$ allocation always exists for n being an integer power of 2, and we show that a doubly PROP-($2\lceil \log n\rceil$) allocation always exists and can be computed in polynomial time. If we restrict to binary valuations, we show that a doubly PROP-2 allocation always exists and can be computed in polynomial time.

Table 3. Positive and Negative Results of Maximizing Allocator’s Efficiency. The numbers of agents and items are denoted by n and m, respectively. For each agent i, $v_i$ represents her utility function while $u_i$ represents how much the allocator regards each item values for agent i. Numbers $\alpha$ for negative results indicate that the problem is NP-hard to approximate to within the ratio $\alpha$; numbers $\alpha$ for positive results indicate that the problem admits a polynomial time $\alpha$-approximation algorithm. All our negative results hold for the special case $c=1$. The theorem statements and the proofs for these negative results are only available in the full version of this paper [11].

For the second problem, we study its complexity and approximability for both binary and general (additive) valuations. Our results are presented in Table 3. The gap between the approximation ratio and the inapproximability ratio is closed, or asymptotically closed, under most settings. If agents’ valuations are binary, this problem is tractable for EF-c with a constant number of agents and for PROP-c with a general number of agents. Under most other settings, this problem admits strong inapproximability ratios even for $c=1$.

Our results use many technical tools that are uncommon in the fair division literature, including i) the chromatic numbers of generalized Kneser graphs and ii) some linear programming-based analyses.

For i), we use a generalized Kneser graph to model a set of allocations and the relations between the allocations. Specifically, the set of allocations that are not fair based on an agent’s valuation form an independent set in the graph. The existence of a doubly fair allocation is built upon the argument that there are still remaining vertices after removing all vertices that correspond to unfair allocations. Since the set of unfair allocations for each agent forms an independent set, the chromatic number of the graph plays an important role in our analysis.

For ii), we use linear programs to formulate our problems. The solution to the linear program naturally corresponds to a fractional allocation. Our technique is mainly based on the analysis of the vertices of the polytope defined by the linear program. In some applications, we bound the number of the fractional items in an allocation given by a vertex solution of the linear program, and then handle those few fractional items separately. In other applications, we prove that all the vertex solutions of the linear program are integral.

1.2 Further Related Work

Conceptually, our model with allocator’s preference shares similarities with recent research work on fair division with two-sided fairness, e.g., [19, 21, 25, 36]. The existing two-sided fairness literature studies the fair division problem where there are two disjoint groups of agents and each agent in one group has a preference over the agents of the other group. The objective is then to find a (many-to-many) matching that is fair to each agent with respect to her belonging group. We remark these two models are different due to the following major reasons:

• In their model, there are two disjoint sets of agents, and each group of preferences is defined from one set of agents to the other set of agents (viewed as a set of “goods”). On the other hand, the two groups of preferences (one is from the agents and the other one is from the allocator) in our setting are both defined on a single set of agents and a single set of goods.

• In their model, each agent will be allocated (or matched) a set of agents from the other group which is different from ours, whereas the allocator in our model will not receive any resource in the allocation.

As we can see, our model with allocator’s preference reduces to the standard setting of indivisible goods when the allocator’s preference coincides with agents’ preferences. Our first research question reduces to find EF-c or PROP-c allocations in indivisible fair allocation, where the fairness notions of EF-1 and PROP-1 are extensively studied. In particular, an EF-1 allocation always exits and can be computed in polynomial time [14, 28]. For PROP-1, an allocation that is PROP1 and Pareto optimal always exits and can be computed in polynomial time [4, 7, 16, 34]. When considering the issue of economic efficiency, the problem in our second research question could be mapped to the problem of maximizing social welfare within either EF-1 or PROP-1 allocations in the indivisible goods setting. Aziz et al. [3] showed that the problem with either the EF-1 or the PROP-1 condition is NP-hard for $n \ge 2$ and Barman et al. [6] showed that the problem with the EF-1 requirement is NP-hard to approximate to within a factor of $1/m^{1-\varepsilon }$ for any $\varepsilon >0$ for general numbers of agents n and items m. Later, Bu et al. [10] gave a complete landscape for the approximability of the problem with the EF-1 criterion.

Moreover, several works studied the fair division problem where the resources need to be allocated among groups of agents and the resources are shared among the agents within each predefined group [31, 39, 40, 43]. In their model, $n=n_1+\cdots +n_k$ agents will be divided into $k \ge 2$ groups, where group i contains $n_i \ge 1$ agents. An allocation is a partition of goods into k groups. Each agent in the i-th group extracts utilities according to the i-th bundle. Kyropoulou et al. [27] also generalized the classic EF-c to the group setting: An agent’s envy towards another group could be eliminated by removing at most c goods from that group’s bundle. PROP-c could be defined similarly [32]. With binary valuations, Kyropoulou et al. [27] gave the characterization of the cardinalities of the groups for which a group EF-1 allocation always exits. In particular, they showed that a group EF-1 allocation always exists when there are two groups and each group contains two agents with binary valuations. Later, Manurangsi and Suksompong [32] showed via the discrepancy theory that EF-$O(\sqrt{n})$ and PROP-$O(\sqrt{n})$ allocations always exist in the group setting. Note that, when each group contains exactly two agents, i.e., $n_1 = \ldots = n_k =2$, the fair division problem in the predefined group setting coincides with our model (where each group could be considered to have an agent and the allocator). However, we obtain improved results in this particular setting through different technical tools.

2 Preliminaries

Let $[k] = \{1,\ldots ,k\}$. Our model consists of a set of agents $N = [n]$, a set of indivisible items $M = \{g_1, \ldots , g_m\}$, and the allocator. Each agent i has a nonnegative utility function $v_i:\{0, 1\}^m \rightarrow \mathbb {R}_{\ge 0}$. In addition, the allocator has her own preference in our model. The allocator’s preference is composed by n utility functions $u_i:\{0, 1\}^m \rightarrow \mathbb {R}_{\ge 0}$ where each $u_i$ is used to describe how much the allocator regards each item values for agent i. We assume both utility functions $u_i$ and $v_i$ are additive, which means $v_i(X) = \sum _{g\in X} v_i(g)$ and $u_i(X) = \sum _{g\in X} u_i(g)$ for any bundle $X\subseteq M$. A utility function $v_i$ (or $u_i$) is said to be binary if $v_i(g) \in \{0,1\}$ for any item $g\in M$. An allocation of the items $\mathcal {A}= (A_1, A_2, \dots , A_n)$ is an ordered partition of M, where $A_i$ is the bundle of items allocated to agent i.

An allocation $\mathcal {A}$ is said to be envy-free up to c goods (EF-c) if for all pairs of agents $i\ne j$, there exists a set $B\subseteq A_j$ such that $\left| B\right| \le c$ and $v_i(A_i)\ge v_i\left( A_j\setminus B\right)$ (or $v_i(A_i)\ge v_i(A_j)-v_i(B)$ for additive utility functions). An allocation $\mathcal {A}$ is said to be proportional up to c goods (PROP-c) if for any agent i, there exists a set $B \subseteq M\setminus A_i$ such that $\left| B\right| \le c$ and $v_i(A_i\cup B)\ge \frac{1}{n}v_i(M)$ (or $v_i(A_i)\ge \frac{1}{n} v_i(M) - v_i(B)$ for additive utility functions).

EF-c implies PROP-c for additive utility functions. An EF-1 (hence, PROP-1) allocation always exists and can be computed in polynomial time [14, 28]. In our model, besides ensuring fairness among agents, we also consider allocator’s fairness. Thus, we generalize the above fairness criteria in the following.

Definition 1

(Doubly Envy-free up to c goods). An allocation $\mathcal {A}$ is said to be doubly envy-free up to c goods (Doubly EF-c) if for all pairs of agents $i\ne j$, there exist sets $B_1, B_2\subseteq A_j$ such that $\left| B_1\right| , \left| B_2\right| \le c$, $v_i(A_i)\ge v_i\left( A_j\setminus B_1\right)$, and $u_i(A_i)\ge u_i\left( A_j{\setminus }B_2\right)$.

Definition 2

(Doubly Proportional up to c goods). An allocation $\mathcal {A}$ is said to be doubly proportional up to c goods (Doubly PROP-c) if for any $i\in N$, there exist sets $B_1, B_2 \subseteq M\setminus A_i$ such that $\left| B_1\right| , \left| B_2\right| \le c$, $v_i(A_i\cup B_1)\ge \frac{1}{n}v_i(M)$, and $u_i(A_i\cup B_2)\ge \frac{1}{n}u_i(M)$.

When the allocator’s utility functions are identical to agents’ utility functions, it is easy to see that doubly EF-c and doubly PROP-c degenerate to EF-c and PROP-c respectively. The above defined double fairness notions with the allocator’s preference can also be interpreted as: There are two groups of valuation functions u and v where one is from the agents and the other one is from the allocator. A single allocation is said to satisfy double fairness if such an allocation is fair, e.g., doubly EF-c/PROP-c, with respect to both valuation functions u and v.

To measure the economic efficiency for the allocator, we consider allocator’s efficiency:

Definition 3

The allocator’s efficiency of an allocation $\mathcal {A}=(A_1,\ldots ,A_n)$, denoted by ${{\,\mathrm{\texttt{EFFICIENCY}}\,}}(\mathcal {A})$, is the summation of the allocator’s utilities of all the agents ${{\,\mathrm{\texttt{EFFICIENCY}}\,}}(\mathcal {A})=\sum _{i=1}^nu_i(A_i)$.

In this paper, we are interested in the following two problems.

Problem 1

Given a set of indivisible items M, a set of agents $N=[n]$ with their utility functions $(v_1,\ldots ,v_n)$, and the allocator with her preference $(u_1,\ldots ,u_n)$, determine whether there exists an allocation $\mathcal {A}=(A_1,\ldots ,A_n)$ that is doubly EF-c/PROP-c.

Problem 2

Given a set of indivisible items M, a set of agents $N=[n]$ with their utility functions $(v_1,\ldots ,v_n)$, and the allocator with her preference $(u_1,\ldots ,u_n)$, the problem of maximizing allocator’s efficiency subject to EF-c/PROP-c aims to find an allocation $\mathcal {A}=(A_1,\ldots ,A_n)$ that maximizes allocator’s efficiency ${{\,\mathrm{\texttt{EFFICIENCY}}\,}}$ subject to that $\mathcal {A}$ is EF-c/PROP-c.

2.1 Kneser Graph and Chromatic Number

Let n, k be two integers. The Kneser graph $\mathcal {K}(n, k)$ is the graph with the set of all the k-element subsets of [n] as its vertex set and two vertices are adjacent if their intersection is empty. It was further extended to the following generalized version. Given three integers $n, k, s\in \mathbb {Z}^+$, in the generalized Kneser graph $\mathcal {K}(n, k, s)$, two vertices are adjacent if and only if their corresponding subsets intersect in s or fewer elements.

The chromatic number of a graph is the minimum number of colors needed to color the vertices such that no two adjacent vertices have the same color. In other words, the vertices with the same color form an independent set. We denote the chromatic number of a kneser graph $\mathcal {K}(n,k, s)$ by $\chi (n, k, s)$. For instance, when $n=4, k=3, s=2$, the kneser graph has $\left( {\begin{array}{c}4\\ 3\end{array}}\right) =4$ vertices and every two vertices are adjacent. Thus, $\mathcal {K}(4,3,2)$ is a clique and $\chi (4,3,2) = 4$.

For the chromatic number of the Kenser graph, when $n \ge 2k$, it is exactly equal to $n -2k +2$ [5, 22, 30, 33]. For the generalized Kneser graph, Jafari and Moghaddamzadeh [26] gave the following lower bounds.

Lemma 1

([26]). For any positive integers $s < k < n$,

$$\chi (n, k, s) \ge n - 2k + 2\,s + 2.$$

Lemma 2

([26]). For any $k\in \mathbb {Z}^+ \ge 2$, $\chi (2k, k, 1) = 6$.

2.2 Totally Unimodular Matrix and Linear Programming

Totally unimodular matrix is a special family of matrices that can be used to check whether a linear programming is integral, i.e., there exists one optimal solution such that all decision variables are integers.

Definition 4 (Totally Unimodular Matrix)

A matrix $\textbf{A}_{m\times n}$ is a totally unimodular matrix (TUM) if every square submatrix of $\textbf{A}$ has determinant 0, $+1$ or $-1$.

To determine whether a matrix is TUM, we have the following lemma.

Lemma 3

Given a matrix $\textbf{A} \in \{0, \pm 1\}^{m\times n}$, $\textbf{A}$ is TUM if it can be written as the form of $\left[ \begin{array}{c} \textbf{A}_1 \\ \textbf{A}_2 \end{array}\right]$, where $\textbf{A}_1\in \{0, 1\}^{r\times n}$ (or $\{0, -1\}^{r\times n}$), $\textbf{A}_2\in \{0, 1\}^{(m-r)\times n}$ (or $\{0, -1\}^{(m-r)\times n}$), $1\le r\le m$ and there is at most one nonzero number in every column of $\textbf{A}_1$ or $\textbf{A}_2$.

Lemma 4

([24]). If $\textbf{A}$ is totally unimodular and $\textbf{b}$ is an integer vector, then each vertex of the polytope $\{\textbf{A}\textbf{x}\le \textbf{b},\textbf{x}\ge \textbf{0}\}$ has integer coordinates.

We can further show there exist polynomial-time algorithms to find the optimal vertex solution for such a linear program by the following lemma.

Lemma 5

([23]). For a linear program $\max \{\textbf{c}^\top \textbf{x}:\textbf{A}\textbf{x}\le \textbf{b},\textbf{x}\ge \textbf{0}\}$, if optimal solutions exist, an optimal vertex solution can be found in polynomial time. In particular, we can find an (integral) vertex of the polytope $\{\textbf{A}\textbf{x}\le \textbf{b},\textbf{x}\ge \textbf{0}\}$ in polynomial time.

3 Double Fairness

In this part, we present the results for the existence of double fairness. In the first part, we assume the allocator’s utility depends exclusively on the item (rather than to whom an item is allocated). That is, we assume the allocator’s utility functions are identical $u_1=\cdots =u_n$. We show that a doubly EF-1 allocation always exists in this case by adapting the envy-cycle procedure. After that, we consider the general setting without $u_1=\cdots =u_n$. In this case, we first show that a doubly EF-1 allocation always exists for $n =2$ based on the chromatic number of the generalized Kneser graph $\mathcal {K}(m,m/2,1)$. However, the existence of doubly EF-1 allocations for $n>3$ is highly non-trivial. For this reason, we consider relaxing the fairness constraint to doubly EF-c or PROP-c and try to minimize the value of c. We show that a doubly PROP-$O(\log n)$ allocation always exists for any number of agents via the techniques based on the generalized Kneser graph and linear programming. Finally, we also consider another common setting, where both the allocator and agents’ utility functions are binary (the utility value can only be 0 or 1). This relaxation makes the problem tractable and we demonstrate a doubly PROP-2 allocation always exists in this setting.

3.1 Identical Allocator’s Utility Function

This section considers the case when the allocator’s utility functions $u_1,\ldots ,u_n$ are identical. Let $u=u_1=\cdots =u_n$.

We first give a brief introduction of the techniques used in this section. The envy-cycle procedure was first proposed by [28] to compute an EF-1 allocation for general valuations. In the envy-cycle procedure, an envy-graph is constructed for a partial allocation. Each vertex in the envy-graph represents an agent and each directed edge (u, v) means that agent u envies agent v in the current allocation. When there is a cycle in an envy-graph, we use the cycle-elimination algorithm to eliminate this cycle.

Definition 5 (Cycle-elimination Algorithm)

Given an envy-graph with a cycle $u_1\rightarrow \ldots \rightarrow u_n \rightarrow u_1$, shift the agents’ bundles along the cycle ($A_{u_i} \leftarrow A_{u_{i+1}}$ for $i=1, \ldots , n-1$ and $A_n \leftarrow A_1$).

Algorithm 1

Finding Doubly EF-1 Allocation for Identical Utility Function

Theorem 1

When the allocator’s utility functions are identical, a doubly EF-1 allocation always exists for any number of agents n, and can be found by Algorithm 1 in polynomial time.

Our algorithm is presented in Algorithm 1. At the beginning of the algorithm, we construct an envy-graph G with n vertices and no edges and sort the items according to the allocator’s utility function in descending order. Then, we divide the sorted items into $\Big \lceil {\frac{m}{n}}\Big \rceil$ groups where each group contains n items. In each round, we allocate a group of items to the agents such that each agent receives exactly one item. This can guarantee the EF-1 property from the allocator’s perspective. To allocate the group of n items to the n agents in each round, each agent takes away her favorite item from the group, where the agents are sorted in the topological order of G before the iteration begins. After all these n items are allocated, we update the envy-graph and run the cycle-elimination algorithm, so that the envy-graph contains no cycle and a topological order of the agents can be successfully found in the next round. By an induction-based argument showing the EF-1 property of the well-known round-robin algorithm, the EF-1 property of our algorithm in the agents’ perspectives can be proved.

3.2 General Additive Valuations with Two Agents

For general (monotone) valuations with two agents, the existence of a doubly EF-1 allocation can be proved with the help of the generalized Kneser graph.

Theorem 2

When $n = 2$, there always exists a doubly EF-1 allocation.

Proof

Our high-level idea is to consider the allocations that some agents or the allocator do not regard as EF-1. We then use the Kneser graph to demonstrate that the union of these allocations cannot cover the entire space of all possible allocations. We assume the number of items, m, is even. Otherwise, we can add a dummy item g such that $v_i(g) = u_i(g) = 0$. We denote the set of allocations where each bundle’s size is exactly equal to $\frac{m}{2}$ by $\varPi$. For $i=1,2$, Let $\mathcal {V}_i$ be the set of allocations that agent i does not regard as EF-1. Besides, $\mathcal {U}_i$ represents the set of allocations that the allocator does not regard as EF-1 for agent i. Formally, they are given by the following formulas:

$$\begin{aligned}\begin{gathered} \mathcal {V}_i \triangleq \{\mathcal {A} \in \varPi : v_i(A_i) < v_i\left( (M{\setminus }A_i) {\setminus } \{g\}\right) , \forall g\in (M{\setminus } A_i)\},\\ \mathcal {U}_i \triangleq \{\mathcal {A} \in \varPi : u_i(A_i) < u_i\left( (M{\setminus } A_i) {\setminus } \{g\}\right) , \forall g\in (M{\setminus } A_i) \}. \end{gathered}\end{aligned}$$

For the existence of a doubly EF-1 allocation, it suffices to show that $\mathcal {V}_1\,\cup \,\mathcal {V}_2\,\cup \,\mathcal {U}_1\,\cup \,\mathcal {U}_2\subsetneq \varPi$. Let $\mathcal {V}_1^{(1)}=\{A_1:(A_1,A_2)\in \mathcal {V}_1\}$, and define $\mathcal {V}_2^{(1)}, \mathcal {U}_1^{(1)}, \mathcal {U}_2^{(1)}$ analogously. We give the proposition for $\mathcal {V}_1^{(1)}$ below, which also works for the other three sets.

Proposition 1

For each $A_1, A_1' \in \mathcal {V}_1^{(1)}$, $\left| A_1 \cap A_1' \right| \ge 2$.

Proof

For the sake of contradiction, we assume $\left| A_1 \cap A_1' \right| \le 1$. If $A_1\cap A_1'=\emptyset$, $(A_1,A_1')$ is a valid allocation. If $(A_1,A_1')$ is not EF1 according to $v_1$, then $(A_1',A_1)$ is envy-free, which means $A_1'\notin \mathcal {V}_1^{(1)}$.

If $\left| A_1\cap A_1'\right| =1$, let $g_1$ be the item in $A_1\cap A_1'$ and $g_2$ be the only item in $M\setminus (A_1\cup A_1')$. According to the definition of $\mathcal {V}_1$, we have

$$\begin{aligned}\begin{gathered} v_1(A_1) < v_1(M {\setminus } A_1) - v_1(g_2) = v_1(A_1') - v_1(g_1),\\ v_1(A_1') < v_1(M {\setminus } A_1') - v_1(g_2) = v_1(A_1) - v_1(g_1). \end{gathered}\end{aligned}$$

Combining the above two inequalities yields a contradiction.   $\square$

Return to the proof of Theorem 2. We consider the generalized Kneser graph $\mathcal {H}= \mathcal {K}\left( m, \frac{m}{2}, 1\right)$. Each vertex of the graph defines a bundle B of m/2 items, and it defines an allocation $(A_1,A_2)$ where $A_1=B$ and $A_2=M{\setminus } B$. Due to Proposition 1, each of $\mathcal {V}_1^{(1)}, \mathcal {V}_2^{(1)}, \mathcal {U}_1^{(1)}, \mathcal {U}_2^{(1)}$ cannot contain two adjacent vertices of $\mathcal {H}$ and is thus an independent set.

Finally, we have $\mathcal {V}_1\cup \mathcal {V}_2\cup \mathcal {U}_1\cup \mathcal {U}_2\subsetneq \varPi$. Otherwise, $\mathcal {H}$ can be decomposed into four independent sets, which contradicts to $\chi (\mathcal {H})=6$ (Lemma 2).    $\square$

Remark 1

Theorem 2 also holds for general monotone utility functions that are not necessarily additive, with the same proof above.

Theorem 2 is non-constructive. For constructive results, we use linear programming to construct a doubly EF-2 allocation in Theorem 3.

Theorem 3

When $n = 2$, there always exists a doubly EF-2 allocation that can be computed in polynomial time.

Proof

For each item $g_j\in M$, we use one decision variable $x_j$ to represent the fraction of item $g_j$ allocated to group $N_1$. Consider the following linear program:

$$\begin{aligned} \max _{{\textbf {x}}}\quad &\left( \sum _{j=1}^m v_1(g_j)x_j - \sum _{j=1}^m v_1(g_j) (1-x_j) \right) \nonumber \\ \text {subject to}\quad & 0\le x_j \le 1,\forall 1\le j\le m \end{aligned}$$

(1)

$$\begin{aligned} & \sum _{j=1}^m u_1(g_j)x_j \ge \sum _{j=1}^m u_1(g_j) (1-x_j) \end{aligned}$$

(2)

$$\begin{aligned} &\sum _{j=1}^m v_2(g_j)x_j \le \sum _{j=1}^m v_2(g_j) (1-x_j) \end{aligned}$$

(3)

$$\begin{aligned} &\sum _{j=1}^m u_2(g_j)x_j \le \sum _{j=1}^m u_2(g_j) (1-x_j) \end{aligned}$$

(4)

Notice that a solution ${\textbf {x}}$ with a non-negative objective provides a fractional doubly envy-free allocation. In addition, $\{x_j=0.5\}_{j=1,\ldots ,m}$ is such a solution.

Consider an optimal vertex solution ${\textbf {x}}^*$. Lemma 5 implies such a solution can be found in polynomial time. Among all the constraints given in (1), (2), (3), and (4), a vertex solution is obtained by setting m of them being tight. Even if all of the three constraints (2), (3), and (4) are tight, at least $m-3$ constraints are tight in (1). This implies at most three variables have value in the open interval (0, 1). Let $x_1^*,x_2^*,x_3^*$ be them without loss of generality. This implies we have a doubly envy-free allocation where only the first three items may be fractionally allocated. In the remaining part of the proof, we show that how to carefully decide the (integral) allocation of the first three items to make the allocation doubly EF-2.

Let $(O_1,O_2)$ be the allocation of the remaining $m-3$ items indicated by the LP solution ${\textbf {x}}^*$. We consider the two cases of $x_1^*, x_2^*, x_3^*$.

Suppose at least two of them are no less than $\frac{1}{2}$, and assume $x_1^*, x_2^* \ge \frac{1}{2}$. Consider the allocation $(O_1\cup \{g_1,g_2\}, O_2\cup \{g_3\})$. For agent 1, for each $v\in \{u_1, v_1\}$, we have $v(A_1)+ v\left( g_3\right) \ge \sum _{g_j\in M} v\left( g_j\right) x_j^* \ge v(A_2)$. For agent 2, for each $v\in \{u_2, v_2\}$, assume $v(g_1)\ge v(g_2)$, then we have

$$\begin{aligned} v(A_2) + v\left( g_1\right) &= v(A_2)+ \left( 1- x_1^*\right) v(g_1) +x_1^* v(g_1) \\ &\ge v(A_2) + \left( 1-x_1\right) v(g_1) + (1- x_2^*) v(g_1)\\ &\ge v(A_2)+ \left( 1-x_1^*\right) v(g_1) + \left( 1-x_2^*\right) v(g_2)\\ &\ge \sum _{g_j\in M} v(g_j)\left( 1-x_j^*\right) \ge \frac{1}{2}v(M) \ge v(A_1). \end{aligned}$$

Suppose at least two of them are no more than $\frac{1}{2}$, and assume $x_1^*, x_2^* \le \frac{1}{2}$. Similarly, we can also verify that $\left( O_1 \cup \{g_3\}, O_2 \cup \{g_1, g_2\}\right)$ is doubly EF-2.    $\square$

It is easy to see that an EF-2 allocation is always PROP-1 for two agents.

Corollary 1

When $n = 2$, there always exists a doubly PROP-1 allocation that can be computed in polynomial time.

3.3 General Additive Valuations with General Number of Agents

Next, we consider the lower bound of c when $n \ge 2$. Our results are shown in the two theorems below.

Theorem 4

For any $n= 2^k$, there always exists a doubly PROP-k allocation.

Theorem 5

For any $n\ge 2$, there always exists a doubly PROP-$\left( 2 \Big \lceil \log n\Big \rceil \right)$ allocation and it can be computed in polynomial time.

The proofs are available in the full version of our paper [11]. Here we briefly describe the high-level ideas. Both theorems are based on the idea of Even-Paz algorithm [17]. Given n agents, we first partition the agent set into two groups and try to allocate each group one bundle. After that, we fix the two bundles to the two groups and then do further allocating within groups recursively. To guarantee the property of PROP-c, in each recursive iteration, we ensure that each agent and the allocator believe the agent’s group receives approximately a $\frac{1}{2}$ fraction of the total value. To be specific, the value should be at least $\frac{1}{2}$ up to d items, where d depends on the level of the recursion tree.

The ideas in the proofs of both Theorem 2 and Theorem 3 can be generalized to achieve this. The idea of Kneser graphs can give a better fairness guarantee with a smaller value of c. However, it only works when agents can be partitioned into two equal-sized groups, and it is non-constructive. This yields Theorem 4. The idea of linear programming analysis gives a slightly worse fairness guarantee, but it is constructive and it works for any number of agents.

3.4 Binary Valuations

As shown in Theorem 5, for general additive valuation, when $n\ge 2$, doubly PROP-$O(\log n)$ allocations always exist. In this section, we further consider another common setting where the utility functions are binary. We show that a doubly PROP-2 allocation always exists and can be found in polynomial time for any $n\ge 2$ in Theorem 6. The advantage of this setting is that an agent i only needs to focus on the items whose values are regarded as 1 by $v_i(\cdot )$ or $u_i(\cdot )$.

Theorem 6

When $u_i, v_i$ are both binary for any $i\in N$, a doubly PROP-2 allocation always exists for any $n\ge 2$ and can be computed in polynomial time.

Proof

For each agent $i\in N$, we define the following three item sets: $\mathcal {I}_i^{(1)} \triangleq \{g\in M: v_i(g) = 1 \wedge u_i(g) = 0 \}$, $\mathcal {I}_i^{(2)} \triangleq \{g\in M: v_i(g) = u_i(g) = 1 \}$, $\mathcal {I}_i^{(3)} \triangleq \{g\in M: u_i(g) = 1 \wedge v_i(g) = 0 \}$. Then, we formulate this problem by a linear program. For each agent $i\in N$, we define a vector ${\textbf {x}}_i = \left( x_{i,j}\right) _{j\in [m]}$, where $x_{i, j}$ represents the fraction of item $g_j$ allocated to agent i. Denote $\left( \textbf{x}_1, \ldots , \textbf{x}_n\right)$ by $\textbf{x}$. Hence ${\textbf {x}}$ is a vector with $n\times m$ variables. Consider the polytope $P = \{\textbf{x}: \textbf{A}\textbf{x}^{\textsf{T}} \le \textbf{b}, \textbf{x} \ge \textbf{0} \}$, where $\textbf{A} \in \mathbb {R}^{(3n+m)\times (n\times m)}$ and $\textbf{Ax}^\top \le \textbf{b}$ is decomposed into two parts:

• For each agent $i\in N$ and $k\in \{1, 2, 3\}$, $\sum _{j \in \mathcal {I}_i^{(k)}} x_{i, j} \ge \lfloor \frac{1}{n} \cdot \vert \mathcal {I}_i^{(k)}\vert \rfloor .$

• For each item $g_j\in M$, $\sum _{i\in N} x_{i,j} \le 1$.

The second part says that a total amount of at most one unit can be allocated for each item j. The first part gives a sufficient condition for the allocation being PROP-2. Specifically, for each agent i, it implies $1+\sum _{j \in \mathcal {I}_i^{(k)}} x_{i, j} \ge 1/n \cdot \vert \mathcal {I}_i^{(k)}\vert$ for $k=1,2,3$. For $k=1,2$, this implies the allocation is PROP-2 with respect to $v_i$, $2+\sum _{j \in \mathcal {I}_i^{(1)}}x_{i, j}+\sum _{j \in \mathcal {I}_i^{(2)}} x_{i, j} \ge 1/n \cdot (\vert \mathcal {I}_i^{(1)}\vert +\vert \mathcal {I}_i^{(2)}\vert )$; for $k=2,3$, this implies the allocation is PROP-2 with respect to $u_i$, $2+\sum _{j \in \mathcal {I}_i^{(2)}}x_{i, j}+\sum _{j \in \mathcal {I}_i^{(3)}} x_{i, j} \ge 1/n \cdot (\vert \mathcal {I}_i^{(2)}\vert +\vert \mathcal {I}_i^{(3)}\vert )$.

Notice that $\textbf{A}$ can also be written as the form $\left[ \begin{array}{c} \textbf{A}_1 \\ \textbf{A}_2 \end{array}\right]$, where $\textbf{A}_1$ and $\textbf{A}_2$ correspond to the two parts of the constraints. It is easy to verify that $\textbf{A}_1$ is a matrix containing only 0 and $-1$ and $\textbf{A}_2$ is a matrix containing only 0 and 1. Moreover, each column of $\textbf{A}_1$ and $\textbf{A}_2$ contains at most one non-zero entry. According to Lemma 3, $\left[ \begin{array}{c} \textbf{A}_1 \\ \textbf{A}_2 \end{array}\right]$ is TUM.

Since $\textbf{x} = \left( x_{i,j}\right) = \left( \frac{1}{n}\right)$ is in the polytope, P is nonempty. In addition, since A is TUM and ${\textbf {b}}$ is an integer vector, by Lemma 4, all vertices of P are integral. By Lemma 5, we can find a vertex $\mathbf {x^*}\in \{0,1\}^{n\times m}$ in polynomial time. Then for each agent $i\in N$, allocate the bundle $A_i = \left\{ g_j\in M: x_{i, j}^{*} = 1 \right\}$ to her.

Thus, by the definition of the above linear program,

$$ v_i(A_i) \ge v_i\left( \mathcal {I}_i^{(1)}\right) + v_i\left( \mathcal {I}_i^{(2)}\right) \ge \frac{1}{n}\left| \mathcal {I}_i^{(k)}\right| - 1 + \frac{1}{n} \left| \mathcal {I}_i^{(k)}\right| - 1 = \frac{v_i(M)}{n} - 2. $$

Similarly, we can verify the above inequality for $u_i$. If there are no less than two items with value 1 outside $A_i$, this allocation is already PROP-2. Otherwise, if there is at most one item with value 1 outside $A_i$, then $v_i(M)\le v_i(A_i)+1$. It is easy to verify any bundle $A_i$ satisfying this condition is PROP-2.    $\square$

4 Allocator’s Efficiency

In this section, we consider the problem of maximizing allocator’s efficiency subject to EF-c or PORP-c constraint for the agents. Other than general additive utility functions, we also consider the special case of binary utility functions. Note that we no longer consider the special case with identical allocator’s utility $u_1=\cdots =u_n$ since the problem becomes trivial otherwise (all allocations have the same allocator’s efficiency).

All the negative results (corresponding to the fifth column in Table 3), including theorem statements and proofs, are available in the full version of our paper and are omitted here [11].

When the number of agents is 2, the problem is NP-hard to approximate to within a factor of 2 (see the full version), and this is matched with the following positive result.

Theorem 7

The problem of maximizing allocator’s efficiency subject to EF-c for two agents has a polynomial time 2-approximation algorithm when the agents’ utility functions are arbitrary.

Proof ((sketch))

Our algorithm is described as follows. We initialize two empty bundles $S_1$ and $S_2$, and sort the items according to agent 1’s utility in descending order. Assume the sorted items are $\{g_1,\dots , g_m\}$, and use $G_i (i\ge 1)$ to denote a group of two items $\{g_{2i-1},g_{2i}\}$. For each group $G_i (i\ge 1)$, we allocate one item to each bundle. In particular, without loss of generality, we assume $v_2(S_1)\ge v_2(S_2)$ before allocating group $G_i$. Then, if $v_2(g_{2i-1})\ge v_2(g_{2i})$, we allocate $g_{2i-1}$ to $S_2$ and $g_{2i}$ to $S_1$. Otherwise, we allocate $g_{2i-1}$ to $S_1$ and $g_{2i}$ to $S_2$. Notice that, in this algorithm, agent 1’s utility function is used exclusively for the ordering of the item, and agent 2’s utility function is used exclusively for deciding the allocation of the two items in each group.

After all the items are allocated, we consider the two allocations $(S_1,S_2)$ and $(S_2,S_1)$, and output the allocation with a higher allocator’s efficiency.

It is not hard to check that the allocation is always EF-1 and is thus EF-c for any $c\ge 1$. To see the approximation guarantee of 2, notice that $u_1(M)+u_2(M)$ is a trivial upper bound to the allocator’s efficiency, and the social welfare of the output allocation is at least half of it.    $\square$

For a constant number of agents, we have an inapproximability factor of about $\sqrt{n}$ (see the full version) even when the allocator has binary utility functions. However, when the agents have binary valuations, the problem becomes tractable.

Theorem 8

The problem of maximizing allocator’s efficiency subject to EF-c for any fixed $n\ge 3$ can be found in polynomial time when the agents’ utility functions are binary.

Proof ((sketch))

We can adopt the dynamic programming used in the proof of Theorem 7.5 in [3] to prove this theorem. The details are available in the full version of our paper [11].    $\square$

For general numbers of agents, even when both the agents and the allocator have binary valuations, the optimization problem admits an inapproximability factor of $m^{1-\epsilon }$ or $n^{1/2-\epsilon }$. This is complemented by the following positive result.

Theorem 9

The problem of maximizing allocator’s efficiency subject to EF-c has a m-approximation algorithm when both the agents’ and the allocator’s utility functions are arbitrary.

Proof

Let the allocator allocates a single item to a single agent with the highest value $u_i(g_j)$ for $1\le i\le n, 1\le j\le m$ to agent i. Then the agents use the round-robin algorithm to allocate the remaining items. The allocation is EF-1 (and is thus EF-c) guaranteed by the round-robin algorithm and is a trivial m-approximation to the optimal allocator’s efficiency.    $\square$

Finally, we turn our attention to PROP-c. If the agents’ utility functions are binary, we can use linear programming to prove the following result.

Theorem 10

When agents’ utility functions are binary, the problem of maximizing allocator’s efficiency subject to PROP-c can be solved exactly in polynomial time by linear programming.

Proof

The problem can be formulated as a linear program. Moreover, a careful analysis with the help of Lemma 3 reveals that the coefficient matrix is totally unimodular and all values in the constraints are integers. The theorem follows from Lemma 4 and Lemma 5.    $\square$

5 Conclusion and Future Work

In this paper, we initialize the study of a new fair division model that incorporates the allocator’s preference. We focused on the indivisible goods setting and mainly studied two research questions based on the allocator’s preference: 1) How to find a doubly fair allocation? 2) What is the complexity of the problem of maximizing the allocator’s efficiency subject to agents’ fairness constraint?

We believe this new model is worth more future studies. For example, could we extend our results to the setting with more general valuation functions, e.g., submodular valuations? It is also an interesting (and challenging) problem to study what is the minimum number of c where a doubly EF-c/PROP-c allocation is guaranteed to exist. Indeed, we do not know any lower bound for c. Specifically, we do not know if a doubly EF-1/PROP-1 allocation exists even for binary valuations. We have searched for a non-existence counterexample with the aid of computer programs, and a non-existence counterexample seems hard to find.

On the other hand, our current techniques about Kneser graph and linear programming seem to have their limitations for further reducing the upper bound of c. Our current technique with Kneser graph can only analyze a bi-partition of the items with an equal size m/2 (this is crucial for Propositions 1 in the proof of Theorem 2 and the proof of Theorem 4). In addition, the value of the bundle must be exactly half of the total value up to the addition of c items. This is why we need n to be an integer power of 2 in Theorem 4. Moreover, the nature of Kneser graph-based analysis makes the existence proof non-constructive. Our linear programming technique, on the other hand, provides a weaker bound on c. It seems to us that a Kneser graph captures more structural insights about our problem than a linear program. Nevertheless, linear programming-based techniques provide a constructive existence proof.

It is fascinating to see these techniques to be further exploited and the above-mentioned limitations to be bypassed. Unearthing new techniques for closing the gap between the upper bound and the lower bound of c may also be necessary.

In our double fairness setting, we aim to find an allocation that is fair with respect to two valuation profiles $(u_1,\ldots ,u_n)$ and $(v_1,\ldots ,v_n)$, one for the agents and one for the allocator. A natural generalization of this is to consider allocations that are fair with respect to t valuation profiles for general t. The problem of fair division with more than two sets of valuations is also well-motivated in many applications (e.g., there may be more than one “allocator” in many scenarios, and an agent’s valuation of the items may be multi-dimensional). We discuss the setting with multiple sets of valuations in the full version of our paper [11].