Paper deep dive
Multilevel Fair Allocation under Additive Preferences
Maxime Lucet, Nawal Benabbou, Aurélie Beynier, Nicolas Maudet
Intelligence
Status: succeeded | Model: Gemma-4-26B-A4B | Prompt: intel-v1 | Confidence: 91%
Last extracted: 8/29/2026, 4:36:44 AM
Summary
This paper studies multilevel fair resource allocation within tree-structured hierarchical relations among agents. It proposes multilevel adaptations of envy-based fairness notions (WEF1, WEFX) using three estimation functions: pessimistic, agnostic, and optimistic. The authors prove that under identical preferences, these notions coincide and are guaranteed by the Multilevel extension of Weighted Round Robin (MWRR). Under general additive preferences, MWRR guarantees the pessimistic notion but may fail others, though experiments show it performs well empirically.
Entities (10)
Relation Signals (6)
Leaves → have → Additive Preferences
confidence 95% · the leaves have classical additive utilities over items
Internal Nodes → uses → Utilitarian Welfare
confidence 95% · Assuming that internal nodes' utilities are the utilitarian welfare of their children
MWRR → guarantees → M-WEFX
confidence 90% · under identical preferences... the Multilevel extension of Weighted Round Robin (MWRR) guarantees them.
WEF1 → isadaptedto → Multilevel Fair Allocation
confidence 90% · we first propose multilevel adaptations of usual envy-based fairness notions (e.g., WEF1).
MWRR → guarantees → Pessimistic Estimation
confidence 85% · Although the MWRR guarantees the pessimistic adaptation, it fails to satisfy the stronger ones.
Chakraborty et al. → proposed → Weighted Round Robin
confidence 80% · Multilevel extension of Weighted Round Robin (Chakraborty et al., 2021)
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
Abstract:We study multilevel fair resource allocation with tree-structured hierarchical relations among agents. At each level, the problem can be viewed locally as allocating an agent's bundle to its children, the overall allocation being a trace of this process iterated down to the leaves. Assuming that internal nodes' utilities are the utilitarian welfare of their children, and the leaves have classical additive utilities over items, we first propose multilevel adaptations of usual envy-based fairness notions (e.g., WEF1). We present three adaptations and show that the choice among them is not neutral. We prove that, under identical preferences, the three adapted envy-based notions coincide, and that the Multilevel extension of Weighted Round Robin (Chakraborty et al., 2021) (MWRR) guarantees them. We then show that under general preferences, MWRR may guarantee some notions while failing others. Finally, through experiments, we show that MWRR may still perform well even for adaptations it does not formally guarantee.
Tags
Links
- Source: https://arxiv.org/abs/2608.24400v1
- Canonical: https://arxiv.org/abs/2608.24400v1
Trouble viewing inline? Open PDF directly →
Full Text
86,569 characters extracted from source content.
Expand or collapse full text
Multilevel Fair Allocation under Additive Preferences Maxime Lucet Nawal Benabbou Aurélie Beynier Nicolas Maudet E-mail Email: firstname.lastname@lip6.fr Affiliation: LIP6, CNRS, Sorbonne Université, F-75005 Paris, France Abstract We study multilevel fair resource allocation with tree-structured hierarchical relations among agents. At each level, the problem can be viewed locally as allocating an agent’s bundle to its children, the overall allocation being a trace of this process iterated down to the leaves. Assuming that internal nodes’ utilities are the utilitarian welfare of their children, and the leaves have classical additive utilities over items, we first propose multilevel adaptations of usual envy-based fairness notions (e.g., WEF1). We present three adaptations and show that the choice among them is not neutral. We prove that, under identical preferences, the three adapted envy-based notions coincide, and that the Multilevel extension of Weighted Round Robin [11] (MWRR) guarantees them. We then show that under general preferences, MWRR may guarantee some notions while failing others. Finally, through experiments, we show that MWRR may still perform well even for adaptations it does not formally guarantee. Keywords: Fair division Computational Social Choice Resource allocation. 1 Introduction Fair allocation has traditionally focused on designing algorithms to allocate fairly resources between individual agents [10, 16], and was then later extended to groups [4, 11, 15, 3, 14]. However, in many real-world settings, agents/groups actually belong to higher level entities, ultimately forming a hierarchical structure. Such hierarchy can be naturally modelled by a directed tree, where the root is responsible for allocating the bundle of items it receives to its children. This new setting, called multilevel fair allocation, was recently formalized in [17]. Multilevel fair allocation problems can arise in multiple real-world situations. For instance, consider a food charity operating in a country with multiple administrative levels: regional branches oversee departmental units, which in turn manage city-level distribution centres with potentially heterogeneous supply needs (see Fig. 2 for an illustration). In such a setting, fairness should be enforced locally at each level of the hierarchy (e.g., among departments within a region or among cities within a department), rather than across levels, as entities at different levels are not directly comparable. Note that many allocation problems across territories, or within a hierarchical structure, can be covered by this multilevel setting. Interestingly, this setting can be useful even in contexts where no explicit hierarchy exists. For instance, when assigning medical resources to patients characterized by severity, age, and risk level, one may first prioritize fairness across severity (e.g., giving higher priority to the most severe cases), then within severe cases place greater weight on high-risk patients, while for less severe cases one may instead balance allocation across age groups to avoid age bias (see Fig. 2 for an illustration). Such implicit hierarchy may also arise in affirmative action schemes. 1: Food charity2: RegionA4: CityA5: CityB3: RegionB6: CityC7: CityD Figure 1: Hierarchical structure of a food charity. HospitalLow-severity<18<18 years18−4518-45 years>45>45 yearsHigh-severityHigh-riskLow-risk Figure 2: Example of implicit hierarchy. In this paper, we assume that intermediary nodes act solely as representative bodies of their constituents (as in [17]), and therefore receive items only to allocate them to their children. These entities derive utility from the satisfaction of their constituents11 1 Other assumptions could have been made, e.g., they could be oblivious of how the items are allocated to their children, or only care about the properties of the allocation to their children., and we adopt the utilitarian social welfare as an aggregation rule (following [17]), which is a standard modelling choice in collective decision-making. However, while [17] assume matroid-rank utilities at the leaves, we assume additive preferences. The additive utility model is the most studied preference model in the literature and is more expressive over singletons than matroid-rank utilities. Coming back to our illustrative example, this assumption is natural in the context of food charities (see e.g., [2]). Moreover, we further depart from [17] by considering different notions of fairness. More precisely, they consider welfare-based fairness notions (e.g., Lorenz dominance) ensuring that, under matroid-rank utilities, a utilitarian-optimal solution is also fair. In contrast, we consider envy-based fairness notions. A central notion of fairness in classical fair division is envy-freeness (EF), together with its relaxations: envy-freeness up to one good (EF1) [10] and envy-freeness up to any good (EFX). Recent works have also examined weighted variants of these criteria [11, 12], namely WEF1 and WEFX. The general idea behind these notions is that no agent should envy the bundle received by another agent, after accounting for the weight differences. In the multilevel setting, envy-based notions require some adaptations. Indeed, an internal node does not observe how an alternative bundle would be allocated among its children, and thus cannot compute the exact utilitarian welfare it would derive from it, but only an estimate. In this paper, we consider three possible estimation functions (pessimistic, agnostic, and optimistic), and we investigate whether a multilevel version of Weighted Round Robin (WRR) [11] can guarantee some of our fairness notions together with completeness (i.e., all items are allocated). In monolevel settings, the Round Robin [10] and WRR are indeed simple algorithms achieving EF1 and WEF1, respectively. Related work. Group fairness has become a highly active topic in fair division [4, 11, 15, 3, 14], and was recently extended to multilevel settings by [17]. While they focus on matroid-rank valuations and fairness notions unrelated to envy, we consider additive valuations and envy-based fairness notions in multilevel settings. However, some previous works can be seen as bilevel settings. [19] study individual and group envy-freeness when groups’ valuations depend on those of their members, and propose algorithms guaranteeing fairness at both levels. Our work extends this setting, as well as some of their algorithmic ideas. Closely related, [9] reconcile group and individual perspectives, allowing group preferences that do not necessarily aggregate those of their members (unlike our assumption). However, their model is limited to two levels, whereas ours allows an arbitrary number of levels. Finally, [2] study a bilevel allocation problem motivated by food charities, but focus on auction mechanisms, in contrast with our setting. Our multilevel model is also related to the multilevel apportionment framework of [20], which uses a similar tree-based hierarchy. However, their work focuses specifically on apportionment, a very specific subfield of resource allocation. Finally, the multilevel fairness notions proposed in this paper induce some visibility constraints, which is reminiscent of work on local fairness [1, 5, 8]; for instance, in our model, only labs affiliated to the same department can compare their situations. Contributions. In this paper, we formally study multilevel fair allocation problems, assuming that internal nodes follow a utilitarian welfare objective and that leaves have additive preferences, and focusing on weighted envy-based fairness notions. We first show that WEF1 must be adapted to the multilevel setting, and that the choice of adaptation is not neutral. We propose three adaptations, ranging from the weakest to the strongest: pessimistic, agnostic, and optimistic. Under identical preferences, our three adaptations coincide and can be guaranteed by a multilevel extension of the Weighted Round Robin [11] (MWRR). However, results become more nuanced under general additive preferences. Although the MWRR guarantees the pessimistic adaptation, it fails to satisfy the stronger ones. Nevertheless, we show in Section 4.3 that the algorithm still performs extremely well experimentally with respect to the agnostic fairness notion. 2 Model In this paper, we consider an allocation problem where a set of goods =g1,…,gmG=\g_1,…,g_m\ must be distributed among agents organized in a hierarchical structure. Hierarchical structure. We consider a multilevel allocation problem represented by an arborescence (i.e. a directed rooted tree in which all edges point away from the root) denoted by =(,ℰ)T=(N,E), where =1,…,nN=\1,…,n\ is the set of nodes representing agents and ℰE is the set of arrows representing hierarchical relations among agents. We assume that the nodes are indexed according to a topological ordering of T (hence the root of T is node 11). We also assume that any node i∈i has a weight wi∈ℝ>0w_i _>0, which can be arbitrarily fixed, or can depend on the structure of the tree. For any node i∈i , let h(i)h(i) be the height of i, i.e. the number of arrows in a longest path starting at node i. Let (i)C(i) denote the set of children of i, which is defined by (i)=j∈:(i,j)∈ℰC(i)\!=\!\j\!∈\!N\!:\!(i,j)\!∈\!E\. Let (i)P(i) be the parent of i, which is the unique node such that ((i),i)∈ℰ(P(i),i) , and (1)=∅P(1)= . Moreover, let Anc(i)Anc(i) be the set of its ancestors, i.e. nodes belonging to the unique path from 11 to i (including i itself). For any node i, let i=(i,ℰi)T_i=(N_i,E_i) denote the subtree of T rooted at i, consisting of all nodes and edges belonging to paths that start at i. Let ℒ(i)L(i) be the set of leaves of iT_i, formally defined as ℒ(i)=j∈i:(j)=∅L(i)=\j _i:C(j)= \. Let ℐ(i)I(i) denote the set of internal nodes of iT_i, defined by ℐ(i)=i∖ℒ(i)I(i)=N_i (i). In particular, ℒL and ℐI denote the sets of leaves and internal nodes of the entire tree. For brevity, we write ℐ:=ℐ(1)I:=I(1) and ℒ:=ℒ(1)L:=L(1) throughout the paper, and use ℐ(i)I(i) and ℒ(i)L(i) when referring to a specific subtree. Allocations. We introduce different types of allocations relevant to our setting: Definition 1 (Complete multilevel allocation). π:→2π:N→ 2^G is a multilevel allocation if it satisfies: (i) π(1)=π(1)=G, (i) π(i)⊇∪j∈(i)π(j),∀i∈ℐπ(i) _j (i)π(j),∀ i , and (i) π(i)∩π(j)=∅,∀i,j∈π(i)∩π(j)\!=\! ,∀ i,j such that (i)=(j)P(i)\!=\!P(j), where π(i)π(i) denotes the bundle of any node i∈i . A multilevel allocation π is complete if condition (i) is an equality. We require that the root owns all items (i.e. π(1)=π(1)=G) only to ensure that none are discarded a priori. Moreover, we require that each internal node allocate each of its item to at most one child. The set of all multilevel allocations is denoted by Π hereafter. Definition 2 (Restricted multilevel allocation). Given a multilevel allocation π∈Ππ∈ and a set of nodes N⊆N , the restriction of π to the nodes in N is denoted by π|Nπ|_N and defined by π|N=(π(i))i∈Nπ|_N=(π(i))_i∈ N. Definition 3 (Local allocation). Given a set of nodes N⊆N and a set of items S⊆S , A:N→2SA:N→ 2^S is a local allocation if (i) ∪i∈NA(i)⊆S _i∈ NA(i) S and (i) A(i)∩A(j)=∅A(i)∩ A(j)= for all i,j∈Ni,j∈ N. Such a local allocation A is complete if condition (i) is an equality. For any N⊆N and S⊆S , let NSA^S_N denote the set of corresponding complete local allocations. Note that, for any complete multilevel allocation π∈Ππ∈ and any node i∈ℐi , the restricted allocation π|(i)π|_C(i) is a complete local allocation belonging to (i)π(i)A^π(i)_C(i). Utility model. Let vi:Π→ℝ≥0v_i: _≥ 0 be the utility function of node i∈i , and let v=(vi)i∈v=(v_i)_i . For any internal node i∈ℐi and any multilevel allocation π∈Ππ∈ , vi(π)v_i(π) quantifies some concept of overall welfare derived by the children of i from π. We focus here on the utilitarian social welfare, i.e. vi(π)=∑j∈(i)vj(π)v_i(π)= _j (i)v_j(π) Hence, we assume that internal nodes have additive utilities over their children. Note that, by linearity of summation, vi(π)v_i(π) can be rewritten as vi(π)=∑x∈ℒ(i)vx(π)v_i(π)= _x (i)v_x(π), where the sum ranges over the leaves of the subtree iT_i. In contrast, leaves have no children and are here equipped with standard additive utilities: any leaf x∈ℒx is associated with a utility function ux:2→ℝ≥0u_x:2^G _≥ 0 such that vx(π)=ux(π(x))v_x(π)=u_x(π(x)) for any multilevel allocation π∈Ππ∈ . Formally, ux(∅)=0u_x( )=0 and ux(S)=∑g∈Sux(g)u_x(S)= _g∈ Su_x(g) for any bundle S⊆S , where ux(g)u_x(g) is a slight abuse of notation for ux(g)u_x(\g\). Estimated utility functions. Our goal is to compute a multilevel allocation that is both complete and fair. We focus on envy-based fairness notions, which typically require that each agent values its own bundle at least as much as any other agent’s bundle. Such notions rely on agents being able to evaluate bundles directly. However, in our setting, utility functions vi,i∈ℐv_i,i , are defined over multilevel allocations rather than bundles of items. As a result, standard envy-based notions cannot be applied directly. We therefore begin by introducing a method to evaluate bundles. As highlighted by [19], there are two ways to do so: (i) we can assume that i computes an allocation of its bundle S within iT_i, in which case its estimated utility is the sum of its children’s (equivalently, leaves’) utilities, or (i) we can assume that i is agnostic to the allocation, and its estimated utility is the weighted average of S over the leaves in ℒ(i)L(i). In this paper, we investigate both propositions. For (i), we propose two natural approaches: the first one, which we call the optimistic approach, assumes that i computes a utilitarian-optimal allocation of S to its leaves ℒ(i)L(i), while the pessimistic approach assumes that i compute an allocation of S to ℒ(i)L(i) minimizing the utilitarian-welfare. Definition 4 (Optimistic estimated utility function). Given a node i∈i and a subset of items S⊆S , the optimistic estimated utility function of i for S is v∧i(S)=maxA∈ℒ(i)S∑x∈ℒ(i)∑g∈A(x)ux(g) v_i(S)= _A ^S_L(i) _x (i) _g∈ A(x)u_x(g) Definition 5 (Pessimistic estimated utility function). Given a node i∈i and a subset of items S⊆S , the pessimistic estimated utility function of i for S is v∨i(S)=minA∈ℒ(i)S∑x∈ℒ(i)∑g∈A(x)ux(g) v_i(S)= _A ^S_L(i) _x (i) _g∈ A(x)u_x(g) For (i), we refer to the weighted average evaluation of bundle S as the agnostic approach. On the contrary of the optimistic and pessimistic approaches, the agnostic approach does not assume a specific allocation to the leaves, and measures the value of a bundle as a weighted average utility over all leaves in ℒ(i)L(i). Definition 6 (Agnostic estimated utility function). Given a node i∈i and a subset of items S⊆S , the agnostic estimated utility function of i for S is v¯i(S)=∑x∈ℒ(i)∑g∈Sux(g)×W(x,i) with W(x,i)=Πk∈Anc(x)∖Anc(i)wkw((k)) v_i(S)= _x (i) _g∈ Su_x(g)× W(x,i) with W(x,i)= _k∈ Anc(x) Anc(i) w_kw_C(P(k)) where w((k))=∑k′∈((k))wk′w_C(P(k))= _k (P(k))w_k . For any internal node i∈ℐi and leaf x∈ℒ(i)x (i), W(x,i)W(x,i) can be interpreted as the weight of x in the subtree iT_i. The quantity W(i,j)W(i,j) is defined similarly for any node i∈i and ancestor j∈Anc(i)j∈ Anc(i). Moreover, Appendix B shows that ∑x∈ℒ(i)W(x,i)=1 _x (i)W(x,i)=1. Note that, for any leaf x∈ℒx , we have v∧x(S)=v¯x(S)=v∨x(S)=ux(S) v_x(S)= v_x(S)= v_x(S)=u_x(S) for any bundle S⊆S , since leaf x is a tree with only one node (and thus ℒ(x)=xL(x)=\x\). Fairness. Having defined the estimation functions, we can propose some multilevel extensions of some envy-based notions. This definition is parametrized to accommodate our three estimated utility functions. Definition 7 (M[ℰE]-WEF). Multilevel allocation π∈Ππ\!∈\! is estimated Multilevel Weighted Envy-Free for ℰ∈pess,agno,optE∈\pess,agno,opt\ (denoted by M[ℰE]-WEF), if for any internal node i∈ℐi , and any pair of children j,k∈(i)j,k (i), we have vj(π)wj≥v~j(π(k))wk v_j(π)w_j≥ v_j(π(k))w_k where v~ v denotes v∧ v, v¯ v or v∨ v for ℰ=pessE=pess, agno, or opt, respectively. The definition of M[ℰE]-WEF1 is obtained by simply requiring vj(π)wj≥v~j(π(k)∖g)wk v_j(π)w_j≥ v_j(π(k) \g\)w_k for some item g∈π(k)g∈π(k). For M[ℰE]-WEFX, this must hold for all items g∈π(k)g∈π(k). Note that, if T has height h(1)=1h(1)\!\!=\!\!1, the problem reduces to a standard monolevel allocation setting, and our three estimated fairness notions coincide with the classical WEF, WEF1, and WEFX notions. Example 1 We now illustrate the different estimated utility functions. Assume an instance with =1,…,7N=\1,…,7\ organized as in Fig 2, and =g1,…,g5G=\g_1,…,g_5\. Leaves 4 and 6 have the following preferences ux(g)=2u_x(g)=2 for x∈4,6x∈\4,6\ and any g∈g ; leaves 5 and 7 have the following preferences ux(g)=1u_x(g)=1 for x∈5,7x∈\5,7\ and any g∈g . Assume the weight of any node i∈i is wi=|ℒ(i)|w_i=|L(i)|. Suppose we have the multilevel allocation π∈Ππ∈ such that π(4)=g1,g5π(4)=\g_1,g_5\, π(5)=g3π(5)=\g_3\, π(6)=g2π(6)=\g_2\, and π(7)=g4π(7)=\g_4\. By definition, π(2)=g1,g3,g5π(2)=\g_1,g_3,g_5\ and π(3)=g2,g4π(3)=\g_2,g_4\. To assess whether node 33 is envious towards node 22, we need to choose an estimated utility function to estimate the value of 22’s bundle. Depending on which estimated utility functions we choose, the results might differ. Indeed, in this example, we can see that: v∧3(π(2)∖g1)=4 v_3(π(2) \g_1\)=4 since all items are allocated to leaf 66 in a utilitarian-optimal allocation ; v¯3(π(2)∖g1)=3 v_3(π(2) \g_1\)=3 ; and finally, v∨3(π(2)∖g1)=2 v_3(π(2) \g_1\)=2 since all items are allocated to leaf 77 to minimize the utilitarian-welfare. Hence, the conclusions on whether 33 envies 22 would differ based on which notion you use: according to the optimistic function, 33 is weighted envious towards 22 even up to one good, while according to both agnostic and pessimistic, 33 is weighted envy-free towards 22 up to one good. 3 Identical additive valuations In [19], the authors propose algorithms achieving strong fairness guarantees under two assumptions: (i) all agents share identical preferences, and (i) agents within the same group share identical preferences. We show that their algorithms and arguments extend naturally to our multilevel setting. In our framework, these assumptions translate to: (i) all leaves x∈ℒx have identical preferences, and (i) all leaves within each subtree rooted at a child of the root (i.e., x∈ℒ(i)x (i) for i∈(1)i (1)) have identical preferences; for instance, in our food charity example, branches within the same department may face similar needs and thus share preferences over supplies. We refer to (i) as all-common valuations, and to (i) as root-child-common valuations. Remark 1. Under both all-common and root-child-common valuations, for any internal node i∈ℐ∖1i \1\ and any bundle S⊆S , we have: ∀A,B∈ℒ(i)S,∑x∈ℒ(i)ux(A(x))=∑x∈ℒ(i)ux(B(x)).∀ A,B ^S_L(i), _x (i)u_x(A(x))= _x (i)u_x(B(x)). In other words, the allocation of S to the leaves in ℒ(i)L(i) does not affect the utility derived by i. Consequently, the three estimated utility functions coincide, i.e., v∧i(S)=v¯i(S)=v∨i(S) v_i(S)\!=\! v_i(S)\!=\! v_i(S). Hence the definitions of M[ℰE]-WEF, for ℰ∈E∈ pess, agno, opt, also coincide. Accordingly, in this section, we slightly abuse notation and refer to the value of a bundle even for internal nodes, rather than the value of a multilevel allocation. We also write M-WEF instead of M[ℰE]-WEF for brevity. 3.1 All-common valuations Theorem 3.1 Under all-common valuation, a M-WEFX allocation can be computed in polynomial time. Proof. The following algorithm is a multilevel extension of the algorithm presented in the proof of Theorem 3.1 in [19]. Order the goods in decreasing order of preferences. Starting at the root, select the child with the least weighted bundle value (i.e. the utility of the bundle divided by the weight of the node). If this child is not a leaf, repeat the selection process until selecting a leaf, denoted x∈ℒx . Allocate the first remaining item (i.e. the highest-value remaining item) to the selected leaf. At any point in time, the leaf we selected (or any of its ancestors) cannot be weighted envied before the allocation of the new item by one of its siblings (as it has the least valued bundle). Any envy that forms towards any of the nodes i∈Anc(x)i∈ Anc(x) can only result of the latest good allocated, and any envy will disappear upon dropping this good. Moreover, this good is also the least valued one in i’s bundle, by construction. The resulting multilevel allocation is thus M-WEFX. Furthermore, the algorithm is polynomial: sorting the goods is polynomial-time doable, the leaf-selection process is in O(n)O(n), and allocating the chosen item at an iteration also takes O(n)O(n). ∎ We then show that we can obtain M-WEF1 jointly with some (monolevel) fairness notion at the leaves. The full proof and the algorithm can be found in the appendix. One component of the algorithm presented in the appendix is the Multilevel Weighted Round Robin, presented in Algorithm 1 in Section 3.2. Theorem 3.2 Under all-common valuations and wi=|ℒ(i)|w_i=|L(i)| for all i∈i , there exists a polynomial-time algorithm that returns an allocation that is M-WEF1 and EFX between all leaves in ℒL. 3.2 Root-child-common valuations We now present a multilevel extension of the Weighted Round Robin (WRR) algorithm from [11, 19]. The principle of our algorithm, which we call Multilevel Weighted Round Robin (MWRR), is the following: each node i∈i is equipped with a picking score tit_i which counts the number of times i was picked by the MWRR, and this picking score is weighted by i’s weight. Then, starting at the root, MWRR picks the child i∈(1)i (1) minimizing this picking score (breaking ties lexicographically). If i is an internal node, we repeat the selection process, i.e. we select the child j∈(i)j (i) which minimizes the picking score, until the selected node is a leaf. Once it is the case, the selected leaf gets to choose her preferred item among the remaining ones. We repeat this procedure until all items are allocated. For the leaf selection procedure, ties are broken differently depending on whether they occur between internal nodes or leaves: (i) among internal nodes, ties are broken lexicographically; (i) among leaves, they are broken in favor of the leaf with the highest utility for any remaining item. If the children of the considered node is a mix of internal nodes and leaves, we use (i). Pseudocode can be found in Algorithm 1. Algorithm 1 Multilevel Weighted Round Robin (MWRR) 1: Input: T - a multilevel tree ; G - a set of items ; the leaves’ valuations (ux)x∈ℒ(u_x)_x 2: Output: π - a multilevel allocation 3: Initialize π with empty bundle for any i∈∖1i \1\ and π(1)=π(1)=G 4: Initialize picking scores s.t. ti=0,∀i∈t_i=0,∀ i 5: ℛℐ←RI ⊳ Initial set of remaining items 6: while ℛℐ≠∅RI≠ do 7: i=argmini′∈(1)ti′wi′i= _i (1) t_i w_i 8: while i∉ℒi do 9: i=argmini′∈(i)ti′wi′i= _i (i) t_i w_i 10: end while 11: g=argmaxg′∈ℛℐui(g′)g= _g u_i(g ) 12: while i≠1i≠ 1 do 13: π(i)←π(i)∪gπ(i)←π(i)∪\g\ 14: ti←ti+1t_i← t_i+1 15: i←(i)i (i) 16: end while 17: ℛℐ←ℛℐ∖gRI \g\ 18: end while 19: return π Our goal is to study what fairness properties MWRR may guarantee. We first look at its performance under root-child-common additive valuations, and in Section 4, we study thoroughly how fair it is in the general additive case. Theorem 3.3 Under root-child-common valuations and arbitrary weights, the MWRR returns an M-WEF1 allocation in polynomial time. Proof. We first show that the MWRR runs in polynomial time: the while loop (Line 6) runs in O(m)O(m) steps. Finding the child of the root with minimum weighted picking score (Line 7) is at most in O(n)O(n) (for tree of height 1), and a loose bound for the while loop (Line 8) is O(n2)O(n^2). Finding the item with maximum utility (Line 11) can be done in O(m)O(m), and updating the bundle (Line 12) requires at most O(n)O(n) (in a comb tree). Hence, the complexity of the algorithm is O(m(n2+m))O(m(n^2+m)). Then, recall that for any child of the root, i∈(1)i (1), all leaves in ℒ(i)L(i) have the same preferences over singletons, i.e. ∀x,y∈ℒ(i),∀g∈,ux(g)=uy(g)∀ x,y (i),∀ g ,u_x(g)=u_y(g). Hence, any child of the root i can be seen as an agent with additive utility over items: no matter which of its leaves is chosen at any iteration, node i will receive the same item (as all leaves in ℒ(i)L(i) have the same preferences), which will yield the same utility. Moreover, MWRR at the root chooses a child according to the "least weight-adjusted frequent picker" criterion, exactly like in [11]. Since their algorithm is known to be WEF1 w.r.t. agents with additive utilities over items, we can conclude that MWRR is WEF1 w.r.t. (1)C(1). Then, we can repeat the same argument recursively for any node i∈i . ∎ Corollary 1 Under root-child-common valuations and wi=|ℒ(i)|w_i=|L(i)| for all i∈i , the MWRR is M-WEF1 and EF1 between all leaves in ℒL. Proof. From Theorem 3.3, we know that MWRR satisfies M-WEF1. Furthermore, the proof of Theorem 3.9 in [19] can be extended to our setting and establishes EF1 among the leaves. The full proof can be found in Appendix A. ∎ In this section, we showed that the algorithms proposed in [19] could be extended easily to satisfy our multilevel fairness properties, namely M-WEF1 and M-WEFX, sometimes even jointly with fairness at the leaves. In Section 4 we discuss how to extend our multilevel fairness notions under general additive valuations. 4 General additive valuations We now focus on the more general case where we have general additive valuations. 4.1 Relations among M[ℰE]-WEF1 notions We formally establish the hierarchy between the adaptations we presented. Lemma 1 For any internal node i∈ℐi and bundle S⊆S , we have v∧i(S)≥v¯i(S) v_i(S)≥ v_i(S). Proof. By linearity, v¯i(S) v_i(S) and v∧i(S) v_i(S) can be rewritten as follows: v¯i(S) v_i(S) =∑x∈ℒ(i)∑g∈Sux(g)W(x,i)=∑g∈S∑x∈ℒ(i)ux(g)W(x,i) = _x (i) _g∈ Su_x(g)\,W(x,i)= _g∈ S _x (i)u_x(g)\,W(x,i) v∧i(S) v_i(S) =maxA∈ℒ(i)S∑x∈ℒ(i)∑g∈A(x)ux(g)=∑g∈Smaxx∈ℒ(i)ux(g) = _A ^S_L(i) _x (i) _g∈ A(x)u_x(g)= _g∈ S _x (i)u_x(g) Note that, for any g∈Sg∈ S, both ∑x∈ℒ(i)ux(g)W(x,i) _x (i)u_x(g)\,W(x,i) and maxx∈ℒ(i)ux(g) _x (i)u_x(g) are convex combinations of (ux(g))x∈ℒ(i)(u_x(g))_x (i); the latter places all the weight on some leaf x∗∈argmaxx∈ℒux(g)x^*∈ _x u_x(g), while the former uses weights (W(x,i))x∈ℒ(i)(W(x,i))_x (i), which satisfy ∑x∈ℒ(i)W(x,i)=1 _x (i)W(x,i)=1 (as shown in Appendix B). Since a convex combination is maximized by putting all the weight on the largest element, we obtain: maxx∈ℒ(i)ux(g)≥∑x∈ℒ(i)ux(g)W(x,i). _x (i)u_x(g)≥ _x (i)u_x(g)\,W(x,i). Then, summing over g∈Sg∈ S gives: v∧i(S)=∑g∈Smaxx∈ℒ(i)ux(g)≥∑g∈S∑x∈ℒ(i)ux(g)W(x,i)=v¯i(S). v_i(S)= _g∈ S _x (i)u_x(g)≥ _g∈ S _x (i)u_x(g)\,W(x,i)= v_i(S). ∎ Lemma 2 For any internal node i∈ℐi and bundle S⊆S , we have v¯i(S)≥v∨i(S) v_i(S)≥ v_i(S). Proof. The proof is similar to that of Lemma 1: since v∨i(S) v_i(S) is obtained by placing all weight on the leaf with minimum utility for g, we have ∑x∈ℒ(i)ux(g)W(x,i)≥minx∈ℒ(i)ux(g) _x (i)u_x(g)W(x,i)≥ _x (i)u_x(g), and thus v¯i(S)≥v∨i(S) v_i(S)≥ v_i(S). ∎ These relationships between the estimated utility functions induce an implication structure among the fairness notions. The proof trivially results from Lemmas 1 and 2. Proposition 1 M[opt]-WEF1⇒M[agno]-WEF1⇒M[pess]-WEF1M[opt]-WEF1\; \;M[agno]-WEF1\; \;M[pess]-WEF1. In other words, for any allocation π∈Ππ∈ , if π is not M[pess]-WEF1, then it is not M[agno]-WEF1; similarly, if it is not M[agno]-WEF1, then it is not M[opt]-WEF1. However, some allocations that are not M[opt]-WEF1 may still be M[agno]-WEF1 (e.g., the allocation in Example 1), and some that are not M[agno]-WEF1 may still be M[pess]-WEF1, as shown in the following example. Example 2 We can slightly modify the instance of Example 1 to exhibit a multilevel allocation that is M[pess]-WEF1 but not M[agno]-WEF1. We now have =1,…,9N=\1,…,9\ organized in the tree of Fig. 3. Leaves x=4,5x=4,5 and 77 have utilities ux(g)=2u_x(g)=2 for all g∈g ; leaves x=6,8x=6,8 and 99 have utilities ux(g)=1u_x(g)=1 for all g∈g . Assume the weight of any node i∈ℐi is wi=|ℒ(i)|w_i=|L(i)|, and that of any leaf x∈ℒx is 1. Suppose we have the multilevel allocation π∈Ππ∈ such that π(4)=g1π(4)=\g_1\, π(5)=g3π(5)=\g_3\, π(6)=g5π(6)=\g_5\, π(7)=g2π(7)=\g_2\, π(8)=g4π(8)=\g_4\, and π(9)=∅π(9)= . For such an allocation π, we have v3(π(3))=3v_3(π(3))=3, and for any g∈π(2)g∈π(2), v¯3(π(2)∖g)=10/3 v_3(π(2) \g\)=10/3, while v∨3(π(2)∖g)=2 v_3(π(2) \g\)=2. Hence, since w2=w3w_2=w_3, π is M[pess]-WEF1, but not M[agno]-WEF1. 124563789 Figure 3: Tree of Example 2. 4.2 On the existence of M[ℰE]-WEF1 allocation In this section, we show that MWRR guarantees M[pess]-WEF1 under general additive valuations. In contrast, M[agno]-WEF1 is harder to ensure: some instances admit no such allocation (and thus no M[opt]-WEF1 allocation either), and MWRR may fail to guarantee it even when one exists. Nevertheless, Section 4.3 shows that such failures remain rare in practice. We begin by showing that MWRR guarantees M[pess]-WEF1. Our approach relies on a key lemma, which allows us to adapt the proof of WEF1 for the Weighted Round Robin algorithm from [11] to our multilevel setting. Theorem 4.1 MWRR always returns an M[pess]-WEF1 allocation. Proof sketch. The proof follows the same structure as the WRR proof of [11], with an additional lemma (Lemma 5, Appendix B) to handle the multilevel pessimistic setting. We first prove the result for the children of the root. The same argument then applies recursively to any internal node. During the first |(1)||C(1)| steps, each child of the root receives at most one item. Hence, the allocation is trivially M[pess]-WEF1 at this stage. Then, as in WRR, the picking rule ensures that for any i,j∈(1)i,j (1), we have tjti≥wjwi t_jt_i≥ w_jw_i. We show a lemma stating that whenever node j is selected, the utility it derives from the chosen item (through its selected leaf) is at least the worst utility that any leaf in ℒ(i)L(i) can obtain from any item allocated in subsequent steps. In particular, it dominates the worst item eventually received by any sibling i. Combining the picking ratio property with the mentioned lemma, we obtain that the total utility accumulated by j (excluding its first item) is at least the total worst-case utility of i. This implies that j is M[pess]-WEF1 with respect to i. Applying the same argument recursively to each internal node concludes the proof. Theorem 4.2 Under general valuations, an M[agno]-WEF1 allocation needs not exist. Proof. Consider the multilevel instance represented in Fig. 4, and assume weights are wi=|ℒ(i)|w_i=|L(i)| for i∈i . Let =g1,…,g5G=\g_1,…,g_5\. Leaves have additive utilities: children of 44 and 66 value every item at 22, while children of 55 and 77 value every item at 11. We show that no multilevel allocation can be M[agno]-WEF1. 12489101151213361415161771819 Figure 4: Tree of Example 3 First, notice that no multilevel allocation allocating all items to (leaves of) node 22 can be M[agno]-WEF1. Indeed, in such case, v3(π)/w3=0<v¯3(∖g)/w2=20/18v_3(π)/w_3=0< v_3(G \g\)/w_2=20/18 for any item g∈g . Conversely, no multilevel allocation allocating all items to leaves of node 33 can be M[agno]-WEF1, by symmetry of the instance. Similarly, no multilevel allocation allocating exactly one item g∈g to node 33 can be M[agno]-WEF1. Indeed, even if this item was allocated to a leaf in (6)C(6) (i.e. the group of leaves with the highest utilities), we would have v3(π)/w3=2/<v¯3(π(2)\g′)=10/12v_3(π)/w_3\!=\!2/6\!<\! v_3(π(2) \g \)\!=\!10/12, where π(2)=∖gπ(2)\!=\!G \g\, and g′∈π(2)g \!∈\!π(2). The same applies when allocating exactly one item to node 22, and the rest to node 33, again by symmetry. Finally, we show that even allocating 33 items to node 22, and 22 items to node 33 (or conversely) cannot yield a M[agno]-WEF1 allocation. Suppose a multilevel allocation where |π(2)|=3|π(2)|=3 and |π(3)|=2|π(3)|=2. Then, we show that no matter how π(3)π(3) is allocated to its leaves, it must be agnostic weighted envious towards node 22. Indeed, assume the two items are allocated to leaves in (6)C(6), then node 77 is agnostic weighted envious towards node 66, since it received no item, and node 66 received 22 items. Then, node 33 is obliged to allocate one item to node 66, and one item to node 77. But then, we have v3(π)/w3=3/6<v¯3(π(2)∖g)/w2=10/18v_3(π)/w_3=3/6< v_3(π(2) \g\)/w_2=10/18. By symmetry, no multilevel allocation allocating 22 items to node 22, and 33 items to node 33 can be M[agno]-WEF1. ∎ This example shows that under general valuations, an M[agno]-WEF1 allocation may fail to exist. However, this is not the reason why MWRR fails: the algorithm may return an allocation that is not M[agno]-WEF1 even when such an allocation exists. Theorem 4.3 Under general valuations, MWRR does not guarantee an M[agno]-WEF1 allocation, even when it exists. Example 3 We consider the same instance as in the proof of Theorem 4.2, modifying only the leaves’ preferences over singletons. We assume that all leaves in (5)C(5) and (7)C(7) have utility ux(g)=1/5u_x(g)=1/5 for any g∈g . For x∈(4)x (4), we set ux(g)=5/21u_x(g)=5/21 for g∈g1,g2,g4,g5g∈\g_1,g_2,g_4,g_5\ and ux(g)=1/21u_x(g)=1/21 for g3g_3. Finally, for x∈(6)x (6), we set ux(g)=5/21u_x(g)=5/21 for g∈g1,g2,g3,g5g∈\g_1,g_2,g_3,g_5\ and ux(g)=1/21u_x(g)=1/21 for g4g_4. For this instance, MWRR outputs multilevel allocation π, where we have : π(8)=g1,π(9)=g5,π(12)=g3,π(14)=g2,π(18)=g4π(8)=\g_1\,π(9)=\g_5\,π(12)=\g_3\,π(14)=\g_2\,π(18)=\g_4\, and all other leaves received nothing. One can check that v3(π)=46/105≃0.438v_3(π)=46/105 0.438 and v¯3(π(2)∖g1)=142/315≃0.451 v_3(π(2) \g_1\)=142/315 0.451. Since nodes 2 and 3 have the same weights, we can deduce that π is not M[agno]-WEF1. However, there does exist an M[agno]-WEF1 allocation: π(8)=g2π(8)=\g_2\, π(12)=g3π(12)=\g_3\, π(13)=g4,π(14)=g1,π(18)=g5π(13)=\g_4\,π(14)=\g_1\,π(18)=\g_5\. Corollary 2 Under general valuations, MWRR is not guaranteed to compute an M[opt]-WEF1 allocation, even when it exists. Though these results are negative, one may still ask whether an α-approximation of M[agno]-WEF1 can be guaranteed. Definition 8 (α-M[agno]-WEF1). A multilevel allocation π is an α-approximation of M[agno]-WEF1, for some α>0α>0, if, for any internal node i∈ℐi and any children j,k∈(i)j,k (i), there exists g∈π(k)g∈π(k) such that: vj(π)/wj≥α⋅v¯j(π(k)∖g)/wkv_j(π)/w_j≥α· v_j(π(k) \g\)/w_k Unfortunately, we show that MWRR cannot guarantee any such α-approximation. Theorem 4.4 For any constant factor α>0α>0, there exists an instance where the allocation returned by MWRR is not an α-approximation of M[agno]-WEF1. Proof. Consider the tree in Fig. 5, and assume wi=|ℒ(i)|w_i=|L(i)| for all i∈i . Let =g1,g2,g3G=\g_1,g_2,g_3\ be the set of items. Consider the following utilities: for any x∈ℒ(2)x (2), ux(g1)=0u_x(\g_1\)=0 and ux(g2)=ux(g3)=1u_x(\g_2\)=u_x(\g_3\)=1 ; for any x∈(6)x (6), ux(g1)=1u_x(\g_1\)=1 and ux(g2)=ux(g3)=0u_x(\g_2\)=u_x(\g_3\)=0 ; and for any x∈(7)x (7), ux(g1)=0u_x(\g_1\)=0 and ux(g2)=ux(g3)=Mu_x(\g_2\)=u_x(\g_3\)=M for M>0M>0 arbitrarily large. Let π be the allocation returned by MWRR on this instance: π(8)=g2,π(10)=g3,π(12)=g1π(8)=\g_2\,π(10)=\g_3\,π(12)=\g_1\. Note that we have v3(π)=1v_3(π)=1, and v¯3(π(2)∖g)=W(14,3)×M+W(15,3)×M=M2 v_3(π(2) \g\)=W(14,3)× M+W(15,3)× M= M2 for any g∈π(2)g∈π(2). Hence, for π to be an α-approximation of M[agno]-WEF1, we need in particular v3(π)/w3≥α⋅v¯3(π(2)∖g1)/w2v_3(π)/w_3≥α· v_3(π(2) \g_1\)/w_2. This requires α≤2/Mα≤ 2/M. Since M can be arbitrarily large, α can be arbitrarily small. ∎ 124895101136121371415 Figure 5: Tree of Theorem 4.4 This result is particularly striking when compared to the 13 13-approximation of [19] in the bilevel setting. It highlights a fundamental gap between bilevel instances and multilevel trees of height at least three. While the bilevel case still admits an α-approximation for some α>0α>0, this is no longer possible in the multilevel setting. 4.3 Experimental results In this section, we run experiments to test how often MWRR fails to return a fair allocation. We show that, while it may frequently violate the optimistic notion, it is almost always fair under the agnostic one (an experimental finding that significantly refines the negative result of Theorem 4.3). We describe hereafter the experimental protocol (hardware details are provided in Appendix C). Trees. We consider three classes of trees in our experiments: (1) balanced binary trees, (i) comb trees, and (i) partially unbalanced trees, which are binary except at the last internal level: for any pair of siblings at this level, one internal node has two children while the other has five. For balanced and comb trees, we tested for n=15,31,63,127n=\15,31,63,127\, and for partially unbalanced trees, we tested for n=21,43,87,175n=\21,43,87,175\. Since the number of nodes varies between comb/balanced trees and partially unbalanced trees, we will refer to those number of nodes as small, medium-, medium+, large. In all cases, we tested for m=n,2nm=\n,2n\ items. Moreover, we evaluate two weighting schemes: (i) each node i∈i is assigned weight wi=|ℒ(i)|w_i=|L(i)|, or (i) the weight of each node is sampled independently and uniformly at random from the integer interval [1,6][1,6]. In the tables below, we denote (i) by LW for leaf-count weights and (i) by RW for random weights. Preference generation. To ensure a robust experimental evaluation, we generate preferences using four different methods. Specifically, we propose multilevel adaptations of (i) the Mallows model, (i) the resampling Dirichlet model recently introduced by [6], (i) cost utilities [7], and (iv) correlated utilities as in [13]. Importantly, our results are mostly consistent across all generation methods, which is why we do not devote extensive space to their detailed presentation in the main paper. The generation methods are nevertheless detailed in Appendix C. Results. For each class of instances, we report the 95% confidence interval for the proportion of cases in which the MWRR algorithm produces an M[agno]-WEF1 or an M[opt]-WEF1 allocation. We also provide the average running time of MWRR and its standard deviation. All results are based on 200 instances per class. Due to space constraints, some tables are deferred to the appendix. Running time. Experimental results show that MWRR is extremely fast and scales well (see Table 1). For instance, for balanced trees, the average running time for n=15,m=15n=15,m=15 (over all generation methods, all weighting schemes) is 0.0002 second, while that for n=127,m=254n=127,m=254 is 0.0191 second. Moreover, the running time is consistent across different types of instances. Table 1: Average running time (s) ± std. n m Comb Balanced Partially unbalanced small n 8.50012ptn 8.50012pt 0.0002±0.0001 8.50012pt0.0002± 0.0001 8.50012pt 0.0002±0.0000 8.50012pt0.0002± 0.0000 8.50012pt 0.0003±0.00010.0003± 0.0001 small 2n2n 0.0003±0.00010.0003± 0.0001 0.0003±0.00010.0003± 0.0001 0.0007±0.00010.0007± 0.0001 medium- n 0.0006±0.00030.0006± 0.0003 0.0005±0.00010.0005± 0.0001 0.0010±0.00010.0010± 0.0001 medium- 2n2n 0.0012±0.00060.0012± 0.0006 0.0011±0.00010.0011± 0.0001 0.0025±0.00030.0025± 0.0003 medium+ n 0.0027±0.00180.0027± 0.0018 0.0017±0.00010.0017± 0.0001 0.0038±0.00030.0038± 0.0003 medium+ 2n2n 0.0057±0.00340.0057± 0.0034 0.0041±0.00030.0041± 0.0003 0.0099±0.00120.0099± 0.0012 large n 0.0158±0.01260.0158± 0.0126 0.0067±0.00040.0067± 0.0004 0.0155±0.00150.0155± 0.0015 large 2n2n 0.0387±0.02960.0387± 0.0296 0.0191±0.00340.0191± 0.0034 0.0493±0.00850.0493± 0.0085 M[agno]-WEF1. Interestingly, our experiments strongly mitigate the impossibility results of Section 4. Although we cannot formally guarantee that MWRR always returns an M[agno]-WEF1 allocation, we observe that it does so in almost all cases. Out of the 192,000 generated instances, fewer than 50 result in allocations that are not M[agno]-WEF1. The few instances that led to unfair allocations were in general for comb trees with random weights (tables can be found in the appendix). This suggests that MWRR is extremely likely, in practice, to return a fair allocation in the agnostic sense. M[opt]-WEF1. In contrast, the optimistic notion of fairness appears significantly more challenging to satisfy (see Table 2). The performance of MWRR varies substantially depending on the tree structure, the size of the instance, and whether weights are randomly generated. For example, instances based on comb trees with large n and random weights are particularly challenging, with sometimes near 100% of computed allocations failing to satisfy M[opt]-WEF1. On the other hand, for balanced trees with weights defined as wi=|ℒ(i)|w_i=|L(i)| for all i∈i , achieving M[opt]-WEF1 appears somewhat less challenging. Nevertheless, the proportion of unfair allocations remains highly variable and can still be substantial. Overall, the choice of weights (random or related to the number of leaves) emerges as the most influential factor affecting fairness performance. Table 2: Proportion of non-M[opt]-WEF1 allocations (95% CI). Comb Balanced Part. unbal. n m RW LW RW LW RW LW small n [0.25, 0.27][0.25,\,0.27] [0.02, 0.03][0.02,\,0.03] [0.02, 0.03][0.02,\,0.03] [0.03, 0.04][0.03,\,0.04] [0.05, 0.06][0.05,\,0.06] [0.04, 0.05][0.04,\,0.05] small 2n2n [0.24, 0.27][0.24,\,0.27] [0.01, 0.02][0.01,\,0.02] [0.02, 0.03][0.02,\,0.03] [0.02, 0.03][0.02,\,0.03] [0.06, 0.07][0.06,\,0.07] [0.04, 0.05][0.04,\,0.05] medium- n [0.53, 0.56][0.53,\,0.56] [0.02, 0.03][0.02,\,0.03] [0.09, 0.11][0.09,\,0.11] [0.09, 0.11][0.09,\,0.11] [0.14, 0.17][0.14,\,0.17] [0.12, 0.14][0.12,\,0.14] medium- 2n2n [0.57, 0.60][0.57,\,0.60] [0.01, 0.01][0.01,\,0.01] [0.08, 0.09][0.08,\,0.09] [0.09, 0.10][0.09,\,0.10] [0.14, 0.16][0.14,\,0.16] [0.11, 0.12][0.11,\,0.12] medium+ n [0.70, 0.73][0.70,\,0.73] [0.01, 0.02][0.01,\,0.02] [0.21, 0.23][0.21,\,0.23] [0.21, 0.23][0.21,\,0.23] [0.29, 0.32][0.29,\,0.32] [0.22, 0.25][0.22,\,0.25] medium+ 2n2n [0.71, 0.74][0.71,\,0.74] [0.01, 0.01][0.01,\,0.01] [0.18, 0.20][0.18,\,0.20] [0.12, 0.15][0.12,\,0.15] [0.27, 0.30][0.27,\,0.30] [0.16, 0.18][0.16,\,0.18] large n [0.74, 0.77][0.74,\,0.77] [0.01, 0.01][0.01,\,0.01] [0.40, 0.43][0.40,\,0.43] [0.37, 0.40][0.37,\,0.40] [0.48, 0.51][0.48,\,0.51] [0.38, 0.41][0.38,\,0.41] large 2n2n [0.91, 0.94][0.91,\,0.94] [0.02, 0.04][0.02,\,0.04] [0.55, 0.61][0.55,\,0.61] [0.28, 0.34][0.28,\,0.34] [0.62, 0.69][0.62,\,0.69] [0.51, 0.57][0.51,\,0.57] 5 Conclusion In this paper, we consider multilevel fair division problems where indivisible goods are allocated to agents organized in a tree-structured hierarchy. We assume that internal nodes have additive utilities over their children, while leaves have additive utilities over items. In this setting, we propose three envy-based fairness notions, depending on how a node estimates the value of a bundle, namely M[pess]-WEF1, M[agno]-WEF1, and M[opt]-WEF1. Under identical preferences, these notions coincide, and can be satisfied together with completeness using MWRR. Under general valuations, MWRR guarantees only M[pess]-WEF1 but still performs very well in practice for M[agno]-WEF1. A direct extension concerns the existence of M[agno]-WEF1 allocations. In Section 4, we showed that under general additive valuations, such an allocation may not exist. However, this relies on non-normalized utilities: after normalization, the instance admits an M[agno]-WEF1 allocation, and existence under normalized utilities remains open. Still, this does not resolve the issue with MWRR, which may fail to return an M[agno]-WEF1 allocation even when one exists (as Example 3 is already normalized). A natural extension of this work is to consider broader utility functions for leaves, and alternative utilities for internal nodes. In particular, instead of purely aggregating children’s utilities, internal nodes could incorporate their own preferences, as in [9], e.g., preferring balanced allocations across subgroups. Acknowledgements This work is supported by the ANR project ANR-24-CE23-1700 AROMATICS. References [1] R. Abebe, J. Kleinberg, and D. C. Parkes (2017) Fair division via social comparison. In Proceedings of the 16th Conference on Autonomous Agents and MultiAgent Systems, Richland, SC, p. 281–289. Cited by: §1. [2] G. Aggarwal, M. Mertzanidis, A. Psomas, and D. Wang (2024) Mechanism design with delegated bidding. External Links: 2409.19087, Link Cited by: §1, §1. [3] M. Aleksandrov and T. Walsh (2018) Group envy freeness and group pareto efficiency in fair division with indivisible items. In KI 2018: Advances in Artificial Intelligence, Cited by: §1, §1. [4] N. Benabbou, M. Chakraborty, E. Elkind, and Y. Zick (2019) Fairness towards groups of agents in the allocation of indivisible items. In Proceedings of the 28th International Joint Conference on Artificial Intelligence, IJCAI’19, p. 95–101. External Links: ISBN 9780999241141 Cited by: §1, §1. [5] A. Beynier, Y. Chevaleyre, L. Gourvès, A. Harutyunyan, J. Lesca, N. Maudet, and A. Wilczynski (2019) Local envy-freeness in house allocation problems. Autonomous Agents and Multi-Agent Systems 33 (5), p. 591–627. External Links: ISSN 1387-2532 Cited by: §1. [6] P. Böhm, R. Bredereck, P. Gölz, A. Kaczmarczyk, and S. Szufa Putting fair division on the map. Proceedings of AAAI’2026 40 (20), p. 16726–16734. Cited by: §4.3, C. Additional experimental results. [7] S. Botan, A. Ritossa, M. Suzuki, and T. Walsh (2023) Maximin fair allocation of indivisible items under cost utilities. In Algorithmic Game Theory, p. 221–238. External Links: ISBN 978-3-031-43254-5 Cited by: §4.3, C. Additional experimental results. [8] R. Bredereck, A. Kaczmarczyk, and R. Niedermeier (2022) Envy-free allocations respecting social networks. Artificial Intelligence 305, p. 103664. External Links: ISSN 0004-3702 Cited by: §1. [9] X. Bu, Z. Li, S. Liu, J. Song, and B. Tao (2024) Fair division with allocator’s preference. In Web and Internet Economics: 19th International Conference, p. 77–94. External Links: ISBN 978-3-031-48973-0 Cited by: §1, §5. [10] I. Caragiannis, D. Kurokawa, H. Moulin, A. D. Procaccia, N. Shah, and J. Wang (2019) The unreasonable fairness of maximum nash welfare. ACM Trans. Economics and Comput. 7 (3), p. 12:1–12:32. Cited by: §1, §1. [11] M. Chakraborty, A. Igarashi, W. Suksompong, and Y. Zick (2021) Weighted envy-freeness in indivisible item allocation. ACM Trans. Econ. Comput. 9 (3). External Links: ISSN 2167-8375 Cited by: §1, §1, §1, §1, §3.2, §3.2, §4.2, §4.2, Proof., Proof., Proof., Proof., Lemma 4, Lemma 6, Abstract. [12] M. Chakraborty, E. Segal-Halevi, and W. Suksompong (2024) Weighted fairness notions for indivisible items revisited. ACM Trans. Econ. Comput. 12 (3). External Links: ISSN 2167-8375 Cited by: §1. [13] J. P. Dickerson, J. R. Goldman, J. Karp, A. D. Procaccia, and T. Sandholm (2014) The computational rise and fall of fairness. In Proceedings of the Twenty-Eighth AAAI Conference on Artificial Intelligence, p. 1405–1411. Cited by: §4.3, C. Additional experimental results. [14] N. Gross-Humbert, N. Benabbou, A. Beynier, and N. Maudet (2023) On the notion of envy among groups of agents in house allocation problems. In ECAI 2023 - 26th European Conference on Artificial Intelligence, p. 924–931. Cited by: §1, §1. [15] M. Kyropoulou, W. Suksompong, and A. A. Voudouris (2019) Almost envy-freeness in group resource allocation. In Proceedings of IJCAI’2019, p. 400–406. Cited by: §1, §1. [16] R. J. Lipton, E. Markakis, E. Mossel, and A. Saberi (2004) On approximately fair allocations of indivisible goods. In Proceedings 5th ACM Conference on Electronic Commerce (EC-2004), New York, NY, USA, May 17-20, 2004, J. S. Breese, J. Feigenbaum, and M. I. Seltzer (Eds.), p. 125–131. External Links: Link, Document Cited by: §1. [17] M. Lucet, N. Benabbou, A. Beynier, and N. Maudet (2026) Multilevel fair allocation with matroid-rank preferences. External Links: 2512.24105, Link Cited by: §1, §1, §1, §1. [18] C. L. Mallows (1957) Non-null ranking models. Biometrika 44, p. 114–130. Cited by: C. Additional experimental results. [19] J. Scarlett, N. Teh, and Y. Zick (2023) For one and all: individual and group fairness in the allocation of indivisible goods. In Proceedings of the 2023 International Conference on Autonomous Agents and Multiagent Systems, p. 2466–2468. External Links: ISBN 9781450394321 Cited by: §1, §2, §3.1, §3.2, §3.2, §3.2, §3, §4.2, Proof., Proof., Proof., Algorithm 2. [20] U. Schmidt-Kraepelin, W. Suksompong, and S. Wijaya (2025) On multi-level apportionment. Theory and Decision. External Links: Document Cited by: §1. A. Missing proofs from Section 3 We start by proving Theorem 2. Theorem 5.2 Under all-common valuations and wi=|ℒ(i)|,∀i∈w_i=|L(i)|,∀ i , there exists a polynomial-time algorithm that returns an allocation that is M-WEF1 and EFX between all leaves in ℒL. Proof. The algorithm is called Sequential Maximin - Multilevel Weighted Round Robin, and is a multilevel extension of the SM-IWRR presented in [19]. Pseudocodes can be found in Algorithms 2 and 3. The pseudocode for MWRR can be found in the main paper. Algorithm 2 Sequential Maximin (from [19]) 1: Input: N - a set of agents ; G - a set of items ; u - a common valuation 2: Output: A - an allocation 3: Initialize A(x)=A(x)=\\ for x∈Nx∈ N 4: ℛℐ←RI ⊳ Initial set of remaining items 5: while ℛℐ≠∅RI≠ do 6: g←argmaxg′∈ℛℐu(g′)g← _g u(g ) 7: x←argminy∈Nu(A(y))x← _y∈ Nu(A(y)) 8: A(x)←A(x)∪gA(x)← A(x)∪\g\ 9: ℛℐ←ℛℐ∖gRI \g\ 10: end while 11: return A Algorithm 3 Sequential Maximin - Multilevel Weighted Round Robin (SM-MWRR) 1: Input: T - a multilevel tree ; G - a set of items ; u - a common valuation 2: Output: π - a multilevel allocation 3: Run the SM algorithm with input ℒL, G, and valuation u, and obtain allocation A′∈ℒA ^G_L 4: xmin←argminy∈ℒ(i)u(A(y))x_min← _y (i)u(A(y)) 5: Amin′←A′(xmin)A _min← A (x_min) 6: Initialize a set of representative goods, ℛ=RG=\\ 7: for x∈ℒx do 8: Create a representative good rxr_x such that u^(rx)=u(A′(x))−u(Amin′) u(r_x)=u(A (x))-u(A _min) 9: ℛ←ℛ∪rxRG ∪\r_x\ 10: end for 11: Run the MWRR with input T, items ℛRG, and identical valuation u u, and obtain the multilevel allocation π π 12: Initialise multilevel allocation π such that π(1)=π(1)=G and π(i)=π(i)=\\ for any i∈∖1i \1\ 13: for i∈∖1i \1\ do 14: for x∈ℒ1x 1 do 15: if rx∈π^(i)r_x∈ π(i) then 16: π(i)←π(i)∪A′(x)π(i)←π(i)∪ A (x) 17: end if 18: end for 19: end for 20: return π The proof the allocation is EFX at the leaves is exactly the same than in Theorem 3.5 of [19]. Moreover, we proved in Theorem 3 that the MWRR was M-WEF1 under root-child-common valuations. All-common valuations being a special case of root-child-common valuations, we get the same guarantee. Recall that under identical preferences, the three adaptations of M-WEF1 coincide. Hence, we focus on showing that the returned allocation is M-WEF1. We extend the proof of [19] to apply to the multilevel setting. After the SM algorithm ran at the leaves, which computed an EFX allocation between the leaves, denote A∈ℒA ^G_L the resulting allocation at the leaves, and π the induced multilevel allocation, i.e. π(x)=A(x)π(x)=A(x) for any x∈ℒx , and π(i)=∪x∈ℒ(i)A(x)π(i)= _x (i)A(x) for any i∈ℐi . Consider the set of bundles A1,…,Aℓ\A_1,…,A_ \, where ℓ=|ℒ| =|L|. We relabel it so that u(A1)≥u(A2)≥…≥u(Aℓ)u(A_1)≥ u(A_2)≥…≥ u(A_ ). Note that we denote the utilities of the leaves by u as they are identical. For any leaf x∈ℒx , we define the representative good value to be u^(rx)=u(Ax)−u(Aℓ) u(r_x)=u(A_x)-u(A_ ), where rxr_x is the representative good of bundle AxA_x. We make the following two claims: Claim (1) For all x∈ℒx , u^(rx) u(r_x) is upper-bounded by the value of any good in AxA_x. Claim (2) Given any node i∈ℐi , and any two of its children j,k∈(i)j,k (i). Denote π π the multilevel allocation of representative goods allocated to each node in N, resulting from allocation A to the leaves. If π π is a M-WEF1 allocation of representative goods, then it remains M-WEF1 by replacing the representative goods by their corresponding bundles. Claim 1 holds because the allocation A, hence π, is EFX between the leaves, and therefore, for any leaf x∈ℒx , and any item g∈Axg∈ A_x, we have u(Ax∖g)≤u(Aℓ)u(A_x \g\)≤ u(A_ ). Then, as valuations are additive, u(Ax)−u(g)≤u(Aℓ)u(A_x)-u(\g\)≤ u(A_ ), and hence u^(rx)=u(Ax)−u(Aℓ)≤u(g) u(r_x)=u(A_x)-u(A_ )≤ u(\g\). We now prove Claim 2. Assume we have a M-WEF1 allocation of the representative goods, and denote it π π. For any two children j,kj,k of node i∈ℐi , there must exist a representative good rmax∈π^(k)r_ ∈ π(k) such that u^(rmax)=maxy∈ℒ(k)u^(ry) u(r_ )= _y (k) u(r_y), and the following holds: ∑x∈ℒ(j)u^(rx)wj≥∑y∈ℒ(k)u^(ry)−u^(rmax)wk _x (j) u(r_x)w_j≥ _y (k) u(r_y)- u(r_ )w_k By the definition of a representative good, for any leaf x∈ℒ(j)x (j), we have u^(rx)=u(Ax)−u(Aℓ) u(r_x)=u(A_x)-u(A_ ), and since AℓA_ is the least-valued bundle of A, we get ∑x∈ℒ(j)u^(rx)wj _x (j) u(r_x)w_j =∑x∈ℒ(j)u(Ax)−u(Aℓ)wj = _x (j)u(A_x)-u(A_ )w_j =∑x∈ℒ(j)u(Ax)wj−u(Aℓ),since wj=|ℒ(j)| = _x (j)u(A_x)w_j-u(A_ ), $w_j=|L(j)|$ Moreover, the right-hand side, for the same reason, can be rewritten as : ∑y∈ℒ(k)u^(ry)−u^(rmax)wk=∑y∈ℒ(k)u(Ay)−u^(rmax)wk−u(Aℓ) _y (k) u(r_y)- u(r_ )w_k= _y (k)u(A_y)- u(r_ )w_k-u(A_ ) Since in this setting, u(π(j))=∑x∈ℒ(j)u(Ax)u(π(j))= _x (j)u(A_x) and u(π(k))=∑y∈ℒ(k)u(Ay)u(π(k))= _y (k)u(A_y), we get u(π(j))wj= u(π(j))w_j= ∑x∈ℒ(j)u(Ax)wj≥ _x (j)u(A_x)w_j≥ ∑y∈ℒ(k)u(Ay)−u^(rmax)wk=u(π(k))−u^(rmax)wk. _y (k)u(A_y)- u(r_ )w_k= u(π(k))- u(r_ )w_k. Finally, from Claim 1, we know u^(rmax)≤u(gmax) u(r_ )≤ u(g_ ), where gmaxg_ is some good from bundle π(k)π(k) because by definition of a representative good, if u^(rmax)=maxy∈ℒ(k)u^(ry) u(r_ )= _y (k) u(r_y), then u(gmax)≥u(g)u(g_ )≥ u(g) for any g∈π(k)g∈π(k). Hence, we get u(π(j))wj≥u(π(k))−u^(rmax)wk≥u(π(k))−u(gmax)wk u(π(j))w_j≥ u(π(k))- u(r_ )w_k≥ u(π(k))-u(g_ )w_k In SM-MWRR, we first compute an allocation to the leaves that is EFX between the leaves, then we construct the representative goods sets and values. Then, MWRR is run on the given tree, but with the representative goods to allocate and leaves equipped with the representative good utility function, u u. Since all leaves have the same utility function, we know from Theorem 3 that the returned allocation, denoted π π, is M-WEF1 w.r.t. u u. By Claim 2, we know this implies that the allocation w.r.t. the true bundles of items and utility functions u. This concludes the proof. ∎ We then prove Corollary 1. Corollary 1 Under root-child-common valuations and wi=|ℒ(i)|,∀i∈w_i=|L(i)|,∀ i , the MWRR is M-WEF1 and EF1 between all leaves in ℒL. Proof. From Theorem 3, we know that MWRR satisfies M-WEF1. Furthermore, the proof of Theorem 3.9 in [19] readily extends to our setting and establishes EF1 among the leaves. Their argument proceeds as follows. Consider a single execution of the algorithm and partition the resulting sequence of allocations into ⌈m|ℒ|⌉ m|L| rounds, where in each round every leaf receives exactly one item. At any given round, a leaf x prefers her bundle to that of any other leaf y who picks after her in the same round. Moreover, leaf x prefers the item she selects in a given round to the item selected in the next round by any leaf y who picked before her in the current round. Consequently, at the end of the algorithm, leaf x prefers her final bundle to that of any leaf y appearing after her in the picking order, and prefers her bundle to that of any leaf y appearing before her, up to the removal of the first item allocated to y. ∎ B. Missing proofs from Section 4 We show that v¯i(S) v_i(S) is indeed a convex combination of the (ux)x∈ℒ(i)(u_x)_x (i) for any internal node i∈ℐi . Lemma 3 For any internal node i∈ℐi and any bundle S⊆S , the agnostic estimated utility function v¯i(S) v_i(S) is a convex combination of the (ux)x∈ℒ(i)(u_x)_x (i). Proof. First, recall that we have v¯i(S)=∑x∈ℒ(i)∑g∈Sux(g)⋅W(x,i) v_i(S)= _x (i) _g∈ Su_x(g)· W(x,i) We show that ∑x∈ℒ(i)W(x,i)=1 _x (i)W(x,i)=1. ∑x∈ℒ(i)W(x,i) _x (i)W(x,i) =∑j∈(i)W(j,i)∑x∈ℒ(j)W(x,j) = _j (i)W(j,i) _x (j)W(x,j) OPEN=∑j∈(i)W(j,i)…∑k∈((k))W(k,(k))∑x∈(k)W(x,kCLOSE⏟=1) = _j (i)W(j,i) 8.5359pt… _k (P(k))W(k,P(k)) _x (k)W(x,k_=1) OPEN=∑j∈(i)W(j,i)…∑k∈((k))W(k,(k))⋅1⏟=1) = _j (i)W(j,i) 8.5359pt… _k (P(k))W(k,P(k))· 1_=1) =1 =1 ∎ We then provide the full proof of Theorem 4. Theorem 5.4 MWRR always returns a M[pess]-WEF1 allocation. Proof. We show that MWRR computes an allocation π∈Ππ∈ such that π|(p)π|_C(p) is pessimistic WEF1 for any p∈ℐp . First, notice that for any p such that h(p)=1h(p)=1, the proof follows immediately from the proof of [11] that their "least weight-adjusted frequent picker" procedure is WEF1. Indeed, at such node p the children in (p)C(p) are leaves and hence can compare directly their bundle with that on their sibling. Hence, MWRR acts exactly the same way than their algorithm. The only difference is in the tie-breaking scheme, which does not intervene in their proof. Hence, our objective is to prove that the result holds for any p∈ℐp such that h(p)≥2h(p)≥ 2. First, notice that the first |(p)||C(p)| picks are a simple round-robin, and each child receives one item. Hence, this first round is obviously pessimistic WEF1 as each child has at most one item at this point. Then, we focus on showing that the allocation computed remains WEF1 after the first pick. Lemma 4 (From [11]) Consider an internal node p∈ℐp and one of its children i∈(p)i (p) selected by MWRR at some iteration t, and suppose it is not i’s first pick. Let tit_i and tjt_j be the numbers of times child i and some other child j∈(p)j (p) appear in the prefix of iteration t (not including t itself). Then, tjti≥wjwi t_jt_i≥ w_jw_i. Proof. Since i was picked at iteration t, it must be that i∈argmini′∈(p)ti′wi′i∈ _i (p) t_i w_i . Thus, for any j∈(p)j (p), we have tiwi≤tjwj t_iw_i≤ t_jw_j. Hence, tjti≥wjwi t_jt_i≥ w_jw_i. ∎ Lemma 5 Consider MWRR at some iteration t picked an internal node i∈ℐi , and x∈ℒ(i)x (i) was eventually selected to pick an item among the remaining items, denoted ℛ(t)RG(t). Assume x chooses g∈ℛ(t)g (t), then ux(g)≥miny∈ℒ(i)uy(g′),∀g′∈ℛ(t)u_x(g)≥ _y (i)u_y(g ), ∀ g (t) Proof. Let x∈ℒ(i)x (i) pick item g∈ℛ(t)g (t) among the remaining items at iteration t. Then, by construction, we have g∈argmaxg′∈ℛ(t)ux(g′)g∈ _g (t)u_x(g ) Suppose by contradiction that ∃g′∈ℛ(t)∃ g (t) such that ux(g)<miny∈ℒ(i)uy(g′)u_x(g)< _y (i)u_y(g ) Since g∈argmaxg′∈ℛ(t)ux(g′)g∈ _g (t)u_x(g ), it must be in particular that ux(g′)<miny∈ℒ(i)uy(g′)u_x(g )< _y (i)u_y(g ) However since x∈ℒ(i)x (i), it yields a contradiction. ∎ We then proceed to show that, for any two children i,j∈(p)i,j (p), MWRR computes an allocation such that j is pessimistic weighted envy-free up to the first chosen item by i. To show this, we keep the same proof of [11], and use our Lemma 5 at some point in their proof to be able to use the same argument adapted to our setting. Lemma 6 (Mostly from [11]) Suppose that, for every iteration t in which agent i picks an item (i.e. one of its leaves eventually does) after her first pick, we have tit_i and tjt_j for some other agent j∈(p)j (p) satisfies tjti≥wjwi t_jt_i≥ w_jw_i. Then, in the partial multilevel allocation up to and including i’s latest pick, agent j is pessimistic weighted envy-free towards i up to the first item picked. Proof. Let γ:=wjwiγ:= w_jw_i. Consider any iteration t in which agent i is chosen after her first pick. Let agent j’s minimum values over its leaves in ℒ(j)L(j) for the items allocated to agent i in the latter’s second, third, …, (ti+1)st(t_i+1)^st picks (the last one occuring at current iteration t be β1,β2,…,βti _1, _2,…, _t_i respectively. For instance, we have β1=miny∈ℒ(j)uy(g2) _1= _y (j)u_y(g^2) where g2g^2 is the item selected at agent i’s second pick. Notice that β’s are different than those of [11]. If g∗g^* is the first item picked by agent i (i.e. by one if its leaves) and πtπ^t is the partial multilevel allocation up to and including iteration t, then clearly v∨j(πt(i)∖g∗)=∑x=1tiβti v_j(π^t(i) \g^*\)= _x=1^t_i _t_i. Let the number of times agent j appears in the prefix of agent i’s second pick be τ1 _1 ; that between agent i’s second and third picks be τ2 _2 ; … ; that between agent i’s titht_i^th and (ti+1)th(t_i+1)^th picks be τti _t_i. Let agent j’s values for the items she herself picked during phase x∈[ti]x∈[t_i] be α1x,α2x,…,ατxα^x_1,α^x_2,…,α^x_ _x (i.e. between agent i’s xthx^th and (x+1)th(x+1)^th picks, agent j’s received τx _x items). Notice that here when we say "agent j’s values for the items", we actually mean that for each item, we call αkxα^x_k the utility of the leaf that picked the item at iteration k during phase x. Then, we have vj(πt)=∑x=1ti∑y=1τxαyxv_j(π^t)= _x=1^t_i _y=1 _xα^x_y. Let, for r∈[ti]r∈[t_i], ∑x=1rτx _x=1^r _x and r be the numbers of times agents j and i appear in the prefix of the latter’s (r+1)th(r+1)^th pick respectively. The condition of the lemma that tjti≥wjwi t_jt_i≥ w_jw_i yields ∑x=1rτx≥rγ _x=1^r _x≥ rγ (1) Note that while τ1≥γ>0 _1≥γ>0 (because each agent is selected once in the first (p)C(p) picks), it can be that τx=0 _x=0 for x∈2,3,…,tix∈\2,3,…,t_i\. It corresponds to the scenario where agent i picked more than once without agent j picking in between. Moreover, we know from Lemma 5 that every time agent j was chosen, the item eventually picked by the selected leaf in ℒ(j)L(j) has a value greater or equal than the worst utility over all leaves in ℒ(j)L(j) for any of the remaining items at this iteration, including those eventually picked by agent i later. Hence, if τx>0 _x>0 for some x∈[ti]x∈[t_i], we have αyx≥maxβx,βx+1,…,βti,∀y∈[τx]α^x_y≥ \ _x, _x+1,…, _t_i\, ∀ y∈[ _x] Note that this is where Lemma 5 is necessary to carry on with the same proof than [11]. Summing over all y’s, we get ∑y=1τxαyx≥τxmaxβx,βx+1,…,βτx _y=1 _xα^x_y≥ _x \ _x, _x+1,…, _ _x\ (2) Note that Inequality (2) holds trivially for τx=0 _x=0 since both sides are zero. Hence, it holds for any x∈[ti]x∈[t_i]. Now, we claim the following for each r∈[ti]r∈[t_i] ∑x=1r∑y=1τxαyx≥γ∑x=1rβx+(∑x=1rτx−rγ)maxβr,βr+1,…,βti _x=1^r _y=1 _xα^x_y≥γ _x=1^r _x+ ( _x=1^r _x-rγ ) \ _r, _r+1,…, _t_i\ To prove the claim, we proceed by induction on r. For the base case r=1r=1, we obtain from Inequality (2) ∑y=1τ1αy1 _y=1 _1α^1_y ≥τ1maxβ1,β2,…,βti ≥ _1 \ _1, _2,…, _t_i\ ≥γβ1+(τ1−γ)maxβ1,β2,…,βti ≥γ _1+( _1-γ) \ _1, _2,…, _t_i\ where second line follows from γmaxβ1,β2,…,βti≥γβ1γ \ _1, _2,…, _t_i\≥γ _1. For the inductive step, assume the claim holds for r−1r-1. We now prove it for r. ∑x=1r∑y=1τx _x=1^r _y=1 _x αyx=∑x=1r=1∑y=1τxαyx+∑y=1τrαyr α^x_y= _x=1^r=1 _y=1 _xα^x_y+ _y=1 _rα^r_y ≥γ∑x=1r−1βx+(∑x=1r−1τx−(r−1)γ)maxβr−1,βr,…,βti+∑y=1τrαyr ≥γ _x=1^r-1 _x+ ( _x=1^r-1 _x-(r-1)γ ) \ _r-1, _r,…, _t_i\+ _y=1 _rα^r_y ≥γ∑x=1r−1βx+(∑x=1r−1τx−(r−1)γ)maxβr−1,βr,…,βti+τrmaxβr,…,βti ≥γ _x=1^r-1 _x+ ( _x=1^r-1 _x-(r-1)γ ) \ _r-1, _r,…, _t_i\+ _r \ _r,…, _t_i\ ≥γ∑x=1r−1βx+(∑x=1r−1τx−(r−1)γ)maxβr,…,βti+τrmaxβr,…,βti ≥γ _x=1^r-1 _x+ ( _x=1^r-1 _x-(r-1)γ ) \ _r,…, _t_i\+ _r \ _r,…, _t_i\ =γ∑x=1r−1βx+(∑x=1rτx−(r−1)γ)maxβr,…,βti =γ _x=1^r-1 _x+ ( _x=1^r _x-(r-1)γ ) \ _r,…, _t_i\ =γ∑x=1r−1βx+γmaxβr,…,βti+(∑x=1rτx−rγ)maxβr,…,βti =γ _x=1^r-1 _x+γ \ _r,…, _t_i\+ ( _x=1^r _x-rγ ) \ _r,…, _t_i\ ≥γ∑x=1r−1βx+γβr+(∑x=1rτx−rγ)maxβr,…,βti ≥γ _x=1^r-1 _x+γ _r+ ( _x=1^r _x-rγ ) \ _r,…, _t_i\ =γ∑x=1rβx+(∑x=1rτx−rγ)maxβr,…,βti =γ _x=1^r _x+ ( _x=1^r _x-rγ ) \ _r,…, _t_i\ where second line follows from the inductive hypothesis. The third line comes from Inequality (2). The forth line follows from ∑x=1r−1τx−(r−1)γ≥0 _x=1^r-1 _x-(r-1)γ≥ 0 from Inequality (1) and maxβr−1,βr,…,βti≥maxβr,…,βti \ _r-1, _r,…, _t_i\≥ \ _r,…, _t_i\. This completes the induction. Now, let r=tir=t_i, we get ∑x=1ti∑y=1τtxαyx _x=1^t_i _y=1 _t_xα^x_y ≥γ∑x=1tiβx+(∑x=1tiτx−tiγ)βti ≥γ _x=1^t_i _x+( _x=1^t_i _x-t_iγ) _t_i ≥γ∑x=1tiβx ≥γ _x=1^t_i _x where second line follows from Inequality (1). Hence, as vj(π)=∑x=1ti∑y=1τxαyxv_j(π)= _x=1^t_i _y=1 _xα^x_y and v∨j(π(i)∖g∗)=∑x=1tiβx v_j(π(i) \g^*\)= _x=1^t_i _x, we get vj(π)≥γ⋅v∨j(π(i)∖g∗) v_j(π)≥γ· v_j(π(i) \g^*\) ⇔ vj(π)wj≥v∨j(π(i))∖g∗wi v_j(π)w_j≥ v_j(π(i)) \g^*\w_i Hence, agent j is pessimistic weighted envy-free towards i up to the first item agent i picked. ∎ Hence, since Lemma 6 holds for any p∈ℐp and any of its children, it concludes the proof. ∎ C. Additional experimental results We provide hereafter further details on the experimental results we obtain. Protocol. Experiments were conducted on a server equipped with two Intel Xeon E5-2690v3 CPUs running at 2.60GHz, and 192 GB of RAM (each experiment was run on 4 cores). The program is written in Python. All results were obtained over 200 instances. Preference generation. In order to design a robust experimental protocol, we use four different methods to generate the preferences of our leaves. Mallows. We adapt the Mallows model [18], commonly used in voting theory, to a multilevel setting. Although it generates ordinal preferences, it remains useful for fair allocation when we want similar rankings over items across agents. The model relies on a central ranking and a dispersion parameter ϕ∈[0,1]φ∈[0,1]: when ϕ=0φ=0, rankings match the central ranking exactly, while ϕ=1φ=1 yields uniformly random rankings (Impartial Culture). In the multilevel version, each internal node i is assigned its own dispersion parameter ϕi _i. Starting from a uniformly sampled root ranking, we recursively generate central rankings for each node: the children of node i receive rankings drawn from a Mallows model centered at i’s ranking with parameter ϕi _i. This process continues down the tree until all leaves are assigned rankings, which we convert into (non-normalized) utilities using the pref_voting library. This framework enables fine control over preference correlations across the hierarchy: low ϕi _i enforces similarity among siblings, while higher values introduce greater diversity. Resampling-Dirichlet. The second method we use was introduced in [6]. Our multilevel adaptation works as follows: we first generate randomly a central approval vector V, where m∗pm*p items are approved, with p∈0.3,0.6,0.9p∈\0.3,0.6,0.9\ a probability. Then, starting at the root, we generate approval vector for each of its children – if item g is approved in V, then child i approves it with probability p, and if g is not approved, then i approves it with probability ϕ∈0.2,0.8φ∈\0.2,0.8\. We repeat this procedure until reaching the leaves. For each leaf x, we construct a utility vector uxu_x. Let AppApp be the ordered list of items approved by x. For a parameter t≥0t≥ 0, we assign utilities ux(g)=10−10u_x(g)=10^-10 for non-approved items, and ux(g)=2(j/|App|+0.01)tu_x(g)= 2(j/|App|+0.01)^t for the j-th approved item. If no item is approved, one is selected uniformly at random. Finally, we sample a normalized utility vector from a Dirichlet distribution parametrized by this vector. Cost utilities. The third method, proposed in [7], assumes a utility vector describing the public value of each item (drawn uniformly at random). Each agent can either approve or disapprove an item. It she approves it, then her utility for the item is the public utility ; otherwise, she has no utility for it. We adapt it to the multilevel setting by computing from the root to the leaves, an approval vector for each node i as follows: for any item g∈g , if (i)P(i) approves it, then i approves with probability p∈0.3,0.6,0.9p∈\0.3,0.6,0.9\, while if (i)P(i) disapproves it, then i approves it with probability ϕ∈0.2,0.8φ∈\0.2,0.8\. Correlated utilities. The last method, proposed in [13], assumes again a central utility vector V, drawn uniformly at random. The utility of any agent x for any item g is then drawn from a normal distribution whose mean is V(g)V(g), i.e. ux(g)∼(V(g),σx)u_x(g) (V(g), _x) with σx∈0.2,0.8 _x∈\0.2,0.8\ the standard deviation associated with agent x. Our adaptation to the multilevel setting follows the same logic: we draw uniformly at random a central vector. Starting at the root, we sample some utility vector for the children of the root, i.e. for each i∈(1)i (1) and each item g∈g , ui(g)∼(V(g),σ1)u_i(g) (V(g), _1). We repeat this process until reaching the leaves. Results. In the main body of the paper, we reported our experimental results and observed that, among the 192,000 generated instances, fewer than 50 led MWRR to return a non-M[agno]-WEF1 allocation. In this section, we provide the detailed tables corresponding to those instances. We observe that, across all preference generation methods, non-M[agno]-WEF1 allocations occur only for instances defined on comb trees with random weights (See Tables 3, 4, 5, and 6). Note, however, that such unfair allocations are not limited to this class of instances; they also arise in other settings (see, for example, the proof of Theorem 6). Table 3: Proportion of non-M[agno]-WEF1 allocations (95% CI) - Mallows - RW - Comb tree. Columns: (φ1,φ2)( _1, _2). N M (2,2)(2,2) (2,8)(2,8) (8,2)(8,2) (8,8)(8,8) 15 15 [0.00, 0.01][0.00,\,0.01] [0.00, 0.00][0.00,\,0.00] [0.00, 0.00][0.00,\,0.00] [0.00, 0.00][0.00,\,0.00] 15 30 [0.00, 0.00][0.00,\,0.00] [0.00, 0.00][0.00,\,0.00] [0.00, 0.00][0.00,\,0.00] [0.00, 0.00][0.00,\,0.00] 31 31 [0.00, 0.00][0.00,\,0.00] [0.00, 0.00][0.00,\,0.00] [0.00, 0.00][0.00,\,0.00] [0.00, 0.00][0.00,\,0.00] 31 62 [0.00, 0.00][0.00,\,0.00] [0.00, 0.00][0.00,\,0.00] [0.00, 0.00][0.00,\,0.00] [0.00, 0.01][0.00,\,0.01] 63 63 [0.00, 0.00][0.00,\,0.00] [0.00, 0.00][0.00,\,0.00] [0.00, 0.00][0.00,\,0.00] [0.00, 0.00][0.00,\,0.00] 63 126 [0.00, 0.00][0.00,\,0.00] [0.00, 0.00][0.00,\,0.00] [0.00, 0.00][0.00,\,0.00] [0.00, 0.00][0.00,\,0.00] 127 127 [0.00, 0.00][0.00,\,0.00] [0.00, 0.00][0.00,\,0.00] [0.00, 0.00][0.00,\,0.00] [0.00, 0.00][0.00,\,0.00] 127 254 [0.00, 0.00][0.00,\,0.00] [0.00, 0.00][0.00,\,0.00] [0.00, 0.00][0.00,\,0.00] [0.00, 0.00][0.00,\,0.00] Table 4: Proportion of non-M[agno]-WEF1 allocations (95% CI) - resampling dirichlet - RW - Comb tree. Columns: (p,φ)(p, ). N M (3,2)(3,2) (3,8)(3,8) (6,2)(6,2) (6,8)(6,8) (9,2)(9,2) (9,8)(9,8) 15 15 [0.00, 0.05][0.00,\,0.05] [0.00, 0.01][0.00,\,0.01] [0.00, 0.02][0.00,\,0.02] [0.00, 0.01][0.00,\,0.01] [0.00, 0.00][0.00,\,0.00] [0.00, 0.00][0.00,\,0.00] 15 30 [0.00, 0.02][0.00,\,0.02] [0.00, 0.00][0.00,\,0.00] [0.00, 0.00][0.00,\,0.00] [0.00, 0.00][0.00,\,0.00] [0.00, 0.00][0.00,\,0.00] [0.00, 0.00][0.00,\,0.00] 31 31 [0.00, 0.02][0.00,\,0.02] [0.00, 0.01][0.00,\,0.01] [0.00, 0.00][0.00,\,0.00] [0.00, 0.01][0.00,\,0.01] [0.00, 0.00][0.00,\,0.00] [0.00, 0.00][0.00,\,0.00] 31 62 [0.00, 0.00][0.00,\,0.00] [0.00, 0.00][0.00,\,0.00] [0.00, 0.00][0.00,\,0.00] [0.00, 0.00][0.00,\,0.00] [0.00, 0.00][0.00,\,0.00] [0.00, 0.00][0.00,\,0.00] 63 63 [0.00, 0.00][0.00,\,0.00] [0.00, 0.00][0.00,\,0.00] [0.00, 0.00][0.00,\,0.00] [0.00, 0.01][0.00,\,0.01] [0.00, 0.00][0.00,\,0.00] [0.00, 0.00][0.00,\,0.00] 63 126 [0.00, 0.00][0.00,\,0.00] [0.00, 0.00][0.00,\,0.00] [0.00, 0.00][0.00,\,0.00] [0.00, 0.00][0.00,\,0.00] [0.00, 0.00][0.00,\,0.00] [0.00, 0.00][0.00,\,0.00] 127 127 [0.00, 0.00][0.00,\,0.00] [0.00, 0.00][0.00,\,0.00] [0.00, 0.00][0.00,\,0.00] [0.00, 0.00][0.00,\,0.00] [0.00, 0.00][0.00,\,0.00] [0.00, 0.00][0.00,\,0.00] 127 254 [0.00, 0.00][0.00,\,0.00] [0.00, 0.00][0.00,\,0.00] [0.00, 0.00][0.00,\,0.00] [0.00, 0.00][0.00,\,0.00] [0.00, 0.00][0.00,\,0.00] [0.00, 0.00][0.00,\,0.00] Table 5: Proportion of non-M[agno]-WEF1 allocations (95% CI) - Cost utilities - RW - Comb tree. Columns: (p,φ)(p, ). N M (3,2)(3,2) (3,8)(3,8) (6,2)(6,2) (6,8)(6,8) (9,2)(9,2) (9,8)(9,8) 15 15 [0.00, 0.04][0.00,\,0.04] [0.00, 0.01][0.00,\,0.01] [0.00, 0.01][0.00,\,0.01] [0.00, 0.01][0.00,\,0.01] [0.00, 0.00][0.00,\,0.00] [0.00, 0.00][0.00,\,0.00] 15 30 [0.00, 0.03][0.00,\,0.03] [0.00, 0.01][0.00,\,0.01] [0.00, 0.01][0.00,\,0.01] [0.00, 0.00][0.00,\,0.00] [0.00, 0.00][0.00,\,0.00] [0.00, 0.00][0.00,\,0.00] 31 31 [0.00, 0.04][0.00,\,0.04] [0.00, 0.01][0.00,\,0.01] [0.00, 0.01][0.00,\,0.01] [0.00, 0.00][0.00,\,0.00] [0.00, 0.00][0.00,\,0.00] [0.00, 0.00][0.00,\,0.00] 31 62 [0.00, 0.01][0.00,\,0.01] [0.00, 0.00][0.00,\,0.00] [0.00, 0.00][0.00,\,0.00] [0.00, 0.00][0.00,\,0.00] [0.00, 0.00][0.00,\,0.00] [0.00, 0.00][0.00,\,0.00] 63 63 [0.00, 0.00][0.00,\,0.00] [0.00, 0.00][0.00,\,0.00] [0.00, 0.00][0.00,\,0.00] [0.00, 0.00][0.00,\,0.00] [0.00, 0.00][0.00,\,0.00] [0.00, 0.00][0.00,\,0.00] 63 126 [0.00, 0.00][0.00,\,0.00] [0.00, 0.00][0.00,\,0.00] [0.00, 0.00][0.00,\,0.00] [0.00, 0.00][0.00,\,0.00] [0.00, 0.00][0.00,\,0.00] [0.00, 0.00][0.00,\,0.00] 127 127 [0.00, 0.00][0.00,\,0.00] [0.00, 0.00][0.00,\,0.00] [0.00, 0.00][0.00,\,0.00] [0.00, 0.00][0.00,\,0.00] [0.00, 0.00][0.00,\,0.00] [0.00, 0.00][0.00,\,0.00] 127 254 [0.00, 0.00][0.00,\,0.00] [0.00, 0.00][0.00,\,0.00] [0.00, 0.00][0.00,\,0.00] [0.00, 0.00][0.00,\,0.00] [0.00, 0.00][0.00,\,0.00] [0.00, 0.00][0.00,\,0.00] Table 6: Proportion of non-M[agno]-WEF1 allocations (95% CI) - Correlated preferences - RW - Comb tree. Columns: (φ1,φ2)( _1, _2). N M (2,2)(2,2) (2,8)(2,8) (8,2)(8,2) (8,8)(8,8) 15 15 [0.00, 0.00][0.00,\,0.00] [0.00, 0.00][0.00,\,0.00] [0.00, 0.00][0.00,\,0.00] [0.00, 0.00][0.00,\,0.00] 15 30 [0.00, 0.00][0.00,\,0.00] [0.00, 0.00][0.00,\,0.00] [0.00, 0.00][0.00,\,0.00] [0.00, 0.00][0.00,\,0.00] 31 31 [0.00, 0.00][0.00,\,0.00] [0.00, 0.00][0.00,\,0.00] [0.00, 0.00][0.00,\,0.00] [0.00, 0.00][0.00,\,0.00] 31 62 [0.00, 0.00][0.00,\,0.00] [0.00, 0.00][0.00,\,0.00] [0.00, 0.00][0.00,\,0.00] [0.00, 0.00][0.00,\,0.00] 63 63 [0.00, 0.00][0.00,\,0.00] [0.00, 0.01][0.00,\,0.01] [0.00, 0.00][0.00,\,0.00] [0.00, 0.00][0.00,\,0.00] 63 126 [0.00, 0.00][0.00,\,0.00] [0.00, 0.00][0.00,\,0.00] [0.00, 0.00][0.00,\,0.00] [0.00, 0.00][0.00,\,0.00] 127 127 [0.00, 0.00][0.00,\,0.00] [0.00, 0.00][0.00,\,0.00] [0.00, 0.00][0.00,\,0.00] [0.00, 0.00][0.00,\,0.00] 127 254 [0.00, 0.00][0.00,\,0.00] [0.00, 0.00][0.00,\,0.00] [0.00, 0.00][0.00,\,0.00] [0.00, 0.00][0.00,\,0.00]