The price of defense

DOI10.1007/s00453-020-00783-7OpenAlexW3121036260MaRDI QIDQ2663706

Giuseppe Persiano, Anna Philippou, Marios Mavronicolas, Vicky Papadopoulou Lesta, Loizos Michael, Paul G. Spirakis

Publication date: 19 April 2021

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://zenodo.org/record/5620037

zbMATH Keywords

game theorysecurityNash equilibriagraph theoryattacks and defenses

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx) Graph theory (05Cxx)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Worst-case equilibria
• A characterization of the graphs in which the transversal number equals the matching number
• The complexity of computing the permanent
• Defending against multiple different attackers
• A network game with attackers and a defender
• The complexity of uniform Nash equilibria and related regular subgraph problems
• A linear-time algorithm for testing the truth of certain quantified Boolean formulas
• Independence numbers of graphs - an extension of the Koenig-Egervary theorem
• König-Egerváry graphs, 2-bicritical graphs and fractional matchings
• Static search games played over graphs and general metric spaces
• How many attackers can selfish defenders catch?
• Non-cooperative games
• Network Games with and without Synchroneity
• Subgraph characterization of red/blue-split graph and kőnig egerváry graphs
• Equilibrium points in n -person games