Difference between revisions of "Publications/hemon.08.sagt"

From LRDE

(Created page with "{{Publication | date = 2008-04-01 | authors = Sébastien Hémon, Michel de Rougemont, Miklos Santha | title = Approximate Nash Equilibria for Multi-Player Games | titre = Équ...")
 
Line 8: Line 8:
 
| urllrde = 2008-01-18-SAGT
 
| urllrde = 2008-01-18-SAGT
 
| 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 joueursce 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 joueursce qui confère des résultats novateurs dans le domaine.
  +
| lrdepaper = http://www.lrde.epita.fr/dload/papers/hemon.08.sagt.pdf
 
| type = inproceedings
 
| type = inproceedings
 
| id = hemon.08.sagt
 
| id = hemon.08.sagt

Revision as of 15:43, 22 October 2013

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