We are pleased to announce that the following paper has been accepted
for publication at the first Symposium on Algorithmic Game Theory (SAGT
2008) that will take place at Paderborn, Germany from April 30th to May 2nd.
Sébastien Hémon, Miklos Santha and Michel de Rougemont. Approximate Nash
Equilibria for multi-players Games.
http://publis.lrde.epita.fr/2008-01-18-SAGT
We consider Games of complete information with r players, and study the
existence of polynomial time algorithms for \eps-approximate Nash
equilibria in the additive and multiplicative sense. For the additive
approximation, we prove an \frac{r-1}{r} lower bound on \eps for
strategies using a support less than \sqrt[r-1]{\log{n}} where n is the
maximum number of pure strategies, and give a polynomial time algorithm
which computes an \frac{r-1}{r}-approximate Equilibrium. For the
multiplicative approximation, we prove a Lipton-result to approximate a
Nash Equilibrium. If we assume that the gains of the players at a Nash
Equilibrium are greater than a value g, we find an \eps-approximate Nash
equilibrium whose support is included in the support of the Nash
equilibrium of size \frac{\log n.r}{g.\eps^2}. We exhibit a class of
games where this hypothesis does not hold and where the support size of
such an \eps-approximate Nash equilibrium is greater than
\frac{n}{2.(1+\eps)}.
--
Daniela Becker
Chers collègues,
la prochaine session du séminaire Performance et Généricité du LRDE
(Laboratoire de Recherche et Développement de l'EPITA) aura lieu le
30 Janvier.
Au programme:
* 14h: Robustesse, efficacité et généricité dans la bibliothèque CGAL
Sylvain Pion, chargé de recherche, INRIA Sophia Antipolis
* 15h15: Morph-M et généricité en traitement d'images
Romain Lerallut, ingénieur R&D chez A2iA
Raffi Enficiaud, ingénieur de recherche chez DxO Labs
L'entrée du séminaire est libre.
Pour plus de renseignements, consultez http://seminaire.lrde.epita.fr/.
Merci de bien vouloir diffuser cette information le plus largement possible.
--
Didier Verna, didier(a)lrde.epita.fr, http://www.lrde.epita.fr/~didier
EPITA / LRDE, 14-16 rue Voltaire Tel.+33 (0)1 44 08 01 85
94276 Le Kremlin-Bicêtre, France Fax.+33 (0)1 53 14 59 22 didier(a)xemacs.org
Bonjour,
Vous êtes tous cordialement invités à assister au séminaire qui aura
lieu le mercredi 16 janvier 2008 à 14 heures en Amphi Masters (KB).
-----------------------------------------------------------------------
Le programme :
*Transformers, Théorie des Jeux & Vérification du locuteur*
http://www.lrde.epita.fr/cgi-bin/twiki/view/Publications/Seminar-2008-01-16
TRANSFORMERS
14h00 : revCPP : Un préprocesseur C++ réversible -- Quentin Hocquet
14h30 : Transformation de programmes en syntaxe concrète en C++ --
Benoit Sigoure
15h00 : Propagation automatique des attributs pour des grammaires
attribuées modulaires -- Nicolas Pierron
15h30 : Désambiguïsation guidée par la sémantique: Comparaison de
différentes méthodes -- Renaud Durlin
THEORIE DES JEUX
16h15 : La tablette de chocolat transfinie -- Nicolas Neri
VERIFICATION DU LOCUTEUR
16h45 : Combinaison de noyaux à partir de systèmes SVM en vérification
du locuteur -- Charles Alban Deledalle
-----------------------------------------------------------------------
Les Résumés des exposés :
**************************
TRANSFORMERS
revCPP : Un préprocesseur C++ réversible -- Quentin Hocquet
Le but du projet Transformers est de créer un framework générique pour
de la transformation source à source de code C++. Une transformation
"source à source" consiste à retravailler le code et produire un fichier
de code source modifié. Ce code peut être relu, ré-utilisé, modifié ...
par des programmeurs et doit donc être lisible. De plus, il doit
respecter le coding style d'origine. Ce processus de préservation de la
mise en page est appelé "High fidelity program transformation".
Transformers cible les langages C et C++. Contrairement à de nombreux
langages, le C++ est un langage préprocessé pour obtenir le code source
effectif. Dans le contexte de la transformation de programmes, il faut
dé-préprocesser le code pour le rendre lisible au programmeur. Ce
document présente le travail de recherche que nous avons mené pour
implémenter un préprocesseur de C++ réversible et un postprocesseur,
c'est-à-dire un outil permettant d'obtenir le code d'origine à partir du
code préprocessé.
Transformation de programmes en syntaxe concrète en C++ -- Benoit Sigoure
La transformation de programmes dans des langages généralistes tels que
le C++ est fastidieuse car elle nécessite de manipuler l'AST du
programme transform en syntaxe abstraite (c'est-à-dire dans le langage
hôte, ici le C++). Le code à écrire est lourd et coûteux à maintenir.
Le but de ce séminaire est de présenter la mise en œuvre de nouvelles
techniques de transformation de programmes en syntaxe concrète
(c'est-à-dire utilisant directement le langage du programme transformé)
dans un environnement C++ standard. Notre approche utilise l'analyseur
syntaxique l'exécution pour appliquer des règles de transformation
dynamiques. Un compilateur de Tiger servira de support à la présentation.
Propagation automatique des attributs pour des grammaires attribuées
modulaires -- Nicolas Pierron
Les grammaires attribuées sont plus adaptées pour décrire (des parties
de) la sémantique d'un langage de programmation : accrochées sur les
règles de production syntaxique, elles permettent d'exprimer des
relations locales qui sont par la suite liées entre elles globalement
par un évaluateur générique. Cependant elles ne passent pas à l'échelle
quand on travaille avec des langages volumineux et complexes.
Premièrement les attributs qui sont requis quasiment partout ont besoin
d'être véhiculés par chaque règle de production. Deuxièmement, ces
contraintes cassent la modularité car le fait d'étendre une grammaire
nécessite la propagation des nouveaux attributs à travers le reste du
langage. Ce papier montre comment résoudre ces problèmes en introduisant
un système de propagation automatique des attributs qui complète
l'ensemble des règles sémantiques. Nous avons défini formellement les
contraintes de propagations de manière optimisée afin d'éviter l'ajout
de règles sémantiques inutiles. Ainsi les grammaires attribuées sont
devenus plus maintenables, modulaires et facile à utiliser.
Désambiguïsation guidée par la sémantique: Comparaison de différentes
méthodes -- Renaud Durlin
Modularité, extensibilité et expressivité, trois aspects fondamentaux
pour un système de désambiguïsation. La désambiguïsation est l'étape
survenant juste après l'analyse syntaxique qui consiste à analyser la
sortie obtenue lors de l'utilisation d'un parseur LR généralisé. Le but
de cette étape étant de sélectionner, parmi toute une forêt, l'unique
arbre valide correspondant à l'entrée en prenant en compte les règles de
sémantique contextuelles. Au travers d'une comparaison avec deux autres
techniques reposant sur SDF (le formalisme ASF et le langage Stratego),
le système de grammaires attribuées utilisé dans Transformers sera évalu
par rapport à ces aspect fondamentaux pour en faire ressortir les
avantages et inconvénients.
THEORIE DES JEUX
La tablette de chocolat transfinie -- Nicolas Neri
Dans ce rapport technique, nous nous attardons sur le jeu de la tablette
de chocolat. On dispose d'une tablette de chocolat dont le carré
inférieur gauche est empoisonné. Les joueurs jouent à tour de rôle. Un
coup consiste à choisir un carré de chocolat et à le manger ainsi que
tous les carrés qui sont à sa droite et au dessus de lui. Le joueur qui
mange le carré empoisonné perd la partie. Dans cet exposé, nous nous
intéresserons particulièrement au cas où les dimensions du jeu sont de
classe cardinale infinie. On présentera également, pour une meilleure
compréhension, les nombres ordinaux et leur ordre associé.
VERIFICATION DU LOCUTEUR
Combinaison de noyaux à partir de systèmes SVM en vérification du
locuteur -- Charles Alban Deledalle
Les meilleurs systèmes de Verification du Locuteur (VL) sont fondés sur
la fusion des scores de décision de plusieurs approches. Les méthodes
basées sur les Séparateurs à Vaste Marge (SVM) donnent des résultats
très performants. En conséquence, l'apport de ces méthodes est très
important pour la fusion. Dans notre approche, nous proposons une
nouvelle méthode de fusion des systèmes de VL basés sur les méthodes SVM
en construisant une nouvelle fonction noyau à partir d'une combinaison
linéaire de plusieurs fonctions. Dans cette combinaison, les poids
utilisés varient selon les locuteurs, ce qui diffère des approches par
fusion de score qui elles utilisent des poids universels.
--
Daniela Becker
Hello,
I'm happy to announce that I will hold a special 90 minutes session on
Lisp at the next ACCU conference, April 2008, Oxford. The abstract is
given below.
Performance and Genericity: the forgotten power of Lisp
Lisp is one of the eldest languages around, and probably still is the
most versatile of them. In our current times where there seem to be a
regain of interest for dynamic and functional programming, many of those
recent languages (Ruby to name one) acknowledge the fact that they were
inspired by Lisp, but not quite as powerful.
So why is it that so many people seem to acknowledge the power of Lisp
but so few of us are actually using it? Two important reasons are that
people either still think it is slow, or think that being so old, it
must be dead, so they simply have forgotten all about it.
The purpose of this session of twofold: first we want to remind people
of the power of Lisp, and second, we want to break the myth of slowness.
In a first step, we illustrate the expressive power of Lisp by showing
how straightforward it is to implement binary methods, a concept
otherwise difficult to reach in traditionnal OO languages. This will
allow us to provide a "guided-tour" of some of the powerful features of
Common Lisp: CLOS (the Object System) and its multiple-dispatch
paradigm, the CLOS MOP (the Meta-Object Protocol) and it's ability to
let us rewrite new, specialized, objet-systems for our own purpose, and
finally the Common Lisp particular package system.
In a second step, we present a recent research demonstrating that Lisp
can run as fast as C, given that it is properly typed and optimized.
This is done by analyzing the behavior and performance of pixel access
and arithmetic operations in equivalent Lisp and C code for some simple
image processing algorithms.
--
Didier Verna, didier(a)lrde.epita.fr, http://www.lrde.epita.fr/~didier
EPITA / LRDE, 14-16 rue Voltaire Tel.+33 (0)1 44 08 01 85
94276 Le Kremlin-Bicêtre, France Fax.+33 (0)1 53 14 59 22 didier(a)xemacs.org
Bonjour,
nous avons le plaisir de vous présenter le n°12 du bulletin du LRDE.
C'est un numéro spécial consacré aux deux sessions du séminaire CSI en
janvier 2008 avec les résumés de toutes les présentations. Les étudiants
de la promo 2008 y présenteront leur travail concluant les années
passées au LRDE.
Dates de séminaire à retenir : les 9 et 16 janvier 2008.
Vous pouvez télécharger le bulletin en couleur à la page suivante :
http://publis.lrde.epita.fr/200801-l-air-de-rien-12
--
Daniela Becker
Bonjour,
Vous êtes tous cordialement invités à assister au séminaire qui aura
lieu le mercredi 09 janvier 2008 à 14 heures en Amphi 2 (KB).
-----------------------------------------------------------------------
Le programme :
*Olena, DD, Vérification du locuteur, Théorie des Jeux & Vaucanson*
http://www.lrde.epita.fr/cgi-bin/twiki/view/Publications/Seminar-2008-01-09
OLENA
14h00 : Une introduction à SCOOP, un paradigme C++ orienté objet --
Thomas Moulard
DD
14h30 : Homolib -- Samuel Charron
VERIFICATION DU LOCUTEUR
15h00 : SVM-MLLR et fusion pour la vérification du locuteur -- Geoffroy
Querol
THEORIE DES JEUX
15h45 : Étude du fictitious play dans le cas d'un jeu à fonctions
d'utilité identiques -- Jean Philippe Garcia Ballester
VAUCANSON
16h15 : Booster la généricité de Vaucanson -- Guillaume Lazzara
16h45 : Transducteurs synchronisés -- Guillaume Leroi
-----------------------------------------------------------------------
Les Résumés des exposés :
**************************
OLENA
Une introduction à SCOOP, un paradigme C++ orienté objet -- Thomas Moulard
Le C++ a réussi à supporter à la fois la programmation orienté objet
classique et la programmation générique, cependant certains problèmes
récurrents restent difficiles à résoudre. SCOOP est un paradigme orienté
objet dont le but est de mélanger approche orienté objet classique et
programmation générique afin d'allier élégance, sécurité et rapidité. Le
paradigme fournit des méthodes virtuelles, les arguments covariants, les
types virtuels et les multi-méthodes typées statiquement sans avoir
besoin d'étendre le langage. SCOOP fournit également des mécanismes
d'écriture de morphers qui permettent d'exprimer en C++ des fonctions de
type vers type. Cette présentation fait un tour d'horizon de SCOOP en
présentant d'une part le paradigme en lui-même et d'autre part son
utilisation en C++ au travers d'exemples.
DD
Homolib -- Samuel Charron
Les Diagrammes de Décision sont une famille de structures de données
permettant de représenter avec peu de mémoire de grands ensembles de
données. Ces structures peuvent être de taille fixe (un tuple) ou
variable (une liste, un conteneur associatif, ...), la manipulation du
DD ne se faisant pas de la même manière. Les Data Decision Diagrams et
Set Decision Diagrams manipulent des données de taille variable grâce à
des opérations, les homomorphismes. Cependant la définition d’une
opération correcte peut dérouter l’utilisateur, et passe souvent par de
nombreuses erreurs, difficiles à identifier. Ce séminaire propose une
bibliothèque d’algorithmes fournissant une vue plus abstraite que les
homomorphismes "bruts" des données manipulées, en reprenant les
algorithmes définis dans les modules "List" et "Map" d’Objective Caml.
L’utilisateur peut se concentrer sur les parties spécifiques à son problème.
VERIFICATION DU LOCUTEUR
SVM-MLLR et fusion pour la vérification du locuteur -- Geoffroy Querol
Afin d'améliorer la performance globale des systèmes de vérification du
locuteur, il faut diversifier les approches. Le but de ce travail est
d'étudier les performances d'un système SVM-MLLR. Cette méthode se base
sur la construction, à partir du modèle du monde, d'une transformation
linéaire des vecteurs moyennes (mean supervectors) maximisant la
vraisemblance du modèle transformé par rapport aux données locuteur. On
évaluera deux approches différentes : logarithme du rapport de
vraisemblance (GMM-MLLR) et utilisation des SVMs pour évaluer les scores
de décision.
THEORIE DES JEUX
Étude du fictitious play dans le cas d'un jeu à fonctions d'utilité
identiques -- Jean Philippe Garcia Ballester
Le fictitious play, en théorie des jeux, est une règle d'apprentissage
dans laquelle chaque joueur suppose que ses adversaires jouent une
stratégie fixe (potentiellement mixte, c'est-à-dire une distribution de
probabilité sur un ensemble de stratégies). À chaque tour, chaque joueur
joue ainsi le meilleur coup contre la stratégie de ses adversaires,
déterminée de manière empirique à partir de leurs coups précédents.
La convergence de telles stratégies n'est pas assurée, mais on sait que
si il y a convergence, alors les stratégies jouées correspondront
statistiquement à un équilibre de Nash. Il est donc très intéressant de
connaître les critères de convergence.
Nous nous intéresserons pour cette présentation au cas des jeux où les
fonctions d'utilité (le gain d'un joueur en fonction des stratégies
jouées) de chaque joueur sont identiques.
Nous étudierons d'abord des résultats de convergence dans ce cas
particulier. Afin de réduire la complexité en temps, nous verrons une
variante de cet algorithme, qui consiste à autoriser une erreur dans la
meilleure réponse des joueurs. Nous présenterons enfin un exemple
d'application du fictitious play pour résoudre un problème a priori non
lié à la théorie des jeux : un problème d'optimisation, c'est-à-dire
calculer le maximum des valeurs prises par une fonction.
VAUCANSON
Booster la généricité de Vaucanson -- Guillaume Lazzara
L'architecture du projet Vaucanson a été conçue initialement autour du
design pattern Element. Ce dernier a l'énorme avantage de distinguer à
la fois les concepts et les implémentations. C'est à dire que pour un
type d'automate comme les automates booléens, on peut théoriquement
avoir plusieurs implémentations qui se côtoient dans un même programme.
Malgré toutes ces précautions, aujourd'hui, ajouter une nouvelle
structure s'avère très délicat et remet en cause de nombreux points au
sein du projet. C'est pour cette raison que durant ce séminaire nous
tenterons de répondre à ces problèmes. Les problèmes de performances
qu'a pu rencontrer le projet sont également une bonne motivation pour
s'attaquer à ce sujet : il est aujourd'hui indispensable de proposer des
nouvelles structures plus efficaces, notamment implémentées avec la
bibliothèque Boost.
Transducteurs synchronisés -- Guillaume Leroi
Lors de cette présentation, un algorithme de resynchronisation sera
décrit ainsi que son implémentation dans Vaucanson. De plus, des
explications sont données sur l'ajout des transducteurs a délai borné,
ainsi que sur les difficultés qui peuvent être rencontrées lors de
l'extension de la hierarchie de classes de Vaucanson.
--
Daniela Becker
