BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//University of Liverpool Computer Science Seminar System//v2//EN
BEGIN:VEVENT
DTSTAMP:20260922T051857Z
UID:Seminar-EcCo-596@lxserverM.csc.liv.ac.uk
ORGANIZER:CN=Nicos 	Protopapas:MAILTO:N.Protopapas@liverpool.ac.uk
DTSTART:20190313T130000
DTEND:20190313T140000
SUMMARY:Economics and Computation Series
DESCRIPTION:Paul Spirakis: The Price of Defence\n\nWe examine here a game on a graph G(V,E) between ? attacker players and a single defender. Each attacker selects (as a pure strategy) a vertex ; the defender selects an edge. The defender seeks to maximize the number of attackers he catches. The Price of Defence (PoD) is the worst case ratio over all Nash Equilibria of ? divided by the expected utility of the defender at the Nash Equilibrium. We show a lower bound of n/2 (n is the number of vertices in G) for PoD. We characterize the defence-optimal graphs and show that they can be efficiently recognized. We define several classes of Nash Equilibria by imposing structure on players randomized strategies. We show trade-offs between the computational complexity of such equilibria and their price of defence.\n\nThis is joint work with M. Mavronicolas, L. Michael, V. Papapdopoulou Lesta, A. Philippou, and G. Persiano.\n\nhttps://www.csc.liv.ac.uk/research/seminars/abstract.php?id=596
LOCATION:
END:VEVENT
END:VCALENDAR