{'fraction_non_alphanumeric': 0.05393877922550779, 'fraction_numerical': 0.01843905230033029, 'mean_word_length': 3.882173692229558, 'pattern_counts': {'":': 1, '<': 6, '<?xml version=': 0, '>': 7, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 16, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Weighted Envy-Freeness for Submodular Valuations

We investigate the fair allocation of indivisible goods to agents with possibly different entitlements represented by weights. Previous work has shown that guarantees for additive valuations with existing envy-based notions cannot be extended to the case where agents have matroid-rank (i.e., binary submodular) valuations. We propose two families of envy-based notions for matroid-rank and general submodular valuations, one based on the idea of transferability and the other on marginal values. We show that our notions can be satisfied via generalizations of rules such as picking sequences and maximum weighted Nash welfare. In addition, we introduce welfare measures based on harmonic numbers, and show that variants of maximum weighted harmonic welfare offer stronger fairness guarantees than maximum weighted Nash welfare under matroid-rank valuations.


Introduction
Fair division refers to the study of how to fairly allocate resources among agents with possibly differing preferences. Over the 70 years since Steinhaus [1948] initiated a mathematical framework of fair division, the field has given rise to numerous fairness notions and procedures for computing fair outcomes in a variety of scenarios [Brams andTaylor, 1996, Moulin, 2003]. For instance, in the common scenario of allocating indivisible goods, the notion envy-freeness up to one good (EF1) has emerged as a standard benchmark. An allocation of the goods satisfies EF1 if any envy that an agent has toward another agent can be eliminated by removing some good in the latter agent's bundle. Even when agents have arbitrary monotonic valuations over the goods, an EF1 allocation always exists and can be found in polynomial time [Lipton et al., 2004].
The definitions of many fairness notions in the literature, including EF1, inherently assume that all agents have the same entitlement to the resource. In the past few years, several researchers have examined a more general model in which different agents may have different weights reflecting their entitlements to the goods [Farhadi et al., 2019, Aziz et al., 2020, Babaioff et al., 2021a,c, Chakraborty et al., 2021a,b, 2022, Garg et al., 2020, Scarlett et al., 2021, Hoefer et al., 2022, Suksompong and Teh, 2022, Viswanathan and Zick, 2022a. This model allows us to capture settings such as inheritance division, in which relatives are typically entitled to unequal shares of the legacy, as well as resource allocation among groups or organizations of different sizes. Chakraborty et al. [2021a] generalized EF1 to weighted EF1 (WEF1): for instance, if Alice's weight is three times as high as Bob's, then WEF1 stipulates that, after removing some good from Bob's bundle, Alice should have at least three times as much value for her own bundle as for Bob's. The same authors demonstrated that if agents have additive valuations over the goods, a complete WEF1 allocation always exists and can be computed efficiently. 1 However, they provided the following example showing that existence is no longer guaranteed once we move beyond additivity.
Example 1.1 (Chakraborty et al. [2021a]). Consider an instance with n = 2 agents whose weights are w 1 = 1 and w 2 = 2, and m ≥ 6 goods. Agent 1 has an additive valuation with value 1 for every good, whereas agent 2 has value 0 for the empty bundle and 1 for any nonempty bundle. If agent 1 is allocated more than one good, then agent 2 has weighted envy toward agent 1 even after removing any good from agent 1's bundle. Thus, assuming that all goods need to be allocated, agent 2 obtains at least m − 1 goods. Again, this causes weighted envy according to WEF1, this time from agent 1 toward agent 2. Hence, no complete WEF1 allocation exists in this instance.
The impossibility result illustrated in this example still holds even if WEF1 is relaxed to weak WEF1 (WWEF1), whereby an agent is allowed to either remove a good from the other agent's bundle or copy one such good into her own bundle, 2 and stands in contrast to the aforementioned EF1 guarantee in the unweighted setting [Lipton et al., 2004]. In light of these observations, Chakraborty et al. [2021a] left open the direction of identifying appropriate envy-based notions for non-additive valuations. Note also that the valuations in Example 1.1 are particularly simple: both agents have binary submodular valuations, that is, submodular valuations 3 in which the marginal gain from receiving any single good is either 0 or 1. Binary submodular valuations are also known as matroid-rank valuations, and have been studied in a number of recent fair division papers, mostly in the unweighted setting [Babaioff et al., 2021b, Barman and Verma, 2021, Benabbou et al., 2021, Goko et al., 2022, Viswanathan and Zick, 2022a. 4 Such valuations arise in settings such as the allocation of course slots to students, or apartments in public housing estates to ethnic groups [Benabbou et al., 2021].
In this paper, we explore weighted envy-freeness for both matroid-rank and general submodular valuations. We propose new envy-based notions and show that they can be satisfied in these settings, not only via extensions of existing algorithms, but also via new rules. For the sake of generality, we define our notions based on the notion WEF(x, 1 − x) of Chakraborty et al. [2022]. With additive valuations, given a parameter x ∈ [0, 1], WEF(x, 1 − x) allows each agent i to subtract x times the value of some good in another agent j's bundle from i's value for this bundle, and add (1 − x) times the value of this good to the value of i's own bundle. WEF1 corresponds to WEF(1, 0), and higher values of x yield notions that favor lower-weight agents. Chakraborty et al. [2022] showed that for any instance with additive valuations and any x, a complete WEF(x, 1 − x) allocation always exists; on the other hand, they proved that for any distinct x and x ′ , there is an instance with binary additive valuations and identical goods in which no complete allocation satisfies both WEF(x, 1 − x) and WEF(x ′ , 1 − x ′ ).

Our Contributions
In Section 2, we introduce two new families of weighted envy-freeness notions. The first family, TWEF(x, 1−x), is based on the concept of "transferability": 5 we consider the condition TWEF(x, 1−x) from agent i to agent j to be violated only if the WEF(x, 1 − x) condition between i and j fails and i's value for her own bundle does not increase even if all goods from j's bundle are transferred to i's bundle. TWEF(x, 1 − x) handles instances such as the one in Example 1.1, where an agent could be unsatisfied with respect to WEF(x, 1 − x) even if she already receives her maximum possible utility. Our second family, WMEF(x, 1−x), is an extension of the notion marginal EF1 (MEF1) of Caragiannis et al. [2019] from the unweighted setting. The idea is that, instead of agent i considering her value for agent j's bundle as in WEF(x, 1 − x), agent i considers her marginal value of j's bundle when added to i's own bundle. While TWEF(x, 1 − x) is stronger than WMEF(x, 1 − x), we show that the former notion is suitable primarily for matroid-rank valuations, whereas the latter can be guaranteed even for general submodular valuations.
In Sections 3 and 4, we allow agents to have arbitrary submodular valuations. In Section 3, we investigate picking sequences, which let agents take turns picking a good according to a specified agent ordering until the goods run out. While previous work on picking sequences typically assumed that agents have additive valuations, this assumption may be violated in real-world applications of picking sequences, such as the allocation of ministries to political parties. We adjust picking sequences to submodular valuations by letting agents pick a good with the highest marginal gain in each of their turns. We show that for every x, the output of the adjusted version of the picking sequence proposed by Chakraborty et al. [2022] with parameter x satisfies WMEF(x, 1 − x); this generalizes their result from the weighted additive setting. As a corollary, in the unweighted submodular setting, the adjusted version of the commonly studied round-robin algorithm produces an MEF1 allocation. In Section 4, we consider the maximum weighted Nash welfare (MWNW) rule, which chooses an allocation that maximizes the weighted product of the agents' utilities. Although prior results rule out the possibility that MWNW implies WMEF(x, 1 − x) for any x, we show that an MWNW allocation always satisfies a relaxation of WMEF(x, 1 − x) called weak weighted MEF1 (WWMEF1). This extends a corresponding result of Chakraborty et al. [2021a] from the weighted additive setting, which is in turn a generalization of the prominent result by Caragiannis et al. [2019] in the unweighted additive setting.
Next, in Sections 5 and 6, we focus on agents with matroid-rank valuations. In Section 5, we extend the "transfer algorithm" of Benabbou et al. [2021] from the unweighted setting, and prove that our algorithm returns a clean 6 TWEF(x, 1 − x) allocation that maximizes the unweighted utilitarian welfare. While Benabbou et al.'s potential function argument can be generalized to show that our algorithm terminates, it is insufficient for establishing polynomial-time termination in our setting with different weights; hence, we devise a more elaborate argument for this purpose. Finally, in Section 6, we introduce new welfare measures based on harmonic numbers and their variants. 7 Perhaps surprisingly, we demonstrate that the maximum-welfare rules based on our measures offer stronger fairness guarantees compared to MWNW under matroid-rank valuations. In particular, while MWNW does not imply WEF(x, 1 − x) for any x even with binary additive valuations and identical goods [Chakraborty et al., 2022], we prove that a clean maximum weighted harmonic welfare allocation parameterized by x satisfies TWEF(x, 1 − x) for matroid-rank valuations (and therefore WEF(x, 1 − x) for binary additive valuations). 8

Preliminaries
Let N = [n] be the set of agents and G = {g 1 , . . . , g m } be the set of indivisible goods, where [k] := {1, . . . , k} for any positive integer k. A bundle refers to a subset of G. Each agent i ∈ N has a weight w i > 0 representing her entitlement, and a valuation function (or utility function) v i : 2 G → R ≥0 . The setting where all of the weights are equal is sometimes referred to as the unweighted setting. For convenience, we write v i (g) instead of v i ({g}) for a single good g. We assume throughout the paper that v i is 6 An allocation is clean if no good can be discarded from an agent's bundle without decreasing the agent's utility [Benabbou et al., 2021]. The term non-redundant has also been used with the same meaning [Babaioff et al., 2021b]. 7 The harmonic welfare measure is the basis of the proportional approval voting (PAV) rule in the context of approval-based committee voting [Lackner and Skowron, 2022]. To the best of our knowledge, we are the first to consider this measure in the context of fair division. 8 To further exhibit the potential of harmonic welfare, we show in Appendix C that, in the unweighted additive setting, if each agent's value for each good is an integer, then a maximum harmonic welfare allocation always satisfies EF1.
The function v i is said to be matroid-rank (or binary submodular) if it is submodular and v and binary additive if it is additive and v i (g) ∈ {0, 1} for all g ∈ G. An instance consists of the set of agents N , the set of goods G, and the agents' weights (w i ) i∈N and valuation functions (v i ) i∈N .
An allocation A is a list of bundles (A 1 , . . . , A n ) such that no two bundles overlap, where bundle A i is assigned to agent i. The allocation is complete for all i ∈ N and the inequality is strict for at least one i ∈ N ; such an allocation A ′ is said to Pareto-dominate A. For each i ∈ N , we denote by N + A the subset of agents receiving positive utility from A. The unweighted utilitarian welfare of A is defined as i∈N v i (A i ).
For a bundle G ′ ⊆ G, we define the marginal gain of a good g ∈ G ′ for agent i as Similarly, the marginal loss of a good g ∈ G ′ for agent i is defined as Benabbou et al., 2021, Prop. 3.3].
We now introduce our first family of fairness notions, TWEF(x, y). 9 Definition 2.1 (TWEF(x, y)). For x, y ∈ [0, 1], an allocation A is said to satisfy transferable WEF(x, y) (TWEF(x, y)) if, for any pair of agents For any x and y, if valuations are additive, then TWEF(x, y) reduces to the notion WEF(x, y) of Chakraborty et al. [2022]. We will mostly be concerned with the case where y = 1 − x. As we will see, TWEF(x, 1 − x) is a useful notion for matroid-rank valuations. However, like WEF(x, 1 − x), it can be too demanding for general submodular valuations. For instance, in Example 1.1, if agent 2 has value 1 + (|G ′ | − 1) · ε for any nonempty bundle |G ′ |, where ε > 0 is a small constant, then the condition v i (A i ) = v i (A i ∪ A j ) becomes impotent and a complete TWEF(x, 1 − x) allocation does not exist for any x. The second family of notions that we propose, which is based on the marginal EF1 (MEF1) notion of Caragiannis et al. [2019], 10 does not suffer from this shortcoming.
Definition 2.2 (WMEF(x, y)). For x, y ∈ [0, 1], an allocation A is said to satisfy WMEF(x, y) if, for any pair of agents i, j ∈ N , either A j = ∅ or there exists g ∈ A j such that If valuations are additive, WMEF(x, y) reduces to WEF(x, y) for any x and y. On the other hand, if all agents have the same weight, WMEF(x, 1 − x) reduces to MEF1 only if x = 1. The following proposition establishes an implication relationship between our two families of notions.
Proof. Let A be a TWEF(x, y) allocation, and consider any i, j ∈ N . By definition of TWEF(x, y), Assume first that the latter holds.
Hence, the WMEF(x, y) condition between agents i and j is fulfilled.
then the WMEF(x, y) condition between agents i and j is automatically fulfilled. Otherwise, for any good g ∈ A j , we have and WMEF(x, y) between i and j is again fulfilled.
Since the valuations that we consider in this paper are not necessarily additive, in order to reason about the running time of algorithms, we make the standard assumption that an algorithm can query the value of any agent i for any bundle G ′ ⊆ G in constant time.

Picking Sequences
In this section, we investigate picking sequences, which are procedures wherein agents take turns picking a good according to a specified agent ordering until there are no more goods left. For brevity, we will say that a picking sequence satisfies a fairness notion if the allocation that it returns always satisfies that notion. With additive valuations, Chakraborty et al. [2022] showed that for any x ∈ [0, 1], a picking sequence that assigns each subsequent pick to an agent i ∈ N with the smallest ratio t i +(1−x) w i , where t i denotes the number of times agent i has picked so far, satisfies WEF(x, 1 − x). Our main result of this section extends their result to submodular valuations. We make the specification that, in each turn, the agent picks a good that yields the highest marginal gain with respect to the agent's current bundle, breaking ties arbitrarily. More formally, if it is agent i's turn, then i chooses a good g that maximizes where A i is the set of goods i has picked in previous turns.
Theorem 3.1. Let x ∈ [0, 1]. Consider a picking sequence π x such that, in each turn, the pick is assigned to an agent i ∈ N with the smallest ratio , where t i denotes the number of times agent i has picked so far, and the agent picks a good that yields the highest marginal gain. Then, under submodular valuations, π x satisfies WMEF(x, 1 − x).
For any x and agents with equal weights, π x encompasses the popular round-robin algorithm where the agents take turns in the order 1, 2, . . . , n, 1, 2, . . . , n, 1, 2, . . . , and WMEF(1, 0) reduces to MEF1 of Caragiannis et al. [2019]. We therefore have the following corollary, which is also new to the best of our knowledge.

Corollary 3.2. Assume that all agents have equal weights and submodular valuations. Suppose that in each turn of the round-robin algorithm, the picking agent picks a good with the highest marginal gain. Then, the algorithm returns a complete MEF1 allocation.
As Corollary 3.2 admits a more direct proof, which also illustrates the ideas that we will use to show Theorem 3.1, we first present the (shorter) proof of Corollary 3.2.
Proof of Corollary 3.2. Let A be the allocation produced by the round-robin algorithm, and consider any i, j ∈ N . Assume without loss of generality that i < j.
We first establish the MEF1 condition from i toward j. Let k := |A j | ≤ |A i |, and suppose that agent j picks the goods in the order c 1 , c 2 , . . . , c k . Let b 1 , b 2 , . . . , b k be the first k goods picked by agent i in this order.

Combining the previous two inequalities yields
The proof for the MEF1 condition from j toward i is almost identical: by ignoring the first good g picked by agent i and applying the same argument, we have Thus, the MEF1 condition is again satisfied.
In Appendix A, we provide an example demonstrating that the condition MEF1 in Corollary 3.2 cannot be strengthened to EF1, even when agents have matroid-rank valuations.
We now establish Theorem 3.1 by augmenting the proof of Chakraborty et al. [2022, Thm. 3.2] from the additive setting with the ideas from our proof of Corollary 3.2 and arguments involving submodularity.
Proof of Theorem 3.1. Fix two agents i, j ∈ N . For convenience, we write π instead of π x . For any prefix P of π, if i and j pick t i and t j times in P , respectively, then it must be that . Using this property, we will show that the WMEF(x, 1 − x) condition from i to j is satisfied after every prefix of π.
We first prove a general claim that, for any x, y ∈ [0, 1], if the WMEF(x, y) condition from i to j is satisfied with bundles A i and A j , and we add one good h ∈ A i ∪ A j to A i , then the condition remains satisfied. To this end, we show that for every good g and From the definition of WMEF(x, y), these two inequalities suffice to prove our claim. In order to prove inequality (1), we observe that where the inequality follows from submodularity.
We are ready to prove Theorem 3.1. Let ρ = w i /w j and y = 1 − x. From the previous paragraph, it is sufficient to show that the WMEF(x, 1−x) condition from i to j is fulfilled after every pick by agent j. Consider any pick by agent j, and suppose that it is the agent's t j -th pick. We divide the sequence of picks up to this pick into phases, where each phase ℓ ∈ [t j ] consists of the picks after agent j's (ℓ − 1)-th pick up to (and including) the agent's ℓ-th pick. Let A i and A j be the bundle of agent i and j after phase t j , respectively. If A j = ∅, then the WMEF(x, 1 − x) condition from i to j holds trivially, so assume that A j = ∅. In addition, we introduce the following notation: • τ ℓ := the number of times agent i picks in phase ℓ (that is, between agent j's (ℓ − 1)-th and ℓ-th picks); • α ℓ 1 , α ℓ 2 , . . . , α ℓ τ ℓ := agent i's marginal gain for each good that she picks herself in phase ℓ with respect to the goods that she has already picked (including those in phase ℓ, if any); • α ℓ := α ℓ 1 + · · · + α ℓ τ ℓ = the total marginal gain of agent i in phase ℓ with respect to the goods that she has picked in prior phases; • β ℓ := agent i's marginal gain for the good that agent j picks at the end of phase ℓ with respect to A i .
For any integer s ∈ [t j ], applying the condition in the first paragraph of our proof to the picking sequence up to and including phase s, we have Every time it is agent i's turn, she picks a good with the highest marginal gain with respect to her current bundle among the available goods. In particular, in each phase ℓ, she picks τ ℓ goods each of which yields at least as high marginal gain to her as any good not yet picked by agent j. By submodularity, this implies Using (3) and (4), the same inductive argument as in Chakraborty et al.'s proof of their Theorem 3.2 yields Let g * ∈ arg max g∈A j ∆ + i (A i , g), and let g 1 be the first good picked by agent j (possibly g 1 = g * ). Using (5), we get where the second inequality follows from the definition of g * and the last inequality from submodularity.
Here, the second inequality holds by submodularity. As a result, the WMEF(x, 1−x) condition between agents i and j is fulfilled, completing the proof.

Nash Welfare
In this section, we turn our attention to maximum weighted Nash welfare (MWNW), a weighted extension of the well-studied maximum Nash welfare (MNW). MWNW has been studied in several recent papers [Chakraborty et al., 2021a,b, 2022, Garg et al., 2020, Suksompong and Teh, 2022, Viswanathan and Zick, 2022a.
Definition 4.1 (MWNW). Given an instance, an allocation A is a maximum weighted Nash welfare (MWNW) allocation if it maximizes the weighted Nash welfare WNW(A) := i∈N v i (A i ) w i . If the highest possible weighted Nash welfare is 0, an MWNW allocation should maximize the number of agents receiving positive utility and, subject to that, maximize the weighted Nash welfare of these agents. Chakraborty et al. [2022] showed that, for any x ∈ [0, 1], there exists an instance with binary additive valuations and identical goods such that every MWNW allocation is not WEF(x, 1 − x). As a consequence, MWNW allocations cannot always satisfy WMEF(x, 1 − x) for submodular valuations. On the other hand, Chakraborty et al. [2021a] proved that, under additive valuations, MWNW allocations satisfy weak WEF1 (WWEF1), which is weaker than WEF(x, 1 − x) for every x but still reduces to EF1 in the unweighted additive setting. We extend their result to the submodular setting via a natural generalization of WWEF1.
Definition 4.2 (WWMEF1). An allocation A is said to satisfy weak weighted marginal envy-freeness up to one good (WWMEF1) if for any pair of agents i, j with A j = ∅, there exists a good g ∈ A j such that Proof. Let A be an MWNW allocation, and recall that N + A denotes the set of agents who receive positive utility from A. We first prove the PO property. If A were not PO, there would exist an allocation A such A ∪ {j}, contradicting the assumption that N + A is a largest subset of agents to whom it is possible to give positive utility simultaneously. On the other hand, if j ∈ N + A , we would have i∈N + which would mean that A does not maximize the weighted Nash welfare of the agents in N + A , again a contradiction. Therefore, A is PO. Next, we proceed to establish the WWMEF1 property. Following the approach of Caragiannis et al.
[2019] and Chakraborty et al. [2021a], we first prove that A is WWMEF1 for the scenario N + A = N and then address the case where N + A = N . Assume that N + A = N , and suppose for contradiction that A is not WWMEF1. This means that there exists a pair of agents i, j ∈ N such that the WWMEF1 condition between i and j is violated. That is, A j = ∅, and for every good g ∈ A j it holds that and We will construct another allocation A ′ obtained by transferring a good g * (to be chosen later) from A j to A i , so that A ′ i = A i ∪{g * } and A ′ j = A j \{g * }, and the bundles of all other agents remain unchanged. Then, we have

By Lemma C.5 of Caragiannis et al. [2019] (which is a simple application of submodularity), it holds that
Moreover, by submodularity, we have that for every g ′ ∈ A j , and where the last inequality follows from (7). By (11), we have that ∆ + i (A i , g) > 0 for at least one g ∈ A j . Let B = {g ∈ A j : ∆ + i (A i , g) > 0}, and let g * ∈ arg min g∈B g) . Due to our choice of g * and the definition of B, we have . (12) Combining (12) with (9), (10), and (11), we get and We split our remaining argument into two cases. In each case, we will show that the expression in (8) is greater than 1, which results in a contradiction because A is an MWNW allocation.
< 1 and w j w i > 1, Bernoulli's inequality together with (16) implies that a contradiction. This completes the proof for the scenario where N + A = N . Finally, we handle the scenario where N + A N . Let i, j ∈ N with A j = ∅, and consider three cases.
• If i, j ∈ N + A , we can show as in the scenario where N + A = N that the WWMEF1 condition between i and j is satisfied.
If v j (A j \ {g ′ }) > 0, we can transfer g ′ from A j to A i and obtain an allocation with more agents receiving positive utility than in A, a contradiction. Therefore By submodularity, we must have v j (A j ) = 0 as well, contradicting the assumption that j ∈ N + A .
• Suppose that j ∈ N + A . This means that v j (A j ) = 0. If v i (A i ∪ {g}) > v i (A i ) for some g ∈ A j , we can transfer g from A j to A i and obtain an allocation with the same number of agents receiving positive utility as in A but a higher weighted Nash welfare of these agents than in A, a contradiction.
. Therefore, the WWMEF1 condition from i to j is satisfied.
It follows that A is WWMEF1 in all cases. Viswanathan and Zick [2022a] showed that if agents have matroid-rank valuations, then an MWNW allocation can be found in polynomial time. On the other hand, with equal-weight agents and additive valuations, even approximating the maximum Nash welfare is computationally difficult [Lee, 2017].

Transfer Algorithm
For agents with equal weights and matroid-rank valuations, Benabbou et al. [2021, Algorithm 1] proposed a "transfer algorithm" that computes a clean, utilitarian welfare-maximizing EF1 allocation in polynomial time. In this section, we extend their algorithm to the weighted setting. Our algorithm is presented as Algorithm 1; we argue in the proof of Theorem 5.1 that the algorithm is well-defined.
Theorem 5.1. Suppose that all agents have matroid-rank valuations, and let x ∈ [0, 1]. Algorithm 1 with parameter x returns a clean TWEF(x, 1 − x) (and therefore WMEF(x, 1 − x)) allocation that maximizes the unweighted utilitarian welfare among all allocations in polynomial time.
Algorithm 1 For finding a clean TWEF(x, 1 − x) allocation maximizing i∈N v i (A i ) Compute a clean allocation A that maximizes the unweighted utilitarian welfare. while there exist i, j ∈ N such that TWEF(x, 1 − x) from i to j fails with respect to A do Find a good g ∈ A j with ∆ + i (A i , g) = 1.
Since any allocation maximizing the unweighted utilitarian welfare is PO, the allocation output by Algorithm 1 is also PO. In the unweighted setting, Benabbou et al. [2021] exhibited polynomialtime termination of their algorithm using the potential function Φ(A) := i∈N v i (A i ) 2 . As Φ(A) is always an integer between 0 and m 2 and decreases with every transfer, the number of transfers made by their algorithm is at most m 2 . While we can also establish termination of our weighted algorithm by modifying the potential function to , this argument does not yield a polynomial upper bound on the number of transfers, because the potential function may decrease by a very small amount depending on the weights. Therefore, we will instead employ a different, more refined, argument to show that our algorithm terminates in polynomial time as well.
Proof of Theorem 5.1. By Proposition 2.3, it suffices to prove the statement for TWEF(x, 1 − x).
First, we claim that each transfer maintains the welfare optimality and cleanness of the allocation. Indeed, v j (A j ) decreases by 1 because the previous allocation is clean, while v i (A i ) increases by 1 due to the algorithm's choice of the good g ∈ A j . Hence, i∈N v i (A i ) remains the same. Moreover, since v i (A i ) = |A i | for all i ∈ N , the allocation remains clean.
If the TWEF(x, 1 − x) condition from agent i to agent j fails at some point during the execution of the algorithm, it must be that where the latter inequality follows from cleanness.
, by submodularity, there exists g * ∈ A j such that ∆ + i (A i , g * ) = 1; in particular, the algorithm is well-defined. Plugging this good g * into (17) and using the cleanness of A, we get If the algorithm terminates, then TWEF(x, 1 − x) is satisfied for all pairs of agents i, j. We will show that the algorithm always terminates, and moreover does so in polynomial time. The initial clean allocation A can be found in polynomial time [Benabbou et al., 2021]. Checking whether TWEF(x, 1 − x) fails for some pair i, j (and, if so, finding a valid transfer) can be done in polynomial time. It therefore remains to argue that the number of transfers is polynomial. For ease of understanding, we will formulate this argument in terms of cupboards and balls.
Associate each i ∈ N with a cupboard consisting of m shelves at height 1−x w i , 2−x w i , . . . , m−x w i , respectively. For the clean allocation A at the beginning of the algorithm and each i ∈ N , place one ball on each of the |A i | lowest shelves 11 of cupboard i. Whenever a good is transferred from A j to A i , move 11 Note that the sum of the heights of all balls is i∈N , which is exactly half of the potential function mentioned before the proof. the highest ball in cupboard j to the lowest shelf without a ball in cupboard i. This means that the ball is moved from height (18), the height of the ball decreases. Since there are m balls and at most mn heights of the shelves, the number of transfers is at most m 2 n, which is indeed polynomial. 12 This concludes the proof.

Harmonic Welfare
Recall from Section 4 that an MWNW allocation maximizes the product i∈N v i (A i ) w i , or equivalently, the sum i∈N w i · ln v i (A i ). Since ln k is approximately the k-th harmonic number H k := 1 + 1 2 + · · · + 1 k for each positive integer k, one could also consider a maximum weighted harmonic welfare (MWHW) allocation, defined as an allocation maximizing the sum i∈N w i · H v i (A i ) , where H 0 = 0. Interestingly, we show in this section that for agents with matroid-rank valuations, MWHW outperforms MWNW in terms of fairness. Specifically, even though for each x ∈ [0, 1] there exists an instance with binary additive valuations and identical goods in which every MWNW allocation fails WEF(x, 1 − x) [Chakraborty et al., 2022], we show that a clean MWHW allocation satisfies TWEF(0, 1) for matroidrank valuations (and therefore WEF(0, 1) for binary additive valuations). More generally, we define a class of modified harmonic numbers parameterized by x such that a clean maximum-welfare allocation based on each x satisfies TWEF(x, 1 − x).
Definition 6.1 (Modified harmonic numbers). Let k ∈ Z ≥0 . For x ∈ [0, 1), the number H k,x is defined by whereas for x = 1, H k,x is defined by Note that the numbers H k,0 correspond to the canonical harmonic numbers H k , and that for each x, the sequence H 0,x , H 1,x , . . . is increasing. We define a maximum weighted harmonic welfare allocation parameterized by x. Recall that N + A denotes the set of agents who receive positive utility from an allocation A.
Definition 6.2 (MWHW x ). For x ∈ [0, 1), given an instance with matroid-rank valuations, an allocation A is an MWHW x allocation if it maximizes the sum WHW x (A) : For x = 1, A is an MWHW 1 allocation if it maximizes the number of agents receiving positive utility and, subject to that, maximizes the sum i∈N + The quantity H v i (A i ),x is well-defined because, for matroid-rank valuations, v i (A i ) is always a nonnegative integer. We now prove the efficiency and fairness guarantees of MWHW x allocations, starting with efficiency.
Consider the case x = 1. If A were not PO, there would exist an allocation A such that A ∪ {j}, contradicting the assumption that N + A is the largest subset of agents to whom it is possible to give positive utility simultaneously. On the other hand, if j ∈ N + A , we would have i∈N + x , again a contradiction. Therefore, A is PO.
For the fairness guarantee, we will make an assumption that the allocation is clean; we later demonstrate that this assumption is necessary. We also remark that given any MWHW x allocation, one can easily obtain another MWHW x allocation in which every agent receives the same utility as before by iteratively removing any good that does not contribute to its owner's utility until no such good exists.
Proof. By Proposition 2.3, it suffices to prove the statement for TWEF(x, 1 − x).
Let A be a clean MWHW x allocation. Assume for contradiction that for some i, j ∈ N , the TWEF(x, 1 − x) condition from i to j is violated. This means that By the same argument as in the proof of Theorem 5.1, this implies that , submodularity implies that there exists a good g * ∈ A j such that ∆ + i (A i , g * ) = 1. We now consider two cases depending on whether x = 1.
Case 1: 0 ≤ x < 1. If we transfer g * from A j to A i , we obtain an allocation Since A is an MWHW x allocation, it must be that This is equivalent to
Since v i (A i ) ≥ 0 and v j (A j ) is an integer, it must be that v j (A j ) ≥ 2. If v i (A i ) = 0, we can transfer g * from A j to A i and increase the number of agents with positive utility, contradicting the assumption that A is an MWHW 1 allocation. Hence, v i (A i ) ≥ 1.
The rest of the argument proceeds in a similar way as in Case 1. If we transfer g * from A j to A i , we obtain an allocation Note that the number of agents with positive utility is the same in A and A ′ . Since A is an MWHW 1 allocation, it must be that This is equivalent to
We now exhibit the necessity of the cleanness condition in Theorem 6.4.
Proposition 6.5. There exists an instance and an allocation such that, for every x ∈ [0, 1], the allocation is MWHW x but does not satisfy TWEF(x, 1 − x).
To finish the proof, we show that A violates the TWEF(x, 1 − x) condition from agent 2 toward agent 1. Note that v 2 (A 2 ) = 3 < 4 = v 2 (A 2 ∪ A 1 ). Moreover, for any g ∈ A 1 , it holds that Hence, the TWEF(x, 1 − x) condition from agent 2 to agent 1 is not satisfied.
By applying results from the recent work of Viswanathan and Zick [2022a], we show in Appendix B that an MWHW x allocation (which additionally maximizes the unweighted utilitarian welfare across all allocations) can be found in polynomial time.
Finally, we remark that it may be interesting to consider harmonic welfare beyond binary valuations. In Appendix C, we prove that for agents with equal weights and additive valuations, if the value of every agent for every good is an integer (in which case the harmonic welfare is well-defined), then an allocation maximizing the harmonic welfare is always EF1.

A Round-Robin Algorithm and EF1
In the unweighted setting, it is well-known that if agents have additive valuations, then the round-robin algorithm always produces an EF1 allocation (e.g., [Caragiannis et al., 2019, p. 7]). A natural question is therefore whether the MEF1 condition in Corollary 3.2 can be strengthened to EF1. We show that the answer is negative, even for matroid-rank valuations.
One can check that v 2 is matroid-rank. 13 Assume that the round-robin algorithm lets agent 1 pick first, and that the agents break ties in the goods lexicographically. Under these assumptions, agent 1 picks g 4 , agent 2 picks g 1 , agent 1 picks g 8 , agent 2 picks g 5 , agent 1 picks g 2 , agent 2 picks g 3 , agent 1 picks g 6 , and agent 2 picks g 7 . Hence, A 1 = {g 2 , g 4 , g 6 , g 8 } and A 2 = {g 1 , g 3 , g 5 , g 7 }, and so v 2 (A 2 ) = 2 < 3 = v 2 (A 1 \ {g}) for every g ∈ A 1 . This means that agent 2 is not EF1 toward agent 1. Note also that adding the condition v i (A i ) = v i (A i ∪ A j ) as in our definition of TWEF(x, y) does not help circumvent this negative result, as we have v 2 (A 2 ) = 2 < 4 = v 2 (A 2 ∪ A 1 ).

B Computing MWHW x allocations
Recently, Viswanathan and Zick [2022a] introduced a framework for efficiently computing allocations that maximize a range of fairness objectives. Formally, a fairness objective is a function that maps each allocation A (more precisely, the utility vector (v 1 (A 1 ), . . . , v n (A n )) induced by A) to a totally ordered space. A gain function maps each clean allocation and each agent i ∈ N to a real number. 14 They showed that if a fairness objective admits a gain function satisfying certain properties, then an allocation that maximizes the objective (along with the unweighted utilitarian welfare) can be computed in polynomial time. Lemma B.1 (Viswanathan and Zick [2022a]). Suppose that the fairness objective Ψ admits a gain function φ such that the following conditions are satisfied: (i) For any two allocations A and A ′ , if A Pareto-dominates A ′ , then Ψ(A) ≥ Ψ(A ′ ).
(ii) For any clean allocation A and any agent i ∈ N , let A +i be an allocation resulting from giving a good g ∈ k∈N A k such that ∆ + i (A i , g) = 1 to i. Define A +j analogously. If φ(A, i) ≥ φ(A, j), then Ψ(A +i ) ≥ Ψ(A +j ); equality holds if and only if φ(A, i) = φ(A, j). (iv) The gain function φ can be computed in polynomial time.
Then, there exists a polynomial-time algorithm that computes an allocation that maximizes the fairness objective Ψ as well as the unweighted utilitarian welfare.
We now apply Lemma B.1 to MWHW x .
Theorem B.2. For any x ∈ [0, 1], under matroid-rank valuations, an MWHW x allocation that maximizes the unweighted utilitarian welfare can be computed in polynomial time.
Combining this with (21) yields Since v i (A j ) − v i (g) ≥ 1 and v j (A j ) − v j (g) + 1 ≥ 2 for every g ∈ B, applying Lemma C.2 to both sides, we get As a result, we have the first inequality holds because g∈A j v i (g) = g∈B v i (g) by definition of B and g∈A j v j (g) ≥ g∈B v j (g) due to the relation B ⊆ A j . This yields the desired contradiction.
In spite of Theorem C.3, a disadvantage of MHW compared to MNW is that MHW is not scaleinvariant-multiplying the value of a certain agent for every good by the same factor may change the MHW outcome. Moreover, MHW is well-defined only when all utilities are integers. Even though there is a natural extension of the harmonic numbers to the real domain given by H x = Proof. Let m = 3, and assume that the agents' valuations are given by v 1 (g 1 ) = 0, v 1 (g 2 ) = v 1 (g 3 ) = 4, v 2 (g 1 ) = 1.9, and v 2 (g 2 ) = v 2 (g 3 ) = 2. Clearly, in any MHW allocation, g 1 must be allocated to agent 2. We consider the three possibilities.
Hence, the only MHW allocation gives g 1 to agent 2 and both g 2 and g 3 to agent 1. However, agent 2 is not EF1 toward agent 1 with respect to this allocation.