Maximizing Social Welfare in a Competitive Diffusion Model

• URL: http://arxiv.org/abs/2012.03354v1
• Date: Sun, 6 Dec 2020 19:09:12 GMT
• Title: Maximizing Social Welfare in a Competitive Diffusion Model
• Authors: Prithu Banerjee, Wei Chen, Laks V.S. Lakshmanan
• Abstract summary: UIC (IM) has garnered a lot of attention owing to applications such as viral marketing and infection containment. It aims to select a small number of seed users to adopt an item such that adoption propagates to a large number of users in the network. Existing works on competitive IM have several limitations.
• Score: 19.18481967353127
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: Influence maximization (IM) has garnered a lot of attention in the literature owing to applications such as viral marketing and infection containment. It aims to select a small number of seed users to adopt an item such that adoption propagates to a large number of users in the network. Competitive IM focuses on the propagation of competing items in the network. Existing works on competitive IM have several limitations. (1) They fail to incorporate economic incentives in users' decision making in item adoptions. (2) Majority of the works aim to maximize the adoption of one particular item, and ignore the collective role that different items play. (3) They focus mostly on one aspect of competition -- pure competition. To address these concerns we study competitive IM under a utility-driven propagation model called UIC, and study social welfare maximization. The problem in general is not only NP-hard but also NP-hard to approximate within any constant factor. We, therefore, devise instant dependent efficient approximation algorithms for the general case as well as a $(1-1/e-\epsilon)$-approximation algorithm for a restricted setting. Our algorithms outperform different baselines on competitive IM, both in terms of solution quality and running time on large real networks under both synthetic and real utility configurations.

Related papers

• CompeteSMoE -- Effective Training of Sparse Mixture of Experts via Competition [52.2034494666179]
  Sparse mixture of experts (SMoE) offers an appealing solution to scale up the model complexity beyond the mean of increasing the network's depth or width. We propose a competition mechanism to address this fundamental challenge of representation collapse. By routing inputs only to experts with the highest neural response, we show that, under mild assumptions, competition enjoys the same convergence rate as the optimal estimator.
  arXiv  Detail & Related papers  (2024-02-04T15:17:09Z)
• Communication-Efficient Decentralized Federated Learning via One-Bit Compressive Sensing [52.402550431781805]
  Decentralized federated learning (DFL) has gained popularity due to its practicality across various applications. Compared to the centralized version, training a shared model among a large number of nodes in DFL is more challenging. We develop a novel algorithm based on the framework of the inexact alternating direction method (iADM)
  arXiv  Detail & Related papers  (2023-08-31T12:22:40Z)
• Multi-Prompt Alignment for Multi-Source Unsupervised Domain Adaptation [86.02485817444216]
  We introduce Multi-Prompt Alignment (MPA), a simple yet efficient framework for multi-source UDA. MPA denoises the learned prompts through an auto-encoding process and aligns them by maximizing the agreement of all the reconstructed prompts. Experiments show that MPA achieves state-of-the-art results on three popular datasets with an impressive average accuracy of 54.1% on DomainNet.
  arXiv  Detail & Related papers  (2022-09-30T03:40:10Z)
• GraMeR: Graph Meta Reinforcement Learning for Multi-Objective Influence Maximization [1.7311053765541482]
  Influence (IM) is a problem of identifying a subset of nodes called the seed nodes in a network (graph) IM has numerous applications such as viral marketing, epidemic control, sensor placement and other network-related tasks. We develop a generic IM problem as a Markov decision process that handles both intrinsic and influence activations.
  arXiv  Detail & Related papers  (2022-05-30T03:48:51Z)
• Contingency-Aware Influence Maximization: A Reinforcement Learning Approach [52.109536198330126]
  influence (IM) problem aims at finding a subset of seed nodes in a social network that maximize the spread of influence. In this study, we focus on a sub-class of IM problems, where whether the nodes are willing to be the seeds when being invited is uncertain, called contingency-aware IM. Despite the initial success, a major practical obstacle in promoting the solutions to more communities is the tremendous runtime of the greedy algorithms.
  arXiv  Detail & Related papers  (2021-06-13T16:42:22Z)
• The MineRL 2020 Competition on Sample Efficient Reinforcement Learning using Human Priors [62.9301667732188]
  We propose a second iteration of the MineRL Competition. The primary goal of the competition is to foster the development of algorithms which can efficiently leverage human demonstrations. The competition is structured into two rounds in which competitors are provided several paired versions of the dataset and environment. At the end of each round, competitors submit containerized versions of their learning algorithms to the AIcrowd platform.
  arXiv  Detail & Related papers  (2021-01-26T20:32:30Z)
• The Best of Many Worlds: Dual Mirror Descent for Online Allocation Problems [7.433931244705934]
  We consider a data-driven setting in which the reward and resource consumption of each request are generated using an input model unknown to the decision maker. We design general class of algorithms that attain good performance in various input models without knowing which type of input they are facing. Our algorithms operate in the Lagrangian dual space: they maintain a dual multiplier for each resource that is updated using online mirror descent.
  arXiv  Detail & Related papers  (2020-11-18T18:39:17Z)
• Competing Bandits: The Perils of Exploration Under Competition [99.68537519404727]
  We study the interplay between exploration and competition on online platforms. We find that stark competition induces firms to commit to a "greedy" bandit algorithm that leads to low welfare. We investigate two channels for weakening the competition: relaxing the rationality of users and giving one firm a first-mover advantage.
  arXiv  Detail & Related papers  (2020-07-20T14:19:08Z)
• Regularized Online Allocation Problems: Fairness and Beyond [7.433931244705934]
  We introduce the emphregularized online allocation problem, a variant that includes a non-linear regularizer acting on the total resource consumption. In this problem, requests repeatedly arrive over time and, for each request, a decision maker needs to take an action that generates a reward and consumes resources. The objective is to simultaneously maximize additively separable rewards and the value of a non-separable regularizer subject to the resource constraints.
  arXiv  Detail & Related papers  (2020-07-01T14:24:58Z)
• Online Competitive Influence Maximization [46.08146352395603]
  We introduce a new Online Competitive Influence Maximization (OCIM) problem, where two competing items propagate in the same network and influence probabilities on edges are unknown. We adopt a multi-armed bandit (CMAB) framework for OCIM, but unlike the non-competitive setting, the important monotonicity property (influence spread increases when influence probabilities on edges increase) no longer holds due to the competitive nature of propagation.
  arXiv  Detail & Related papers  (2020-06-24T01:11:02Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.