Weighted Envy-Freeness in Indivisible Item Allocation

(This post is based on joint work with Mithun Chakraborty, Ayumi Igarashi, and Yair Zick)

Prologue

Suppose that Alice, Bob, and Charlie have jointly invested in a facility, with Alice contributing 3/5 of the construction expenses while Bob and Charlie contributed 1/5 each. How should they divide the usage of the facility among themselves?

At first glance, this may seem like a trivial problem: just allocate 3/5 of the time to Alice, and 1/5 to each of Bob and Charlie. Yet, there are a couple of reasons why this proposal is not necessarily ideal.

Weighted Envy-Freeness

The first reason is that agents may have preferences beyond merely the amount of time that they get. For instance, Alice may want to use the facility in the morning, while Bob and Charlie benefit more from using it in the afternoon. The literature of fair division offers fairness notions that take into account these differing preferences. The most prominent among these notions is perhaps envy-freeness: an envy-free allocation is one in which no agent envies another. In other words, every agent thinks that he or she receives the best share compared to anyone else.

While envy-freeness is a natural and intuitive property, it does not apply well to our situation. Indeed, since Alice contributed three times as much as Bob, she has reason to be unhappy if she ends up receiving a share that she values only twice as much as Bob’s (and therefore would be “envy-free” according to the above definition). Conversely, Bob should already be quite satisfied if he views his share as being worth half of Alice’s, given that his relative contribution is only one-third. This suggests that the entitlements of the agents should be taken into consideration. Fortunately, this can be done in a clean way: if agent i contributed x times as much as agent j, then we require agent i’s value for his or her own share to also be at least x times that of agent j’s share. The resulting notion is called weighted envy-freeness.

In our example, the entitlements of the agents, or weights, are governed by their investment in the facility. There are many other situations in which the agents involved have unequal claims to the resource. In inheritance division, closer relatives typically have a greater entitlement than more distant ones. Or we may be dividing resources among organizations of varying size — larger organizations naturally deserve a greater share of the resource. Weighted envy-freeness can be readily applied to all of these scenarios.

Indivisible Items

Now that we have taken care of the unequal entitlements via the introduction of weights, let us look at our second issue. So far, we have assumed that our resource can be arbitrarily and infinitely divided among the agents. Yet, in several applications, this is either inconvenient or outright impractical. Indeed, it would be strange to let Alice use the facility between 9:47am and 1:06pm — time slots are usually allocated in hours or half-hours — and cutting up a piece of jewelry into two half-pieces will not preserve half of the original value in each part!

How can we achieve envy-freeness when the resource consists of indivisible items? Even in the absence of weights (or, put differently, when all weights are equal), this is not always possible: it could be that all agents value a particular item more than the remaining items combined, so whoever receives that special item is guaranteed to be a subject of envy. We therefore need to lower our bar and declare ourselves content if agents have low but possibly nonzero envy. Specifically, we say that an allocation is envy-free up to one item (EF1) provided that the following holds: for any pair of agents i and j, if i envies j, then the envy can be eliminated when we hypothetically remove an item of our choice from j’s bundle.

Like envy-freeness, EF1 is an intuitive property. What makes it even more appealing is that it can be obtained by an incredibly simple algorithm, which many of you may have used at some point to allocate books to students or divide Christmas presents among children without even thinking of it as an “algorithm”. I’m talking about the round-robin algorithm, where agents take turns picking an item that they like most from the remaining items in cyclic order (e.g., Alice, Bob, Charlie, Alice, Bob, Charlie, …) until the items run out.

Even though the round-robin algorithm slightly favors agents who get to pick earlier, it still feels like a fair method for allocating items. We can make this statement precise — I claim that the output of the round-robin algorithm always satisfies EF1. To see why, let’s take any pair of agents i and j. There are two possibilities: either i comes before j in the ordering, or after. In the first case, i gets to pick before j in every round, so she gets an item that she likes at least as much as j’s item in each round, and therefore does not envy j at the end. In the second case, it could be that i’s first pick is extremely valuable for j. However, if we consider the first round to begin with j’s first pick, then a similar argument as in the first case shows that j has no reason to envy i from that point on. Hence, in total, j envies i by no more than i’s first pick — in other words, EF1 is satisfied. (This argument implicitly assumes that valuations are additive across items, a typical assumption which we will make throughout this post.)

So life is good when we don’t have weights. But what happens when we add weights back? What is the right definition of envy-freeness to use, and can it still be satisfied by some algorithm? To the best of our knowledge, we were the first to address this surprisingly rich problem in our recent paper. In the rest of this post, let me show you some highlights of what we found.

WEF1 and Picking Sequence

First, the definition. Just as we earlier generalized envy-freeness to weighted envy-freeness by incorporating the weights, we can do the same with EF1. In particular, if we denote the valuation function and allocated bundle of agent i by vᵢ and Aᵢ respectively, then EF1 requires that for any pair of agents i and j, if Aⱼ is not empty, then vᵢ(Aᵢ) ≥ vᵢ(Aⱼ) - vᵢ(g) for some item g in Aⱼ. We extend this definition to weighted envy-freeness up to one item (WEF1): denoting agent i’s weight by wᵢ, an allocation satisfies WEF1 if for any pair of agents i, j such that Aⱼ is not empty, it holds that vᵢ(Aᵢ)/wᵢ ≥ (vᵢ(Aⱼ) - vᵢ(g))/wⱼ for some item g in Aⱼ. In words, there exists an item in agent j’s bundle such that if we hypothetically remove it, then i no longer has weighted envy towards j.

Coming up with new definitions is usually fun, but it would not mean much if we cannot say interesting things about them. For fairness criteria, the first question that one usually asks is: can the criterion always be satisfied? This is not at all obvious for WEF1. However, given that the round-robin algorithm achieves EF1, it is tempting to try to extend the algorithm to include weights in some way. Of course, agents with higher weights should get to pick more frequently. So how about in each round, we let every agent pick a number of items proportional to his or her weight? In our example with Alice, Bob, and Charlie having weights 3, 1, 1, the picking sequence would be:

A, A, A, B, C, A, A, A, B, C, …

While this seems like a reasonable solution, it fails to guarantee WEF1. To see why, imagine that all three agents happen to value the same two items and do not care about the remaining items. With this picking sequence, Alice would get both of these items, and Bob and Charlie would consequently envy her even after removing any single item from her bundle.

For our example, we can in fact recover WEF1 by modifying the picking sequence slightly to:

B, C, A, A, A, B, C, A, A, A, …

But it is not clear how to extend this pattern to higher weights. For instance, what if the three agents have weights 3, 5, and 7? How should their picks be interleaved?

It turns out that one more idea suffices to solve the problem for arbitrary weights. The idea is to look at the round-robin algorithm in a slightly different way. Instead of viewing it as a fixed cyclic order, consider the following interpretation: at each stage, the next agent to pick is the one who has picked the least number of times so far, with ties broken according to a predetermined ordering. With this interpretation, the extension to the weighted setting almost suggests itself. Indeed, the next agent to pick should be one who has the smallest weight-adjusted picking frequency — that is, the number of times the agent has picked so far divided by the agent’s weight. So if the weights are 3, 5, and 7, the first 15 picks would be:

A, B, C, C, B, C, A, B, C, C, B, A, C, B, C

after which Alice has picked three times, Bob five times, and Charlie seven times, and the sequence repeats. For example, in the seventh turn we let Alice pick because her weighted-adjusted picking frequency is 1/3 ≈ 0.33, Bob’s is 2/5 = 0.4, and Charlie’s is 3/7 ≈ 0.42.

In fact, this scheme for constructing the picking sequence works even if the weights are irrational numbers— say, Alice has weight 𝜋 ≈ 3.14159…, Bob has weight e ≈ 2.71828…, and Charlie has weight φ ≈ 1.61803… — though this feature is unlikely to be needed in real-world applications!

Proving that our scheme actually produces a WEF1 allocation regardless of the number of items is much less straightforward than the short proof for the unweighted case above; the details can be found in our paper. In spite of that, we would like to emphasize that the algorithm itself is simple, intuitive and can be easily explained and implemented, so we are optimistic that it will be useful for practical division problems.

Maximum Weighted Nash Welfare

We now have a satisfactory answer to the first question about our new fairness notion: a WEF1 allocation exists for any problem instance, and it can be computed by a natural picking-sequence algorithm. The next question is whether we can ask for even more, that is, WEF1 in conjunction with some other desirable property. One commonly considered property is Pareto optimality (PO): an allocation is said to be Pareto optimal if there is no other allocation that makes some agent strictly better off and no other agent worse off. If PO is not satisfied, we are clearly missing out on an improvement opportunity. Yet even in the unweighted setting, it is known that an allocation produced by the round-robin algorithm may fail to be PO.

So, taking a step back, can we obtain EF1 and PO simultaneously when all weights are equal? Caragiannis and others showed that the answer is positive, and there is a particularly elegant way to achieve this combination. They proposed looking at the Nash welfare of each allocation — yes, this is named after the famous mathematician John F. Nash — and picking an allocation that maximizes the Nash welfare, which is defined as the product of the agents’ values for their own share. It is easy to see that this allocation will be PO; indeed, if some other allocation improves an agent and leaves no other agent worse off, then this new allocation will also have a higher Nash welfare. (An exception is when the maximum Nash welfare is zero— in this case, we have to be a bit more careful in choosing our allocation, but let’s not worry about this minor issue.) However, obtaining PO alone is not hard: one could maximize other functions of the agents’ values, for example the sum or the sum of squares, or even simply assign all items to the same agent. The real power of maximizing Nash welfare lies in the fact that the resulting allocation is also EF1.

With this knowledge in hand, we again attempt to extend Nash welfare to accommodate weights. The most sensible way to do this is to put the weights in the exponents — in symbols, we want to maximize the function v₁(A₁)ʷ₁ × v₂(A₂)ʷ₂ × ···, where the number of terms is equal to the number of agents. To see why this function makes sense intuitively, imagine that all agents have the same value for every item, so they only care about the number of items that they receive. Moreover, the total number of items is equal to the sum of the agents’ weights. Then it seems reasonable that each agent should receive the same number of items as his or her weight, so that the resulting distribution is proportional to the agents’ entitlements. Maximizing our function exactly fulfills this goal.

Similarly to the unweighted case, it is again clear why the allocation chosen by this method is PO. Given the consistently positive news reported so far in this post, you might wish that it also satisfies WEF1. But the world is not a wish-granting factory. If Augustus and Hazel have weights 1 and 3, and there are six items for which both of them have value 1 each, the weighted maximum Nash welfare solution will give one item to Augustus and five to Hazel. Since 1/1 < (5–1)/3, Augustus will have weighted envy towards Hazel even when any item is removed from her bundle. At this point, it seems natural to relax WEF1. An obvious candidate is to allow removing a larger number of items, say k, instead of just one. Yet no matter which value of k we choose, we run into a similar problem when Hazel’s weight and the number of items grow.

Is all lost? Does the maximum weighted Nash welfare solution fail to satisfy any fairness property? Not quite. It turns out that there is a different, less obvious way to relax WEF1. As the above example shows, the difficulty with WEF1 arises when the agents have weights that are far apart: when Augustus removes an item from Hazel’s bundle, this has very little effect on the comparison once the resulting value is divided by Hazel’s weight. To fix this issue, we will give Augustus a choice: either remove an item from Hazel’s bundle as in WEF1, or duplicate one of her items in his bundle. In our example, choosing the latter option indeed eliminates Augustus’ envy, as we have (1+1)/1 > 5/3. We call this requirement weak weighted envy-freeness up to one item (WWEF1). While the requirement is of course weaker than WEF1, it is still stronger than if we would allow Augustus to transfer one of Hazel’s items to his bundle.

When all weights are equal, both WEF1 and WWEF1 reduce to EF1. But the two properties are quite different in the presence of weights — as we show in our paper, the maximum weighted Nash welfare allocation always satisfies WWEF1, meaning that WWEF1 and PO are compatible. So, are WEF1 and PO compatible? We also demonstrate that they are, by generalizing an algorithm of Barman and others, but the algorithm is much harder to describe than anything in this post.

Epilogue

If you’ve made it this far, I hope I have convinced you that weighted allocation of indivisible items is an important domain with interesting theoretical solutions and practical algorithms. You can find much more in our paper, including implications for other weighted fairness concepts, generalizations beyond additive valuations, and simulation results. Thank you for reading!