Efficiency versus fairness in link recommendation algorithms

We investigate algorithmic fairness in a model of network formation governed by recommendation algorithms. The model defines a Markov chain over network configurations, which converges towards a class of efficient networks where each agent maximizes its utility. In this setting, we measure the efficiency of a recommendation algorithm via the speed at which it reaches the recurrent class of efficient networks. We propose a micro-founded measure of fairness that coincides with the entropy of the invariant distribution associated to this Markov chain. We develop analytical and numerical methods for the computation of efficiency and fairness. We find a strong relationship between the structure of users' preferences and the properties of recommendation algorithms. In particular, we show that there is a trade-off between efficiency and fairness as the hierarchical recommendation algorithms that ensure fast convergence to efficient networks are also those that lead to high level of unfairness. We put forward a simple solution to this trade-off where the designer adapts the recommendation algorithm to the different phases of the network formation process