Eight female badminton players were disqualified from the Olympics on Wednesday for trying to lose matches the day before, the Badminton World Federation announced after a disciplinary hearing.
The players from China, South Korea and Indonesia were accused of playing to lose in order to face easier opponents in future matches, drawing boos from spectators and warnings from match officials Tuesday night.
All four pairs of players were charged with not doing their best to win a match and abusing or demeaning the sport.
Apparently the Badminton competition has the typical structure of a preliminary round followed by an elimination tournament. Performance in the preliminary round determines seeding in the elimination tournament. The Chinese and South Korean teams had already qualified for the elimination tournament but wanted to lose their final qualifying match in order to get a worse seeding in the elimination tournament. They must have expected to face easier competition with the worse seeding.
This widely-used system is not incentive-compatible. This is a problem with every sport that uses a seeded elimination tournament. Economist/Market Designers have fixed Public School Matching and Kidney Exchange, let’s fix tournament seeding. Here are two examples to illustrate the issue:
1. Suppose there are only three teams in the competition. Then the elimination tournament will have two teams play in a first elimination round and the remaining team will have a “bye” and face the winner in the final. This system is incentive compatible. Having the bye is unambiguously desirable so all teams will play their best in the qualifying to try and win the bye.
2. Now suppose there are four teams. The typical way to seed the elimination tournament is to put the top performing team against the worst-performing team in one match and the middle two teams in the other match. But what if the best team in the tournament has bad luck in the qualifying and will be seeded fourth. Then no team wants to win the top seed and there will be sandbagging.
As I see it the basic problem is that the seeding is too rigid. One way to try and improve the system is to give the teams some control over their seeding after the qualifying round is over. For example, we order the teams by their performance then we allow the top team to choose its seed, then the second team chooses, etc. The challenge in designing such a system is to make this seed-selection stage incentive-compatible. The risk is that the top team chooses a seed and then after all others have chosen theirs the top team regrets its choice and wants to switch. If the top team foresees this possibility it may not have a clear choice and this instability is not only problematic in itself but could ruin qualifying-round incentives again.
So that is the question. As far as I know there is no literature on this. Let’s us, the Cheap Talk community, solve this problem. Give your analysis in the comments and if we come up with a good answer we will all be co-authors.
UPDATE: It seems we have a mechanism which solves some problems but not all and a strong conjecture that no mechanism can do much better than ours. GM was the first to suggest that teams select their opponents with higher qualifiers selecting earlier and Will proposed the recursive version. (alex, AG, and Hanzhe Zhang had similar proposals) The mechanism, lets call it GMW, works like this:
The qualifiers are ranked in descending order of qualifying results. (In case the qualifying stage produces only a partial ranking, as is the case with the group stages in the FIFA World Cup, we complete the ranking by randomly ordering within classes.) In the first round of the elimination stage the top qualifier chooses his opponent. The second qualifier (if we was not chosen!) then chooses his opponent from the teams that remain. This continues until the teams are paired up. In the second round of elimination we pair teams via the same procedure again ordering the surviving teams according to their performance in the qualifying stage. This process repeats until the final.
It was pointed out by David Miller (also JWH with a concrete example, and afinetheorem) that GMW is not going to satisfy the strongest version of our incentive compatibility condition and indeed no mechanism can.
Let me try to formalize the positive and negative result. Let’s consider two versions of No Envy. They are strong and weak versions of a requirement that no team should want to have a lower ranking after qualifying.
Weak No Envy: Let P_k(r,h) be the pairing that results in stage k of the elimination procedure when the ordering of teams after the qualifying stage was r and the history of eliminations prior to stage k is given by h. Let r’ be the ordering obtained by altering r by moving team x to some lower position without altering the relative ordering of all other teams. We insist that for every r, k, h, and x, the pairing P_k(r,h) is preferred by team x to the pairing P_k(r’,h).
Strong No Envy: Let r’ be an ordering that obtains by moving team x to some lower position and possibly also altering the relative positions of other teams. We insist that for every r,k,h, and x, the pairing P_k(r,h) is preferred by team x to P_k(r’,h).
GMW satisfies Weak No Envy but no mechanism satisfies Strong No Envy. (The latter is not quite a formal statement because it could be that the teams pairing choices, which come from the exogenous relative strengths of teams, make Strong No Envy hold “by accident.” We really want No Envy to hold for every possible pattern of relative strengths.)
One could also weaken Strong No Envy and still get impossibility. The interesting impossibility result would find exactly the kind of reorderings r->r’ that cause problems.
Finally, we considered a second desideratum like strategy-proofness. We want the mechanism that determines the seedings to be solvable in dominant strategies. Note that this is not really an issue when the teams are strictly ordered in objective strength and this ordering is common knowledge. It becomes an issue when there is some incomplete information (an issue raised by AG, and maybe also when there are heterogeneous strengths and weaknesses, also mentioned by AG.)
Formalizing this may bring up some new issues but it appears that GMW is strategyproof even with incomplete information about teams strengths and weaknesses.
Finally, there are some interesting miscellaneous ideas brought up by Scott (you can unambiguously improve any existing system by allowing a team who wins a qualifying match to choose to be recorded as the loser of the match) and DRDR (you minimize sandbagging, although you don’t eliminate it, by having a group format for qualifiers and randomly pairing groups ex post to determine the elimination matchups, this was also suggested by Erik, ASt and SX.)
Cheap Talk 
89 comments
Comments feed for this article
August 1, 2012 at 2:30 pm
GM
Wild guess: The top-performing team picks its opponent among the qualifiers, the second top-performing team picks the opponent among the left-overs, etc… That should give incentives to perform during the qualifiers and the selection should be incentive compatible.
August 1, 2012 at 2:33 pm
jeff
looks good. but what about position within the overall elimination bracket? same mechanism?
August 1, 2012 at 2:38 pm
jeff
i guess we could also just have the top qualifier set the entire bracket. but this doesn’t give an incentive to be the second qualifier rather than a third which seems undesirable.
August 1, 2012 at 2:51 pm
Will
Have the teams pick their opponents each round with GM’s mechanism. Of course it is a tougher problem if they choose their seeds and then the knockout proceeds in the typical manner.
August 1, 2012 at 2:52 pm
John
The problem is that the top team has externalities as to the other matches (in case in loses they become relevant).
August 1, 2012 at 3:43 pm
jeff
Here is a potential problem. Suppose N teams enter the competition and the elimination tournament will have M<N teams. This is almost always the structure if for no other reason than M must be a power of 2
Then in your system the top team wants the weakest teams to qualify. It may have an incentive to lose to a weak team in the qualifying in order to allow it to qualify and then pick it as an opponent.
August 1, 2012 at 3:51 pm
David Miller
+jeff: I think this problem cannot be eliminated if we want the mechanism to depend only on the rank order of teams. Once the top team has clinched its position, it is liable to want to lose to some teams “on the bubble.”
August 1, 2012 at 4:40 pm
jeff
¥david, agreed except if you randomly seed or if you make the top qualifier a dictator (let him set the entire bracket).
August 1, 2012 at 6:23 pm
John
The top team as a dictator does not help. The top team will still want to lose in the first round to a team it knows it can beat in the second.
August 1, 2012 at 2:43 pm
John
IC alone is easy. Use randomization in the second round. However, in some sense this is not fair to the top ranked teams since their advantage does not carry over. This prevents you from having an accurate ranking based on the second round.
IC and fairness can be achieved by eliminating the second stage (which also smooths out randomness inherent in elimination tournaments). From a pure mechanism design I see no reason to have the second stage at all.
If you wish to have an elimination stage and have an accurate ranking you must have fixed seeding. If you do not have fixed seeding the choice of matches in the second round prevents you from having an accurate ranking. Hence, you get the problem you observe.
August 1, 2012 at 3:31 pm
David Miller
+John: I agree that a “round robin” format is most likely to generate an accurate ranking and is always incentive compatible, but a round robin without an elimination round does not guarantee a unique winner. Also, elimination rounds are exciting! I think that entertainment value, rather than having an accurate ranking, is the primary goal of the competition. Part of Jeff’s point is that incentive compatibility has entertainment value, because it induces consistent effort. This is evidenced by the reaction of the spectators when the players were trying to throw their matches.
August 1, 2012 at 3:37 pm
jeff
To be clear, by IC I mean nobody wants to sandbag in the qualifiers. You are right that this can be achieved trivially but lets ask for a strict version where all teams are “trying to win”
Let’s call this No Sandbagging from now on. It is going to be related to a kid of no-envy condition. We want the final tournament position of the nth best qualifier to NOT want to switch his position with the n+1st qualifier.
Another desideratum is Stability of the seeding process. Given the outcome of the qualifying round the teams will play some mechanism which will determine their position in the elimination tournament. Ideally we want this mechanism to be strategy proof.
It may be that the result we are looking for tells us the limits of this kind of system I. Terms of a tradeoff between No Sandbagfing and Stability.
August 1, 2012 at 6:27 pm
John
Essentially you are asking for IC in strictly dominant strategies. Again this can be achieved trivially.
For example, N*(N-1) matches. A match is then chosen at random and the winner of that match wins the total competition. This is IC in dominant strategies but not very interesting sportsmanship.
August 1, 2012 at 2:53 pm
alex
Here’s a solution: after the first round, as you suggest, the team ranked 1 chooses its opponent first, then the team ranked 2 chooses its opponent, etc. After the games have been played, the remaining team that had the best ranking in the first stage chooses its opponent among the remaining teams, then the second chooses its opponent, etc. The way I see it, it is always better to be ranked as high as possible.
August 1, 2012 at 2:56 pm
alex
Actually you only suggested that teams would choose their seeds, but I guess it’s better to choose your opponent.
August 1, 2012 at 2:54 pm
AG
Suppose that there is an underlying team quality, which is expressed (with error) in match performance, and is also privately observed (maybe also with a different error) by other teams. When match performance is worse than a player’s assessment, you want to avoid being seeded against them.
Seeding should somehow incorporate game performance as well as eliciting player assessments of others quality. Winning the game should always allow the player to meet a worse-ranked team by their own assessed quality, relative to the choice they have when losing.
What about this: all teams play an initial round robin and are ranked according to match performance. The top winner can then choose his opponent, and so on down. The incentive is to play better in every initial round, because every win increases your choice set in the final pick.
This system is also robust to a team’s quality being different depending on the “style” of the team which they are playing against. Suppose I am really good against the method of play favored by the Australians, but bad against the Japanese. I want to do really well in the preliminary round to maximize my chances of picking the Australians as my partner, and avoid being picked by the Japanese.
August 1, 2012 at 2:59 pm
David Miller
Reseed after the first round of the elimination bracket (this is not a new idea) and run the same process. This should be incentive compatible all the way through, and regret-free for the winners in each round.
August 1, 2012 at 3:02 pm
Will
Assume we can’t have teams choose their opponents in each round, so seeds have to be set before the knockout. Maybe one solution would be to have several rounds of bidding. In the first round, the first ranked team chooses its seed, then the second ranked team chooses its seed, etc. In subsequent rounds we go through in order again and any team is allowed to swap its seed with a lower-ranked team. Equivalently, give the nth ranked team the nth seed then start in the second round of bidding.
August 1, 2012 at 3:03 pm
John
Does not necc converge…
August 1, 2012 at 3:07 pm
Will
My guess is that this converges to an equilibrium with regret, so there shouldn’t be any cycles. Hopefully it reaches equilibrium in theory in at most some finite number of steps, maybe n, 2^n, or n! steps. In practice it should converge pretty quickly; we probably don’t want teams to have the hassle of dealing with this. So the tougher challenge is then to require teams to rank preferences over some small set (maybe over all opponents, not all n! seedings) and then run an algorithm so that there is only one round of decisions and not some back and forth.
August 1, 2012 at 3:09 pm
Will
*without regret. John, what is necc converge? Google and Google Scholar fail me.
August 1, 2012 at 3:21 pm
David Miller
I think John meant “necessarily converge.” In general this method will lead to cycles. Jeff’s scenario, in which Team A chooses its seed but then regrets after Team B chooses, also applies to Team B regretting after Team A chooses a different seed. In this method Team A and B can end up flipping back and forth forever. If you cut the process off at any point, it won’t be incentive compatible.
August 1, 2012 at 3:48 pm
Will
I wasn’t clear or maybe I am just wrong. Your rank is determined by your play in the round robin. Then your seed for the knockout is determined by this swapping mechanism. To avoid cycles, you can only switch with a lower-ranked (by performance in round robin) team.
August 1, 2012 at 6:43 pm
John
Even if you can only switch with a lower ranked team the problem remains. Team 1 (by rank) will want to choose team 3 iff team 2 wants to choose team 4. Team 2 wants to choose team 4 iff team 1 does *not* choose team 3.
Infinite loop.
August 1, 2012 at 3:13 pm
GM
Another wild guess for the overall bracket (8 team example):
–seed1 vs choice of seed 1—-
——-
–seed 4 vs choice of seed 4—
–seed 2 vs choice of seed 2—
——-
–seed 3 vs choice of seed 3—
August 1, 2012 at 3:17 pm
David Miller
This doesn’t work: Suppose I think seed 2 is better than seed 1; then I prefer to be seed 4 over seed 3. This is why we need to reseed after each elimination round.
August 1, 2012 at 3:15 pm
Scott
The winner of each game always has the option to choose the official outcome of the game. In soccer this means the winner can choose to walk away with three points, one point, or zero points.
I am not sure this solves all problems, but at least in ensures that teams never want to actively lose a game.
August 1, 2012 at 3:17 pm
David Miller
+Scott: Great idea!
August 1, 2012 at 3:30 pm
jeff
Scott doesn’t this have multiple equilibria? The winner of match A might want to choose to be the official winner of match A only if the winner of match B is choosing to be the official loser of match B.
August 1, 2012 at 3:36 pm
David Miller
+jeff: It’s still incentive compatible, just not regret-free.
August 1, 2012 at 6:30 pm
John
Good idea but this only gives you weakly dominant strategies. I don’t see how you could make it strongly dominant.
August 1, 2012 at 10:21 pm
Scott
David, thanks for the support! Jeff, just read your earlier replies and I think what I suggest definitely prevents “sandbagging,” full stop.
Also, I agree with multiple equilibria, but at least this problem has been punted to a coach submitting an envelope, and not players angering fans.
August 1, 2012 at 11:39 pm
jeff
Scott: if a team wants to lose a match they can do it in two ways: win the match and call itself the winner or just lose (if they expect the opponent to call itself the winner). If it wants to conserve effort it would prefer to lose.
August 2, 2012 at 2:56 am
Evan
I think there could be a problem here. In the case where there are two teams (winners of matches A and B) making strategic decisions If there exists a mixed strategy equilibrium then there will be a ‘co-ordination’ problem where the worst outcome could accidently be selected. Perhaps if team A threw their match, forcing team C to play the strategic decision game against team B, their could be a unique NE where team A qualifies for the next stage.
August 2, 2012 at 1:45 pm
Roger
@jeff: If you make almost any threat at all of disqualifying intentional losers, (which was surely made in this case), then that should overcome the “conserving effort” effect. I doubt any team would take even a minuscule risk of being kicked out.
August 1, 2012 at 3:43 pm
btwied@umich.edu
The proposals so far where teams get to choose opponents in order of rank provide no positive incentives to care about rankings within the bottom half. Perhaps the matchups for the later rounds could be chosen by the highest ranked teams that haven’t gotten to pick (so if the chosen first-round matchups are 1v8, 2v7, 3v6, 4v5, then 5 would get to choose which game their opponents would come from assuming they beat 4).
August 1, 2012 at 3:53 pm
GM
True if the quality of teams is known. If it is not, teams in the bottom half would want to win to signal their talent.
August 1, 2012 at 3:56 pm
Ariel Procaccia
In that case you may prefer to be 4 rather than 3, because your “partner” (5) would have their pick for the next round (which potentially would be played by you).
August 1, 2012 at 5:06 pm
jeff
I thought that the issue identified by btwied is taken care of by the sequential re-seeding version of GM’s mechanism. Suppose for example that in the first elimination round all of the lower seeds won their matches. Then the order among the bottom half determines the order of choosing opponents in the second round.
If the bottom teams continue to win in every stage of the elimination then for every n there will come a stage where you are better off having been the nth qualifier rather than the n+1st.
The one exception is the bottom two qualifying positions. You are always indifferent between those two qualifying positions because they are both always in the bottom half until the final when they play each other and there is nothing to choose.
August 1, 2012 at 4:00 pm
Jason Hartline
Here is a project that looks at dynamically pairing contestants so that they can be ranked by ability.
http://research.microsoft.com/en-us/projects/trueskill/
Was there any convergence on what the objective should be? As John pointed out, trivial mechanisms satisfy the strategic requirements. If you restrict to olympics, then a possible objective would be to maximize the probability of getting the top three ranking correct (a la, the a secretary problem). Other objectives might be to minimize the expected number of swaps between the obtained ranking and the correct ranking.
August 1, 2012 at 5:25 pm
jeff
Here is an abstract model to frame the question. There will be two stages of the competition with the second stage being an elimination tournament. This is given to us. (David above gave the right motivation for this.)
We can model the first stage in reduced form by simply assuming that each team makes a binary effort choice (no effort vs yes effort) and as a function of all of the effort choices there is determined (perhaps stochastically) an ordering of the teams. This represents in reduced form a round robin, or group stage or any other system currently in use.
Our problem is to design a game to be played in between the two stages. Lets call it the seeding game. In this game the teams send messages and there is an outcome function which takes as an input the messages sent and the first-round rankings and outputs a tournament bracket.
The goals are some combination of No Sandbagging (the strong version, i.e. every team should strictly prefer to spend effort in the qualifying stage) and Stability (the seeding game should be dominant strategies or satisfy some other desirable stability property)
There is a separate question of how to make sure that the best team wins the overall competition.
August 1, 2012 at 5:33 pm
David Miller
+jeff: We might be interested in a weaker version of no-sandbagging: No team should prefer to throw a game IN ORDER TO hurt its ranking. I think it will be very difficult to get incentive compatibility for a game that does not change the ranking, because then to overcome incentive problems we will need to make the mechanism depend strictly on the results of such games.
August 1, 2012 at 5:44 pm
Jason Hartline
You still haven’t specified an objective. Given two mechanisms which are stable and have no sandbagging, which should one prefer? You would of course like to rule out the mechanism where the outcome of the first stage is ignored and the seeds to the second stage is random/arbitrary. (John pointed this out earlier.)
I disagree with David that the current format is entirely for entertainment value. The tournament stage is to reduce variance in the round-robin stage assuming the only statistic we care about is identifying the best team. There is a tradeoff in likelihood of identifying the best team and number of matches (or perhaps the maximum number of matches any team must play, which might be the more relevant constraint). As was mentioned, the outcome of the matches are noisy.
Suppose teams are honest: do we know that the round-robin + single-elimination tournament optimizes probability of selecting the best contestant subject to a constraint on the maximum number of games any contestant can compete in?
August 1, 2012 at 6:03 pm
jeff
Jason, you could say that the objective is to maximize effort subject to the constraint that the seeding game is stable. So No Sandbagging is just a way of saying we want the first-best, i.e. maximum effort.
But I agree with you that trying to maximize the probabilty that the objectively best team wins the overall tournament is another interesting question. And if that is the real objective then instead of assuming the tournament structure we would want to show that it is optimal.
(But I don’t think we want a mechanism that achieves this by giving the weaker teams reduced incentives to try hard. So formulating this problem may be more subtle than it appears at first.)
August 1, 2012 at 4:43 pm
Hanzhe Zhang
The players from the top half of the players sequentially pick their opponents from the bottom half. Then half of the players are eliminated, and the top half of the remaining players choose the opponents from the remaining bottom half. The problem of odd number of players is solved by giving the top player (or top odd number of players) “byes”.
For example, if there are four players, #1 picks his opponent between #3 and #4 and #2 is paired with the one #1 didn’t pick. If there are three players, #1 automatically advances to the final, and #2 and #3 play to gain the chance of playing with #1. If there are 8 players, we just use the algorithm repeatedly. Say that the first round of picking resulted in matches of (1,6), (2,8), (3,7), (4,5), and winners are 1,2,7,4 respectively, then 1 picks between 4 and 7…
This algorithm is envy-free, and sequentially consistent, and “fair” to better players. No one has incentive to lose to be lower ranked in the seeding determination round.
However, one problem is the lack of incentives for the bottom half to compete to be better seated as they are always getting picked (for example, in the seeding round, if two players meet to determine whether who is #6 and who is #7 in 8-player tournament, they have no incentives to play hard). One possible way to fix it and give even lower-ranked players incentives to improve their ranks is to restrict higher-seeded players from choosing among the entire bottom half. That is, in 8-player tournament, #1 is restricted to choose an opponent between #7 and #8 instead of #5-#8, and #2 to choose between #6 and the remaining of #7 and #8. This way, if #6 and #7 prefer playing #2 over #1, they will play as hard as they can in the seed-determination round. This still avoids the same-country problem: since each player has a non-degenerate choice set, he can always choose to avoid his countryman if he wishes.
August 1, 2012 at 6:49 pm
John
While it is true that nobody has incentive to be lower ranked it is still not IC. The motivation to lose in order to allow a weaker player (not universally weaker but just weaker in style vs the top team) pass to the second round remains.
August 1, 2012 at 6:10 pm
soxsail
The problem is not in the tournament system, but in the reward system. Tournaments are poorly designed to select between second and third place teams, and the silver medal gives greater than normal incentive to get second. Pool play for the final four spots would nearly eliminate the incentive to cheat the system as it were.
August 2, 2012 at 1:41 pm
Roger
Double elimination tournaments with a losers bracket also do a better job at distinguishing 2nd/3rd place teams.
August 1, 2012 at 6:59 pm
DRDR
The particular format used here is actually one where you have several round-robin pools of four teams, the top 2 advance, and it’s known in advance which pools cross over such that the pool winners play the runner-up of the other pool in the first knockout round. This format is also used in any international soccer tournament that has 8, 16, or 32 teams (e.g. Euro, the men’s and women’s World Cup, and Olympic men’s soccer). The women’s doubles badminton competition has 16 teams.
A simple improvement for the 16 or 32-team format is to randomize which round-robin pools are paired for the first knockout round. This greatly reduces but does not eliminate the chance that a team would have a strategic incentive to throw a game and finish 2nd.
August 1, 2012 at 8:13 pm
jeff
I think the world cup and other group-based systems (evem olympic badminton has group play from what i can tell) can be made to fit into the same framework.
Take the world cup. After the group stage we have not a total order but just a partial order. We have 8 group winners and 8 runners up. We complete the ordering by randomly ordering the winners, randomly ordering the runners up and then putting the lowest winner ahead of the highest runner up.
So we dispense with the fixed cross-group pairings in the elimination stage.
August 1, 2012 at 7:50 pm
JWH
Let’s consider a simple case where each competitor has a given ability. It seems that that GM’s mechanism (in each round, the highest seed chooses his opponent, the highest remaining seed chooses his opponent, and so on) satisfies every desirable property except that it gives good teams an incentive to lose to bad ones in order to get them into the tournament. But why not just add a caveat to GM’s mechanism that a team can never choose as an opponent a team it lost to in the round-robin stage? Then good teams really do want to beat bad teams, so that they can play them in the next stage (if they make it to the next stage). Losing to a bad team would mean that they could not play against them in the next stage and that their strongest opponent could. (This logic certainly works when only 4 competitors qualify–I am not sure what happens for 8, 16, etc.)
August 1, 2012 at 8:11 pm
JWH
Actually, even this may not work…the best team may still want to lose to the 5th best team to ensure their entry into the tournament over the 4th best team. (Suppose that the best team sees the 2nd, 3rd, and 4th best teams as roughly equivalent, but sees the 5th best team as much worse–then the best team may prefer to play the 3rd best team for sure and then the winner of 5th/2nd match rather then the 4th best team and the winner of the 2nd/3rd best team match.) But maybe something like this mechanism works with an appropriate sub/supermodularity condition.
August 1, 2012 at 8:48 pm
afinetheorem
I don’t think any system has the desiderata…if losing can result in a weaker team moving on, and if there is nonzero chance of playing every elimination round team, you will want to lose once you have qualified. This can be ameliorated by having the best teams play the worst in the first round of round robin, but this will not totally fix the problem, and only does anything if we agree on ex ante quality with no pairwise effects.
Letting winning teams choose whether to officially count as winners or losers, per Scott, does not give the property that best teams move on.
August 1, 2012 at 10:36 pm
Enrique
what’s the problem here? — the problem one of “strategic behavior” (not cheating per se) — in basketball, you see this occur all the time, i.e. when a team puts on the floor its bench players (in place of its starters) — I am this skeptical if any of the proposed solutions here “scale up” to other sports — I am going to give this some thought and write back in a couple of days
August 2, 2012 at 2:40 am
Links for 08-02-2012 | FavStocks
[…] Let’s Write This Paper – Cheap Talk […]
August 2, 2012 at 10:00 am
ASt
What about something like the UEFA Champions League in which teams play the qualifying round in one of several groups, hoping to get a first or second seed. They don’t know exactly who they’ll play in the knockout stages, though, only that the 8 first seeds will play against one of 8 randomly chosen second seeds. Granted, if the other 7 groups have upsets for the 1st and 2nd seeds, then you still have the same problem, but it’s far less likely for that to happen than for when you know exactly who your second round opponent will be given a 1st or 2nd place group finish.
August 2, 2012 at 12:20 pm
erik
This might work:
In the qualifying round you divide the set of teams into a large (and even) number of groups, say 4 teams per group. Teams play their group mates and are seeded 1 through 4 within their groups. Then groups are then paired at random after the qualifying round is finished (this is the key). Each group’s first seed plays the other group’s fourth seed, and each group’s second seed plays the other group’s third seed.
This alleviates issue #2 in Jeff’s post, provided the number of groups is not too small. Even if a strong team like China is upset in qualifying play, other teams know that the probability of being paired with China’s group is low, and that they will more likely be paired with a group whose seeding accurately reflects its teams’ quality levels. Thus a team would sandbag only if it believed that there were significant upsets in a majority of opposing groups. If the number of teams is large, then such an event is very unlikely.
August 2, 2012 at 12:24 pm
erik
I just realized I didn’t include a qualification mechanism, but that’s easy to do. Assume that qualifying groups have 6 teams instead of 4, and that only the top 4 members of each team move on. Then the resulting groups of 4 are matched as specified above. The same result follows.
August 2, 2012 at 12:36 pm
erik
Another problem: We need to specify how the tournament progresses after the group pairing stage. But as long as all matches following the qualification round are elimination games, then we won’t have to worry about sandbagging.
August 2, 2012 at 1:39 pm
Roger
I just wanted to note that the real reason why all of this was set off was because the Chinese wanted to set up the possibility of a 1-2 sweet. If the Chinese had won their match, they would have been in the same side of the bracket as the other Chinese team. But the team that the Chinese were facing wanted to lose for ease-of-schedule reasons.
This then caused a cascading effect when the Chinese managed to lose their match. Since they were then seeded lower, it became advantageous for later teams to lose their match as well, as being seeded higher meant facing the Chinese. This resulted in multiple “losing competitions” later down the road.
So creating solutions based purely on ability won’t necessarily work, as if any team loses based on a motivation besides “winning it all”, it can cause cascading incentive-problems.
August 2, 2012 at 1:43 pm
David Miller
+Roger: We can’t hope to eliminate non-winning-motivated sandbagging like that of the Chinese team, but if we could construct a mechanism that’s immune to sandbagging the way Jeff described, the incentive problems would not cascade.
August 2, 2012 at 2:10 pm
SX
Jeff: First, the pairing in the second stage (elimination stage) is determined randomly after the first stage (qualifier stage) is over, so that no one can manupilate in the first stage.
Second, add a “bonus policy” (for the second stage), which is an increasing function of the result of the first stage result. Here are three examples.
1. NBA: higher-ranked team gets home-game advantage;
2. Soccer: eliminate penalty kick in case of tie; instead, the higher-ranked team gets the tie-breaker;
3. Olympic badminton: the higher-ranked team gets a head start, e.g., 1st Vs 3rd starts at 2:0; 2nd Vs 2nd starts at 0:0…
This seems a strategy-proof mechanism.
August 2, 2012 at 3:30 pm
JWH
Jeff: GM’s mechanism does not work, even in the special case where the round-robin is used purely for seeding. Consider an example with 8 teams, and suppose the 1st team can always beat all but the 2nd team, the 2nd team always wins except against the 1st and 3rd, and the 3rd is assured victory only against 8. Suppose that the last round-robin match is 1 v. 3, and the ordering is 1,2,3,… if 1 wins, but 1,3,2,… if 3 wins. Then 1 will want to sandbag in order to allow 3 to choose an opponent 3 can beat for sure, so as to ensure that 3 gets to play 2 in the second round (as 1 only cares whether 1 plays 2 or not).
In fact, even allowing the top team to be a dictator is not IC, since I may have an incentive to lose in order to manipulate who chooses and hence give myself a better expected sequence of matches. So it may be that no mechanism that uses the information from the round robin is IC…
August 2, 2012 at 8:24 pm
jeff
John yes. It appears that there is no hope of combating the incentive to manipulate the seed (or qualification status) of other teams. Tonight I will write up a summary and append it to the original post. There is a weak and reasonably useful form of Ic that we can satisfy. On the other hand if we insist on too strong a version we get impossibility.
August 2, 2012 at 3:54 pm
Morality in sport » TVHE
[…] There’s a more technical discussion of incentive compatibility constraints in the design of the competition over at Cheap Talk. […]
August 2, 2012 at 8:16 pm
Jonathan
I would add a twist to the idea that the top seed picks his opponent. The top seed is not allowed to pick the lowest seed.
August 2, 2012 at 9:27 pm
Enrique
Upon further reflection, is this “sandbagging” behavior really a problem? — if so, why? — that is, why is not putting in one’s best efforts or “sandbagging” (as some here have called it) “bad” or “wrongful” — presumably, each player will put in his best efforts in the final round of the competition, so why should we worry about pre-final round “sandbagging” or strategic behavior?
August 6, 2012 at 7:23 am
Michael Nuwer
http://en.wikipedia.org/wiki/West_Germany_1%E2%80%930_Austria_%281982_FIFA_World_Cup%29
“in the 1982 FIFA World Cup, West Germany played Austria in the last match of group B. A West German victory by 1 or 2 goals would result in both teams advancing; any less and Germany was out; any more and Austria was out (and replaced by Algeria, who had just beaten Chile). West Germany attacked hard and scored after 10 minutes. Afterwards, the players then proceeded to just kick the ball around aimlessly for the remainder of the match. Algerian supporters were so angered that they waved banknotes at the players, while a German fan burned his German flag in disgust.[9] By the second half, the ARD commentator Eberhard Stanjek refused any further comment on the game, while the Austrian television commentator Robert Seeger advised viewers to switch off their sets. As a result, FIFA changed its tournament scheduling for subsequent World Cups so that the final pair of matches in each group are played simultaneously.”
August 6, 2012 at 7:46 am
David Miller
+Michael Nuwer: Wow, great story. This would be solved by allowing Austria to forfeit the game down by one goal. It certainly highlights the problems of using goal differentials as a tiebreaker.
August 3, 2012 at 2:09 pm
Luc
Dave Sirlin (a guy who’s set up fighting videogame tournaments, where “fake” matches where one player aims to lose are even more of a failure state) has an interesting article on the matter at http://www.sirlin.net/blog/2012/8/1/playing-to-win-in-badminton.html
August 3, 2012 at 7:54 pm
LP
I’ll explain what I have in mind with an example, let me know where it fails.
Consider the FIFA World Cup – the final phase only.
Stage 0: An 6×8 matrix of 0 and 1 is drawn at random, subject to some “technical” conditions. 8 is the number of groups, 6 is the number of matches within each group, so each cell represents a match in the round-robin phase. 1 means that the match is valid and will count for qualification purposes, and 0 means it’s not. The matrix is not made public.
Stage 1: the round-robin is played as usual
Stage 2: the matrix is published and the rankings are made.
Stage 3: everything else goes on as usual.
August 5, 2012 at 5:46 pm
Anonymous
Isn’t this all about Muller-Satterthwaite Theorem:
August 6, 2012 at 7:04 am
Michael Nuwer
Is there any sport in which a team or player can choose their opponent? Choosing an opponent doesn’t seem like sport, and then there is the problem of respect for one’s opponent. If the top qualifier chooses an opponent, how is is image of disrespect managed?
August 6, 2012 at 7:40 am
David Miller
+Michael Nuwer: I think it would be fun to see the teams struggle with managing the image of disrespect. Just picture the pre-game interviews…
August 11, 2012 at 3:23 pm
Vincent
I know this procedure from the final rounds of the K1 Grand Prix.
The last 8 fighters competing in the finals qualify through minor tournaments. In an event prior to the fights, each fighter gets assigned a numbeer (1-8) by lottery which determines the order of choosing. The first one arbitrarily picks a slot and can only chose when to fight. The second one can then choose to directly fight the first one or pick another of the remaining 7 slots… and so on.
Fighters always strategically place themselves against weaker opponents or opponents that suit their style better. Every once in a while, this is used to make statements to show toughness by picking a very strong opponent in the first round..
http://en.wikipedia.org/wiki/K-1_World_Grand_Prix#Match-Ups
e.g. http://en.wikipedia.org/wiki/K-1_World_Grand_Prix_2009_Final#Match_Ups
August 11, 2012 at 6:34 am
Olympic Game Theory
[…] in the badminton tournament where some teams tried to lose, the cyclists are trying to win so going slow isn’t considered unsporting but it does make […]
August 12, 2012 at 2:46 pm
Enrique
I tried to link this post to the above MR post, but MR doesn’t let me — whatever happened to reciprocal altruism?
August 13, 2012 at 1:17 pm
jeff
I have noticed that too
August 16, 2012 at 3:28 pm
Jeff L
Giving the higher ranked teams a choice in their match ups gives them too much of an advantage when skill is not an ordinal value and some styles perform better than others. This is especially the case when teams from the same group (country in this case) are in the pairings and one sees they have an opportunity to knock out someone who is good against their other team.
The miscellaneous option to let the winner pick a W or L right after the match will avoid fake matches (The Sirlin link above is good), but it still gives an unfair advantage to matches scheduled later.
August 23, 2012 at 2:33 am
Gianni De Fraja
how about:
after the round robin phase, a new draw is made, with (i) either no seeds (ii) or with seeds determined by ranking within the round robin group (eg a group winner will be matched to a group runner-up).
incidentally (ii) is exactly the mechanism used by the (soccer) Champions league in Europe.
September 28, 2012 at 10:04 am
S
So, are you guys actually writing a paper? Please do!
April 21, 2013 at 2:42 pm
Jim Stein
I haven’t read a lot about this, but the problem reminds me of one that seems related. Suppose you have a contest with an elimination round followed by a final round, and a set of rules. My guess is that determining whether that set of rules is incentive-compatible is an NP-hard problem — it seems to resemble satisfiability, which is known to be NP-hard. Also, incentive compatibility, at least the definition I saw in Wikipedia, reminded me of the Gibbard-Satterthwaite Theorem — which raises the possibility that you may be drawing dead. I’m not sufficiently knowledgeable to go beyond that.
October 17, 2013 at 8:56 pm
Olympic badminton is not incentive compatible — revisited | Turing's Invisible Hand
[…] people have floated different ideas for other competition formats, especially in response to a Cheap Talk blog post on the same topic. But I kinda like an idea suggested in a comment on Bobby’s post by… […]
August 30, 2014 at 10:00 am
アレックス・タバロック 「オリンピックゲーム理論」 — 経済学101
[…] バトミントンの試合でわざと負けようとしたあの例のケースとは異なり、スプリントのレースに臨む選手たちはあくまでも勝つために速度を落としている。そのためいくらのろのろと走ったところで「スポーツマンシップに反する」と非難されることはないものの、観客たちは眼前で何ともおかしな光景が繰り広げられる様を目にすることになるというわけだ。 […]
July 24, 2015 at 10:06 am
arnaque rdv
fuyez c’est une arnaque
February 3, 2016 at 12:40 am
xxx
Every weekend i used to pay a visit this web page, as i wish for enjoyment,
as this this web site conations really nice funny
stuff too.
February 3, 2016 at 12:57 am
xxx
Thanks for your marvelous posting! I really enjoyed reading it, you may be a great author.
I will always bookmark your blog and will eventually come back someday.
I want to encourage you to continue your great posts, have a nice morning!
March 7, 2022 at 11:58 pm
アレックス・タバロック 「オリンピックゲーム理論」（2012年8月11日） — 経済学101
[…] バトミントンの試合でわざと負けようとしたあの例のケースとは異なり、スプリントのレースに臨む選手たちはあくまでも勝つために速度を落としている。そのためいくらのろのろと走ったところで「スポーツマンシップに反する」と非難されることはないものの、観客たちは眼前で何ともおかしな光景が繰り広げられる様を目にすることになるというわけだ。 […]
March 8, 2022 at 12:59 am
アレックス・タバロック 「オリンピックゲーム理論」（2012年8月11日） — 経済学101
[…] バトミントンの試合でわざと負けようとしたあのケースとは違って、スプリントのレースに出場する選手たちは、あくまでも勝つために速度を落としている。そのため、どんなにノロノロと走っても、「スポーツマンシップに反する」と非難されることはない・・・ものの、何ともおかしなレース展開が繰り広げられることになるわけだ。 […]