The Worst Possible Winner

2010-07-11T22:59:00Z

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

Answer by Doug Chatham for The Worst Possible Winner

2010-07-12T01:12:20Z

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.

The Worst Possible Winner - MathOverflow

The Worst Possible Winner

Answer by Doug Chatham for The Worst Possible Winner