# The Worst Possible Winner

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$?

-
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. – Doug Chatham Jul 12 '10 at 0:14
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.) – Alexander Woo Jul 12 '10 at 3:32

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.
@Charles Staats: Thanks for asking. Somehow I misread $n$ as $p$. – Doug Chatham Jul 12 '10 at 9:35
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. – Mark Bell Jul 12 '10 at 15:37