Fairness in Influence Maximization through Randomization

Authors

  • Ruben Becker Gran Sasso Science Institute
  • Gianlorenzo D'Angelo Gran Sasso Science Institute
  • Sajjad Ghobadi Gran Sasso Science Institute
  • Hugo Gilbert Université Paris-Dauphine, Université PSL, CNRS, LAMSADE

Keywords:

Networks and Social Networks, Social Welfare, Justice, Fairness and Equality

Abstract

The influence maximization paradigm has been used by researchers in various fields in order to study how information spreads in social networks. While previously the attention was mostly on efficiency, more recently fairness issues have been taken into account in this scope. In the present paper, we propose to use randomization as a mean for achieving fairness. While this general idea is not new, it has not been applied in the area of information spread in networks. Similar to previous works like Fish et al. (WWW '19) and Tsang et al. (IJCAI '19), we study the maximin criterion for (group) fairness. By allowing randomized solutions, we introduce two different variants of this problem. While the original deterministic maximin problem has been shown to be inapproximable, interestingly, we show that both probabilistic variants permit approximation algorithms with a constant multiplicative factor of 1-1/e plus an additive arbitrarily small error that is due to the simulation of the information spread. For an experimental study, we provide implementations of our methods and compare the achieved fairness values to existing methods. Non-surprisingly, the ex-ante values, i.e., minimum expected value of an individual (or group) to obtain the information, of the computed probabilistic strategies are significantly larger than the (ex-post) fairness values of previous methods. This confirms that studying fairness via randomization is a worthwhile direction. More surprisingly, we observe that even the ex-post fairness values, i.e., fairness values of sets sampled according to the probabilistic strategies, computed by our routines dominate over the fairness achieved by previous methods on most of the instances tested.

Downloads

Published

2021-05-18

How to Cite

Becker, R., D’Angelo, G., Ghobadi, S., & Gilbert, H. (2021). Fairness in Influence Maximization through Randomization. Proceedings of the AAAI Conference on Artificial Intelligence, 35(17), 14684-14692. Retrieved from https://ojs.aaai.org/index.php/AAAI/article/view/17725

Issue

Section

AAAI Special Track on AI for Social Impact