Source-linked AI summary
Multilevel Fair Allocation under Additive Preferences
Maxime Lucet, Nawal Benabbou, Aurélie Beynier, Nicolas Maudet
TL;DR
The paper studies fair allocation of indivisible goods among agents organized in tree-structured hierarchies, where fairness must be adapted because internal nodes evaluate bundles indirectly. It proposes three envy-based estimators and analyzes Multilevel Weighted Round Robin, finding coincidence and guarantees under identical preferences, selective guarantees under general preferences, and strong practical performance for agnostic fairness.
Problem
Internal nodes cannot directly evaluate alternative bundles because their utilities depend on how those bundles are allocated among descendants, requiring adapted envy-based fairness notions.
Method
The paper defines pessimistic, agnostic, and optimistic bundle estimators and studies their multilevel envy-based fairness notions alongside Multilevel Weighted Round Robin.
Results
Under identical preferences, the three notions coincide and MWRR guarantees them; under general preferences, MWRR formally guarantees only M[pess]-WEF1 but performs well for M[agno]-WEF1 in experiments.
Takeaways & Limitations
The choice of bundle estimator is consequential: MWRR’s formal fairness guarantees differ across notions, while agnostic fairness is observed in almost all tested instances.
Takeaways & Limitations
Existence of M[agno]-WEF1 allocations under normalized utilities remains open, and MWRR may fail to find one even when it exists.
Abstract
from arXiv · showhide
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.
1 Introduction
The paper extends fair allocation from individuals and groups to agents organized in tree-structured hierarchies, where fairness is enforced locally among siblings. It models both explicit organizational structures and implicit priority hierarchies, and introduces multiple envy-based adaptations for this setting.
- Motivation: Multilevel fair allocation models agents as nodes in a directed tree, with each parent allocating its received bundle among its children.The setting generalizes allocation across individuals and groups to arbitrary hierarchical structures.
- Motivation: Fairness is enforced locally among entities at the same level because agents at different hierarchical levels are not directly comparable.Examples include departments within regions and cities within departments in a food charity.
- Motivation: Implicit hierarchies can prioritize fairness across severity and then apply different priorities within severity groups, such as risk or age.The paper also identifies affirmative action schemes as another possible source of implicit hierarchy.
- Modeling choices: Internal nodes represent their constituents and use utilitarian welfare, while leaves have additive preferences over items.The paper adopts this model for representative bodies that receive items only to allocate them to their children.
- Contribution: The paper proposes three envy-based fairness adaptations based on pessimistic, agnostic, and optimistic bundle-value estimates.It investigates whether Multilevel Weighted Round Robin can guarantee fairness at multiple levels under these alternatives.
2 Model
The model represents complete allocations on an arborescence and combines additive leaf utilities with utilitarian internal-node welfare. Because internal nodes evaluate allocations rather than bundles directly, the paper defines three bundle-estimation approaches and corresponding multilevel envy criteria.
- Hierarchical structure: Goods are distributed among agents arranged in an arborescence, with node weights, parent-child relations, ancestors, and leaf subtrees defined structurally.The root is node 1 under a topological ordering, and each node has a unique parent except the root.
- Allocations: A complete multilevel allocation gives the root all goods and partitions each internal node’s bundle completely among its children without sibling overlap.These conditions prevent goods from being discarded a priori and ensure each item reaches at most one child at every split.
- Utility model: Internal nodes use utilitarian welfare over their children, while each leaf values a bundle additively as the sum of its item utilities.For a leaf x, ux(S) = P g∈S ux(g).
- Estimated utilities: Standard envy criteria cannot be applied directly because internal-node utilities are defined over multilevel allocations rather than item bundles.The paper therefore introduces estimated utility functions for evaluating alternative bundles.
- Estimated utilities: Optimistic estimation assumes a utilitarian-optimal allocation to leaves, pessimistic estimation assumes a welfare-minimizing allocation, and agnostic estimation uses a weighted average over leaves.The three estimates encode different assumptions about how a node’s bundle will be allocated internally.
- Fairness: The resulting M[E]-WEF, M[E]-WEF1, and M[E]-WEFX notions compare sibling bundles using one of the three estimated utility functions.When the tree has height one, these notions coincide with classical WEF, WEF1, and WEFX.
- Fairness: An example shows that the fairness judgment can change with the estimator: optimistic evaluation finds envy up to one good, whereas agnostic and pessimistic evaluation do not.The differing estimates arise from assigning the alternative bundle optimally, by weighted average, or to minimize welfare.
3 Identical additive valuations
Under identical additive valuations, multilevel envy notions simplify and coincide, while polynomial-time extensions of weighted fair-division algorithms provide multilevel fairness guarantees. MWRR guarantees M-WEF1 under root-child-common valuations and arbitrary weights, with stronger leaf-level guarantees under uniform structural weights.
- Coinciding fairness notions: Under all-common and root-child-common valuations, the allocation within an internal node's subtree does not affect that node's utility, so the three estimated utilities coincide.Consequently, M-WEF definitions based on pessimistic, agnostic, and optimistic estimates also coincide.
- All-common valuations: A polynomial-time algorithm computes an M-WEFX allocation under all-common valuations.The algorithm repeatedly assigns the highest-valued remaining good to a leaf reached by selecting the child with the least weighted bundle value at each level.
- All-common valuations: Under all-common valuations with wi = |L(i)|, a polynomial-time algorithm achieves M-WEF1 together with EFX among all leaves.The construction includes Multilevel Weighted Round Robin as one component.
- Multilevel Weighted Round Robin: MWRR selects children by minimum weighted picking score, recursively descends to a leaf, assigns that leaf its highest-valued remaining item, and updates scores along the path.Its stated implementation runs in O(m(n^2 + m)).
- Multilevel Weighted Round Robin: Under root-child-common valuations and arbitrary weights, MWRR returns an M-WEF1 allocation in polynomial time.With wi = |L(i)|, it also guarantees EF1 among all leaves.
- Scope of the results: The identical-valuation results extend earlier algorithms to multilevel fairness properties, sometimes jointly with fairness at the leaves.The subsequent analysis studies which guarantees remain under general additive valuations.
4 General additive valuations
Under general additive valuations, the three multilevel WEF1 adaptations form a strict implication structure, while MWRR formally guarantees only the pessimistic notion. Experiments show that agnostic fairness is nevertheless achieved in almost all tested instances, whereas optimistic fairness is much more variable.
- Relations among M[E]-WEF1 notions: The three adaptations satisfy a hierarchy: failure of M[pess]-WEF1 implies failure of M[agno]-WEF1, which implies failure of M[opt]-WEF1.The reverse implications do not generally hold.
- MWRR guarantees: MWRR always returns an M[pess]-WEF1 allocation under general additive valuations.The proof adapts the Weighted Round Robin guarantee recursively across the hierarchy.
- Existence: Under general valuations, an M[agno]-WEF1 allocation need not exist.The impossibility example uses leaves valuing every item at 2 in some subtrees and 1 in others.
- MWRR limitations: MWRR does not guarantee M[agno]-WEF1 or M[opt]-WEF1, even when such allocations exist.The paper gives an instance where MWRR fails M[agno]-WEF1 despite an M[agno]-WEF1 allocation existing, and derives the corresponding optimistic failure.
- Approximation: For any constant α > 0, some instance makes MWRR's allocation fail to be an α-approximation of M[agno]-WEF1.The construction forces α ≤ 2/M, and M can be arbitrarily large.
- Experimental results: Fewer than 50 of 192,000 generated instances were not M[agno]-WEF1, while M[opt]-WEF1 performance varied substantially with tree structure, size, and weights.Comb trees with large n and random weights were particularly challenging for M[opt]-WEF1; weight choice was the most influential factor.
5 Conclusion
The paper introduces three envy-based multilevel fairness notions and characterizes when MWRR guarantees them. Under general valuations, formal guarantees weaken, although MWRR performs well empirically for agnostic fairness.
- 5 Conclusion: The paper proposes M[pess]-WEF1, M[agno]-WEF1, and M[opt]-WEF1 based on different bundle-value estimates.These notions extend envy-based fairness to tree-structured allocations with additive leaf preferences and utilitarian internal-node utilities.
- 5 Conclusion: Under identical preferences, the three notions coincide and MWRR can satisfy them together with completeness.The guarantee is stated for multilevel fair division with indivisible goods organized in a hierarchy.
- 5 Conclusion: Under general valuations, MWRR guarantees only M[pess]-WEF1 but performs very well in practice for M[agno]-WEF1.The conclusion distinguishes the formal guarantee from the algorithm’s empirical performance.
- 5 Conclusion: Existence of M[agno]-WEF1 allocations under normalized utilities remains open, and MWRR may fail even when such an allocation exists.The cited discussion notes that the nonexistence example relies on non-normalized utilities, while the algorithmic failure persists in a normalized example.
- 5 Conclusion: Broader leaf utilities and internal-node utilities incorporating their own preferences are identified as natural extensions.One example is internal nodes preferring balanced allocations across subgroups rather than purely aggregating children’s utilities.
A. Missing proofs from Section 3
The appendix develops polynomial-time guarantees under common valuations by combining leaf-level EFX allocation with multilevel weighted round robin over representative goods.
- A. Missing proofs from Section 3: Under all-common valuations, a polynomial-time algorithm returns an allocation that is M-WEF1 and EFX between all leaves.This is the stated guarantee of Theorem 2 for weights wi = |L(i)|.
- A. Missing proofs from Section 3: Sequential Maximin first computes an EFX leaf allocation, then replaces leaf bundles with representative goods valued by their excess over the least-valued bundle.For leaf x, the representative-good value is ˆu(rx) = u(Ax) − u(Aℓ).
- A. Missing proofs from Section 3: MWRR allocates the representative goods on the hierarchy, after which each representative good is replaced by its corresponding leaf bundle.The construction initializes the root with all goods and reconstructs descendant bundles from the representative-good allocation.
- A. Missing proofs from Section 3: If the representative-good allocation is M-WEF1, replacing representative goods by their corresponding bundles preserves M-WEF1.This is the key lifting step connecting the auxiliary allocation to the original multilevel allocation.
- A. Missing proofs from Section 3: Under root-child-common valuations, MWRR is M-WEF1 and EF1 between all leaves.The all-common case is a special case, and under identical preferences the three adapted WEF1 notions coincide.
B. Missing proofs from Section 4
The appendix proves MWRR’s pessimistic WEF1 guarantee by showing that its weighted picking sequence controls cross-child envy at every internal node.
- B. Missing proofs from Section 4: For any internal node and bundle, the agnostic estimated utility is a convex combination of the utilities of its leaves.This establishes the relationship between internal-node agnostic estimates and leaf utilities.
- B. Missing proofs from Section 4: MWRR always returns an M[pess]-WEF1 allocation.The theorem concludes by applying the partial-allocation argument recursively across internal nodes.
- B. Missing proofs from Section 4: At height-one internal nodes, MWRR coincides with the least weight-adjusted frequent-picker procedure, so the classical WEF1 proof applies.The difference in tie-breaking does not affect that proof.
- B. Missing proofs from Section 4: MWRR’s selection counts satisfy the conditions needed to show pessimistic weighted envy-freeness up to the first item picked.Lemma 6 establishes this property in partial allocations, and the argument applies to every internal node and child pair.
- B. Missing proofs from Section 4: The proof tracks the minimum values that one child assigns to items received by another during successive picks.These values are denoted β1, β2, ..., βti and are combined with the intervening pick counts in the induction.
C. Additional experimental results
The appendix details a four-model experimental protocol for generating hierarchical preferences and reports where MWRR violates M[agno]-WEF1. Across the reported table settings, violations are concentrated in comb trees with random weights.
- Experimental protocol: Experiments used four preference-generation methods to test MWRR across diverse hierarchical preference structures.The methods include Mallows, resampling-Dirichlet, cost utilities, and correlated utilities.
- Preference generation: Mallows preferences are generated recursively from a root ranking, with each internal node assigning its own dispersion parameter to control sibling similarity.Lower ϕ_i produces more similar sibling rankings, while higher values produce greater diversity.
- Preference generation: Resampling-Dirichlet utilities begin from a central approval vector and convert each leaf’s approved-item ranking into a Dirichlet-sampled normalized utility vector.The construction uses approval probability p ∈ {0.3, 0.6, 0.9} and a parameter t controlling approved-item utilities.
- Additional results: The appendix reports separate proportions of non-M[agno]-WEF1 allocations for Mallows, resampling-Dirichlet, cost-utility, and correlated-preference settings on comb trees.Tables 3–6 use 95% confidence intervals and parameterized columns for the corresponding preference models.
- Additional results: Fewer than 50 of 192,000 generated instances produced non-M[agno]-WEF1 allocations, with such cases occurring only for comb trees with random weights across the reported preference methods.The appendix provides the detailed tables for these rare instances.