Approximate Nash Equilibria for Multi-Player Games

From LRDE

Revision as of 14:01, 22 October 2013 by Bot (talk | contribs) (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...")
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)


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