Main Problem:
This paper tries to tackle the famous problem of fair ranking. To avoid overdoing the formal definition of fair ranking as the previous summaries, I will just put it in a nutshell. Fair ranking is ordering a group of items in order to maximize utility while satisfying one or more fairness constraints.
Authors argue that traditional ranking methods, which only aim to be useful for users, may treat items unfairly. In particular, standard ranking systems can give items of comparable quality (i.e. relevance) very unequal visibility and economic potential. In other words, ranking algorithms that focus solely on maximizing utility for users can lead to unequal exposure for items, even if those items are of similar merit or relevance. This means that some items end up getting much more visibility and business opportunity compared to others that are essentially just as good. Conventional ranking approaches do not account for fairness towards the items being ranked.
Why we needed this approach?
To address the unfair treatment of similarly relevant items in rankings, existing research explores how to directly connect an item's quality to the visibility it receives in results. Specific definitions of fair exposure enforce constraints so items or groups get visibility proportional to their relevance on average. This exposure-based fairness approach has been expanded to end-to-end policy learning, dynamic ranking, evaluation metrics, and contextual bandits.
However, a key criticism is that there is no justification for selecting a specific function that links merit to exposure, such as a linear relationship. Furthermore, exposure-based fairness can still produce rankings that violate basic fairness principles.
In summary, current exposure-based fairness ranking methods aim to allocate visibility proportionally to an item's relevance. But there is no agreed way to define the relationship between relevance and exposure. Additionally, exposure-based approaches do not necessarily guarantee fundamentally fair rankings.
Hence, the authors proposed Impact-based ranking as fair division instead of exposure-based methods.
Methodology( my understanding so far)
To address the limitations of exposure-based fairness ranking, they developed an axiomatic approach rooted in fair division principles. They formulate fairness in ranking as a resource allocation problem, where ranking positions are resources to be fairly divided among items. They propose two fairness axioms - envy-freeness and dominance over uniform ranking.
Envy-freeness means no item can gain more impact by swapping position allocations with another item. Dominance over uniform ranking means all items gain more impact than with random ranking, ensuring participation benefit. This axiomatization avoids arbitrary exposure-relevance links and directly captures item impact like clicks and revenue, not just visibility.
Prior attempts to extend exposure-based fairness to impact-based individual fairness failed since they focus on the individual fairness of each item's impact have been demonstrated to result in flawed ranking systems. This makes this paper's proposed approach the first workable formulation of fairness in ranking that is centered on the individual impact of each item, rather than just exposure.
they formulated an optimization problem to extend the concept of Nash Social Welfare (NSW) to fair rankings:
𝜋 indicates policy. 𝑋𝜋 is the tensor whose (𝑢, 𝑖, 𝑘) element 𝑋𝑢,𝑖,𝑘 := P(𝜎(𝑖) =𝑘|𝜋,𝑢) denotes the marginal probability of item 𝑖 being ranked at the 𝑘-th position for user 𝑢 under policy.
Authors mentioned that " The objective maximizes the product of impacts on the items, and the constraints express that each item needs to have probability 1 to be placed in some position, and each position needs to have probability 1 of receiving an item."
It is notable that the optimization formulation part was mathematically challenging for me and the best I could do was to get an abstract sense about methodology and principals. I'll add up to this section after further understanding.
Results
To have explicit control over fairness-utility tradeoff, they extend the NSW(Nash Social Welfare) to what they call the 𝛼-NSW. 𝛼 is a positive hyper-parameter that controls the balance between maximizing user utility (large 𝛼) and guaranteeing impact-based fairness (small 𝛼). When 𝛼 = 0, the 𝛼-NSW objective is reduced to the standard NSW.
More about social welfare functions can be found here
They experimented with different values for 𝛼 and the results are as follows:
Title: Fair Ranking as Fair Division: Impact-Based Individual Fairness in Ranking Year: 2022 Venue: KDD
Main Problem: This paper tries to tackle the famous problem of fair ranking. To avoid overdoing the formal definition of fair ranking as the previous summaries, I will just put it in a nutshell. Fair ranking is ordering a group of items in order to maximize utility while satisfying one or more fairness constraints. Authors argue that traditional ranking methods, which only aim to be useful for users, may treat items unfairly. In particular, standard ranking systems can give items of comparable quality (i.e. relevance) very unequal visibility and economic potential. In other words, ranking algorithms that focus solely on maximizing utility for users can lead to unequal exposure for items, even if those items are of similar merit or relevance. This means that some items end up getting much more visibility and business opportunity compared to others that are essentially just as good. Conventional ranking approaches do not account for fairness towards the items being ranked.
Why we needed this approach? To address the unfair treatment of similarly relevant items in rankings, existing research explores how to directly connect an item's quality to the visibility it receives in results. Specific definitions of fair exposure enforce constraints so items or groups get visibility proportional to their relevance on average. This exposure-based fairness approach has been expanded to end-to-end policy learning, dynamic ranking, evaluation metrics, and contextual bandits. However, a key criticism is that there is no justification for selecting a specific function that links merit to exposure, such as a linear relationship. Furthermore, exposure-based fairness can still produce rankings that violate basic fairness principles. In summary, current exposure-based fairness ranking methods aim to allocate visibility proportionally to an item's relevance. But there is no agreed way to define the relationship between relevance and exposure. Additionally, exposure-based approaches do not necessarily guarantee fundamentally fair rankings. Hence, the authors proposed Impact-based ranking as fair division instead of exposure-based methods.
Methodology( my understanding so far) To address the limitations of exposure-based fairness ranking, they developed an axiomatic approach rooted in fair division principles. They formulate fairness in ranking as a resource allocation problem, where ranking positions are resources to be fairly divided among items. They propose two fairness axioms - envy-freeness and dominance over uniform ranking. Envy-freeness means no item can gain more impact by swapping position allocations with another item. Dominance over uniform ranking means all items gain more impact than with random ranking, ensuring participation benefit. This axiomatization avoids arbitrary exposure-relevance links and directly captures item impact like clicks and revenue, not just visibility.
Prior attempts to extend exposure-based fairness to impact-based individual fairness failed since they focus on the individual fairness of each item's impact have been demonstrated to result in flawed ranking systems. This makes this paper's proposed approach the first workable formulation of fairness in ranking that is centered on the individual impact of each item, rather than just exposure.
they formulated an optimization problem to extend the concept of Nash Social Welfare (NSW) to fair rankings:
𝜋 indicates policy. 𝑋𝜋 is the tensor whose (𝑢, 𝑖, 𝑘) element 𝑋𝑢,𝑖,𝑘 := P(𝜎(𝑖) =𝑘|𝜋,𝑢) denotes the marginal probability of item 𝑖 being ranked at the 𝑘-th position for user 𝑢 under policy. Authors mentioned that " The objective maximizes the product of impacts on the items, and the constraints express that each item needs to have probability 1 to be placed in some position, and each position needs to have probability 1 of receiving an item." It is notable that the optimization formulation part was mathematically challenging for me and the best I could do was to get an abstract sense about methodology and principals. I'll add up to this section after further understanding. Results To have explicit control over fairness-utility tradeoff, they extend the NSW(Nash Social Welfare) to what they call the 𝛼-NSW. 𝛼 is a positive hyper-parameter that controls the balance between maximizing user utility (large 𝛼) and guaranteeing impact-based fairness (small 𝛼). When 𝛼 = 0, the 𝛼-NSW objective is reduced to the standard NSW. More about social welfare functions can be found here
They experimented with different values for 𝛼 and the results are as follows:
Datasets "Delicious" and "Wiki10-31K" from The Extreme Classification Repository Codebase: https://github.com/usaito/kdd2022-fair-ranking-nsw