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$?
No comments:
Post a Comment