Arrow's theorem and the postseason - MathOverflow most recent 30 from http://mathoverflow.net 2013-06-20T06:12:27Z http://mathoverflow.net/feeds/question/40877 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/40877/arrows-theorem-and-the-postseason Arrow's theorem and the postseason Harrison Brown 2010-10-02T21:58:53Z 2013-05-17T13:22:38Z <p>There are a <a href="http://en.wikipedia.org/wiki/Match_fixing#Better_playoff_chances" rel="nofollow">number of instances</a> of sports teams intentionally losing matches in order to secure a more favorable situation in a playoff round. While this doesn't happen terribly often, when it does it's <a href="http://en.wikipedia.org/wiki/West_Germany_v_Austria_%281982%29" rel="nofollow">usually pretty disappointing</a> even for fans of teams who both win and benefit from the win -- and certainly for fans of the sport generally.</p> <p>So it would be useful if there was a system for seeding the playoff round which was not susceptible to "tactical losing." Unfortunately I can't think of any such rule which seems fair, as long as there is more than one team in the playoffs.</p> <p>So the question, albeit ill-defined, is this: Is there an analogue of <a href="http://en.wikipedia.org/wiki/Arrow%2527s_impossibility_theorem" rel="nofollow">Arrow's theorem</a> for sports tournaments/leagues? (Or perhaps more appropriately an analogue of the related Gibbard-Satterthwaite theorem.) </p> <p>I can make this a little bit more precise, but probably not totally (and there may be other ways of making the question more rigorous). We'll model the results of the regular season as a directed multigraph on the set of teams $S$, with an edge from $u$ to $v$ for each time team $u$ defeated team $v$. Is there a function from such multigraphs to ordered lists of size $n$ (N.B. that the order isn't meant to represent the relative strength of the teams, but is just a proxy for the extra structure of the playoffs) which satisfies the following (roughly defined) conditions:</p> <ol> <li>Path-independence: If there is a directed edge from $u$ to $v$ and a directed edge from $v$ to $u$, then the function is invariant under swapping the directions of these two edges.</li> <li>Universality. At weakest, this condition ought to state that for each underlying multigraph $G$ and each team, there's some orientation $G'$ of the multigraph such that that team makes the playoffs.</li> <li>Weak independence of irrelevant alternatives. Suppose $G, G'$ differ only in the orientations of edges between $u$ and $v$. Then, if any team $w \in S$ is in exactly one of $f(G), f(G')$, one of $u$ or $v$ must be in exactly one of $f(G), f(G')$. (Intuitively, this says that the only way that changing the result of an individual game changes who's in the playoffs is if it causes one of the teams playing the game to drop out of or enter the playoffs.)</li> <li>No tactical losing. This is hardest to define, and the big reason why this is a soft question. Is there a reasonable way to make this condition rigorous that leads to an Arrow-type theoreM?</li> </ol> http://mathoverflow.net/questions/40877/arrows-theorem-and-the-postseason/40878#40878 Answer by TonyK for Arrow's theorem and the postseason TonyK 2010-10-02T22:07:10Z 2010-10-02T22:07:10Z <p>In the first playoff round, you let the first-placed team choose its opponent. Then you let the second-placed team choose its opponent (unless it was already chosen by the first-placed team). And so on.<br> In the second playoff round, you could repeat this process, or you could just use the order in which the first-round fixtures were chosen to determine the further seeding.<br> This may not answer your question, but it works!</p> http://mathoverflow.net/questions/40877/arrows-theorem-and-the-postseason/40879#40879 Answer by Tony Huynh for Arrow's theorem and the postseason Tony Huynh 2010-10-02T22:16:07Z 2010-10-02T22:32:43Z <p>Here's an attempt, which I view as sort of a monotonicity property.</p> <p><strong>4. (Monotonicity)</strong> Let $G'$ be obtained from $G$ by choosing $u \in V(G)$, and adding a subset of edges directed towards $u$. Then the position of $u$ on the list for $G'$ should not be higher than its position on the list for $G$.</p> <p>So, this loosely says that a team cannot advance its position by losing games. Think of $G$ as the partial results for the season so far (from which it should be theoretically possible to already rank the teams), and think of $G'$ as the final ranking at season's end. </p> http://mathoverflow.net/questions/40877/arrows-theorem-and-the-postseason/40910#40910 Answer by ross-millikan for Arrow's theorem and the postseason ross-millikan 2010-10-03T05:11:50Z 2010-10-03T05:11:50Z <p>Simple answer: make sure the teams are linearly ordered in skill and that every game result respects the order. Then any reasonable structure will find the best team and nobody will want to lose strategically.</p> <p>This is not as flip as it seems. In American baseball, the best teams win about 60% of the games in the regular season. In the playoffs, since the opponent is among the best, you would think that the chance of the weaker team winning a game is even higher than 40%. So a 5 or 7 game series could easily go to the weaker team. The simple answer is to crown the regular season (162 games) champion the winner. Probably the proper mathematical answer, but it gives away the revenue of playoff games-clearly unacceptable.</p> <p>This indicates there are two problems: each game does not find the better team, and some teams think (rightly or wrongly) that they have a better chance against a particular opponent than their position in the ranking would imply. The first can be solved with longer or more games, which may not be acceptable. The second requires transitivity in the probability of victory, which I suspect is more true than people admit but still not absolute.</p> http://mathoverflow.net/questions/40877/arrows-theorem-and-the-postseason/130947#130947 Answer by Waldemar for Arrow's theorem and the postseason Waldemar 2013-05-17T12:00:01Z 2013-05-17T13:22:38Z <p>I’m writing my doctoral thesis exactly on seeding in playoffs.</p> <p>First of all, strictly speaking, a system completely eliminating "tactical losing" can exist. I exclude the example given - a case when only one team advances to the playoffs. The system eliminating “tactical losing” is the one where all the teams participating in the regular season also participate in the postseason and the rule in the postseason is a “random seeding”, eg. all pairs can be formed with the same probability independent of the performance in the regular season. Of course, it is unacceptable. It is unfair and all the matches in the regular season are of a kind of friendly matches with no stake.</p> <p>The important insight from the above example is such that if we allow only some top teams to advance to the playoffs (as is always a case), even a random seeding cannot eliminate “tactical losing”. There’s always a chance that one team will try to knock the other team out of the postseason. I think the match San Francisco 49ers vs Los Angeles Rams from 1988 is a good example here – see <a href="http://en.wikipedia.org/wiki/Match_fixing#Better_playoff_chances" rel="nofollow">http://en.wikipedia.org/wiki/Match_fixing#Better_playoff_chances</a>.</p> <p>In my thesis I try to minimize the risk of temptations to “tactical losing”. I propose a measure of this risk (it takes into account the number of such temptations as well as their strength). I suggest a new method of seeding in the playoffs. The comparison of my method to different proposals is performed with Monte Carlo simulations.</p>