• xmlui.mirage2.page-structure.header.title
    • français
    • English
  • Help
  • Login
  • Language 
    • Français
    • English
View Item 
  •   BIRD Home
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Publications
  • View Item
  •   BIRD Home
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Publications
  • View Item
JavaScript is disabled for your browser. Some features of this site may not work without it.

Browse

BIRDResearch centres & CollectionsBy Issue DateAuthorsTitlesTypeThis CollectionBy Issue DateAuthorsTitlesType

My Account

LoginRegister

Statistics

Most Popular ItemsStatistics by CountryMost Popular Authors
Thumbnail

Fairness in Influence Maximization through Randomization

Becker, Ruben; D'Angelo, Gianlorenzo; Ghobadi, Sajjad; Gilbert, Hugo (2021), Fairness in Influence Maximization through Randomization, Thirty-Fifth AAAI Conference on Artificial Intelligence, AAAI 2021, 2021-02

View/Open
2010.03438.pdf (890.7Kb)
Type
Communication / Conférence
Date
2021
Conference title
Thirty-Fifth AAAI Conference on Artificial Intelligence, AAAI 2021
Conference date
2021-02
Metadata
Show full item record
Author(s)
Becker, Ruben
D'Angelo, Gianlorenzo
Ghobadi, Sajjad
Gilbert, Hugo
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Abstract (EN)
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 this paper, we propose to use randomization as a mean for achieving fairness. Similar to previous works like Fish et al. (WWW '19) and Tsang et al. (IJCAI '19), we study the maximin criterion for (group) fairness. In contrast to their work however, we model the problem in such a way that, when choosing the seed sets, probabilistic strategies are possible rather than only deterministic ones. We introduce two different variants of this probabilistic problem, one that entails probabilistic strategies over nodes (node-based problem) and a second one that entails probabilistic strategies over sets of nodes (set-based problem). While the original deterministic problem involving the maximin criterion has been shown to be inapproximable, interestingly, we show that both probabilistic variants permit approximation algorithms that achieve 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 multiplicative-weight routines for both problems and compare the achieved fairness values to existing methods. Maybe non-surprisingly, we show that the ex-ante values of the computed probabilistic strategies are significantly larger than the (ex-post) fairness values of previous methods. This indicates that studying fairness via randomization is a worthwhile path to follow. Interestingly and maybe more surprisingly, we observe that even the ex-post fairness values computed by our routines, dominate over the fairness achieved by previous methods on most of the instances tested.
Subjects / Keywords
Fairness

Related items

Showing items related by title and author.

  • Thumbnail
    Fairness in Influence Maximization through Randomization 
    Becker, Ruben; d'Angelo, Gianlorenzo; Ghobadi, Sajjad; Gilbert, Hugo (2022) Article accepté pour publication ou publié
  • Thumbnail
    Influence Maximization With Co-Existing Seeds 
    Becker, Ruben; D'Angelo, Gianlorenzo; Gilbert, Hugo (2021) Communication / Conférence
  • Thumbnail
    Group-Harmonic and Group-Closeness Maximization – Approximation and Engineering 
    Angriman, Eugenio; Becker, Ruben; D'Angelo, Gianlorenzo; Gilbert, Hugo; van der Grinten, Alexander; Meyerhenke, Henning (2021) Communication / Conférence
  • Thumbnail
    Unveiling the Truth in Liquid Democracy with Misinformed Voters 
    Becker, Ruben; D’Angelo, Gianlorenzo; Delfaraz, Esmaeil; Gilbert, Hugo (2021) Communication / Conférence
  • Thumbnail
    Computation and Bribery of Voting Power in Delegative Simple Games 
    d'Angelo, Gianlorenzo; Delfaraz, Esmaeil; Gilbert, Hugo (2022) Communication / Conférence
Dauphine PSL Bibliothèque logo
Place du Maréchal de Lattre de Tassigny 75775 Paris Cedex 16
Phone: 01 44 05 40 94
Contact
Dauphine PSL logoEQUIS logoCreative Commons logo