Three weary wanderers reach a pub in the middle of nowhere. Bad news for them: no customers were expected, and only one liter of beer remains. The wanderers sit at the counter. Alan is not so thirsty, and picks a small glass. Bill and Carl take a big one each.

Empty glasses

The available beer’s not enough to fill all the glasses. The bartender – not the sharpest knife in the drawer – scratches his head for a few moments. Then, he begins distributing beer from the largest glass:

Greedy allocation

The three customers look at their glasses. The allocation surely looks efficient, in the sense that no beer is wasted. If the happiness (let’s call it utility) of each customer is equivalent to the amount of beer they got, this is also a social optimum, in the sense that the sum of the utilities (or, equivalently, their average) is maximized.

But, well, it really doesn’t look like a fair allocation to Alan. Bill and Carl got so much more beer than him! The bartender shrugs, and pours some beer from Bill into Alan’s glass.

Maximin allocation

This looks much better for Alan, who’s perfectly happy. This is the type of solution obtained when the focus is on maximizing the minimum (worst-case) allocation, which is one of the simplest ways to model equity or balancing criteria in a resource allocation problem. However, the solution is still unfair for someone: Bill. Carl now has more than he got. That is definitely not fair!

Suddenly, the bartender has an idea. There you go:

Max-min fair allocation

This does look fair: no-one can really ask for more. Indeed, this is an allocation that satisfies the so-called max-min fairness criterion, where the minimum resource allocation is maximized, then the second-worst, the third-worst, and so on. This is closely related to the concept of equality of Rawls [1], whose difference principle posits:

[I]n a basic structure with n relevant representatives, first maximize the welfare of the worst off representative man; second, for equal welfare of the worst-off representative, maximize the welfare of the second worst-off representative man, and so on until the last case which is, for equal welfare of all the preceding n–1 representatives, maximize the welfare of the best-off representative man. We may think of this as the lexical difference principle.

Another equivalent1 definition states that an allocation is max-min fair if there is no way to increase the utility of any user without decreasing the utility of a user with a smaller or equal utility. To put it as Robin Hood certainly would, an allocation is not fair if you can increase the utility of a peasant by stealing from a rich man.

Getting back to our friends. With the current, max-min fair allocation, Alan’s happy, and, in a perfect Robin Hood world, Bill and Carl certainly can’t claim any more beer.

Or can they? A grin appears on Carl’s face: a-ha! We shouldn’t reason in terms of absolute values. In a really fair solution, each customer should get exactly the same fraction of their maximal capacity! Carl redistributes the beer:

Concurrently fair allocation

Now both Bill and Carl get a slightly larger piece of the cake. The implicit assumption here is that the utility is proportional to the fraction of the the satisfied demand of each customer, and not to the sheer allocated quantity. Alan has something to say about this…

But the bartender’s had enough of all this petty talking. Do they want a fair allocation? Let them have the most egalitarian of them all. He fills Alan’s glass to the top, takes Bill and Carl’s glasses in his hands, and spills their content on the floor, until they have the same quantity that Alan has. ¯\_(ツ)_/¯

Egalitarian allocation

Oh well. This is definitely an inefficient solution, but effective in killing the discussion. Observe that all previous allocations were efficient in the sense that 100% of the resource was used. However, in less trivial situations, fair solutions (such as the max-min fair allocation) can be significantly less efficient than solutions where the total efficiency is maximized. This trade-off is sometimes called “price of fairness” [7].

Fairness is a concept that comes up very often when limited resources have to be shared among a set of users, each with its own utility function. In many settings, a central decision maker (we could think of a government, a network provider allocating bandwith, or even Santa Claus) has to allocate the resources to the users. Since optimizing for the average case can bring about large inequalities in the allocations, it often makes sense to consider different fairness criteria in different contexts – e.g., proportional fairness [5] is another widely studied criterion that I haven’t mentioned. In practice, compared to this simple example, things can get much more complicated: for example, the utility functions can be nonlinear, the resources can be non-divisible, and the feasible set (the set of “valid” allocations) can be non-convex, so that determining a fair allocation requires solving hard optimization problems.

The few lines of code used to formulate and solve the allocation problems with the different criteria can be found here. The code also includes mathematical formulations for other fairness criteria. It’s quite easy to verify that, in this example, the max-min fair solution is as fair as possible also according to proportional fairness, Gini coefficient and Jain’s index (provided we want to use all the beer; otherwise, the “egalitarian” allocation would be preferred by the latter two indices).

There’s a ton of interesting stuff that can be read on the subject: equity and fairness have been studied from different point of views in philosophy, political science and economics (especially in social choice theory), game theory (where the interaction between players is taken into account), optimization, telecommunications, so pretty much everyone can find something to chew on. I’d like to conclude with a few interesting references to read while you sip your favorite trappist beer:

  1. Rawls J. A Theory of Justice, 1971
  2. Varian, H. R. Equity, envy, and efficiency. Journal of economic theory, 9(1), 63-91, 1974.
  3. Rabin, M. Incorporating fairness into game theory and economics. The American economic review, 1281-1302, 1993.
  4. Brams, S. J., & Taylor, A. D. Fair Division: From cake-cutting to dispute resolution. Cambridge University Press, 1996.
  5. Kelly, F. P., Maulloo, A. K., & Tan, D. K. Rate control for communication networks: shadow prices, proportional fairness and stability. Journal of the Operational Research society, 237-252, 1998.
  6. Radunović, B., & Boudec, J. Y. L. A unified framework for max-min and min-max fairness with applications. IEEE/ACM Transactions on Networking (TON), 15(5), 1073-1083, 2007.
  7. Bertsimas, D., Farias, V. F., & Trichakis, N. The price of fairness. Operations research, 59(1), 17-31, 2011

  1. Almost. ↩