# fair_division_with_prioritized_agents__d13fff3a.pdf

Fair Division with Prioritized Agents

Xiaolin Bu1, Zihao Li2, Shengxin Liu3*, Jiaxin Song1, Biaoshuai Tao1

1 School of Electronic Information and Electrical Engineering, Shanghai Jiao Tong University 2 School of Physical and Mathematical Sciences, Nanyang Technological University 3 School of Computer Science and Technology, Harbin Institute of Technology, Shenzhen lin bu@sjtu.edu.cn, zihao003@e.ntu.edu.sg, sxliu@hit.edu.cn, sjtu xiaosong@sjtu.edu.cn, bstao@sjtu.edu.cn

We consider the fair division problem of indivisible items. It is well-known that an envy-free allocation may not exist, and a relaxed version of envy-freeness, envy-freeness up to one item (EF1), has been widely considered. In an EF1 allocation, an agent may envy others allocated shares, but only up to one item. In many applications, we may wish to specify a subset of prioritized agents where strict envy-freeness needs to be guaranteed from these agents to the remaining agents, while ensuring the whole allocation is still EF1. Prioritized agents may be those agents who are envious in a previous EF1 allocation, those agents who belong to underrepresented groups, etc. Motivated by this, we propose a new fairness notion named envy-freeness with prioritized agents EFPRIOR, and study the existence and the algorithmic aspects for the problem of computing an EFPRIOR allocation. With additive valuations, the simple round-robin algorithm is able to compute an EFPRIOR allocation. In this paper, we mainly focus on general valuations. In particular, we present a polynomialtime algorithm that outputs an EFPRIOR allocation with most of the items allocated. When all the items need to be allocated, we also present polynomial-time algorithms for some well-motivated special cases.

1 Introduction

The fair division problem studies how to fairly allocate a set of resources to a set of agents who have heterogeneous preferences over the resources. Starting with Steinhaus (1948), the fair division problem has been receiving significant attention from mathematicians, economists, and computer scientists in the past decades. Among different fairness interpretations, envy-freeness (Foley 1967) is the most studied fairness criterion which requires that each agent believes she receives a share that has weakly more value than the share allocated to each of the other agents (i.e., each agent does not envy any other agents). Classical work in fair division has been focused on resources that are infinitely divisible, which is also known as cake-cutting problem (Even and Paz 1984; Brams and Taylor 1995; Chen et al. 2013; Bei et al. 2012, 2017; Tao 2022) . Envy-free allocations always exist in the cake-cutting setting (Brams and Taylor 1995) and can

*Shengxin Liu is the corresponding author. Copyright 2023, Association for the Advancement of Artificial Intelligence (www.aaai.org). All rights reserved.

be computed via a discrete and bounded protocol (Aziz and Mackenzie 2016). Recent research focuses more on allocations of indivisible items (Lipton et al. 2004; Budish 2011; Conitzer, Freeman, and Shah 2017; Caragiannis et al. 2019; Bu et al. 2022b; Amanatidis et al. 2022; Li, Bei, and Yan 2022). Obviously, violation of fairness is unavoidable in some scenarios, e.g., when the number of items is less than the number of agents (in which case some agents will receive an empty set). This necessitates the relaxation of fairness. To relax envy-freeness, Lipton et al. (2004) and Budish (2011) proposed the notion envy-freeness up to one item (EF1) which allows an agent i to envy another agent j, as long as there exists an item in j s allocated bundle whose (hypothetical) removal eliminates the envy from i to j.1 EF1 has then been one of the most widely-studied fairness notions for indivisible item allocation, and is guaranteed to exist (Lipton et al. 2004; Caragiannis et al. 2019). While an allocation that gives advantages to some agents over the others is perhaps justifiable by the inherent unfairness in the allocation of indivisible items, in many applications, it is desirable that a specified set of agents with higher priority are favored. The examples abound: it is natural to prioritize those agents who are not favored in the past allocations (due to the intrinsic unfairness of item-allocation); for applicants with equal qualifications, job positions are given to those applicants in underrepresented groups first. These motivate the proposal of new fairness solution concepts that not only mitigates the unfairness but also ensures that those prioritized agents are favored if unfairness is inevitable. In the context of envy-freeness, although EF1 mitigates the unfairness by restricting envy to up to one item , it does not consider agents priorities. To incorporate this feature, we propose a new fairness notion called envy-freeness with prioritized agents (EFPRIOR). Given a set of prioritized agents, an EFPRIOR allocation requires that 1) the allocation as a whole is EF1 and 2) strict envy-freeness from each prioritized agent to each non-prioritized agent is ensured. As an important remark, by introducing prioritized agents, our solution concept EFPRIOR does not create unfairness. Instead, we are seeking for allocations that prioritize a pre-

1EF1 was implicitly mentioned by Lipton et al. (2004), and explicitly formulated by Budish (2011).

The Thirty-Seventh AAAI Conference on Artificial Intelligence (AAAI-23)

scribed set of agents subject to that unfairness has been justified and mitigated. This differentiates our work from those who assign weights to agents based on their importance (Chakraborty et al. 2021; Chakraborty, Segal-Halevi, and Suksompong 2022). Our solution concept applies to the scenarios where fairness is of paramount importance and the tie-breaking matters if absolute fairness fails.

Applications of fairness with prioritized agents. Our model aligns with all the fair division applications where fairness is the primary desideratum, and a secondary desideratum is used to break ties. This secondary desideratum can be arbitrarily specified as needed. For example, in a typical course registration mechanism of a university, students submit rankings to the available courses reflecting their preferences, and the system allocates courses based on their (heterogeneous) preferences and course vacancies. The course allocation is primarily based on students preferences and will allocate a course to a student only when all the students ranking this course higher than her are registered. This minimizes the envy among the students. However, when the number of vacancies cannot sustain all the students who rank this course high, priority is given to senior students among those students submitting the same ranking, in order to ensure these senior students timely graduation. Here, the secondary desideratum takes the academic year into account. As another example, when a set of entitled benefits cannot be evenly distributed among the employees in a company, slight advantages are normally given to those older employees for their longer time of service, those who have larger family expenses (e.g., having more children, being under medical treatment), or other desirable tie-breaking factors. Another potential application of our model is the fair division with underrepresented agents. A vast among of organizations value DEI (diversity, equity, and inclusion) and offer corresponding training program to avoid discrimination to those underrepresented groups. However, the mere presence of these diversity structures may fail to serve their purpose without a concrete fairness measurement (Kaiser et al. 2013). On the other hand, this type of measurements needs to be carefully made to avoid reverse discrimination: inappropriate policies may cause those overrepresented groups feel they have been discriminated (Fish 1993; Newkirk and Vann 2017). Our EFPRIOR notion gives a concrete measurement and provides advantages to the underrepresented groups to an extent that is also acceptable to other groups in the sense that an overall fairness criterion EF1 is still guaranteed. The practice of prioritizing underrepresented groups within the range of fairness has already been adopted widely. For example, under the Equality Act 2010 in the United Kingdom, the membership in a protected and disadvantaged group is allowed to be considered in hiring and promotion, if the candidates are of equal merit. In this case, the membership in an underrepresented group is used as a tie-breaker .

On computing EFPRIOR allocations. Unfortunately, most EF1 algorithms do not have control over which agents are favored in the output EF1 allocation. Lipton et al. (2004) proposed an algorithm, envy-graph procedure, that com-

putes an EF1 allocation with polynomial time. The algorithm starts by assigning each agent the empty bundle, and adds an item to an agent s bundle in each iteration. Specifically, an envy-graph (see Sect. 2.2 for details) is constructed where vertices represent agents and a directed edge (i, j) represents i envies j in the current allocation. To maintain EF1 property throughout the process, the algorithm always chooses a source vertex in the graph and adds an item to the bundle of the agent corresponding to this vertex. Whenever there is a cycle in the graph, a cycle-rotation step is performed where each agent s bundle is replaced by the bundle of the next agent in the cycle; this guarantees the existence of the source vertices at the beginning of each iteration. In this algorithm, a source in the envy-graph is not envious and is thus favored, but the cycle-rotation step in the algorithm changes the set of source vertices unpredictably. Caragiannis et al. (2019) showed that the allocation with the maximum Nash social welfare (NSW) is always EF1. Thus, a natural algorithm for computing an EF1 allocation is to find a NSW maximizing allocation, which is adopted by the fair division website spliddit.org (Goldman and Procaccia 2015; Shah 2017). However, the uniqueness of the NSW maximizing allocations makes it impossible to prioritize a fixed set of agents. Although a simple round-robin algorithm (Caragiannis et al. 2019) can output an EF1 allocation with specified agents prioritized, it only works if agents valuations are additive (see Sect. 2.1 for details). However, in general settings, the existence and the computation of an EFPRIOR allocation remain to be open problems, which is the main concern of this paper.

1.1 Our Results As our main contribution, we propose a new fairness notion EFPRIOR that is stronger than EF1 by additionally enforcing strict envy-freeness from a prescribed set of prioritized agents to the remaining agents. We then study the existence and the algorithmic aspects of EFPRIOR. We note that EFPRIOR always exists for agents with additive valuations, and can be computed by a round-robin algorithm (Sect. 2.1). With general valuations, we present a polynomial-time algorithm that outputs a partial EFPRIOR allocation where the set of unallocated items has a small bounded size and small bounded values to all agents (Theorem 10). Our techniques are built upon the algorithm for computing an envy-freeness up to any item (EFX) allocation proposed by Chaudhury et al. (2021b). Other than some additional effort being made to maintaining the strict envy-freeness from the prioritized agents to the remaining agents, our algorithm makes use of a novel approach to exchange the agents bundles with the pool of unallocated items. This new approach makes our algorithm run in polynomial time, whereas Chaudhury et al. s algorithm is only known to run in pseudo-polynomial time. We also study two special cases: when all the prioritized agents have the same valuations, and when all the nonprioritized agents have the same valuations (Sect. 3). Under both cases, we show the existence of EFPRIOR by presenting polynomial time algorithms. The positive results on these two special cases imply the tractability of EFPRIOR in the

following three scenarios: 1) when there is only one prioritized agent, 2) when there is only one non-prioritized agent, and 3) when the total number of agents is at most 3. The algorithms in Sect. 3 provide some basic ideas that are used in the algorithm for our main technical result (mentioned in the previous paragraph) in Sect. 4. We conclude our paper by proposing the open problem about the existence and the computational complexity of a (complete) EFPRIOR allocation in the general setting.

1.2 Related Work

Besides envy-freeness and EF1 as introduced before, another important envy-based fairness notion is called envyfreeness up to any item (EFX) (Caragiannis et al. 2019). In an EFX allocation, each agent i may envy agent j but the envy can be eliminated by removing an arbitrary item from agent j s bundle. Clearly, EFX is a stronger fairness notion than EF1. The existence of EFX allocations is largely open. We only know that EFX allocations exist in some special cases, e.g., two agents with general valuations (Plaut and Roughgarden 2020) and three agents with additive valuations (Chaudhury, Garg, and Mehlhorn 2020). Other notable indivisible fairness notions include proportionality up to one item (PROP1) (Conitzer, Freeman, and Shah 2017), maximin share (MMS) fairness (Budish 2011), and so on. These notions are also extended to incorporate agents weights or entitlements such as weighted EF1 (Chakraborty et al. 2021), weighted PROP1 (Aziz, Moulin, and Sandomirskiy 2020) and weighted MMS (Farhadi et al. 2019). Previous work also considers partial allocations. Caragiannis, Gravin, and Huang (2019) show that there exist partial EFX allocations that have high Nash social welfares. Chaudhury et al. (2021b) show that partial EFX allocations exist if the number of unallocated goods is at most n 1. Furthermore, Chaudhury et al. (2021a) prove that there always exists a (1 ϵ)-EFX allocation with 64(n/ϵ)4/5 unallocated goods and high Nash welfare. The bound of the size of unallocated goods has been respectively improved to O n0.67

for any ϵ (0, 1

2] by Berendsohn, Boyadzhiyska, and Kozma (2022) and O (n/ϵ)2/3 by Akrami et al. (2022). For four agents, Berger et al. (2022) give a method that computes an EFX allocation while leaving at most one item unallocated. Another related fairness notion of EFPRIOR is called local envy-freeness (proposed by (Beynier et al. 2019)), in which each agent is only required to not envy her neighbors on an underlying social network. However, two agents connected by an edge are treated symmetrically with neither of them being prioritized. On the other hand, strict envy-freeness is imposed from each prioritized agent to each non-prioritized agent in our notion EFPRIOR.

2 Preliminaries

A set M of m indivisible items is allocated to a set N of n agents. Each agent i has a valuation function vi : {0, 1}m R 0 that specifies a non-negative value to a bundle/set of

items.2 The valuation function vi is assumed to be

normalized: vi( ) = 0; monotone: vi(S) vi(T) for any T S M.

A (complete) allocation (A1, . . . , An) is a partition of M, where Ai is the set of items allocated to agent i. A partial allocation (A1, . . . , An, B) is a partition of M into n + 1 subsets, where the extra subset B is the set of unallocated items. In this paper, unless specified otherwise, an allocation means a complete allocation. We will only consider partial allocations in Sect. 4. In a complete or partial allocation, we say that agent i envies agent j if vi(Ai) < vi(Aj). That is, according to agent i s utility function, agent i believes her own bundle Ai has less value than agent j s bundle Aj. An allocation is envy-free if i does not envy j for any pair of agents i and j. An envy-free allocation may not exist in the problem of allocating indivisible items (e.g., when m < n). A wellknown common relaxation of envy-freeness, envy-freeness up to one item (EF1), is defined below.

Definition 1. An allocation (A1, A2, . . . , An) is said to satisfy envy-freeness up to one item (EF1), if for any two agents i and j, there exists an item g Aj such that vi(Ai) vi(Aj \ {g}).

EF1 on partial allocations can be defined analogously. For a verbal description, in an EF1 allocation, after removing some item g from agent j s bundle, agent i will no longer envy agent j. Given an allocation (A1, . . . , An), we say that agent i strongly envies agent j if vi(Ai) < vi(Aj \ {g}) for every g Aj. By our definition, an allocation is EF1 if and only if i does not strongly envy j for every pair (i, j) of agents. As it is well-known that EF1 allocations always exist (Lipton et al. 2004), strong envy can always be eliminated. However, as mentioned before, envy may be unavoidable, and in this case we would like to give priority to a specified subset P of agents such that each agent in P does not envy each agent in Q := N \ P.

Definition 2. An allocation (A1, . . . , An) is envy-free with respect to the set of prioritized agents P if 1) the allocation is EF1, and 2) i does not envy j for any i P and j Q = N \P. We say EFPRIOR with respect to P to refer to this, or simply EFPRIOR when the context is clear.

This definition also applies to partial allocations.

2.1 Additive Valuations

When agents valuations are additive (vi(S) = P g S vi({g})), the simple round-robin algorithm always outputs an EFPRIOR allocation if agents in P pick items first. (See the full version of this paper for more details about this.) However, this is not true for general valuations. In the full version of this paper, we provide a counterexample showing that the round-robin algorithm fails to output an EFPRIOR allocation even when valuations are submodular.

2We will use the words bundle and set interchangeably.

2.2 Envy-Graph Lipton et al. (2004) first proposed the tool of envy-graph for finding an EF1 allocation on general valuations. In an envy-graph, each vertex corresponds to an agent, and each directed edge (u, v) represents that agent u envies agent v. The envy-graph procedure to find an EF1 allocation works as follows: it starts with an empty allocation and adjusts the allocation so that the envy-graph is a directed acyclic graph (DAG) before allocating the next item. When there is still an unallocated item, choose an arbitrary source agent (Definition 4) of the envy-graph (so no one envies her), and allocate an item to her; reconstruct the graph according to the new allocation; If there exists a cycle in the envy-graph, we run the cycle-elimination algorithm (defined in Definition 3). The value for each agent is non-decreasing throughout the process after which the envy-graph contains no cycle. It is easy to verify that the (partial) allocation is EF1 throughout the entire procedure. In particular, adding an item g to a source agent i does not destroy the EF1 property, as an agent will not envy i if g is removed from i s bundle. The cycle-elimination step does not destroy the EF1 property either: this step does not change the constituents of each bundle, and each agent receives a bundle with a weakly larger value. Definition 3 (Cycle-Elimination). For a cycle u0 uk 1 u0 on the envy-graph, each agent ui receives the bundle from ui+1 where i {0, 1, . . . , k 1} (indices are modulo k). This is done iteratively until the envy-graph contains no cycle. We will also use the above cycle-elimination algorithm as a subroutine multiple times. The cycle-elimination requires less than n2 iterations, since each iteration removes at least one edge (the edges in the cycle are removed) and there are less than n2 edges. Thus, the envy-graph algorithm always terminates since the number of unallocated items is reduced by one after each iteration. Lastly, we define a few notions that are used. Definition 4. An agent is called a source agent if her corresponding vertex is a source in the envy-graph. Definition 5. An agent i is called a P-source agent if she is a source agent in the subgraph induced by P. Moreover, i is a P-source agent of agent j if she is a P-source agent and j is reachable from i in the subgraph. Definition 6. An agent i is called a Q-source agent if she is a source agent in the envy-graph and i Q. Moreover, i is a Q-source agent of agent j if she is a Q-source agent and j is reachable from i in the envy-graph. All omitted proofs can be found in the full version of our paper (Bu et al. 2022a).

3 Identical Valuations of P or Q This section studies two special cases of general valuations: when agents in P have the same valuation, and when agents

Algorithm 1: Algorithm for computing EFPRIOR allocation satisfying Theorem 7

Output: an EFPRIOR allocation.

1 Let Ai = , for any i N, and B = M;

2 while there exists an item g B do

3 if there exists one source agent i P then

4 Ai Ai {g};

6 Let i be one P-source agent;

7 Let j be one Q-source agent of agent i;

8 Aj Aj {g};

9 if agent i envies j then

10 Add the edge (i, j) to the envy-graph;

11 Eliminate the cycle j i j // there is a path from j to i by Definition 6 and Line 7;

12 B B \ {g};

13 Reconstruct the envy-graph;

14 Run cycle-elimination algorithm (Definition 3);

15 return A

in Q have the same valuation. We design a polynomial-time algorithm that computes an EFPRIOR allocation for each of the two cases. The two algorithms in this section provide some basic ideas for our algorithm in Sect. 4 where we consider general valuations. In the next section, we will see how to extend these ideas to general valuations and the limitations of them. Our results for the two special cases are also interesting on their own. In the applications where P is the underrepresented agents or Q is the over-represented agents, it is natural to assume people in the same group (underrepresented or over-represented) share a similar valuation. In addition, our results immediately apply to the three natural settings: when P = 1, when Q = 1, and when there are 3 agents. We first consider the case where all agents in P have identical valuations by using Algorithm 1. Lines 3-4 consider the simple case where an item can be directly assigned to one source agent in P, while Lines 6-11 try to assign an item to a suitable Q-source agent and keep no envy from P to Q by eliminating one envy cycle. Lines 12-14 update the item set B and the envy-graph after adding one item.

Theorem 7. An EFPRIOR allocation always exists and can be found in polynomial time when all agents in P have identical valuations.

Proof. The cycle-elimination step at Line 14 always makes the envy-graph a DAG, which validates Line 6 and 7. It can then be easily checked that Algorithm 1 always terminates in polynomial time. It suffices to show the allocation returned by Algorithm 1 is EFPRIOR. Since the empty allocation at the beginning is a partial EFPRIOR allocation, we just need to show the allocation is still a partial EFPRIOR allocation after each iteration of the while-loop. We first consider the simple case where we can find one

source agent i P (Lines 3-4). Before allocating item g, there is no envy to agent i and no envy from P to Q from the definition of source agent and partial EFPRIOR allocation. Thus, after allocating g to agent i, there is no strong envy to agent i (as the envy is eliminated if g is removed from i s bundle), and there is no envy from P to Q by the monotonicity of valuation functions. This is still a partial EFPRIOR allocation. We then consider the case where there is no source agent in P (Lines 6-11). We first denote i as one P-source agent and j as one Q-source agent of i. As mentioned, since the envy-graph is a DAG, there must exist such agents i and j. After allocating item g to agent j, two cases may happen:

Agent i does not envy j. Since all agents in P have identical valuations and i is a P-source agent, we have uk(Ak) ui(Ai) ui(Aj {g}) = uk(Aj {g}) for each agent k P, so there is no envy from P to Q. There is no strongly envy to agent j because there is no envy to agent j before allocating item g. Agent i envies j. We will eliminate the cycle including j and i. Since i is a P-source agent and the only agent in P whose bundle is reallocated to an agent in Q is agent i, there is no envy from P to Q. Because the bundle Aj is held by one source agent before allocating g and each agent in the cycle gets a better bundle, there is still no strongly envy.

In both two cases above, the allocation is still a partial EFPRIOR allocation. From the fact that there is no envy edge from P to Q, there is no envy cycle containing agents in P and Q at the same time, so Line 12-14 keep the envy-graph acyclic and maintain EFPRIOR.

We then consider the case where all agents in Q have identical valuations. The technique is similar to Algorithm 1, where the only difference is that when there exists no source agent in P, we find and eliminate one envy cycle more carefully. The proof for the following theorem is available in the full version of this paper. Theorem 8. An EFPRIOR allocation always exists and can be found in polynomial time when all agents in Q have identical valuations. From the above two theorems, we can easily get the tractability of the following three natural special cases. Corollary 9. An EFPRIOR allocation always exists and can be found in polynomial time in any of the following settings: when |P| = 1, when |Q| = 1, and when |N| 3.

4 General Valuations In this section, we consider general valuations with no constraint. The main challenge of applying Algorithm 1 to the setting here is that vertices in P may not be well-connected. Consider the following scenario. We have a total of four agents 1, 2, 3, 4 where P = {1, 2} and Q = {3, 4}. After a certain iteration, we have a partial allocation where the envygraph only have two edges (3, 1) and (4, 2). Moreover, for each remaining unallocated item g, it satisfies that 1) adding g to 1 or 2 introduces strong envy, 2) adding g to 3 makes 2

Algorithm 2: Computing a partial EFPRIOR allocation

Output: a partial EFPRIOR allocation satisfying Theorem 10.

1 Let Ai = , for any i N, and B = M;

2 while there exists an applicable rule Uℓdo

3 A, B Uℓ(A, B);

4 Reconstruct the envy-graph;

5 Run cycle-elimination algorithm (Definition 3);

6 return the partial EFPRIOR allocation A

envy 3, and 3) adding g to 4 makes 1 envy 4. Then, the algorithm cannot continue with existing techniques in the previous section. In particular, no cycle appears if we add g to agent 3 or 4, and the partial allocation is no longer EFPRIOR. In the previous setting, the good connections between agents in P ensures that we can always make a cycle appear by carefully selecting an agent to whom an item is added. Nevertheless, we are able to obtain a slightly weaker result for general valuations. We prove that such a partial EFPRIOR allocation always exists: the number of unallocated items is less than the size of both P and Q, and no one envies the unallocated bundle B. We will call the set of the unallocated items the pool.

Theorem 10. For any P N, a partial EFPRIOR allocation (with respect to P) that satisfies the following properties always exists.

|B| < min(|P|, |Q|), and vi(B) vi(Ai) for all i N.

In addition, there is a polynomial-time algorithm that computes such an allocation.

The algorithm shares some similarities with the one proposed by Chaudhury et al. (2021b). However, there are substantial differences in the analysis of the algorithm as the objective is changed from EFX to EFPRIOR. Moreover, our update rule U3 that exchanges an agent s bundle with a set of unallocated items is more technically involved compared to its counterpart in Chaudhury et al. s algorithm. This additional techniques also make our algorithm run in polynomial time, whereas Chaudhury et al. s algorithm runs in pseudopolynomial time.

4.1 The Main Algorithm

The main algorithm is shown in Algorithm 2. Each iteration of Algorithm 2 applies one of the four update rules defined in Algorithms 3, 4 and 5. After that, the envy-graph is reconstructed and cycles in the graph are eliminated. We will prove that the EFPRIOR property is secured after applying any of the four rules, and we will also prove that the cycleelimination step does not destroy the EFPRIOR property.

4.2 Proof of Theorem 10

In this section, we show that the output allocation of Algorithm 2 satisfies all the requirements in Theorem 10.

Algorithm 3: The Update Rules U0 and U1.

1 Function U0(allocation A, pool B):

2 Precondition: There exist an item g B and one source agent i P;

3 Allocate g to i: Ai Ai {g};

4 Update pool: B B \ {g};

5 Function U1(allocation A, pool B):

6 Precondition: There exist an item g B and one source agent i Q such that allocating g to i would not cause any agent in P to envy i;

7 Allocate g to i: Ai Ai {g};

8 Update pool: B B \ {g};

Figure 1: An example envy-graph for rule U2. The solid lines and the dotted lines respectively represent the original edges and newly constructed edges during U2. At the first iteration, item gq0 is allocated to agent q0, and it causes agent p 1 to envy q0. Then we create an edge (p 1, q0), and let one Psource agent of p 1 be p1 and one Q-source agent of p1 be q1. Next, this loop terminates when finding one Q-source agent of p2 is just the previous q0. Finally, these agents form a cycle q0 b p2 p 2 q1 p1 p 1 q0. We remark that the cycle starts and ends at q0 in this example, and the cycle may start at a middle vertex qi in general.

Below, we prove two properties for the update rule U2. The first proposition follows straightforwardly from Algorithm 4.

Proposition 11. For an edge (i, j) in the cycle at Line 13 of the update rule U2 (Algorithm 4), the followings are true.

1. If i Q and j P, then j is a P-source agent. 2. If j is an agent whose bundle has been updated at Line 7, then i P.

Proof. Both statements hold straightforwardly from the update rule. See the full version for the complete proof.

The second proposition justifies the validity of the update rule U2.

Proposition 12. The while-loop in the update rule U2 (Algorithm 4) will terminate before the unallocated items running out.

Proof. See the full version of this paper.

The following proposition shows that the EFPRIOR property is preserved after applying any of the four update rules.

Algorithm 4: The Update Rule U2

1 Function U2(allocation A, pool B):

2 Precondition: The preconditions of both U0 and U1 are not satisfied, and |B| min(|P|, |Q|);

3 Let p0 P be an arbitrary P-source agent;

4 Find one p0 s Q-source agent q0 Q;

5 A A, i 0;

6 while the envy-graph contains no cycle do

7 Allocate gqi to qi: A qi Aqi {gqi};

8 Let p i+1 P be one agent who envies A qi;

9 Add the edge (p i+1, qi) in the envy-graph;

10 Let pi+1 be one P-source agent of p i+1;

11 Let qi+1 be one Q-source agent of pi+1;

12 i i + 1;

13 Let u0 uk 1 u0 be the cycle consisting of the segments qi pi p i ;

14 Aui A ui+1 for each i (indices are modulo k);

15 Update the pool B: B M \ (Sn i=1 Ai);

Proposition 13. For a partial EFPRIOR allocation, the allocation is still EFPRIOR after applying one iteration for any of U0, U1, U2, and U3.

Proof. For the first three rules, the allocation remains EF1 as the envy-graph procedure claims (see Sect. 2.2). Hence, we only need to prove that, for every agent in p P and q Q, agent p does not envy agent q. When rules U0 and U1 are applicable, it is easily checked by their preconditions. We then analyze the rule U2. Let U = {u0, . . . , um} be the set of vertices in the cycle at Line 13 of Algorithm 4. We discuss the following two cases of q. Note that in both cases, the value of agent p s bundle would not decrease.

q / U : In this case, agent q will still receive her old bundle. Hence, p still will not envy q. q U: Agent q would take the bundle from her adjacent agent (denote this agent as r) at Line 14. We consider two sub-cases: r P and r Q. If r P, according to the first part of Proposition 11, r must be a P-source agent. In this case, no agent in P envies r before the reallocation (Line 14), so no agent in P envies q after the reallocation. If r Q, according to the second part of Proposition 11, r cannot be an agent whose bundle has been updated at Line 7 as q Q. Since p does not envy r before applying U2, p will not envy q after applying rule U2. Thus, p will not envy q in both cases.

Now we come to rule U3. Rule U3 consists of two cases: the envy-graph forms a cycle at Line 21, or no cycle is formed and the unallocated items run out. In the first case, the bundle S will get back to the pool, and the correctness is the same as rule U2. In the second case, the allocation is EF1 because all agents do not strongly envy S (by our construction of S with iterative addition of one item) and other items are added to the source agents such that each source

Algorithm 5: The Update Rule U3.

1 Function U3(allocation A, pool B):

2 Precondition: The preconditions of both U0 and U1 are not satisfied, and there exists one agent that envies the unallocated bundle B;

3 B B, S , i 0, A A;

4 while no agent envies S do

5 Add an item g B to S;

6 B B \ {g};

7 if there exists s P that envies S then

8 Let p be one P-source agent of s;

9 Let q0 be one Q-source agent of p;

11 Let s be one agent in Q that envies S;

12 Let q0 be one Q-source agent of s;

13 while B = do

14 Allocate gqi to qi: A qi Aqi {gqi};

15 Let p i+1 P be one agent who envies A qi;

16 Add the edge (p i+1, qi) in the envy-graph;

17 Let pi+1 be one P-source agent of p i+1;

18 Let qi+1 be one Q-source agent of pi+1;

19 i i + 1;

20 if the envy-graph contains a cycle then

21 Terminate U3 and apply U2 from Line 13;

22 Let u0 uk be the path from qi to s;

23 Update pool: B Aqi;

24 Aui A ui+1 for i [1, k 1], Auk S;

agent receives at most one extra item. Next, we prove that any agent p P will not envy agent q Q. It is worth noting that all agents valuations to their own bundle will not decrease. We consider the following three cases:

If q is not on the path, her bundle stays the same and p s valuation will not decrease. Hence, p will not envy q. If q = s where s Q, p does not envy q. Otherwise, she will take the bundle S according to Algorithm 5. If q = s is an agent on the path, during the reallocation process, she will receive a bundle from her adjacent agent, that is, an agent in Q or a P-source agent. p does not envy these two kinds of agents before the reallocation process and, after reallocation, her valuation to her bundle will not decrease, so she will not envy q.

Overall, the allocation is still EFPRIOR after applying any of U0, U1, U2 and U3.

The following proposition shows that the cycleelimination at Line 5 of our main algorithm (Algorithm 2) does not destroy the EFPRIOR property. The proposition follows from that each cycle cannot contain vertices from both P and Q (since there is no edge from P to Q).

Proposition 14. For a partial EFPRIOR allocation, running cycle-elimination on the envy-graph does not violate the EFPRIOR property.

Proof. Since there is no edge from P to Q, the possible cycles in the envy-graph will involve vertices only in P or only in Q. Since the cycle-elimination operation is a permutation of the previous allocation inside P or Q and everyone on the cycle gets a new bundle with higher valuation, the allocation is EF1 and no new edge occurs from P to Q.

With the propositions above, it is easy to show by induction that the allocation output by our main algorithm is EFPRIOR. After showing that the output allocation is EFPRIOR, the preconditions of rule U2 and U3, we conclude that the two requirements in Theorem 10 holds. It remains to analyze the algorithm s time complexity. The time complexity of Algorithm 2 is given below.

Theorem 15. The time complexity of Algorithm 2 is O(n2m max(n2, m)).

Proof. It is straightforward to compute the time complexity for each update rule. The overall time complexity for one while-loop iteration of Algorithm 2 is O(n2 max(n2, m)). (See the full version of this paper.) We further claim that the while-loop at Algorithm 2, Line 2 is executed for a polynomial number of iterations. The only case in the while loop that increases the size of the pool is when U3 is applied and no cycle is formed. The updated pool becomes a bundle from a previous Q-source agent, so no one envies the pool immediately after applying this rule. This operation may cause |B| min{|P|, |Q|}, and the while loop continues. However, during the application of the four rules, each agent s valuation to her bundle does not decrease, so no one will envy the pool anymore, and the precondition for U3 will never be satisfied. Hence, the case may appear only once and increase the size of the pool by at most m. In other cases, each application of the rules will decrease the size of the pool by at least one. Hence, the while-loop will run for at most 2m iterations. Hence, we may conclude that the time complexity of Algorithm 2 is O(n2m max(n2, m)) which is a polynomialtime algorithm.

5 Conclusion and Open Problems

In this paper, we studied fair division with prioritized agents. In particular, we proposed a new notion EFPRIOR that is stronger than EF1 by allowing the allocation favors a prescribed subset of prioritized agents justified by some factors secondary to fairness. For general valuations, we proposed a polynomial-time algorithm that computes a partial EFPRIOR allocation where the set of unallocated items has small values to all agents and a small cardinality. We believe the existence and the computational tractability of a complete EFPRIOR allocation is an important open problem. Other than the settings with infinitely divisible resources (i.e., cake-cutting) and indivisible items, the setting with mixed divisible and indivisible items has received significant attention recently (Bei et al. 2021a,b). Another future direction is to extend our EFPRIOR notion to this setting.

Acknowledgments The research of Biaoshuai Tao was supported by the National Natural Science Foundation of China (Grant No. 62102252). The research of Shengxin Liu was partially supported by the National Natural Science Foundation of China (Grant No. 62102117), by the Shenzhen Science and Technology Program (Grant No. RCBS20210609103900003), by the Department of Education of Guangdong Province (Innovative Research Program: 2022KTSCX214), and by the Guangdong Basic and Applied Basic Research Foundation (Grant No. 2023A1515011188), and was partially sponsored by CCF-Huawei Populus Grove Fund (Grant No. CCFHuawei LK2022005).

References Akrami, H.; Chaudhury, B. R.; Garg, J.; Mehlhorn, K.; and Mehta, R. 2022. EFX Allocations: Simplifications and Improvements. ar Xiv preprint ar Xiv:2205.07638. Amanatidis, G.; Aziz, H.; Birmpas, G.; Filos-Ratsikas, A.; Li, B.; Moulin, H.; Voudouris, A. A.; and Wu, X. 2022. Fair division of indivisible goods: A survey. ar Xiv preprint ar Xiv:2208.08782. Aziz, H.; and Mackenzie, S. 2016. A Discrete and Bounded Envy-Free Cake Cutting Protocol for Any Number of Agents. In Proceedings of the Annual IEEE Symposium on Foundations of Computer Science (FOCS), 416 427. Aziz, H.; Moulin, H.; and Sandomirskiy, F. 2020. A Polynomial-Time Algorithm for Computing a Pareto Optimal and Almost Proportional Allocation. Operations Research Letters, 48(5): 573 578. Bei, X.; Chen, N.; Hua, X.; Tao, B.; and Yang, E. 2012. Optimal Proportional Cake Cutting with Connected Pieces. In Proceedings of AAAI Conference on Artificial Intelligence (AAAI), 1263 1269. Bei, X.; Chen, N.; Huzhang, G.; Tao, B.; and Wu, J. 2017. Cake Cutting: Envy and Truth. In Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI), 3625 3631. Bei, X.; Li, Z.; Liu, J.; Liu, S.; and Lu, X. 2021a. Fair Division of Mixed Divisible and Indivisible Goods. Artificial Intelligence, 293: 103436. Bei, X.; Liu, S.; Lu, X.; and Wang, H. 2021b. Maximin Fairness with Mixed Divisible and Indivisible Goods. Autonomous Agents and Multi-Agent Systems, 35(2): 1 21. Berendsohn, B. A.; Boyadzhiyska, S.; and Kozma, L. 2022. Fixed-point cycles and EFX allocations. In Proceedings of the International Symposium on Mathematical Foundations of Computer Science (MFCS), 17:1 17:13. Berger, B.; Cohen, A.; Feldman, M.; and Fiat, A. 2022. Almost Full EFX Exists for Four Agents. In Proceedings of the AAAI Conference on Artificial Intelligence (AAAI), 4826 4833. Beynier, A.; Chevaleyre, Y.; Gourv es, L.; Harutyunyan, A.; Lesca, J.; Maudet, N.; and Wilczynski, A. 2019. Local envyfreeness in house allocation problems. Autonomous Agents and Multi-Agent Systems, 33(5): 591 627.

Brams, S. J.; and Taylor, A. D. 1995. An Envy-Free Cake Division Protocol. The American Mathematical Monthly, 102(1): 9 18. Bu, X.; Li, Z.; Liu, S.; Song, J.; and Tao, B. 2022a. Fair Division with Prioritized Agents. ar Xiv preprint ar Xiv:2211.16143. Bu, X.; Li, Z.; Liu, S.; Song, J.; and Tao, B. 2022b. On the Complexity of Maximizing Social Welfare within Fair Allocations of Indivisible Goods. ar Xiv preprint ar Xiv:2205.14296. Budish, E. 2011. The Combinatorial Assignment Problem: Approximate Competitive Equilibrium from Equal Incomes. Journal of Political Economy, 119(6): 1061 1103. Caragiannis, I.; Gravin, N.; and Huang, X. 2019. Envy Freeness Up to Any Item with High Nash Welfare: The Virtue of Donating Items. In Proceedings of the ACM Conference on Economics and Computation (EC), 527 545. Caragiannis, I.; Kurokawa, D.; Moulin, H.; Procaccia, A. D.; Shah, N.; and Wang, J. 2019. The Unreasonable Fairness of Maximum Nash Welfare. ACM Transactions on Economics and Computation (TEAC), 7(3): 12:1 12:32. Chakraborty, M.; Igarashi, A.; Suksompong, W.; and Zick, Y. 2021. Weighted Envy-Freeness in Indivisible Item Allocation. ACM Transactions on Economics and Computation (TEAC), 9(3): 18:1 18:39. Chakraborty, M.; Segal-Halevi, E.; and Suksompong, W. 2022. Weighted Fairness Notions for Indivisible Items Revisited. In Proceedings of the AAAI Conference on Artificial Intelligence (AAAI), 4949 4956. Chaudhury, B. R.; Garg, J.; and Mehlhorn, K. 2020. EFX Exists for Three Agents. In Proceedings of the ACM Conference on Economics and Computation (EC), 1 19. Chaudhury, B. R.; Garg, J.; Mehlhorn, K.; Mehta, R.; and Misra, P. 2021a. Improving EFX Guarantees Through Rainbow Cycle Number. In Proceedings of the ACM Conference on Economics and Computation (EC), 310 311. Chaudhury, B. R.; Kavitha, T.; Mehlhorn, K.; and Sgouritsa, A. 2021b. A Little Charity Guarantees Almost Envy Freeness. SIAM Journal on Computing, 50(4): 1336 1358. Chen, Y.; Lai, J. K.; Parkes, D. C.; and Procaccia, A. D. 2013. Truth, justice, and cake cutting. Games and Economic Behavior, 77(1): 284 297. Conitzer, V.; Freeman, R.; and Shah, N. 2017. Fair Public Decision Making. In Proceedings of the ACM Conference on Economics and Computation (EC), 629 646. Even, S.; and Paz, A. 1984. A note on cake cutting. Discrete Applied Mathematics, 7(3): 285 296. Farhadi, A.; Ghodsi, M.; Hajiaghayi, M.; Lahaie, S.; Pennock, D.; Seddighin, M.; Seddighin, S.; and Yami, H. 2019. Fair Allocation of Indivisible Goods to Asymmetric Agents. Journal of Artificial Intelligence Research, 64(1): 1 20. Fish, S. 1993. Reverse Racism, or How the Pot Got to Call the Kettle Black. Atlantic Monthly, 272(5): 128 136. Foley, D. K. 1967. Resource Allocation and the Public Sector. Yale Economics Essays, 7(1): 45 98.

Goldman, J.; and Procaccia, A. D. 2015. Spliddit: Unleashing Fair Division Algorithms. ACM SIGecom Exchanges, 13(2): 41 46. Kaiser, C. R.; Major, B.; Jurcevic, I.; Dover, T. L.; Brady, L. M.; and Shapiro, J. R. 2013. Presumed Fair: Ironic Effects of Organizational Diversity Structures. Journal of Personality and Social Psychology, 104(3): 504. Li, Z.; Bei, X.; and Yan, Z. 2022. Proportional Allocation of Indivisible Resources under Ordinal and Uncertain Preferences. In Proceedings of the Conference on Uncertainty in Artificial Intelligence (UAI). Lipton, R.; Markakis, E.; Mossel, E.; and Saberi, A. 2004. On Approximately Fair Allocations of Indivisible Goods. In Proceedings of the ACM Conference on Electronic Commerce (EC), 125 131. Newkirk, V. R.; and Vann, R. 2017. The Myth of Reverse Racism. The Atlantic, 5. Plaut, B.; and Roughgarden, T. 2020. Almost Envy-Freeness with General Valuations. SIAM Journal on Discrete Mathematics, 34(2): 1039 1068. Shah, N. 2017. Spliddit: Two years of Making the World Fairer. XRDS: Crossroads, The ACM Magazine for Students, 24(1): 24 28. Steinhaus, H. 1948. The Problem of Fair Division. Econometrica, 16(1): 101 104. Tao, B. 2022. On Existence of Truthful Fair Cake Cutting Mechanisms. In Proceedings of the ACM Conference on Economics and Computation (EC), 404 434.