BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//jEvents 2.0 for Joomla//EN
CALSCALE:GREGORIAN
METHOD:PUBLISH
BEGIN:VEVENT
UID:ebcf93d1a8398ee6647998d1ad1e370f
CATEGORIES:Lectures & Presentations
CREATED:20170203T120247
SUMMARY:Guest Talk: "Exact Algorithms for Stochastic Games and Polynomial System Solving"
LOCATION:SBA Research\, Vienna
DESCRIPTION;ENCODING=QUOTED-PRINTABLE:Elias Tsigaridas, POLSYS team, INRIA Paris, France, is giving a guest talk
about "Exact Algorithms for Stochastic Games and Polynomial System Solving"
.\nAbstract: Shapley introduced stochastic games in 1953 and since then the
y are a subject of intensive study. They model dynamic interactions in an e
nvironment that changes in response to the behavior of the players. Their a
pplications include industrial organization, resource economics, market gam
es, communication networks.\nIn this context Shapley's discounted stochasti
c games are classical models of game theory describing two-player zero-sum
games of potentially infinite duration. For these games we can express the
equilibrium strategies and the payoffs of the players using systems of poly
nomial equations and inequalities.\nWe present an exact algorithm for solvi
ng such games based on the properties of polynomial system solving. When t
he number of positions of the game is constant, the algorithm runs in polyn
omial time and is the first with this property.\nIf time permits, we will a
lso present lower bounds on the algebraic degree of the values of stochasti
c games, induced from the irreducibility of polynomials that have coefficie
nts that depend on the combinatorial parameters of the games, based on a ge
neralization of Eisenstein criterion.\nJoint work with K.A. Hansen, M. Kouc
ky, N. Lauritzen, and P.B. Miltersen.\nThis event is hosted by the IEEE CS/
SMCS Austria Chapter.\n
CONTACT:Bettina Bauer
X-EXTRAINFO:11/06
DTSTAMP:20211201T115124Z
DTSTART:20161213T150000Z
DTEND:20161213T163000Z
SEQUENCE:0
TRANSP:OPAQUE
END:VEVENT
END:VCALENDAR