Preventing ties

Question

I'm working on a simple game to rate a users' preference among several styles. There are C classes, and the game consists of R rounds of comparison. At each round, the user is presented a [pseudorandomly selected] single representative image from each of S classes and chooses exactly one to be the "round winner." At the end of the R rounds, there cannot be a tie among any classes (i.e., one of the classes must have a higher score than all the others).

For example, say I have 3 classes (traditional, contemporary, alternative), and I want to run a 5 round game, comparing 2 classes per round.

I'm looking for an algorithm to provide as-even-as-possible sampling from each of the classes, but in such a way that it would be impossible to end the 5th round with a tie.

Answer 1

Perhaps a different approach will help: You're basically after a 'winner' so perhaps a 'ladder' approach used in one-on-one sports might be what you're after. Each choice is a rung on a ladder and adjacent choices can compete, the winner swapping places. This does rely on some kind of initial ordering which could be random.

eg for C=3 Classes (a, b, c) with S=2 choices and R=5 rounds

At start: (Top) c-b-c (Bottom)

1. a vs b. b wins => b-a-c
2. c vs a. c wins => b-c-a
3. b vs c. b wins => b-c-a
4. c vs a. a wins => b-a-c (players can be fickle!)
5. b vs a. b wins => b-a-c (so b is overall winner!)

Admittedly the player will likely be presented with some of the same choices more than once, but you don't get a tie and in the example above, 5 rounds should be plenty to get allow the randomly placed bottom Class to 'float' to the top.

Anyway, hope this helps!

Answer 2

How Fixed is R? Would the Player notice if after the regular rounds of comparison, you ended the sequence with a series of direct comparisons of the tied classes?

Let's say R is 10. After 10 rounds you have A and B which are tied. Can't you do an A vs B round to force the direct comparison?

This will work better if R varies from time to time normally, so as to hide the occasions when you need a few extra rounds for tie-elimination.

Answer 3

Your first issue is that with your example of 3 classes and 5 rounds you can't make any selection of five comparisons where each of the three classes has an equal chance of winning given random choices by the user. That's because 5 rounds * 2 choices per round isn't a multiple of the number of classes.

Unfortunately fixing that and making it fair means you can almost always end up with a tie. The only exception I can think of is with two classes and and odd number of rounds. Other than that I don't think there's any way to rig it so that ties are impossible without adding unlimited numbers of extra rounds, or biasing the selections you present to the user.

Of course if the classes are significantly different and the number of rounds is high it's very unlikely that you'll actually get a tie. You could always just pick randomly between the tied classes if you need to pick a single winner.