On the behavior of threshold models over finite networks
We study a model for cascade effects over finite networks based on a deterministic binary linear threshold model. Our starting point is a networked coordination game where each agent's payoff is the sum of the payoffs coming from pairwise interaction with each of the neighbors. We first establi...
| Main Authors: | , , |
|---|---|
| 其他作者: | |
| 格式: | 文件 |
| 语言: | en_US |
| 出版: |
Institute of Electrical and Electronics Engineers (IEEE)
2014
|
| 在线阅读: | http://hdl.handle.net/1721.1/86039 https://orcid.org/0000-0002-1827-1285 https://orcid.org/0000-0002-1470-2148 https://orcid.org/0000-0002-6185-1998 |
| _version_ | 1826200577415053312 |
|---|---|
| author | Adam, Elie M. Dahleh, Munther A. Ozdaglar, Asuman E. |
| 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 Adam, Elie M. Dahleh, Munther A. Ozdaglar, Asuman E. |
| author_sort | Adam, Elie M. |
| collection | MIT |
| description | We study a model for cascade effects over finite networks based on a deterministic binary linear threshold model. Our starting point is a networked coordination game where each agent's payoff is the sum of the payoffs coming from pairwise interaction with each of the neighbors. We first establish that the best response dynamics in this networked game is equivalent to the linear threshold dynamics with heterogeneous thresholds over the agents. While the previous literature has studied such linear threshold models under the assumption that each agent may change actions at most once, a study of best response dynamics in such networked games necessitates an analysis that allows for multiple switches in actions. In this paper, we develop such an analysis. We establish that agent behavior cycles among different actions in the limit, we characterize the length of such limit cycles, and reveal bounds on the time steps required to reach them. We finally propose a measure of network resilience that captures the nature of the involved dynamics. We prove bounds and investigate the resilience of different network structures under this measure. |
| first_indexed | 2024-09-23T11:38:32Z |
| format | Article |
| id | mit-1721.1/86039 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T11:38:32Z |
| publishDate | 2014 |
| publisher | Institute of Electrical and Electronics Engineers (IEEE) |
| record_format | dspace |
| spelling | mit-1721.1/860392022-10-01T04:58:55Z On the behavior of threshold models over finite networks Adam, Elie M. Dahleh, Munther A. Ozdaglar, Asuman E. Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Massachusetts Institute of Technology. Engineering Systems Division Massachusetts Institute of Technology. Laboratory for Information and Decision Systems Adam, Elie M. Dahleh, Munther A. Ozdaglar, Asuman E. We study a model for cascade effects over finite networks based on a deterministic binary linear threshold model. Our starting point is a networked coordination game where each agent's payoff is the sum of the payoffs coming from pairwise interaction with each of the neighbors. We first establish that the best response dynamics in this networked game is equivalent to the linear threshold dynamics with heterogeneous thresholds over the agents. While the previous literature has studied such linear threshold models under the assumption that each agent may change actions at most once, a study of best response dynamics in such networked games necessitates an analysis that allows for multiple switches in actions. In this paper, we develop such an analysis. We establish that agent behavior cycles among different actions in the limit, we characterize the length of such limit cycles, and reveal bounds on the time steps required to reach them. We finally propose a measure of network resilience that captures the nature of the involved dynamics. We prove bounds and investigate the resilience of different network structures under this measure. Irwin Mark Jacobs and Joan Klein Jacobs Presidential Fellowship Siebel Scholarship United States. Air Force Office of Scientific Research (Grant FA9550-09-1-0420) United States. Army Research Office (Grant W911NF-09-1-0556) 2014-04-07T12:10:43Z 2014-04-07T12:10:43Z 2012-12 Article http://purl.org/eprint/type/ConferencePaper 978-1-4673-2066-5 978-1-4673-2065-8 978-1-4673-2063-4 978-1-4673-2064-1 http://hdl.handle.net/1721.1/86039 Adam, Elie M., Munther A. Dahleh, and Asuman Ozdaglar. “On the Behavior of Threshold Models over Finite Networks.” 2012 IEEE 51st IEEE Conference on Decision and Control (CDC) (n.d.). https://orcid.org/0000-0002-1827-1285 https://orcid.org/0000-0002-1470-2148 https://orcid.org/0000-0002-6185-1998 en_US http://dx.doi.org/10.1109/CDC.2012.6426073 Proceedings of the 2012 IEEE 51st IEEE Conference on Decision and Control (CDC) Creative Commons Attribution-Noncommercial-Share Alike http://creativecommons.org/licenses/by-nc-sa/4.0/ application/pdf Institute of Electrical and Electronics Engineers (IEEE) MIT web domain |
| spellingShingle | Adam, Elie M. Dahleh, Munther A. Ozdaglar, Asuman E. On the behavior of threshold models over finite networks |
| title | On the behavior of threshold models over finite networks |
| title_full | On the behavior of threshold models over finite networks |
| title_fullStr | On the behavior of threshold models over finite networks |
| title_full_unstemmed | On the behavior of threshold models over finite networks |
| title_short | On the behavior of threshold models over finite networks |
| title_sort | on the behavior of threshold models over finite networks |
| url | http://hdl.handle.net/1721.1/86039 https://orcid.org/0000-0002-1827-1285 https://orcid.org/0000-0002-1470-2148 https://orcid.org/0000-0002-6185-1998 |
| work_keys_str_mv | AT adameliem onthebehaviorofthresholdmodelsoverfinitenetworks AT dahlehmunthera onthebehaviorofthresholdmodelsoverfinitenetworks AT ozdaglarasumane onthebehaviorofthresholdmodelsoverfinitenetworks |