Iterated Weaker-than-Weak Dominance
by CHENG Shih-Fen
| Speaker: |  |
Date: Time: Venue: |
02 February 2007 (Friday)
|
CHENG Shih-Fen |
We look forward to seeing you at this research seminar. |
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 dependence, 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.
Biography
Shih-Fen is presently an Assistant Professor at School of Information Systems, Singapore Management University. His dissertation research focuses on the optimization of complex systems in engineering and business domains via game-theoretic and market-based approaches. These techniques are suitable for solving problems with computationally challenging properties, most notably combinatorial explosion of the solution space and the globally distributed nature of the problem. His most active area of research is in transportation, production systems, and decentralized resource allocation.