A Taxation Perspective for Fair Re-ranking

In Theorem 2, we will establish the non Lipschitz continuous (Hager, 1979) of the optimization objective for the existing taxation w.r.t. the tax rate $\lambda$:

The detailed proof of Theorem 2 can be seen in Appendix B. Intuitively, the binary variable $\bm{x}_{u,i}$ under the item-level policy and the non-differentiable property of some $r(\bm{v})$ lead to the non-continuity. The Theorem 2 tells us a slight change in tax rates $\lambda$ leads to significant shifts in fair re-ranking performances.

we will establish the definition of the price of taxation (POT) (Bertsimas et al., 2011) as the maximum ranking accuracy loss across various taxation levels, formulated as the ratio of ranking accuracy loss to the maximum accuracy:

where $\textbf{Acc}^{\prime}(\lambda)$ denotes the ranking accuracy (here, accuracy refers to the overall user-item ranking scores that these items are exposed to by users) under existing tax rate $\lambda$, i.e.,

and $\bm{x}^{*}(\lambda)$ is the optimal result with specific tax rate $\lambda$. Upon examining Equation (3), it becomes evident that the relationship between the ranking result $\bm{x}^{*}(\lambda)$ and the tax rate is non-linear and non-continuous (refer to Theorem 2 and the non-linear of the fairness function $r(\bm{v})$ (Xu et al., 2023a; Patro et al., 2020)). Simultaneously, it is noteworthy that Equation (3) represents a well-studied integral knapsack problem (Salkin and De Kluyver, 1975), and obtaining an upper bound for such a non-linear and non-continuous knapsack problem remains a huge challenge (Cacchiani et al., 2022). Therefore, we are uncertain about the extent to which a specific tax rate will incur accuracy losses.

To gain a better understanding of Tax-rank, we visualize the geometric to show our taxation process for taxing the difference in utility between two items. In Figure 2, the ranking system only has two items and ranking size $K=1$. The x-axis $\bm{v}_{1}$ and y-axis $\bm{v}_{2}$ represent the expected click numbers of items 1 and 2 (see Section 3). We set their weight $\gamma_{1}=\gamma_{2}=1$. The green area describes the feasible region of all the possible values of $\bm{v}_{1}$ and $\bm{v}_{2}$ under ranking constraint. The circle points are optimal solutions under different tax rates $t$. The line in Figure 2 (b) represents the tangent between the optimization objective and the feasible region.

In Figure 2 (a), we observe that when $t=0$ (red points), prioritizing overall utility $\bm{v}_{1}+\bm{v}_{2}=2.5$; at $t=1$ (yellow points), the tax rate will make the item utilities proportional to its weight, i.e., $\bm{v}_{1}:\bm{v}_{2}=2:5$. At $t=\infty$ (blue points), the two items will share the same utility, i.e., $\bm{v}_{1}=\bm{v}_{2}$. In Figure 2 (b), we give a geometric explanation to show the optimal points change w.r.t. tax rate. From Figure 2, the optimal points must stay in the boundary lines (i.e., Pareto frontier) of the ranking feasible region (see detailed proof in  (Bertsimas et al., 2011)). Therefore, the optimal points should be the tangent points between the contours of the optimization objective and the Pareto front. Let’s consider the taxation process in two-dimensional space.

For example, in Figure 2 (b), when $t=0$, the red point is the tangent point between the red line $\bm{v}_{1}+\bm{v}_{2}=2.5$ and the Pareto front. When $t=1$, a tax of $\frac{\bm{v}_{2}}{\bm{v}_{1}}$ is applied to from $\bm{v}_{2}$ to $\bm{v}_{1}$ along the red line if $\bm{v}_{2}>\bm{v}_{1}$, which means the slope $\frac{\partial\bm{v}_{2}}{\partial\bm{v}_{1}}$ becomes $\frac{\bm{v}_{1}}{\bm{v}_{2}}$. When $\bm{v}_{1}>\bm{v}_{2}$, similar operation also make the slope $\frac{\partial\bm{v}_{2}}{\partial\bm{v}_{1}}$ becomes $\frac{\bm{v}_{1}}{\bm{v}_{2}}$. Then the taxation process leads to the optimization function of $\log\bm{v}_{1}+\log\bm{v}_{2}$ (orange line). Similarly, $t=\infty$, a tax of $(\frac{v_{2}}{v_{1}})^{\infty}$ is applied at each point on the red line, resulting in a slope $\frac{\partial\bm{v}_{2}}{\partial\bm{v}_{1}}$ of each point become $\infty$ and $0$ for each point when $\bm{v}_{2}>\bm{v}_{1}$ and $\bm{v}_{1}>\bm{v}_{2}$, respectively. Such taxation process leads to the objective becomes $\min(\bm{v}_{1},\bm{v}_{2})$ (blue line). Without loss of generality, tax the value as $\frac{\gamma_{j}}{\gamma_{i}}(\frac{\bm{v}_{i}}{\bm{v}_{j}})^{t}$ for every $\bm{v}_{i}>\bm{v}_{j}$ will transform the objective into the Equation (5).

In summary, the tax process of imposing taxes based on the disparity in utility between two items will determine the optimization objective of Equation (5) by influencing the slope of each point in the geometric perspective.

we demonstrate the optimization objective meets two ideal controllable requirements: continuous and controllability over the accuracy loss.

Continuity. Firstly, the Tax-rank policy $f(\bm{x};t)$ adheres to the Lipschitz continuity property (Hager, 1979) of the optimization objective associated with the existing taxation concerning the tax rate $t$. Because we can easily observe that $f(\bm{x};t)$ takes an exponential form w.r.t. $t$, and their first-order derivatives are also continuous (Lan et al., 2010). Meanwhile, transforming the binary solution of previous methods to a continuous solution also ensures feasible region is continuous.

Controllability over accuracy loss. For the bound the maximum ranking accuracy loss across different taxation degrees under varying tax rates $t$, we will have the following Theorem:

Detailed proof can be seen in Appendix C. As we can see from Theorem 1: when increasing the tax rate $t$ in a ranking system, there is a bound on the rate $1-O(|\mathcal{U}|^{-\frac{t}{1+t}})$ at which ranking utilities will decrease. The bound offers fair re-ranking systems a controllable way to determine the appropriate tax rate $t$.

This lemma can be easily achieved when $\sum_{u\in\mathcal{U}}\sum_{i\in\mathcal{I}}w_{u,i}\bm{x}_{u,i}\geq\sum_{i\in\mathcal{I}}\eta_{i}\sum_{u\in\mathcal{U}}\bm{x}_{u,i}.$ Let $\bm{e}^{*}$ be the optimal value of the variable $\bm{e}$, which represents the accumulated exposure of items over all users. Then we will apply the Sinkhorn algorithm (Pham et al., 2020) to project the averaged exposure $\bm{e}^{*}$ to recommendation decision variable $\bm{x}\in\mathcal{X}_{s}$ discussed in Section 3.

We obtain the final ranking result by utilizing the following sample process, where $\widetilde{\bm{x}}$ (i.e. ranking score distribution) is derived from the OT projection process.

where it implies sampling $K$ non-repeated items to user $u$ according to the recommended probability $\widetilde{\bm{x}}_{u,i}\in[0,1]$ of item $i$.

We construct a matrix $\bm{C}=\mathbb{R}^{|\mathcal{U}|\times|\mathcal{I}|}$, where the element $\bm{C}_{u,i}=\gamma_{i}w_{u,i}$. An OT problem can be formulated as:

where $\bm{1}$ denotes a vector of ones, $\bm{e}^{*}$ denotes the optimal value of Equation (7) and $\lambda_{ot}$ is the coefficient of entropy regularizer. $\langle\bm{x},-\bm{C}\rangle$ results transport plan lies on the Pareto frontier and $H(\bm{x})=\sum_{u\in\mathcal{U}}\sum_{i\in\mathcal{I}}\bm{x}_{u,i}\log(\bm{x}_{u,i}),$ which forces the variable $\bm{x}_{u,i}$ into the feasible region $[0,1]$. The constraint condition ensures that the ranking satisfies the limitation that each user can only be ranked among the top $K$ items, and it also guarantees that the exposure of each item aligns optimally with the predefined exposure vector $\bm{e}^{*}$.

This problem can be efficiently solved by the Sinkhorn algorithm (Swanson et al., 2020), where the solution of the form $\widetilde{\bm{x}}=\text{diag}(\bm{m})\bm{B}\text{diag}(\bm{n})$, where diag$(\cdot)$ denote the generating diagonal matrix from vector,$\bm{B}=e^{\frac{-C}{\lambda}}$, and $\bm{m}\in\mathbb{R}^{|\mathcal{U}|}$, $\bm{n}\in\mathbb{R}^{|\mathcal{I}|}$, which iteratively computes $\bm{m}\leftarrow K\bm{1}\oslash\bm{B}\bm{n},\quad\bm{n}\leftarrow\bm{e}^{*}\oslash\bm{B}\bm{m},$ where $\oslash$ denotes element-wise division.

Firstly, we experiment to assess the continuity of the proposed Tax-rank and other baseline methods by adjusting the tax rate $t$ or other parameters related to fairness. As shown in Figure 5, we draw the Lorenz Curve (Gastwirth, 1971) of three best-performing baselines and our model Tax-rank under different tax rate $t$ or other parameters. Since Lorenz Curve is a graphical representation that vividly illustrates income or wealth distribution within a population, providing insights into the level of inequality in economics.

Figure 5 shows the proportion of overall exposure percentage assumed by the bottom $x$% items. In simpler terms, the Lorenz Curve reveals the percentage (y%) of the total exposures accumulated by the worst-off $x\%$ of items in the distribution. From Figure 5, it is evident that as the tax rate changes from $0$ to $\infty$, Tax-rank exhibits superior continuity. This is observed by the nearly averaged increase in the colored area between the two Lorenz Curves (can also be viewed as the fairness increasing value when increasing tax rate $t$). It indicates a more consistent response to a tenfold increase in the tax rate. On the contrary, as the tax rate changes, baselines, exhibit either minimal alterations (P-MMF) or an uneven increase (Welf and FairRec) in the colored area. This implies that a minor adjustment in the fair-aware parameter will result in a more significant performance alteration compared to Tax-rank.

Then, we experiment Figure LABEL:fig:analysis_1 (a) to demonstrate how the price fairness of the taxation (POT) changes of Tax-rank and baseline P-MMF w.r.t. variations in the tax rate $t$, ranging from $0$ to $1$. Since P-MMF is a represented and best-performing tax policy in Theorem 1.

From the curve, it is evident that as we increase the tax rate $t$, our proposed Tax-rank and P-MMF approach leads to a reduction in the total ranking accuracy. Firstly, it is evident that the POT achieved by Tax-rank is notably lower compared to that of P-MMF, highlighting the effectiveness of the Tax-rank approach. Secondly, we can also observe that the POT of Tax-rank obeys a smooth form, as the theoretical analysis results in Theorem 1. However, the previous ranking tax policies exhibit a more complex POT function form, resulting in poor systematic controllability.

We conduct experiments to investigate the total inference time of the Tax-rank method compared to other item fairness baselines. In our analysis, our objective is to assess the total inference time across various user sizes $|\mathcal{U}|$, within real-world ranking applications. Therefore, we conducted tests to measure the total inference time of various models in terms of the varying number of users, all while keeping the number of items constant.

Figure LABEL:fig:analysis_1 (b) reports the curves of total inference time (s) w.r.t. user size $|\mathcal{U}|$. It is worth noting that the Tax-rank method demonstrates remarkably low inference times, typically taking less than ten million seconds across different user sizes. Furthermore, when compared to other baseline methods, the inference time of these alternatives tends to increase either linearly or exponentially with changing user sizes, whereas Tax-rank consistently maintains a low inference time.

This is attributed to the fact that the CP solver process (Equation (7)) along with Tax-rank reduces the variable size from $|\mathcal{U}||\mathcal{I}|$ to $|\mathcal{I}|$ and employs the OT algorithm to efficiently map the solution to each user. Therefore, Tax-rank method involves matrix operations with limited sensitivity to changes in user size.

In Figure 6, we visualize the Tax-rank recommendation results under the tax rate of $0,1,3$. In Figure 6, we visualize the ranking result matrix $\widetilde{\bm{x}}$, where the elements $\widetilde{\bm{x}}_{u,t}$ denotes the probability of recommending item $i$ to user $u$ in Equation (9). We also visualize the utility vector $\bm{v}$, which is the amortized value for the columns value of $\widetilde{\bm{x}}$ (i.e., $\bm{v}=\sum_{u\in\mathcal{U}}\widetilde{\bm{x}}_{u,i}$). The utility vector $\bm{v}_{i}$ represents the utility value associated with the ownership of item $i$.

The results clearly demonstrate that the accuracy-first solution consistently ranks the most popular items highly for users, thereby enhancing overall utility but potentially leading to market dominance by a few top items. Regarding $t=1$, Tax-rank tends to distribute rankings to items in proportion to their contribution to the market. For $t=3$, Tax-rank method strives to provide equal exposure and similar utilities to every item in the ranking. The experiment also served as validation that Tax-rank method can effectively adapt to various fairness principles as intended.

In this section, we first conduct the ablation study for the OT regularizer coefficient $\lambda_{ot}$ (Equation (9), which trade-off the entropy loss to force the variable $\bm{x}_{u,i}$ into the feasible region. Figure  8 illustrates how the ranking accuracy (eCN) and fairness metric (Gini) w.r.t. $\lambda_{ot}$ from $0.1-2.0$.

Specifically, from Figure  8 (a), we can observe that when the tax rate $t$ is small ($t<1$), the accuracy increases as $\lambda_{ot}$ becomes larger. When the tax rate $t$ is large ($t\geq 1$), the accuracy will decrease as $\lambda_{ot}$ becomes larger. From Figure  8 (b), We can observe that Gini remains relatively stable across the different $\lambda_{ot}$. Moreover, as the tax rate $t$ increases, Tax-rank begins to prioritize fairness among items more prominently, resulting in a decrease in Gini.

The reason is the trade-off between the smoothness and convexity of the exposure probability distribution among items by tuning the parameter $\lambda_{ot}$. A higher $\lambda_{ot}$ will emphasize more on the smoothness of the probability distribution, implying a reduced disparity in exposure among items. When tax rate $t$ is relatively small ($t<1$), a slight reduction in the difference in exposure probability among items allows some items with lower $w_{u,i}$ to gain more exposure, resulting in an increase in eCN. However, when $t$ becomes larger, the increased smoothness of probability distributions results in a decrease in eCN consequently.