Multilevel Fair Allocation under Additive Preferences

Maxime Lucet; Nawal Benabbou; Aurélie Beynier; Nicolas Maudet

cs.GTAug 25, 2026

Multilevel Fair Allocation under Additive Preferences

Authors: Maxime Lucet, Nawal Benabbou, Aurélie Beynier, Nicolas Maudet

Organizations: 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 (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.

Figures & tables

Panel of Figure 3 — Figure 3: Tree of Example 2.

Panel of Figure 4 — Figure 4: Tree of Example 3

Panel of Figure 5 — Figure 5: Tree of Theorem 4.4

$n$	$m$	Comb	Balanced	Partially unbalanced
small	$\hskip 8.50012ptn\hskip 8.50012pt$	$\hskip 8.50012pt0.0002\pm 0.0001\hskip 8.50012pt$	$\hskip 8.50012pt0.0002\pm 0.0000\hskip 8.50012pt$	$0.0003\pm 0.0001$
small	$2n$	$0.0003\pm 0.0001$	$0.0003\pm 0.0001$	$0.0007\pm 0.0001$
medium-	$n$	$0.0006\pm 0.0003$	$0.0005\pm 0.0001$	$0.0010\pm 0.0001$
medium-	$2n$	$0.0012\pm 0.0006$	$0.0011\pm 0.0001$	$0.0025\pm 0.0003$
medium+	$n$	$0.0027\pm 0.0018$	$0.0017\pm 0.0001$	$0.0038\pm 0.0003$
medium+	$2n$	$0.0057\pm 0.0034$	$0.0041\pm 0.0003$	$0.0099\pm 0.0012$

Table 1: Average running time (s)

\pm

std.

		Comb		Balanced		Part. unbal.
$n$	$m$	RW	LW	RW	LW	RW	LW
small	$n$	$[0.25,\,0.27]$	$[0.02,\,0.03]$	$[0.02,\,0.03]$	$[0.03,\,0.04]$	$[0.05,\,0.06]$	$[0.04,\,0.05]$
small	$2n$	$[0.24,\,0.27]$	$[0.01,\,0.02]$	$[0.02,\,0.03]$	$[0.02,\,0.03]$	$[0.06,\,0.07]$	$[0.04,\,0.05]$
medium-	$n$	$[0.53,\,0.56]$	$[0.02,\,0.03]$	$[0.09,\,0.11]$	$[0.09,\,0.11]$	$[0.14,\,0.17]$	$[0.12,\,0.14]$
medium-	$2n$	$[0.57,\,0.60]$	$[0.01,\,0.01]$	$[0.08,\,0.09]$	$[0.09,\,0.10]$	$[0.14,\,0.16]$	$[0.11,\,0.12]$
medium+	$n$	$[0.70,\,0.73]$	$[0.01,\,0.02]$	$[0.21,\,0.23]$	$[0.21,\,0.23]$	$[0.29,\,0.32]$	$[0.22,\,0.25]$

Table 2: Proportion of non-M[opt]-WEF1 allocations (95% CI).

$N$	$M$	$(2,2)$	$(2,8)$	$(8,2)$	$(8,8)$
15	15	$[0.00,\,0.01]$	$[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]$
31	31	$[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.01]$
63	63	$[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]$

Table 3: Proportion of non-M[agno]-WEF1 allocations (95% CI) - Mallows - RW - Comb tree. Columns:

(\varphi_{1},\varphi_{2})

$N$	$M$	$(3,2)$	$(3,8)$	$(6,2)$	$(6,8)$	$(9,2)$	$(9,8)$
15	15	$[0.00,\,0.05]$	$[0.00,\,0.01]$	$[0.00,\,0.02]$	$[0.00,\,0.01]$	$[0.00,\,0.00]$	$[0.00,\,0.00]$
15	30	$[0.00,\,0.02]$	$[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.01]$	$[0.00,\,0.00]$	$[0.00,\,0.01]$	$[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]$
63	63	$[0.00,\,0.00]$	$[0.00,\,0.00]$	$[0.00,\,0.00]$	$[0.00,\,0.01]$	$[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]$

Table 4: Proportion of non-M[agno]-WEF1 allocations (95% CI) - resampling dirichlet - RW - Comb tree. Columns:

(p,\varphi)

$N$	$M$	$(3,2)$	$(3,8)$	$(6,2)$	$(6,8)$	$(9,2)$	$(9,8)$
15	15	$[0.00,\,0.04]$	$[0.00,\,0.01]$	$[0.00,\,0.01]$	$[0.00,\,0.01]$	$[0.00,\,0.00]$	$[0.00,\,0.00]$
15	30	$[0.00,\,0.03]$	$[0.00,\,0.01]$	$[0.00,\,0.01]$	$[0.00,\,0.00]$	$[0.00,\,0.00]$	$[0.00,\,0.00]$
31	31	$[0.00,\,0.04]$	$[0.00,\,0.01]$	$[0.00,\,0.01]$	$[0.00,\,0.00]$	$[0.00,\,0.00]$	$[0.00,\,0.00]$
31	62	$[0.00,\,0.01]$	$[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]$
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]$

Table 5: Proportion of non-M[agno]-WEF1 allocations (95% CI) - Cost utilities - RW - Comb tree. Columns:

(p,\varphi)

$N$	$M$	$(2,2)$	$(2,8)$	$(8,2)$	$(8,8)$
15	15	$[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]$
31	31	$[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]$
63	63	$[0.00,\,0.00]$	$[0.00,\,0.01]$	$[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]$

Table 6: Proportion of non-M[agno]-WEF1 allocations (95% CI) - Correlated preferences - RW - Comb tree. Columns:

(\varphi_{1},\varphi_{2})

Fair Resource Allocation

Fair resource allocation studies how to distribute scarce goods, services, and computing capacity equitably while accounting for efficiency and constraints.

See all 59 papers

Allocating Indivisible Goods to Strategic Agents: Pure Nash Equilibria and Fairness
Sep 17, 2021Georgios Amanatidis, Georgios Birmpas, Federico Fusco +3Fair Resource Allocation Nash Equilibrium
School of Mathematics, Statistics and Actuarial Science, University of Essex, UK. · Archimedes/Athena RC, Greece. · Department of Computer Science, University of Liverpool, UK. +3
Trading Utility for Dynamic Fairness in Multiple Resource Division with Sequential Demand
Jun 9, 2026Kaiqi Jiang, Karim El Husseini, Wenzhe Fan +1Sequential Decision Making Fair Resource Allocation
Computer Science Dept., University of Illinois Chicago, Chicago, Illinois, USA
Fair Online Resource Allocation
Jun 17, 2026Christopher En, Yuri Faenza, Andrea Lodi +1Sequential Decision Making Fair Resource Allocation
Columbia University, IEOR Department · Cornell Tech · Universidad de Chile

Sep 17, 2021J/K move · Enter open · S save

Allocating Indivisible Goods to Strategic Agents: Pure Nash Equilibria and Fairness

Georgios Amanatidis, Georgios Birmpas, Federico Fusco, Philip Lazos+2

School of Mathematics, Statistics and Actuarial Science, University of Essex, UK. · Archimedes/Athena RC, Greece. · Department of Computer Science, University of Liverpool, UK.+3

Fair Resource Allocation Nash Equilibrium Social Choice Theory

Open paper AskPDF arXiv

We consider the problem of fairly allocating a set of indivisible goods to a set of strategic agents with additive valuation functions. We assume no monetary transfers and, therefore, a mechanism in our setting is an algorithm that takes as input the reported -- rather than the true -- values of the agents. Our main goal is to explore whether there exist mechanisms that have pure Nash equilibria for every instance and, at the same time, provide fairness guarantees for the allocations that correspond to these equilibria. We focus on two relaxations of envy-freeness, namely envy-freeness up to one good (EF1), and envy-freeness up to any good (EFX), and we positively answer the above question. In particular, we study two algorithms that are known to produce such allocations in the non-strategic setting: Round-Robin (EF1 allocations for any number of agents) and a cut-and-choose algorithm of Plaut and Roughgarden [SIAM Journal of Discrete Mathematics, 2020] (EFX allocations for two agents). For Round-Robin we show that all of its pure Nash equilibria induce allocations that are EF1 with respect to the underlying true values, while for the algorithm of Plaut and Roughgarden we show that the corresponding allocations not only are EFX but also satisfy maximin share fairness, something that is not true for this algorithm in the non-strategic setting! Further, we show that a weaker version of the latter result holds for any mechanism for two agents that always has pure Nash equilibria which all induce EFX allocations.

Abstract

Fair Resource Allocation

Explore similar work

Allocating Indivisible Goods to Strategic Agents: Pure Nash Equilibria and Fairness

Trading Utility for Dynamic Fairness in Multiple Resource Division with Sequential Demand

Fair Online Resource Allocation