Ομιλία από καθηγητή του MIT για Nash Equilibrium 8/1/2010
Posted: Wed Jan 06, 2010 4:48 pm
Το προωθώ όπως μου το παρέδωσε ο κ.Β.Βασσάλος
Ανακοίνωση ομιλίας -
ΠΑΡΑΣΚΕΥΗ 12 το μεσημέρι
> Αγαπητοί συνάδελφοι:
>
> Στα πλαίσια της Σειράς Σεμιναρίων του
Τμήματος μας, θα διεξαχθεί
> την Παρασκευή 8/1ου/2010, ώρα 12.00-13.00
> στην αίθουσα Α41, ομιλία
> του Κωστή Δασκαλάκη, καθηγητή του CSAI Lab.
του ΜΙΤ,
> με τίτλο:
> "On the Complexity of Approximating a Nash Equilibrium"
>
> Ακολουθούν περίληψη της ομιλίας και
σύντομο
> βιογραφικό σημείωμα του ομιλητή.
>
>
> *Abstract*: According to Bob Aumann, strictly competitive games---a
> generalization of zero-sum games---are "one of the few areas in game
> theory,
> and indeed in the social sciences, where a fairly sharp, unique prediction
> is made". We present a generalization of these games to multi-player
> games
> played on a network, where the nodes are players and the edges are
> zero-sum
> games between their endpoints; that is, we are looking at a network of
> competitors. Our generalization of the minmax theorem to the network
> setting
> comes with interesting consequences: convexity of equilibria,
> polynomial-time tractability, and convergence of no-regret algorithms to
> equilibria.
>
>
> Is it then possible to extend our results beyond zero-sum games on the
> edges? Previous work has established that computing exact equilibria is
> computationally intractable and research on approximation algorithms has
> not
> made progress beyond finite values of the approximation. On the other
> hand,
> inapproximability results have been evading current techniques. We provide
> the first inapproximability result for Nash equilibria, for finite values
> of
> relative approximation.
>
>
> *Bio*: Constantinos (or Costis) Daskalakis grew up in Athens, Greece,
> where
> he received an undergraduate degree in Electrical and Computer Engineering
> from the National Technical University of Athens. In 2004 he moved to UC
> Berkeley to pursue doctorate studies in Computer Science under the
> supervision of Prof. Christos Papadimitriou. After completing his
> doctorate
> studies in 2008, he spent a year in Microsoft Research-New England as a
> postdoctoral researcher, and since fall '09 he is an Assistant Professor
> of
> Computer Science at MIT.
>
>
> Daskalakis's research interests lie in Algorithmic Game Theory and Applied
> Probability, particularly in computational aspects of markets and the
> Internet, in social networks, and in computational problems in Biology. He
> has been the recipient of a 2004 UC Regents Fellowship, a 2006 Best
> Student
> paper award in the ACM conference on Electronic Commerce, and a 2007
> Microsoft Research Fellowship in honor of Dean Richard Newton. In 2008,
> the
> Game Theory Society honored Costis, Paul Goldberg and Christos
> Papadimitriou, with the first Game Theory and Computer Science Prize for
> their work on the Computational Complexity of the Nash equilibrium.
> Costis's
> dissertation on the same topic was honored with the 2008 Doctoral
> Dissertation Award by the Association for Computing Machinery (ACM).
>
>
> _______________________________________________
