Hostname: page-component-cd9895bd7-gbm5v Total loading time: 0 Render date: 2024-12-25T07:35:06.313Z Has data issue: false hasContentIssue false
  • English
  • Français

Robust coordination in adversarial social networks: From human behavior to agent-based modeling

Published online by Cambridge University Press:  17 May 2021

Chen Hajaj Open the ORCID record for Chen Hajaj [Opens in a new window] ,
Zlatko Joveski Open the ORCID record for Zlatko Joveski [Opens in a new window] ,
Sixie Yu  and
Yevgeniy Vorobeychik Open the ORCID record for Yevgeniy Vorobeychik [Opens in a new window]
Chen Hajaj*
Affiliation:
Department of Industrial Engineering and Management, Ariel University, Ariel, Israel Cyber Innovation Center, Ariel University, Ariel, Israel
Zlatko Joveski
Affiliation:
Department of Electrical Engineering and Computer Science, Vanderbilt University, Nashville, TN 37235, USA (e-mail: [email protected])
Sixie Yu
Affiliation:
Department of Computer Science and Engineering, Washington University, St. Louis, MO 63130, USA (e-mails: [email protected], [email protected])
Yevgeniy Vorobeychik
Affiliation:
Department of Computer Science and Engineering, Washington University, St. Louis, MO 63130, USA (e-mails: [email protected], [email protected])
*
*Corresponding author. Email: [email protected]
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

Decentralized coordination is one of the fundamental challenges for societies and organizations. While extensively explored from a variety of perspectives, one issue that has received limited attention is human coordination in the presence of adversarial agents. We study this problem by situating human subjects as nodes on a network, and endowing each with a role, either regular (with the goal of achieving consensus among all regular players), or adversarial (aiming to prevent consensus among regular players). We show that adversarial nodes are, indeed, quite successful in preventing consensus. However, we demonstrate that having the ability to communicate among network neighbors can considerably improve coordination success, as well as resilience to adversarial nodes. Our analysis of communication suggests that adversarial nodes attempt to exploit this capability for their ends, but do so in a somewhat limited way, perhaps to prevent regular nodes from recognizing their intent. In addition, we show that the presence of trusted nodes generally has limited value, but does help when many adversarial nodes are present, and players can communicate. Finally, we use experimental data to develop computational models of human behavior and explore additional parametric variations: features of network topologies and densities, and placement, all using the resulting data-driven agent-based (DDAB) model.

Keywords

coordinationsocial networksadversariesagent-based modeling
Type
Research Article
Information
Network Science , Volume 9 , Issue 3 , September 2021 , pp. 255 - 290
Creative Commons
Creative Common License - CCCreative Common License - BY
This is an Open Access article, distributed under the terms of the Creative Commons Attribution-NonCommercial-NoDerivatives licence (http://creativecommons.org/licenses/by/4.0/), which permits non-commercial re-use, distribution, and reproduction in any medium, provided the original work is unaltered and is properly cited. The written permission of Cambridge University Press must be obtained for commercial re-use or in order to create a derivative work.
Copyright
© The Author(s), 2021. Published by Cambridge University Press

Footnotes

Action Editor: Fernando Vega-Redondo

References

Abbas, W., Laszka, A., & Koutsoukos, X. (2017). Improving network connectivity and robustness using trusted nodes with application to resilient consensus. IEEE Transactions on Control of Network Systems, 5(4), 2036–2048.CrossRefGoogle Scholar
Abbas, W., Vorobeychik, Y., & Koutsoukos, X. (2014). Resilient consensus protocol in the presence of trusted nodes. In International symposium on resilient control systems (pp. 1–7).CrossRefGoogle Scholar
Albert, R., Jeong, H., & Barabasi, A.t.-L. (2000). Error and attack tolerance of complex networks. Nature, 406, 378–482.CrossRefGoogle ScholarPubMed
Alon, N., Feldman, M., Lev, O., & Tennenholtz, M. (2015). How robust is the wisdom of the crowds? In IJCAI (pp. 2055–2061).Google Scholar
Arenas, A., Camacho, J., Cuesta, J. A., & Requejo, R. J. (2011). The joker effect: Cooperation driven by destructive agents. Journal of Theoretical Biology, 279(1), 113–119.CrossRefGoogle ScholarPubMed
Bannikova, M., Dery, L., Obraztsova, S., Rabinovich, Z., & Rosenschein, J. S. (2021). Reaching consensus under a deadline. Autonomous Agents and Multi-Agent Systems, 35(1), 1–42.CrossRefGoogle Scholar
Barabasi, A.-L., & Albert, R. (1999). Emergence of scaling in random networks. Science, 286(5439), 509–512.CrossRefGoogle ScholarPubMed
Bracha, G., & Toueg, S. (1983). Resilient consensus protocols. In ACM symposium on principles of distributed computing (pp. 12–26).CrossRefGoogle Scholar
Chakraborty, T., Judd, S., Kearns, M., & Tan, J. (2010). A behavioral study of bargaining in social networks. In Proceedings of the 11th ACM conference on electronic commerce (pp. 243–252).CrossRefGoogle Scholar
Cooper, R., DeJong, D. V., Forsythe, R., & Ross, T. W. (1992). Communication in coordination games. Quarterly Journal of Economics, 107(2), 739–771.CrossRefGoogle Scholar
Coviello, L., Franceschetti, M., McCubbins, M., Paturi, R., & Vattani, A. (2012). Human matching behavior in social networks: An algorithmic perspective. Plos One, 7(8), e41900.CrossRefGoogle Scholar
Demichelis, S., & Weibull, J. W. (2008). Language, meaning, and games: A model of communication, coordination, and evolution. American Economic Review, 98(4), 1292–1311.CrossRefGoogle Scholar
Ellingsen, T., & Ostling, Rt. (2010). When does communication improve coordination? American Economic Review, 100, 1695–1724.CrossRefGoogle Scholar
Elmalech, A., Sarne, D., David, E., & Hajaj, C. (2016). Extending workers’ attention span through dummy events. In Fourth AAAI conference on human computation and crowdsourcing.Google Scholar
Erdos, P., & Rényi, A. (1960). On the evolution of random graphs. Publication of the Mathematical Institute of the Hungarian Academy of Sciences, 5(1), 17–60.Google Scholar
Farrell, J. (1987). Cheap talk, coordination, and entry. Rand Journal of Economics, 18(1), 34–39.CrossRefGoogle Scholar
Farrell, J. (1988). Communication, coordination and Nash equilibrium. Economic Letters, 27, 209–214.CrossRefGoogle Scholar
Gracia-Lázaro, C., Ferrer, A., Ruiz, G., Tarancón, A., Cuesta, J. A., Sánchez, A., & Moreno, Y. (2012). Heterogeneous networks do not promote cooperation when humans play a prisoner’s dilemma. Proceedings of the National Academy of Sciences, 109(32), 12922–12926.CrossRefGoogle Scholar
Gvirts, H. Z., & Dery, L. (2021). Alexithymia and reaching group consensus. Cognition and Emotion, 35(3), 510–523. doi: 10.1080/02699931.2019.1675600.CrossRefGoogle Scholar
Hajaj, C., Hazon, N., & Sarne, D. (2015). Improving comparison shopping agents’ competence through selective price disclosure. Electronic Commerce Research and Applications, 14(6), 563–581.CrossRefGoogle Scholar
Hajaj, C., Hazon, N., & Sarne, D. (2017). Enhancing comparison shopping agents through ordering and gradual information disclosure. Autonomous Agents and Multi-Agent Systems, 31(3), 696–714.CrossRefGoogle Scholar
Hajaj, C., Yu, S., Joveski, Z., Guo, Y., & Vorobeychik, Y. (2019). Adversarial coordination on social networks. In Proceedings of the 18th international conference on autonomous agents and multiagent systems (pp. 1515–1523).Google Scholar
Hardin, G. (1968). The tragedy of the commons. Science, 162(3859), 1243–1248.Google ScholarPubMed
Judd, S., Kearns, M., & Vorobeychik, Y. (2010). Behavioral dynamics and influence in networked coloring and consensus. Proceedings of the National Academy of Sciences, 107(34), 14978–14982.CrossRefGoogle Scholar
Kearns, M. (2012). Experiments in social computation. Communications of the ACM, 55(10), 56–67.CrossRefGoogle Scholar
Kearns, M., Judd, S., Tan, J., & Wortman, J. (2009). Behavioral experiments in biased voting in networks. Proceedings of the National Academy of Sciences, 106(5), 1347–1352.CrossRefGoogle ScholarPubMed
Kearns, M., Judd, S., & Vorobeychik, Y. (2012). Behavioral experiments on a network formation game. In Proceedings of the 13th ACM conference on electronic commerce (pp. 690–704). ACM.Google Scholar
Kearns, M., Suri, S., & Montfort, N. (2006). An experimental study of the coloring problem on human subject networks. Science, 313(5788), 824–827.CrossRefGoogle ScholarPubMed
LeBlanc, H. J., & Koutsoukos, X. D. (2012 ). Low complexity resilient consensus in networked multi-agent systems with adversaries. In Proceedings of the 15th ACM international conference on hybrid systems: Computation and control. HSCC’12 (pp. 5–14). New York, NY, USA: ACM.Google Scholar
LeBlanc, H. J., Zhang, H., Koutsoukos, X., & Sundaram, S. (2013). Resilient asymptotic consensus in robust networks. IEEE Journal on Selected Areas in Communications, 31(4), 766–781.CrossRefGoogle Scholar
Leibbrandt, A., Ramalingam, A., Saaksvuori, L., & Walker, J. M. (2015). Incomplete punishment networks in public goods games: Experimental evidence. Experimental Economics, 18(1), 15–37.CrossRefGoogle Scholar
Mao, A., Dworkin, L., Suri, S., & Watts, D. J. (2017). Resilient cooperators stabilize long-run cooperation in the finitely repeated prisoner’s dilemma. Nature Communications, 8, 13800.CrossRefGoogle ScholarPubMed
Mason, W., & Suri, S. (2012). Conducting behavioral research on amazon’s mechanical turk. Behavior Research Methods, 44(1), 1–23.CrossRefGoogle ScholarPubMed
Matthew, M., Ramamohan, P., & Nicholas, W. (2009). Networked coordination: Effect of network structure on human subjects’ ability to solve coordination problem. American Politics Research, 37, 899–920.Google Scholar
Miller, J. H., & Moser, S. (2004). Communication and coordination. Complexity, 9(5), 31–40.CrossRefGoogle Scholar
Narayanan, A., Bonneau, J., Felten, E., Miller, A., & Goldfeder, S. (2016). Bitcoin and cryptocurrency technologies: A comprehensive introduction. Princeton, NJ: Princeton University Press.Google Scholar
Nay, J. J., & Vorobeychik, Y. (2016). Predicting human cooperation. Plos One, 11(5), e0155656.CrossRefGoogle ScholarPubMed
Olmstead, A. J, Viswanathan, N., Aicher, K. A, & Fowler, C. A. (2009). Sentence comprehension affects the dynamics of bimanual coordination: Implications for embodied cognition. Quarterly Journal of Experimental Psychology, 62(12), 2409–2417.CrossRefGoogle ScholarPubMed
Paolacci, G., Chandler, J., & Ipeirotis, P. G. (2010). Running experiments on amazon mechanical turk. Judgment and Decision Making, 5(5), 411–419.Google Scholar
Peled, N., Gal, Y., & Kraus, S. (2015). A study of computational and human strategies in revelation games. Autonomous Agents and Multi-Agent Systems, 29(1), 73–97.CrossRefGoogle Scholar
Rapoport, A., Chammah, A. M., & Orwant, C. J. (1965). Prisoner’s dilemma: A study in conflict and cooperation, Vol. 165. United States of America: University of Michigan Press.CrossRefGoogle Scholar
Richerson, P. J., & Boyd, R. (2010). Why possibly language evolved. Biolinguistics, 4(2–3), 289–306.Google Scholar
Shirado, H., & Christakis, N. A. (2017). Locally noisy autonomous agents improve global human coordination in network experiments. Nature, 545(7654), 370.CrossRefGoogle ScholarPubMed
Szamado, S. (2011). Pre-hunt communication provides context for the evolution of early human languge. Biological Theory, 5(4), 366–382.CrossRefGoogle Scholar
Usevitch, J., & Panagou, D. (2018). Resilient leader-follower consensus to arbitrary reference values. In Annual american control conference (pp. 1292–1298).CrossRefGoogle Scholar
Vorobeychik, Y., Joveski, Z., & Yu, S. (2017). Does communication help people coordinate? Plos One, 12(2), 1–19.CrossRefGoogle ScholarPubMed
Watts, D. J., & Strogatz, S. H. (1998). Collective dynamics of ‘small-world’ networks. Nature, 393(6684), 440.CrossRefGoogle ScholarPubMed
Wunder, M., Suri, S., & Watts, D. J. (2013). Empirical agent based models of cooperation in public goods games. In Proceedings of the fourteenth ACM conference on electronic commerce (pp. 891–908). ACM.Google Scholar
Zeng, W., & Chow, M.-Y. (2014). Resilient distributed control in the presence of misbehaving agents in networked control systems. IEEE Transactions on Cybernetics, 44(11), 2038–2049.CrossRefGoogle ScholarPubMed
Zhang, H., & Vorobeychik, Y. (2019). Empirically grounded agent-based models of innovation diffusion: A critical review. Artificial Intelligence Review, 52(1), 707–741.CrossRefGoogle Scholar
Zhang, H., Vorobeychik, Y., Letchford, J., & Lakkaraju, K. (2016). Data-driven agent-based modeling, with application to rooftop solar adoption. Journal of Autonomous Agents and Multiagent Systems, 30(6), 1023–1049.CrossRefGoogle Scholar