{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:41:41Z","timestamp":1740109301070,"version":"3.37.3"},"reference-count":41,"publisher":"Springer Science and Business Media LLC","issue":"5","license":[{"start":{"date-parts":[[2021,1,4]],"date-time":"2021-01-04T00:00:00Z","timestamp":1609718400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2021,1,4]],"date-time":"2021-01-04T00:00:00Z","timestamp":1609718400000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/100011199","name":"FP7 Ideas: European Research Council","doi-asserted-by":"publisher","award":["IST-2004-001907","IST-015964"],"award-info":[{"award-number":["IST-2004-001907","IST-015964"]}],"id":[{"id":"10.13039\/100011199","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2021,5]]},"DOI":"10.1007\/s00453-020-00783-7","type":"journal-article","created":{"date-parts":[[2021,1,4]],"date-time":"2021-01-04T16:04:15Z","timestamp":1609776255000},"page":"1256-1315","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["The Price of Defense"],"prefix":"10.1007","volume":"83","author":[{"given":"Marios","family":"Mavronicolas","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Loizos","family":"Michael","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2920-8473","authenticated-orcid":false,"given":"Vicky","family":"Papadopoulou Lesta","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Giuseppe","family":"Persiano","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Anna","family":"Philippou","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Paul G.","family":"Spirakis","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2021,1,4]]},"reference":[{"issue":"3","key":"783_CR1","doi-asserted-by":"publisher","first-page":"121","DOI":"10.1016\/0020-0190(79)90002-4","volume":"8","author":"B Aspvall","year":"1979","unstructured":"Aspvall, B., Plass, M.F., Tarjan, R.E.: A linear-time algorithm for testing the truth of certain quantified boolean formulas. Inf. Process. Lett. 8(3), 121\u2013123 (1979)","journal-title":"Inf. Process. Lett."},{"issue":"1\u20133","key":"783_CR2","doi-asserted-by":"publisher","first-page":"144","DOI":"10.1016\/j.tcs.2008.03.036","volume":"401","author":"V Bonifaci","year":"2008","unstructured":"Bonifaci, V., Di Iorio, U., Laura, L.: The complexity of uniform Nash equilibria and related regular subgraph problems. Theor. Comput. Sci. 401(1\u20133), 144\u2013152 (2008)","journal-title":"Theor. Comput. Sci."},{"issue":"1\u20133","key":"783_CR3","doi-asserted-by":"publisher","first-page":"63","DOI":"10.1016\/0166-218X(92)90273-D","volume":"24","author":"J-M Bourjolly","year":"1989","unstructured":"Bourjolly, J.-M., Pulleyblank, W.R.: K\u00f6nig-Egerv\u00e1ry graphs, 2-bicritical graphs and fractional matchings. Discrete Appl. Math. 24(1\u20133), 63\u201382 (1989)","journal-title":"Discrete Appl. Math."},{"key":"783_CR4","doi-asserted-by":"crossref","unstructured":"Calinescu, G., Kapoor, S., Qiao, K., Shin, J.: Stochastic strategic routing reduces attack effects. In: Proceedings of the IEEE Global Communications Conference, pp. 1\u20135 (2011)","DOI":"10.1109\/GLOCOM.2011.6133863"},{"key":"783_CR5","volume-title":"Firewalls and Internet Security","author":"ER Cheswick","year":"1994","unstructured":"Cheswick, E.R., Bellovin, S.M.: Firewalls and Internet Security. Addison-Wesley, Reading (1994)"},{"key":"783_CR6","doi-asserted-by":"crossref","unstructured":"Dasgupta, A., Ghosh, S., Tixeuil, S.: Selfish stabilization. In: Proceedings of the 8th International Symposium on Stabilization, Safety, and Security of Distributed Systems. Lecture Notes in Computer Science, vol. 4280, pp. 231\u2013243. Springer (2006)","DOI":"10.1007\/978-3-540-49823-0_16"},{"issue":"1","key":"783_CR7","doi-asserted-by":"publisher","first-page":"23","DOI":"10.1016\/0012-365X(79)90066-9","volume":"27","author":"RW Deming","year":"1979","unstructured":"Deming, R.W.: Independence numbers of graphs\u2014an extension of the K\u00f6nig-Egerv\u00e1ry theorem. Discrete Math. 27(1), 23\u201333 (1979)","journal-title":"Discrete Math."},{"key":"783_CR8","first-page":"16","volume":"38","author":"E Egerv\u00e1ry","year":"1931","unstructured":"Egerv\u00e1ry, E.: On combinatorial properties of matrices (in Hungarian with German summary). Matematikai \u00e9s Fizikai Lapok 38, 16\u201328 (1931)","journal-title":"Matematikai \u00e9s Fizikai Lapok"},{"key":"783_CR9","doi-asserted-by":"crossref","unstructured":"Fultz, N., Grossklags, J.: Blue versus red: towards a model of distributed security attacks. In: Proceedings of the 13th International Conference on Financial Cryptography and Data Security. Lecture Notes in Computer Science, vol. 5628, pp. 167\u2013183. Springer (2009)","DOI":"10.1007\/978-3-642-03549-4_10"},{"key":"783_CR10","first-page":"133","volume":"2","author":"T Gallai","year":"1959","unstructured":"Gallai, T.: \u00dcber Extreme Punkt-und Kantenmengen. Annales Universitatis Scientiarum Budapestinensis de Rolando E\u00f6tv\u00f6s Nominatae, Sectio Mathematica 2, 133\u2013138 (1959)","journal-title":"Annales Universitatis Scientiarum Budapestinensis de Rolando E\u00f6tv\u00f6s Nominatae, Sectio Mathematica"},{"key":"783_CR11","volume-title":"Computers and Intractability: A Guide to the Theory of ${\\cal{NP}}$\u2013Completeness","author":"MR Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of ${\\cal{NP}}$\u2013Completeness. W. H. Freeman and Co., New York (1979)"},{"key":"783_CR12","doi-asserted-by":"crossref","unstructured":"Gelastou, M., Mavronicolas, M., Papadopoulou, V., Philippou, A., Spirakis, P.: The power of the defender. In: CD-ROM Proceedings of the 2nd International Workshop on Incentive-Based Computing (2006)","DOI":"10.1109\/ICDCSW.2006.107"},{"key":"783_CR13","doi-asserted-by":"crossref","unstructured":"Ghani, A.T.A., Tanaka, K.: Network games with and without synchroneity. In: Proceedings of the 2nd International Conference in Decision and Game Theory for Security. Lecture Notes in Computer Science, vol. 7037, pp. 87\u2013103. Springer (2011)","DOI":"10.1007\/978-3-642-25280-8_9"},{"issue":"4","key":"783_CR14","doi-asserted-by":"publisher","first-page":"438","DOI":"10.1145\/581271.581274","volume":"5","author":"L Gordon","year":"2002","unstructured":"Gordon, L., Loeb, M.: The economics of information security investment. ACM Trans. Inf. Syst. Secur. 5(4), 438\u2013457 (2002)","journal-title":"ACM Trans. Inf. Syst. Secur."},{"key":"783_CR15","unstructured":"Haifeng, X.: The mysteries of security games: equilibrium computation becomes combinatorial algorithm design. In: Proceedings of the 2016 ACM Conference on Economics and Computation, pp. 497\u2013514 (2016)"},{"issue":"2","key":"783_CR16","doi-asserted-by":"publisher","first-page":"370","DOI":"10.1016\/j.ejor.2010.12.013","volume":"211","author":"K Hausken","year":"2011","unstructured":"Hausken, K., Bier, V.M.: Defending against multiple different attackers. Eur. J. Oper. Res. 211(2), 370\u2013384 (2011)","journal-title":"Eur. J. Oper. Res."},{"key":"783_CR17","doi-asserted-by":"publisher","DOI":"10.1090\/mbk\/101","volume-title":"Game Theory, Alive","author":"AR Karlin","year":"2017","unstructured":"Karlin, A.R., Peres, Y.: Game Theory, Alive. American Mathematical Society, Providence (2017)"},{"key":"783_CR18","unstructured":"Kearns, M., Ortiz, L.: Algorithms for interdependent security games. In: Advances in Neural Information Processing Systems, pp. 561\u2013568. MIT Press (2004)"},{"key":"783_CR19","first-page":"191","volume":"20","author":"L Khachiyan","year":"1979","unstructured":"Khachiyan, L.: A polynomial algorithm in linear programming. Sov. Math. Dokl. 20, 191\u2013194 (1979)","journal-title":"Sov. Math. Dokl."},{"key":"783_CR20","first-page":"116","volume":"38","author":"D K\u00f6nig","year":"1931","unstructured":"K\u00f6nig, D.: Graphen und Matrizen. Matematikai Lapok 38, 116\u2013119 (1931)","journal-title":"Matematikai Lapok"},{"key":"783_CR21","doi-asserted-by":"crossref","unstructured":"Korach, E., Nguyen, T., Peis, B.: Subgraph characterization of red\/blue-split graphs and K\u00f6nig-Egerv\u00e1ry graphs. In: Proceedings of the 17th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 842\u2013850 (2006)","DOI":"10.1145\/1109557.1109650"},{"issue":"2","key":"783_CR22","doi-asserted-by":"publisher","first-page":"65","DOI":"10.1016\/j.cosrev.2009.04.003","volume":"3","author":"E Koutsoupias","year":"2009","unstructured":"Koutsoupias, E., Papadimitriou, C.H.: Worst-case equilibria. Comput. Sci. Rev. 3(2), 65\u201369 (2009)","journal-title":"Comput. Sci. Rev."},{"key":"783_CR23","doi-asserted-by":"crossref","unstructured":"Letchford, J., Conitzer, V.: Solving security games on graphs via marginal probabilities. In: Proceedings of the 27th AAAI Conference on Artificial Intelligence pp. 591\u2013597 (2013)","DOI":"10.1609\/aaai.v27i1.8688"},{"issue":"1","key":"783_CR24","doi-asserted-by":"publisher","first-page":"71","DOI":"10.1007\/s10207-004-0060-x","volume":"4","author":"K Lye","year":"2005","unstructured":"Lye, K., Wing, J.: Game strategies in network security. Int. J. Inf. Secur. 4(1), 71\u201386 (2005)","journal-title":"Int. J. Inf. Secur."},{"issue":"1","key":"783_CR25","doi-asserted-by":"publisher","first-page":"78","DOI":"10.1145\/1053283.1053288","volume":"8","author":"P Liu","year":"2005","unstructured":"Liu, P., Zang, W., Yu, M.: Incentive-based modeling and inference of attacker intent, objectives, and strategies. ACM Trans. Inf. Syst. Secur. 8(1), 78\u2013118 (2005)","journal-title":"ACM Trans. Inf. Syst. Secur."},{"key":"783_CR26","doi-asserted-by":"crossref","unstructured":"Markham, T., Payne, C.: Security at the network edge: a distributed firewall architecture. In: Proceedings of the 2nd DARPA Information Survivability Conference and Exposition, vol. 1, pp. 279\u2013286 (2001)","DOI":"10.1109\/DISCEX.2001.932222"},{"issue":"16\u201317","key":"783_CR27","doi-asserted-by":"publisher","first-page":"2563","DOI":"10.1016\/j.dam.2013.05.022","volume":"161","author":"M Mavronicolas","year":"2013","unstructured":"Mavronicolas, M., Monien, B., Papadopoulou, V.G.: How many attackers can selfish defenders catch? Discrete Appl. Math. 161(16\u201317), 2563\u20132586 (2013)","journal-title":"Discrete Appl. Math."},{"issue":"3","key":"783_CR28","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.G., Philippou, A., Spirakis, P.G.: A network game with attackers and a defender. Algorithmica 51(3), 315\u2013341 (2008)","journal-title":"Algorithmica"},{"issue":"4","key":"783_CR29","doi-asserted-by":"publisher","first-page":"390","DOI":"10.1504\/IJAACS.2008.021488","volume":"1","author":"M Mavronicolas","year":"2008","unstructured":"Mavronicolas, M., Papadopoulou, V.G., Philippou, A., Spirakis, P.G.: A graph-theoretic network security game. Int. J. Auton. Adapt. Commun. Spec. Issue Algorithmic Game Theory 1(4), 390\u2013410 (2008)","journal-title":"Int. J. Auton. Adapt. Commun. Spec. Issue Algorithmic Game Theory"},{"key":"783_CR30","doi-asserted-by":"publisher","DOI":"10.1093\/acprof:oso\/9780199233212.001.0001","volume-title":"The Nature of Computation","author":"C Moore","year":"2011","unstructured":"Moore, C., Mertens, S.: The Nature of Computation. Oxford University Press, Oxford (2011)"},{"key":"783_CR31","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. Proc. Natl. Acad. Sci. USA 36, 48\u201349 (1950)","journal-title":"Proc. Natl. Acad. Sci. USA"},{"issue":"2","key":"783_CR32","doi-asserted-by":"publisher","first-page":"286","DOI":"10.2307\/1969529","volume":"54","author":"JF Nash","year":"1951","unstructured":"Nash, J.F.: Non-cooperative games. Ann. Math. 54(2), 286\u2013295 (1951)","journal-title":"Ann. Math."},{"key":"783_CR33","unstructured":"Okamoto, S., Hazon, N., Sycara, K.: Solving non-zero-sum multiagent network flow security games with attack costs. In: Proceedings of the 11th International Conference on Autonomous Agents and Multiagent Systems, pp. 879\u2013888 (2012)"},{"key":"783_CR34","doi-asserted-by":"publisher","first-page":"667","DOI":"10.1016\/j.ejor.2013.06.024","volume":"231","author":"T Ol\u00e1ron Evans","year":"2013","unstructured":"Ol\u00e1ron Evans, T., Bishop, S.R.: Static search games played over graphs and general metric spaces. Eur. J. Oper. Res. 231, 667\u2013689 (2013)","journal-title":"Eur. J. Oper. Res."},{"key":"783_CR35","unstructured":"Scheinerman, E.R., Ullman, D. H.: Fractional Graph Theory, Wiley-Interscience Series in Discrete Mathematics and Optimization (1997)"},{"issue":"2","key":"783_CR36","doi-asserted-by":"publisher","first-page":"228","DOI":"10.1016\/0095-8956(79)90085-6","volume":"27","author":"F Sterboul","year":"1979","unstructured":"Sterboul, F.: A characterization of the graphs in which the transversal number equals the matching number. J. Comb. Theory (Ser. B) 27(2), 228\u2013229 (1979)","journal-title":"J. Comb. Theory (Ser. B)"},{"key":"783_CR37","doi-asserted-by":"crossref","unstructured":"Tsai, J., Yin, Z., Kwak, J., Kempe, D., Kiekintveld, C., Tambe, M.: Urban security: game-theoretic resource allocation in networked physical domains. In: Proceedings of the 24th AAAI Conference on Artificial Intelligence, p. 881 (2010)","DOI":"10.1609\/aaai.v24i1.7612"},{"key":"783_CR38","unstructured":"Tsai, J., Yin, Z., Kwak, J., Kempe, D., Kiekintveld, C., Tambe, M.: Game-theoretic allocation of security forces in a city. In: Proceeding of the 3th International Workshop on Optimisation in Multi-agent Systems (OPTMAS III) (2010)"},{"issue":"2","key":"783_CR39","doi-asserted-by":"publisher","first-page":"189","DOI":"10.1016\/0304-3975(79)90044-6","volume":"8","author":"LG Valiant","year":"1979","unstructured":"Valiant, L.G.: The complexity of computing the permanent. Theor. Comput. Sci. 8(2), 189\u2013201 (1979)","journal-title":"Theor. Comput. Sci."},{"key":"783_CR40","doi-asserted-by":"publisher","first-page":"295","DOI":"10.1007\/BF01448847","volume":"100","author":"J von Neumann","year":"1928","unstructured":"von Neumann, J.: Zur Theorie der Gesellschaftsspiele. Math. Ann. 100, 295\u2013320 (1928)","journal-title":"Math. Ann."},{"key":"783_CR41","volume-title":"Introduction to Graph Theory","author":"DB West","year":"2001","unstructured":"West, D.B.: Introduction to Graph Theory, 2nd edn. Prentice Hall, Upper Saddle River (2001)","edition":"2"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-020-00783-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-020-00783-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-020-00783-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,8,20]],"date-time":"2024-08-20T18:39:42Z","timestamp":1724179182000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-020-00783-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,1,4]]},"references-count":41,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2021,5]]}},"alternative-id":["783"],"URL":"https:\/\/doi.org\/10.1007\/s00453-020-00783-7","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2021,1,4]]},"assertion":[{"value":"5 September 2018","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"4 November 2020","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"4 January 2021","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}