The Worst Possible Winner - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-19T14:46:33Z http://mathoverflow.net/feeds/question/31476 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/31476/the-worst-possible-winner The Worst Possible Winner qwerty1793 2010-07-11T22:59:00Z 2010-07-12T09:39:36Z <p>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.</p> <p>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). </p> <p>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.</p> <p>Let $\text{score}(\alpha_i) = \sum_{j = 1}^{n} f(\beta_{i,j})$ be the total score obtained by player $\alpha_i$.</p> <p>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.</p> <p>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. </p> <blockquote> <p>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?</p> </blockquote> <p>Or alternatively:</p> <blockquote> <p>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$?</p> </blockquote> <p>If the general case is too hard, how about when $f(x) = p + 1 - x$?</p> http://mathoverflow.net/questions/31476/the-worst-possible-winner/31489#31489 Answer by Doug Chatham for The Worst Possible Winner Doug Chatham 2010-07-12T01:12:20Z 2010-07-12T09:39:36Z <p>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. </p>