Minimización de Arrepentimiento Aproximadamente Bisubmodular en Publicidad en Vallas y Redes Sociales

Información Básica

• ID del Artículo: 2510.09084
• Título: Minimización de Arrepentimiento Aproximadamente Bisubmodular en Publicidad en Vallas y Redes Sociales
• Autores: Dildar Ali, Suman Banerjee, Yamuna Prasad (Instituto Indio de Tecnología Jammu)
• Clasificación: cs.GT (Teoría de Juegos), cs.DB (Bases de Datos), cs.DS (Estructuras de Datos y Algoritmos)
• Fecha de Publicación: Octubre de 2025 (preimpresión en arXiv)
• Enlace del Artículo: https://arxiv.org/abs/2510.09084

Resumen

Este artículo estudia el problema de minimización de arrepentimiento en entornos de publicidad multimodal, donde los proveedores de influencia necesitan asignar simultáneamente espacios en vallas publicitarias y nodos semilla en redes sociales a múltiples anunciantes. Los autores proponen un modelo novedoso de efectos de interacción para capturar los efectos individuales y combinados de dos medios publicitarios distintos, y diseñan dos soluciones: el Método de Gradiente Proyectado (PGM) y la Búsqueda Local Aproximadamente Bisubmodular (ABLS). Los experimentos demuestran que los métodos propuestos reducen efectivamente el arrepentimiento total en diversos escenarios de demanda.

Antecedentes de Investigación y Motivación

Definición del Problema

1. Problema Central: ¿Cómo pueden los proveedores de influencia asignar conjuntamente recursos entre publicidad en vallas y redes sociales para minimizar el arrepentimiento total?
2. Escenarios Prácticos: Las empresas comerciales presentan propuestas diarias a los proveedores de influencia que contienen requisitos de influencia, abarcando modalidades en línea y fuera de línea, con pagos condicionales basados en la satisfacción de requisitos

Importancia de la Investigación

• Las empresas comerciales típicamente dedican el 7-10% de sus ingresos anuales a publicidad
• La investigación existente se enfoca principalmente desde la perspectiva del anunciante, careciendo de optimización conjunta desde la perspectiva del proveedor de influencia
• Los métodos tradicionales ignoran los efectos de interacción entre vallas publicitarias y redes sociales

Limitaciones de Métodos Existentes

• La literatura existente trata por separado los modelos de arrepentimiento para vallas publicitarias y publicidad en redes sociales
• Carece de un marco unificado que considere los efectos de interacción entre dos modalidades publicitarias
• Los modelos de arrepentimiento existentes no son monótonos ni submodulares, lo que hace que las garantías de rendimiento sean inalcanzables

Contribuciones Principales

1. Modelado Conjunto por Primera Vez: Propone el problema de minimización de arrepentimiento considerando simultáneamente publicidad en vallas y redes sociales
2. Análisis Teórico: Demuestra que el problema es NP-difícil e inaproximable dentro de cualquier factor constante
3. Diseño de Algoritmos: Propone dos soluciones: Método de Gradiente Proyectado (PGM) y Búsqueda Local Aproximadamente Bisubmodular (ABLS)
4. Modelo de Efectos de Interacción: Modelado matemático de los efectos de interacción entre vallas publicitarias y redes sociales
5. Verificación Experimental: Valida la efectividad de los métodos en conjuntos de datos reales

Explicación Detallada de Métodos

Definición de Tareas

Entrada:

• Conjunto de espacios en vallas publicitarias BS = {bs₁, bs₂, ..., bsₘ}
• Conjunto de nodos semilla en redes sociales P = {p₁, p₂, ..., pᵣ}
• Conjunto de anunciantes A = {a₁, a₂, ..., aₙ}, cada uno con requisito de influencia σᵢ y presupuesto Kᵢ

Salida:

• Esquema de asignación L = {(S₁,P₁), (S₂,P₂), ..., (Sₙ,Pₙ)} que minimiza el arrepentimiento total

Restricciones:

• Restricción de exclusividad mutua: Las asignaciones de diferentes anunciantes no pueden superponerse
• Restricción de presupuesto: El costo de asignación no puede exceder el presupuesto del anunciante

Modelo Central

1. Modelo de Influencia

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

Donde:

• I(S): Influencia del conjunto de espacios en vallas publicitarias S
• IG(P): Influencia del conjunto de nodos semilla P
• Ψ(S,P): Efecto de interacción

2. Modelo de Efectos de Interacción

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

Donde ρ ∈ 0,1 controla la intensidad de interacción

3. Modelo de Arrepentimiento

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

Diseño de Algoritmos

1. Método de Gradiente Proyectado (PGM)

• Método de optimización continua basado en la extensión de Lovász
• Utiliza vectores fraccionarios para representar selecciones suaves de espacios y semillas
• Actualiza iterativamente mediante descenso de subgradiente y pasos de proyección
• Complejidad temporal: O(T·m³·n·r·t + Tm²·n·r²·t + m⁴·n·r·t + m³·n·r²·t + m²·n·r³·t)

2. Búsqueda Local Aproximadamente Bisubmodular (ABLS)

• Método de búsqueda local codicioso
• Ordena anunciantes en orden descendente por relación de requisito de presupuesto
• Selecciona elementos que maximizan la reducción de arrepentimiento por unidad de influencia
• Complejidad temporal: O(m·r²·t + m²·r·t)

Puntos de Innovación Técnica

1. Bisubmodularidad ε-Aproximada: Extiende funciones bisubmodulares tradicionales permitiendo desviación acotada
2. Marco Unificado: Modelado unificado por primera vez de publicidad en vallas y redes sociales
3. Cuantificación de Efectos de Interacción: Proporciona método matemático para calcular efectos de interacción
4. Garantías Teóricas: Proporciona límites de rendimiento para funciones aproximadamente bisubmodulares

Configuración Experimental

Conjuntos de Datos

1. Datos de Trayectoria: Datos de registro de Foursquare (2012.4-2014.1)
   • 124,539 registros, 51,318 usuarios únicos
   • Cubre principales ciudades de Estados Unidos
2. Datos de Red Social: Instantánea de red social de usuarios
   • Red antigua: 95,994 relaciones de amistad
   • Red nueva: 129,864 relaciones de amistad
3. Datos de Vallas Publicitarias: Conjunto de datos LAMAR
   • Nueva York: 716 vallas publicitarias, 1,031,040 espacios
   • Los Ángeles: 1,483 vallas publicitarias, 2,135,520 espacios

Métricas de Evaluación

• Arrepentimiento Total: Suma del arrepentimiento de todos los anunciantes
• Número de Anunciantes Satisfechos: Cantidad de anunciantes cuya demanda se satisface
• Tiempo de Cálculo: Tiempo de ejecución del algoritmo

Métodos de Comparación

• Asignación Aleatoria (RA): Selecciona aleatoriamente espacios en vallas publicitarias y nodos semilla
• Asignación Top-k: Selecciona los k espacios en vallas publicitarias y nodos semilla más influyentes

Parámetros Clave

Resultados Experimentales

Resultados Principales

1. Rendimiento en Diferentes Escenarios de Demanda

Caso 1 (α bajo, λ bajo): α ≤ 80%, λ ≤ 2%

• PGM y ABLS superan significativamente los métodos de referencia
• Mayor número de anunciantes satisfechos
• Reducción de arrepentimiento del 30-40%

Caso 2 (α bajo, λ alto): α ≤ 80%, λ ≥ 5%

• Con demandas individuales altas, la sobreoferta disminuye
• Los métodos propuestos mantienen ventaja
• Reducción de arrepentimiento del 25-35%

Caso 3 (α alto, λ bajo): α ≥ 100%, λ ≤ 2%

• Oferta insuficiente aumenta el arrepentimiento general
• PGM y ABLS aún superan la referencia
• Reducción de arrepentimiento del 15-25%

Caso 4 (α alto, λ alto): α ≥ 100%, λ ≥ 5%

• Todos los métodos enfrentan arrepentimiento más alto
• Pocos anunciantes con demanda alta son menos favorables que muchos con demanda baja

2. Análisis de Eficiencia Computacional

• ABLS generalmente tiene tiempo de cálculo más corto en la mayoría de casos
• PGM tiene sobrecarga computacional significativa cuando el número de anunciantes es grande
• El tiempo de cálculo de todos los métodos aumenta con la relación demanda-oferta α

3. Análisis de Sensibilidad de Parámetros

• Aumento de ε: Tiempo de ejecución disminuye pero arrepentimiento aumenta
• Aumento de δ: Penaliza asignaciones grandes, resultando en soluciones compactas pero menos efectivas
• Aumento de γ: Enfatiza satisfacción de demanda, intercambiando mayor uso de recursos por menor arrepentimiento
• Aumento de ρ: Aumenta la intensidad de interacción entre espacios en vallas y nodos semilla

Experimentos de Ablación

1. Impacto de Efectos de Interacción:
   • El arrepentimiento total disminuye de 341.37 a 295.14 al considerar efectos de interacción
   • Demuestra la importancia del modelado de efectos de interacción
2. Impacto de Configuración de Probabilidades:
   • La configuración de probabilidad trivalente muestra mejor rendimiento
   • Simula mejor la variación de influencia entre individuos en la realidad

Pruebas de Escalabilidad

• Escenario a Gran Escala: λ = 1%, |A| = 100
• Escenario a Pequeña Escala: λ = 20%, |A| = 5
• PGM y ABLS superan métodos de referencia en ambos escenarios

Trabajo Relacionado

Investigación de Maximización de Influencia

• Maximización de influencia en publicidad en vallas publicitarias 6, 33, 36
• Maximización de influencia en publicidad en redes sociales 17, 19, 24
• Problema de selección conjunta de etiquetas y espacios 7

Investigación de Minimización de Arrepentimiento

• Minimización de arrepentimiento en redes sociales 13, 30
• Minimización de arrepentimiento en publicidad en vallas publicitarias 37
• Minimización de arrepentimiento bajo restricciones de influencia regional 2, 4

Contribución de Este Artículo

Este es el primer estudio que considera simultáneamente minimización de arrepentimiento en publicidad en vallas y redes sociales, llenando un vacío en el campo.

Conclusiones y Discusión

Conclusiones Principales

1. Complejidad del Problema: Demuestra que el problema de minimización de arrepentimiento en publicidad multimodal es NP-difícil e inaproximable
2. Efectividad de Algoritmos: PGM y ABLS reducen efectivamente el arrepentimiento en diversos escenarios
3. Importancia de Efectos de Interacción: Considerar efectos de interacción entre vallas publicitarias y redes sociales mejora significativamente los resultados
4. Orientación Práctica: Múltiples anunciantes con demanda baja son más favorables que pocos con demanda alta

Limitaciones

1. Complejidad Computacional: PGM tiene sobrecarga computacional significativa en escenarios a gran escala
2. Sensibilidad de Parámetros: Múltiples parámetros requieren ajuste cuidadoso
3. Simplificación del Modelo de Interacción: El modelo de efectos de interacción puede no capturar completamente la complejidad de la realidad
4. Configuración Estática: No considera escenarios con llegada dinámica de anunciantes

Direcciones Futuras

1. Algoritmos En Línea: Desarrollar algoritmos en línea que manejen llegada dinámica de anunciantes
2. Optimización Paralela: Diseñar marcos de optimización paralela y distribuida para mejorar escalabilidad
3. Modelos de Interacción Más Complejos: Explorar métodos de modelado de efectos de interacción más precisos
4. Otros Dominios de Aplicación: Extender el marco a otros campos como asignación de recursos en computación en la nube

Evaluación Profunda

Fortalezas

1. Novedad del Problema: Primer estudio de minimización de arrepentimiento conjunta en publicidad multimodal, con importante significado práctico
2. Rigor Teórico: Proporciona análisis teórico completo, incluyendo pruebas de complejidad y garantías de aproximación
3. Innovación de Métodos:
   • Propone concepto de bisubmodularidad ε-aproximada
   • Diseña modelo matemático de efectos de interacción
   • Desarrolla dos algoritmos complementarios
4. Suficiencia Experimental:
   • Utiliza conjuntos de datos reales a gran escala
   • Considera múltiples configuraciones de parámetros y escenarios
   • Proporciona experimentos de ablación y análisis de sensibilidad detallados

Deficiencias

1. Limitaciones del Modelo de Interacción: La suposición de combinación lineal de efectos de interacción puede ser demasiado simplificada
2. Eficiencia Computacional: La complejidad temporal de PGM es alta, pudiendo enfrentar desafíos en aplicaciones prácticas
3. Dependencia de Parámetros: El rendimiento del algoritmo es sensible a múltiples parámetros, requiriendo ajuste cuidadoso en implementación práctica
4. Limitaciones de Evaluación: Carece de comparación con más métodos de referencia avanzados

Impacto

1. Contribución Académica:
   • Abre nueva dirección de investigación en optimización de publicidad multimodal
   • Extiende teoría de optimización submodular a funciones aproximadamente bisubmodulares
   • Proporciona base teórica para problemas de optimización relacionados
2. Valor Práctico:
   • Directamente aplicable a industria de publicidad digital
   • Marco extensible a problemas de asignación de recursos en otros campos
   • Proporciona herramienta de apoyo a decisiones para proveedores de influencia
3. Reproducibilidad: El artículo proporciona descripción detallada de algoritmos y configuración experimental, facilitando reproducción

Escenarios de Aplicación

1. Plataformas de Publicidad Digital: Aplicable a plataformas que necesitan gestionar simultáneamente recursos publicitarios en línea y fuera de línea
2. Sistemas de Asignación de Recursos: Extensible a problemas de asignación de recursos en computación en la nube, logística, etc.
3. Marketing de Influencia: Aplicable a optimización conjunta de marketing en redes sociales y publicidad tradicional

Referencias Bibliográficas

El artículo cita 37 referencias relacionadas, cubriendo múltiples campos de investigación incluyendo maximización de influencia, optimización submodular, asignación de publicidad, proporcionando base teórica sólida para esta investigación.

Evaluación General: Este es un artículo de investigación de alta calidad que logra buen equilibrio entre innovación teórica y aplicación práctica. Aunque presenta algunas limitaciones, su dirección de investigación pionera y diseño de métodos rigurosos le confieren importante valor académico y significado práctico.