Theodoros Giannakas

Pavlos Sermpezis
email: sermpezis@csd.auth.gr

Anastasios Giovanidis
email: anastasios.giovanidis@lip6.fr

Thrasyvoulos Spyropoulos

George Arvanitakis
email: garvanitakis@csd.auth.gr

Fairness in Network-Friendly Recommendations

of the RS of the content provider towards content that can be delivered in a "network-friendly" way (e.g., cached in the mobile edge [START_REF] Chatzieleftheriou | Caching-aware recommendations: Nudging user preferences towards better caching performance[END_REF]- [START_REF] Garetto | Similarity caching: Theory and algorithms[END_REF], or coded broadcast transmissions [START_REF] Lin | Joint pushing and recommendation for susceptible users with time-varying connectivity[END_REF]- [START_REF] Lin | Content pushing over multiuser miso downlinks with multicast beamforming and recommendation: A cross-layer approach[END_REF]), thus shaping the user demand in favor of this content.

The NFR paradigm involves three main parties: the network, the users, and the content provider. Existing works design NFR schemes that explicitly aim to benefit the network. Indeed, the envisioned network gains (lower load, congestion, resources, or costs) have been shown to be very promising [START_REF] Spyropoulos | Soft cache hits and the impact of alternative content recommendations on mobile edge caching[END_REF]- [START_REF] Giannakas | Soba: Session optimal mdp-based network friendly recommendations[END_REF]. Moreover, the user experience can improve as well due to the higher satisfaction from high quality content delivery [START_REF] Sermpezis | Towards qos-aware recommendations[END_REF]. Finally, there can be benefits for the content provider (e.g., higher user engagement); however, those have only been envisioned as a consequence of the higher user satisfaction, but have not been explicitly studied.

The problem: Fairness in NFR. To enable network benefits through NFR, the "cost" to be paid by the RS is that NFR (a) nudge the optimal recommendations list provided to users, which may lead to worse user satisfaction, and (b) bias the demand for different contents (by making some contents more and others less popular), which may lead to displeasure from the content owners/producers (e.g., YouTubers). The former (user perspective) has been explicitly taken into account in NFR schemes, by considering the quality of recommendations (QoR) in the nudged recommendations, e.g., by imposing a minimum threshold in the content similarity [START_REF] Giannakas | Show me the cache: Optimizing cache-friendly recommendations for sequential content access[END_REF] or a window of user preferences [START_REF] Chatzieleftheriou | Caching-aware recommendations: Nudging user preferences towards better caching performance[END_REF]. However, the latter (content provider perspective) has been overlooked in related literature. In fact, the shaping of the content demand relates to the fairness of a RS towards the content producers/owners, which is a key requirement for content providers and has attracted a lot of attention recently in the design of RS [START_REF] Abdollahpouri | Multi-stakeholder recommendation and its connection to multi-sided fairness[END_REF]- [START_REF] Liu | Personalizing fairness-aware re-ranking[END_REF].

On one hand, some unfairness due to NFR may be acceptable by the content providers under some conditions (during periods of network congestion, peak hours, etc.), in order to better satisfy the users or increase their engagement by avoiding serving them content in poor quality. However, previous works have not studied how much unfairness is created by the NFR schemes, and whether this is acceptable by the content provider. On the other hand, a content provider may need to satisfy some explicit fairness requirements for the contents (or, the content producers/owners), e.g., not allow a change in the demand larger than 5%. Up to now, this is not an option in Abstract-As mobile traffic i s d ominated b y c ontent services (e.g., video), which typically use recommendation systems, the paradigm of network-friendly recommendations (NFR) has been proposed recently to boost the network performance by promoting content that can be efficiently d elivered ( e.g., c ached a t the edge). NFR increase the network performance, however, at the cost of being unfair towards certain contents when compared to the standard recommendations. This unfairness is a side effect of NFR that has not been studied in literature. Nevertheless, retaining fairness among contents is a key operational requirement for content providers. This paper is the first t o s tudy the fairness in NFR, and design fair-NFR. Specifically, we use a set of metrics that capture different notions of fairness, and study the unfairness created by existing NFR schemes. Our analysis reveals that NFR can be significantly u nfair. W e i dentify a n inherent trade-off between the network gains achieved by NFR and the resulting unfairness, and derive bounds for this trade-off. We show that existing NFR schemes frequently operate far from the bounds, i.e., there is room for improvement. To this end, we formulate the design of Fair-NFR (i.e., NFR with fairness guarantees compared to the baseline recommendations) as a linear optimization problem. Our results show that the Fair-NFR can achieve high network gains (similar to non-fair-NFR) with little unfairness.

I. INTRODUCTION

Background. The paradigm of network-friendly recommendations (NFR) has been very recently proposed as a promising solution for improving the quality and/or the cost of content delivery [START_REF] Spyropoulos | Soft cache hits and the impact of alternative content recommendations on mobile edge caching[END_REF]- [START_REF] Munaro | Content recommendation and service costs in swarming systems[END_REF]. NFR is based on the fact that content traffic dominates the mobile traffic today [START_REF]Visual networking index: Forecast and trends[END_REF], [START_REF] Ericsson | Ericsson mobility report[END_REF] and the majority of content services (online video, radio, social networks, etc.) employ recommendation systems (RS), which heavily affect the user choices and shape the content demand [START_REF] Zhou | The impact of youtube recommendation system on video views[END_REF], [START_REF] Gomez-Uribe | The netflix recommender system: Algorithms, business value, and innovation[END_REF]. The main idea behind NFR is to nudge the recommendations the existing NFR schemes, since fairness requirements have not been considered as a design aspect in NFR. Contributions. Motivated by this gap in literature, this paper is the first to study the aspect of fairness in NFR:

• Fairness characterization. We use metrics that capture different notions of fairness in RS (Section II), and then quantify the unfairness created in a wide range of representative scenarios and NFR algorithms, and investigate the role of different system parameters (Section III). • The fairness vs. network gain trade-off. We identify an inherent trade-off between the network gains achieved by a NFR scheme and the resulting unfairness. We analytically study this trade-off and derive bounds. We show that existing NFR schemes, frequently operate far from the optimal operating point that is given by the bound (Section IV). • Optimal Fair-NFR. We formulate the problem of designing NFR that maximize the network gain, under fairness guarantees compared to the baseline RS. Through a series of transformations, we show that the problem of optimal fair-NFR can be expressed as a linear program (Section V). • The price of fairness. Studying the performance of the Fair-NFR scheme shows that by allowing a little unfairness, high network gains can be achieved, which is a promising message for the NFR paradigm. A comparison with (nonfair) NFR schemes demonstrates that the Fair-NFR scheme achieves equal gains with much less unfairness (Section VI).

II. PRELIMINARIES

A. Network-friendly Recommendations

We consider a content service that has integrated in its (web/mobile) platform a recommendation system (RS). When a user is in the platform and consumes (e.g., watches, listens to, reads, buys) a content, a list of recommendations is presented by the RS suggesting to her to consume another content next. This is a typical scenario for the majority of online video/radio services (e.g., YouTube, Netflix, Spotify), news sites, e-shops and online marketplaces (e.g., Amazon), online social networks (e.g., Facebook, Instagram), etc. In the following, we describe the generic setup considered in NFR; the main notation is summarized in Table I. Content service. Assume that the service has a content catalog K (|K| = K). Users request contents in two ways: (i) directly, e.g., by following an external link or typing the content through a search bar, or (ii) by following one of the recommendations provided by the RS of the service (users typically consume several contents when visiting the service). These are the main types of demand in most content services.

We define the demand p i for a content i as the fraction of all requests (i.e., direct and through recommendations) that are for this content; we denote as p = [p 1 , ..., p K ] the vector with the distribution of total demand for all contents. Network. We assume that a subset of the content catalog C ⊂ K can be delivered with low cost for the network (and/or in high quality). For instance, in the context of mobile edge caching considered by the majority of related work in NFR [START_REF] Spyropoulos | Soft cache hits and the impact of alternative content recommendations on mobile edge caching[END_REF]- [START_REF] Giannakas | Show me the cache: Optimizing cache-friendly recommendations for sequential content access[END_REF], [START_REF] Zhu | Coded caching with joint content recommendation and user grouping[END_REF]- [START_REF] Costantini | Approximation guarantees for the joint optimization of caching and recommendation[END_REF], the contents in C are cached in the mobile edge. In this context, and w.l.o.g., we set the cost for delivering contents in C to zero and the cost for the other contents to 1. Hence, the cache hit ratio, CHR = i∈C p i , captures the total benefit for the network (i.e., the decrease in the cost by using a cache).

Recommendations. We assume a "recommendation score" u ij for every pair of contents i, j ∈ K, which indicates how good a recommendation for content j after content i is. The score u ij may correspond to the similarity between two contents, or more generally to the relevance of recommending j after i (e.g., capturing from item-item collaborative filtering [START_REF] Sarwar | Item-based collaborative filtering recommendation algorithms[END_REF] to black-box deep learning architectures [START_REF] Covington | Deep neural networks for YouTube recommendations[END_REF]), and can be the output of any state-of-the-art RS. W.l.o.g, we assume u ij ∈ [0, 1] and higher values denote better recommendations.

Baseline RS (BS-RS) is the standard RS (i.e., non networkfriendly) that generates the recommendation scores u ij and is used in production by the content/service provider. After a user has consumed content i, the BS-RS recommends to the user a list R BS i that contains the N contents with the highest recommendation score values u ij .

Network-friendly RS (NF-RS) is a RS that takes into account the network conditions (e.g., delivery cost [START_REF] Giannakas | Show me the cache: Optimizing cache-friendly recommendations for sequential content access[END_REF], [START_REF] Sermpezis | Towards qos-aware recommendations[END_REF], cached contents [START_REF] Sermpezis | Soft cache hits: Improving performance through recommendation and delivery of related content[END_REF], [START_REF] Chatzieleftheriou | Jointly optimizing content caching and recommendations in small cell networks[END_REF], wireless channel [START_REF] Song | Making recommendations bandwidth aware[END_REF], [START_REF] Lin | Content pushing over multiuser miso downlinks with multicast beamforming and recommendation: A cross-layer approach[END_REF]) and provides a list of recommendations R N F i to the user. In general, the lists R N F i can be the same as those of the BS-RS R BS i , partially overlap with them, or be totally disjoint sets. Typically, the recommendations of NF-RS tend to (i) include more recommendations to contents that can be delivered in a network-friendly way (e.g., cached contents), while (ii) trying to maintain the quality of recommendations (QoR) by recommending contents with relatively high scores u ij . In a simple example, with one user, three contents a, b, c with scores u a = 1, u b = 0.8, u c = 0.5, and a BS-RS recommending only one content R BS = [a]. Let only b, c ∈ C be cached; then the NF-RS would recommend R N F = [b], because this would bring network gains, and would have QoR= u b ua = 0.8, which is higher than if c was recommended instead of b (QoR=0.5).

Finally, the resulting demand p depends on the underlying RS: a RS that selects more frequently a content i in the recommendation lists, will lead to an increase in the demand p i . In the remainder, we denote with a superscript the RS that corresponds to the content demand, e.g., p BS for the BS-RS and p NF for a NF-RS. The differences between the vectors p BS and p NF capture the notion of fairness, which we formally define below.

B. Fairness Definition

Content providers aim to satisfy two parties, their users (consumers) and the content owners (producers) [START_REF] Abdollahpouri | Multi-stakeholder recommendation and its connection to multi-sided fairness[END_REF]- [START_REF] Burke | Balanced neighborhoods for multi-sided fairness in recommendation[END_REF], [START_REF] Sacharidis | A common approach for consumer and provider fairness in recommendations[END_REF], [START_REF] Mehrotra | Towards a fair marketplace: Counterfactual evaluation of the trade-off between relevance, fairness & satisfaction in recommendation systems[END_REF], while at the same time maximizing their own utility (e.g., revenue) [START_REF] Abdollahpouri | Multi-stakeholder recommendation and its connection to multi-sided fairness[END_REF]. In general, the goal of a fair RS is to strike a balance between utility and satisfaction of the involved parties [START_REF] Sacharidis | A common approach for consumer and provider fairness in recommendations[END_REF], [START_REF] Mehrotra | Towards a fair marketplace: Counterfactual evaluation of the trade-off between relevance, fairness & satisfaction in recommendation systems[END_REF]. probability that a "direct request" is for content i ∈ K;

p (d) = p (d) 1 , ..., p (d) K and i∈K p (d) i = 1 G network gain, G = CHR N F -CHR BS
In the context of NFR, user satisfaction is taken into account with the concept of quality of recommendations (QoR). However, the content owner/producer satisfaction, which is identified as a key component in the design of fair RS, especially in multistakeholder settings [START_REF] Abdollahpouri | Multi-stakeholder recommendation and its connection to multi-sided fairness[END_REF], [START_REF] Burke | Multisided fairness for recommendation[END_REF], has been neglected in previous works in NFR. Hence, we focus on the need of the content provider to satisfy content owners/producers, by providing recommendations that are fair with respect to them (which in literature is referred to also as p-fairness [START_REF] Abdollahpouri | Multi-stakeholder recommendation and its connection to multi-sided fairness[END_REF], [START_REF] Burke | Multisided fairness for recommendation[END_REF]).

Fairness in RS can be defined in several ways [START_REF] Abdollahpouri | Multi-stakeholder recommendation and its connection to multi-sided fairness[END_REF]- [START_REF] Yang | Measuring fairness in ranked outputs[END_REF], depending on the system, the involved parties, the needs of the content provider, etc. The fairness of a RS can be measured with respect to the recommendations of a fair RS. In our setting, where the goal is to quantify the (un)fairness of NFR, this fair RS is by convention the BS-RS (i.e., any standard RS) and the fairness captures the deviation in the total demand p created by the NF-RS. Thus, a generic measure F can be used:

F = f (p BS , p NF ) (1)
In general, the function f can be defined at will according to the use case or requirements of the content provider. For example, [START_REF] Sacharidis | A common approach for consumer and provider fairness in recommendations[END_REF] suggests that f can be any probability divergence measure. Different measures f can capture different notions of fairness. In this paper, we consider the three fairness measures that are most commonly used in literature and practice1 :

F-max F max = max i∈K |p N F i -p BS i |
relates to the individual fairness [START_REF] Pessach | Algorithmic fairness[END_REF] and accounts for the "worst case", i.e., no content will have a demand difference larger than

F max . F-tv F tv = 1 2 • i∈K |p N F i -p BS i |
is the total variation distance between the two distributions, i.e., the average (absolute) change in the content demand [START_REF] Patro | Incremental fairness in two-sided market platforms: On smoothly updating recommendations[END_REF]. It allows more flexibility than F max in shaping the demand, since it does not impose a constraint for every single content; e.g., a large difference in a content demand can be compensated by small demand differences in other contents.

F-kl F kl = i∈K p BS i • log p BS i p N F i
is the Kullback-Leibler (KL) divergence, a widely used measure for the difference between distributions, and commonly used to quantify fairness in RSs [START_REF] Sacharidis | A common approach for consumer and provider fairness in recommendations[END_REF]- [START_REF] Yang | Measuring fairness in ranked outputs[END_REF]. F kl is more sensitive to changes in contents with lower demand, e.g., an increase ∆p in the demand p BS i leads to a higher increase in F kl when p BS i is small [START_REF] Steck | Calibrated recommendations[END_REF].

Remark: Note that F max , F tv ∈ [0, 1], whereas F kl ∈ [0, ∞] (F kl → ∞ when p N F i = 0 and p BS i = 0).
For the sake of presentation, in the results we normalize the values of F kl so that it takes values in [0, 1] and is comparable with the other metrics. In particular, we use the smoothed version of [START_REF] Sacharidis | A common approach for consumer and provider fairness in recommendations[END_REF], [START_REF] Steck | Calibrated recommendations[END_REF], where we substitute

p N F i → (1 -w) • p N F i + w • p BS
i , with w = 0.01 and normalize with its upper bound log 1 w ; i.e.,

F kl = 1 log 1 w • i∈K p BS i • log p BS i (1-w)•p N F i +w•p BS i
The above metrics reflect different notions of fairness and requirements of the content provider. In general, it is not possible to satisfy all notions of fairness at the same time [START_REF] Pessach | Algorithmic fairness[END_REF]. In this paper, we consider all these metrics, and study their characteristics in relation to NFR (Sections III and IV) and take them into account in the design of fair NF-RS (Section V). QoR vs. fairness. As a remark, we stress that the notions of QoR (considered in previous works) and fairness (not considered before) describe different quantities in NFR; the former relates to the satisfaction of the users/consumers, and the latter to the satisfaction of the content owners/producers. The following example demonstrates this distinction: Let two users and three contents a, b, c with scores u a = 1, u b = 0.8, u c = 0.8 (same for both users), and b, c ∈ C, i.e., are cached. The BS-RS recommends content a, with the highest score u, to both users. Let's assume two NF-RS that nudge the BS-RS recommendations towards cached contents: A NF-RS recommends b to both users, and another NF-RS recommends b to the first user and c to the second user. Since, u b = u c the QoR in both NF-RS is the same. However, the former NF-RS is less fair, e.g., in terms of F-max, since it increases twice the demand for content b compared to the latter NF-RS.

III. CHARACTERIZATION OF UNFAIRNESS IN NFR

In this section, we aim to understand the (un)fairness F in NFR. To this end, we employ an empirical approach where we (i) consider a wide range of scenarios, (ii) apply the BS-RS and different NF-RS algorithms that have been proposed in previous works, and (iii) calculate the resulting content demand and its unfairness (Section III-A). We analyze the results to investigate whether existing NFR schemes create unfairness, and what are the key factors that cause it (Section III-B).

A. Simulation Setup

Content catalogs. We consider content catalogs and matrices U = {u ij } extracted from two datasets of real services:

Last.fm. We use a dataset from the Last.fm database [START_REF]Last.fm dataset[END_REF], where we applied the "getSimilar" method to the content IDs' and populate the matrix U. As the resulting U matrix is quite sparse, for the purpose of demonstration, we keep the largest component of the underlying graph, and round to u ij = 1 the values above a threshold of 0.1. MovieLens. We use the Movielens movies-rating dataset [START_REF] Harper | The movielens datasets: History and context[END_REF], containing 69162 ratings (0 to 5 stars) of 671 users for 9066 TABLE II: Parameters of the simulation (in total, all their combinations give 1296 scenarios)

U: last.fm (K = 757), Movielens (K = 1060) N ∈ {2, 5, 10} p (d) ∼ {Zipf (s = 1), unif orm} C ∈ {5, 10, 20} α ∈ {0.5, 0.8, 0.99} q ∈ {0.5, 0.8, 0.9} W BF S ∈ {N, 2N } D BF S ∈ {1, 2}
movies. We apply an item-to-item collaborative filtering (using 10 most similar items) to extract the missing user ratings, and then use the cosine distance to calculate the similarity for each pair of contents. We set u ij = 1 for contents with cosine distance larger than 0.6, and 0 otherwise. Caching. We consider cache sizes C ∈ {5, 10, 20}, with a popularity-based caching policy, i.e., the cache contains the C contents with the highest demand under the BS-RS (p BS ). Content demand. Similarly to previous works [START_REF] Giannakas | Show me the cache: Optimizing cache-friendly recommendations for sequential content access[END_REF], [START_REF] Zhu | Coded caching with joint content recommendation and user grouping[END_REF], [START_REF] Chatzieleftheriou | Jointly optimizing content caching and recommendations in small cell networks[END_REF], [START_REF] Giannakas | The order of things: Position-aware network-friendly recommendations in long viewing sessions[END_REF], [START_REF] Lin | Joint pushing and recommendation for susceptible users with time-varying connectivity[END_REF], [START_REF] Lin | Content pushing over multiuser miso downlinks with multicast beamforming and recommendation: A cross-layer approach[END_REF], we assume that a user follows a recommendation with probability α, or directly requests a content with probability 1 -α. We set α ∈ {0.5, 0.8, 0.99}, to capture the behavior reported for YouTube (α=0.5) [START_REF] Zhou | The impact of youtube recommendation system on video views[END_REF] and Netflix (α=0.8) [START_REF] Gomez-Uribe | The netflix recommender system: Algorithms, business value, and innovation[END_REF] and an extreme value where users follow almost always recommendations (α=0.99), e.g. as in YouTube autoplay or online radio services like Last.fm, Jango, etc.. We assume that direct requests for different contents follow a Zipf distribution with exponent s, where we used a typical scenario with s = 1 [START_REF] Zhou | The impact of youtube recommendation system on video views[END_REF] and an extreme scenario with s = 0 (i.e., uniform distribution). We denote the distribution of direct requests as p (d) . NF-RS algorithms. Several NFR variants have been proposed. To avoid restricting our study to a single algorithm or setup, we consider three representative NF-RS algorithms. Greedy NF-RS includes in each recommendation list R i as many cached contents as possible, without violating a minimum QoR threshold q. It aims to maximize the CHR by considering every request independently (without taking into account the long term performance). It can be seen as a simplified version of only the recommendation part of the CawR algorithm [START_REF] Chatzieleftheriou | Jointly optimizing content caching and recommendations in small cell networks[END_REF] (with the cache assumed already filled) 2 , or the "Myopic" version of CARS [START_REF] Giannakas | Show me the cache: Optimizing cache-friendly recommendations for sequential content access[END_REF]. Multi-step NF-RS [START_REF] Giannakas | The order of things: Position-aware network-friendly recommendations in long viewing sessions[END_REF] is an algorithm that includes in each recommendation list R i a set of contents that satisfy a QoR constraint (similarly to the Greedy NF-RS) and maximizes the network gains in the long term, i.e., by taking into account requests made directly and through recommendations, and the probability α. It returns the optimal solution in our model setup under no fairness requirements. CABaRet [START_REF] Kastanakis | Cabaret: Leveraging recommendation systems for mobile edge caching[END_REF] follows a different approach, by leveraging the BS-RS and assuming no explicit knowledge on the scores u ij . For each content i, it does a breadth-first search (BFS) starting II). (b) Unfairness vs. QoR, in Movielens scenarios with α=0.8, N =5, C=10, uniform p (d) , Greedy (continuous lines) and Multi-step (dashed lines) NF-RS. from the list R BS i (depth 1), and then to the lists R BS j , ∀j ∈ R BS i , (depth 2), and so on. It returns a recommendation list that contains the cached contents found in the BFS and, if needed, fills the list with the initial recommendations R BS i . In all cases recommendation lists are of size N ∈ {2, 5, 10}. Quality of Recommendations (QoR). In the Greedy and Multi-step NF-RS, the QoR constraint is explicitly defined as a fraction of the recommendation quality of the BS-RS by a parameter q ∈ [0, 1], i.e., j∈R N F i [START_REF] Giannakas | Show me the cache: Optimizing cache-friendly recommendations for sequential content access[END_REF], [START_REF] Giannakas | The order of things: Position-aware network-friendly recommendations in long viewing sessions[END_REF]. In CABaRet, the QoR is implicitly determined by the width W BF S and depth D BF S parameters of the BFS [START_REF] Kastanakis | Cabaret: Leveraging recommendation systems for mobile edge caching[END_REF]. In our simulations, we consider values q ∈ {0.5, 0.8, 0.9}, and W BF S ∈ {N, 2N } and D BF S = {1, 2}.

u ij ≥ q • j∈R BS i u ij
Table II summarizes the parameters of the considered scenarios. In total, we simulated 1296 scenarios, accounting for all the combinations of the parameters.

B. Unfairness in NFR

In the scenarios we simulate, we calculate the content demand under the BS-RS (p BS ) and the different NF-RS algorithms (p NF ), and then the resulting unfairness captured with the metrics F (p NF , p BS ) defined in Section II-B. Unfairness in existing NF-RS algorithms. We first quantify the unfairness created by existing NF-RS algorithms. Figure 1(a) presents the CDF of the values of the fairness metrics F among all the scenarios we tested; large values of the fairness metric F denote more unfair systems (e.g., the system is fair for F =0 and very unfair for F =1). We see that the NF-RS algorithms create unfairness, which is very high in several cases (we remind that the presented F metrics take values in [0, 1]). Moreover, comparing the curves of the different metrics (or, notions) of fairness, we can see that F max that captures the individual fairness takes lower values, whereas F tv that is averaged over all contents takes the highest values (even up to 1). The CDF of F kl , which considers all contents while also giving emphasis on individual contents whose demand deviates a lot from p BS , lies between the other two metrics. The role of the QoR. with different QoR constraints q (x-axis). It is clearly seen that as the QoR constraint becomes looser (lower values in x-axis) the unfairness of the system increases (higher values in y-axis). This is due to the fact that by relaxing the required QoR, the NF-RS has more flexibility in changing the recommendation lists, and consequently this nudges the content demand p NF farther from p BS . However, it is interesting to note the change in unfairness is not linear to the QoR, but is rather a concave function that decreases more steeply for higher values of QoR.

In fact, a key observation in Fig. 1(b) is that even a small decrease in QoR from the maximum value that corresponds to the BS-RS (q = 1), can already lead to significant unfairness (e.g., see the F values for q = 0.9). This finding (similar behavior holds in all the scenarios we tested) highlights the following insight, which is a main motivation for this paper:

"The QoR constraint commonly used in NF-RS to satisfy the users, may not suffice to (implicitly) impose fairness for the content provider as well. To account for fairness, one needs to explicitly take it into account when designing a NF-RS."

The role of the NF-RS algorithm and the system parameters. Comparing the curves of the two NF-RS algorithms in Fig. 1(b), we see that the unfairness introduced by the Multi-step NF-RS is higher than the Greedy NF-RS, under any fairness metric F . This finding holds in all (for F tv , F kl ) and in 95% (for F max ) of the scenarios we tested, and is due to the fact that the Multi-step NF-RS, by accounting the long term behavior, can shape in a larger degree than the Greedy NF-RS (or other heuristics) the content demand under the same QoR constraint. Hence, on the one hand the Multi-step NF-RS achieves higher network gains, but on the other hand it leads to less fairness (e.g., 10% higher CHR and 45% higher F kl than Greedy among all scenarios). We observed the same relation between fairness and network gains, when varying the other system parameters as well; see Table III. Specifically, increasing the α means that the users choices are affected more by the RS, and the same happens for small N since there are less choices (recommendations); this makes the shaping of the demand caused by a NF-RS more intense, and leads to higher network gains, and as we present in Table III, less fairness as well. The cache size C does not significantly affect the fairness, but it also had a small effect on the network gains in the scenarios we tested.

The above observations raise the following question, on which we focus in the next section:

"Does great network gain come with great unfairness?"

IV. THE FAIRNESS VS. NETWORK GAINS TRADE-OFF

In this section we proceed to study the trade-off between the network gains that can be achieved by a NF-RS algorithm and the unfairness it creates. We first analyze the simulation results to verify that such a trade-off exists, and then study it analytically and derive analytic bounds (closed form expressions) for the minimum possible unfairness as a function of the network gains under any NFR scheme.

Let us first formally define the network gain G as the increase in the cache hit rate (CHR) achieved by a NF-RS:

G = CHR N F -CHR BS = i∈C (p N F i -p BS i ) (2)
where C ⊂ K is the set of cached contents. In other words, the network gain is the extra content demand that can be served by the cache when applying a NF-RS.

In Fig. 2 we present scatter plots, where each marker corresponds to a simulation scenario and its (x, y)-coordinates correspond to the resulting fairness metric F and network gain G values, respectively. The results verify our previous observations: as the achieved network gain increases, the unfairness of the system increases as well. This positive correlation holds for all fairness metrics. However, the exact behavior differs among the different F metrics (note that all subplots of Fig. 2 present the same simulation scenarios, i.e., with the same network gains); for instance, F max sees a lower increase and with values up to 0.3, while F tv has a larger increase with values up to 1.

In the following theorem we analytically the observed behavior, and derive theoretical bounds for the trade-off.

Theorem 1. Under any NF-RS and any system parameters, for the fairness F vs. network gain G trade-off it holds that

F max ≥ 1 C • G (3)
F tv ≥ G (4)
F kl ≥ -H • log(1 + G H ) -(1 -H) • log(1 - G 1 -H ) (5)
where C = |C| is the number of cached contents, and H = CHR BS = i∈C p BS i . Proof. The proof is given in the Appendix.

The expressions in Theorem 1 state that the maximum network gain that can be achieved by any NF-RS (i) cannot be larger than the desired F tv value, and (ii) increases with the cache size C in the F max case. This indicates that larger caches can allow network gains without compensating in individual fairness (F max ), while this is not the case in aggregate fairness (F tv ). In the case of F kl , the bound is given by a non-linear function (convex in G), which depends on the cache size and the distribution of the demand under the BS-RS (captured by the parameter H = CHR BS ).

Comparing the results in Fig. 2 with the bounds, we can see that in some scenarios the achieved network gains are close to (or, coincide with) the bound, i.e., the bounds are tight 3 .

However, in the majority of scenarios, the operating point of the considered NF-RS algorithms is far from the bound. For instance, in Fig 2(d) that gives the CDF of the distance (along the x-axis) between the operating points and the bound, we can see that in half of the cases (i.e., for 0.5 in the y-axis) the resulting unfairness (x-axis) is at least 50% larger than the value of the bound for F max and F kl and 20% larger for F tv . The fact that NF-RS algorithms do not operate on the bound can be due to (i) the system parameters (e.g., the QoR constraint) that restrict an algorithm from shaping arbitrarily the content demand, and in this case the bound may not be achievable, or (ii) the NF-RS algorithms themselves, which were designed to optimize the network gain without taking the fairness into account. Thus, a question that follows naturally is: "Can a NF-RS be designed to operate closer to the bound, and achieve the optimal fairness vs. network gain trade-off?"

In Section V we address the above question and design an optimal NF-RS algorithm that achieves the maximum network gain under a fairness constraint, and in Section VI we study how the introduced constraint affects the network gains.

V. OPTIMAL FAIR NFR In this section we formulate the problem of designing the optimal NF-RS that takes fairness into account. We first model and describe the problem, and then prove that it can be expressed as a linear program (LP) whose solution is the optimal fair NF-RS. Objective. The objective in NFR is to maximize the network gains (or, equivalently minimize the network cost), which in our framework is captured by the CHR, i.e., i∈C p N F i . Decision variables. An NF-RS algorithm selects which contents to recommend, i.e., the recommendation lists R i4 . We model the recommendation decisions with a set of variables r ij , which denote the probability (or frequency) that a content j appears in the recommendation list of i, i.e., r ij = Prob{j ∈ R i }. We denote as R the K × K matrix that contains all the variables r ij ∀i, j ∈ K. We follow a probabilistic approach, i.e., r ij ∈ [0, 1] (instead of the deterministic r ij ∈ {0, 1}), to capture variations of recommendations among different users, or even for the same user (e.g., to not show always the same recommendations for a given content). Constraints. First, we require that the decision variables are probabilities (r ij ∈ [0, 1]) and the recommendation lists contain N recommendations ( j∈K r ij =N ) [START_REF] Giannakas | The order of things: Position-aware network-friendly recommendations in long viewing sessions[END_REF], [START_REF] Giannakas | Soba: Session optimal mdp-based network friendly recommendations[END_REF]. Second, we use a threshold q ∈ [0, 1] for the QoR constraint similarly to previous works, i.e., j∈K r ij • u ij ≥ q • q BS i , where q BS i the maximum QoR achieved by the BS-RS. Finally, we introduce the fairness constraint, by using a threshold c f for the maximum allowed unfairness, i.e., F (p BS , p NF ) ≤ c f , where F is any of the metrics F max , F tv , or F kl . Both thresholds q and c f , and the fairness metric F , can be selected by the content provider according to its operational requirements.

In the following theorem we express the above problem as a LP. To do this, we need to introduce a set of auxiliary variables and transform the non-linear expressions in the objective and constraints; the remainder of this section gives the proof, which includes all the needed details.

Theorem 2. The optimal fair NF-RS is given by the solution of the following linear optimization problem:

maximize z,p NF ,W i∈C p N F i (6a) subject to p N F j - α N • i∈K wij = p d (j), ∀j ∈ K (6b) j∈K wij • uij -p N F i • q • q BS i ≥ 0, ∀ i ∈ K, (6c) j∈K wij -N • p N F i = 0, wii = 0, ∀ i ∈ K (6d) wij -p N F i ≤ 0, wij ≥ 0, ∀ i, j ∈ K (6e) S(z, p NF ) (6f)
where z ∈ R K , W ∈ R K×K , and S(z, p NF ) a set of linear constraints given in Table IV for each fairness metric.

IV: Set of linear fairness constraints S(z, p NF ).

Fmax:

p BS i -p N F i ≤ c f p N F i -p BS i ≤ c f ∀ i ∈ K Ftv: i∈K z i ≤ c f p BS i -p N F i ≤ z i ∀ i ∈ K p N F i -p BS i ≤ z i ∀ i ∈ K F kl : i∈K p BS i • z i ≥ -c f -i∈K p BS i log(p BS i ) z i ≤ e (m-1)•s • p N F i -(m -1)s -1, ∀i ∈ K, m ∈ {1, ..., M }
Proof. The objective (and the fairness constraint) involves terms of the content demand p NF , which depends on the recommendations R. In the considered framework, and similarly to previous works (e.g., [START_REF] Giannakas | Show me the cache: Optimizing cache-friendly recommendations for sequential content access[END_REF], [START_REF] Zhu | Coded caching with joint content recommendation and user grouping[END_REF], [START_REF] Chatzieleftheriou | Jointly optimizing content caching and recommendations in small cell networks[END_REF], [START_REF] Giannakas | The order of things: Position-aware network-friendly recommendations in long viewing sessions[END_REF], [START_REF] Lin | Content pushing over multiuser miso downlinks with multicast beamforming and recommendation: A cross-layer approach[END_REF]), the content demand can be modeled with a Markov Chain, with transition probabilities that depend on the recommendations R, the direct requests p (d) and the probability α. Hence, using the result of [START_REF] Langville | Deeper inside pagerank[END_REF] (the detailed proof is omitted due to space limitations), we prove the following lemma.

Lemma 1. The content demand p NF is given by

p NF = (1 -α) • p (d) • I - α N • R -1 (7)
for α ∈ (0, 1) and p (d) > 0; I is the K × K identity matrix.

Lemma 1 gives p N F as a function of an inverse matrix of R, which in general is non-convex on the variable R. To overcome this non-linearity, we explicitly introduce p NF as an auxiliary optimization variable. The only constraint we need for the variable p NF is Eq. [START_REF] Zhu | Coded caching with joint content recommendation and user grouping[END_REF]. To express this constraint as a linear equation, we first multiply both sides with the term Iα N • R and write:

p NF - α N • p NF • R = (1 -α) • p (d) (8)
Since Eq. ( 8) involves products of the variables p NF • R (i.e., a quadratic term), we substitute the optimization variables r ij with the new auxiliary variables w ij , where r ij = wij p N F i . This substitution is possible because p N F i > 0 for the cases of interest, as stated in the following corollary (whose proof follows by observing Eq. ( 8)) .

Corollary 1. p N F i > 0, ∀i ∈ K, for α ∈ (0, 1) and p (d) > 0.

Having introduced the new auxiliary variables, it is easy to show how the constraints of Eq. ( 6) are derived, by substituting

r ij = wij p N F i , as follows: Eq. (6b) ⇔ p N F j - α N • i∈K p N F i • r ij = (1 -α) • p d i (9a) Eq. (6c) ⇔ j∈K r ij • u ij ≥ q • q BS i (9b) Eq. (6d) ⇔ j∈K r ij = N, r ii = 0 (9c) Eq. (6e) ⇔ r ij ≤ 1, r ij ≥ 0 (9d)
where Eq. (9a) is equivalent to Eq. ( 8) (and guarantees that p NF is a stationary distribution for R), Eq. (9b) is the QoR constraint, and Eq. (9c) and Eq. (9d) are constraints on the recommendation variables.

Up to now, we have transformed all the constraints, apart from the fairness constraint F (p BS , p NF ) ≤ c f . In the following, we transform the fairness constraint in a set of linear constraints S(z, p NF ) for each fairness metric of Section II-B. F-max. In the case of F max the fairness constraint is

F max (p NF , p BS ) = max i∈K {|p N F i -p BS i |} ≤ c f (10)
Eq. ( 10) is not a linear inequality. However, it can be expressed as the intersection of the following 2 • K linear inequalities

p BS i -p N F i ≤ c f p N F i -p BS i ≤ c f ∀ i ∈ K (11)
where we first set |p N F i -p BS i | ≤ c f ∀i ∈ K as equivalent to constraining the max, and then substituted each absolute term |x| ≤ c f with two constraints x ≤ c f and -x ≤ c f . F-tv. A similar approach could be applied for the constraint

F tv (p NF , p BS ) = 1 2 • i∈K |p N F i -p BS i | ≤ c f (12)
However, it would lead to 2 K linear inequalities, which is impractical for large catalogs. Hence, we introduce an auxiliary set of variables z ∈ R K (a K-sized vector) and substitute Eq. ( 12) with the following constraints

i∈K z i ≤ c f |p BS i -p N F i | ≤ z i , ∀ i ∈ K (13)
The first constraint is a linear inequality, and the remaining K inequalities of Eq. ( 13) can be substituted with 2 • K linear inequalities similarly to Eq. [START_REF] Qi | Optimizing caching and recommendation towards user satisfaction[END_REF]. F-kl. In the F kl case, the constraint can be written as

F kl = i∈K p BS i • log(p BS i ) -log(p N F i ) ≤ c f (14)
Eq. ( 14) involves a logarithmic function, thus, we cannot proceed as in F max or F tv . We first rewrite Eq. ( 14) as

i∈K p BS i log(p N F i ) ≥ -c f -i∈K p BS i log(p BS i ) (15
) where we remind that p N F i are optimization variables and p BS i are given constants. Then, we introduce an auxiliary set of K variables z ∈ R K , and we demand the following K + 1 inequalities which are equivalent to Eq. ( 15)

i∈K p BS i • z i ≥ -c f -i∈K p BS i log(p BS i ) log(p N F i ) ≥ z i , ∀ i ∈ K (16)
The first inequality of Eq. ( 16) is linear. The remaining K inequalities are nonlinear due to the presence of the logarithm.

To transform them to linear constraints, we approximate the logarithm with a general family of linear cuts. Specifically, we define M lines for every i, as f (p network gains. A similar issue is addressed in [START_REF] Liu | Personalizing fairness-aware re-ranking[END_REF], from a multi-stakeholders perspective.

N F i ) = a m,i •p N F i +b m,i

VIII. CONCLUSION

Previous works have shown that NFR can bring significant gains for the network, however, without considering the fairness, which is a key factor for content providers. This work is the first to study the dimension of fairness in NFR, and explore the trade-offs between controlling fairness and increasing network gains. Our results show that fairness need and can be taken into account in NFR, while the price (wrt. network cost) that one has to pay to impose fairness is small.

We believe that the findings of this paper can motivate further research on fairness in NFR. For example, under NFR schemes that jointly select the recommendation and network policies, we expect a more aggressive shaping of the demand. Hence, it is of interest to investigate if, and how the introduced unfairness and the trade-offs change under such schemes. In terms of fairness notions, an extension can be towards group fairness [START_REF] Sacharidis | A common approach for consumer and provider fairness in recommendations[END_REF], [START_REF] Xiao | Fairness-aware group recommendation with pareto-efficiency[END_REF], where the contents belong to classes (e.g., of the same genre or producer) [START_REF] Liu | Personalizing fairness-aware re-ranking[END_REF], [START_REF] Mehrotra | Towards a fair marketplace: Counterfactual evaluation of the trade-off between relevance, fairness & satisfaction in recommendation systems[END_REF], and the fairness is defined among the aggregate demand of content classes. This more relaxed fairness metric, probably allows more flexibility in the decisions of the NF-RS and, thus, higher network gains.

APPENDIX: PROOF OF THEOREM 1

The bound for the network gain G vs. fairness F trade-off is given by the solution of the optimization problem

max p NF G s.t. F ≤ c F ( 17
)
where G is defined in Eq. ( 2), F is the fairness metrics (such as the F max , F tv , F kl of Section II-B), c F a constant, and p NF has to be a probability distribution. F-max. For the network gain it holds that

G ≤ i∈C |p N F i -p BS i | ≤ C • max j∈K |p N F j -p BS j | = C • Fmax
where the first inequality follows by applying the property x ≤ |x| to the terms in the expression of G (Eq. ( 2)), the second inequality holds because |p N F i -p BS i | ≤ max j∈K |p N F j -p BS j |, ∀i ∈ C, since C ⊂ K, and in the last equality we simply substituted from the definition of F max (Section II-B). F-tv. Starting similarly to the F max case, we get

G ≤ i∈C |p N F i -p BS i | = 2 • Ftv - i∈K\C |p N F i -p BS i | (18)
where the equality follows from the definition of F tv . The right hand side of Eq. ( 18) increases when i∈K\C |p N F i -p BS i | decreases. The min value of this term can be calculated as:

i∈K p BS i = i∈K p N F i ⇒ i∈K\C (p BS i -p N F i ) = i∈C (p N F i -p BS i ) ⇒ i∈K\C |p BS i -p N F i | ≥ G (19)
where in the first equation both sums equal to 1 (probability distributions), the second equation follows by moving all terms for i ∈ K\C to the left hand side, and in the third equation the left hand side follows from the property x ≤ |x| and the right hand side directly from the definition of G (Eq. ( 2)). Substituting Eq. ( 19) in Eq. [START_REF] Giannakas | Soba: Session optimal mdp-based network friendly recommendations[END_REF] gives

G ≤ 2 • Ftv -G ⇒ G ≤ Ftv
F-kl. Due to the logarithm involved in the expression of F kl , we cannot proceed similarly to the cases of F max or F tv , and we calculate the bound by solving the optimization problem of Eq. ( 17) with the method of Lagrangian multipliers. We first formulate the Lagrangian function L as follows 5

L = i∈C (p N F i -p BS i ) -λ • (F kl -c f ) -µ • i∈K p N F i -1
The derivative of L with respect to p N F i is

∂L ∂p N F i =      1 + λ • p BS i p N F i -µ , i ∈ C λ • p BS i p N F i -µ , i ∈ K\C (20)
where we calculate ∂F kl ∂p N F i = -

p BS i p N F i (see F kl definition;
Sec. II-B). Setting ∂L ∂p N F i = 0 for the optimal solution, gives:

p N F i = λ µ-1 • p BS i , i ∈ C λ µ • p BS i , i ∈ K\C (21)
To calculate the Lagrange multipliers, we use the definition of G (Eq. ( 2)), substitute from Eq. ( 21), and get

G = i∈C λ µ -1 p BS i -p BS i ⇒ λ µ -1 = 1 + G i∈C p BS i = 1 + G H (22)
where for brevity we denoted H = CHR BS = i∈C p BS i . Then we consider the constraint i∈K p N F i = 1 and substituting from the expressions in Eq. ( 21) and Eq. ( 22) we get

i∈C 1 + G H • p BS i + i∈K\C λ µ • p BS i = 1 ⇒ 1 + G H • i∈C p BS i + λ µ • i∈K\C p BS i = 1 ⇒ 1 + G H • H + λ µ • (1 -H) = 1 ⇒ λ µ = 1 - G 1 -H (23)
where we used i∈K\C p BS i = 1 -i∈C p BS i = 1 -H. Now, substituting from Eq. ( 21), Eq. ( 22) and Eq. ( 23), in the expression for the F kl , gives

F kl = i∈C p BS i • log   p BS i 1 + G H p BS i   + i∈K\C p BS i • log   p BS i 1 -G 1-H p BS i   = - i∈C p BS i • log 1 + G H - i∈K\C p BS i • log 1 - G 1 -H = -H • log 1 + G H -(1 -H) • log 1 - G 1 -H (24)
The above equality holds for the optimal p NF , i.e., the maximum network gain G; for any other p NF the gains will be lower, which makes the above the inequality of Theorem 1. 5 The problem Eq. ( 17) involves also the constraints 0 ≤ p N F i ≤ 1, ∀i ∈ K, which need to be accounted in the Lagrangian. However, if p N F i is 0 or 1, the F kl diverges and thus the constraint in Eq. ( 17) is not satisfied. Hence, for any feasible solution it will hold that 0 < p N F i < 1 and the corresponding Lagrange multipliers will be equal to zero (Karush-Kuhn-Tucker conditions).

Fig. 1 :

 1 Fig. 1: (a) CDF of unfairness created by the NF-RS algorithms in all scenarios (TableII). (b) Unfairness vs. QoR, in Movielens scenarios with α=0.8, N =5, C=10, uniform p(d) , Greedy (continuous lines) and Multi-step (dashed lines) NF-RS.

Figure 1 (

 1 b) presents the resulting unfairness (y-axis) by applying the Greedy NF-RS (continuous lines) and the Multi-step NF-RS (dashed lines) in scenarios

Fig. 2 :

 2 Fig. 2: (a),(b),(c): Network gain G (y-axis) vs. fairness metric F (x-axis) in all scenarios of Table II with C = 10, and under the Greedy (circles), Multi-step (crosses), CABaRet (triangles) NF-RS. The bounds are denoted with dashed lines. (d): CDF of the relative distance F -min F min F of the operating points (F, G) of the NF-RS algorithms from the corresponding bounds (min F, G).

Fig. 3 :

 3 Fig.3: The price of fairness: Comparison of the performance (fairness at x-axis vs. CHR at y-axis) of the Fair NF-RS (continuous lines) with other RS (markers) and the bounds (dashed lines). Red colors correspond to the LastFM dataset scenario and blue colors to the Movielens dataset scenario, with parameters α=0.99, N =2, q=0.9, C=5 (LastFM) and C=10 (Movielens).

TABLE I :

 I Important notation.

	K	content catalog (|K| = K)
	p i	demand for content i; p = [p 1 , ..., p K ] and i∈K p i =1
	C	set of cached contents (|C| = C)
	CHR	cache hit rate, CHR = i∈C p i
	u ij	recommendation score, u ij ∈ [0, 1]
	R i	list of recommendations after content i
	N	number of recommendations.
	α	probability a user to follow a recommendation
	p	(d) i

TABLE III :

 III Relation between system parameters, fairness F and network gain G: monotonicity and correlation (ρ).

		Fmax	Ftv	F kl	G
	q	(ρ=-0.40)	(ρ=-0.38)	(ρ=-0.30)	(ρ=-0.42)
	α	(ρ=0.46)	(ρ=0.81)	(ρ=0.75)	(ρ=0.69)
	N	(ρ=-0.47)	(ρ=-0.13)	(ρ=-0.16)	(ρ=-0.20)
	C	(ρ=-0.13)	-(ρ=0.06)	-(ρ=0.03)	(ρ=0.18)

This research is co-financed by Greece and the European Union (European Social Fund-ESF) through the Operational Programme "Human Resources Development, Education and Lifelong Learning" in the context of the project "Reinforcement of Postdoctoral Researchers -2nd Cycle" (MIS-5033021) implemented by the State Scholarships Foundation (IKY), and the Operational Program Competitiveness, Entrepreneurship and Innovation under the call RESEARCH-CREATE-INNOVATE (project T2EDK-04937). It is also funded by the ANR (French National Agency of Research) by the "FairEngine" project under grant ANR-19-CE25-0011, by the ANR "5C-for-5G" project under grant ANR-17-CE25-0001, and the IMT F&R, "Joint Optimization of Mobile Content Caching and Recommendation" project.

Note that, since we aim to capture the fairness in recommendations, we use metrics from the RS field. Other fairness measures from other fields, e.g., resource allocation[START_REF] Lan | An axiomatic theory of fairness in network resource allocation[END_REF], would be less relevant.

We note that CawR[START_REF] Chatzieleftheriou | Jointly optimizing content caching and recommendations in small cell networks[END_REF] optimizes at the same time the caching and recommendation policies. Since the scope of this paper is on the fairness of the recommendations in NF-RS, we focus on the resulting recommendations of NF-RS algorithms, given a pre-filled cache; we discuss implications of joint NF-RS and caching policy optimization algorithms in Section VIII.

Note that some of the scenarios/markers in Fig.2(c) (F kl case) correspond to different values CHR BS (e.g., due to different p BS distributions), and thus different bounds. In favor of readability, we avoid depicting several bounds and show only the worst-case bound among those scenarios; i.e., for some scenarios/markers the bound is tighter than the depicted bound.

There are NF-RS algorithms that select also the network policy, e.g., caching[START_REF] Sermpezis | Soft cache hits: Improving performance through recommendation and delivery of related content[END_REF],[START_REF] Zhu | Coded caching with joint content recommendation and user grouping[END_REF]-[START_REF] Costantini | Approximation guarantees for the joint optimization of caching and recommendation[END_REF]. While our framework can be generalized in this direction, this is out of the scope of this paper (see also discussion in Section VIII).

for every dimension i ∈ K, these tangent lines can be straightforwardly calculated. Thus, instead of using the K nonlinear inequalities of Eq. ( 16), we use the following M • K inequalities that are linear on the variables z i and p N F i z i ≤ e (m-1)•s • p N F i -(m -1)s -1, ∀i ∈ K, m ∈ {1, ..., M } Remark: The sampling step s and the number of linear cuts M , play a major role in the optimization process. s that is small enough for dense sampling, and an M according to the size of the catalog. In our scenarios, we found that s = 0.05 and M = 160 suffices for a catalog of K ≈ 1000 contents.

VI. THE PRICE OF FAIRNESS

In this section, we employ the Fair NF-RS of Section V to the simulation setup of Section III-A. We consider different values for the fairness constraints c f , and in Fig. 3 we present the performance, i.e., the achieved CHR (y-axis) of the Fair NF-RS (continuous lines) vs. the resulting unfairness (x-axis). We present two indicative scenarios for the LastFM/Movielens datasets (red/blue color). Also, we present the bound for each scenario (dash lines), the operating points {unfairness, CHR} of the BS-RS (star markers) and the NF-RS schemes that do not consider fairness (star, cross, and hexagonal markers for the Greedy, Multi-step, and CABaRet NF-RS, respectively).

Below we discuss the main findings stemming from Fig. 3, which provide useful insights for the effect of imposing fairness in NFR and the price we have to pay for this. Key finding 1: "The Fair NF-RS always achieves a better performance trade-off than other NF-RS algorithms"

The first observation that verifies the correctness of the proposed approach is that the Fair NF-RS performs better than other NF-RS (both in fairness and network gains), i.e., the curve of the Fair NF-RS is above (higher CHR) and/or on the left (less unfairness) of the markers that indicate the operation points of the other NF-RS algorithms. Extending the Fair NF-RS curve towards (i) small values of F (x-axis) leads to the operating point of the BS-RS (F = 0), and (ii) large values of F leads to the operating point of the Multi-step NF-RS, which is equivalent to the Fair NF-RS without fairness constraint. Key finding 2: "By allowing a little unfairness, high network gains can be achieved"

Comparing the Fair NF-RS performance with this of the BS-RS, we see that the increase in the network gains is steep for a small relaxation in the unfairness (i.e., for small values in the x-axis). In fact, we can see that the curve of the Fair NF-RS coincides with the bound, which means that the optimal fairness-gains trade-off is achievable by the Fair NF-RS for small values of fairness constraints. This is a promising message for the practical feasibility of the NFR framework: significant network gains are possible even when a level of fairness is required by the content provider. Key finding 3: "The price (wrt. the network gain) of imposing fairness is small" Moving our attention on the other side of the Fair NF-RS curve (i.e., for higher values of F ), two interesting observations can be made: (i) the curve of the Fair NF-RS is concave, and (ii) the gains in CHR diminish for large values of F . These findings show that similar network gains to the Multi-step NF-RS (which achieves the best performance under no fairness constraints) can be achieved with much less unfairness. In particular in the case of F max that captures the individual fairness, this behavior is clearer: a CHR very close to the highest possible can be achieved by the Fair NF-RS even with 3 times lower F max compared to the Multi-step NF-RS .

Moreover, we can see that while the bounds are linear in the case of F max and F tv , the curve of the Fair NF-RS is concave: this is a positive finding indicating that the Fair NF-RS stays close to the bound and deviates for it only when large values of unfairness are allowed. Even in the case of F kl where the bound is also concave, the Fair NF-RS curve approaches the highest possible CHR with a faster rate.

VII. RELATED WORK

NFR. The paradigm of network-friendly (or, network-aware) recommendations has been recently proposed and studied under different network setups and content services [1]- [START_REF] Kastanakis | Cabaret: Leveraging recommendation systems for mobile edge caching[END_REF], [START_REF] Zhu | Coded caching with joint content recommendation and user grouping[END_REF]- [START_REF] Lin | Content pushing over multiuser miso downlinks with multicast beamforming and recommendation: A cross-layer approach[END_REF], [START_REF] Sermpezis | Towards qos-aware recommendations[END_REF]- [START_REF] Munaro | Content recommendation and service costs in swarming systems[END_REF]. The proposed NFR schemes aim to increase the network gains (and/or improve the quality of content delivery) by selecting recommendations [START_REF] Giannakas | Show me the cache: Optimizing cache-friendly recommendations for sequential content access[END_REF], [START_REF] Kastanakis | Cabaret: Leveraging recommendation systems for mobile edge caching[END_REF], [START_REF] Giannakas | The order of things: Position-aware network-friendly recommendations in long viewing sessions[END_REF], [START_REF] Krishnappa | Cache-centric video recommendation: an approach to improve the efficiency of youtube caches[END_REF] or by jointly designing the recommendation and network policy (e.g., caching) [START_REF] Chatzieleftheriou | Caching-aware recommendations: Nudging user preferences towards better caching performance[END_REF], [START_REF] Sermpezis | Soft cache hits: Improving performance through recommendation and delivery of related content[END_REF], [START_REF] Zhu | Coded caching with joint content recommendation and user grouping[END_REF]- [START_REF] Qi | Optimizing caching and recommendation towards user satisfaction[END_REF], [START_REF] Chatzieleftheriou | Joint user association, content caching and recommendations in wireless edge networks[END_REF]- [START_REF] Lin | Content pushing over multiuser miso downlinks with multicast beamforming and recommendation: A cross-layer approach[END_REF]. The majority of related works considers cache-friendly recommendations in mobile networks [START_REF] Spyropoulos | Soft cache hits and the impact of alternative content recommendations on mobile edge caching[END_REF]- [START_REF] Giannakas | Show me the cache: Optimizing cache-friendly recommendations for sequential content access[END_REF], [START_REF] Zhu | Coded caching with joint content recommendation and user grouping[END_REF]- [START_REF] Costantini | Approximation guarantees for the joint optimization of caching and recommendation[END_REF]. However, the same principles apply to generic network setups [START_REF] Giannakas | The order of things: Position-aware network-friendly recommendations in long viewing sessions[END_REF], such as coded caching [START_REF] Zhu | Coded caching with joint content recommendation and user grouping[END_REF], broadcast communications [START_REF] Lin | Joint pushing and recommendation for susceptible users with time-varying connectivity[END_REF]- [START_REF] Lin | Content pushing over multiuser miso downlinks with multicast beamforming and recommendation: A cross-layer approach[END_REF], user association to base stations [START_REF] Chatzieleftheriou | Joint user association, content caching and recommendations in wireless edge networks[END_REF], or swarming systems [START_REF] Munaro | Content recommendation and service costs in swarming systems[END_REF]. While some of the proposed schemes take into account the user perspective by accounting the QoR, none of them has considered the fairness in recommendations from the perspective of the content provider. In this context, our work studies the dimension of fairness, thus providing a more complete view of the NFR paradigm. The proposed Fair NF-RS retains the efficiency of previous NFR schemes for achieving high network gains, while reduces the unfairness.

Fairness in RS.

A variety of fairness metrics are used by the RS community [START_REF] Abdollahpouri | Multi-stakeholder recommendation and its connection to multi-sided fairness[END_REF]- [START_REF] Liu | Personalizing fairness-aware re-ranking[END_REF] to capture different notions and needs of the content providers. Moreover, the fairness in RS can be defined with respect to the consumer (c-fairness) or the provider (p-fairness) [START_REF] Abdollahpouri | Multi-stakeholder recommendation and its connection to multi-sided fairness[END_REF], [START_REF] Burke | Multisided fairness for recommendation[END_REF]. The former is typically used to design recommendation algorithms whose output is independent of sensitive user traits, e.g., race or gender [START_REF] Burke | Multisided fairness for recommendation[END_REF], [START_REF] Edizel | Fairecsys: Mitigating algorithmic bias in recommender systems[END_REF]. In other words, c-fairness aims to capture discrimination between users. Hence, it is orthogonal to our study, e.g., it could be considered as a part of the BS-RS and depends on the recommendation scores u ij for which we consider a generic definition. The notion of p-fairness, which we use in this paper, aims to capture potential discrimination of the content provider towards different content producers/owners (or, individual contents). The proposed Fair NF-RS provides recommendations that achieve a balance between the user satisfaction (QoR), the content provider (fairness), and the