Minimisation Approximative du Regret Bisubmodulaire dans la Publicité sur Panneaux d'Affichage et les Réseaux Sociaux

Informations Fondamentales

• ID de l'article : 2510.09084
• Titre : Approximately Bisubmodular Regret Minimization in Billboard and Social Media Advertising
• Auteurs : Dildar Ali, Suman Banerjee, Yamuna Prasad (Indian Institute of Technology Jammu)
• Classification : cs.GT (Théorie des Jeux), cs.DB (Bases de Données), cs.DS (Structures de Données et Algorithmes)
• Date de publication : Octobre 2025 (prépublication arXiv)
• Lien de l'article : https://arxiv.org/abs/2510.09084

Résumé

Cet article étudie le problème de minimisation du regret dans un environnement publicitaire multimodal, où les fournisseurs d'influence doivent allouer simultanément des créneaux publicitaires et des nœuds germes de réseaux sociaux à plusieurs annonceurs. Les auteurs proposent un nouveau modèle d'effets d'interaction pour capturer les effets individuels et combinés de deux médias publicitaires distincts, et conçoivent deux solutions : la méthode du gradient projeté (PGM) et la recherche locale bisubmodulaire approximative (ABLS). Les expériences démontrent que les méthodes proposées réduisent efficacement le regret total dans diverses configurations de demande.

Contexte et Motivation de la Recherche

Définition du Problème

1. Problème central : Comment un fournisseur d'influence peut-il allouer conjointement les ressources entre la publicité sur panneaux d'affichage et les réseaux sociaux pour minimiser le regret total ?
2. Scénarios pratiques : Les entreprises commerciales soumettent des propositions quotidiennes aux fournisseurs d'influence contenant des exigences d'influence, couvrant les modes en ligne et hors ligne, avec des paiements conditionnels basés sur la satisfaction des exigences

Importance de la Recherche

• Les entreprises commerciales consacrent généralement 7 à 10 % de leurs revenus annuels à la publicité
• Les recherches existantes se concentrent principalement sur la perspective des annonceurs, manquant l'optimisation conjointe du point de vue des fournisseurs d'influence
• Les approches traditionnelles ignorent les effets d'interaction entre la publicité sur panneaux d'affichage et les réseaux sociaux

Limitations des Méthodes Existantes

• La littérature existante traite séparément les modèles de regret pour la publicité sur panneaux d'affichage et les réseaux sociaux
• Absence d'un cadre unifié considérant les effets d'interaction entre les deux modes publicitaires
• Les modèles de regret existants ne sont ni monotones ni submodulaires, rendant les garanties de performance inatteignables

Contributions Principales

1. Modélisation conjointe pionnière : Propose le problème de minimisation du regret considérant simultanément la publicité sur panneaux d'affichage et les réseaux sociaux
2. Analyse théorique : Démontre que le problème est NP-difficile et non approximable dans tout facteur constant
3. Conception d'algorithmes : Propose deux solutions : la méthode du gradient projeté (PGM) et la recherche locale bisubmodulaire approximative (ABLS)
4. Modèle d'effets d'interaction : Formalise mathématiquement les effets d'interaction entre les panneaux d'affichage et les réseaux sociaux
5. Validation expérimentale : Vérifie l'efficacité des méthodes sur des ensembles de données réelles

Explication Détaillée des Méthodes

Définition de la Tâche

Entrées :

• Ensemble de créneaux publicitaires BS = {bs₁, bs₂, ..., bsₘ}
• Ensemble de nœuds germes du réseau social P = {p₁, p₂, ..., pᵣ}
• Ensemble d'annonceurs A = {a₁, a₂, ..., aₙ}, chaque annonceur ayant une exigence d'influence σᵢ et un budget Kᵢ

Sorties :

• Schéma d'allocation L = {(S₁,P₁), (S₂,P₂), ..., (Sₙ,Pₙ)} minimisant le regret total

Contraintes :

• Contrainte d'exclusivité mutuelle : les allocations de différents annonceurs ne peuvent pas se chevaucher
• Contrainte budgétaire : le coût d'allocation ne peut pas dépasser le budget de l'annonceur

Modèle Principal

1. Modèle d'Influence

Φ(S,P) = I(S) + IG(P) + Ψ(S,P)

Où :

• I(S) : influence de l'ensemble de créneaux publicitaires S
• IG(P) : influence de l'ensemble de nœuds germes P
• Ψ(S,P) : effet d'interaction

2. Modèle d'Effets d'Interaction

Ψ(S,P) = ρ · Σᵤ∈U (1 - ∏ᵦ∈S(1 - Pr(u,b))) · Σᵥ∈P Pr'(u,v)

Où ρ ∈ 0,1 contrôle l'intensité de l'interaction

3. Modèle de Regret

R(Naᵢ) = Kaᵢ · (1 - γ · min(Φ(Saᵢ,Paᵢ),σaᵢ)/σaᵢ) + δ · log(1 + |Saᵢ| + |Paᵢ|)

Conception d'Algorithmes

1. Méthode du Gradient Projeté (PGM)

• Méthode d'optimisation continue basée sur l'extension de Lovász
• Utilise des vecteurs fractionnaires pour représenter la sélection souple de créneaux et de germes
• Mise à jour itérative par descente de sous-gradient et étapes de projection
• Complexité temporelle : O(T·m³·n·r·t + Tm²·n·r²·t + m⁴·n·r·t + m³·n·r²·t + m²·n·r³·t)

2. Recherche Locale Bisubmodulaire Approximative (ABLS)

• Méthode de recherche locale gourmande
• Classe les annonceurs par ordre décroissant du ratio demande-budget
• Sélectionne les éléments avec la plus grande réduction de regret par unité d'influence
• Complexité temporelle : O(m·r²·t + m²·r·t)

Points d'Innovation Technique

1. Bisubmodularité ε-approximative : Extension des fonctions bisubmodulaires traditionnelles permettant un écart borné
2. Cadre unifié : Première modélisation unifiée de la publicité sur panneaux d'affichage et des réseaux sociaux
3. Quantification des effets d'interaction : Fournit une méthode mathématique pour calculer les effets d'interaction
4. Garanties théoriques : Fournit des limites de performance pour les fonctions bisubmodulaires approximatives

Configuration Expérimentale

Ensembles de Données

1. Données de trajectoire : Données d'enregistrement Foursquare (avril 2012 - janvier 2014)
   • 124 539 enregistrements, 51 318 utilisateurs uniques
   • Couvre les principales villes américaines
2. Données de réseau social : Instantané du réseau social des utilisateurs
   • Ancien réseau : 95 994 relations d'amitié
   • Nouveau réseau : 129 864 relations d'amitié
3. Données de panneaux d'affichage : Ensemble de données LAMAR
   • New York : 716 panneaux d'affichage, 1 031 040 créneaux
   • Los Angeles : 1 483 panneaux d'affichage, 2 135 520 créneaux

Métriques d'Évaluation

• Regret total : Somme des regrets de tous les annonceurs
• Nombre d'annonceurs satisfaits : Nombre d'annonceurs dont les exigences sont satisfaites
• Temps de calcul : Temps d'exécution de l'algorithme

Méthodes de Comparaison

• Allocation Aléatoire (RA) : Sélection aléatoire de créneaux publicitaires et de nœuds germes
• Allocation Top-k : Sélection des k créneaux publicitaires et nœuds germes les plus influents

Paramètres Clés

Résultats Expérimentaux

Résultats Principaux

1. Performance dans Différents Scénarios de Demande

Cas 1 (α faible, λ faible) : α ≤ 80%, λ ≤ 2%

• PGM et ABLS surpassent significativement les méthodes de base
• Plus grand nombre d'annonceurs satisfaits
• Réduction du regret de 30-40%

Cas 2 (α faible, λ élevé) : α ≤ 80%, λ ≥ 5%

• Suroffre réduite avec demandes individuelles élevées
• Les méthodes proposées conservent leur avantage
• Réduction du regret de 25-35%

Cas 3 (α élevé, λ faible) : α ≥ 100%, λ ≤ 2%

• Insuffisance d'offre entraînant un regret global accru
• PGM et ABLS restent supérieurs aux méthodes de base
• Réduction du regret de 15-25%

Cas 4 (α élevé, λ élevé) : α ≥ 100%, λ ≥ 5%

• Toutes les méthodes font face à un regret plus élevé
• Peu d'annonceurs à forte demande moins avantageux que de nombreux annonceurs à faible demande

2. Analyse de l'Efficacité Computationnelle

• ABLS présente généralement un temps de calcul plus court
• PGM présente une surcharge computationnelle significative avec un nombre accru d'annonceurs
• Le temps de calcul de toutes les méthodes augmente avec le ratio demande-offre α

3. Analyse de Sensibilité aux Paramètres

• Augmentation de ε : Temps d'exécution réduit mais regret augmenté
• Augmentation de δ : Pénalise les allocations volumineuses, entraînant des solutions compactes mais moins efficaces
• Augmentation de γ : Souligne la satisfaction des exigences, échangeant une utilisation accrue des ressources contre un regret réduit
• Augmentation de ρ : Augmente l'intensité d'interaction entre panneaux d'affichage et nœuds germes

Expériences d'Ablation

1. Impact des effets d'interaction :
   • Le regret total diminue de 341,37 à 295,14 en considérant les effets d'interaction
   • Démontre l'importance de la modélisation des effets d'interaction
2. Impact des paramètres de probabilité :
   • Le paramétrage de probabilité trivalent montre les meilleures performances
   • Simule mieux les variations d'influence entre individus dans la réalité

Tests d'Extensibilité

• Scénario à grande échelle : λ = 1%, |A| = 100
• Scénario à petite échelle : λ = 20%, |A| = 5
• PGM et ABLS surpassent les méthodes de base dans les deux scénarios

Travaux Connexes

Recherche sur la Maximisation d'Influence

• Maximisation d'influence dans la publicité sur panneaux d'affichage 6, 33, 36
• Maximisation d'influence dans la publicité sur réseaux sociaux 17, 19, 24
• Problèmes de sélection conjointe d'étiquettes et de créneaux 7

Recherche sur la Minimisation du Regret

• Minimisation du regret dans les réseaux sociaux 13, 30
• Minimisation du regret dans la publicité sur panneaux d'affichage 37
• Minimisation du regret sous contraintes d'influence régionale 2, 4

Contribution de cet Article

Cet article est le premier à étudier la minimisation du regret considérant simultanément la publicité sur panneaux d'affichage et les réseaux sociaux, comblant une lacune dans ce domaine.

Conclusion et Discussion

Conclusions Principales

1. Complexité du problème : Démontre que le problème de minimisation du regret en publicité multimodale est NP-difficile et non approximable
2. Efficacité des algorithmes : PGM et ABLS réduisent efficacement le regret dans diverses configurations
3. Importance des effets d'interaction : Considérer les effets d'interaction entre panneaux d'affichage et réseaux sociaux améliore significativement les résultats
4. Orientations pratiques : De nombreux annonceurs à faible demande sont plus avantageux que peu d'annonceurs à forte demande

Limitations

1. Complexité computationnelle : PGM présente une surcharge computationnelle élevée dans les scénarios à grande échelle
2. Sensibilité aux paramètres : De nombreux paramètres nécessitent un ajustement minutieux
3. Simplification du modèle d'interaction : Le modèle d'effets d'interaction peut ne pas capturer complètement la complexité réelle
4. Configuration statique : Ne considère pas les scénarios avec arrivée dynamique d'annonceurs

Directions Futures

1. Algorithmes en ligne : Développer des algorithmes en ligne traitant l'arrivée dynamique d'annonceurs
2. Optimisation parallèle : Concevoir des cadres d'optimisation parallèles et distribués pour améliorer l'extensibilité
3. Modèles d'interaction plus complexes : Explorer des méthodes de modélisation des effets d'interaction plus précises
4. Autres domaines d'application : Étendre le cadre à d'autres domaines comme l'allocation de ressources informatiques en nuage

Évaluation Approfondie

Avantages

1. Nouveauté du problème : Première étude de la minimisation conjointe du regret en publicité multimodale, avec une importance pratique significative
2. Rigueur théorique : Fournit une analyse théorique complète incluant les preuves de complexité et les garanties d'approximation
3. Innovation méthodologique :
   • Introduit le concept de bisubmodularité ε-approximative
   • Conçoit un modèle mathématique des effets d'interaction
   • Développe deux algorithmes complémentaires
4. Suffisance expérimentale :
   • Utilise des ensembles de données réelles à grande échelle
   • Considère plusieurs configurations de paramètres et scénarios
   • Fournit des expériences d'ablation détaillées et analyses de sensibilité

Insuffisances

1. Limitations du modèle d'interaction : L'hypothèse de combinaison linéaire des effets d'interaction peut être trop simplifiée
2. Efficacité computationnelle : La complexité temporelle élevée de PGM peut poser des défis dans les applications pratiques
3. Dépendance aux paramètres : La performance de l'algorithme est sensible à plusieurs paramètres, nécessitant un ajustement minutieux lors du déploiement
4. Limitations d'évaluation : Manque de comparaison avec davantage de méthodes de base avancées

Impact

1. Contribution académique :
   • Ouvre une nouvelle direction de recherche en optimisation publicitaire multimodale
   • Étend la théorie de l'optimisation submodulaire aux fonctions bisubmodulaires approximatives
   • Fournit une base théorique pour les problèmes d'optimisation connexes
2. Valeur pratique :
   • Directement applicable à l'industrie de la publicité numérique
   • Le cadre est extensible à d'autres problèmes d'allocation de ressources
   • Fournit un outil d'aide à la décision pour les fournisseurs d'influence
3. Reproductibilité : L'article fournit des descriptions d'algorithmes détaillées et des configurations expérimentales facilitant la reproduction

Scénarios d'Application

1. Plateformes de publicité numérique : Applicable aux plateformes devant gérer simultanément les ressources publicitaires en ligne et hors ligne
2. Systèmes d'allocation de ressources : Extensible aux problèmes d'allocation de ressources en informatique en nuage, logistique, etc.
3. Marketing d'influence : Applicable à l'optimisation conjointe du marketing sur réseaux sociaux et de la publicité traditionnelle

Références

L'article cite 37 travaux connexes couvrant plusieurs domaines de recherche incluant la maximisation d'influence, l'optimisation submodulaire et l'allocation publicitaire, fournissant une base théorique solide pour cette recherche.

Évaluation globale : Ceci est un article de recherche de haute qualité qui atteint un bon équilibre entre l'innovation théorique et l'application pratique. Bien que présentant certaines limitations, sa direction de recherche pionnière et sa conception méthodologique rigoureuse lui confèrent une importance académique et une valeur pratique significatives.