Subject: [[email-masked]: 6/2/94 B. von Stengel ICSI Talk / Exponentially Faster Algorithms for Solving Extensive Games]

From: [email-masked] (Barney Pell)
Date: Thu, 26 May 94 16:32:56 PDT

To: [email-masked], [email-masked]
Subject: 6/2/94 B. von Stengel ICSI Talk / Exponentially Faster Algorithms for Solving Extensive Games

              The International Computer Science Institute
                     is pleased to present a talk:

                   Thursday, June 2, 1994  2:00 p.m.

                          BERNHARD VON STENGEL
               University of Fed. Armed Forces at Munich
                                GERMANY
                      [email-masked]

      "Exponentially Faster Algorithms for Solving Extensive Games"

           Game trees  (called  extensive  games)  are  convenient
      modeling  tools,  but  their  use was limited since solution
      methods were prohibitively slow.  We present a new strategic
      description  for an extensive game that overcomes this prob-
      lem. Assuming "perfect recall", this  description  allows  a
      direct representation and efficient computation of "behavior
      strategies".  It is similar to the previously known "normal"
      strategic  form  but  has LINEAR instead of exponential com-
      plexity.  The equilibria of the game are the solutions to  a
      corresponding  small  a  linear program (LP) for two players
      and zero-sum payoffs, and to a linear complementarity  prob-
      lem (LCP) for general payoffs.

           This is  joint  work  with  Daphne  Koller  and  Nimrod
      Megiddo.

        This talk will be held in the Main Lecture Hall at ICSI.
          1947 Center Street, Sixth Floor, Berkeley, CA 94704
       (On Center between Milvia and Martin Luther King Jr. Way)

       ----------------------------------------------------------
       Requests to be added to or deleted from the "talk" mailing
       list should be directed to [email-masked].
       ----------------------------------------------------------
+----------------------------------------------------------------------------+
| To get removed from this mailing list (colloq-all), send your request      |
| to [email-masked]. See the weekly summary for more info.   |
+----------------------------------------------------------------------------+