Iterated Weaker-than-Weak Dominance
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...
Saved in:
| Main Authors: | , |
|---|---|
| Format: | text |
| Language: | English |
| Published: |
Institutional Knowledge at Singapore Management University
2007
|
| Subjects: | |
| Online Access: | https://ink.library.smu.edu.sg/sis_research/840 https://ink.library.smu.edu.sg/context/sis_research/article/1839/viewcontent/IJCAI_ChengS1471.pdf |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Institution: | Singapore Management University |
| Language: | English |
| Summary: | 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. |
|---|