Daily Arxiv

Cette page résume et organise les publications en intelligence artificielle du monde entier.
Les contenus sont synthétisés grâce à Google Gemini et le service est proposé à but non lucratif.
Les droits d'auteur des articles appartiennent à leurs auteurs ou institutions respectives ; en cas de partage, il suffit d'en mentionner la source.

Actions dominées dans les jeux d'information imparfaite

Created by
  • Haebom

Auteur

Sam Ganzfried

Contour

Cet article définit et étudie le concept de stratégies dominantes dans les jeux à information incomplète. Si les stratégies dominantes peuvent être identifiées en temps polynomial dans les jeux stratégiquement formés, la taille de la partie peut croître exponentiellement lors de la transformation en jeux stratégiquement formés à information incomplète. Cet article présente un algorithme en temps polynomial permettant de déterminer quelles actions, dans une partie à n joueurs, sont (strictement ou faiblement) dominées par des stratégies mixtes. Cet algorithme peut être étendu pour supprimer itérativement les actions dominantes, réduisant ainsi efficacement la taille de l'arbre de jeu lors de l'étape de prétraitement pour le calcul de l'équilibre de Nash. Le rôle des actions dominantes est exploré expérimentalement à l'aide de la variante de poker Texas Hold'em No-Limit « All In or Fold ».

Takeaways, Limitations

Takeaways: Nous avons amélioré l'efficacité du calcul de l'équilibre de Nash en fournissant un algorithme efficace pour identifier et éliminer les actions dominantes dans les jeux à information incomplète en temps polynomial. Nous avons également présenté une méthode de prétraitement pratique qui réduit la complexité de calcul en réduisant la taille de l'arbre de jeu.
Limitations: Les performances et l'efficacité réelles de l'algorithme présenté peuvent varier selon le type et la taille de la partie. Seule une analyse expérimentale de la variante de poker Texas Hold'em No-Limit « All In or Fold » est présentée, et des recherches supplémentaires sont nécessaires pour déterminer sa généralisabilité à d'autres types de jeux. La complexité polynomiale de l'algorithme repose sur une analyse théorique, et des considérations de temps constant doivent être prises en compte dans la mise en œuvre pratique.
👍