[PATH] HOME > Invited Speakers

SAGT2010Invited Speakers

SAGT2010 is proud to have the following distinguished scientists for the plenary talks of its scientific program:

SPEAKER 1:

 

Prof. Amos Fiat
Tel Aviv University
ISRAEL
TITLE: When the Players are not Expectation Maximizers

 
ABSTRACT: Much of Game Theory, including the Nash equilibrium concept, is based on the assumption that players are expectation maximizers. It is known that if players are risk averse, games may no longer have Nash equilibria [KS89,Crawford].

We show that

  1. Under risk aversion (convex risk valuations), and for almost all games, there are no mixed Nash equilibria, and thus either there is a pure equilibrium or there are no equilibria at all, and,
  2. For a variety of important valuations other than expectation, it is NP-complete to determine if games between such players have a Nash equilibrium.

 

SPEAKER 2:

 

Prof. Paul W. Goldberg
University of Liverpool
UK
TITLE: How do you like your equilibrium selection problems? Hard, or very hard?

 
ABSTRACT: The PPAD-completeness of Nash equilibrium computation is taken as evidence that the problem is computationally hard in the worst case. This evidence is necessarily rather weak, in the sense that PPAD is only known to lie "between P and NP", and there is not a strong prospect of showing it to be as hard as NP.

Of course, the problem of finding an equilibrium that has certain sought-after properties should be at least as hard as finding an unrestricted one, thus we have for example the NP-hardness of finding equilibria that are socially optimal (or indeed
that have various efficiently checkable properties), the results of Gilboa and Zemel [GZ], and Conitzer and Sandholm [CS]. In the talk I will give an overview of this topic, and a summary of recent progress showing that the equilibria that are found by the Lemke-Howson algorithm, as well as related homotopy methods, are PSPACE-complete to compute. Thus we show that there are no short cuts to the Lemke-Howson solutions, subject only to the hardness of PSPACE. I mention some open problems.