How to influence people with partial incentives
We study the power of fractional allocations of resources to maximize our influence in a network. This work extends in a natural way the well-studied model by Kleinberg, Kempe, and Tardos (2003), where a designer selects a (small) seed set of nodes in a social network to influence directly, this inf...
| Main Authors: | , , , , , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Association for Computing Machinery (ACM)
2015
|
| Online Access: | http://hdl.handle.net/1721.1/99998 https://orcid.org/0000-0003-3803-5703 |
| _version_ | 1826196717642448896 |
|---|---|
| author | Demaine, Erik D. Hajiaghayi, MohammadTaghi Mahini, Hamid Malec, David L. Raghavan, S. Sawant, Anshul Zadimoghaddam, Morteza |
| author2 | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science |
| author_facet | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Demaine, Erik D. Hajiaghayi, MohammadTaghi Mahini, Hamid Malec, David L. Raghavan, S. Sawant, Anshul Zadimoghaddam, Morteza |
| author_sort | Demaine, Erik D. |
| collection | MIT |
| description | We study the power of fractional allocations of resources to maximize our influence in a network. This work extends in a natural way the well-studied model by Kleinberg, Kempe, and Tardos (2003), where a designer selects a (small) seed set of nodes in a social network to influence directly, this influence cascades when other nodes reach certain thresholds of neighbor influence, and the goal is to maximize the final number of influenced nodes. Despite extensive study from both practical and theoretical viewpoints, this model limits the designer to a binary choice for each node, with no chance to apply intermediate levels of influence. This model captures some settings precisely, such as exposure to an idea or pathogen, but it fails to capture very relevant concerns in others, for example, a manufacturer promoting a new product by distributing five "20% off" coupons instead of giving away a single free product.
While fractional versions of problems tend to be easier to solve than integral versions, for influence maximization, we show that the two versions have essentially the same computational complexity. On the other hand, the two versions can have vastly different solutions: the added flexibility of fractional allocation can lead to significantly improved influence. Our main theoretical contribution is to show how to adapt the major positive results from the integral case to the fractional case. Specifically, Mossel and Roch (2006) used the submodularity of influence to obtain their integral results; we introduce a new notion of continuous submodularity, and use this to obtain matching fractional results. We conclude that we can achieve the same greedy (1-1/e-ε)-approximation for the fractional case as the integral case, and that other heuristics are likely to carry over as well. In practice, we find that the fractional model performs substantially better than the integral model, according to simulations on real-world social network data. |
| first_indexed | 2024-09-23T10:35:18Z |
| format | Article |
| id | mit-1721.1/99998 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T10:35:18Z |
| publishDate | 2015 |
| publisher | Association for Computing Machinery (ACM) |
| record_format | dspace |
| spelling | mit-1721.1/999982022-09-27T10:01:02Z How to influence people with partial incentives Demaine, Erik D. Hajiaghayi, MohammadTaghi Mahini, Hamid Malec, David L. Raghavan, S. Sawant, Anshul Zadimoghaddam, Morteza Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Demaine, Erik D. Zadimoghaddam, Morteza We study the power of fractional allocations of resources to maximize our influence in a network. This work extends in a natural way the well-studied model by Kleinberg, Kempe, and Tardos (2003), where a designer selects a (small) seed set of nodes in a social network to influence directly, this influence cascades when other nodes reach certain thresholds of neighbor influence, and the goal is to maximize the final number of influenced nodes. Despite extensive study from both practical and theoretical viewpoints, this model limits the designer to a binary choice for each node, with no chance to apply intermediate levels of influence. This model captures some settings precisely, such as exposure to an idea or pathogen, but it fails to capture very relevant concerns in others, for example, a manufacturer promoting a new product by distributing five "20% off" coupons instead of giving away a single free product. While fractional versions of problems tend to be easier to solve than integral versions, for influence maximization, we show that the two versions have essentially the same computational complexity. On the other hand, the two versions can have vastly different solutions: the added flexibility of fractional allocation can lead to significantly improved influence. Our main theoretical contribution is to show how to adapt the major positive results from the integral case to the fractional case. Specifically, Mossel and Roch (2006) used the submodularity of influence to obtain their integral results; we introduce a new notion of continuous submodularity, and use this to obtain matching fractional results. We conclude that we can achieve the same greedy (1-1/e-ε)-approximation for the fractional case as the integral case, and that other heuristics are likely to carry over as well. In practice, we find that the fractional model performs substantially better than the integral model, according to simulations on real-world social network data. National Science Foundation (U.S.) (CAREER Award 1053605) National Science Foundation (U.S.) (Grant CCF-1161626) United States. Office of Naval Research. Young Investigator Program (Award N000141110662) United States. Defense Advanced Research Projects Agency (United States. Air Force Office of Scientific Research Grant FA9550-12-1-0423) 2015-11-23T16:25:54Z 2015-11-23T16:25:54Z 2014-04 Article http://purl.org/eprint/type/ConferencePaper 9781450327442 http://hdl.handle.net/1721.1/99998 Erik D. Demaine, MohammadTaghi Hajiaghayi, Hamid Mahini, David L. Malec, S. Raghavan, Anshul Sawant, and Morteza Zadimoghadam. 2014. How to influence people with partial incentives. In Proceedings of the 23rd international conference on World wide web (WWW '14). ACM, New York, NY, USA, 937-948. https://orcid.org/0000-0003-3803-5703 en_US http://dx.doi.org/10.1145/2566486.2568039 Proceedings of the 23rd international conference on World wide web (WWW '14) Creative Commons Attribution-Noncommercial-Share Alike http://creativecommons.org/licenses/by-nc-sa/4.0/ application/pdf Association for Computing Machinery (ACM) arXiv |
| spellingShingle | Demaine, Erik D. Hajiaghayi, MohammadTaghi Mahini, Hamid Malec, David L. Raghavan, S. Sawant, Anshul Zadimoghaddam, Morteza How to influence people with partial incentives |
| title | How to influence people with partial incentives |
| title_full | How to influence people with partial incentives |
| title_fullStr | How to influence people with partial incentives |
| title_full_unstemmed | How to influence people with partial incentives |
| title_short | How to influence people with partial incentives |
| title_sort | how to influence people with partial incentives |
| url | http://hdl.handle.net/1721.1/99998 https://orcid.org/0000-0003-3803-5703 |
| work_keys_str_mv | AT demaineerikd howtoinfluencepeoplewithpartialincentives AT hajiaghayimohammadtaghi howtoinfluencepeoplewithpartialincentives AT mahinihamid howtoinfluencepeoplewithpartialincentives AT malecdavidl howtoinfluencepeoplewithpartialincentives AT raghavans howtoinfluencepeoplewithpartialincentives AT sawantanshul howtoinfluencepeoplewithpartialincentives AT zadimoghaddammorteza howtoinfluencepeoplewithpartialincentives |