Picking Sequences and Monotonicity in Weighted Fair Division

1 Introduction

After a national election, the parties forming a coalition government are faced with the task of dividing the ministries among themselves. How can they perform this task in a fair manner, taking into account both their preferences on ministries and the votes that they received in the election?

The study of fairly allocating resources to interested agents (in this case, parties), commonly known as fair division, has a long history dating back several decades [Brams and Taylor, 1996; Moulin, 2003]. Among the most prominent fairness criteria are envy-freeness-no agent prefers another agent's allocated bundle over her own-and proportionality-if there are n agents, then every agent receives at least 1/n

value for the entire resource. These criteria implicitly assume that all agents have the same entitlement to the resource, an assumption that is made in the vast majority of the fair division literature, yet utterly fails in our ministry example as well as when allotting supplies to districts, organizations, or university departments, which typically have different sizes. Fortunately, both envy-freeness and proportionality allow for taking the entitlements, or weights, into account in a natu-

ral way. For instance, if agent A's weight is twice that of agent B, then A will be satisfied with respect to weighted envy-freeness as long as she derives at least twice as much value for her own bundle as for B's bundle. While such weight-based extensions of classical fairness concepts are appropriate for scenarios with different entitlements, they sometimes cannot be satisfied when allocating indivisible items like ministries (e.g., when every party places all of its value on the same important ministry). Consequently, recent work has proposed relaxations including weighted envy-freeness up to one item (WEF1) [Chakraborty et al., 2020] and weighted proportionality up to one item (WPROP1) [Aziz et al., 2020], each of which can always be fulfilled.

An attractive class of procedures for allocating items is the class of picking sequences: these procedures let agents take turns picking their favorite items according to a prespecified order. Picking sequences are intuitive, can be implemented efficiently, and help preserve privacy since each agent only has to reveal the picks in her turns as opposed to her full preferences. In fact, several methods for apportioning seats in a parliament-a setting commonly known as apportionment-can be formulated as picking sequences. 1 For example, Adams' method assigns each pick to an agent i who minimizes ti/wi, where ti and wi denote the number of times that agent i has picked so far and her weight, respectively. Brams and Kaplan [2004] proposed using picking sequences to allocate ministries, noting that such sequences have been used in Northern Ireland and Denmark, and Chakraborty et al. [2020] showed that the allocation produced by Adams' method always fulfills WEF1 but not necessarily WPROP1. It is therefore an important question which fairness criteria, if any, are satisfied by picking sequences based on other prevalent apportionment methods.

In addition to fairness, another desirable set of properties for allocation procedures is monotonicity in terms of the parameters of the setting. In particular, resource-monotonicity means that whenever an extra item is added, no agent receives a lower utility as a result. Similarly, populationmonotonicity stipulates that introducing an additional agent should not increase the utility of any existing agent, and weight-monotonicity implies that when the weight of an agent increases, her utility does not go down. 2 Segal-Halevi and Sziklai [2019] showed that for divisible items in the unweighted setting, the maximum Nash welfare (MNW) solution, which chooses an allocation maximizing the product of the agents' utilities, is resource- and population-monotone. How do picking sequences and (a weighted generalization of) MNW perform with respect to monotonicity properties in the weighted allocation of indivisible items?

1 Note that apportionment is a special case of our setting where all items are identical [Balinski and Young, 2001].

2 Resource-monotonicity is known as house-monotonicity in the

1.1 Our Results

In this paper, we conduct a thorough investigation of picking sequences based on common apportionment methods, as well as the maximum (weighted) Nash welfare solution, in relation to fairness and monotonicity properties. In addition to WEF1 and WPROP1, we consider weak weighted envy-freeness up to one item (WWEF1), a weakening of WEF1 proposed by Chakraborty et al. [2020]. For brevity, we say that an allocation rule satisfies a fairness notion if the allocation that it produces for an arbitrary input instance satisfies that notion.

We begin in Section 3 by establishing fundamental results on our properties in the context of picking sequences. In particular, we define three consistency properties with respect to the resource, population, and weights-for example, resource-consistency means that whenever an item is added, the new picking sequence should simply be the old one with an additional pick appended at the end. We show that resource- and population-consistency imply the respective monotonicity properties for any number of agents, while weight-consistency implies weight-monotonicity only for two agents. In addition, for each fairness notion, we characterize the picking sequences whose output always satisfies that notion.

With this groundwork laid, we proceed to determine the properties satisfied by each allocation rule in Section 4. First, we consider the picking sequences derived from five traditional divisor methods due to Adams, Jefferson, Webster, Hill, and Dean. These methods assign each pick to an agent i who minimizes the ratio f(ti)/wi capturing the proportion between the number of times the agent has picked so far and the agent's weight, where the function f varies from method to method. We establish that all five methods satisfy resourceand population-monotonicity for any number of agents as well as weight-monotonicity for two agents; however, they all fail weight-monotonicity when there are three agents. On the fairness front, all of the methods satisfy WWEF1, but Adams' is the only one satisfying the stronger notion of WEF1 while Jefferson's is the only one fulfilling WPROP1.

Next, in Section 5, we address the picking sequence derived from another important apportionment method: the quota method. While not itself a divisor method, the quota method has a definition similar to that of Jefferson's method, which uses the function f(t) = t + 1, but also imposes a "quota" to determine each agent's eligibility. We show that the quota method exhibits similar monotonicity behavior as the divisor methods, with the notable exception that it fails population-monotonicity. As for fairness, like Jefferson's method, the quota method satisfies WWEF1 and WPROP1. In fact, these two rules are the first to have been shown to satisfy both WWEF1 and WPROP1, to the best of our knowledge.

context of apportionment; a violation of it is referred to as the Alabama paradox [Balinski and Young, 2001]. Likewise, violations of (variants of) population- and weight-monotonicity are called the new states paradox and the population paradox, respectively.

Finally, in Section 6, we examine the maximum weighted Nash welfare (MWNW) solution, which is a natural generalization of the well-studied MNW solution to the weighted setting. Chakraborty et al. [2020] already proved that MWNW satisfies WWEF1 but not WEF1; we show that it fails WPROP1. We then present examples demonstrating that even in the unweighted setting (where MWNW reduces to MNW), the rule fails both resource- and populationmonotonicity. This result stands in stark contrast to the aforementioned result of Segal-Halevi and Sziklai [2019] that MNW is resource- and population-monotone in the context of divisible items, and is perhaps even more striking given that MNW is known to fulfill several desirable properties [Caragiannis et al., 2019; Halpern et al., 2020]. On the positive side, MWNW satisfies weight-monotonicity for any number of agents, and is the only rule to do so among the ones we consider in this paper.

Our results are summarized in Table 1. Overall, we believe that they serve as an argument in favor of using picking sequences in division problems with unequal entitlements in view of both fairness and monotonicity considerations.

1.2 RelatedWork

The fair allocation of indivisible items has received substantial recent attention, notably among computer scientists-see the surveys of Bouveret et al. [2016] and Markakis [2017]. A large majority of work assumes that all agents have equal entitlements, in which case the notions envy-freeness up to one item (EF1) [Lipton et al., 2004; Budish, 2011] and proportionality up to one item (PROP1) [Conitzer et al., 2017; Aziz et al., 2019a] are often considered. Both WEF1 and WWEF1 reduce to EF1 in the unweighted setting, while WPROP1 reduces to PROP1. Even though EF1 implies PROP1, Chakraborty et al. [2020] showed that no rule can simultaneously satisfy WEF1 and WPROP1. Aziz et al. [2020] gave a protocol satisfying WPROP1 along with the economic efficiency notion of Pareto optimality, while Babaioff et al. [2019] considered competitive equilibrium for agents with different budgets representing their weights. Farhadi et al. [2019] proposed a weighted version of maximin share fairness [Budish, 2011; Kurokawa et al., 2018], and Aziz et al. [2019b] studied the analogous notion for chores (i.e., items that yield negative utilities).

Like fair division, apportionment methods have given rise to a long line of work that analyzes their advantages and disadvantages according to various desiderata [Balinski and Young, 2001; Pukelsheim, 2014]. As Balinski and Young [2001] noted, Adams' method tends to favor agents with smaller weights and Jefferson's typically benefits those with larger weights, whereas the other three divisor methods lie in between. Apportionment has also attracted interest in artificial intelligence [Brill et al., 2017; Brill et al., 2020; Bredereck et al., 2020] as well as in philosophy [Wintein and Heilmann, 2018].

Finally, picking sequences have been studied by several authors due to their simplicity and practicality [Bouveret and Lang, 2011; Bouveret and Lang, 2014; Aziz et al., 2015; Tominaga et al., 2016; Beynier et al., 2019], with a number of authors investigating manipulation issues. We assume in this paper that agents are not strategic and always pick their most preferred item available. In the unweighted setting, a popular picking sequence is the round-robin algorithm, which lets agents pick items in cyclic order until the items run out.

2 Preliminaries

We consider a discrete resource allocation setting with a set of agents N = [n] and a set of indivisible items M = [m], where [k] := {1, 2, . . . , k} for any k ∈ N. Each agent i ∈ N is endowed with a weight wi > 0 and a utility function ui : 2M →R≥0; for convenience, we sometimes write ui(j) instead of ui({j}) for an item j ∈ M. As is very common in the fair division literature, we assume that the utility functions are additive, i.e., ui(M ′ ) = ∑j∈M′ ui(j) for all i ∈ N and M ′ ⊆ M. An allocationM = (M1, . . . ,Mn) is a partition of the items into n bundles so that agent i receives bundle Mi. An instance consists of the agents, items, weights, and utility functions. When all weights are equal (in which case we can take them to be 1 without loss of generality), we refer to the resulting setting as the unweighted setting.

We consider the following three fairness notions. The first two notions were proposed by Chakraborty et al. [2020] and the third by Aziz et al. [2020].

Definition 2.1. An allocation (M1, . . . ,Mn) is said to satisfy

• weighted envy-freeness up to one item (WEF1) if for any i, j ∈ N, there exists B ⊆ Mj with |B| ≤ 1 such that ui(Mi) wi ≥ ui(Mj\B) wj ;
• weak weighted envy-freeness up to one item (WWEF1) if for any i, j ∈ N, there exists B ⊆ Mj with |B| ≤ 1 such that ui(Mi) wi ≥ ui(Mj\B) wj or ui(Mi∪B) wi ≥ ui(Mj) wj ;
• weighted proportionality up to one item (WPROP1) if for any i ∈ N, there exists B ⊆ M \ Mi with |B| ≤ 1 such that ui(Mi) ≥ ( wi ∑i′∈N wi′ · ui(M)) -ui(B).

Chakraborty et al. [2020] showed that no rule can simultaneously satisfy WEF1 and WPROP1. In particular, consider an instance where m = n and every agent has a nonzero utility for every item. Any WEF1 allocation has to assign exactly one item to each agent. 3 On the other hand, if a certain agent has the same utility for all items and a sufficiently larger weight than every other agent, WPROP1 will require this agent to receive at least m- 1 items.

A domain refers to a set of instances. A domain may include all instances with any number of agents and items, weights, and utility functions, or it may only include-for example-all instances with two agents, or all instances with equal weights (this corresponds to the unweighted setting). An allocation rule is a function that maps each instance in a given domain to an allocation; it is said to satisfy a fairness notion if the allocation that it produces always fulfills that notion. We now define the three monotonicity properties that we consider-the first two have been studied by Segal-Halevi and Sziklai [2018; 2019], while the third has not been studied in fair division to the best of our knowledge.

Definition 2.2. An allocation rule R with domain I satisfies

• resource-monotonicity if the following holds: for any instance with m items, when an extra item is added as item m+1, if both the original and the modified instance belong to I, then each agent receives no higher utility from the allocation produced by R in the original instance than in the modified instance;
• population-monotonicity if the following holds: for any instance with n agents, when an extra agent is added as agent n+1, if both the original and the modified instance belong to I, then each of the first n agents receives at least as much utility from the allocation produced by R in the original instance as in the modified instance;
• weight-monotonicity if the following holds: for any instance, when the weight of an agent increases, if both the original and the modified instance belong to I, the utility that the agent receives from the allocation produced by R does not decrease.

While these monotonicity properties are intuitive and it may seem that any reasonable allocation rule should satisfy them, this is in fact not the case: In the full version of our paper [Chakraborty et al., 2021], we show that two popular fair division algorithms-the envy cycle elimination algorithm and the adjusted winner procedure-fail resourcemonotonicity even in the unweighted setting.

3 Otherwise an agent with no item will (weighted-)envy an agent with at least two items by more than one item.

Next, we provide definitions related to picking sequences.

Definition 2.3. A picking sequence on n agents and m items is a sequence πn,m,w = (a1, a2, . . . , am), where ai ∈ N for each i ∈ M. A family of picking sequences is a collection Π = {πn,m,w}, with at most one picking sequence for each pair of positive integers n,m and weight vector w = (w1, . . . , wn). A family of picking sequences Π is called

• resource-consistent if for every n,m, w such that both πn,m,w and πn,m+1,w belong to Π, the sequence πn,m,w forms a prefix of πn,m+1,w;
• population-consistent if for every n,m, w, w′ such that w′ = (w1, . . . ,wn,w′n+1 ) where w′n+1 is the weight of agent n+1 and both πn,m,w and πn+1,m,w′ belong to Π, the sequence πn+1,m,w′ can be obtained from πn,m,w by inserting agent n + 1 in some positions (possibly none) and trimming the suffix of the resulting sequence so that the sequence has length m.
• weight-consistent if the following holds: for every n, m, w and w′i > wi such that both πn,m,w and πn,m,w′ belong to Π, where w′ = (w1, . . . ,w′i , . . . ,wn), the sequence πn,m,w′ can be obtained from πn,m,w by moving some of agent i's picks earlier (possibly none), inserting agent i in some positions (possibly none), and trimming the suffix of the resulting sequence so that the sequence has length m.

Given a picking sequence (a1, . . . , am) and the agents' utility functions, we assume that in the ith turn, agent ai picks her highest-valued item from among the remaining items, breaking ties in a consistent manner (say, in favor of lowernumbered items). We sometimes drop the subscript from πn,m,w when n,m,w are clear from the context. A family of picking sequences generates an allocation rule, which we will refer to interchangeably with the family itself. We also refer to a picking sequence π interchangeably with the family of picking sequences that consists only of π.

All omitted proofs can be found in the full version of this paper [Chakraborty et al., 2021].

3 General Picking Sequences

We begin by proving results for general picking sequences. In addition to being interesting in their own right, these results will later help us determine the properties that each apportionment method satisfies. First, we present characterizations of picking sequences whose output is guaranteed to satisfy each of the fairness notions WEF1, WWEF1, and WPROP1. In particular, we show that a picking sequence guarantees a fairness notion for agents with arbitrary utility functions if and only if it does so for agents with identical utility functions that put utility 1 on some items and 0 on the remaining items. This means that the fairness guarantees for general utilities can be expressed as relatively simple conditions on the number of picks in each prefix of the picking sequence.

Theorem 3.1. A picking sequence π satisfies WEF1 if and only if for every prefix of π and every pair of agents i, j with tj ≥ 2, we have ti tj-1 ≥ wi wj , where ti and tj denote the number of agent i's and agent j's picks in the prefix, respectively.

Theorem 3.2. A picking sequence π satisfies WWEF1 if and only if for every prefix of π and every pair of agents i, j with tj ≥ 2, both of the following hold:

• ti tj-1 ≥ wi wj if wi ≥ wj;
• ti+1 tj ≥ wi wj if wi ≤ wj,

where ti and tj denote the number of agent i's and agent j's picks in the prefix, respectively.

As an example of a picking sequence that satisfies WWEF1 but not WEF1, suppose that n = 2, w1 = 1, w2 = 2, and consider the sequence (1, 2, 2, 2, 2). For this sequence, we have t1 = 1 and t2 = 4, and therefore t1+1 t2 = w1 w2 > t1 t2-1 .

Theorem 3.3. A picking sequence π satisfies WPROP1 if and only if for every prefix of π and every agent i, we have ti ≥ ( wi ∑i′∈N wi′ · k) - 1, where ti and k denote the number of agent i's picks in the prefix and the length of the prefix, respectively.

Next, we establish a strong relationship between resourceand population-consistency and the corresponding monotonicity notions.

Theorem 3.4. Any resource-consistent family of picking sequences satisfies resource-monotonicity.

Theorem 3.5. Any population-consistent family of picking sequences satisfies population-monotonicity.

The relationship between weight-consistency and weightmonotonicity is less straightforward: we show that the former implies the latter in the case of two agents. As we will see later (Proposition 4.2), this relationship breaks down when there are three agents.

Theorem 3.6. For two agents, any weight-consistent family of picking sequences satisfies weight-monotonicity.

4 Divisor Methods

As we explained in the introduction, a divisor apportionment method gives rise to a picking sequence that, in each turn, lets an agent i with the smallest f(ti)/wi pick the next item (breaking ties in a consistent manner, say, in favor of lowernumbered agents), where ti denotes the number of times that agent i has picked so far and f : Z≥0 → R≥0 is a strictly increasing function specific to the method such that t ≤ f(t) ≤ t + 1. 4 We will refer to the divisor methods and their associated families of picking sequences interchangeably. By definition, it is clear that every divisor method yields a family of picking sequences (for all n, m, w) that are resource-, population-, and weight-consistent. Theorems 3.4, 3.5, and 3.6 therefore imply the following:

Corollary 4.1. Every divisor method satisfies resourcemonotonicity and population-monotonicity; it also satisfies weight-monotonicity when there are two agents.

4 Some non-divisor apportionment methods such as Hamilton's method do not give rise to a picking sequence and are therefore not useful in our context [Brams and Kaplan, 2004, p. 149].

The five traditional divisor methods of Adams, Jefferson, Webster, Hill, and Dean have the function f(t) equal to t, t + 1, t + 12 , √t(t +1), and t(t+1) t+ 12 , respectively [Balinski and Young, 2001, p. 99]. We prove that, perhaps surprisingly, all five methods fail weight-monotonicity in the case of three agents. 5 This also means that weight-consistency does not imply weight-monotonicity beyond two agents.

Proposition 4.2. Each of the five traditional divisor methods does not satisfy weight-monotonicity even when there are three agents.

We now explore how the five divisor methods fare with respect to the three fairness notions, starting with WEF1.

Theorem 4.3. Of the five traditional divisor methods, Adams' method is the only one satisfying WEF1.

Next, we show that interestingly, all five methods satisfy WWEF1, meaning that each of them can guarantee fairness beyond the setting with identical items (i.e., apportionment).

Theorem 4.4. All five traditional divisor methods satisfy WWEF1.

Proof. We claim that any divisor method whose function f fulfills the following two conditions satisfies WWEF1:

• f(a) f(b) ≤ ab for any integers 1 ≤ b ≤ a;
• f(a) f(b) ≤ a+1 b+1 for any integers 0 ≤ a ≤ b with b ̸= 0.

To prove the claim, consider such a divisor method, and fix a pair of agents i, j. It suffices to show that every time agent j picks an item starting from her second pick, the conditions in Theorem 3.2 are satisfied. By definition of the divisor method, after agent j's pick it holds that f(tj-1) wj ≤ f(ti) wi ; otherwise agent i should have picked instead of agent j. Consider two cases as in the conditions of Theorem 3.2 with tj ≥ 2.

Case 1: wi ≥ wj. Since f is strictly increasing, we have f(tj - 1) > f(0) ≥ 0, and so 1 ≤ wi wj ≤ f(ti) f(tj-1) . This means that ti ≥ tj - 1, and our assumption on f implies that wi wj ≤ f(ti) f(tj-1) ≤ ti tj-1 , as desired.

Case 2: wi ≤ wj. We have f(tj - 1) > 0 and wi wj ≤ f (ti) f(tj-1) . If ti ≥ tj - 1, then wi wj ≤ 1 ≤ ti+1 tj . Otherwise, ti < tj - 1, and our assumption on f implies that wi wj ≤ f (ti) f(tj-1) ≤ ti+1 (tj-1)+1 = ti+1 tj , as desired.

Next, we show that the functions f of all five divisor methods satisfy the two conditions above. First, consider f(t) = t + c for any constant c ∈ [0, 1]. If 1 ≤ b ≤ a, the function a+x b+x is non-increasing for x ≥ 0, so a+c b+c ≤ ab . On the other hand, if 0 ≤ a ≤ b with b ̸= 0, the function a+x b+x is non-decreasing for x ≥ 0, so a+c b+c ≤ a+1 b+1 . This shows that Adams', Jefferson's, and Webster's methods fulfill WWEF1. For Hill's method, when 1 ≤ b ≤ a, the desired condition √a(a+1) √b(b+1) ≤ ab is equivalent to a+1 b+1 ≤ ab , which holds by our previous observation; an analogous statement can be made for the case 0 ≤ a ≤ b with b ̸= 0. Finally, for Dean's method, when 1 ≤ b ≤ a, the desired condition a(a+1)/(a+ 12 )

5 Brams and Kaplan [2004, p. 157] showed that for n = 3, an agent can do worse when her picks move earlier in the picking sequence. However, their example does not correspond to a weight increase with respect to a divisor method and moreover assumes that agents are strategic rather than truthful.

b(b+1)/(b+ 12 ) ≤ ab is equivalent to a+1 b+1 ≤ a+ 1 2 b+ 12 , which holds by our previous observation; a similar statement can again be made for the case

0 ≤ a ≤ b with b ̸= 0.

We now turn to WPROP1, where we illustrate a strong relationship with a notion from the apportionment setting. A picking sequence πn,m,w is said to satisfy lower quota if for any i ∈ N, it holds that ti ≥ ⌊ wi·m ∑i′∈N wi′ ⌋, where ti denotes the number of picks in πn,m,w assigned to agent i.

Proposition 4.5. Let π be a picking sequence such that every prefix of π satisfies lower quota. Then π satisfies WPROP1.

Since Jefferson's method satisfies lower quota [Balinski and Young, 2001, p. 130] and is resource-consistent, any prefix of its associated picking sequence also satisfies lower quota. By Proposition 4.5, the method satisfies WPROP1. We prove that it is the only traditional divisor method to do so.

Theorem 4.6. Of the five traditional divisor methods, Jefferson's method is the only one satisfying WPROP1.

5 QuotaMethod

Although divisor methods are widely used in practice, they do come with an axiomatic downside: no divisor method satisfies an arguably natural axiom known as quota [Balinski and Young, 2001, p. 130]. A picking sequence satisfies the quota axiom if for every i ∈ N, it holds that ⌊ wi·m ∑i′∈N wi′ ⌋ ≤ ti ≤ ⌈ wi·m ∑i′∈N wi′ ⌉ , where ti is the number of picks assigned to agent i by the picking sequence-note that the lower bound simply corresponds to the lower quota notion introduced before Proposition 4.5. Motivated by this observation, [Balinski and Young, 1975] proposed the quota method which satisfies the quota axiom as well as resourceconsistency. Intuitively, this method can be seen as a constrained version of Jefferson's method where we choose an agent i minimizing (ti +1)/wi over a restricted subset of "eligible" agents. The picking sequence for the quota method is determined iteratively. For each round k ∈ [m], let ti be the number of times agent i has picked in rounds 1, . . . , k - 1. An agent is eligible if she would not exceed her upper bound in the quota axiom upon getting an additional pick in round k. Equivalently, the set of eligible agents is U(w, t, k) = {i ∈ N ∣∣∣ ti < wi·k ∑i′∈N wi′ }, where t = (t1, . . . , tn). Among all eligible agents, the next pick is assigned to an agent minimizing (ti + 1)/wi, breaking ties in a consistent manner. The method trivially satisfies resource-consistency, which by Theorem 3.4 implies the following:

Corollary 5.1. The quota method satisfies resourcemonotonicity.

However, satisfying the quota axiom comes at a price: in contrast to all divisor methods (Corollary 4.1), the quota method fails population-monotonicity. Moreover, like the five traditional divisor methods (Proposition 4.2), the quota method fails weight-monotonicity for n = 3.

Proposition 5.2. The quota method does not satisfy population-monotonicity. In addition, it does not satisfy weight-monotonicity even when there are three agents.

As we observed in Section 4, all divisor methods are weight-consistent for any number of agents by definition, and therefore weight-monotone for two agents by Theorem 3.6. In contrast, we show in the full version of our paper that the quota method is not weight-consistent [Chakraborty et al., 2021]. However, for two agents, we prove that the method is weight-consistent and hence weight-monotone.

Theorem5.3. The quota method satisfies weight-consistency and weight-monotonicity when there are two agents.

Next, we address fairness criteria for the quota method.

Theorem 5.4. The quota method fails WEF1 but satisfies WWEF1 and WPROP1.

6 Maximum (Weighted) NashWelfare

Given any instance in the unweighted setting, the maximum Nash welfare (MNW) solution chooses an allocation that maximizes the Nash welfare, i.e., the product of the agents' utilities. MNW is known to satisfy strong fairness guarantees including EF1 [Caragiannis et al., 2019; Halpern et al., 2020]. When weights are present, a natural generalization called maximum weighted Nash welfare (MWNW), which maximizes 6 the weighted product ∏ni=1 ui(Mi)wi , satisfies WWEF1 but not WEF1 [Chakraborty et al., 2020].

Segal-Halevi and Sziklai [2019] showed that for divisible items in the unweighted setting, MNW satisfies both resource- and population-monotonicity. It is therefore rather surprising that the same is not true for indivisible items.

Proposition 6.1. In the unweighted setting, MNW satisfies neither resource-monotonicity nor population-monotonicity.

With only the first three items available, the unique MNW allocation gives items 1 and 3 to agent 1 and item 2 to agent 2, resulting in a utility of 5 for agent 1. However, when we add item 4, MNW uniquely allocates items 3 and 4 to agent 1 and items 1 and 2 to agent 2. So agent 1's utility drops to 4, violating resource-monotonicity.

6 Ties can be broken arbitrarily unless the maximum weighted Nash welfare is 0 (which occurs, for example, when m < n). In this exceptional case, we choose a maximum subset of agents who can be given positive utilities simultaneously, breaking ties in a consistent manner among all such subsets independently of the weights (e.g., lexicographically with respect to the agent indices). We then pick an allocation maximizing the weighted Nash welfare of the agents in this subset.

The example for population-monotonicity uses three agents and four items and can be found in the full version of our paper [Chakraborty et al., 2021].

On the other hand, we prove that MWNW fulfills weightmonotonicity, making it the only rule among the ones we consider in this paper to do so.

Theorem 6.2. MWNW satisfies weight-monotonicity.

As mentioned, MWNW is known to satisfy WWEF1 but not WEF1. To complete the picture, we show that it does not satisfy WPROP1. This contrasts with the unweighted setting, where MNW satisfies PROP1 (since EF1 implies PROP1).

Proposition 6.3. MWNW does not satisfy WPROP1.

7 Conclusion and FutureWork

In this paper, we have thoroughly investigated picking sequences derived from common apportionment methods, including the five traditional divisor methods and the quota method, in relation to fairness and monotonicity properties. Our results indicate that picking sequences based on divisor methods provide strong guarantees in weighted fair division scenarios such as allocating ministries to political parties, with Adams' and Jefferson's methods standing out for fulfilling WEF1 and WPROP1, respectively. Since Jefferson's method tends to favor large parties while Adams' often benefits smaller ones (see Section 1.2), an interesting question is whether there are compelling fairness notions in addition to WWEF1 that the other three traditional divisor methods, which intuitively lie somewhere in the middle, satisfy.

A natural direction for future work is to construct rules that exhibit a stronger axiomatic behavior than the ones considered in this paper, or to prove that such rules do not exist. Satisfying the three monotonicity properties simultaneously is trivial: one can always allocate all items to a fixed agent, or ignore the weights and use the round-robin algorithm with a fixed ordering. However, this will not result in a fair allocation with respect to the weights. Does there exist a rule fulfilling the three monotonicity properties along with, say, WWEF1? Other notions that one could consider include strategyproofness and Pareto optimality-even in the unweighted setting, we are not aware of any rule that simultaneously fulfills EF1, Pareto optimality, and resource- or population-monotonicity. Our work leaves many intriguing combinations of properties to investigate, which we hope will lead to more interesting rules for fair resource allocation.

Acknowledgments

This work was partially supported by the Deutsche Forschungsgemeinschaft under grant BR 4744/2-1 and by an NUS Start-up Grant. We would like to thank Dominik Peters for helpful discussion and the anonymous reviewers for valuable feedback.