Difference between revisions of "Publications/hemon.08.sagt"
From LRDE
| Line 7: | Line 7: | ||
| booktitle = 1st International Symposium on Algorithmic Games Theory |
| booktitle = 1st International Symposium on Algorithmic Games Theory |
||
| address = Paderborn, Germany |
| address = Paderborn, Germany |
||
| − | | resume = Les équilibres de Nash sont des positions-clés de tout jeu admettant une représentation finie : en effet, quel que soit le nombre de joueurs et de stratégies, une telle position existe toujours. Lorsqu'elle est atteinte, elle dissuade tout joueur de vouloir se détourner de sa stratégie actuelle, d'où la notion d'équilibre. De nombreux problèmes y font appel mais calculer de façon effective l'équilibre demeure un problème difficile. En effet, le meilleur algorithme connu pourdans le cas général, calculer un équilibre est exponentiel en le nombre de stratégies. Nous présenterons ici la notion d'équilibres approchés, et donnerons des résultats concernant leur calcul. Nous montrerons qu'il ne saurait exister d'algorithmes pouvant calculer un équilibre, même approché, sans utiliser au moins, pour un joueur, un nombre logarithmique de stratégies. Nous montrerons comment calculer un équilibre approché en temps sub-exponentiel |
+ | | resume = Les équilibres de Nash sont des positions-clés de tout jeu admettant une représentation finie : en effet, quel que soit le nombre de joueurs et de stratégies, une telle position existe toujours. Lorsqu'elle est atteinte, elle dissuade tout joueur de vouloir se détourner de sa stratégie actuelle, d'où la notion d'équilibre. De nombreux problèmes y font appel mais calculer de façon effective l'équilibre demeure un problème difficile. En effet, le meilleur algorithme connu pourdans le cas général, calculer un équilibre est exponentiel en le nombre de stratégies. Nous présenterons ici la notion d'équilibres approchés, et donnerons des résultats concernant leur calcul. Nous montrerons qu'il ne saurait exister d'algorithmes pouvant calculer un équilibre, même approché, sans utiliser au moins, pour un joueur, un nombre logarithmique de stratégies. Nous montrerons comment calculer un équilibre approché en temps sub-exponentiel n^O(fracln nvarepsilon^2), ce qui demeure actuellement, pour le cas général, la meilleure complexité en pire cas. Enfin, nous présenterons une approche inductive de transfert d'approximation d'une position d'un jeu à deux joueurs en une approximation pour un jeu à r joueurs, ce qui confère des résultats novateurs dans le domaine. |
| lrdepaper = http://www.lrde.epita.fr/dload/papers/hemon.08.sagt.pdf |
| lrdepaper = http://www.lrde.epita.fr/dload/papers/hemon.08.sagt.pdf |
||
| lrdenewsdate = 2008-01-18 |
| lrdenewsdate = 2008-01-18 |
||
Revision as of 00:01, 29 April 2016
- Authors
- Sébastien Hémon, Michel de Rougemont, Miklos Santha
- Where
- 1st International Symposium on Algorithmic Games Theory
- Place
- Paderborn, Germany
- Type
- inproceedings
- Date
- 2008-01-18
Documents
Bibtex (lrde.bib)
@InProceedings{ hemon.08.sagt,
author = {S\'ebastien H\'emon and Michel de Rougemont and Miklos
Santha},
title = {Approximate {N}ash Equilibria for Multi-Player Games},
titre = {\'Equilibres de Nash approch\'es dans les jeux
multi-joueurs},
booktitle = {1st International Symposium on Algorithmic Games Theory},
year = 2008,
address = {Paderborn, Germany},
month = apr,
resume = {Les \'equilibres de Nash sont des positions-cl\'es de tout
jeu admettant une repr\'esentation finie : en effet, quel
que soit le nombre de joueurs et de strat\'egies, une telle
position existe toujours. Lorsqu'elle est atteinte, elle
dissuade tout joueur de vouloir se d\'etourner de sa
strat\'egie actuelle, d'o\`u la notion d'\'equilibre. De
nombreux probl\`emes y font appel mais calculer de
fa\c{c}on effective l'\'equilibre demeure un probl\`eme
difficile. En effet, le meilleur algorithme connu pour,
dans le cas g\'en\'eral, calculer un \'equilibre est
exponentiel en le nombre de strat\'egies. Nous
pr\'esenterons ici la notion d'\'equilibres approch\'es, et
donnerons des r\'esultats concernant leur calcul. Nous
montrerons qu'il ne saurait exister d'algorithmes pouvant
calculer un \'equilibre, m\^eme approch\'e, sans utiliser
au moins, pour un joueur, un nombre logarithmique de
strat\'egies. Nous montrerons comment calculer un
\'equilibre approch\'e en temps sub-exponentiel
$n^{\mathcal{O}(\frac{\ln n}{\varepsilon^2})}$, ce qui
demeure actuellement, pour le cas g\'en\'eral, la meilleure
complexit\'e en pire cas. Enfin, nous pr\'esenterons une
approche inductive de transfert d'approximation d'une
position d'un jeu \`a deux joueurs en une approximation
pour un jeu \`a $r$ joueurs, ce qui conf\`ere des r\'esultats novateurs dans le domaine.}
}