Iterated Weaker-than-Weak Dominance

S-F Cheng and MP Wellman

Twentieth International Joint Conference on Artificial Intelligence, pages 1233–1238, 2007.
Copyright (c) 2007, Cheng & Wellman.

Abstract

We introduce a weakening of standard game-theoretic dominance conditions, called delta-dominance, which enables more aggressive pruning of candidate strategies at the cost of solution accuracy. Equilibria of a game obtained by eliminating a delta-dominated strategy are guaranteed to be approximate equilibria of the original game, with degree of approximation bounded by the dominance parameter, delta. We can apply elimination of delta-dominated strategies iteratively, but the delta 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.

Downloads

• Full Paper