BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//talks.cam.ac.uk//v3//EN
BEGIN:VTIMEZONE
TZID:Europe/London
BEGIN:DAYLIGHT
TZOFFSETFROM:+0000
TZOFFSETTO:+0100
TZNAME:BST
DTSTART:19700329T010000
RRULE:FREQ=YEARLY;BYMONTH=3;BYDAY=-1SU
END:DAYLIGHT
BEGIN:STANDARD
TZOFFSETFROM:+0100
TZOFFSETTO:+0000
TZNAME:GMT
DTSTART:19701025T020000
RRULE:FREQ=YEARLY;BYMONTH=10;BYDAY=-1SU
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
CATEGORIES:Optimization and Incentives Seminar
SUMMARY:Pathways to Equilibria\, Pretty Pictures and Diagr
ams (PPAD) - Bernhard von Stengel (LSE)
DTSTART;TZID=Europe/London:20121119T150000
DTEND;TZID=Europe/London:20121119T160000
UID:TALK40928AThttp://talks.cam.ac.uk
URL:http://talks.cam.ac.uk/talk/index/40928
DESCRIPTION:Existence of an equilibrium in various economic mo
dels can be shown by following a certain combinato
rially defined path\, for example of edges of a la
beled polytope similar to the simplex algorithm fo
r linear programming. In addition\, such a path h
as a direction that defines the ``index'' of an eq
uilibrium. Examples include Sperner's lemma about
completely labeled simplices and Nash equilibria i
n games. We present a general model of "pivoting s
ystems" that shows the essence of the path-followi
ng and the directedness argument. We also present
a connection of bimatrix games where the paths are
exponentially long with signed perfect matchings
in Euler graphs\, and an algorithm that gives a po
lynomial-time "shortcut" for these paths. We also
present a concept of orientation for the "Euler c
omplexes" recently introduced by Edmonds\, which g
eneralizes the orientability of abstract simplicia
l manifolds. Our exposition uses colorful picture
s and examples wherever possible.\n\n(Joint work w
ith Marta Maria Casetti\, Julian Merschen and Lasz
lo Vegh.)\n
LOCATION:MR12\, Centre for Mathematical Sciences\, Wilberfo
rce Road\, Cambridge
CONTACT:Felix Fischer
END:VEVENT
END:VCALENDAR