Thursday, June 16, 2005

Cyclical Dominance

Here's a numbers puzzle to think about during your idle cycles.

Let's start with some background. Say we have a spinner with 3 numbered sections. Each section in this spinner is equally likely to be picked when the spinner is spun. Now, say that this spinner had the numbers 1, 2, and 5. Let's take another spinner with the numbers 3, 7, and 9. If we put both the spinners in a heads-up competition against each other, the second spinner (3 7 9) would win in the long-run. So, we say that Spinner 3 7 9 dominates Spinner 1 2 5.

Onto the puzzle. We have 3 spinners just as described above. How can you assign the numbers from 1-9 to each of the sections, using each number exactly once, such that we have cyclical dominance? That is to say, Spinner A dominates Spinner B dominates Spinner C dominates Spinner A. Put yet another way... say we lay these spinners out on a table much like weapons prior to a duel. I then ask you to choose your weapon first. I will always be able to choose another that dominates yours (i.e. gives me the advantage) if there is a dominance cycle.

Follow-up question. There is more than one possible configuration that satisfies the cyclical dominance constraint. When you find one, check to see if your configuration is a fair one? A fair configuration being defined as one where any pair of spinners chosen will result in the same advantage for the dominant spinner.


Anonymous said...

I am not understanding the problem. What does it mean for a spinner to be dominant, are we talking about the EV of one spinner greater than another? If so, given that A's EV is greater than B's greater than C's. I don't see any way C's EV can be greater than A's. What am I missing?

Brute Force said...

Yes, a spinner dominates another if the EV is greater. So, we want to find a set of 3 spinners where if you were to choose one first, I could always choose one that beats yours. As Spud put it in a private chat, we want a Ro-Sham-Bo cycle.

Anonymous said...

Well, I don't think that it would be possible then. Maybe I am missing something here, but if A>B and B>C, how could C ever be greater than A? By transitivity A > C.

Brute Force said...

Perhaps I confused you with my usage of EV in my last comment. I suspect that you were thinking of what the expected value of the spin from each spinner would be. I was talking about EV in terms of expected win rate over the long-run. If you chose spinner A and I chose spinner B, and we were to bet 1 unit each spin. If you spin a bigger number you win, otherwise you lose. After N spins, how many units do you expect to be up or down?

In any case, here are the 5 solutions:

* { (168), (249), (357) }
* { (159), (267), (358) }
{ (168), (239), (457) }
{ (178), (249), (356) }
{ (178), (239), (456) }

The ones marked with * are "fair" configurations. Each spinner is dominated by one and dominates another with a 5 to 4 edge. The others are not "fair," because some are dominated by or dominate another with a a 6 to 3 edge.