MathOverflow will be down for maintenance for approximately 3 hours, starting Monday evening (06/24/2013) at approximately 9:00 PM Eastern time (UTC-4).

## Arrow’s theorem and the postseason

There are a number of instances 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 usually pretty disappointing even for fans of teams who both win and benefit from the win -- and certainly for fans of the sport generally.

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.

So the question, albeit ill-defined, is this: Is there an analogue of Arrow's theorem for sports tournaments/leagues? (Or perhaps more appropriately an analogue of the related Gibbard-Satterthwaite theorem.)

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:

1. 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.
2. 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.
3. 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.)
4. 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?
-
 It is easy to avoid this problem by not having a single-elimination format (eg Mcintyre system, in particular their final four and final five). – Peter McNamara Oct 2 2010 at 22:54 Not mathematics per se, but note that your Weak Independence condition is already not compatible to the FIFA rules, where the ranking depends also on goal scored and against and comparison of such secondary information. So this already prevents some tactical losing (your second link). – Willie Wong Oct 3 2010 at 0:57 More mathematical: does the Path-Independence condition imply that you can just use a weighted direct graph instead of a multigraph? Also, the proof that I know of Arrow's theorem uses pretty strongly that each elector produces an ordering on all candidates. So it seems to me that the result you are musing about will have to be proved in a much different way. – Willie Wong Oct 3 2010 at 1:08 Lastly, in view of Weak Independence, I think tactical losing can be rendered moot if you allow the output of $F$ to be just a set rather than an ordered list. And just draw the DE table randomly. Of course, some people will complain that it is "not fair"... – Willie Wong Oct 3 2010 at 1:21 Regarding (2), you probably want some sort of connectedness assumption on $G$. For example, consider the extreme case of $G$ being an independent set. – Tony Huynh Oct 3 2010 at 1:35

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.
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.

-
This does not always work. For example, you might sometimes want to stuff Team X's ranking, knowing that they'll pick you as their opponent, if Team Y would be more difficult for you to beat. – Tom Church Oct 2 2010 at 23:50
You're absolutely right. I didn't think of that. – TonyK Oct 3 2010 at 0:19
What if every team in the playoff receives a seed at the beginning of the postseason, and in every round of the DE the highest ranked, currently surviving team, plays the lowest ranked one? This would heavily favour teams with good regular season performances, but would provide incentive not to get a low initial seed. – Willie Wong Oct 3 2010 at 2:46
@Willie Wong: No it wouldn't. Suppose the first and second teams have already been decided, but the first team is perceived as being easier to beat than the second team. (Don't forget, the best team doesn't always win.) Then it's better to be the last seed than the next-to-last. – TonyK Oct 3 2010 at 21:35

Here's an attempt, which I view as sort of a monotonicity property.

4. (Monotonicity) 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$.

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.

-
 But the idea behind tactical losing (slightly different from tactical voting) is that by losing games, you lower your ranking in the final ordered list, so that you have a potentially easier path in the DE table. To be more precise, in a tournament with a very strong first seed and mediocre other opponents, it may be desirable to lose in the regular season to drop ones ranking from 4th or 5th place to 6th or 7th place in the (8-team) playoff, to increase the chance of making to the Finals. (Assuming the 1st seed doesn't lose, the 4/5th place will face 1st in the semis.) – Willie Wong Oct 3 2010 at 2:42

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.

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.

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.

-
 How do you "make sure the teams are linearly ordered in skill"? A directed graph need not accommodate a compatible total ordering. Think rock-paper-scissor. – Willie Wong Oct 3 2010 at 12:50 "This indicates there are two problems: each game does not find the better team." Note that most sports fans do not believe this to be a problem. – JSE Oct 3 2010 at 19:15

I’m writing my doctoral thesis exactly on seeding in playoffs.

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.

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 http://en.wikipedia.org/wiki/Match_fixing#Better_playoff_chances.

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.

-