{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:42:00Z","timestamp":1740109320961,"version":"3.37.3"},"reference-count":20,"publisher":"Springer Science and Business Media LLC","issue":"11","license":[{"start":{"date-parts":[[2021,8,1]],"date-time":"2021-08-01T00:00:00Z","timestamp":1627776000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2021,8,1]],"date-time":"2021-08-01T00:00:00Z","timestamp":1627776000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100000266","name":"Engineering and Physical Sciences Research Council","doi-asserted-by":"publisher","award":["EP\/P02002X\/1"],"award-info":[{"award-number":["EP\/P02002X\/1"]}],"id":[{"id":"10.13039\/501100000266","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2021,11]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We study a security game over a network played between a<jats:italic>defender<\/jats:italic>and<jats:italic>k<\/jats:italic><jats:italic>attackers<\/jats:italic>. Every attacker chooses, probabilistically, a node of the network to damage. The defender chooses, probabilistically as well, a connected induced subgraph of the network of<jats:inline-formula><jats:alternatives><jats:tex-math>$$\\lambda $$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mi>\u03bb<\/mml:mi><\/mml:math><\/jats:alternatives><\/jats:inline-formula>nodes to scan and clean. Each attacker wishes to maximize the probability of escaping her cleaning by the defender. On the other hand, the goal of the defender is to maximize the expected number of attackers that she catches. This game is a generalization of the model from the seminal paper of Mavronicolas et al. Mavronicolas et al. (in: International symposium on mathematical foundations of computer science, MFCS, pp 717\u2013728, 2006). We are interested in Nash equilibria of this game, as well as in characterizing<jats:italic>defense-optimal<\/jats:italic>networks which allow for the best<jats:italic>equilibrium defense ratio<\/jats:italic>; this is the ratio of<jats:italic>k<\/jats:italic>over the expected number of attackers that the defender catches in equilibrium. We provide a characterization of the Nash equilibria of this game and defense-optimal networks. The equilibrium characterizations allow us to show that even if the attackers are centrally controlled the equilibria of the game remain the same. In addition, we give an algorithm for computing Nash equilibria. Our algorithm requires exponential time in the worst case, but it is polynomial-time for<jats:inline-formula><jats:alternatives><jats:tex-math>$$\\lambda $$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mi>\u03bb<\/mml:mi><\/mml:math><\/jats:alternatives><\/jats:inline-formula>constantly close to 1 or<jats:italic>n<\/jats:italic>. For the special case of tree-networks, we further refine our characterization which allows us to derive a polynomial-time algorithm for deciding whether a tree is defense-optimal and if this is the case it computes a defense-optimal Nash equilibrium. On the other hand, we prove that it is<jats:inline-formula><jats:alternatives><jats:tex-math>$${\\mathtt {NP}}$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mi>NP<\/mml:mi><\/mml:math><\/jats:alternatives><\/jats:inline-formula>-hard to find a best-defense strategy if the tree is not defense-optimal. We complement this negative result with a polynomial-time constant-approximation algorithm that computes solutions that are close to optimal ones for general graphs. Finally, we provide asymptotically (almost) tight bounds for the<jats:italic>Price of Defense<\/jats:italic>for any<jats:inline-formula><jats:alternatives><jats:tex-math>$$\\lambda $$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mi>\u03bb<\/mml:mi><\/mml:math><\/jats:alternatives><\/jats:inline-formula>; this is the worst equilibrium defense ratio over all graphs.<\/jats:p>","DOI":"10.1007\/s00453-021-00858-z","type":"journal-article","created":{"date-parts":[[2021,8,1]],"date-time":"2021-08-01T02:02:19Z","timestamp":1627783339000},"page":"3403-3431","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Connected Subgraph Defense Games"],"prefix":"10.1007","volume":"83","author":[{"given":"Eleni C.","family":"Akrida","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6513-6748","authenticated-orcid":false,"given":"Argyrios","family":"Deligkas","sequence":"additional","affiliation":[]},{"given":"Themistoklis","family":"Melissourgos","sequence":"additional","affiliation":[]},{"given":"Paul G.","family":"Spirakis","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2021,8,1]]},"reference":[{"key":"858_CR1","doi-asserted-by":"crossref","unstructured":"Akrida, E.C., Deligkas, A., Melissourgos, T., Spirakis, P.G.: Connected subgraph defense games. In: International Symposium on Algorithmic Game Theory, pp. 216\u2013236. SAGT (2019)","DOI":"10.1007\/978-3-030-30473-7_15"},{"issue":"1","key":"858_CR2","doi-asserted-by":"publisher","first-page":"78","DOI":"10.1137\/S0097539792224474","volume":"24","author":"N Alon","year":"1995","unstructured":"Alon, N., Karp, R.M., Peleg, D., West, D.B.: A graph-theoretic game and its application to the k-server problem. SIAM J. Comput. 24(1), 78\u2013100 (1995)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"858_CR3","doi-asserted-by":"publisher","first-page":"31","DOI":"10.1145\/1978721.1978729","volume":"10","author":"B An","year":"2011","unstructured":"An, B., Pita, J., Shieh, E., Tambe, M., Kiekintveld, C., Marecki, J.: Guards and protect: Next generation applications of security games. ACM SIGecom Exchanges 10(1), 31\u201334 (2011)","journal-title":"ACM SIGecom Exchanges"},{"issue":"6","key":"858_CR4","doi-asserted-by":"publisher","first-page":"1077","DOI":"10.1016\/j.jcss.2006.02.003","volume":"72","author":"J Aspnes","year":"2006","unstructured":"Aspnes, J., Chang, K.L., Yampolskiy, A.: Inoculation strategies for victims of viruses and the sum-of-squares partition problem. J. Comput. Syst. Sci. 72(6), 1077\u20131093 (2006)","journal-title":"J. Comput. Syst. Sci."},{"key":"858_CR5","doi-asserted-by":"publisher","DOI":"10.1002\/0471478210","volume-title":"Distributed Computing: Fundamentals, Simulations and Advanced Topics","author":"H Attiya","year":"2004","unstructured":"Attiya, H., Welch, J.: Distributed Computing: Fundamentals, Simulations and Advanced Topics. Wiley, Hoboken (2004)"},{"key":"858_CR6","volume-title":"Firewalls and Internet Security: Repelling the Wily Hacker","author":"WR Cheswick","year":"2003","unstructured":"Cheswick, W.R., Bellovin, S.M., Rubin, A.D.: Firewalls and Internet Security: Repelling the Wily Hacker. Addison-Wesley Longman Publishing Co., Inc, Boston, MA, USA, 2 edn. (2003)","edition":"2"},{"issue":"2","key":"858_CR7","doi-asserted-by":"publisher","first-page":"225","DOI":"10.1145\/333979.333980","volume":"47","author":"MK Franklin","year":"2000","unstructured":"Franklin, M.K., Galil, Z., Yung, M.: Eavesdropping games: a graph-theoretic approach to privacy in distributed systems. J. ACM 47(2), 225\u2013243 (2000)","journal-title":"J. ACM"},{"key":"858_CR8","unstructured":"Jain, M., Conitzer, V., Tambe, M.: Security scheduling for real-world networks. In: International Conference on Autonomous Agents and Multi-agent Systems, pp. 215\u2013222. AAMAS (2013)"},{"key":"858_CR9","unstructured":"Kearns, M.J., Ortiz, L.E.: Algorithms for interdependent security games. In: Advances in Neural Information Processing Systems, pp. 561\u2013568. NeurIPS (2003)"},{"key":"858_CR10","doi-asserted-by":"crossref","unstructured":"Letchford, J., Conitzer, V.: Solving security games on graphs via marginal probabilities. In: desJardins, M., Littman, M.L. (eds.) Conference on Artificial Intelligence, pp. 591\u2013597. AAAI (2013)","DOI":"10.1609\/aaai.v27i1.8688"},{"key":"858_CR11","doi-asserted-by":"crossref","unstructured":"Mavronicolas, M., Michael, L., Papadopoulou, V.G., Philippou, A., Spirakis, P.G.: The price of defense. In: International Symposium on Mathematical Foundations of Computer Science, pp. 717\u2013728. MFCS (2006)","DOI":"10.1007\/11821069_62"},{"issue":"3","key":"858_CR12","doi-asserted-by":"publisher","first-page":"315","DOI":"10.1007\/s00453-007-9109-3","volume":"51","author":"M Mavronicolas","year":"2008","unstructured":"Mavronicolas, M., Papadopoulou, V., Philippou, A., Spirakis, P.G.: A network game with attackers and a defender. Algorithmica 51(3), 315\u2013341 (2008)","journal-title":"Algorithmica"},{"key":"858_CR13","doi-asserted-by":"crossref","unstructured":"Mavronicolas, M., Papadopoulou, V.G., Persiano, G., Philippou, A., Spirakis, P.G.: The price of defense and fractional matchings. In: 8th International Conference on Distributed Computing and Networking, pp. 115\u2013126. ICDCN (2006)","DOI":"10.1007\/11947950_13"},{"key":"858_CR14","doi-asserted-by":"crossref","unstructured":"Mavronicolas, M., Papadopoulou, V.G., Philippou, A., Spirakis, P.G.: A graph-theoretic network security game. In: Internet and Network Economics, pp. 969\u2013978. WINE (2005)","DOI":"10.1007\/11600930_98"},{"issue":"1","key":"858_CR15","doi-asserted-by":"publisher","first-page":"48","DOI":"10.1073\/pnas.36.1.48","volume":"36","author":"JF Nash","year":"1950","unstructured":"Nash, J.F.: Equilibrium points in n-person games. Proceedings of the National Academy of Sciences 36(1), 48\u201349 (1950)","journal-title":"Proc. Natl. Acad. Sci."},{"issue":"2","key":"858_CR16","doi-asserted-by":"publisher","first-page":"286","DOI":"10.2307\/1969529","volume":"54","author":"J Nash","year":"1951","unstructured":"Nash, J.: Non-cooperative games. Annals of Mathematics 54(2), 286\u2013295 (1951)","journal-title":"Ann. Math."},{"issue":"6","key":"858_CR17","doi-asserted-by":"publisher","first-page":"678","DOI":"10.1145\/63526.63527","volume":"32","author":"EH Spafford","year":"1989","unstructured":"Spafford, E.H.: The internet worm: Crisis and aftermath. Commun. ACM 32(6), 678\u2013687 (1989)","journal-title":"Commun. ACM"},{"key":"858_CR18","volume-title":"Cryptography and Network Security-Principles and Practice","author":"W Stallings","year":"2003","unstructured":"Stallings, W.: Cryptography and Network Security-Principles and Practice, 3rd edn. Prentice Hall, Hoboken (2003).","edition":"3"},{"key":"858_CR19","unstructured":"Van\u011bk, O., Yin, Z., Jain, M., Bo\u0161ansk\u1ef3, B., Tambe, M., P\u011bchou\u010dek, M.: Game-theoretic resource allocation for malicious packet detection in computer networks. In: International Conference on Autonomous Agents and Multiagent Systems, pp. 905\u2013912. AAMAS (2012)"},{"key":"858_CR20","doi-asserted-by":"crossref","unstructured":"Xu, H.: The mysteries of security games: Equilibrium computation becomes combinatorial algorithm design. In: ACM Conference on Economics and Computation, pp. 497\u2013514. EC (2016)","DOI":"10.1145\/2940716.2940796"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-021-00858-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-021-00858-z\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-021-00858-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,1,6]],"date-time":"2023-01-06T01:43:29Z","timestamp":1672969409000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-021-00858-z"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,8,1]]},"references-count":20,"journal-issue":{"issue":"11","published-print":{"date-parts":[[2021,11]]}},"alternative-id":["858"],"URL":"https:\/\/doi.org\/10.1007\/s00453-021-00858-z","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2021,8,1]]},"assertion":[{"value":"20 July 2019","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"16 July 2021","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"1 August 2021","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}