How to make recommendation systems fair: an adequate utility-based approach Open Access

A usual user-oriented website – whether it is a news website or a website of a seller – contains a large amount of information. It is not possible to have all this information on the same page, and even on the main page, some items are listed first, some second, etc. In other words, inevitably different items have different levels of exposure from very high to very low.

It is therefore necessary to select which items should receive high exposure and which not. To make this decision, we can use information about what different users prefer. The problem is that different users have different preferences. So, it is necessary to take all these preferences into account when selecting levels of exposure for different items.

Since we are talking about user-oriented systems, a natural idea is to follow the users’ preferences, and in decision theory, such preferences are described by numerical values known as utilities; see, e.g. Fishburn (1969), Fishburn (1988), Luce and Raiffa (1989), Raiffa (1997), Nguyen et al. (2009), Nguyen et al. (2012) and Kreinovich (2014). Each user i makes a decision that maximizes his/her utility u_i.

To combine these utilities, a seemingly natural idea is

1. To add the utilities of all the users and

2. To use maximizing this sum as a criterion for selecting levels of exposure.

Comment. This is similar to how we gauge the state of a country’s economy – crudely speaking, we add up all the incomes and consider the resulting sum – gross domestic product (GDP) – as an appropriate measure for comparing different countries.

To illustrate what is wrong with this seemingly reasonable idea, let us consider a simplified example of a news website that serves both left- and right-leaning users; this example is, in effect, borrowed from Singh and Joachims (2018) and Joachims et al. (2021). Every day, there are some left-leaning new articles and some right-leaning new articles, and it is known that each user prefers the news articles that are closer to his/her own beliefs.

On top of the news website, we can place

1. Either a link to a left-learning new article

2. Or a link to a right-leaning news article.

What is the best proportion of times p_L when the left-leaning article is placed on top?

To answer this question, let us introduce some notations. Let us denote

1. By U, the average utility of the user seeing a link to his/her preferred article placed on top and

2. By u (u < U), the average utility of having to go through other links first in order to access the desired link.

Let us also denote

1. The number of left-leaning users by n_L and

2. The number of right-leaning users by n_R.

Now, we are ready to perform the analysis:

1. A left-leaning user:

   • Gains utility U in p_L cases and

   • Gains utility u in the remaining 1 − p_L cases.

Thus, this user’s expected utility is equal to p_L ⋅ U + (1 − p_L) ⋅ u.

1. Similarly, a right-leaning user:

   • Gains utility u in p_L cases and

   • Utility U in the remaining 1 − p_L cases.

Thus, this user’s expected utility is equal to p_L ⋅ u + (1 − p_L) ⋅ U.

So, the sum of the utilities of all the users is equal to

One can see that this expression is a linear function of the unknown p_L. We can explicitly describe this expression as a linear function:

We want to find the value p_L ∈ [0, 1] that maximizes the objective function (2). A linear function attains its largest value on an interval at one of its endpoints, i.e. in this case, either for p_L = 0 or for p_L = 1. In our case, we can see that

1. When n_L > n_R, the maximum is attained when p_L = 1, i.e. when the left-leaning article is always placed on top, and

2. When n_L < n_R, the maximum is attained when p_L = 0, i.e. when the right-leaning article is always placed on top.

In both cases, this does not seem fair to the minority group that its articles are never placed on top.

Not only it is not fair but it also harmful to the business: when the minority group feels discriminated by this website, they will stop using it and form their own news website, which is, by the way, what often happens.

A usual opinion in the recommender community is that the above limitation shows that we must go beyond utility and explicitly take fairness into account when selecting levels of exposure; see, e.g. Joachims et al. (2021).

In this paper, we show that the problem is caused not so much by restricting ourselves to utility but rather by an inadequate way utilities of different users are combined now.

We show that if we use an adequate way to combine utilities, then a purely utility-based approach already leads to a fair selection. So there is no need to additionally take fairness into account.

According to the decision theory, a proper way to select an alternative is to maximize the product of utilities u₁ ⋅ … ⋅u_n; this was proven by the Nobelist John Nash and is thus called Nash’s bargaining solution; see, e.g. Nash (1950) and Luce and Raiffa (1989).

In the above two-group example, according to Nash’s criterion, we must select the proportion p_L that maximizes the following product:

Since logarithm is a strictly increasing function, maximizing the product (3) is equivalent to maximizing its logarithm:

Differentiating the expression (4) with respect to the unknown p_L and equating the derivative to 0, we conclude that

i.e. equivalently,

Dividing both sides by U − u and inverting the resulting fractions, we get

Multiplying both sides by n_L ⋅ n_R, we get

Moving all the terms containing p_L to left side and other terms to the right side, we get

If we divide both sides by the total population n_L + n_R and take into account that the ratios

describe the proportion of the two types of users, then we get

so

Of course, this formula only makes sense if the right-hand side of formula (5) is between 0 and 1:

1. If the right-hand side of formula (5) is smaller than 0, then we should take p_L = 0, and

2. If the right-hand side of formula (5) is larger than 1, then we should take p_L = 1.

Here

1. The inequality 0 ≤ p_L is equivalent to

Thus, this inequality is equivalent to

1. Similarly, the inequality p_L ≤ 1, i.e.

is equivalent to r_L ⋅ U − r_R ⋅ u ≤ U − u, i.e. to

By adding u to both sides of the last inequality, we get r_L ⋅ (U + u) ≤ U, i.e.

Thus, we arrive at the following conclusion.

1. If the proportion r_L of the L-group is small, namely, smaller than

then links to messages favored by this group should never appear on top.

1. If the proportion r_L of the L-group is sufficiently large, namely, larger than

then links to messages favored by this group should always appear on top.

1. In all other cases, links to messages favored by this group should be placed on top with frequency

1. In a realistic case when U = 2u

   • Messages favored by a group smaller than 1/3 will never be on top,

   • Messages favored by a group larger than 2/3 should always appear on top and

   • In intermediate cases 1/3 ≤ r_L ≤ 2/3, messages of both groups should appear on top.

2. When the groups are almost equal, i.e. when r_L ≈ r_R ≈ 0.5, we have

In other words,

• In approximately half of the cases, the left-leaning article is on top and

• In approximately half of the cases, the right-leaning article is on top.

This is exactly the fairness that was missing in the current solution.