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

About these ads