First a little background. In racing it is possible for a player to win a tournament without winning a single race, however, how bad can a tournament winner actually be? Can a player win a tournament without even doing better than coming third? Or even fourth? Obviously this depends on the scoring method used for awarding points for each race.

More formally, suppose $p$ players, named $\alpha_1, \alpha_2, \ldots, \alpha_p$, play a game consisting of $n$ races (with no possibility of ties for a position).

Suppse that player $\alpha_i$ finishes race $j$ in position $\beta_{i,j} \in \lbrace 1, 2, \ldots p \rbrace$ (with $\beta_{i,j} = 1$ being the best possible result for player $\alpha_i$). And that for each race the points scored by a player are given by a non-negative, strictly decreasing function called a scoring function $f : \lbrace 1,2, \ldots, p \rbrace \to \mathbb{N}$, i.e. the player coming first receives $f(1)$ points, the player coming second receives $f(2)$ points and the player coming last receives $f(p)$ points.

Let $\text{score}(\alpha_i) = \sum_{j = 1}^{n} f(\beta_{i,j})$ be the total score obtained by player $\alpha_i$.

Let $\text{best}(\alpha_i) = \min_{1 \leq j \leq n} \lbrace \beta_{i,j} \rbrace$, be the best position that player $\alpha_i$ came in.

We say that player $\alpha_i$ is a winner iff $\forall j \in \lbrace 1, 2, \ldots, p \rbrace$ $\text{score}(\alpha_i) \geq \text{score}(\alpha_j)$, note there may be more than one winner of a game.

Given a particular choice of scoring function $f$, if $\alpha_i$ is a winner what is the maximum value $\text{best}(\alpha_i)$ can possibly be?

Or alternatively:

For what $k \in \lbrace 1, 2, \ldots, p \rbrace$, is there a choice of scoring function $f$ such that it is possible for $\alpha_i$ to be a winner and $\text{best}(\alpha_i) \geq k$?

If the general case is too hard, how about when $f(x) = p + 1 - x$?

  • 8
    $\begingroup$ This seems to be a voting problem in disguise. The racers are the alternatives being voted on, the results of each race is an individual's preference profile, and your scoring function $f$ is a positional voting method. (See for example the Borda Count page of Wikipedia (en.wikipedia.org/wiki/Borda_count ). I don't have an answer to your question yet, but I suspect the best position of your winning racer can be low. $\endgroup$ Commented Jul 12, 2010 at 0:14
  • 2
    $\begingroup$ Assuming the number of races is a multiple of $p-1$ or large enough to avoid issues with lack of solutions to linear diophantine equations, the answer is the smallest $x$ with $f(x)$ bigger than the average score. (Everyone else takes the other $p-1$ places exactly once.) $\endgroup$ Commented Jul 12, 2010 at 3:32

1 Answer 1


With the "right" scoring function, it is possible that $best(\alpha_{i}) = p-1$: Suppose our winner is next-to-last in every race, that each of the other racers is last in at least one race, and the scoring function awards $100^{p}-k+1$ (or some other large enough number) points for position $k=1,\ldots, p-1$ and $0$ points for position $p$. (EDIT: Also suppose $n \geq p-1$.) The scoring function gives roughly equal awards to the racers who don't come in last and severely penalizes a racer who comes in last. Our consistently next-to-last racer is the overall winner since he or she is the only one who never comes in last.

  • 3
    $\begingroup$ What if the number of racers is greater than the number of races by at least two? $\endgroup$ Commented Jul 12, 2010 at 4:57
  • 2
    $\begingroup$ Then there are at least two racers who never come last, so the winner must get at least once p-2. Generally, if there are r races, then the best position will be p-\ceiling[p-1/r]. $\endgroup$
    – domotorp
    Commented Jul 12, 2010 at 6:54
  • $\begingroup$ @Charles Staats: Thanks for asking. Somehow I misread $n$ as $p$. $\endgroup$ Commented Jul 12, 2010 at 9:35
  • $\begingroup$ But what if n < p-1? $\endgroup$
    – Mark Bell
    Commented Jul 12, 2010 at 14:51
  • $\begingroup$ Actually I guess by this method you can be a winner and have $\text{best}(\alpha_i) = n$ if n < p-1 by ensuring that the n-1 players who beat you and the player who comes in last permute in each race and that each of them finishes last at least once. $\endgroup$
    – Mark Bell
    Commented Jul 12, 2010 at 15:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.