{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T01:37:53Z","timestamp":1760146673277,"version":"build-2065373602"},"reference-count":28,"publisher":"MDPI AG","issue":"6","license":[{"start":{"date-parts":[[2024,12,2]],"date-time":"2024-12-02T00:00:00Z","timestamp":1733097600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Games"],"abstract":"<jats:p>The threshold protocol game is a graphical game that models the adoption of an idea or product through a population. There are two states players may take in the game, and the goal of the game is to motivate the state that begins in the minority to spread to every player. Here, the threshold protocol game is defined, and existence results are studied on infinite graphs. Many generalizations are proposed and applied. This work explores the impact of graph topology on the outcome of the threshold protocol game and consequently considers finite graphs. By exploiting the well-known topologies of complete and complete bipartite graphs, the outcome of the threshold protocol game can be fully characterized on these graphs. These characterizations are ideal, as they are given in terms of the game parameters. More generally, initial conditions in terms of game parameters that cause the preferred game outcome to occur are identified. It is shown that the necessary conditions differ between non-bipartite and bipartite graphs because non-bipartite graphs contain odd cycles while bipartite graphs do not. These results motivate the primary result of this work, which is an exhaustive list of achievable game outcomes on bipartite graphs. While possible outcomes are identified, it is noted that a complete characterization of when game outcomes occur is not possible on general bipartite graphs.<\/jats:p>","DOI":"10.3390\/g15060041","type":"journal-article","created":{"date-parts":[[2024,12,3]],"date-time":"2024-12-03T04:04:04Z","timestamp":1733198644000},"page":"41","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["End Behavior of the Threshold Protocol Game on Complete and Bipartite Graphs"],"prefix":"10.3390","volume":"15","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-1949-2290","authenticated-orcid":false,"given":"Alexandra","family":"Fedrigo","sequence":"first","affiliation":[{"name":"Department of Mathematical Sciences, University of Alabama in Huntsville, 301 Sparkman Drive, Huntsville, AL 35899, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2024,12,2]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","unstructured":"Mikkelsen, K.B., and Bach, L.A. (2016). Threshold Games and Cooperation on Multiplayer Graphs. PLoS ONE, 11.","DOI":"10.1371\/journal.pone.0152340"},{"key":"ref_2","unstructured":"Kearns, M., Littman, M.L., and Singh, S. (2001, January 2\u20135). Graphical models for game theory. Proceedings of the Seventeenth Conference on Uncertainty in Artificial Intelligence, UAI\u201901, Seattle, WA, USA."},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"016104","DOI":"10.1103\/PhysRevE.86.016104","article-title":"Relationship between clustering coefficient and the success of cooperation in networks","volume":"86","author":"Kuperman","year":"2012","journal-title":"Phys. Rev. E"},{"key":"ref_4","doi-asserted-by":"crossref","unstructured":"Smyrnakis, M., Freris, N.M., and Tembine, H. (2018). Consensus over evolutionary graphs. arXiv.","DOI":"10.23919\/ECC.2018.8550392"},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"383","DOI":"10.1006\/jeth.1995.1014","article-title":"Evolution of Equilibria in the Long Run: A General Theory and Applications","volume":"65","author":"Kandori","year":"1995","journal-title":"J. Econ. Theory"},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"826","DOI":"10.1038\/359826a0","article-title":"Evolutionary games and spatial chaos","volume":"359","author":"Nowak","year":"1992","journal-title":"Nature"},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"748","DOI":"10.1111\/j.1461-0248.2005.00773.x","article-title":"Models of cooperation based on the Prisoner\u2019s Dilemma and the Snowdrift game: Prisoner\u2019s Dilemma and the Snowdrift game","volume":"8","author":"Doebeli","year":"2005","journal-title":"Ecol. Lett."},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"405","DOI":"10.1119\/1.1848514","article-title":"Game theory and physics","volume":"73","author":"Hauert","year":"2005","journal-title":"Am. J. Phys."},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"P04019","DOI":"10.1088\/1742-5468\/2011\/04\/P04019","article-title":"Random topologies and the emergence of cooperation: The role of short-cuts","volume":"2011","author":"Vilone","year":"2011","journal-title":"J. Stat. Mech. Theory Exp."},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"4395","DOI":"10.1073\/pnas.1105757109","article-title":"Collaboration in social networks","volume":"109","author":"Marsili","year":"2012","journal-title":"Proc. Natl. Acad. Sci. USA"},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"440","DOI":"10.1038\/30918","article-title":"Collective dynamics of \u2018small-world\u2019 networks","volume":"393","author":"Watts","year":"1998","journal-title":"Nature"},{"key":"ref_12","first-page":"1","article-title":"Local Conventions","volume":"2","author":"Ely","year":"2002","journal-title":"Adv. Theor. Econ."},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"028702","DOI":"10.1103\/PhysRevLett.106.028702","article-title":"Emergent Hierarchical Structures in Multiadaptive Games","volume":"106","author":"Lee","year":"2011","journal-title":"Phys. Rev. Lett."},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"95","DOI":"10.1016\/B978-0-444-53766-9.00003-3","article-title":"Games on Networks","volume":"Volume 4","author":"Jackson","year":"2015","journal-title":"Handbook of Game Theory with Economic Applications"},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"423","DOI":"10.1093\/restud\/rdu039","article-title":"History, Expectations, and Leadership in the Evolution of Social Norms","volume":"82","author":"Acemoglu","year":"2015","journal-title":"Rev. Econ. Stud."},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"113018","DOI":"10.1088\/1367-2630\/ac3319","article-title":"The dual problems of coordination and anti-coordination on random bipartite graphs","volume":"23","author":"Jones","year":"2021","journal-title":"New J. Phys."},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"502","DOI":"10.1038\/nature04605","article-title":"A simple rule for the evolution of cooperation on graphs and social networks","volume":"441","author":"Ohtsuki","year":"2006","journal-title":"Nature"},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"102340","DOI":"10.1016\/j.isci.2021.102340","article-title":"Random choices facilitate solutions to collective network coloring problems by artificial agents","volume":"24","author":"Jones","year":"2021","journal-title":"iScience"},{"key":"ref_19","doi-asserted-by":"crossref","unstructured":"Rahmani, A., and Mesbahi, M. (2006, January 14\u201316). On the controlled agreement problem. Proceedings of the 2006 American Control Conference, Minneapolis, MN, USA.","DOI":"10.1109\/ACC.2006.1656409"},{"key":"ref_20","doi-asserted-by":"crossref","unstructured":"Mesbahi, M., and Egerstedt, M. (2010). Graph Theoretic Methods in Multiagent Networks, Princeton University Press.","DOI":"10.1515\/9781400835355"},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"97","DOI":"10.1016\/j.physrep.2007.04.004","article-title":"Evolutionary games on graphs","volume":"446","year":"2007","journal-title":"Phys. Rep."},{"key":"ref_22","doi-asserted-by":"crossref","unstructured":"Goyal, S., and Kearns, M. (2012, January 20\u201322). Competitive contagion in networks. Proceedings of the Forty-Fourth Annual ACM Symposium on Theory of Computing, New York, NY, USA.","DOI":"10.1145\/2213977.2214046"},{"key":"ref_23","doi-asserted-by":"crossref","unstructured":"Jafari, S., and Navidi, H. (2018). A Game-Theoretic Approach for Modeling Competitive Diffusion over Social Networks. Games, 9.","DOI":"10.3390\/g9010008"},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"105","DOI":"10.4086\/toc.2015.v011a004","article-title":"Maximizing the Spread of Influence through a Social Network","volume":"11","author":"Kempe","year":"2015","journal-title":"Theory Comput."},{"key":"ref_25","doi-asserted-by":"crossref","unstructured":"Easley, D., and Kleinberg, J. (2010). Networks, Crowds, and Markets: Reasoning About a Highly Connected World, Cambridge University Press.","DOI":"10.1017\/CBO9780511761942"},{"key":"ref_26","unstructured":"Kleinberg, J. (2011). Cascading Behavior in Networks: Algorithmic and Economic Issues. Algorithmic Game Theory, Cambridge University Press."},{"key":"ref_27","doi-asserted-by":"crossref","first-page":"539","DOI":"10.1007\/978-3-642-17572-5_48","article-title":"Threshold Models for Competitive Influence in Social Networks","volume":"Volume 6484","author":"Saberi","year":"2010","journal-title":"Internet and Network Economics"},{"key":"ref_28","doi-asserted-by":"crossref","first-page":"57","DOI":"10.1111\/1467-937X.00121","article-title":"Contagion","volume":"67","author":"Morris","year":"2000","journal-title":"Rev. Econ. Stud."}],"container-title":["Games"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/2073-4336\/15\/6\/41\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,10]],"date-time":"2025-10-10T16:44:30Z","timestamp":1760114670000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/2073-4336\/15\/6\/41"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,12,2]]},"references-count":28,"journal-issue":{"issue":"6","published-online":{"date-parts":[[2024,12]]}},"alternative-id":["g15060041"],"URL":"https:\/\/doi.org\/10.3390\/g15060041","relation":{},"ISSN":["2073-4336"],"issn-type":[{"type":"electronic","value":"2073-4336"}],"subject":[],"published":{"date-parts":[[2024,12,2]]}}}