Been playing this a bit today on my iPaq. It’s one of those games I play a lot, but don’t report on here very often as it isn’t “mainstream”. It is, however, ACEBEST.
It is sort of like Risk meets Paper, Scissors, Stone, where you have to take over territories, but do so by having ever more powerful fighters to defeat less powerful ones. Erm. That doesn’t really explain it very well, but the website for the game (and there are Palm and Windows versions too) does a better job. Probably: Pocket Slay.