Re: Ranking is hardsniffnoyOctober 26 2015, 18:45:47 UTC
Oh man, I hadn't even thought of this in terms of voting! I suppose you could think of this as a voting system, too -- a candidate's "matchup" against another candidate is how many people vote for the one candidate over the other. (Except that you'd have to normalize, because otherwise it might not be zero-sum, if some people only ranked some of the candidates.) It would be an odd voting system, that's for sure. I'm not sure it would be Condorcet. (Maybe it is? Is it in general true that if there's character with no disadvantageous matchups, and at least one advantageous one, then the game is dominance-solvable with them as the winner? I hadn't considered that. I'll have to think about that, or look it up...)
EDIT: OK, that's definitely false, because we have a counterexample above: In SSBM, Fox and Falco both have no disadvantageous matchups, but obviously the optimal strategy can't both be "only play Fox" and "only play Falco"! Of course, that's a pretty complicated counterexample, I should come up with a simpler one.
Perhaps more of a problem is that when snarls occur -- which of course should be rare, but which is where all this different voting systems actually differ from one another -- this one seems prone to producing ties (at least if you don't use the tiebreaker). It's easy to see that in a zero-sum symmetric game, all of the pure strategies that occur in the optimal strategy must do equally well against this optimal strategy. So in fact the first ranking doesn't matter at all, it's just based on how often each occurs in the optimal strategy. Which seems less prone to producing ties. Hm. Still, I don't really see why one would want to use this as a voting system in the first place; it just seems kind of arbitrary in that context.
One could also do the reverse, and take matchups as votes and use standard voting systems to yield a result. (It would have to be a system that worked with just that information, obviously; there isn't enough information to do, say, a Borda count.) That said, I don't see any particular motivation for doing this other than that you can. Whereas, like, my method actually makes sense for ranking the characters in a world where everyone could actually play them all optimally.
Re: Ranking is hardsniffnoyOctober 26 2015, 21:25:49 UTC
OK, here's a simple example: Suppose you have four strategies, A, B, C, and D. A beats the others by 1, while B, C, and D exist in a rock-paper-scissors relation, each beating the other by 2. A has only positive matchups, but nothing dominates anything else.
However, plugging this into a solver, apparently the optimal strategy is in fact pure A. So finding one where it's mixed will be harder (assuming that's possible, which I don't see why it wouldn't be). Still, the SSBM example illustrates that in general having no bad matchups doesn't mean you're part of the optimal strategy.
Re: Ranking is hardsniffnoyNovember 21 2015, 23:25:14 UTC
OK, here's a nice small sort-of-example, with four strategies. Actually, it's trivial to come up with examples if you allow two of the strategies to be identical (and then you can do it with three), but let's assume we don't allow that.
Just take my example above and modify it so that A, rather than beating all the others by 1, ties with one of the others; call it B. Now there's no longer a unique best strategy; anything from "pure A" to "2/3 A, 1/3 B" is optimal.
Unfortunately this is only a sort-of example, since pure A still is an optimal strategy, just not a unique one. So I don't have any better example there than the Fox/Falco example for now. And that one has both Fox and Falco with no negative matchups; I'd like one where ideally only one character had this. Hm -- actually, if you just have 3 strategies, A, B, and C, and A and B tie against each other but each beat C (let's say A beats C by more), then that's a Fox/Falco example right there. OK, so that one's silly.
This still leaves the question: Does one character having only strictly positive matchups -- or possibly just being the unique character with no negative matchups -- mean the optimal strategy consists of only that character? I haven't found a counterexample so far, or a proof, but I assume an answer is known to this. I think I'll go ask on Math.SE.
EDIT: Nevermind; this paper answers the question -- though I don't understand the reasoning? Oh well, assuming it's correct, a symmetric zero-sum game has an optimal pure strategy iff there is a strategy with only nonnegative payoffs. So if one pure strategy has all positive payoffs, or more generally is the unique one with no negative ones, it is the unique optimal strategy.
Re: Ranking is hardjoshuazelinskyOctober 26 2015, 23:14:26 UTC
The pairwise comparison voting system can be though of as actually taking voting preferences and moving that to rankings. But it is probably true that games can exhibit much weirder behavior than what one would get from listing out all the pair comparisons from some set of voting preferences.
EDIT: OK, that's definitely false, because we have a counterexample above: In SSBM, Fox and Falco both have no disadvantageous matchups, but obviously the optimal strategy can't both be "only play Fox" and "only play Falco"! Of course, that's a pretty complicated counterexample, I should come up with a simpler one.
Perhaps more of a problem is that when snarls occur -- which of course should be rare, but which is where all this different voting systems actually differ from one another -- this one seems prone to producing ties (at least if you don't use the tiebreaker). It's easy to see that in a zero-sum symmetric game, all of the pure strategies that occur in the optimal strategy must do equally well against this optimal strategy. So in fact the first ranking doesn't matter at all, it's just based on how often each occurs in the optimal strategy. Which seems less prone to producing ties. Hm. Still, I don't really see why one would want to use this as a voting system in the first place; it just seems kind of arbitrary in that context.
One could also do the reverse, and take matchups as votes and use standard voting systems to yield a result. (It would have to be a system that worked with just that information, obviously; there isn't enough information to do, say, a Borda count.) That said, I don't see any particular motivation for doing this other than that you can. Whereas, like, my method actually makes sense for ranking the characters in a world where everyone could actually play them all optimally.
Reply
However, plugging this into a solver, apparently the optimal strategy is in fact pure A. So finding one where it's mixed will be harder (assuming that's possible, which I don't see why it wouldn't be). Still, the SSBM example illustrates that in general having no bad matchups doesn't mean you're part of the optimal strategy.
Reply
Just take my example above and modify it so that A, rather than beating all the others by 1, ties with one of the others; call it B. Now there's no longer a unique best strategy; anything from "pure A" to "2/3 A, 1/3 B" is optimal.
Unfortunately this is only a sort-of example, since pure A still is an optimal strategy, just not a unique one. So I don't have any better example there than the Fox/Falco example for now. And that one has both Fox and Falco with no negative matchups; I'd like one where ideally only one character had this. Hm -- actually, if you just have 3 strategies, A, B, and C, and A and B tie against each other but each beat C (let's say A beats C by more), then that's a Fox/Falco example right there. OK, so that one's silly.
This still leaves the question: Does one character having only strictly positive matchups -- or possibly just being the unique character with no negative matchups -- mean the optimal strategy consists of only that character? I haven't found a counterexample so far, or a proof, but I assume an answer is known to this. I think I'll go ask on Math.SE.
EDIT: Nevermind; this paper answers the question -- though I don't understand the reasoning? Oh well, assuming it's correct, a symmetric zero-sum game has an optimal pure strategy iff there is a strategy with only nonnegative payoffs. So if one pure strategy has all positive payoffs, or more generally is the unique one with no negative ones, it is the unique optimal strategy.
Reply
Reply
Leave a comment