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 <math>n^O(fracln nvarepsilon^2)</math>, 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 à <math>r</math> joueurs, ce qui confère des résultats novateurs dans le domaine.
+
| 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

Latest revision as of 17:40, 25 November 2016

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.}
}