  News

### Machine Learning, Social Welfare and Fairness

With machine learning and economics becoming increasingly related, one area of active research concerns allocation, mathematical social welfare and mathematical fairness. Machine learning and economics are becoming increasingly related. One area of active research concerns allocation, mathematical social welfare, and mathematical fairness. These ideas are best introduced using an example. Suppose three brothers, Adam, Brad, Carl, have inherited five items of jewelry (gold, jade, opal, ruby, teak) from an aunt. Each brother places a different subjective utility value, measured in utils, on each piece of jewelry according to the table in Figure 1. How should the five items be allocated to the three brothers? [Click on image for larger view.] Figure 1: Example of Nash Social Welfare

Using classical economics, a standard approach is to use Nash Social Welfare (NSW). The NSW principle says you should allocate items in a way that maximizes the geometric mean of the brothers' utility values. This solution is sometimes called maximum Nash welfare (MNW). For this problem, the NSW allocation is for Adam to get the opal (4) and teak items (5), Brad gets the gold (3) and ruby (4) items, and Carl gets the jade item (8). The utility values for each brother, assuming additive utility values, are 9, 7, 8. The geometric mean of (9, 7, 8) is the cube root of 9 * 7 * 8 = 7.96 utils.

There is no other allocation of jewelry items that would result in a larger geometric mean. Maximizing the geometric mean is equivalent to maximizing the product of each person's utility value. However, the geometric mean is used more often because it's a bit easier to interpret and compare against individual utility values.

Nash Social Welfare is named after John F. Nash, Jr. (1928-2015), an American mathematician who made fundamental contributions to several areas that are related to decision-making in complex systems. NSW is an extension of a technique published in Nash's 1950 paper "The Bargaining Problem" where just two people must allocate items.

All large companies have allocation problems, ranging from dividing a salary budget among employees, to assigning incoming network requests to servers. Some of the earliest recorded examples of allocation problems date back more than 2500 years. Allocation problems have received particular interest from companies that work at huge scale, such as Amazon, Facebook, and Google. Allocating many thousands or even millions of items is a very difficult problem.

Fairness and Envy
Allocation problems introduce the ideas of mathematical fairness and envy. There are many definitions of mathematical fairness. One definition which makes intuitive sense is that an allocation is fair if no person would prefer another person's set of items (bundle) to their own set of items. This definition of fairness is called envy-free (EF). For the jewelry example, Brad's set of items (gold 3, ruby 4) has the smallest value of 7 utils among the three brothers. Suppose Brad had Adam's items (opal, teak). Brad would value those items as opal = 2 and teak = 4 for a total of 6 utils, which is less than his current 7 utils. Or suppose Brad had Carl's item which is the jade. Brad would value the jade item as 5 utils, which is again less than his current 7 utils. In other words, one definition of allocation fairness is that no person would envy another person.

Notice that in the context of economics, the term social welfare refers to a narrowly focused idea of equity among agents rather than a more general idea related to ethics and moral values. In the same way, fairness refers to a mathematical definition of some sort rather than the more general meaning of impartiality and justice.

Envy-free allocation is a strict criterion. In research, a common idea is to find an allocation that has some upper bound of envy. For example, "envy-free except one" (EF1) means for every pair of persons A and B, there is one item in B's bundle that can be removed, and then A will not envy B. So, stated loosely, an EF1 allocation is not quite as strict as an EF allocation.

In addition to the notion of mathematical fairness, an allocation algorithm can be analyzed to see if it has various nice mathematical properties or not. Some of these properties include Pareto-optimality, symmetry, scale-invariance, irrelevant-independence, and resource-monotonicity. In spite of its simplicity, NSW satisfies all these attributes except resource-monotonicity. The 2016 paper, "The Unreasonable Fairness of Maximum Nash Welfare", by I. Caragiannis, et al. provides a rigorous math explanation.

Machine Learning and Allocation
For allocation problems and fairness, machine learning enters the picture in two ways. First, computing an exact NSW or similar allocation is very difficult and so machine learning techniques have been used to find approximate solutions. Second, for machine learning algorithms that explicitly or implicitly generate an allocation, you can analyze allocation results for mathematical fairness.

The jewelry allocation problem is an example where the items are not divisible. Each brother must get an item or not. It's not possible to take the jade item and give 0.60 of it to Adam, 0.10 of it to Brad, and 0.30 of it to Carl. This makes allocation with non-divisible items a combinatorial optimization problem where the challenge is to partition n items among k people. Combinatorial optimization problems are among the most difficult in machine learning, in part because of the combinatorial explosion issue.

The number of ways to partition n items into k subsets is called a Stirling number of the second kind, often written as S(n, k). For example, S(4, 2) is the number of ways to group 4 items into 2 subsets and is 7. Suppose the four items are a, b, c, d. The seven partitions are: (a | bcd), (b | acd), (c | abd), (d | abc), (ab |cd), (ac | bd), and (ad | bc).

For the jewelry example, S(5, 3) = 25 and so to compute the NSW allocation you could use brute force to examine each possible allocation and select the one that has the largest geometric mean of utility values. However, the value of S(n, k) gets astronomically large, very quickly. For example, S(100, 3) = 85,896,253,455,335,221,205,584,888,180,155,511,368,666,317,646. [Click on image for larger view.] Figure 2: Computing the Number of Ways to Allocate n=100 Items to k=3 Groups

In general, it's not possible to examine every possible allocation of non-divisible items. Because of this characteristic, there are several ways to find an approximate NSW solution. These include techniques used in machine learning such as epsilon-greedy agglomeration, and evolutionary combinatorial optimization.

In epsilon-greedy agglomeration, you start with each person/agent having one randomly selected item. Then you iterate through each person, adding the item that most increases the geometric mean of the utility values, or with small probability epsilon you add a randomly selected item. For example, see the 2018 paper "Greedy Algorithms for Maximizing Nash Social Welfare" by S. Barman, et al.

In evolutionary combinatorial optimization, you create a population of many allocations. From these, you select a few of the good allocations and then mutate each good allocation by switching the assignments of two items and other rearrangements. You repeat this process until you are satisfied.

In many practical allocation problems, items are not divisible. But if items are divisible, then classical numerical convex optimization techniques can be used to find a Nash Social Welfare solution. For problems with non-divisible items, in addition to the epsilon-greedy and evolutionary approaches, another way to approximate a solution is to assume items are divisible, get that exact solution, and then convert partial items (such as 0.40 of the gold item) to whole items. See the 2015 paper "Approximating the Nash Social Welfare with Indivisible Items" by R. Cole and V. Gkatzels.

There are many areas of research that are related to pure allocation. One example is bidding for online advertising resources. The 2020 paper "Robust Market Equilibria with Uncertain Preferences" by Riley Murray et al. explored online advertising where items are scare and divisible, and buyers compete for items. The fundamental model in such scenarios is called a linear Fisher market. The model is named after Irving Fisher (1867-1947), an American economist. The paper looked at scenarios where there is uncertainty in valuations which makes the problem scenario very difficult.