BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Talks.cam//talks.cam.ac.uk//
X-WR-CALNAME:Talks.cam
BEGIN:VEVENT
SUMMARY:Pathways to Equilibria\, Pretty Pictures and Diagrams (PPAD) - Ber
 nhard von Stengel (LSE)
DTSTART:20121119T150000Z
DTEND:20121119T160000Z
UID:TALK40928@talks.cam.ac.uk
CONTACT:Felix Fischer
DESCRIPTION:Existence of an equilibrium in various economic models can be 
 shown by following a certain combinatorially defined path\, for example of
  edges of a labeled polytope similar to the simplex algorithm for linear p
 rogramming.  In addition\, such a path has a direction that defines the ``
 index'' of an equilibrium. Examples include Sperner's lemma about complete
 ly labeled simplices and Nash equilibria in games. We present a general mo
 del of "pivoting systems" that shows the essence of the path-following and
  the directedness argument. We also present a connection of bimatrix games
  where the paths are exponentially long with signed perfect matchings in E
 uler graphs\, and an algorithm that gives a polynomial-time "shortcut" for
  these paths.  We also present a concept of orientation for the "Euler com
 plexes" recently introduced by Edmonds\, which generalizes the orientabili
 ty of abstract simplicial manifolds.  Our exposition uses colorful picture
 s and examples wherever possible.\n\n(Joint work with Marta Maria Casetti\
 , Julian Merschen and Laszlo Vegh.)\n
LOCATION:MR12\, Centre for Mathematical Sciences\, Wilberforce Road\, Camb
 ridge
END:VEVENT
END:VCALENDAR