1 Introduction↩︎

Given a set of valuable resources, the fair division problem asks whether these resources can be allocated among agents with potentially differing preferences in a fair manner. This problem is important in economics and has garnered increasing attention in artificial intelligence and computer science over the past few decades [1]–[5]. The problem has many applications, including land division [6], apartment rent sharing [7], and divorce settlements [1]. Envy-freeness is one of the most widely studied fairness criteria in the literature. It requires that each agent considers their assigned bundle to be at least as desirable as any other bundle in the allocation [8], [9]. For more information about fair allocations, we refer to two surveys by Amanatidis et al. [10] and Aziz et al. [11].

Recently, motivated by real-world applications where agents are often not equally obliged, Chakraborty et al. [12] introduced the weighted setting. In this framework, the weights assigned to agents can reflect widely recognized and accepted indicators of entitlement, such as eligibility or merit. A classic illustration of this is inheritance distribution, where individuals who are closer relatives typically have a greater claim to the inheritance than more distant relatives. Likewise, larger organizations with more individuals may be entitled to a larger share of resources. By incorporating weights, this model is able to account for a wider variety of real-world situations. Weighted models have been extremely studied in fair allocations, and we will provide more information on weighted models later.

Under the most widely studied weighted envy-freeness, the utility of each agent is divided by his weight in the fairness. This setup is simple and can promote more fairness in some scenarios. However, experimental tests show that this weighted envy-freeness significantly reduces the likelihood of fair allocations [12]. Our subsequent experiments will also show that the probability of weighted fair allocations is substantially less than the probability of fair allocations without weights.

When discussing fair allocations, we often introduce new fairness concepts because the fair allocations under the current concept may not exist. In such cases, we must settle for a relaxed fairness concept. For instance, envy-freeness allocation may not always exist, and we introduced new fairness concepts like MMS and EF1. The weighted envy-freeness appears to take a different approach: it enhances fairness theoretically, yet diminishes the feasibility of equitable distribution in practice. To understand this better, we reexamine weighted envy-freeness and propose a new envy-freeness concept under the weight setting, which is called SumAvg-envy-freeness. In fact, our envy-freeness integrates the classic envy-freeness and weighted envy-freeness concepts. We will show allocations under the new envy-freeness concept is more practical and more “likely” to exist than that under the old weighted envy-freeness concept.

The allocation problems we consider mainly involve two scenarios. One is the allocation of indivisible resources, where each resource can only be assigned to one agent as a whole and we also require that all resources be allocated. Otherwise, not allocating any resources at all could be a trivial solution. The other one is the house allocation problem, which requires that each agent is assigned exactly one resource. The house allocation problem is also an important problem in fairness allocations. When considering the weighted setting in house allocation, the weights for a family can represent the number of members in that family. Naturally, larger families require larger living spaces compared to smaller families. Therefore, even if a smaller family receives a less valuable house than a larger family, there may still be no envy.

1.1 More Related Work↩︎

1.1.0.1 Weighted Models.

Weighted models have been studied in a wide range of fair allocations under different concepts of fairness. In addition to weighted envy-freeness, there are other concepts of weighted fairness in the literature. Chakraborty et al. [12] introduced the concept of weighted envy-freeness up to one item (WEF1) for the allocation of goods and demonstrated that WEF1 allocations always exist and can be found in polynomial time. Both Wu et al. [13] and Springer et al. [14] established the existence and presented algorithms for the computation of WEF1 allocations for chores. WPROP1 allocations have been shown to always exist for chores [15] and for a mixture of goods and chores [16]. Li et al. [17] established the existence and computation of WPROPX allocations for chores. The weighted version of MMS has also been studied for both goods [18] and chores [19]. When we consider more general utility functions, Chakraborty et al. [12] showed that WEF1 allocations do not always exist for arbitrary monotonic utilities. There are also some researches combining weighted setting and non-additive utility functions [20], [21]. For a comprehensive review of existing research on weighted indivisible fair allocation, please refer to the recent surveys [22].

1.1.0.2 House Allocation.

House allocation is a special case of indivisible resource allocation, where each agent gets exactly one resource. This problem has been extensively studied in the context of designing incentive-compatible mechanisms and ensuring economic efficiency [23], [24]. Recent research has increasingly focused on fairness, often defined through the notion of envy-freeness [8], [9], [25], [26]. Gan et al. [27] developed a polynomial-time algorithm to check and find an envy-free house allocation. Recently, Dai et al. [28] extended the weight setting to house allocation and also got a polynomial-time algorithm to check and find an weighted envy-free house allocation. When the agents are previously partitioned into several groups, group-fairness was also extended to house allocation [29]. In cases where fair allocations under existing fairness concepts may not be achievable, researchers have also explored compromises, aiming to balance fairness objectives. The problem of finding allocations that maximize multiple fairness criteria has been widely studied [30]–[33].

2 Our Model and Contributions↩︎

For the sake of presentation, we call the envy-freeness without weight Sum-envy-freeness and the previous weighted envy-freeness Avg-envy-freeness.

2.1 New Concept of Envy-Freeness↩︎

As mentioned earlier, one motivation for proposing a new concept of fairness is the hope that fair allocations under this new concept will exist. In fact, most new fairness concepts typically exhibit the inheritability property: if an allocation satisfies the original fairness concept, it will also satisfy the new one.

We also observe another property commonly held by previous fairness concepts: when an agent envies another, swapping the resources assigned to them can eliminate the envy. We refer to this property as exchange elimination. This property is quite reasonable, and almost all existing fairness concepts satisfy it.

The concept of weighted envy-freeness (Avg-envy-freeness) does not satisfy either of the two properties mentioned above. In Example 1, when there are no weights, an envy-free allocation exists where each agent receives one resource. But after introducing weights, no envy-free allocation can be found. Thus, weighted envy-freeness does not satisfy the inheritability property. Moreover, when each agent receives one resource, agent 2 envies agent 1 because agent 1’s weight is larger. Even if we exchange the resources between them, agent 2 continues to envy agent 1. Therefore, the exchange elimination property does not hold.

We hope that the two properties discussed above can be satisfied under the concept of weighted fairness. To achieve this, we hope that a fair allocation in the unweighted case should also be fair in the weighted case.

Based on this principle, we modify the concept of fairness in the weighted model as follows: agent A will not envy agent B if at least one of the following two conditions is met: (1) in agent A’s view, the utility of the resources assigned to agent A divided by agent A’s weight is no less than the utility of the resources assigned to agent B divided by agent B’s weight (this corresponds to the condition for Avg-envy-freeness); (2) in agent A’s view, the utility of the resources assigned to agent A is no less than the utility of the resources assigned to agent B (this corresponds to the condition for Sum-envy-freeness). We refer to this new concept as SumAvg-envy-freeness.

SumAvg-envy-freeness should not be viewed as a simple union of the previous concepts of Sum-envy-freeness and Avg-envy-freeness. For example, in Example 2, there exists a SumAvg-envy-free allocation where \(r_1\) is assigned to \(a_1\) and \(r_2\) is assigned to \(a_2\). However, there is no allocation that is Sum-envy-free or Avg-envy-free.

From the above examples, we can see that SumAvg-envy-free allocation is more likely to exist. Our experiments further support this observation. We test on 10000 weighted instances with 8 resources and 5 to 8 agents. The ratio of instances having fair allocations under different envy-free concepts is shown in Table 1. More discussion and experimental results in different settings are shown in Section 6.

It should be noted that we are not denying Avg-envy-freeness. In fact, our proposed concept of SumAvg-envy-freeness complements, rather than contradicts, the idea of Avg-envy-fairness. SumAvg-envy-freeness exhibits the inheritability property not only for Sum-envy-freeness but also Avg-envy-freeness. When Avg-envy-freeness does not exist, we still need to allocate the resources—how should we proceed? Perhaps SumAvg-envy-freeness can be used as a fallback concept to perform the allocation. Our proposal of SumAvg-envy-freeness is not a denial of Avg-envy-freeness, but rather an extension of the notion of fairness under weights. It’s analogous to how EF1 was proposed when EF allocations were not guaranteed to exist.

2.2 Computational Complexity↩︎

After introducing a new concept of fairness, we need to study the existence of the fair allocation under this concept and the computational complexity of computing the fair allocation. Although SumAvg-envy-freeness can be applied for a wider range, SumAvg-envy-free allocations may still not exist even in very simple scenarios. For example, in the case where it is to assign one resource to two agents, fair allocation will not exist. Next, we systematically investigate the computational complexity of finding a fair allocation under different fairness concepts.

We will first consider the NP-hardness of our problems. In fact, they will be computationally hard in general. Next, our research approach contains two ways. One is to investigate whether a polynomial-time algorithm exists for the restricted version of the problem under different constraints. The other is to study the parameterized complexity of the problem with different parameters. We mainly consider two restricted versions on the utility functions which are identical and 0/1. We call an utility function identical if the utility of each agent on any resource \(r\) is the same. We call an utility function 0/1 if the utility of each agent on any resource \(r\) is either 0 or 1. For parameterized complexity, we will mainly consider two parameters: “number of agents” and “number of resources”. Previous results and our results under the three fair concepts Sum-envy-freeness, Avg-envy-freeness, and SumAvg-envy-freeness are presented in Table 2.

In Section 4, we consider the allocation of indivisible resources. We show that under identical and 0/1 preferences, checking the existence of Avg-envy-free and SumAvg-envy-free allocations can be solved in polynomial time. However, under general 0/1 preferences, both of these problems become NP-hard.

We then further demonstrate that under 0/1 preferences, checking the existence of Avg-envy-free and SumAvg-envy-free allocations is fixed-parameter tractable (FPT) with respect to the parameter “number of agents." Under general preferences, we show that checking the existence of Avg-envy-free and SumAvg-envy-free allocations is FPT with respect to the parameter”number of resources."

In Section 5, we shift focus to house allocation. Under general preferences, while checking the existence of Sum-envy-free and Avg-envy-free allocations can be solved in polynomial time, the problem of checking the existence of Sum-envy-free allocations becomes NP-hard, even when there are only two types of weights and three types of numbers in the utility functions. However, under 0/1 preferences or identical preferences, finding SumAvg-envy-free house allocations can be done in polynomial time.

3 Preliminaries↩︎

An instance of the weighted fair allocation problem consists of a set \(A = \{a_1, a_2, \dots, a_n\}\) of \(n\) agents where each \(a_i\in A\) has weight \(w_i > 0\). Let \(R=\{r_1, r_2,\dots, r_m\}\) be a set of \(m\) resources with utility functions \(u_i : 2^R \rightarrow \mathbb{Z}\). An allocation of a set \(R\) of indivisible resources to a set \(A\) of agents is a mapping \(\pi : A \rightarrow 2^R\) such that \(\pi(a)\) and \(\pi(a')\) are disjoint whenever \(a \neq a'\). For any agent \(a \in A\), we call \(\pi(a)\) the bundle of \(a\) under \(\pi\). Furthermore, if for each \(a_i\in A\), the size of \(\pi(a_i)\) is exactly one, the allocation \(\pi\) is called a house allocation.

An utility function \(u : 2^R \rightarrow \mathbb{Z}\) is additive if for each bundle \(X \subseteq R\), \(u(X) = \sum_{r\in X} u(\{r\})\). An additive utility function is monotonic if it only outputs non-negative utilities. In this paper, we assume that utility functions are additive and monotonic.

Next, we give the formal definitions of the three fairness concepts.

When we consider indivisible resource allocations, we may always require the completeness to avoid some trivial cases.

We define the following computational problems.

SAEF-Allocation
Instance: A set \(A\) of \(n\) agents where each \(a \in A\) has weight \(w_a > 0\), a set \(R\) of \(m\) indivisible resources, a family \(U = \{u_1, u_2, \dots, u_n\}\) of non-negative utility functions.
Task: To find a complete and SumAvg-envy-free allocation.

Similarly, we can define SEF-Allocation and AEF-Allocation by finding a Sum-envy-free allocation or an Avg-envy-free allocation instead of a SumAvg-envy-free allocation. For house allocation, we define the following SAEF-House-Allocation problem.

SAEF-House-Allocation
Instance: A set \(A\) of \(n\) agents where each \(a \in A\) has weight \(w_a > 0\), a set \(R\) of \(m\) indivisible resources, a family \(U = \{u_1, u_2, \dots, u_n\}\) of non-negative utility functions.
Task: To find an SumAvg-envy-free house allocation.

Similarly, we can define SEF-House-Allocation and AEF-House-Allocation.

4 Indivisible Resource Allocations↩︎

In this section, we consider indivisible resource allocations. We will analyze the NP complexity and parameterized complexity for checking the existence of fairness allocations under the three envy-free concepts. Recall that previous and our results are presented in Table 2.

Consider an instance \((A, R, U)\) of AEF-Allocation or SAEF-Allocation, if for any agent \(a\in A\), we have \(w_a = 1\), this instance is equivalent to the same instance of SEF-Allocation. Thus, the hardness results for SEF-Allocation will imply the same hardness results for AEF-Allocation and SAEF-Allocation. The NP-hardness results under different restricted preferences of SEF-Allocation are established by Lipton et al. [37], Bouveret and Lang [36], and Aziz et al. [38].

4.1 Polynomial solvable cases↩︎

We consider the case where the preferences are 0/1 and identical. Firstly, we show AEF-Allocation under identical and 0/1 preferences can be solved in polynomial time by a simple observation. Then we show a main result in this section that SAEF-Allocation under identical and 0/1 preferences can be solved in polynomial time.

Next, we show that SAEF-Allocation under identical and 0/1 preferences can be solved in polynomial time. Firstly, we prove the following two properties of SumAvg-envy-free allocations.

Consider an instance \((A, R, U)\) of SAEF-Allocation where \(A = \{a_1, a_2, \dots, a_n\}\) is sorted by weights in ascending order. Clearly, if an allocation \(\pi\) satisfies that for any \(1\leq i \leq n - 1\), \(u(\pi(a_i)) \leq u(\pi(a_{i+1}))\) and \(u(\pi(a_i))/w_i \geq u(\pi(a_{i+1})) / w_{i+1}\), then \(\pi\) is a SumAvg-envy-free allocation. By Property 1 and Property 2, we have that \(\pi\) is a SumAvg-envy-free allocation if and only if \(\pi\) satisfies that for any \(1\leq i \leq n - 1\), \(u(\pi(a_i)) \leq u(\pi(a_{i+1}))\) and \(u(\pi(a_i))/w_i \geq u(\pi(a_{i+1})) / w_{i+1}\). Thus, in our algorithm, we search for an allocation satisfing that for any \(1\leq i \leq n - 1\), \(u(\pi(a_i)) \leq u(\pi(a_{i+1}))\) and \(u(\pi(a_i))/w_i \geq u(\pi(a_{i+1})) / w_{i+1}\). We call such allocation feasible.

Now we are ready to show our main algorithm.

4.2 Few agents or few resources↩︎

Although SAEF-Allocation under identical and 0/1 preferences can be solved in polynomial time, Bouveret and Lang [36] show that SEF-Allocation under identical preferences is NP-hard and SEF-Allocation under 0/1 preferences is also NP-hard. Clearly, the hardness results for SEF-Allocation will imply the same hardness results for AEF-Allocation and SAEF-Allocation. Thus, we turn to consider parameterized complexity for the hard problems. We consider two parameters: the number \(n\) of agents and the number \(m\) of resources. We first show that SAEF-Allocation is FPT with respect to the number of resources.

We encode our instance \((A, R, U)\) of SAEF-Allocation as an Integer Programming instance (SAEF-IP). Let \(A = \{a_1, a_2\dots, a_n\}\), \(R = \{r_1, r_2, \dots, r_m\}\). For some resource \(r\), we define the type of \(r\) as a vector \(t_r:= (u_1(r), u_2(r), \dots, u_n(r))\). And let \(T := \{t_r: r\in R\}\) be the set of types of all resources in \(R\). Let \(t_r[i]\) be the value \(u_i(r)\). Let \(\# t\) be the number of resources of type \(t\). Now we are ready to construct our ILP model.

For each agent \(a_i\in A\) and each type \(t\in T\), we introduce a variable \(x_i^t \in [m]\) to represent the number of resources of type \(t\) allocated to agent \(a_i\). Since each feasible allocation is complete, we have the following constraint. \[\forall t\in T:\sum_{i\in[n]}x_i^t = \#t.\] Since each feasible allocation is SumAvg-envy-free, we have the following two constraints, where at least one should be satisfied. For each two agents \(a_i, a_j\in A\), \[\sum_{t\in T}x_i^t t[i]\geq \sum_{t\in T}x_j^t t[i]\] or \[w_j\sum_{t\in T}x_i^t t[i]\geq w_i\sum_{t\in T}x_j^t t[i].\]

To represent this “or” constraint, we introduce a big number \(M = \sum_{i\in [n], j\in [m]} u_i(j) \cdot \sum_{i\in [n]} w_i\). Then, for each two agents \(a_i, a_j\in A\), we introduce two variables \(y_{ij}^1\in \{0, 1\}\) and \(y_{ij}^2\in \{0, 1\}\) and introduce the following two constraints. \[M y_{ij}^1\leq M+(\sum_{t\in T}x_i^t t[i]- \sum_{t\in T}x_j^t t[i]),\] \[M y_{ij}^2\leq M+(w_j\sum_{t\in T}x_i^t t[i]- w_i\sum_{t\in T}x_j^t t[i]).\] Consider the inequality (4), if \(\sum_{t\in T}x_i^t t[i] \geq \sum_{t\in T}x_j^t t[i]\), we have that \(M+(\sum_{t\in T}x_i^t t[i]- \sum_{t\in T}x_j^t t[i])\geq M\) and \(y_{ij}^1\) can be 0 or 1. If \(\sum_{t\in T}x_i^t t[i] < \sum_{t\in T}x_j^t t[i]\), we have that \(M+(\sum_{t\in T}x_i^t t[i]- \sum_{t\in T}x_j^t t[i])< M\) and \(y_{ij}^1\) must be 0. The similar arguments hold for \(y_{ij}^2\). Thus, we know that at least one of inequalities (2) and (3) is satisfied if and only if \(y_{ij}^1 + y_{ij}^2 \geq 1\). We have the following constraint.

\[\forall i,j\in [n]: y_{ij}^1+y_{ij}^2\geq 1.\]

Now, we put all things together, and get the following Integer Programming instance (SAEF-IP). \[\begin{align} & Min1\\ & subject to: \\ & \forall t\in T:\sum_{i\in[n]}x_i^t = \#t\\ & \forall i,j\in[n]: M y_{ij}^1<M+(\sum_{t\in T}x_i^t t[i]- \sum_{t\in T}x_j^t t[i])\\ & \forall i,j\in[n]: M y_{ij}^2<M+(w_j\sum_{t\in T}x_i^t t[i]- w_i\sum_{t\in T}x_j^t t[i])\\ & \forall i,j\in [n]: y_{ij}^1+y_{ij}^2\geq 1\\ & \forall t\in T, i\in [n]: x_i^t \in [m]\\ & \forall i,j\in [n]: y_{ij}^1\in \{0, 1\}\\ & \forall i,j\in [n]: y_{ij}^2\in \{0, 1\} \end{align}\]

As a corollary, we show that the FPT result also holds for the case of 0/1 preferences.

For AEF-Allocation, we encode our instance \((A, R, U)\) as an Integer Programming instance (AEF-IP) by a similar way. \[\begin{align} Min& 1\\ subject to:& \forall t\in T:\sum_{i\in[n]}x_i^t = \#t\\ & \forall w_j\sum_{t\in T}x_i^t t[i]\geq w_i\sum_{t\in T}x_j^t t[i]\\ & \forall t\in T, i\in [n]: x_i^t \in [m] \end{align}\] And by similar arguments, we give the following corollaries without proofs.

5 House Allocations↩︎

In this section, we consider house allocations. Recall that previous and our results are presented in Table 3.

SEF-house-Allocation and AEF-house-Allocation under additive monotonic preferences can be solved in polynomial time [27], [28]. Surprisingly, we demonstrate that SAEF-house-Allocation under additive monotonic preferences is NP-hard, even when there are only two types of weights. The hardness result is obtained by reducing from the classic NP-complete problem 3-SAT [40].

3-SAT
Instance: a set of clauses \(C = \{c_1, \dots, c_m\}\) defined over a set of variables \(X = \{x_1, \dots, x_n\}\) such that each clause is disjunctive and consists of 3 literals.
Task: Determine whether there exists an assignment of the variables which satisfies all the clauses.

Proof. We will show a polynomial-time reductions from 3-SAT to SAEF-House-Allocation under additive monotonic preferences. Specifically, consider a 3-SAT instance \((C = \{c_1, \dots, c_m\}, X = \{x_1, \dots, x_n\})\), we construct an equivalent SAEF-House-Allocation instance \((A = A_x\cup A_c, R = R_x\cup R_c, U = U_x\cup U_c)\) as follows.

Let \(M\) be a large constant number. We ensure that the maximum number in utility functions is \(M\).

(a) Variable gadgets: For each variable \(x_i\in X\), we construct two agents \(a_{x, i}\in A_x\) and \(\bar a_{x, i}\in A_x\), and two resources \(r_{x, i}\in R_x\) and \(\bar r_{x, i}\in R_x\). Let \(\overline{\overline{r}}_{x, i} = r_{x, i}\). Let \[u_{a_{x, i}}(r_{x, i}) = u_{a_{x, i}}(\bar r_{x, i}) = 1.\] and \[u_{\bar a_{x, i}}(r_{x, i}) = u_{\bar a_{x, i}}(\bar r_{x, i}) = M.\] And for any other possible resource \(r\), let \[u_{a_{x, i}}(r) = u_{\bar a_{x, i}}(r) = 0.\] Let \(w_{a_{x, i}} = 1\) and \(w_{\bar a_{x, i}} = M\). Clearly, consider any SumAvg-free-allocation \(\pi\), one of \(r_{x, i}\) and \(\bar r_{x, i}\) will be allocated to \(a_{x, i}\) and the other will be allocated to \(\bar a_{x, i}\). If agent \(a_{x, i}\) is allocated resource \(r_{x, i}\), it can be interpreted in 3-SAT as setting variable \(x_i\) to true. Similarly, if agent \(a_{x, i}\) is allocated resource \(\bar r_{x, i}\), it can be interpreted in 3-SAT as setting variable \(x_i\) to false.

(b) Clause gadgets: For each clause \(c_j\), we construct four agents \(a_{c, j}^1, a_{c, j}^2, a_{c, j}^3\) and \(a_{c, j}^*\in A_c\). And we construct four resources \(r_{c, j}^1, r_{c, j}^2, r_{c, j}^3\) and \(r_{c, j}^*\in R_c\). Let \(c_j = l(j, 1)\vee l(j, 2)\vee l(j, 3)\), where \(l(j, k)\) respects the \(k\)-th literal in \(c_j\). We use \(r_{l(j, k)}\) to denote the resource corresponding to the \(k\)-th literal in \(c_j\). For example, if \(c_1 = x_1\vee x_2 \vee \bar x_n\), then \(l(1, 3) = \bar x_n\), \(r_{l(1, 3)} = \bar r_{x, n}\) and \(\bar r_{l(1, 3)} = r_{x, n}\).

Consider the utility functions for \(a_{c, j}^k\) (\(k = 1, 2, 3\)), we construct them as follows. Let \[u_{a_{c, j}^k}(r_{c, j}^k) = u_{a_{c, j}^k}(\bar r_{l(j, k)}) = M,\] and
\[u_{a_{c, j}^k}(r_{c, j}^*) = 1.\]

For any other possible resource \(r\), let \(u_{a_{c, j}^k}(r) = 0\).

For their weights, let \(w_{a_{c, j}^1} = w_{a_{c, j}^2} = w_{a_{c, j}^3} = 1\).

Consider the utility functions for \(a_{c, j}^*\), let \[u_{a_{c, j}^*}(r_{c, j}^1) = u_{a_{c, j}^*}(r_{c, j}^2) = u_{a_{c, j}^*}(r_{c, j}^3) = M.\]

For any other possible resource \(r\), let \(u_{a_{c, j}^*}(r) = 0\). For the weight, let \(w_{a_{c, j}^*} = M\).

We finish our construction of the SAEF-House-Allocation instance. See Fig. 1 for an illustration. Now, we show that \((A, R, U)\) is a yes-instance of SAEF-House-Allocation if and only if \((C, X)\) is a yes-instance of 3-SAT.

Assume \((C, X)\) is a yes-instance, we construct a SumAvg-envy-free house allocation \(\pi\) as follows. For each variable \(x_i\), if \(x_i\) is true, then \(\pi(a_{x,i}) = r_{x, i}\) and \(\bar \pi(\bar a_{x,i}) = \bar r_{x, i}\). Otherwise, \(\pi(a_{x,i}) = \bar r_{x, i}\) and \(\pi(\bar a_{x,i}) = r_{x, i}\). For each clause \(c_j = l(j, 1)\vee l(j, 2)\vee l(j, 3)\), if \(l(j, 1)\) is true, then \(\pi(a_{c, j}^1) = r_{c, j}^*\). Otherwise, \(\pi(a_{c, j}^1) = r_{c, j}^1\). Similarly, if \(l(j, 2)\) (resp. \(l(j, 3)\)) is true and \(r_{c, j}^*\) is not be allocated, then \(\pi(a_{c, j}^2)\) (resp. \(\pi(a_{c, j}^3)\)) \(= r_{c, j}^*\). otherwise, \(\pi(a_{c, j}^2) = r_{c, j}^2\) (resp. \(\pi(a_{c, j}^3) = r_{c, j}^3\)). Since \((C, X)\) is a yes-instance, we know that at least one literal in \(l(j, 1), l(j, 2)\) and \(l(j, 3)\) should be true. Let \(l(j, k)\) (\(k = 1, 2, 3\)) be the first literal that be true, which means that \(\pi(a_{c, j}^k) = r_{c, j}^*\), then \(\pi(a_{c, j}^*) = r_{c, j}^k\).

We show that \(\pi\) is a SumAvg-envy-free allocation as follows. Firstly, for some agent \(a_i\) allocated with a resource with utility \(M\), \(a_i\) will not envy any other agent, since \(a_i\) is allocated with the largest utility in all possible utilities. Thus, the only possible envy will occurs in the agent \(a_{c, j}^k\) allocated with \(r_{c, j}^*\) for some \(j\) and \(k\). Note that when \(a_{c, j}^k\) is allocated with \(r_{c, j}^*\), we know that \(r_{c, j}^k\) is allocated to \(a_{c, j}^*\) and \(\bar r_{l(j, k)}\) is allocated to \(\bar a_{x, i}\) since \(l(j, k)\) is true. Note that the weights of agent \(a_{c, j}^*\) and agent \(\bar a_{x, i}\) are both \(M\). We have that agent \(a_{c, j}^k\) will not envy agent \(a_{c, j}^*\) and agent \(\bar a_{x, i}\) since \(1 / 1 \geq M / M\). Thus, \(\pi\) is a SumAvg-envy-free allocation.

Assume \((A, R, U)\) is a yes-instance and let \(\pi\) be a SumAvg-envy-free house allocation. We show that \((C, X)\) is a yes-instance. We construct the truth assignment as follows. Clearly, one of \(r_{x, i}\) and \(\bar r_{x, i}\) will be allocated to \(a_{x, i}\) and the other will be allocated to \(\bar a_{x, i}\). If agent \(a_{x, i}\) is allocated resource \(r_{x, i}\), we set \(x_i\) to true, otherwise we set \(x_i\) to false. By contradiction, we assume there exists a clause \(c_j = l(j, 1)\vee l(j, 2)\vee l(j, 3)\) such that \(l(j, 1) = l(j, 2) = l(j, 3) =\) false. In this case, we know that the corresponding resources of \(\bar l(j, 1)\), \(\bar l(j, 2)\) and \(\bar l(j, 3)\) are allocated to agents with weights 1. Since there must be a \(k = 1, 2, 3\) such that \(r_{c, j}^k\) is allocated to \(a_{c, j}^*\), there must be an agent \(a_{c, j}^k\) allocated with \(r_{c, j}^*\). However, \(a_{c, j}^k\) will envy the agent allocated with \(\bar r_{l(j, k)}\) since the weights of these two agents are both 1 and \(a_{c, j}^k\) perfer \(\bar r_{l(j, k)}\) than \(a_{c, j}^*\), which leads a contradiction.

Thus, this theorem holds. ◻

Now we show that under more restricted preferences, SAEF-house-Allocation can be solved in polynomial time. Under 0/1 preferences, we have the following observation.

Under identical preferences, we can design a dynamic programming algorithm for SAEF-house-Allocation, which is similar to the algorithm given in Theorem 1.

6 Experiments↩︎

To better understand the distinctions among SumAvg-envy-freeness, Sum-envy-freeness and Avg-envy-freeness, it is important to investigate the existence of them in practical. In this section, we address this question through a series of experiments.

We run 10,000 instances with \(5, 6, 7, 8\) agents and 8 resources. The linear preferences of the agents are generated either from impartial culture (IC), with no restriction of domain, or following a distribution for preferences restricted to the single-peaked domain [41]. Let us recall that a preference order \(\succ\) is single-peaked with respect to an axis \(>^O\) over the objects if there exists a unique peak object \(x^* \in O\) such that for every pair of objects \(a\) and \(b\), \(x^* >^O a >^O b\) implies \(x^*\succ a \succ b\), and \(a >^O b >^O x^*\) implies that \(x^*\succ b \succ a\).

In our experiments, the single-peaked preferences are generated from the single-peaked uniform peak culture (SPUP), meaning they are generated by uniformly drawing a peak alternative on a given axis over the objects and then iteratively choosing the next preferred alternatives with equal probability on either the left or right of the peak along the axis. The values of utility functions are drawn independently from a uniform distribution ranging from \(1\) to \(10,000\). The weights of agents are drawn independently from two uniform distributions ranging from \(1\) to \(100\), and from \(101\) to \(200\), respectively.

The frequency of existence of an EF allocation in three different concepts are shown in Fig. 2. The frequency of existence of an EF house allocation three different concepts are shown in Fig. 3.

The experimental results reveal several key observations:

1. In every setting, the number of instances admitting SumAvg-envy-free allocations is surprisingly larger than the number of instances admitting Sum-envy-free or Avg-envy-free allocations.

2. In almost every setting, the number of instances admitting Sum-envy-free allocations is larger than those admitting Avg-envy-free allocations, aligning with the experimental results in [12].

3. Compared to the setting where \(101 \leq w \leq 200\), under the \(1\leq w\leq 100\) setting, the larger ratio between maximum and minimum weights exerts a stronger influence on weighted allocations. We can see that in the \(1\leq w\leq 100\) setting, SumAvg-envy-free allocations are more likely to exist while Avg-envy-free allocations are more likely to not exist. This outcome is consistent with expectations.

Our experimental results demonstrate that achieving Sum-envy-freeness or Avg-envy-freeness is significantly more challenging than achieving SumAvg-envy-freeness. When Sum-envy-free or Avg-envy-free allocations do not exist, SumAvg-envy-free allocations may be able to serve as a viable alternative.

7 Conclusion↩︎

In this paper, we revisit the concept of weighted envy-freeness. To ensure the existence of fair allocations in broader scenarios, we introduce a new weighted fairness concept. While this approach may relax certain fairness guarantees, it significantly enhances allocation feasibility. Subsequently, we conduct a systematic computational complexity analysis of computing fair allocations under different fairness concepts.

We conclude with an interesting open problem. We have shown that SAEF-House-Allocation under additive monotonic preferences is NP-hard, while SAEF-House-Allocation under identical preferences can be solved in \(O(nm^2)\) time. However, it remains unclear whether SAEF-House-Allocation under identical order preferences can be solved in polynomial time. Identical order preferences mean that there exists an ordering of the resources \(r_1, r_2, \dots, r_m\) such that \(u_i(r_1)\geq u_i(r_2)\geq \dots \geq u_i(r_m)\) for every agent \(a_i\).

References↩︎