A paradox of tournament seeding

We analyse a mathematical model of seeding for sports contests with round-robin qualifying tournaments. The standard seeding system based on coefficients measuring the historical performance of the teams is shown to be unfair as it might potentially punish a team for its better results by having to face stronger opponents on average in the next stage. Major football competitions are revealed to suffer from this weakness. Incentive compatibility can be guaranteed by providing each qualified team with the highest coefficient of all teams that are ranked lower in its qualifying tournament for seeding purposes. Our proposal is illustrated by the 2020/21 UEFA Champions League.


Introduction
Every sports tournament has to provide appropriate incentives for the contestants to exert effort (Szymanski, 2003). In particular, the ranking method should not reward teams for poor performance (Vaziri et al., 2018). But the rules are complex in practice and sometimes lead to unforeseen consequences such as a situation when a team is worse off by winning (Kendall and Lenten, 2017).
Unsurprisingly, various theoretical models of sports contests have been considered in view of incentive compatibility. Pauly (2014) derives an impossibility theorem for championships consisting of two qualifying tournaments with disjoint sets of participants. Vong (2017) proves that, if more than one contestants advances to the next round, some players can benefit from shirking to qualify with a lower rank. Dagaev and Sonin (2018) investigate tournament systems, composed of multiple round-robin and knockout tournaments with the same set of participants when the sets of winners of noncumulative prizes have a nonempty intersection. Csató (2020a) considers group-based qualification systems where teams from different groups are compared, which can create incentives for both teams to play a draw instead of winning (Csató, 2020c). Csató (2021) and Csató (2022c) present how neglecting these theoretical findings has led to problems in European football. Krumer et al. (2020) show that strategic considerations may motivate a contestant to lose in a round-robin tournament because this can result in a higher expected payoff. Last but not least, Lenten and Kendall (2021) collect similar compelling ideas within the academic literature that could yet be considered and adopted by sports administrators.
Although the round-robin format in which each team meets all the others is one of the most common sports tournaments, it requires a lot of time to organise. On the other hand, if the competitors can play only against a limited number of opponents, the set of matches should be chosen carefully. This can be achieved through seeding, by ordering the entrants based on playing history and/or the judgement of experts to pair them according to their ranks. The problem of seeding in knockout tournaments has been thoroughly explored in the literature, see e.g. Hwang (1982); Horen and Riezman (1985); Schwenk (2000); Groh et al. (2012); Dagaev and Suzdaltsev (2018); Arlegi and Dimitrov (2020);Della Croce et al. (2022). The seeding rules of the most prominent football competition, the FIFA World Cup have also got serious attention (Scarf and Yusof, 2011;Guyon, 2015b;Laliena and López, 2019;Cea et al., 2020;Csató, 2022a). Similarly, several statistical papers have analysed the effect of seeding on tournament outcome (Monks and Husch, 2009;Corona et al., 2019;Dagaev and Rudyak, 2019;Engist et al., 2021).
However, no academic work has addressed the incentive compatibility of the seeding rules except for Csató (2020b), a paper revealing a unique shortcoming in the UEFA Champions League group stage draw that emerged from the 2015/16 season due to a misaligned way of filling vacant slots. Our main result is more universal: traditional seeding systems based on exogenous measures of teams' strengths are generically incentive incompatible-but they can be made strategyproof in a straightforward way.
Admittedly, these potentially unfair seeding rules rarely create incentives to lose ex ante. Analogously to the previous literature (Csató, 2019(Csató, , 2020aDagaev and Sonin, 2018), we can only provide hypothetical examples when a team is better off by losing. This is not surprising since these regimes are widely used in practice, thus, they probably would have been changed long ago if the probability of a tanking opportunity would be substantially higher. Nonetheless, we think that (a) even the punishment for better results can be detrimental to the business model of the sports industry if the stakeholders realise this unfairness at the end of a competition; and (b) the academic community can make an important service to the decision-makers and the society by highlighting every issue of potential problems around incentives.
Consequently, the current paper makes a contribution by calling attention to a shortcoming of standard seeding systems that are extensively used in major sports competitions. Therefore, the regulatory bodies will have an opportunity to consider the seriousness of this weakness, and to adopt our proposal for an incentive compatible seeding rule, or to take other measures to prevent tanking, for instance, by choosing a schedule that maximises competitiveness.
Our roadmap is as follows. Section 2 presents two real-world cases to highlight the issue. A mathematical model is given in Section 3. We provide a strategyproof seeding mechanism and summarise policy implications in Section 4. Finally, Section 5 concludes. • The first leg of Sweden vs. Italy was 1-1 (instead of 1-0) on 10 November 2017 in the UEFA Second Round, hence Italy qualified for the World Cup.
In the draw for the 2018 FIFA World Cup, the composition of the pots depended on the October 2017 FIFA World Ranking. The only exception was the automatic assignment of the host-Russia-to Pot 1 besides the seven highest-ranked qualified teams. Hence Uruguay (17th in the relevant FIFA ranking) would have been drawn from Pot 3 as among the best 16 teams, only Chile would have not qualified in the above scenario (Wales was the 14th and Italy was the 15th in the FIFA World Ranking of October 2017). The allocation of the teams in the above scenario is given in Table 1. Consider what would have happened if the result of the match Paraguay (34) vs. Uruguay, played on 5 September 2017 in the South American qualifiers, would have been 2-1 instead of 1-2. Then Uruguay would have remained second and Paraguay would have been fifth in this qualifying competition. Paraguay would have played against New Zealand (122) in the OFC-CONMEBOL qualification play-off, thus Peru (10) could not have qualified for the World Cup. Therefore, Uruguay would have been drawn from the stronger Pot 2 instead of Pot 3 merely due to its loss against Paraguay. It probably means a substantial advantage: in the 2018 FIFA World Cup, seven and two teams advanced to the knockout stage from Pots 2 and 3, respectively.  (2) Switzerland (11) Costa Rica (22) Australia (43) Portugal (3) England (12) Sweden (25) Japan (44) Argentina (4) Colombia (13) Tunisia (28) Morocco (48) Belgium (5) Wales (14) Egypt (30) Panama (49) Poland (6) Italy (15) Senegal (32) South Korea (62) France (7) Mexico (16) Iran (34) Saudi Arabia (63) The pots are determined by the FIFA World Ranking of October 2017, see the numbers in parenthesis.
Russia is the top seed as host.
Teams written in italics qualified only in the hypothetical but feasible scenario of Example 1.
Uruguay (17) Example 1 contains a small sloppiness since we have not checked whether the October 2017 FIFA World Ranking would have been changed. However, this issue does not affect the potential case of incentive incompatibility.
Example 2. In the draw for the 2020/21 UEFA Europa League group stage, the composition of the pots was determined by the 2020 UEFA club coefficients, available at https://kassiesa.net/uefa/data/method5/trank2020.html. Assume the following hypothetical modifications to real-world results in the play-off round of the qualifying phase, with the first favourite team advancing to the group stage in place of the second unseeded underdog (the UEFA club coefficients are given in parenthesis): There were 48 teams in the group stage. Leicester City (22.0) was ranked 20th because Rapid Wien (22.0) had the same 2020 UEFA club coefficient but the tie-breaking criterion-coefficient in the next most recent season in which they are not equal (UEFA, 2020b, Annex D.8)-preferred the latter club. Due to the above changes, five teams with a higher coefficient than Leicester City would have qualified instead of five teams with a lower coefficient. Hence, Leicester City would have been only the 25th highest-ranked, namely, the best club in Pot 3 as each of the four pot consists of 12 clubs. In addition, suppose that Leicester defeated Norwich City at home by 2-1 (instead of 0-0) in the 2019/20 English Premier League. Then Leicester City would have remained fifth at the end of the season with 64 points. The allocation of the clubs in the above scenario is presented in Table 2. Consider what would have happened if the outcome of the match Wolverhampton Wanderers (18.092) vs. Leicester City, played on 14 February 2020 in the 2019/20 Premier League, would have been 1-0 instead of 0-0. Leicester would have remained fifth with 62 points, while Wolverhampton would have been sixth with 61 points rather than Tottenham Hotspur (85.0), which scored 59 points. Consequently, Wolverhampton would have entered the Europa League qualification in the second qualifying round, and it could have qualified for the group stage in the place of Tottenham. Then Leicester would have been drawn from the stronger Pot 2 merely due to its loss against Wolverhampton. This probably means an advantage, although in the 2020/21 Europa League, six teams advanced to the knockout stage from both Pots 2 and 3, respectively.
Examples 1 and 2 uncover that a team can be worse off by winning in the South American qualifiers of the FIFA World Cup and the English Premier League, respectively. By changing the schedule of these round-robin tournaments such that the sensitive games (Paraguay vs. Uruguay and Wolverhampton Wanderers vs. Leicester City, respectively) are played in the last round, losing can be made beneficial for a team because its final ranking is not affected but the modified set of the teams qualifying (Paraguay instead of Peru and Wolverhampton Wanderers instead of Tottenham Hotspur, respectively) allows to be placed with a higher probability in a higher-ranked seeding pot, independently of the outcome of the matches to be played later. For instance, note that Leicester City always prefers to qualify together with Wolverhampton Wanderers instead of Tottenham Hotspur as the former scenario results in gaining one position in the ranking used for seeding compared to the latter scenario, which might lead to being in a better seeding pot with a positive probability.

Theoretical background
Consider a round-robin qualifying tournament with a set of teams T , where each team t ∈ T has a coefficient ξ t . The teams ranked between the pth and qth (p ≤ q) positions qualify for the second stage. There, a qualified team t has a seeding value Ψ t , which is usually (but not necessarily) its coefficient ξ t as we have seen in Examples 1 and 2.
Any team prefers if more teams play in the second round with a lower coefficient. In other words, it is a common belief that these measures positively correlate with true abilities. All coefficients used in practice are constructed along this line. For instance, the FIFA World Ranking and the UEFA coefficients for national teams, countries, and clubs alike award more points for wins (draws) than for draws (losses), thus better achievements in the past translate into a higher value.
Therefore, the first goal for every team is to qualify and the second goal is to qualify together with teams having a lower coefficient. Any team t ∈ T may lose a match to improve the second objective without deteriorating the first. Denote the (strict) rankings of the qualifying tournament by ≻ and ≻ ′ , the ranks of team s ∈ T by #(s) and # ′ (s), as well as the sets of teams qualified by Q = {s ∈ T : p ≤ #(s) ≤ r} and Q ′ = {s ∈ T : p ≤ # ′ (s) ≤ r} before and after the manipulation, respectively. Definition 1. Incentive compatibility with respect to seeding: A round-robin qualifying tournament is said to be incentive compatible with respect to seeding if no team t ∈ T ever has a manipulation strategy such that: • team t qualifies for the second stage both before and after the manipulation, that is, t ∈ Q and t ∈ Q ′ ; • team t has a better seeding position after the manipulation than before, namely, |s ∈ Q ′ : Ψ s > Ψ t | < |s ∈ Q : Ψ s > Ψ t |.
Otherwise, the qualifying tournament is called incentive incompatible with respect to seeding.
As it has been revealed in Section 2, a qualifying tournament is incentive incompatible if Ψ t = ξ t for all t ∈ Q and 2 ≤ |Q| < |T |. In particular, a situation may exist where team i has already secured qualification, while teams j and k compete for another slot such that ξ k > ξ i > ξ j . Then team i may consider losing against team j in order to push it to the next stage at the expense of team k as team i can get a better seeding pot by taking team j to the second round instead of team k.
The result below provides sufficient conditions to prevent a strategic manipulation of this type. For the sake of simplicity, we assume that ties in the seeding values of qualified teams are broken in favour of the team ranked higher in the qualifying tournament.

Proposition 1. A round-robin qualifying tournament is incentive compatible with respect to seeding if at least one of the following conditions hold:
• Only one team is allowed to qualify: p = q; • All teams qualify: p = 1 and q = |T |; • The seeding value of each qualified team t ∈ Q in the second stage is equal to the maximal coefficient of the teams that are ranked lower than team t in the qualifying round-robin tournament: Ψ t = max{ξ s : t ≻ s} for all t ∈ Q.
Proof. If p = q, then t ∈ Q leads to |s ∈ Q : Ψ s > Ψ t | = 0. Consequently, no manipulation strategy can be found according to Definition 1. p = 1 and q = |T | result in Q = T , thus |s ∈ Q ′ : Ψ s > Ψ t | = |s ∈ Q : Ψ s > Ψ t |, which excludes the existence of a manipulation strategy as required by Definition 1. Ψ t = max{ξ s : t ≻ s} for all t ∈ Q implies that s ∈ Q and Ψ s > Ψ t ⇐⇒ s ∈ Q and s ≻ t.
Since team t cannot be ranked higher in the round-robin qualifying tournament after the manipulation, holds. Hence, the qualifying tournament is incentive compatible with respect to seeding.
In the previous literature on the incentive compatibility of sports tournaments, only two papers consider multistage competitions. Csató (2022b) discusses the case when the subsequent phases are related such that the results of some matches played in the previous stage(s) are carried over. Vong (2017) analyses a general model with an arbitrary design but, crucially, the allocation of the teams into groups is assumed to be fixed a priori. Therefore, in the proof of his main theorem, a team is interested in manipulation because it knows that if it achieves a higher rank in the qualifying tournament, then it will play in a group where elimination is guaranteed. On the other hand, our model contains more uncertainty regarding the opponents in the next stage. Hence, losing is beneficial only if it leads to a better seeding position, which is impossible under the conditions of Proposition 1.

Discussion
Now a general procedure is presented to guarantee our requirement, incentive compatibility with respect to seeding, on the basis of the theoretical model. Some alternative ideas are also outlined shortly.
According to Proposition 1, there are three ways to achieve strategyproofness in a round-robin qualifying tournament. However, the first two conditions-when exactly one team qualifies or all teams qualify for the next round-could not offer a universal rule. Nonetheless, they can be exploited in certain cases, for example, only one team advanced from the Oceanian (OFC) section of the 2022 FIFA World Cup qualification. Fortunately, there is a third opportunity, that is, to calculate the seeding value of any qualified team t ∈ Q as Ψ t = max{ξ s : t ≻ s}. In other words, team t is seeded in the second stage based on the maximum of coefficients ξ s of all teams s ranked lower than team t in its round-robin qualifying competition. This is a reasonable rule: if team i finishes ahead of team j in a league, why is it judged worse for the draw in the next round? Our proposal is called strategyproof seeding. Table 3 applies strategyproof seeding for the 2020/21 Champions League group stage. Even though the seeding values of 15 teams, including the 11 lowest-ranked, are increased, it has only a moderated effect on the composition of pots as one German and two French teams benefit at the expense of four teams from the Netherlands, Austria, Greece, and Russia. That amendment usually favours the highest-ranked associations, where some clubs emerging without a robust European record (recall the unlikely triumph of Leicester City in the 2015/16 English Premier League (BBC, 2016)) can "obtain" the performances of clubs with considerable achievements at the international level. Thus, strategyproof seeding contributes to the success of underdogs in the European cups, which may be advantageous for the long-run competitive balance in the top leagues. In addition, it probably better reflects the true abilities of the teams since playing more matches reduces the role of luck in sports tournaments (McGarry and Schutz, 1997;Scarf et al., 2009;Lasek and Gagolewski, 2018;Sziklai et al., 2022). Consequently, it is more difficult to perform better in a round-robin league than in the Champions League or Europa League.
From the 2018/19 season onwards, UEFA club coefficients are determined either as the sum of all points won in the previous five years or as the association coefficient over the same period, whichever is the higher (Kassies, 2022;UEFA, 2018). This rule was effective in the 2020/21 Champions League, the lower bound applied in the case of some Spanish, German, and French teams in the 2020/21 Europa League. A somewhat similar policy is used in the UEFA Champions League and Europa League qualification, too, if a later round is drawn before the identity of the teams is known (Csató, 2022d): "If, for any reason, any of the participants in such rounds are not known at the time of the draw, the coefficient of the club with the higher coefficient of the two clubs involved in an undecided tie is used for the purposes of the draw." Therefore, the principle of strategyproof seeding is not unknown in UEFA club competitions, which can support its implementation. Table 3 reinforces that the strategyproof seeding system may result in more ties than the current definition. If some teams inherit their seeding values from the same lowerranked team, then these remain identical, and the tie should be broken by drawing of lots (UEFA, 2020a, Annex D.8). Although tie-breaking does not affect incentive compatibility, it is reasonable to prefer the teams ranked higher in the domestic league. If clubs from other associations also have the same seeding value (which has a much lower probability), they can be assigned arbitrarily in this equivalence class. Alternatively, the original club coefficients can be used for tie-breaking. In Table 3, two French teams at the boundary of Pots 2 and 3, Marseille and Rennes, inherit the same seeding value from Lyon. However, Marseille finished ahead of Rennes and has a higher coefficient, hence it is placed in Pot 2.
Our incentive compatible mechanism has further favourable implications. UEFA has modified the pot allocation policy in the Champions League from the 2015/16 season, probably inspired by the previous year when Manchester City, the English champion, was drawn from the second pot but Arsenal, the fourth-placed team in England, was drawn from the first pot. This decision-intended to strengthen the position of domestic titleholders (UEFA, 2015)-has considerable sporting effects (Corona et al., 2019;Dagaev and Rudyak, 2019), especially since the poor way of filling vacancies leads to incentive incompatibility (Csató, 2020b). On the other hand, the proposed seeding rule guarantees that a national champion has at least the same seeding value as any team ranked lower in its domestic league.
Naturally, other strategyproof seeding policies can be devised. One example is the system of the 2020 UEFA European Championship: the ranking of all entrants on the basis of their results in the qualification. However, that principle is not appropriate if the achievements in the qualifying tournament(s) cannot be compared. Another solution might be to associate seeding positions not with the coefficients but with the path of qualification. For instance, a club can be identified in the UEFA Champions League as the Spanish runner-up rather than by its name. The results of these "labels" can be measured by the achievements of the corresponding teams (Guyon, 2015a).
To conclude, the recommended strategyproof seeding mechanism provides incentive compatibility in any setting. While other rules are also able to eliminate perverse incentives, they are unlikely to be independent of the particular characteristics of the tournament.

Conclusions
The present work has analysed a mathematical model of seeding for sports tournaments where the teams qualify from round-robin competitions. Several contests are designed this way, including the most prestigious football tournaments (FIFA World Cup, UEFA European Championship, UEFA Champions League). The necessary conditions of incentive incompatibility have turned out to be quite restrictive: if each competitor is considered with its own coefficient (usually a measure of its past performance), only one or all of them should qualify from every round-robin contest.
Similar to the main findings of Vong (2017) and Krumer et al. (2020), our result has the flavour of an impossibility theorem at first glance. However, here we can achieve strategyproofness by giving to each qualified competitor the highest coefficient of all competitors that are ranked lower in its round-robin qualifying tournament for seeding purposes.
The central message of this paper for decision makers is consonant with the conclusion of Haugen and Krumer (2021), that is, tournament design should be included into the family of traditional topics discussed by sports management. In particular, administrators are strongly encouraged to follow our recommendation in order to prevent the occurrence of costly scandals in the future.