BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//University of Liverpool Computer Science Seminar System//v2//EN
BEGIN:VEVENT
DTSTAMP:20260911T194838Z
UID:Seminar-EcCo-605@lxserverM.csc.liv.ac.uk
ORGANIZER:CN=Nicos 	Protopapas:MAILTO:N.Protopapas@liverpool.ac.uk
DTSTART:20190612T130000
DTEND:20190612T140000
SUMMARY:Economics and Computation Series
DESCRIPTION:Rahul Savani: Finding Nash equilibria of Tree Polymatrix Games\n\nPolymatrix games provide a succinct representation of many-player games. In a polymatrix game, a player's payoff is the sum of payoffs from pairwise interactions with other players. The game's interaction graph encodes which players interact with each other.\nThe problem of finding one Nash equilibrium of a polymatrix games is known to be PPAD-complete (i.e., of high complexity) for:\n- degree 3 bipartite interaction graphs with 2 actions per player [Rubinstein 2016]; \n- degree 3 graphs with constant pathwidth and 2 actions per player [Elkind Goldberg Goldberg 2006].\nWe show that the problem is PPAD-hard for tree (actually caterpillar) interaction graphs. \n\nJoint work with Argyrios Deligkas and John Fearnley.\n\nhttps://www.csc.liv.ac.uk/research/seminars/abstract.php?id=605
LOCATION:
END:VEVENT
END:VCALENDAR