Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

share|improve this question
6  
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
2  
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
add comment

1 Answer 1

up vote 12 down vote accepted

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.

share|improve this answer
3  
What if the number of racers is greater than the number of races by at least two? –  Charles Staats Jul 12 '10 at 4:57
2  
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]. –  domotorp Jul 12 '10 at 6:54
    
@Charles Staats: Thanks for asking. Somehow I misread $n$ as $p$. –  Doug Chatham Jul 12 '10 at 9:35
    
But what if n < p-1? –  Mark Bell Jul 12 '10 at 14:51
    
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
show 1 more comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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