Daily Arxiv

This is a page that curates AI-related papers published worldwide.
All content here is summarized using Google Gemini and operated on a non-profit basis.
Copyright for each paper belongs to the authors and their institutions; please make sure to credit the source when sharing.

Dominated Actions in Imperfect-Information Games

Created by
  • Haebom

Author

Sam Ganzfried

Outline

This paper defines and studies the concept of dominant strategies in games with incomplete information. While dominant strategies can be identified in polynomial time in strategically formed games, the process of converting to strategically formed games with incomplete information can exponentially increase the game size. This paper presents a polynomial-time algorithm for identifying dominant actions in games with incomplete information. This algorithm can be used to identify actions that are strictly or weakly dominated and to efficiently reduce the size of the game tree by iteratively eliminating dominant actions. The role of dominant actions is experimentally explored using the "All In or Fold" No-Limit Texas Hold'em poker variant.

Takeaways, Limitations

Takeaways: We provide a polynomial-time algorithm that efficiently identifies and removes dominant actions in incomplete-information games, reducing the game size in the preprocessing stage for Nash equilibrium calculations. This can contribute to improving the efficiency of Nash equilibrium calculations. We demonstrate its applicability to real-world games (e.g., poker).
Limitations: The actual performance of the presented algorithm may vary depending on the size and complexity of the game. Efficiency is not guaranteed for all types of games with incomplete information. "All In or Fold" No-Limit Texas Hold'em is a specific type of game, and generalization to other games may require further research.
👍