Skip to main content
Article
Iterated Weaker-than-Weak Dominance
Proceedings of the Twentieth International Joint Conference on Artificial Intelligence IJCAI-07: Hyderabad, India, 6-12 January, 2007
  • Shih-Fen CHENG, Singapore Management University
  • Michael P. WELLMAN, University of Michigan
Publication Type
Conference Proceeding Article
Publication Date
1-2007
Abstract
We introduce a weakening of standard gametheoretic δ-dominance conditions, called dominance, which enables more aggressive pruning of candidate strategies at the cost of solution accuracy. Equilibria of a game obtained by eliminating a δ-dominated strategy are guaranteed to be approximate equilibria of the original game, with degree of approximation bounded by the dominance parameter. We can apply elimination of δ-dominated strategies iteratively, but the for which a strategy may be eliminated depends on prior eliminations. We discuss implications of this order independence, and propose greedy heuristics for determining a sequence of eliminations to reduce the game as far as possible while keeping down costs. A case study analysis of an empirical 2-player game serves to illustrate the technique, and demonstrate the utility of weaker-than-weak dominance pruning.
ISBN
9781577352983
Publisher
AAAI Press
City or Country
Menlo Park, CA
Creative Commons License
Creative Commons Attribution-Noncommercial-No Derivative Works 4.0
Additional URL
http://www.aaai.org/Library/IJCAI/2007/ijcai07-199.php
Citation Information
Shih-Fen CHENG and Michael P. WELLMAN. "Iterated Weaker-than-Weak Dominance" Proceedings of the Twentieth International Joint Conference on Artificial Intelligence IJCAI-07: Hyderabad, India, 6-12 January, 2007 (2007) p. 1233 - 1238
Available at: http://works.bepress.com/sfcheng/14/