## 2 Background and Related Work
### Problem Formalization  
After presenting MSRS, as well as the main evaluation metrics that are examined in the context of this publication, alongside several applications of the latter in RS, it is worth presenting the work conducted by [PERSON] et al. [7]. In this publication, authors provide a mathematical formalization for the problem of fairness across item providers in terms of user coverage and diversity. Therefore, the problem at hand, along with the proposed solution as defined by [PERSON] et al. [7], are presented in brief. According to [PERSON] et al. [7], a set of items, \(I\), and a set of users, \(U\), are considered along with some baseline recommendation system (in our case, item-based Collaborative Filtering) that generates recommendation lists, \(Lu\), for each user, \(u\). Additionally, that \(C\) is the number of providers, and each item belongs to exactly one provider, while \(Ic\) is the set of items of provider \(c\), \(c=1,\ldots,C\) for each user, \(u\), and item, \(i\), of a provider. Finally, \(riu\) denotes the predicted rating with the baseline RS algorithm. It is worth mentioning that the proposed methodology can be generalized for categories or classes of items. In particular, \(C\) can also denote the number of categories or classes and not necessarily the different providers. Hence, from now on, provider and category will be used interchangeably in the problem at hand. The output of the recommendation algorithm is a list of recommended items for each user. Each recommendation list has size \(L\). Additionally, \(Lu\) denotes the set of items recommended to the user, \(u\). \(Lu^{\prime}\) denotes the new list of recommended items that should satisfy coverage and diversity constraints. Moreover, \(x=(xiu\): \(i\in I,u\in U)\) denotes the new Boolean recommendation policy (if \(xiu=0\), item \(i\) is not recommended to user \(u\), if \(xiu=1\), item \(i\) is recommended to user \(u\)that should be found. The total deviation between the baseline recommendation lists and the new recommended ones is:  
\[Cost(x)=\frac{1}{L|U|}\left(\sum_{u\in U}\sum_{i\in Lu}riu-\sum_{i\in I}\sum_{u \in U}riu*xiu\right), \tag{1}\]  
Regarding provider coverage, it is calculated as the sum of the item coverage values for each item of a provider or category. Thus, the average per item user coverage for items of a given provider, \(c\), is:  
\[Cov(c,x)\;\frac{1}{|Ic|}\sum_{i\in Ic}\sum_{u\in U}xiu, \tag{2}\]  
Concerning per item diversity of users of provider, \(c\), it is calculated for each provider, \(c\), as follows:  
\[Div(c,x)\;\;\frac{1}{|Ic|}\sum_{i\in Ic}\sum_{u\in U}\sum_{v\in U,\;v\
eq u}duv*xiu* xiv, \tag{3}\]  
where \(duv\) is the dissimilarity between users \(u\) and \(v\). Instead of the absolute category diversity, the average normalized diversity (per item, per user pair) that will be used is defined as:  
\[\overline{Div(c,x)}=\frac{2}{|Ic|}\frac{\sum_{i\in Ic}\sum_{u\in U}\sum_{v\in V :u\
eq}duv*xiu*xiv}{(\sum_{i\in Ic}\sum_{u\in U}xiu)*(\sum_{i\in Ic}\sum_{u\in U }xiu-1)}\;, \tag{4}\]  
or simpler:  
\[\overline{Div(c,x)}=\frac{2}{|Ic|}\frac{\sum_{i\in Ic}\sum_{u\in U}\sum_{v \in V:u\
eq}duv*xiu*xiv}{Kc|Ic|*(Kc|Ic|-1)}\;, \tag{5}\]  
and the constraints for provider coverage become:  
\[Cov(c,x)>=Kc\;, \tag{6}\]  
and for diversity:  
\[Divc(c,x)>=Dc\;, \tag{7}\]  
where \(Kc\) is the minimum user coverage for the items of a provider, \(c\), and \(Dc\) is the minimum threshold for average per item and per user pair diversity for provider, \(c\). Along with the optimization problem in the same publication, a solution for the coverage constraints in polynomial time is provided, and a low complexity heuristic approach on top of the coverage solution is proposed in order to also solve the diversity constraints. The results of the proposed approach show satisfactory performance, according to the authors. In the context of this publication, we follow the proposed methodology and introduce a heuristic algorithm for the solution of the diversity constraints.