Approximate Nash Equilibria for Multi-Player Games

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

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