BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Computational Optimisation Group - ECPv6.15.11//NONSGML v1.0//EN
CALSCALE:GREGORIAN
METHOD:PUBLISH
X-WR-CALNAME:Computational Optimisation Group
X-ORIGINAL-URL:http://optimisation.doc.ic.ac.uk
X-WR-CALDESC:Events for Computational Optimisation Group
REFRESH-INTERVAL;VALUE=DURATION:PT1H
X-Robots-Tag:noindex
X-PUBLISHED-TTL:PT1H
BEGIN:VTIMEZONE
TZID:UTC
BEGIN:STANDARD
TZOFFSETFROM:+0000
TZOFFSETTO:+0000
TZNAME:UTC
DTSTART:20120101T000000
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
DTSTART;TZID=UTC:20130522T140000
DTEND;TZID=UTC:20130522T140000
DTSTAMP:20260419T032056
CREATED:20170124T102142Z
LAST-MODIFIED:20170124T102142Z
UID:583-1369231200-1369231200@optimisation.doc.ic.ac.uk
SUMMARY:Seminar: Hard-to-Solve Bimatrix Games
DESCRIPTION:Title: Hard-to-Solve Bimatrix GamesSpeaker: Prof. Bernhard von StengelAffiliation: Depatment of Mathematics – London School of Economics and Political ScienceLocation: CPSE seminar room (C615 Roderic Hill)Time: 2:00pm \nAbstract. A bimatrix game is a two-player game in strategic form\, a 	basic model in game theory. A Nash equilibrium is a pair of 	(possibly randomized) strategies\, one for each player\, so 	that no player can do better by unilaterally changing his or 	her strategy. In this talk\, which will introduce the main 	concepts and geometric tools\, we show that the commonly used 	Lemke-Howson algorithm for finding one equilibrium of a 	bimatrix game is exponential. The algorithm is a pivoting 	method similar to the simplex algorithm for linear 	programming. We present a class of square bimatrix games for 	which the shortest Lemke-Howson path grows exponentially in 	the dimension d of the game. We construct the games using 	pairs of dual cyclic polytopes with 2d facets in d-space. 	The paths are recursively composed so that their lengths 	grow like Fibonacci numbers.  We also mention subsequent 	results and open problems in the area. \nAbout the speaker. Diploma in Mathematics from Aachen\, MSc in Computer Sciences 	at Austin/Texas (student of Edsger W. Dijkstra)\, PhD in 	Passau\, Habilitation in Munich\, Postdoc at Berkeley\, Tilburg 	and ETH Zurich (with a Heisenberg grant)\, at LSE Mathematics 	since 1998. Interested in algorithmic game theory longer 	than the research area has that name.
URL:http://optimisation.doc.ic.ac.uk/event/seminar-hard-to-solve-bimatrix-games/
END:VEVENT
END:VCALENDAR